What are zero-knowledge proofs (ZKPs)?
A zero-knowledge proof (ZKP), also called a zero-knowledge protocol, is a mathematical technique to verify the truth of information without revealing the information itself. The method was first introduced by researchers from MIT in a 1985 paper.1
How do zero-knowledge proofs work?
A popular example to illustrate the basic idea behind ZKPs is as the following:
Suppose you (the prover) have a color-blind friend (the verifier) that cannot distinguish a green and a red ball from each other (have zero knowledge about whether the balls are different colors). You need to prove that the colors of the balls are different but your friend needs something more than your words to be convinced. A ZKP method for this problem would be like this:
- Your friend takes the balls and lets you see which ball is in which hand.
- Then, they either switch the balls between their hands or not behind their back.
- They then present the balls to you and ask you whether they switched the balls or not. As you can distinguish the green ball from the red one, you can easily give the correct answer.
- Your friend is not convinced. You have a 50% chance to correctly guess whether they switched the balls or not and the balls can still be the same color.
- However, if they repeat this several times, eventually, the probability of you correctly guessing whether they switched the balls or not each time would be very low. This enables your friend to verify that the balls are different colors without knowing the actual colors of the balls.
A series of cryptographic algorithms are used in the real-world applications of ZKPs to enable the verification of a computational statement. For instance, using ZKP methods, a receiver of payment can verify that the payer has sufficient balance in their bank account without getting any other information about the payer’s balance.
Another popular example that illustrates how interactive proofs work can be found in the Wikipedia article on Ali Baba’s cave story by Jean-Jacques Quisquater.