A zero-knowledge proof (ZKP) is a cryptographic method that allows a person (called Prover) to convince another person (called Verifier) that a statement is true, without revealing any additional information. For example, a ZKP allows you to prove that you are of a certain age, without revealing your actual age.
The ZKP has been proposed by MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff but their original paper was rejected. They eventually won the Gödel Prize.
How a Zero-Knowledge Proof works
To understand ZKP there is an easy to understand example, given by Chalkias and Hearn. The example uses just two balls with different colors, but you can use other identical in shape objects of different colors as well, i.e. a glass of white wine and another (same) glass of red wine.
Imagine you have a color-blind friend. Your friend has a red and a green ball that are otherwise identical when you touch them.
Your friend is not sure if these balls actually differ in color. Your job is to prove to your friend that they are in fact different in color, but nothing else. You do not reveal nothing else to him (i.e. which one is the red and which is the green).
Here's how the zero-knowledge proof works:
Your friend puts these balls behind his back. Then, he brings the balls forward, shows them to you, and returns the balls to his back. You now know in which hand is the red, and in which hand is the green ball. Then your friend may switch the balls behind his back, and shows you a single ball, and asks you: Did I switch the balls?
Remember, your job is to convince your friend that the balls are different in color.
By just looking the ball, you can say with certainty whether or not he did a switch. You can do that because the balls are of different colour.
On the contrary, if the balls were the same colour , there is no way you could guess correctly with probability higher than 50%. For instance, after 1000 switches, the Law of Large Numbers states that you have guessed approximately 50% of the switches correct.
However, if the balls are of different color, you would end up with a very high number of correct statements (over 99%), since you can determine if the switch has been made. Since obtaining such a high score is highly unlikely when the balls are of the same color, your friend can assume that you are stating the truth: the balls are indeed of a different color.
The above proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.
From this example we learn that there are ZKP has three properties:
- Completeness. If the statement is true, an honest verifier will be convinced by an honest prover.
- Soundness. If the statement is false, no dishonest prover can convince an honest verifier.
- Zero-knowledge. If the statement is true, no dishonest verifier learns anything other than the fact that the statement is true.
Note that this demonstration containing two colored balls is interactive: Only you and your friend are convinced by the outcome of the demonstration. If you wanted to proof to others that, indeed, the color of the balls differ, you would have to perform the demonstration again and again.
Therefore, interactive zero-knowledge proof has limited transferability: others are unable to verify the outcome of the demonstration without repeating it. This renders interactive ZKP impractical for a distributed network. Therefore, we would like to make the ZKP non-interactive, where the prover can show the result, and the Verifier can verify the proof themselves.
Zero-Knowledge Succinct Non-interactive ARgument of Knowledge, or ZK-SNARKS, are a ZKP-variant, that requires no interaction necessary between the Prover and the Verifier.
This FAQ answer contains excerpts from Efficient Zero-Knowledge Range Proofs in Ethereum by Tommy Koens, Coen Ramaekers and Cees van Wijk