The Ali Baba Cave
The Ali Baba Cave is the most intuitive introduction to zero-knowledge proofs — a physical metaphor that makes the abstract idea of "proving without revealing" immediately concrete. Originally described by Jean-Jacques Quisquater and others in 1989, it has become the canonical first example of a ZKP.
The Cave
Imagine a cave shaped like a ring, with a single entrance at the front. Inside, the ring splits into two corridors: Path A on the left and Path B on the right. Both paths lead to the same inner chamber, separated by a magic door in the middle. The door can only be opened by someone who knows the secret word.
From the outside, you can only see the entrance — you cannot tell which path anyone inside has taken.
The Setup
- Peggy (Prover) — knows the secret word that opens the magic door.
- Victor (Verifier) — wants to be convinced Peggy knows the word, without learning the word himself.
The Protocol
Each round of the proof has three steps.
Step 1 — Peggy Enters
Victor waits outside. Peggy walks into the cave and randomly goes down either path A or path B. Victor cannot see which one she chose.
Step 2 — Victor Calls
Victor walks to the entrance (but not inside) and shouts which side he wants Peggy to come back from: "Come out from A!" or "Come out from B!" — chosen randomly with equal probability.
Step 3 — Peggy Exits
If Peggy is already on the called side, she simply walks back out. If she is on the opposite side, she uses the magic door to cross to the other path and then exits. Either way, she emerges from the correct side.
A cheater who doesn't know the secret word is stuck on whichever path they entered. They can only hope that Victor calls the side they happen to be on — a 50% gamble each round.
Try It Yourself
Step through the protocol below. You play both Peggy and Victor — watching the same events from both perspectives simultaneously.
Click Begin Round to start.
The magic door in the centre connects Path A and Path B. Only someone who knows the secret word can pass through it.
Figure 3. Interactive simulation of the Ali Baba Cave zero-knowledge proof. Peggy's random path choice is shown to you (the reader) but is invisible to Victor. Both parties' perspectives are displayed simultaneously for clarity. Original protocol by Jean-Jacques Quisquater et al., 1989.
Why Is This Zero-Knowledge?
Completeness
An honest Peggy who truly knows the secret word will always succeed. Whatever side Victor calls, she can reach it — directly if she is already there, or through the door otherwise. An honest prover always convinces an honest verifier.
Soundness
Suppose Peggy is cheating and does not know the secret word. She cannot open the door, so she is stuck on whichever path she entered. Victor's call is independent and random — there is exactly a $\frac{1}{2}$ probability he calls the side she entered. The probability of a cheater surviving one round is therefore $\frac{1}{2}$. After $k$ rounds:
$$P(\text{cheater not caught after } k \text{ rounds}) = \left(\frac{1}{2}\right)^k$$Zero-Knowledge
What does Victor actually learn from a successful round? He shouted a direction, and Peggy emerged from that direction. But he could have simulated this entire transcript himself — pick a random side (A or B), imagine a person coming from that side, write it down. The simulated transcript is statistically indistinguishable from a real interaction.
Because Victor could produce the same-looking evidence without ever talking to Peggy, the real interaction conveys zero information about the secret word.
How Many Rounds?
The soundness error is exactly $\left(\tfrac{1}{2}\right)^k$ — far better per-round than graph coloring or Sudoku, because there are only two possible challenges.
| Rounds ($k$) | Soundness error $\left(\tfrac{1}{2}\right)^k$ | Verifier confidence |
|---|---|---|
| 1 | 50% | 50% |
| 5 | 3.1% | 96.9% |
| 10 | 0.098% | 99.9% |
| 20 | $\approx 10^{-4}$% | $\approx 100\%$ |
| 30 | $\approx 10^{-7}$% | $\approx 100\%$ |
Twenty rounds push the soundness error below one in a million — far faster convergence than the 27-group Sudoku ZKP or even the graph coloring protocol. The trade-off: the cave ZKP is pedagogically perfect but not practical for complex statements. Real-world ZKPs (zkSNARKs, zkSTARKs) achieve near-zero soundness error in a single non-interactive round, using cryptographic hardness rather than repetition.