Schnorr proves one fixed algebraic sentence. But real life asks messier questions: "did this program execute correctly?", "does this transaction respect every rule?", "is this credential valid?". zk-SNARKs — succinct, non-interactive arguments of knowledge — let you prove any computation, and shrink the whole conversation into a few hundred bytes.
Computation becomes arithmetic
The first move is translation: every program you want to prove things about gets compiled into an arithmetic circuit — a dag of just two gate types, + and ×, over the modular field from Chapter 2 (in practice, numbers mod a 255-bit prime). Inputs on the left, the claim to check on the right.
program → arithmetic circuit → constraints
"age ≥ 18" → comparators, bit-decomp → thousands of × and +
"a·b == 35" → one multiplication gate → one rank-1 constraint
The witness is a satisfying assignment: values for every wire making the output true. Proving in zero knowledge = proving you hold a satisfying assignment without showing it — the 3-coloring idea, industrialized.
🔍 Deeper dive · "true" vs "I know why" — arguments of knowledge
A proof of satisfiability shows some valid witness exists. A proof of knowledge shows the prover actually holds one. The difference matters: "a vault combination that opens this lock exists" is trivia; "I know the combination" is authorization. SNARKs are knowledge proofs by construction — the extractor idea from Chapter 5 scales up: a prover that convinces the verifier can be rewound to yield its witness. Now decode the acronym you've been hearing: Succinct (tiny proofs, ms verification), Non-interactive (one message, thanks to Fiat–Shamir), ARgument (sound only against efficient provers — fine in practice), of Knowledge.
🧪 Circuit Lab
Three puzzles. Fill the input wires; gates propagate live and the output wire must hit the target. What you're doing by hand — hunting for a satisfying assignment — is exactly the NP witness the prover hides.
⚡Arithmetic Circuit Labpuzzle 1 / 3
Puzzle 1 — find x with x·x = 49 (mod 97)
Why only + and ×?
Together they're Turing-complete — subtraction is adding a negative, comparisons decompose numbers into bits (a ≥ gate becomes ~8 bit constraints), and even SHA-256 unrolls into tens of thousands of multiplications. Clunky for humans, perfect for algebra: each multiplication gate becomes one rank-1 constraint of the form (linear combo of wires) × (linear combo) = (linear combo) — the "R1CS" you'll see in SNARK tooling.
🔍 Deeper dive · the arithmetization zoo
How programs are flattened into constraints is a whole design space, and the family names you'll meet are dialects of one idea. R1CS (Groth16): one constraint per multiplication, minimal proofs, circuit-specific setup. Plonkish (PLONK and descendants): custom gates plus copy-constraints and lookup tables — precomputed menus that make range checks, comparisons and hash functions dramatically cheaper (exactly what selective disclosure needs). AIR (STARKs): the computation becomes rows of a running state evolving under fixed rules — arithmetization as a spreadsheet across time; transparent and post-quantum-friendly at the cost of bigger proofs. They all reshape the computation until a polynomial identity can assert "every rule was followed".
Polynomials and the random-point check
The second move is the deep one. The prover encodes all constraints into polynomials, where the statement is true iff a certain combination — call it P(x) — is identically zero. By the Schwartz–Zippel lemma, a non-zero polynomial of degree d has at most d roots, so checking P at one uniformly random field point catches a liar with probability ≥ 1 − d/p — with p ≈ 2²⁵⁵, that's essentially certainty, replacing thousands of checks with one.
🎲Random-Point Liar Catcher0 samples
> field: integers mod 967 (a toy prime)\n> honest polynomial P(x) = 3x³ + 42x + 7\n> liar claims Q(x) = P(x) + (x−11)(x−12)(x−13)\n> P and Q agree at exactly 3 of 968 points: x = 11, 12, 13.\n> sample away…
Each sample is one evaluation. A liar survives a sample only by landing on a root.
The SNARK endgame
One problem remains: the verifier shouldn't learn P's coefficients (that's the witness!). Solution — polynomial commitments: the prover commits to the polynomial (a Pedersen-flavored envelope from Chapter 4, scaled up), then reveals only its value at the verifier's secret random point. Commitment + random-point check + Fiat–Shamir = a 200-byte proof, verifiable in milliseconds, that an entire computation was honest. All four primitives from Part I, fused.
🔍 Deeper dive · polynomial commitments in one breath
How do you commit to a polynomial and later open it at one point without revealing it? KZG (the pairing-based scheme under PLONK): during setup, powers of a secret τ — τ¹, τ², … — are encrypted into group elements; a commitment is essentially the polynomial "evaluated at τ inside the encryption", and opening P(z) = v takes a constant-size quotient proof checked by a pairing. No-setup alternatives: FRI (hash-based folding, used by STARKs — Chapter 3's primitive carrying the whole load) and inner-product arguments (Bulletproofs, inside Monero's range proofs). Every one of them is Chapter 4's envelope generalized from bits to polynomials.
🔍 Deeper dive · recursion and folding — proofs that verify proofs
Once proofs are cheap to verify, a proof can contain the verification of other proofs: an outer SNARK attests "these 10,000 inner proofs all check out". That's how zk-rollups compress a day of blockchain activity into ~200 bytes that a dumb contract verifies in milliseconds. Folding schemes (Nova, Halo2's IPA lineage) go further: instead of nesting proofs, they algebraically merge running proof instances into one — recursion's amortization without recursion's overhead. The signature move of modern ZK engineering: verify lazily, aggregate aggressively.
The landscape (and the ceremony)
Family
Proof size
Setup
Assumption
Used by
Groth16
~200 bytes ⚡
circuit-specific ceremony
pairing-friendly elliptic curves
Zcash (sprout/sapling)
PLONK
~500 bytes
one universal ceremony
pairings
Aztec, many rollups
STARKs
tens of KB
none — transparent 🎉
only hash functions
Starknet, StarkEx
Halo2 / folding
~KB
none / universal
discrete log (ICICLE-tastic)
Zcash orchard, Filecoin
The trusted setup deserves its reputation-management note: generating Groth16's proving key requires random "toxic waste" that must be destroyed — anyone retaining it can forge proofs. Hence public "powers of tau" ceremonies where hundreds of people contribute randomness, and security holds if just one of them was honest. STARKs avoid the issue entirely by leaning only on hash functions — the Chapter 3 primitive doing yeoman service.
📌 Week 7 — key takeaways
Programs become arithmetic circuits (+, × over a field); the witness is a satisfying assignment — you hunted witnesses by hand in the lab.
Each multiplication gate is one rank-1 constraint; R1CS, Plonkish and AIR are dialects of "polynomial identities encode rule-following".
Schwartz–Zippel: one random-point evaluation catches a lying polynomial with probability 1 − d/p — thousands of checks collapse into one.
Polynomial commitments (KZG / FRI / IPA) keep the point-check zero-knowledge — Chapter 4's envelope, generalized to polynomials.
SNARK = Succinct Non-interactive Argument of Knowledge; trusted setups must destroy their randomness (powers-of-tau), STARKs opt out with hash-only assumptions; recursion and folding let proofs verify proofs.
🎯
Checkpoint: Succinct Magic
In an arithmetic circuit, the "witness" is…
the person attesting the proof is real.
the verifier's random challenge.
a full assignment of wire values that satisfies all gates — the secret satisfying the computation.
the hash of the program.
Same concept as the coloring in Chapter 5: the private evidence making the statement true. The circuit puzzle had you hunting witnesses by hand.
Why does one random-point evaluation suffice to (almost) certify that a degree-100 polynomial is identically zero?
Schwartz–Zippel: a non-zero degree-d polynomial is zero at ≤ d points, so over a huge field a random point catches a liar with probability ≥ 1 − d/p ≈ 1.
Because random points have special algebraic power.
Because polynomials are always zero somewhere.
It doesn't — you must check every point.
Over a 255-bit field with degree 100, a surviving liar needs luck of ~100/2²⁵⁵ — and you felt this in the liar catcher: agreement only at the 3 roots out of 968.
What do polynomial commitments add to the random-point check?
They compress the program size.
They let the prover commit to coefficients and open only at the chosen point — so the witness inside the polynomial never leaks.
They eliminate the need for a trusted setup.
They make verification quantum-resistant.
It's Chapter 4's envelope in degree-space: bind to the polynomial, reveal one evaluation. Zero knowledge rides on the hiding property.
"Trusted setup" ceremonies exist because…
SNARK provers need licensed hardware keys.
governments require key escrow.
the verifier must hold a secret to check proofs.
the setup's random "toxic waste" could let its holder forge proofs — so it must be jointly generated and destroyed, with one honest participant sufficing.
Powers-of-tau: an MPC where each contributor wraps the randomness in the previous layer; honesty of any single participant destroys the trapdoor for everyone. STARKs sidestep setup via hash-only assumptions.