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

  1. V waits outside. P walks in and picks a path at random
  2. V walks to the fork and shouts which path P should come back along: "left" or "right"
  3. If P knows the word, P can always comply, going through the door if needed
  4. 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

Loading animation

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"
Q
How can "learns nothing" be made precise ?
A
With a simulator. Suppose V films the cave session. Someone who doesn't know the word can fake an identical-looking video: film many attempts and cut out every round where they guessed wrong. If V could have produced the transcript alone, without the secret, then seeing it taught V nothing. That's the formal definition: a simulator without the witness can produce transcripts nobody can tell apart from real ones

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

Q
Does every SNARK hide the witness ?
A
No, succinctness and zero-knowledge are separate. Many "zk-rollups" use SNARKs only for succinctness (one small proof standing in for thousands of transactions) and publish the transactions anyway, which is why some people prefer the name "validity rollups"

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:

  1. 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)")
  2. 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

Q
Why compile to a circuit at all ?
A
Because circuits become polynomial equations, and polynomials have a superpower: two different low-degree polynomials disagree almost everywhere. That lets V catch one wrong gate among millions by checking a single random point

Construction Overview

Nearly every SNARK is built in three steps:

  1. 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
  2. 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
  3. 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
Q
Why does a hash work as the verifier's randomness ?
A
A good hash acts like a random function, so P can't know a challenge before committing to everything it depends on, and changing a message to cheat changes the challenge too. The catch: you must hash everything, including the public inputs; implementations that forgot (the "Frozen Heart" bugs found by Trail of Bits in 2022) allowed forged proofs

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

Loading animation

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%
Q
So is V's work independent of circuit size ?
A
Almost. V also needs the wiring polynomials (, , or Plonk's "selectors") at the random point, which for an arbitrary circuit costs time proportional to the circuit, so real systems commit to them once in a preprocessing step and V just opens those commitments too

Polynomial Commitments

FamilyExamplesTrusted setup?Post-quantum?Notes
PairingsKZG, PST13YesNoConstant-size proofs (KZG)
Discrete logBulletproofs, Hyrax, DoryNoNoDory uses pairings but no trusted setup
HashingFRI, Ligero, Brakedown, WHIRNoPlausiblyBigger proofs, fast arithmetic
Groups of unknown orderDARKNo (with class groups)NoVery 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
Q
If STARK proofs are big, how do they end up on a blockchain cheaply ?
A
They get wrapped: the big FRI proof is verified inside a Groth16 or Plonk-KZG circuit and only that tiny final proof goes on-chain. zkSync Era does this, proving with Boojum (Plonk-style, FRI over a 64-bit field) and wrapping the result into Plonk (or its variant Fflonk) with KZG on BN254

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
Loading animation

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

Q
What actually limits rollups today ?
A
Mostly L1 data bandwidth, not computation, which is why so much Ethereum work goes into blobs and data sampling rather than faster proof verification

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

Loading animation

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

Loading animation

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
Q
How far are proximity gaps actually proven ?
A
Up to the Johnson bound, distance (Ben-Sasson, Carmon, Ishai, Kopparty, Saraf). Many deployed systems assumed they hold further, up to ("up to capacity"), to use fewer queries; in late 2025 those capacity conjectures, including WHIR's, were shown false (Crites and Stewart, ePrint 2025/2046; Diamond and Gruen, ePrint 2025/2010). The protocols aren't broken, but systems tuned to the conjectured bounds may be less secure than advertised, and parameters within the proven range are the safe choice

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

Q
WHIR vs FRI in one line ?
A
FRI checks "is this a polynomial?", WHIR checks "is this a polynomial, and does it satisfy this constraint?", with a much faster verifier

Prover Performance

Verification takes milliseconds. Proving is the expensive part, and it grows with the computation. A prover:

  1. Runs the program and records every step (the trace, or witness)
  2. Turns the trace into polynomials
  3. Converts them between forms with NTTs
  4. Commits to them (Merkle trees, or elliptic-curve work for KZG)
  5. 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

Q
So what's the overall lesson ?
A
Zero-knowledge means the verifier learns only that the statement is true; SNARKs make such proofs tiny and non-interactive with one recipe (polynomials checked at random points, a commitment, Fiat-Shamir), the commitment sets the trade-offs (KZG: tiny proofs with a trusted setup; hashes: no setup and plausibly post-quantum, with bigger proofs), rollups use them to scale blockchains but still need data availability, and prover speed comes mostly from memory layout, small fields and hardware