Chapter V · Part II — Zero Knowledge

Interactive ZK Proofs 🎨

The cave was theatre. Now we do the real thing: a full zero-knowledge proof of an actual mathematical statement, where you sit in the verifier's chair, issue the challenges, and watch a cheater get shredded by probability.

Statements, witnesses, and NP

A proof system talks about statements — claims that are either true or false:

"This graph can be colored with 3 colors so no edge connects two same-colored nodes." (true/false)
"I know an x with gˣ ≡ y (mod p)."
"This Sudoku grid has a solution." / "This transaction balances."

The witness is the secret evidence — the actual coloring, the exponent, the solved grid. NP is precisely the class of statements whose witnesses are short enough to check quickly. The theorem powering this whole field: every NP statement has a zero-knowledge proof (Goldreich–Micali–Wigderson, 1986). Master it for one NP-complete problem — graph 3-coloring — and you've mastered it for all of them.

The graph coloring protocol

Peggy claims graph G is 3-colorable, and she knows a coloring. Victor doubts. Colors are named red, blue, gold — but any relabeling is equally valid, and that's the secret sauce:

Commit. Peggy randomly permutes her color names (red↔blue↔gold shuffle) and sends Victor one commitment per node — sealed envelopes from Chapter 4. Victor learns nothing: any 3-coloring permutes into any other relabeling with equal probability.
Challenge. Victor picks a random edge and demands both endpoint envelopes.
Respond. Peggy opens exactly those two. Victor checks: commitments verify, and the colors differ. Repeat from step 1.

Why it works: an honest Peggy always passes — completeness. A Peggy without a valid coloring must commit to something; whatever she commits to, at least one edge is monochromatic, so a random challenge catches her with probability ≥ 1/|E| per round — soundness. And the revealed pair is always "two random distinct colors" — precisely what Victor could have generated himself — zero knowledge.

🔍 Deeper dive · which primitive buys which property The protocol is a machine assembled from exactly the parts you already own — and each part is responsible for one guarantee:

Ingredient	Property it provides	Why
Verifier's random challenge	soundness	cheaters can't pre-prepare answers to unpredictable questions
Fresh random permutation each round	zero knowledge	each round's view is a uniformly random relabeling — nothing accumulates
Commitment binding	soundness	after sealing, Peggy can't recolor to fit the challenge
Commitment hiding	zero knowledge	opaque envelopes leak nothing about the coloring

This is the commit-and-prove pattern: nearly every modern ZK system is this table wearing different algebra.

🧪 The Verifier's Chair

Your job: challenge edges. Each round, Peggy re-commits with a fresh secret permutation. Flip on cheat mode to face a Peggy who never had a valid coloring — she fills envelopes with random junk and prays you don't probe a bad edge. Catch her.

Soundness math With m edges, a cheating round survives with probability ≤ 1 − 1/m. After n independent rounds: (1 − 1/m)ⁿ. Our graphs have ~9 edges — 30 rounds drives cheating below 3%. Real deployments repeat hundreds of rounds, or use bigger soundness gaps per round.

🔍 Deeper dive · extraction — why convincingness implies knowledge Here's the deep algebraic reason soundness works. Suppose Peggy could answer two different challenges — two different edges, or in Schnorr's case two different c — about the same commitment. Both answers verify, and subtracting the two verifying equations cancels the fresh randomness, leaving the witness exposed in the difference (you'll perform exactly this subtraction in Chapter 6, and it's how leaked nonces leak keys). So a strategy that convinces too well contains the witness: an "extractor" that rewinds Peggy and asks twice could pull the secret out. This upgrades "the statement is true" to "the prover knows why" — the K in "argument of knowledge", and the reason these systems can authenticate people, not just facts.

The simulator: zero knowledge made rigorous

"Victor learns nothing" can't just be vibes — here's the formal trick. Suppose Victor could record the whole conversation: commitments, challenged edges, opened colors. Now imagine a simulator: a program with no Peggy and no coloring at all that picks a random edge, picks two random distinct colors, seals fake envelopes for those two nodes, and prints the same style of transcript. If honest transcripts and simulated ones are indistinguishable, then the transcript contains nothing that required the secret — because the simulator didn't have it.

Don't take my word for it. Play: one transcript below is from a real honest run, the other was forged by the simulator with zero knowledge of any coloring. Spot the real one.

Why you can't win "Spot the Real" Honest Peggy reveals a random permutation's colors — uniform random distinct pairs under fresh envelopes. The simulator picks uniform random distinct pairs under fresh envelopes. Identical distributions. Any distinguishing strategy would be a statistical test between two things that are statistically the same. Your coin-flip performance is the zero-knowledge property, experienced firsthand.

