â€śHoney Badger BFTâ€ť - hilarious

Greg Maxwell and Peter Wuille are planning to implement zero-knowledge in bitcoin core, comparing with bitcoin or other crytocurrencies, are there anything which canâ€™t be implemented in bitcoin, or whatâ€™s the special thing in Zcash, I think itâ€™s the real value of Zcash blockchain, and itâ€™s why miners will come to mine Zcash. I am not an expert on cryptocurrency, could you brief this thing.

If confidential transactions are implemented in bitcoin I think only the amounts will be privateâ€“not the addresses. In Zcash the addresses and the amount is private. Even the total supply of coins is private. Someone can elaborate but thatâ€™s what I currently understand.

Edit: Or is CT different than what the article is discussing: Zero Knowledge Contingent Payment (ZKCP)?

The total supply of Zcash is the same as Bitcoin

I read that and then read Greg Maxwellâ€™s blog post, and finally I read the post that talked about the graph coloring ZKP by Matthew Green.

In that last post, Matthew shows how you can show that you know the answer to the problem by running a valid protocol to solve the problem and then show a random edge. This needs to be done edge^2 number of times.

So going back to the Sudoku example, how can this work without revealing the Sudoku solution?

Obviously you canâ€™t reveal a random square on the Sudoku solution squares^2 number of times without actually just showing the answer in itâ€™s entirety, and you canâ€™t change your solution to the Sudoku between every challenge because there is only one valid solution (or up to ten in some extreme examples).

Iâ€™m sure Iâ€™m missing something hereâ€¦

Update: It doesnâ€™t provide the solution of a particular 16x16 Sudoku, it just provides a solution to an unspecified 16x16 Sudoku. Is that right?

Update2: Looking at the code, itâ€™s definitely solving a specific Sudoku of a random configuration and size. So ya, Iâ€™m not understanding the proof generating portion. It doesnâ€™t help that Iâ€™m not very familiar with Rust.

What maxwell and wuille are doing is an atomic swap of information and money. Thatâ€™s a very different thing from private payments.

They both use zero-knowledge protocols to accomplish their goals, but they are very different goals.

This may be useful: Zero-knowledge sudoku proof - YouTube

Itâ€™s very similar in nature to the graph colorability interactive ZKP.

Iâ€™m not sure if the proof that Greg and Maxwell use is interactive or not (I havenâ€™t looked at it closely).

Thank you Austin. So you show a row, column, or group, and since you have all 9 numbers that shows that you werenâ€™t cheating, even though you donâ€™t reveal the position of the numbers and thereby spoil the puzzle.

So what prevents you from cheating by just writing in all of the remaining numbers in a given column, row, or group and then presenting them while not knowing the order yourself?

That must be what the â€śCommitmentâ€ť is for, since hashes clearly wouldnâ€™t work.

It looks like Commitment Schemes, like Asymmetric Cryptography, is something Iâ€™ll just need to accept work in their own mysterious way.

â€śThat must be what the â€śCommitmentâ€ť is for, since hashes clearly wouldnâ€™t work.â€ť

Yes (to everything before the comma) and No (to everything after the comma).

â€śIt looks like Commitment Schemes, like Asymmetric Cryptography, is something Iâ€™ll just need to accept work in their own mysterious way.â€ť

No! Never give up! This isnâ€™t as hard as you think. Once it clicks itâ€™ll actually feel â€śeasyâ€ť. To clear one thing up, you arenâ€™t really committing to your solution (directly). You are committing to two things: (1) a permutation of your solution and (2) the permutation you used. You only ever reveal one or the other to the verifier (never both, or else theyâ€™d be able to compute your solution).

Letâ€™s address this first:

â€śâ€¦since hashes clearly wouldnâ€™t work.â€ť

They do work, but you have to add in some randomness. Here is a (general) commitment scheme that uses only randomness and hashes:

Suppose I want to commit to a string x.

I choose a large (say, 128bit ) random number r and keep it secret.

I compute C = H( r || x ) where H is your favorite cryptographically secure hash function.

I give you C. Thatâ€™s my commitment.

You cannot invert H, and so you cannot discover x. Indeed, you canâ€™t even brute force H to find x because you donâ€™t know r (and nobody is ever going to be able to brute force 128 bits of randomness in our lifetimes).

Now when it comes time for me to reveal my string x to you, I reveal both x and r.

You know Iâ€™m not cheating because you can check that C = H( r || x ) yourself.

