a zero-knowledge proof
Suppose you want to convince a friend that you know the secret password to a locked door, but you absolutely do not want to tell them the password. A zero-knowledge proof is a protocol that achieves exactly this paradox-sounding feat: it lets a prover convince a verifier that a statement is true, while revealing nothing whatsoever beyond the bare fact that it is true — not the secret, not the witness, not even a hint that could shorten the verifier's own search.
It is a special kind of interactive proof with one extra demand. Besides completeness (a true statement gets accepted) and soundness (a false one is almost surely rejected), it must satisfy the zero-knowledge property: the verifier learns nothing it could not have produced on its own. This is made precise by a simulator — a procedure that, knowing only that the statement is true, can fake a transcript of the whole conversation that is indistinguishable from a real one. If the verifier could have manufactured a convincing transcript by itself, then the real conversation taught it nothing. The classic illustration is the colour-blind friend and two balls: you can prove the balls are different colours by having them swap or not behind your back and asking you to say whether they swapped — you answer correctly only by seeing the colours, yet the friend never learns which ball is which colour.
Zero-knowledge proofs are a cornerstone of modern cryptography. They underpin password and identity systems that prove you know a secret without exposing it, and they are the technical heart of privacy-preserving blockchains and verifiable computation, where one party proves a transaction or computation is valid without revealing its private inputs. A landmark result shows every statement in NP has a zero-knowledge proof, assuming one-way functions exist. That assumption is the honest caveat: zero-knowledge security rests on unproven hardness assumptions, the same ones that underlie cryptography generally.
To prove a graph is 3-colourable without revealing the colouring: the prover commits to a randomly recoloured version (sealing each vertex's colour in a locked box), the verifier picks one random edge and asks the prover to open just its two endpoints, sees they differ, and accepts. One edge leaks no colouring; if the prover lacked a valid colouring, some edge would match and a random edge would catch it. Many rounds make cheating hopeless, yet the verifier never sees the whole colouring.
A zero-knowledge proof convinces you a statement is true while teaching you nothing else.
'Zero-knowledge' does not mean the verifier learns nothing at all — it learns the one bit that the statement is true. It means it learns nothing BEYOND that, in particular not the secret witness. Security typically rests on unproven assumptions like the existence of one-way functions.