Zero-knowledge proofs, Zcash, and Ethereum
medium.com
medium.com
I can't think of a way to turn it into a true zero knowledge proof. You'd have to ask questions with answers that revealed nothing about granny -- you shouldn't be able to draw a picture of her or reveal any personal info from piecing together the answers. Which makes its choice as the opening explanation of zero knowledge proofs problematic.
His explanation is that the 'hidden' knowledge is meeting the grandmother and that this meeting cannot be proven through communication. Which is, of course, true. But that's a red herring. The q&a the parties engage in do not prove anything about the meeting. They prove that one party knows things about the granny, not that any particular meeting took place nor that the party has ever met her.
In short, it's neither zero-knowledge nor a proof.
I admit that the flawed opening plus the constant attempts to personify every concept, interspersed with giant irrelevant images mean that I couldn't finish it.
A zero-knowledge proof is about a prover convincing a verifier they have some knowledge, without sharing the knowledge. In the case, the prover certainly didn't share the knowledge, and convinced the verifier. Bingo.
I appreciate if you'd prefer mathematical rigor, but if that's the case, you're not the audience. The point of this post is to help make the topic more accessible- there are plenty of rigorous explanations aimed at those interested in the crypto.
What knowledge prover didn't share?
Going back to your public-private key example, the way someone proves their identity is by giving you some information that only the private key can generate.
However, in the event that the person is not who they say they are, don't the gain some information (that the thing they gave it is incorrect)?
A way I see to counter this is to make it indistinguishable whether or not the information was correct to the prover. Instead of saying, "incorrect password", you would give them access to an empty account.
In schemes that rely on computational assumptions (eg, hashing & signing with a nonce) I don't think that's an issue.
Here is a concrete example protocol and proof that it is ZK:
The prover P will prove knowledge of a discrete logarithm z for G = g^z.
1. P chooses a random x and sends h=g^x to V. 2. V chooses a random c, r and sends C = g^r h^c to P. 3. P chooses a random s and sends A = g^s to V. 4. V sends (c,r) to P. 5. P checks C = g^r h^c and if the check passes, sends Z = cz+s and x to V. 6. V checks h=g^x and g^Z = A G^c.
To prove zero knowledge, we use the following simulator S:
A) S performs steps 1-4. B) S rewinds V to step 3 (think of the internal copy of V as a virtual machine; S can take a snapshot etc.). C) Since S already knows (c,r), it picks Z randomly and sends A = g^Z G^(-c), and continues with the remainder of the protocol. Note that A G^c = g^Z G^(-c) G^c = g^Z, so the proof will pass. D) After S sends Z, it outputs whatever the internal copy of V outputs.
This simulator works because after Step 2, the verifier is bound to c (the g^r h^c value is a Pederson commitment, which is binding as long as V does not know the discrete logarithm of h). Once S knows c, it can "cheat" to create a valid A,Z despite not having knowledge of the discrete logarithm of G. Since the internal copy of V is "convinced" by the proof, it will output whatever it would have output following a real interaction -- at each step it sees the same distribution of messages it would have seen in the real world (V is not aware of the fact that it was rewound once -- again, think of a VM).
As to your question about the prover, note that the prover will never learn anything from the protocol; you can apply similar reasoning and construct a "simulator." For P the simulator is trivial -- since there is no secret inputs for V, the simulator can just follow each verifier step honestly, without ever having to rewind P, and will then output whatever P outputs. Typically that simulator is ignored in the case of zero knowledge proofs because it is trivial.
There is a rather big gap between "have never heard about ZKP" and "mathematician comfortable reading complicated proofs all day long". I suspect here on HN there are enough people who wouldn't mind some more rigor in the examples - in fact, some good articles mentioned here do just that.
I don't mean to say that for this subject there aren't any materials available with more rigor than an introductory article, but some more wouldn't hurt.
What was the knowledge they had but didn't share?
It wasn't that they knew the verifier's mother, because they shared that.
It wasn't that the verifier's mother was in hospital, because they shared that.
So what was it?
> In our example, knowledge can’t be directly revealed, because we don’t have an easy way to “serialize” and share human knowledge, like having met your mother — just the loose approximations of verbal and visual language.
You can't share experiential knowledge of knowing another human being. You can claim to have met someone, but human experience isn't easy to transmit like a traditional private key.
My point is mostly that it can be a subjective thing between the prover and the verifier. The verifier simply needs to be convinced, without making it easier for a cheating provers or future cheating provers, and the prover needs to not help a cheating verifier.
With this scheme I use the 19 questions to check that you know my mother (that is the 1-bit of information that we are trying to prove), but with the bonus question, I get to learn something new about my mother. This shows that the proof communicated more than just the 1-bit of information.
A real zero knowledge proof means that a person who is listening in on the proof doesn't glean any information either - at the end of the exchange, the only thing that has been proved is the single bit of information, and it has only been proved to the verifier. If you want a realistic example of this, then the cave example given on wikipedia is good for this. Note that at the end of the proof, an outside observer wouldn't be able to repeat the proof, nor would they even know whether the prover and verifier were in cahoots and actually just acted out the proof using a pre-agreed set of "random" choices.
There may be a few things in common, but the actual details are more nuanced to a point where you may be doing your readers a disservice by convincing them that the story represents a zero-knowledge proof without acknowledging where the scenarios differ.
If you have a minimal example of what you would change or acknowledge to improve the post I'm happy to hear it. As it stands, explaining the "why" of zk proofs and an approximation of the "how" seems reasonable to me.
Anyone who doesn't know what a zero-knowledge proof is will give you positive feedback, because they had an easy time understanding the example you presented.
People who do know what a zero-knowledge proof is will correctly point out that the thing you described is not a zero-knowledge proof.
I think this explains the gap you're seeing between the feedback here and the feedback in "less technical forums." It's difficult to come up with real-world examples of zero-knowledge proofs, but there are two good examples on Wikipedia and one here (the "Where's Waldo?" example).
I think my loose narrative could be turned into a proper zk proof with few restrictions- care to give it a try?
The minimal example of what would have to change would be something along the lines of this: rather than asking specific questions, you would want the stranger to be able do something that only a family friend could do. But, in this case, it's silly to get them to do that when what you want is that knowledge -- who they know, how they know them, etc. -- so you can verify it against what you already know. The question of whether or not someone is a family friend is just not the type of question that these proofs are used for.
I would throw out that example and use something like this: a lock box that anyone could close -- but only someone with knowledge of a secret code could open it. Someone could prove that they know the code by simply opening the box. It's a contrived example, yes, and could probably use some extra pizazz, but I think that's because you'll find most real-world situations simply don't work well with these sorts of proofs.
Also, is somewhat relevant: https://news.ycombinator.com/item?id=14261067
I'm not well-versed on the subject, but I don't think your example is a valid zero-knowledge proof, since the prover is leaking a knowledge to the verifier (the parity of her birthday, the semester of her birthday, etc).
Correct me if I'm wrong.
We're stretching what was supposed to be a useful analogy pretty far here. The idea was that the knowledge of details about your mother can act as a proxy for the secret, experiential knowledge of having met her, which is not current shareable between humans. If the verifier picked good questions, asks enough of them, and never reuses them, this is a decent approximation of the functionality of a zk proof.
Anyway, we're off the rails, but one thing I know is that I'm proud no one on HN has made a "your mom" joke yet. Kudos all around.
It is trivial to show that ZK proofs leak nothing to the prover: the verifier has no secret input to leak. This is somewhat technical but it comes down to the actual definition of ZK, which is that for any verifier V, there exists an algorithm S that has the same output distribution as V but which never interacts with the prover (at least in the case where the proof is valid). The existence of that algorithm implies that the verifier "learns nothing" -- because whatever it can compute after the interaction is something it could have computed a priori.
As a result, whatever inputs the verifier has cannot actually impact the proof itself -- otherwise it would be impossible to satisfy such a requirement. Using your example, suppose the prover can only succeed if its secret input is equal to the verifier's secret input. No algorithm that does not interact with the prover could have the same output distribution as the real verifier, because that distribution will depend on the prover's input (i.e. whether or not the input is equal to the verifier's). So you cannot actually accomplish that task with a zero knowledge proof; or taking the contrapositive, the verifier has no secret inputs in a ZK proof.
(If you are wondering what the verifier would "learn" in such a situation, one answer would be a transcript of the interaction itself.)
So, if we were to try to apply the ZK definition to the prover, we would have something trivial: take the prover P and run an "internal" copy of P in some bigger algorithm that does not interact with the verifier. Since there is no secret verifier inputs, that bigger algorithm can just follow the protocol and output whatever P outputs. Since the protocol is just being followed exactly, P has no way to distinguish the simulation from the real interaction, so the output distribution is unchanged. In other words, the prover necessarily learns nothing from the protocol.
Suppose you and a friend are looking for Waldo in a "Where's Waldo?" book page. You found Waldo first, and would like to prove that, but you don't want to ruin the fun for your friend-- you shouldn't provide any information that would take away from their challenge of finding Waldo themselves. How would you do that?
<Take a minute to think about it>
You take a cardboard several times larger than the "Where's Waldo" frame, and cut a hole the size of Waldo's head right in the middle of it. You then place the book on one side of the cardboard so that the only thing visible from the other side is Waldo's head. You show it to your friend. Notice you have proven you know the solution to "Where's Waldo" without revealing any information about the problem which they haven't known before. That to my understanding is the core concept of ZK proofs.
How about get the coordinates of Waldo's position in the image and hash them?
My understanding is that ZKPs require you to prove only to the verifier that you have the secret information. If proof is convincing to the whole world, that's "too much knowledge" for ZKP.
See the Wikipedia article [1] where they use the example of the ring cave with a wall halfway through that requires a secret password. If you wanted to prove to the world that you have the secret, it's enough to go in the left side and come out the right (or vice versa). But that isn't (traditional) ZKP because it proves to everyone that you can bypass the wall.
Thus (per discussion page), they have to use a more complicated example, where no one gets to see which side you went in, and the verifier calls out which side you must come out of. [2] In that case, it's only convincing to the verifier. Everyone else (for all they know) can't rule out the possibility that the verifier told you which sides they'd call in advance, allowing you to always go the side that doesn't require you to bypass the wall.
OTOH, maybe zcash-style currencies aren't zero-knowledge in that (stronger) sense, because you are trying to convince the whole world of something!
That's also why ZKPs have the general format:
A) randomize the problem,
B) split the knowledge into two pieces where each is useless by itself,
C) commit to each piece, and
D) allow the verifier to pick which piece you must reveal.
How would that work with your Waldo example? Something like:
1) Prover puts a picture behind the cardboard in a position they can't change.
2) Verifier chooses which challenge to give:
A) Take off the cardboard and reveal the original picture.
B) Punch a hole where Waldo is.
3) Repeat until verifier confidence is high enough.
Only a legit prover can always pass. A faker can pass if they cheat and use a fake picture only when the verifier chooses B. (Edit: or if the verifier always picks A)
This is not convining to people other than the verifier because they can argue "Come on, you could have told the prover which stream of options you'd take."
[1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B...
[2] Each time you play, you have a 50/50 chance to pass by dumb luck, but the odds of passing every round decay exponentially in the number of rounds.
1. Create a series of n problems P, based on some secret S, and and publish them. 2. Get some source of randoms everyone can trust, such as PRF(P) where PRF is some expensive secure hash function 3. Publish the proof of knowledge revealing the the piece specified by the random source.
Anyone can create P but only someone with knowledge of S can tractably pass step 3 because being able to do so implies either being able to predict the output of the hash function in which case the PRF is insecure or or getting winning 2^n coin tosses even if an attacker has an infinite pool of half revealed challenges he can pull from.
https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
NIZK is a very different concept from ZK, because the verifier does learn something, in the sense that the verifier has received a string it could not compute on its own. In ordinary ZK the verifier cannot compute anything after running the protocol that it could not have computed beforehand (so it gains nothing from the interaction).
Make a copy of the page and have your friend draw a unique repeating pattern on the entire back. Cut out Waldo from the page and have your friend verify the design “signature” on the back.
For a better design signature have your friend paint the back of the copy with a color made from three unique rgb values they choose that you don’t know. When you cut Waldo out of the copy have them verify the color matches their unique color.
Another qualification is that details about Waldo are public so simply describing the stripes on his shirt and such doesn’t help prove to your friend that you’ve found him.
Would they win the Millennial Prize for that problem?
But for the opposite case I don't think it would be easy