5 ms·

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

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.

stepik777 9y ago
> the prover certainly didn't share the knowledge What knowledge prover didn't share?
QML 9y ago
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.
- mhluongo 9y ago
  Note the verifier doesn't need to share the outcome with the prover- that does, indeed, open certain problems up to enumeration. In schemes that rely on computational assumptions (eg, hashing & signing with a nonce) I don't think that's an issue.
- betterunix2 9y ago
  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.
avmich 9y ago
> 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.
- mhluongo 9y ago
  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.
dghf 9y ago
> 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. So what was it?
- mhluongo 9y ago
  I addressed this in the post > 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.
  - dghf 9y ago
    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.
    - mhluongo 9y ago
      "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.
  - TheNewAndy 9y ago
    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.
johnhenry 9y ago
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.
- mhluongo 9y ago
  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.
  - tomglynch 9y ago
    Hi there, I think the reply above by yonilevy is a very solid example and could be used in your text (with yonilevy's permission of course).
  - smarx 9y ago
    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).
    - mhluongo 9y ago
      Perhaps I should've said "considering the feedback I've gotten from technical and non-technical reviewers". I think my loose narrative could be turned into a proper zk proof with few restrictions- care to give it a try?

stepik777 9y ago

> the prover certainly didn't share the knowledge What knowledge prover didn't share?

QML 9y ago

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.

mhluongo 9y ago
Note the verifier doesn't need to share the outcome with the prover- that does, indeed, open certain problems up to enumeration. In schemes that rely on computational assumptions (eg, hashing & signing with a nonce) I don't think that's an issue.
betterunix2 9y ago
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.

avmich 9y ago

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

mhluongo 9y ago
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.

dghf 9y ago

> 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. So what was it?

mhluongo 9y ago
I addressed this in the post > 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.
- dghf 9y ago
  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.
  - mhluongo 9y ago
    "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.
- TheNewAndy 9y ago
  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.

johnhenry 9y ago

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.

mhluongo 9y ago
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.
- tomglynch 9y ago
  Hi there, I think the reply above by yonilevy is a very solid example and could be used in your text (with yonilevy's permission of course).
- smarx 9y ago
  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).
  - mhluongo 9y ago
    Perhaps I should've said "considering the feedback I've gotten from technical and non-technical reviewers". I think my loose narrative could be turned into a proper zk proof with few restrictions- care to give it a try?