Interactive zero knowledge 3-colorability demonstration

Abstraction: Interactive demo of zero-knowledge proof via graph 3-coloring

Key points:

• Demonstrates the canonical zero-knowledge proof protocol using graph 3-colorability as the hard problem
• User plays as verifier: picks an edge, prover reveals the two endpoint colors without exposing the full coloring
• Prover is permitted to permute the color assignment between rounds, which is essential to preserve zero-knowledge (preventing full coloring reconstruction)
• A "confidence" metric tracks the decreasing probability that a cheating prover got lucky across rounds
• "Turbo" mode automates repeated rounds to build confidence quickly
• Illustrates the key ZK property: verifier gains no knowledge beyond the truth of the statement

Connections: Mit · Zero Knowledge Proofs · Graph Coloring

Source: http://web.mit.edu/~ezyang/Public/graph/svg.html