What is a Zero-Knowledge Proof, and what does the "Where's Waldo?" example illustrate?
A protocol where one party (the prover) convinces another party (the verifier) that they know a secret, without revealing the secret itself.
Three required properties of a ZK proof:
- Completeness — if the prover really knows the secret, an honest verifier will be convinced.
- Soundness — if the prover doesn't know the secret, they cannot convince the verifier (except with vanishingly small probability).
- Zero-knowledge — the verifier learns nothing beyond the fact that the prover knows the secret.
The Waldo example: Alice claims she can find Waldo in a "Where's Waldo?" picture. She wants to convince Bob, but won't show him where (because Bob wants to find Waldo himself).
The trick: Alice takes a huge piece of cardboard, larger than the picture, and cuts a small hole exactly where Waldo is. She covers the picture with the cardboard so only Waldo is visible through the hole. Bob sees Waldo, sees that he's looking through the cardboard, and concludes Alice does know where Waldo is — but he doesn't know where on the original picture the hole was aligned with. He learns nothing about the location.
Key distinction:
"Überzeugen ist nicht Beweisen." — Convincing is not (mathematically) proving.
ZK proofs convince with overwhelming probability after enough rounds, but they don't constitute a mathematical proof transferable to a third party. If Bob is later asked "where's Waldo?", he honestly can't answer — even though he's now sure Alice knew.
Real-world ZK applications:
- Authentication without password disclosure (e.g. Schnorr identification).
- Privacy-preserving cryptocurrencies (Zcash uses zk-SNARKs to prove a transaction is valid without revealing sender/receiver/amount).
- Decentralised identity (prove you're over 18 without revealing your birthdate).
- Voting (prove a ballot is well-formed without revealing the choice).
Tip: ZK proofs are one of those "this can't be possible" cryptographic results until you see the construction. The original paper is Goldwasser-Micali-Rackoff 1985 ("The Knowledge Complexity of Interactive Proof Systems"); two of its authors, Goldwasser and Micali, went on to win the 2012 Turing Award.