The opening story about the sick grandma also seemed to be rather the opposite of a zero-knowledge proof. Each question seemed rather knowledge-y for a 'zero knowledge' exercise.
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.
The best "demonstration" of a Zero-Knowledge proof I've heard is this:
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.
You draw a card from a deck. It's red. You want to convince everyone that it's red without disclosing which card you have drawn. So you take all the black cards from the remaining deck and show them to the public.
I think you're assuming all cards are red or black. I think a better zero knowledge proof analogy using cards would be a sorted deck and saying "I know where your favorite card is" by showing them their card.
I was thinking along those lines, but don't you still make it easier by giving away some details about Waldo's facial expression, the relative size of his head, etc.? Still a pretty illustrative analogy though.
How about get the coordinates of Waldo's position in the image and hash them?
That would work except your friend would have to confirm you know only after finding Waldo himself and hashing it to compare the hash to your hash. The idea is that they don't have to know the secret, but you can demonstrate you know the secret.
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."
Building on the normal discrete log/hamiltonian problems, if you have a random source that can be globally trusted such as some hash, then I think you could pretty easily prove it to the world as such:
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.
Technically that is not "zero knowledge" since the definition of ZK requires interaction (so there is no "publishing" of a proof). What you described sounds like this construction of "non-interactive ZK:"
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).
I'm not quite sure I follow. What does the verifier learn after NIZK? Isn't it the point that the verifier learns nothing other than the prover has some secret knowledge? Seems to me like it's just the same information rescheduled with the help of a PRF.
I agree, in that a proves-for-one ZKP can be converted to a proves-for-n if all n parties can trust the source of randomness used to decide the choice of challenge.
Some other answers (that kind of fix the issue that you might not be showing the exact Waldo):
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.
So if I print out a pic of waldos head and using sleight of hand put that in the hole I have proven something without having to actually find him? Far from a perfect solution.
You can frame the questions in a way that discloses no information to the prover. The questions ideally would have a 50% guess rate either way and leak no info. So, a question like “is her name Alice or Eve?” is a bad one, as you have leaked that her name is one or the other. But, questions like “is her birthday in the first half of the year or second” or “is her birthday on an even day or odd” (modulo there being 31 days in some months) leak no information if you don’t tell them if their answer was right or wrong. You come up with 20 such questions and then give them a pass/fail. No information is leaked, but the prover has a very low chance of guessing 20 50% chance questions correctly in a row.
I think your premise is incorrect. It's not that the verifier doesn't want to leak information (leaking the name alice or eve), it's that the prover doesn't want to leak the substance of the information.
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).
Zk proofs shouldn't leak knowledge to cheating provers or verifiers. Sometimes the verifier has access to a secret, and just needs to confirm the prover does as well.
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.
"Zk proofs shouldn't leak knowledge to cheating provers or verifiers."
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.
Hey, author here! Sorry it didn't gel with you, but I'm happy to defend this example.
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.
We understand that you're trying to make these concepts accessible, which is commendable, but the problem isn't that the example doesn't 'gel' with the critic -- the problem is that the example given doesn't actually support what you're trying to show.
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.
Considering feedback I've gotten in less technical forums, I'm happy with it. I've also linked to more rigorous material throughout the post.
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.
You've given a clear, easy to understand example of something, and you've told people that this something is a zero-knowledge proof.
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).
The fundamental issue is that the stranger is proving something -- the fact that they are close to your family -- by supplying knowledge -- the answer to the questions. Because he or she is proving something by supplying knowledge, this cannot be viewed as a "zero-knowledge proof".
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.
I have a question: when we say, zero-knowledge proofs, they are not really "zero-knowledge" right?
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.
The definition of "zero knowledge" is that for any verifier V, there exists an algorithm S that outputs the same distribution as V without any interaction. Since S has no interaction with the prover, its output has no dependence whatsoever on the prover; and since that output follows the same distribution as V, it follows that V cannot "learn" anything from the protocol.
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.
> I appreciate if you'd prefer mathematical rigor, but if that's the case, you're not the audience.
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.
Agreed, and I tried to strike a balance. Going more technical put off certain reviewers, and going less put off others. In the cryptocurrency space in particular, this is an interesting topic that devs and users are hesitant to even discuss in person, and I wanted to take some of the fear away.
> 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.
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.
> 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.
Consider what happens if I happen to have forgotten my mother's birthday. I meet the person who claims to know them, and I ask a 19 questions about my mother where I know the answer, but I also sneak in the question about when her birthday is.
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.
But doesn't that render the term so broad as to be meaningless? If someone claiming to be a police officer wants to ask me some questions, and I ask to see some ID, and they provide it, by your terms that is a zero-knowledge proof, because they can't share the experiential knowledge of being a police officer.
"Proof" and "zero-knowledge" certainly still have meaning in the situation you've described. If we actually needed to do zk proofs over concepts like that, we'd need defined ontologies and all sorts of logic to codify "the real world".
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.
Well in this case they would be asked to provide a solution to an arbitrarily large NP problem (if they proved P=NP) or a counterexample to the Riemann hypothesis (if they disproved it)
But for the opposite case I don't think it would be easy
Anyone know where the code is for the recent zk-SNARK tests on the Ethereum testnet? I've looked at LibSnark.cpp and its tests, but I'd like to find the code where the transactions were generated and sent to the network.
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.