Chapter VI · Part II — Zero Knowledge
Σ-Protocols: Schnorr 📐
The graph-coloring dance was general but chatty. Now meet the sleek, algebraic heart of practical zero knowledge: a three-move conversation — commit, challenge, respond — shaped like the Greek letter Σ, proving "I know the secret exponent" while never sending it.
The statement
Chapter 2 gave us the one-way street: everyone can see y = gˣ mod p, nobody can recover x. So this is the perfect identification statement:
STATEMENT : "I know x such that y = g^x (mod p)"
WITNESS : x (the discrete log of y — stays secret forever)
Think of y as Peggy's public key and x as her password. She wants to log in to Victor's server by proving knowledge of x — with zero bytes of x ever crossing the wire.
The three moves
- Commit. Peggy picks a fresh random r (a "nonce" — one-time, never reused!) and sends A = gʳ mod p. She has publicly bound herself to r without revealing it — a Pedersen-flavored envelope in exponent land.
- Challenge. Victor fires back a random c. This is the crucial live randomness that a cheating Peggy can't pre-predict.
- Respond. Peggy answers s = r + c·x (mod p−1). The exponents are one-time-pad encrypted: r masks c·x.
Victor accepts iff gˢ ≡ A · yᶜ (mod p). Expand it: g^(r+c·x) = gʳ · (gˣ)ᶜ — the equation can only balance if s genuinely involved x.
🔍 Deeper dive · the challenge width is the soundness dial
In the cave, each challenge carried one bit of unpredictability — soundness error 1/2, so you needed dozens of rounds. Schnorr's challenge c is a whole field element: t bits of unpredictability, soundness error 2⁻ᵗ per round. Bump t to 256 and a single round already leaves a liar odds of 2⁻²⁵⁶ — Chapter 5's many-round choreography compresses into one commit–challenge–respond exchange. "Σ-protocol" is precisely the name for 3-move protocols whose soundness error you set by widening the challenge; that dial is what makes them efficient enough to run on every login, every signature.
🧪 Run the protocol yourself
Real big-number math (a 61-bit Mersenne prime — the real world just uses ~256 bits). You are Victor: you choose the challenge c. Flip to your turn mode to play Peggy and compute s by hand.
Why this is zero knowledge
Stare at the transcript (A, c, s): pick any random c and s you like, compute A = gˢ / yᶜ, and you've manufactured a perfectly valid-looking transcript — without knowing x. Since you can fake it alone, seeing the real one teaches you nothing. (Formally: honest-verifier zero knowledge; Fiat–Shamir inherits it.) And if a cheater could answer two different challenges for the same A, subtracting their responses leaks x itself — special soundness. A liar must survive on one coin flip per round, exactly like the cave.
Fiat–Shamir: fire the verifier
The bottleneck of interactive proofs is the waiting: Peggy needs Victor awake to supply c. In 1986, Fiat and Shamir noticed something cheeky: the hash function from Chapter 3 can play Victor. Instead of asking for a challenge, Peggy computes it herself:
c = H( g ‖ y ‖ A ) ← the "random oracle" mints the challenge from the transcript
Because of the avalanche effect, Peggy can't grind A until c becomes favorable — every tweak to A re-randomizes c completely (that's the hash-grinder lesson!). The conversation collapses into a single message: a digital signature. This exact construction — a Schnorr signature — secures Bitcoin's Taproot upgrade and the passkeys in your phone.
🔍 Deeper dive · what Fiat–Shamir costs — transferability returns
Chapter 1 celebrated proofs that convince only the verifier in the room. Fiat–Shamir deletes the room: anyone, forever, can re-check the signature — which is exactly what signatures are for, and exactly why a Fiat–Shamir proof of your age (Chapter 8) must additionally bind to a fresh verifier challenge and your holder key: otherwise the bar could forward your "18+" artifact to data brokers, and it would keep verifying. One transform, two opposite privacy properties. Protocol design is deciding which one your application needs — interactive identification (non-transferable) versus non-interactive signatures (transferable by design).
🔍 Deeper dive · Schnorr in production
Bitcoin's Taproot upgrade (BIP340) is a Schnorr variant over secp256k1 — the check becomes s·G = R + e·P with the challenge hashed from (R, message, pubkey): same commit-challenge-respond, elliptic-curve dialect. FIDO2/WebAuthn passkeys in your phone and laptop prove credential possession with Schnorr-style signatures. And the same 3-move machine generalizes: DLEQ proofs show that two Diffie–Hellman pairs share the same hidden exponent — the glue inside key-exchange and credential protocols (Chapter 8 uses its cousins). The linearity that makes verification a single equation also enables batch verification (thousands of signatures for ~the cost of one), adaptor signatures, and clean threshold signing (FROST) — the reasons the industry keeps picking Schnorr over ECDSA.
Nonce discipline — where real systems actually break
The one unforgivable sin: reusing r across two signatures. Two challenges c₁ ≠ c₂ with the same A give s₁ − s₂ = (c₁ − c₂)·x — divide and out pops the private key. This isn't theory: the PlayStation 3 ECDSA keys and many a blockchain wallet leaked exactly this way. Fresh randomness, always.
📌 Week 6 — key takeaways
- Σ-shape: commit A = gʳ → challenge c → respond s = r + c·x; verify gˢ = A·yᶜ.
- Zero knowledge because transcripts are forgeable: pick c, s freely, set A = gˢ/yᶜ — no x required, so real transcripts can't leak x.
- Soundness = challenge width: t-bit challenges give 2⁻ᵗ error per round; a 256-bit c makes one round enough (vs the cave's dozens).
- Fiat–Shamir replaces Victor with H(transcript) → non-interactive signatures (Taproot, passkeys) — at the price of transferability.
- Never reuse r: two signatures with one nonce surrender the private key by subtraction — extraction as an attack.
🎯
Checkpoint: Sigma Moves
In Schnorr, why does the verifier check g^s ≡ A · y^c (mod p)?
- To encrypt the challenge for transport.
- Because g^(r+c·x) = g^r · (g^x)^c — the equation balances only if s truly combined r with the secret x.
- Because it compresses the numbers.
- To check that r was truly random.
It's an exponent-algebra identity that becomes a proof of knowledge: producing a balancing s requires ability to compute with x.
The response s = r + c·x doesn't leak x because…
- r is a fresh one-time random value that perfectly masks c·x — like a one-time pad in the exponents.
- because s is reduced mod p.
- because x is prime.
- because Victor deletes s after checking.
One equation, two unknowns (r, x) — and r is uniform and destroyed. Reuse r even once, though, and the masking evaporates (see the callout above!).
What does the Fiat–Shamir transform actually do?
- Compresses the proof to 200 bytes.
- Encrypts the transcript with Victor's key.
- Replaces the verifier's random challenge with c = H(transcript), collapsing the interaction into a non-interactive signature.
- Adds a trusted setup ceremony.
Hash-as-coin-flip: unpredictable (avalanche), ungrindable, and reproducible by any verifier later. The whole conversation becomes one message.
Peggy signs two messages reusing the same nonce r. An observer collects (A, c₁, s₁) and (A, c₂, s₂). What can they do?
- Nothing — the signatures are still individually valid.
- Only detect that r was reused.
- Forge arbitrary messages with 50% success.
- Compute x = (s₁ − s₂) / (c₁ − c₂) mod (p−1) — the private key, fully extracted.
Subtract: s₁ − s₂ = (c₁ − c₂)·x. Special soundness is a feature against cheaters and a lethal bug against sloppy nonce hygiene.