Introduction
Want to understand how a prover can convince a verifier they know a secret without revealing the secret itself? This tool demonstrates zero-knowledge proofs through two interactive scenarios: the Ali Baba Cave (a physical analogy) and graph 3-coloring (an NP-complete problem). Run rounds, watch the cheating probability drop exponentially, and toggle between honest and cheating provers to see how soundness works. Everything runs in your browser with live statistics.
What this tool does
- Simulate the Ali Baba Cave protocol: a prover enters from a random side, the verifier asks them to exit from a random side, and the prover can only comply if they know the secret (or got lucky)
- Simulate graph 3-coloring: the prover commits to a permuted coloring, the verifier picks a random edge, and the prover reveals only the two colors on that edge
- Toggle between an honest prover (knows the secret) and a cheater (does not know the secret) to observe how the cheating probability converges to zero
- Run single rounds or batch 10 rounds at once, with a live log of each round's outcome (pass/fail or valid/invalid)
- Display the cheating probability after n rounds: (1/2)^n for the cave, (2/3)^n for graph coloring
- Show the three ZKP properties (completeness, soundness, zero-knowledge) with plain-language explanations alongside the simulation
How this tool works
The tool implements two ZKP protocols as client-side simulations. In the Ali Baba Cave scenario, the prover enters from a random side (left or right). A magic door at the back connects the two paths, but only someone who knows the password can open it. The verifier, standing at the entrance, asks the prover to exit from a random side. If the prover knows the password, they can always comply regardless of which side they entered from. If the prover is a cheater, they can only comply if they happened to enter from the side the verifier requests, which happens with 50% probability per round.
The tool simulates this by generating random entry and request sides for each round. When the prover knows the password, every round passes. When the prover is a cheater, a round passes only if the entry side matches the request side. The cheating probability after n rounds is (1/2)^n. After 10 rounds, a cheater has a 0.0977% chance of having passed all rounds. After 20 rounds, it is 0.000095%.
In the graph 3-coloring scenario, the tool uses a fixed 6-node, 10-edge graph with a known valid 3-coloring. Each round, the coloring is randomly permuted (so the verifier cannot link rounds). The verifier picks a random edge, and the prover reveals only the two colors on that edge. If the coloring is valid, the two colors are always different. A cheater with an invalid coloring has at most a 2/3 chance per round (they can satisfy at most 2 of 3 possible edge checks). The cheating probability after n rounds is (2/3)^n.
The tool displays a live round log, statistics (total rounds, passed/failed, cheating probability), and an SVG visualization of the cave or graph with the current round's outcome.
How zero-knowledge proofs work (Goldwasser, Micali, Rackoff 1985)
Zero-knowledge proofs were introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their 1985 paper The Knowledge Complexity of Interactive Proof Systems. They defined three properties that a zero-knowledge proof must satisfy:
Completeness: if the statement is true, an honest prover convinces an honest verifier with overwhelming probability. In the cave, an honest prover who knows the password always passes every round.
Soundness: if the statement is false, no cheating prover can convince the verifier except with negligible probability. In the cave, a cheater has a 50% chance per round, so after 20 rounds the probability of cheating is about 1 in a million.
Zero-knowledge: the verifier learns nothing beyond the truth of the statement. The verifier sees only that the prover exited from the requested side, which reveals no information about the password itself.
The Ali Baba Cave analogy was popularized by Jean-Jacques Quisquater and others in their 1989 paper How to Explain Zero-Knowledge Protocols to Your Children. It maps the abstract protocol to a physical story: a cave with a fork, a magic door at the back, and a verifier who cannot see inside the cave.
Graph 3-coloring is an NP-complete problem. The ZKP protocol for it, due to Goldreich, Micali, and Wigderson, works because the prover can commit to a permuted coloring, reveal only two colors per round, and the verifier cannot reconstruct the full coloring from repeated partial revelations (since the permutation changes each round). This protocol is a building block for ZK proofs for any NP problem, via reduction to 3-coloring.
Modern ZK proofs (zk-SNARKs, zk-STARKs) use polynomial commitments and error-correcting codes to achieve succinctness and non-interactivity. They power privacy coins (Zcash), rollup scaling (zkSync, Polygon zkEVM), and identity systems. The interactive protocols in this tool are the conceptual ancestors of those systems.
How to use this tool
- Choose a scenario: Ali Baba Cave (simpler, 50% cheating per round) or Graph 3-Coloring (more complex, 2/3 cheating per round)
- For the cave, toggle the prover type: Honest (knows the password) or Cheater (does not know the password)
- Click Run Round to execute a single round, or Run 10 Rounds to batch multiple rounds and watch the cheating probability drop
- Observe the round log: each round shows the prover's entry side, the verifier's request, and whether the round passed or failed
- Watch the cheating probability statistic: after n rounds it equals (1/2)^n for the cave or (2/3)^n for graph coloring
- For graph coloring, watch the SVG highlight the randomly selected edge and reveal the two colors on that edge
- Switch to Cheater mode and run 20 rounds. Some rounds will fail, demonstrating soundness: a cheater cannot pass indefinitely
- Click Reset to clear the log and start a fresh simulation
Real-world examples
Honest prover in the Ali Baba Cave
Select the Ali Baba Cave scenario and set the prover to Honest (knows password). Click Run 10 Rounds. Every round passes because the prover can always open the magic door and exit from whichever side the verifier requests. The cheating probability shows 0.0977% after 10 rounds, but since the prover is honest, this is the probability that a cheater would have survived, not the probability of the honest prover failing. The honest prover passes with certainty.
Cheater exposed after multiple rounds
Switch the prover to Cheater (no password). Click Run Round several times. Some rounds pass (when the entry side happens to match the request side) and some fail (when they do not match). Click Run 10 Rounds repeatedly. After 20 rounds, the cheating probability drops to about 0.0001%. A cheater who does not know the password cannot sustain this for long. This is soundness: the probability of a false proof vanishes exponentially.
Graph 3-coloring with a valid coloring
Select Graph 3-Coloring. Click Run Round. The tool permutes the valid coloring, picks a random edge, and reveals the two colors on that edge. They are always different because the coloring is valid. Click Run 10 Rounds: all rounds show VALID. The cheating probability drops as (2/3)^n. After 30 rounds, a cheater would have less than a 1 in 4 million chance of surviving. The verifier learns that the graph is 3-colorable without learning the actual coloring.
Why permutation prevents information leakage
In the graph coloring scenario, each round permutes the color labels (red, green, blue are shuffled). Round 1 might reveal colors 0 and 1 on edge A-B. Round 2 might reveal colors 2 and 0 on edge C-D. Because the permutation changes each round, the verifier cannot correlate colors across rounds to reconstruct the full coloring. This is the zero-knowledge property: the verifier sees many pairs of different colors but never learns which specific coloring the prover committed to.
Comparing cheating probabilities between protocols
Run 10 rounds in the cave (cheating probability (1/2)^10 = 0.0977%) and 10 rounds in graph coloring (cheating probability (2/3)^10 = 1.73%). The cave protocol converges faster because the cheater's per-round advantage is smaller (50% vs 67%). This is why the cave is a better teaching example: it reaches high confidence in fewer rounds. Graph coloring is more general (it works for any NP problem via reduction) but requires more rounds for the same confidence level.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Ali Baba Cave | 1 bit per round, (1/2)^n cheating | Teaching analogy for ZKP concepts |
| Graph 3-Coloring | 2/3 per round, (2/3)^n cheating | ZKP for any NP problem via reduction |
| Schnorr Protocol | Discrete log based, (1/2)^n cheating | Proving knowledge of a discrete logarithm |
| zk-SNARK | Succinct, non-interactive, trusted setup | Zcash, zkSync, Polygon zkEVM |
| zk-STARK | Post-quantum, transparent setup, larger proofs | StarkNet, scalability rollups |
Limitations or considerations
This tool simulates interactive ZKP protocols for education. It does not implement real cryptographic commitments, which are needed to prevent the prover from changing the coloring after seeing the verifier's challenge. In a real implementation, the prover would use a cryptographic commitment scheme (e.g. Pedersen commitments or hash-based commitments) to bind themselves to the coloring before the verifier picks an edge.
The graph 3-coloring protocol requires many rounds for high confidence. After 30 rounds, the cheating probability is about 1 in 4 million. For cryptographic confidence (e.g. 2^-128), you would need over 200 rounds, which is impractical. Real ZK systems use more efficient protocols (Schnorr, Sigma protocols) or non-interactive transforms (Fiat-Shamir) to reduce interaction.
The tool does not implement zk-SNARKs or zk-STARKs, which are the production ZK technologies. Those require polynomial commitment schemes, arithmetic circuits, and trusted setups (for SNARKs) or FFT-based protocols (for STARKs). This tool covers the conceptual foundations, not the engineering.
The Ali Baba Cave is a physical analogy, not a protocol you would deploy. It illustrates the structure of an interactive proof (commit, challenge, respond) but has no cryptographic primitives. The graph coloring protocol is the simplest NP-complete ZKP and is the basis for general ZK via reduction, but it is not used in practice due to its round complexity.
Frequently asked questions
What does 'zero knowledge' mean?
It means the verifier learns nothing beyond the fact that the statement is true. In the cave, the verifier learns that the prover can exit from the requested side, but not how they opened the magic door. In graph coloring, the verifier learns that two adjacent nodes have different colors, but not the full coloring. Formally, the verifier's view can be simulated without knowing the secret, which proves that no information leaked.
Why does the cheating probability drop exponentially?
Each round gives the cheater a fixed probability of passing: 1/2 for the cave, 2/3 for graph coloring. Since rounds are independent, the probability of cheating through n rounds is the product of per-round probabilities: (1/2)^n or (2/3)^n. After 20 cave rounds, the probability is about 1 in a million. After 40 rounds, it is about 1 in a trillion. This exponential decay is what makes the protocol sound.
What is the difference between interactive and non-interactive ZK proofs?
Interactive ZK proofs require the verifier to send random challenges to the prover across multiple rounds. Non-interactive ZK proofs (NIZK) eliminate this interaction, typically using the Fiat-Shamir transform: the prover generates the challenges themselves by hashing the protocol transcript. zk-SNARKs are non-interactive. This tool demonstrates interactive protocols because they are easier to understand visually.
How is this related to zk-SNARKs used in blockchain?
zk-SNARKs (Succinct Non-interactive ARguments of Knowledge) are the production version of ZK proofs. They use polynomial commitments and arithmetic circuits to prove computation correctness without revealing inputs. The conceptual properties (completeness, soundness, zero-knowledge) are the same as in this tool. The difference is that SNARKs are non-interactive, succinct (proofs are a few hundred bytes), and use advanced cryptography (pairing-based commitments, trusted setups).
Can zero-knowledge proofs be used for authentication?
Yes. A prover can prove they know a password without sending it to the verifier. The Schnorr protocol proves knowledge of a discrete logarithm, which can serve as a password equivalent. ZK-based identity systems (like Polygon ID) prove attributes (age, citizenship) without revealing the underlying data. Digital signatures, while not ZK proofs themselves, share the property of proving knowledge of a private key. See the Digital Signature Verifier for signature-based authentication.
Conclusion
Zero-knowledge proofs let a prover demonstrate knowledge of a secret without revealing it, a concept introduced by Goldwasser, Micali, and Rackoff in 1985. This tool demonstrates the two foundational protocols (Ali Baba Cave and graph 3-coloring) with live cheating probability calculations. For related modern cryptography, see the Digital Signature Verifier for authentication, the Homomorphic Encryption Demo for computation on encrypted data, and the Post-Quantum Playground for quantum-resistant algorithms.