Zero-Knowledge Proofs and SNARKs
- zero knowledge
- snarks
- rollups
- cryptography
A zero-knowledge proof lets you convince someone a statement is true without showing them why it's true. A SNARK is the practical version used today: a tiny proof that a whole computation was done correctly, which anyone can check in milliseconds. These notes answer three questions:
- What does "zero-knowledge" actually mean, from scratch?
- How is a SNARK built, and what are its moving parts?
- Why do blockchains care, and what makes proving fast or slow?
TLDR; answer: a proof is zero-knowledge if the verifier learns nothing except "the statement is true". Modern SNARKs all follow one recipe: turn the computation into polynomials, check those polynomials at a few random points, lock them in with a commitment so the prover can't change them, then replace the verifier's randomness with a hash. The commitment you pick decides the trade-offs: proof size, trusted setup, and quantum safety
Zero Knowledge
Every proof here has two players:
- Prover (P): knows a secret and wants to convince someone
- Verifier (V): wants to be convinced, but shouldn't trust P
Statement: The public claim, e.g. "I know the password whose hash is "
Witness: The secret that makes the statement true, e.g. the password with
The obvious proof is to hand over and let V check it. That works, but now V knows the secret. Zero-knowledge proofs get rid of that
Example: The Cave
The classic picture (Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children", 1989): a ring-shaped cave with one entrance that splits into a left and a right path. At the back, the two paths are joined by a door that only opens with a secret word. P claims to know the word
- V waits outside. P walks in and picks a path at random
- V walks to the fork and shouts which path P should come back along: "left" or "right"
- If P knows the word, P can always comply, going through the door if needed
- If P doesn't, P can only comply when V happens to name the side P is already on: a 50% chance
One round proves little. But a cheater has to guess right every single round, so the odds collapse fast
And V learns nothing about the word itself: all V ever sees is P walking out of the side V asked for
Completeness, Soundness, Zero Knowledge
A zero-knowledge proof (defined by Goldwasser, Micali and Rackoff in 1985) must be:
- Complete: if the statement is true and P is honest, V accepts
- Sound: if the statement is false, no cheating P can make V accept, except with tiny probability (the above)
- Zero-knowledge: V learns nothing beyond "the statement is true"
This isn't limited to caves: any statement whose answer can be checked efficiently (any NP statement: "this Sudoku has a solution", "I know a private key for this public key") has a zero-knowledge proof, assuming standard cryptography (Goldreich, Micali, Wigderson 1986)
Limits of Interactive Proofs
The cave protocol has two practical problems:
- Interactive: V has to be there, sending fresh random challenges every round. You can't post it once for everyone to check
- Not succinct: for a big statement ("this program ran correctly for a billion steps"), a naive proof is as big and as slow to check as the computation itself
SNARKs fix both
SNARKs
SNARK = Succinct Non-interactive ARgument of Knowledge
- Succinct: the proof is tiny (bytes to kilobytes) and fast to check, no matter how big the computation is
- Non-interactive: P sends one message, anyone can check it later, no back-and-forth
- Argument: soundness holds against provers with realistic computing power (a cheater would have to break cryptography)
- of Knowledge: a valid proof means P actually knows a witness, not just that one exists
A SNARK that also hides the witness is a zk-SNARK
What we want from a SNARK:
- Fast prover: time close to linear in the computation size
- Small proof: a few hundred bytes to a few KB
- Fast verifier: a few milliseconds
- Transparent: no trusted setup (a one-time ceremony that creates secret randomness, called "toxic waste"; anyone who keeps it can forge proofs)
- Post-quantum: no reliance on problems quantum computers break (discrete log, pairings)
No system gets all five. Every design gives something up
From Programs to Circuits
You don't design a new proof for every problem. You write a normal program and push it through two stages:
- Front end: compile the program into a circuit, a network of and gates (or R1CS, a list of constraints of the form "(sum) (sum) = (sum)")
- Back end: prove "I know inputs that make this circuit output ". Examples: Groth16, Plonk, Spartan, STARKs
Finite field: All the arithmetic is modulo a prime : no decimals, no overflow. E.g. modulo 17, . This makes the polynomial tricks below exact
Construction Overview
Nearly every SNARK is built in three steps:
- Polynomial IOP (Interactive Oracle Proof): P encodes the whole computation as a huge polynomial. V never reads it in full; V only asks for its value at a few random points, then runs a short interactive check
- Polynomial commitment scheme (PCS): P can't send a huge polynomial, so it sends a short fingerprint that binds it to . Later V names a point , and P returns plus a short proof that this value matches the commitment
- Fiat-Shamir: replace each of V's random challenges with a hash of everything sent so far. Now P can produce the whole conversation alone: one non-interactive proof
Step 1 is pure math. Apart from the hash in step 3, all the cryptography lives in step 2, so the commitment decides whether a SNARK needs a trusted setup and whether it's post-quantum
Polynomial IOPs
Multilinear Extensions and Schwartz-Zippel
Take a circuit with gates over a field
Transcript: The value on every gate. It's correct when every gate is consistent ("this gate really holds the product of its inputs") and the output is
Transcript as a polynomial: Label each gate with a -bit string. The transcript becomes a function (gate label in, gate value out). P commits to , its multilinear extension: the unique polynomial with degree at most 1 in each variable that matches on every gate label
- On gate labels, reads off gate values
- Everywhere else in (a vastly bigger space) it's still defined, and that's where errors become visible
Schwartz-Zippel lemma: Two different polynomials of total degree agree on at most a fraction of points. So if P's transcript is wrong in even one gate, its polynomial differs from the right one almost everywhere, and a random point exposes it
Worked example: About a million gates (, so 20 variables, total degree at most 20) over a 64-bit field. A wrong polynomial survives one random check with probability at most in
The same idea with ordinary one-variable polynomials (easier to draw): change one gate value and the whole curve moves
Checking Gate Constraints
V also needs to know is a correct transcript, without checking gates one by one. Combine all gate checks into one polynomial over triples of gate labels :
- when gate adds gates and , and 0 otherwise. Same for . These describe the circuit's wiring and are public
- On a real gate, is "this gate's value minus what it should be". So the transcript is correct exactly when on every triple of labels (plus similar checks pinning the inputs and the output )
- Evaluating at one point needs just 3 values of , which keeps everything cheap
That's still too many points to check one by one. Two standard ways squeeze them into one random check:
Way 1, sum-check (Spartan, GKR-based systems): V picks a random and asks P to show , summing over all label triples . Here is the multilinear polynomial that, on bit-strings, is 1 when and 0 otherwise. If any is nonzero, this sum is a nonzero polynomial in , so a random exposes it (Schwartz-Zippel again). The sum-check protocol proves the sum in short rounds, and at the end V needs at just one random point: 3 openings of
Way 2, vanishing polynomial (Plonk, Marlin): Label gates by the points of a set and write the constraints as one single-variable polynomial . is zero on all of exactly when it's divisible by So P commits to the quotient , V picks a random , and checks . If is the -th roots of unity (the field elements with ), then , which is quick to compute. (Plonk also needs a separate permutation argument to check that wires connect the right gates)
Worked example (tiny field): Work modulo 17. The powers of 4 are (then ), so and
- Honest P: is zero on all of , with . V picks : and . Match, accept
- Cheating P: isn't zero on (), so no works. Whatever P sends, is a nonzero polynomial of degree at most 5, zero on at most 5 of the 17 elements. V catches P with probability at least
- That's weak because 17 is tiny. Real fields have to elements, so the catch rate is essentially 100%
Polynomial Commitments
| Family | Examples | Trusted setup? | Post-quantum? | Notes |
|---|---|---|---|---|
| Pairings | KZG, PST13 | Yes | No | Constant-size proofs (KZG) |
| Discrete log | Bulletproofs, Hyrax, Dory | No | No | Dory uses pairings but no trusted setup |
| Hashing | FRI, Ligero, Brakedown, WHIR | No | Plausibly | Bigger proofs, fast arithmetic |
| Groups of unknown order | DARK | No (with class groups) | No | Very slow prover |
Pairing: A special map on certain elliptic curves that lets you check a multiplication between hidden values. It's what makes KZG proofs a single group element. KZG's trusted setup comes from its public parameters (powers of a secret , the toxic waste), and like everything built on elliptic curves it isn't post-quantum
Two kinds of trusted setup:
- Circuit-specific: redo the ceremony for every new circuit (Groth16)
- Universal: one ceremony covers every circuit up to some size (Plonk, Marlin)
Proof Systems Compared
- Groth16: the smallest proofs (3 group elements, 128 bytes on the BN254 curve) and the fastest verifier. Costs: circuit-specific setup, slow prover, not post-quantum
- Plonk / Marlin with KZG: universal setup and flexible constraints (custom gates, lookups). Proofs about 4 to 6 times bigger than Groth16 (around half a KB)
- Spartan, Brakedown, Orion: no trusted setup and fast provers (Brakedown and Orion were the first implemented SNARKs with linear-time provers). Bigger proofs
- STARKs and other FRI-based systems: no trusted setup and plausibly post-quantum, but proofs of tens to hundreds of KB. Modern versions over small fields are among the fastest provers in production
Worked example, Groth16 on Ethereum: Verifying a Groth16 proof is one check over 4 pairings. Ethereum's pairing precompile (EIP-1108) charges gas for pairings, so gas, plus a little per public input. About 200k gas total, the same for 10 transactions or 10,000
Rollups
Blockchains want ordinary machines to verify the chain. Every node normally re-checks every transaction (signatures, balances, smart-contract code) and stores the full state (every account's balance). Rollups cut that work:
- The chain (layer 1, L1) acts as V. An off-chain service (layer 2, L2) acts as P
- L1 stores only a commitment to the state: the root of a Merkle tree over all balances (explained below)
- L2 executes a batch of transactions, computes the new root, and posts it with a SNARK proving "these valid transactions take the old root to the new root"
- Every L1 node checks one small proof instead of thousands of transactions
Throughput and Latency
- Latency: time from sending a transaction to L2 until a proof covering it lands on L1 = time to fill a batch + proving time
- Throughput: if a proof covering transactions lands every seconds, that's transactions per second
- These are independent: run several provers in parallel and a proof lands every seconds however long each one takes. Faster proving buys lower latency, not more throughput
For comparison, optimistic rollups skip proofs and let anyone challenge a bad batch instead, so withdrawals wait out a challenge window of about a week
Recursion: Split one huge batch into pieces, prove the pieces in parallel on many machines, then combine them with proofs that verify other proofs. The final proof is still one small proof
Data Availability
A SNARK proves the new state root is correct. It doesn't prove anyone else can see the data behind it
Data availability attack: An attacker posts a valid proof but keeps the transactions secret. L1 accepts the new root, but nobody else knows the new balances, so nobody can prove the next batch or prove what they own to withdraw. The chain is valid but stuck
Fix: L1 refuses any batch whose data isn't published. To keep the SNARK small, P makes only a hash of the batch data a public input; the data is posted separately, and the L1 contract checks the posted data matches that hash
Where the data lives on L1:
- CALLDATA: transaction input data, stored in chain history (cheaper than storage in the account state). The original option
- Blobs (since March 2024, EIP-4844): 128 KiB chunks of data that L1 guarantees were published, then deletes after about 18 days. Contracts can't read a blob, only a hash of its KZG commitment (the "versioned hash"), so the proof is checked against that commitment instead of a hash of the data
- PeerDAS (Fusaka upgrade, December 2025): each node downloads only part of each blob, and random sampling still guarantees the whole blob was published. This let blob capacity grow
Validium (data off L1): A committee or a separate network stores the data. Much cheaper, but if the data is withheld, users can't rebuild the state and funds can be frozen
Front Ends and Back Ends
Front ends:
- Cairo (StarkWare): a language built for proving. The original version (Cairo 0) was low-level: all arithmetic is modulo a prime, and even comparisons had to be built by hand; Cairo 1 (2023) is a higher-level, Rust-like language. It uses hints: P supplies a value (say a square root) and the circuit only checks it, which is much cheaper than computing it
- zkEVMs (zkSync Era, Scroll, Polygon zkEVM): prove ordinary Ethereum smart-contract execution. Easier for developers, much harder to build
- Either way, speed depends on thousands of lines of hand-optimized circuit code ("gadgets"), which is hard to audit
Back ends:
- StarkWare: STARKs with FRI. Transparent, larger proofs
- zkSync Era: Plonk-style with FRI (Boojum), wrapped into Plonk (or Fflonk) + KZG for L1
- Polygon's Plonky2: Plonk-style with FRI over the 64-bit Goldilocks field
- Zcash (Orchard): Halo 2 with a Bulletproofs-style commitment. No trusted setup, but verification time grows with the circuit, a poor fit for rollups that pay for every on-chain verification
Hash-Based Proofs
Merkle Trees
Hash-based SNARKs commit to data using only a hash function:
- Put the values (e.g. a polynomial's evaluations) at the leaves
- Hash pairs together, level by level, up to a single root
- The root is the commitment: change any leaf and the root changes
Opening one value: send the value plus the sibling hash at each level (the authentication path). V rehashes up the tree and checks it reaches the root
Worked example: evaluations make a tree of depth 20. Opening one value costs 20 sibling hashes, bytes. Open a few dozen positions and you have tens of KB, which is why hash-based proofs are bigger than KZG (one 48-byte group element per opening on BLS12-381)
The full recipe (the BCS transformation, Ben-Sasson, Chiesa, Spooner 2016): commit to every prover message with a Merkle tree, answer V's queries with authentication paths, and derive V's randomness by hashing the roots. Only hashing and field arithmetic, no trusted setup, and plausibly post-quantum
Reed-Solomon Codes
The problem: V only sees a handful of entries in a huge committed table. How does V know the table is really a low-degree polynomial and not junk that looks right at the spots checked?
Reed-Solomon code: Take a low-degree polynomial and evaluate it at many more points than its degree. The list of values is a codeword. In WHIR's notation, for a set of points :
- A polynomial of degree is fixed by values, but we write down of them: built-in redundancy
- Rate : rate means 4 times more values than needed
- Two different codewords disagree on more than a fraction of points, so a table far from every codeword shows it at most positions
Checking that a table is close to a codeword by sampling a few positions is a proximity test. FRI, STIR, WHIR and BaseFold are all proximity tests
FRI
Split into its even and odd coefficients. V sends a random , and P commits to : half the degree, on a domain half the size (because and square to the same point). Repeat until the polynomial is a constant. V spot-checks that each layer was folded correctly from the one before
Proximity Gaps
Folding mixes functions with a random . Could a lucky make a bad function look good? A proximity gap says almost never: for a family like , either every member is close to the code, or only a tiny fraction are. No in-between, so a mix that passes means its parts pass too
- Correlated agreement (stronger): if the mix is close, and are close to codewords on the same set of positions, so errors can't hide in different places
- Mutual correlated agreement (introduced for WHIR): even stronger, every set of positions where the mix matches the code is one where all the inputs match too
WHIR
FRI only asks "is this table close to a low-degree polynomial?". Sum-check based SNARKs end with claims like "the polynomial equals at point ". WHIR (Arnon, Chiesa, Fenzi, Yogev; EUROCRYPT 2025) checks both at once, using a constrained Reed-Solomon code:
- = the polynomial behind , read as multilinear in variables
- = a public weight polynomial saying what to add up; = the claimed total
- Example: with , the sum is exactly , so the constraint says "". That's a polynomial commitment opening
WHIR folds like FRI while running sum-check on the constraint. From the paper: committing to a polynomial of degree at 100-bit security takes about 1.2 s to commit and open, a 63 KiB proof, and about 360 microseconds to verify, against several milliseconds for other hash-based verifiers
Prover Performance
Verification takes milliseconds. Proving is the expensive part, and it grows with the computation. A prover:
- Runs the program and records every step (the trace, or witness)
- Turns the trace into polynomials
- Converts them between forms with NTTs
- Commits to them (Merkle trees, or elliptic-curve work for KZG)
- Proves values at random points (the commitment opening)
A rough split for a STARK-style prover (ballpark only, it varies by system):
- Witness generation, about 10%: plain execution, no cryptography. Grows if the program is memory-heavy or uses operations that are awkward in field arithmetic (like SHA-256's 32-bit bit-twiddling)
- Commitment (NTTs + Merkle hashing): the biggest chunk, often more than half
- Constraint evaluation, about 10%: every row is checked independently, so it parallelizes perfectly
- Commitment opening, about 20%
NTT (Number Theoretic Transform): The FFT over a finite field. It converts a polynomial between its coefficients and its values at the points in steps instead of
- Why provers need it: the trace arrives as values, but the Reed-Solomon commitment needs values on a domain 2 to 16 times bigger. So: inverse NTT to coefficients, then NTT on the bigger domain
- Each step is a butterfly: . For that's million butterflies
- The bottleneck is memory, not arithmetic: later stages pair elements far apart, which defeats the CPU cache. The fix rearranges data: treat the vector as a matrix ( as ), do small NTTs on rows that fit in cache, multiply by twiddle factors, transpose, repeat (the "four-step" algorithm)
Fields and Hardware
Small fields: Field multiplication is a multiply plus a reduction modulo , and CPUs have no native instruction for it. So provers use primes that reduce cheaply and fit in machine words:
- BabyBear:
- Mersenne31: (Circle STARKs)
- Goldilocks: (Plonky2, Boojum)
Extension fields: A random challenge from a -element field is too easy to guess (remember the 17-element example). So challenges come from an extension field, where each element is a short tuple of small-field elements (4 elements over a 31-bit field gives about possibilities). Multiplying tuples costs several base multiplications
Parallel hardware:
- SIMD: one instruction on several values at once (a 128-bit register holds four 32-bit field elements)
- Multi-core CPUs and GPUs split NTTs, hashing and constraint checks across cores. Past a point memory bandwidth is the limit: more cores don't help if memory can't feed them
- Distributed proving: 1 billion steps of a program split into 1,000 segments of 1 million, proved in parallel across many GPUs, then merged pairwise in a tree of levels. The result is still one small proof
Binary fields: Fields of size , where addition is XOR (no carries) and reduction is cheap. Very hardware-friendly; Binius (2023) builds a SNARK on them. Prime fields stay the default because most proof systems and all elliptic-curve tools are built on them