Exhibit 02 · Graph 3-Coloring

EXHIBIT 02⬡ COMMITMENTS SIMPLIFIED

Graph 3-Coloring ZKP

Proving a valid coloring exists without revealing which colors go where · Goldreich, Micali, Wigderson 1986

✓ Completeness ✓ Soundness ✓ Zero-Knowledge

Think of this as proving a map has been colored correctly without handing over the whole answer key. The prover hides every node's color, then the verifier points to just one connecting line and asks to see only the two colors at its ends.

If those two touching nodes are different colors, that local check passes. Because the hidden colors are shuffled each round, the verifier never gets enough information to reconstruct the whole map, but repeated spot-checks still make cheating harder and harder.

Rigor note: in full GMW-style protocols, each round commits to all vertex colors using a cryptographically binding commitment scheme (e.g., H(color ‖ nonce) with a collision-resistant hash). This exhibit replaces that with truncated base64 — enough to show the commit-then-reveal flow, but not binding or hiding in a cryptographic sense. The verifier interaction model and soundness amplification ((5/6)^k) are preserved faithfully.

FULL GRAPH VIEW

Nodes show simplified commitments (base64, not real hashes) — colors hidden

PROVER — committed coloring

Press "New Round" to commit.

Node	Commitment (simplified)
0	0x…
1	0x…
2	0x…
3	0x…
4	0x…

VERIFIER — challenge & reveal

Confidence0.00%

P(cheat) = (5/6)⁰ = 100%

— protocol log —

What the verifier learns: Only that the challenged endpoints differ. Random color permutation each round prevents accumulating a global coloring. The pedagogical simplification is in the commitment layer (base64 encoding, not a binding hash), not in the soundness argument: after k independent rounds, P(undetected cheat) = (5/6)^k. A production version would replace simCommit with SHA-256(color ‖ nonce) to guarantee binding and hiding.