“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.