🔍 Deeper dive · honest Victor vs malicious Victor Our simulation argument assumed Victor flips fair coins — an "honest verifier". A malicious Victor might choose challenges adaptively to harvest information: always probing edges adjacent to a node he's tracking across rounds. The full definition still survives: a simulator with the power to rewind Victor (re-run him on modified randomness) can manufacture equally convincing transcripts, so even adaptive verifiers learn nothing. In practice, protocols ship as "HVZK + special soundness" — a pair which, for 3-move protocols, implies zero knowledge against malicious verifiers. File the word rewinding: it's the classic simulator superpower, and it's also how the extractor from the previous box works.

🔍 Deeper dive · NP-completeness — one protocol to prove everything Sudoku, 3-coloring, circuit satisfiability and thousands of other problems inter-translate: an efficient conversion (a reduction) turns any of them into any other. 3-coloring is NP-complete — every claim with an efficiently checkable witness can be dressed up as a coloring instance, possibly much larger but still polynomial. Prove the coloring protocol zero-knowledge (this chapter) and the Goldreich–Micali–Wigderson theorem hands you zero knowledge for all of NP at once. Modern SNARKs are, at heart, industrial-scale reductions into friendlier algebra — Chapter 7 is that story.

Where this leads

The coloring protocol is beautiful but expensive: ~50 rounds × 20 commitments each, and every round needs Victor awake. Two directions fix this, and they're the next two chapters:

Σ-protocols (Chapter 6): sleek 3-move proofs (commit → challenge → respond) for algebraic statements like "I know x in y = gˣ", plus the Fiat–Shamir trick that removes the verifier entirely.
SNARKs (Chapter 7): proofs of arbitrary computations, compressing thousands of rounds into a single 200-byte artifact verifiable in milliseconds.

📌 Week 5 — key takeaways

The recipe: commit to a randomized encoding of the witness → verifier challenges a random local piece → respond → repeat with fresh randomness.
Soundness per round ≥ 1/|E| because a bad commitment must contain a monochromatic edge; repetition compounds: (1 − 1/m)ⁿ → 0.
Zero knowledge = simulatability: you played the simulator and couldn't beat 50/50 at spotting real transcripts — that IS the definition, experienced.
Binding commitments buy soundness; hiding commitments plus fresh permutations buy zero knowledge — the commit-and-prove pattern behind every modern ZK system.
Answering two challenges on one commitment exposes the witness (extraction) — "proof of knowledge", not just proof of truth.
GMW '86: 3-coloring is NP-complete, so every NP statement — Sudoku, transactions, circuits — inherits zero knowledge.

🎯

Checkpoint: The Real Thing

Why does Peggy re-permute the color names every round?

To make the commitments shorter.
Because the colors would fade otherwise.
So each round reveals a uniformly random relabeling — no matter how many rounds Victor sees, he can never stitch together the actual coloring.
To increase the catch probability for cheaters.

Without fresh permutations, two rounds revealing overlapping nodes would leak relative color information. Randomized relabeling keeps every round's view identically distributed — the ZK engine.

A cheating Peggy commits to a random junk coloring with at least one monochromatic edge. Victor challenges one random edge. Catch probability?

At least 1/m, where m = number of edges.
Exactly 50%.
1/3, because there are three colors.
Zero — she can always answer convincingly.

The bad edge is somewhere among m edges; a uniform random challenge hits it with probability ≥ 1/m. Repetition compounds this into overwhelming soundness.

The simulator demonstrates zero knowledge because…

it runs faster than the real protocol.
it produces indistinguishable transcripts while possessing no witness — so the transcript can't encode any knowledge of the witness.
it uses encryption on all messages.
it convinces Victor without Peggy being online.

That's the definition: zero knowledge ⟺ exists a simulator producing an identically (or computationally) distributed view. You experienced it as "I can't beat 50% at spotting the real one".

Graph 3-coloring is NP-complete. Why does that matter for ZK?

It makes the protocol faster.
It means the protocol is quantum-safe.
It proves P = NP.
Any NP statement can be translated into a coloring instance — so a ZK protocol for coloring gives ZK for every efficiently checkable claim.

GMW: one NP-complete problem in zero knowledge ⟹ all of NP is in zero knowledge. That's why Sudoku, private transactions, and circuit satisfiability all inherit the magic.

← previous

IV · Commitment Schemes

next chapter

VI · Σ-Protocols: Schnorr 📐