So thatâ€™s a cool commitment scheme. Hereâ€™s how weâ€™d use it for the ZKP sudoku situation. Letâ€™s say you are the prover and Iâ€™m the verifyer:

(1) You choose a random permutation, phi, of the numbers 1-9 (letâ€™s assume weâ€™re playing for a 9x9 sudoku puzzle). You keep phi secret.

(2) You apply phi to your solution, S, of the sudoku puzzle.

{Note that the result, phi(S) is another solution to *a* sudoku puzzle (though not necessarily the one you started with). So it is perfectly safe to show me any one row, column, or group of phi(S). As long as you never reveal to me your permutation phi, Iâ€™ll never learn anything about your solution S. But weâ€™ll get to that in a minute.}

(3) Next you commit to every digit in phi(S) separately using the â€śgeneral commitment schemeâ€ť I showed above. Youâ€™ll end up with 81 separate commitments.

(4) You also create another commitment: you commit to phi.

(5) You hand over to me to me all 81 sudoku position commitments, along with your commitment to phi. So youâ€™ve now committed to every position in the solution phi(S), as well as the permutation you used.

Now itâ€™s my turn. At this point I can do exactly one of two things. I can either

(a) choose any one row, column, or group at random and have you show me whatâ€™s under the hood (and you canâ€™t lie to me because youâ€™ve committed and Iâ€™ll catch you if youâ€™re lying). or

(b) I can choose to have you reveal phi, along with all the positions in the sudoku puzzle that were already filled in at the start.

Note that if you do either ONE of those things, I learn nothing about S.

In the case of (a) I learn only stuff about phi(S).

In the case of (b) I learn about phi, but thatâ€™s useless to me without knowing anything about phi(S)

Obviously youâ€™ll never reveal both or I can compute your secret solution S.

Think about what it would take for you to try to trick me into thinking you have a solution to my sudoku puzzle when you donâ€™t.

If you started with something that wasnâ€™t even a solution to *any* sudoku puzzle, I might catch you if I choose (a). (One of the rows, columns, or groups wouldnâ€™t add up). So the threat of me choosing (a) makes you have to have a real solution to some sudoku puzzle.

If you started with something that didnâ€™t match *my* empty sudoku puzzle, I might catch you if I choose (b). So the threat of me choosing (b) makes you have to start with with *my* puzzle.

We run this protocol over and over and over again until Iâ€™m satisfied that you arenâ€™t lying to me. Each time you choose a new random phi, and new random numbers for each of your 81 commitments.

Each iteration I learn nothing about your solution.

Each iteration is a chance for me to catch you lying (if youâ€™re lying).

Run enough iterations and I learn nothing and will (very likely) catch you if you are lying.

/wall of text

A commitment is just a salted hash? There must be something more to this, because you wouldnâ€™t be able to verify any of the rows, columns, or groups if I donâ€™t give you the random number I used.

Is that what you are referring to when you say, â€śyou do either ONE of those thingsâ€ť? I give you either the random number that salts each individual square hash *or* I give you the random number that salts the phi hash (on request)?

I assume thereâ€™s only 2 128 bit random numbers on each iteration, is that right?

Thanks, I really appreciate your explanation.

A commitment is just a salted hash?

Yes, thatâ€™s one way to do it.

There must be something more to this, because you wouldnâ€™t be able to verify any of the rows, columns, or groups if I donâ€™t give you the random number I used.

Sorry for the confusion. You *do* give me the random number you used.

I assume thereâ€™s only 2 128 bit random numbers on each iteration, is that right?

You choose a separate random r for each value you want to commit.

So to commit to each value in a 9x9 sudoku puzzle, youâ€™ll have to choose 81 random r values. Each square in the sudoku puzzle is committed to separately.

The when you want to reveal the secret value behind a particular square, you reveal the secret value and the corresponding r.

So in our case, since we are committing to 81 secret values and 1 permutation phi, weâ€™ll need 82 total random values (râ€™s) on each iteration of the protocol.

If you want to reveal to me a given row, you tell me all the value and all the râ€™s for that row.

Ok. I think I got it now. I see why proofs tend to be so ginormous.

Maxwell says in the blog that ZKCP is interactive, but the Github page says it uses a zk-SNARK (Succinct Non-interactive ARgument of Knowledge).

Do you know what thatâ€™s about?

I havenâ€™t had a chance to look at their work yet.

I also havenâ€™t studied *arguments of knowledge*, *SNARGs*, or *zk-SNARKs* yet.

Iâ€™m still working my way there in what little spare time I find.