Zero-Knowledge Proofs (ZKPs)
ZKPs are a subset of Interactive Proofs (IPs) that require no knowledge to be exchanged between the prover and the verifier, while introducing a very small chance that the proof might actually be incorrect.
Interactive Proofs differ from traditional proofs in several ways:
- Interactive proofs require interaction betwen the prover and verifier. They are not static.
- Interactive proofs are dependent on the relationship and communication between the prover and verifier. They are not (necessarily) transferable to a third-party.
- Interactive proofs admit a tiny probability that the proof might actually be incorrect. They are probabilistic.
A brief definition, from this paper:
Interactive proofs (IPs) and arguments are cryptographic protocols that enable an untrusted prover to provide a guarantee that it performed a requested computation correctly. Introduced in the 1980s, IPs and arguments represented a major conceptual expansion of what constitutes a “proof” that a statement is true.
Traditionally, a proof is a static object that can be easily checked step-by-step for correctness. In contrast, IPs allow for interaction between prover and verifier, as well as a tiny but nonzero probability that an invalid proof passes verification. Arguments (but not IPs) even permit there to be “proofs” of false statements, so long as those “proofs” require exorbitant computational power to find. To an extent, these notions mimic in-person interactions that mathematicians use to convince each other that a claim is true, without going through the painstaking process of writing out and checking a traditional static proof.
Celebrated theoretical results from the 1980s and 1990s such as IP = PSPACE and MIP = NEXP showed that, in principle, surprisingly complicated statements can be verified efficiently. What is more, any argument can in principle be transformed into one that is zero-knowledge, which means that proofs reveal no information other than their own validity. Zero-knowledge arguments have a myriad of applications in cryptography.
An Proof From Intuition That ZKPs Exist
From Brent Anderson.
- Alice wants to prove to color-blind Bob that two otherwise identical balls differ in color: one is red, and one is green.
- Bob can't see the difference between the colors, and has no way of knowing which is which (beyond what Alice says about it)
- Bob takes the two balls in his hands and puts them behind his back. He then mentally flips a fair coin - half the time, he will switch the balls, half the time he will leave them alone.
- Bob shows the balls to Alice. Alice tells him if he switched or did not switch. This is trivial for Alice to do, but impossible for Bob to do. Even so, Bob also knows whether or not he switched - it is trivial for him to verify Alice's claim whether he switched or didn't.
- For the first guess, it's a 50% chance that Alice is a lucky guesser. The second guess, 25% chance. If they play this game 10 times in a row, there is a 1/1000 chance that Alice is that lucky. Playing beyond that is effectively a rounding error away from being proven as truth.
- Conclusion: Alice has proven that the balls are not the same, and Bob has verified her claim without being able to measure anything about the balls themselves. Alice has not necessarily proven what shade of red or green - just that she can tell the difference, and that there is a difference, but nothing is proven about qualitatively what that difference amounts to.