search

matter-labs-archive / sapling-crypto

Zcash "Sapling" cryptography gadgets along with additions. Uses our Ethereum compatible bellman under the hood
Other
15 stars 9 forks source link

Implement arbitrary size Waksman network #2

Closed shamatar closed 5 years ago

shamatar commented 5 years ago

Main application of such network is an efficient proof than one set is a permutation of another. There are two parts than need to be implemented

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

This issue now has a funding of 200.0 DAI (200.0 USD @ $1.0/DAI) attached to it.

shamatar commented 5 years ago

@xiaods

Some details for you:

Just post to this thread if you have more questions. Due to completely different approach of how libsnark and bellman&sapling-crypto define the constraints and witness calculation I'd suggest to write from scratch.

Sincerely, Alex

skywinder commented 5 years ago

@xiaods Please, let us know if everything is clear. so we will approve you for this work :+1:

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Work has been started.

These users each claimed they can complete the work by 4 months, 4 weeks from now. Please review their action plans below:

1) antonyip has been approved to start work.

Hi,

Not sure if this bounty is now open after the previous worker stopped work. I've looked through the https://hal.inria.fr/inria-00072871/document and understand the concept behind it.

From the brief description that you gave to xiaods, I understand that you would like an implementation of the AS Wakesman network.

I would like to know what the actual deliverables are as they seem unclear to me.

Learn more on the Gitcoin Issue Details page.

xiaods commented 5 years ago

@antonyip not yet to me. you can working on it. i have not decide to applied this task.

shamatar commented 5 years ago

@xiaods

Some details for you:

  • Description of Waksman network for arbitrary (not only power-of-2) sizes is here https://hal.inria.fr/inria-00072871/document
  • Geometry of the network should be (in my opinion) made recursively, by using a proper enum.
  • Use of this primitive it allows to take two sets and prove that one is a permutation of another. Another alternative approach would be to sort & compare, but it's usually more expensive

  • Most of the parts of saping-crypto consist of two parts:

    • Separate module that provides function to construct a primitive and calculate witness (e.g. determine a geometry of the network). This module usually knows nothing about R1CS, variables and constraints
    • Gadget itself, that allows to synthesize the constraints and calculate a witness along the way

  • I see two possible workflows (ways of use of the primitive and so semantics):

    • Take two sets and prove the equivalence up to permutation. In this case assignments to the individual "switches" in a Waksman network should be computed as a part of the witness.
    • Take a set and some binary vector of "switches" - in this case output should be a permuted set

Just post to this thread if you have more questions. Due to completely different approach of how libsnark and bellman&sapling-crypto define the constraints and witness calculation I'd suggest to write from scratch.

Sincerely, Alex

As I've described and by the same logic as for many other parts of this gadget library, each in-snark function has a "normal" counterpart, that does some witness generation, for example.

So, I see at least these three parts to be necessary for use:

I hope in clarified a question, @antonyip

antonyip commented 5 years ago

Hi @shamatar,

Thanks for the reply.

For the function that takes 2 sets of elements and computes a bitstring. Is there a concept to do this or by brute forcing a combination by trial and error?

I can complete the task if you approve me on gitcoin.

shamatar commented 5 years ago

@antonyip I’ve never seen an exact algorithms (although there may be one in libsnark), but due to geometry of permutation network you can start with a first element, choose some routing, that will fix you a number of bit in a bitstring, than try the second element, etc. Since it’s recursive, you can abort earlier in case of inability route an element to the place you want.

Sincerely, Alexander

antonyip commented 5 years ago

Got it. Please approve worker on gitcoin so that I can start working.

spm32 commented 5 years ago

Just approved you @antonyip :)

shamatar commented 5 years ago

@antonyip There is a routing algorithm in libsnark https://github.com/scipr-lab/libsnark/blob/master/libsnark/common/routing_algorithms/as_waksman_routing_algorithm.cpp It takes an integer permutation as an input, that is what’s necessary. I would add explicit fields “min” and “max” to the permutation structure, but in general it’s what you would need to calculate the witness for bitstring. Also, when I use terms like “bitstring” it’s a reflection of it’s essence, but you can keep it in any data structure you like.

antonyip commented 5 years ago

Hi @shamatar ,

The construct is done. I've checked it by hand to size 6. Not sure where to implement the tests (Well.. technically it wasn't part of the bounty.. but let me know how to implement it and I will do so..)

Calculate witness is currently done by bruteforce.. Still studying the algorithm.. Unable to figure out the fomula for this

Have a look and let me know if you have any concerns.

Regards, Anton

gitcoinbot commented 5 years ago

@antonyip Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

@antonyip Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@antonyip due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@antonyip due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Work for 200.0 DAI (200.0 USD @ $1.0/DAI) has been submitted by:

  1. @antonyip

@ceresstation please take a look at the submitted work:

shamatar commented 5 years ago

I've started an implementation myself in the corresponding branch, should be finished this week

shamatar commented 5 years ago

6 cover this, closing

gitcoinbot commented 4 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

The funding of 200.0 DAI (200.0 USD @ $1.0/DAI) attached to this issue has been approved & issued to @antonyip.