Exhibit 02 · Graph 3-Coloring

EXHIBIT 02⬡ REAL SHA-256 COMMITMENTS

Graph 3-Coloring ZKP

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

✓ Completeness ✓ Soundness ✓ Zero-Knowledge

Cryptographic honesty: each region is committed with a real SHA-256(color ‖ nonce) digest, and on reveal the opening is re-hashed and checked against the published commitment. The challenge-reveal logic and soundness amplification ((5/6)^k) of ZK graph coloring are preserved faithfully. The zero-knowledge property is exhibited rather than asserted: the extractor bench at the bottom of this page runs two real attacks — a bounded SHA-256 preimage search against the published digests, and a full enumeration of the colourings the transcript leaves possible — and prints only what they returned. The graph and colour palette are small for a legible walkthrough, not for deployment security.

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 — H(color ‖ nonce) with a collision-resistant hash. This exhibit implements exactly that with window.crypto.subtle.digest('SHA-256', ...) over a fresh 16-byte nonce per node, and verifies each opening on reveal. It remains a teaching model (small graph, three colours, no reveal-window enforcement), but the commitment layer itself is genuine.

FULL GRAPH VIEW

Nodes show real SHA-256 commitments (truncated for display) — colors hidden

The prover commits to a random re-coloring of the map, then reveals just the two regions on a border the verifier picks. Valid borders never share a color.

PROVER — committed coloring

Press "New Round" to commit.

Node	Commitment (SHA-256, truncated)
0	0x…
1	0x…
2	0x…
3	0x…
4	0x…

VERIFIER — challenge & reveal

Confidence0.00%

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

— protocol log —

EXTRACTOR BENCH — attack the hiding property

Everything above asserts that the coloring stays hidden. This bench lets you attack it. Both attacks run for real against the digests and transcript this page just produced — every number below is measured, none is written in advance.

Attack 1 · brute-force the commitments

Enumerate (colour, nonce) openings in order, hash each with real SHA-256, and match against the five published digests. The same attacker function runs against the exhibit's 16-byte nonce and against a deliberately weakened 8-bit nonce, so the difference you see is the nonce space and nothing else.

Nonce width	Openings that exist	Real hashes tried	Fraction searched	Openings recovered	Expected cost to break one
16 bytes (this exhibit)	—	—	—	—	—
1 byte (weakened control)	—	—	—	—	—

Not run yet.

Attack 2 · reconstruct the coloring from the transcript

Take only what the verifier legitimately saw — the challenged edges and the opened colour pairs — then enumerate all 3⁵ = 243 colorings and keep every one no round rules out. A candidate survives a round if some palette permutation maps it onto what was opened, because the permutation is secret and fresh each round.

Knowledge held	Colorings still possible	Best single guess
Nothing (before any round)	243	0.41%
This verifier's transcript	—	—
Transcript + broken commitments (fills in after Attack 1)	—	—
The witness itself	1	100%

Challenge at least one edge, then run the extractor.

— extractor log —

What the verifier learns: Only that the challenged endpoints differ. Random color permutation each round prevents accumulating a global coloring. The commitment layer is a real binding+hiding SHA-256(color ‖ nonce) — the reveal step re-hashes each opening and rejects any that does not match the published digest. After k independent rounds, P(undetected cheat) = (5/6)^k. The extractor bench above turns that claim into a measurement: the transcript-only candidate set never falls below the 18 proper colorings of this graph, which is exactly the statement being proved, while breaking the commitments collapses it to 6. This remains a teaching model in scale (5 nodes, 3 colours, no reveal-window enforcement), not the soundness argument.