# Zero-Knowledge Proofs and SNARKs

> What zero-knowledge proofs are from scratch, how SNARKs are built, and how rollups and hash-based provers use them

- Published: 2026-10-21
- Topics: zero knowledge, snarks, rollups, cryptography
- Web: https://sadiq.tech/blog/zero-knowledge

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 $y$"

_Witness_: The secret that makes the statement true, e.g. the password $w$ with $\text{hash}(w) = y$

The obvious proof is to hand over $w$ 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
```manim
from manim import *

class CheaterOddsShrink(Scene):
    def construct(self):
        title = Text("A cheater must guess the right side every round", font_size=30).to_edge(UP)
        sub = Text("chance a cheater survives k rounds = 1 / 2^k", font_size=24, color=YELLOW)\
            .next_to(title, DOWN)
        axes = Axes(x_range=[0, 10.5, 1], y_range=[0, 0.6, 0.1], x_length=10, y_length=4.2,
                    tips=False).to_edge(DOWN, buff=1.0)
        nums = VGroup(*[Text(str(k), font_size=18).next_to(axes.c2p(k, 0), DOWN, buff=0.1)
                        for k in range(1, 11)])
        xl = Text("rounds", font_size=22).next_to(nums, DOWN, buff=0.15)
        self.play(FadeIn(title), Create(axes), FadeIn(nums), FadeIn(xl))
        self.play(FadeIn(sub))

        for k in range(1, 11):
            bottom, top = axes.c2p(k, 0), axes.c2p(k, 0.5 ** k)
            h = max(top[1] - bottom[1], 0.02)
            bar = Rectangle(width=0.6, height=h, fill_color=RED, fill_opacity=0.7, stroke_width=0)\
                .move_to([bottom[0], bottom[1] + h / 2, 0])
            lab = Text(f"1/{2 ** k}", font_size=16).next_to(bar, UP, buff=0.08)
            self.play(GrowFromEdge(bar, DOWN), FadeIn(lab), run_time=0.35)

        note = Text("after 20 rounds: 1 in 1,048,576", font_size=26, color=GREEN)\
            .move_to(axes.c2p(6.5, 0.4))
        self.play(FadeIn(note))
        self.wait(2)
```
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 $\frac{1}{2^k}$ 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 $\times$ gates (or R1CS, a list of constraints of the form "(sum) $\times$ (sum) = (sum)")
2. Back end: prove "I know inputs that make this circuit output $y$". Examples: Groth16, Plonk, Spartan, STARKs

_Finite field_: All the arithmetic is modulo a prime $p$: no decimals, no overflow. E.g. modulo 17, $5 \times 4 = 20 \equiv 3$. 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 $\text{Com}(h)$ that binds it to $h$. Later V names a point $x$, and P returns $h(x)$ 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 $S$ gates over a field $\mathbb{F}$

_Transcript_: The value on every gate. It's correct when every gate is consistent ("this $\times$ gate really holds the product of its inputs") and the output is $y$

_Transcript as a polynomial_: Label each gate with a $\log S$-bit string. The transcript becomes a function $T : \{0,1\}^{\log S} \to \mathbb{F}$ (gate label in, gate value out). P commits to $\tilde{h}$, its multilinear extension: the unique polynomial with degree at most 1 in each variable that matches $T$ on every gate label
$$
\tilde{h}(x) = T(x) \quad \text{for all } x \in \{0,1\}^{\log S}
$$
- On gate labels, $\tilde{h}$ reads off gate values
- Everywhere else in $\mathbb{F}^{\log S}$ (a vastly bigger space) it's still defined, and that's where errors become visible

_Schwartz-Zippel lemma_: Two different polynomials of total degree $d$ agree on at most a $\frac{d}{|\mathbb{F}|}$ 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 ($S = 2^{20}$, so 20 variables, total degree at most 20) over a 64-bit field. A wrong polynomial survives one random check with probability at most $\frac{20}{2^{64}} \approx 1$ in $10^{18}$

The same idea with ordinary one-variable polynomials (easier to draw): change one gate value and the whole curve moves
```manim
from manim import *
import numpy as np

class OneGateChangesEverything(Scene):
    def construct(self):
        xs = np.arange(8, dtype=float)
        T = np.array([2.0, 3.0, 1.5, 2.5, 2.0, 3.0, 2.5, 2.0])
        T_bad = T.copy()
        T_bad[4] = 3.2

        def interp(vals):
            def f(x):
                total = 0.0
                for j, yj in enumerate(vals):
                    lj = 1.0
                    for m, xm in enumerate(xs):
                        if m != j:
                            lj *= (x - xm) / (xs[j] - xm)
                    total += yj * lj
                return total
            return f

        h, h_bad = interp(T), interp(T_bad)
        axes = Axes(x_range=[-0.3, 7.3, 1], y_range=[0, 6, 1], x_length=11, y_length=4.2,
                    tips=False).to_edge(DOWN, buff=0.6)
        gate_labels = VGroup(*[Text(f"gate {i}", font_size=18).next_to(axes.c2p(i, 0), DOWN, buff=0.1)
                               for i in range(8)])
        title = Text("Correct transcript vs one wrong gate", font_size=30).to_edge(UP)

        good_curve = axes.plot(h, x_range=[0, 7], color=BLUE)
        good_dots = VGroup(*[Dot(axes.c2p(i, T[i]), color=BLUE) for i in range(8)])
        good_lab = Text("blue: polynomial through the correct gate values", font_size=22, color=BLUE)\
            .next_to(title, DOWN)

        self.play(FadeIn(title), Create(axes), FadeIn(gate_labels))
        self.play(FadeIn(good_dots), FadeIn(good_lab))
        self.play(Create(good_curve), run_time=2)

        bad_dot = Dot(axes.c2p(4, T_bad[4]), color=ORANGE, radius=0.11)
        bad_curve = axes.plot(h_bad, x_range=[0, 7], color=ORANGE)
        bad_lab = Text("orange: same values except gate 4", font_size=22, color=ORANGE)\
            .next_to(good_lab, DOWN)
        self.play(TransformFromCopy(good_dots[4], bad_dot), FadeIn(bad_lab))
        self.play(Create(bad_curve), run_time=2)

        gaps = VGroup(*[Line(axes.c2p(x, h(x)), axes.c2p(x, h_bad(x)),
                             color=RED, stroke_width=2)
                        for x in np.linspace(0.1, 6.9, 69) if abs(h(x) - h_bad(x)) > 0.05])
        note = Text("they touch only at the 7 unchanged gates and differ everywhere else",
                    font_size=22, color=RED).next_to(bad_lab, DOWN)
        self.play(Create(gaps), FadeIn(note), run_time=2)
        self.wait(2)
```
### Checking Gate Constraints
V also needs to know $\tilde{h}$ is a correct transcript, without checking gates one by one. Combine all gate checks into one polynomial over triples of gate labels $(a, b, c)$:
$$
g_h(a,b,c) = \widetilde{\text{add}}(a,b,c)\,\big(\tilde{h}(a) - \tilde{h}(b) - \tilde{h}(c)\big) + \widetilde{\text{mult}}(a,b,c)\,\big(\tilde{h}(a) - \tilde{h}(b)\,\tilde{h}(c)\big)
$$
- $\widetilde{\text{add}}(a,b,c) = 1$ when gate $a$ adds gates $b$ and $c$, and 0 otherwise. Same for $\widetilde{\text{mult}}$. These describe the circuit's wiring and are public
- On a real gate, $g_h$ is "this gate's value minus what it should be". So the transcript is correct exactly when $g_h = 0$ on every triple of labels (plus similar checks pinning the inputs and the output $y$)
- Evaluating $g_h$ at one point needs just 3 values of $\tilde{h}$, 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 $\tau$ and asks P to show $\sum_{x} \text{eq}(\tau, x)\, g_h(x) = 0$, summing over all label triples $x$. Here $\text{eq}(\tau, x)$ is the multilinear polynomial that, on bit-strings, is 1 when $x = \tau$ and 0 otherwise. If any $g_h(x)$ is nonzero, this sum is a nonzero polynomial in $\tau$, so a random $\tau$ exposes it (Schwartz-Zippel again). The sum-check protocol proves the sum in $3 \log S$ short rounds, and at the end V needs $g_h$ at just one random point: 3 openings of $\tilde{h}$

_Way 2, vanishing polynomial (Plonk, Marlin)_: Label gates by the points of a set $H$ and write the constraints as one single-variable polynomial $g(X)$. $g$ is zero on all of $H$ exactly when it's divisible by
$$
Z_H(X) = \prod_{a \in H} (X - a)
$$
So P commits to the quotient $q(X) = g(X) / Z_H(X)$, V picks a random $r$, and checks $g(r) = q(r) \cdot Z_H(r)$. If $H$ is the $n$-th roots of unity (the $n$ field elements with $\omega^n = 1$), then $Z_H(X) = X^n - 1$, 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 $1, 4, 16, 13$ (then $4^4 = 256 \equiv 1$), so $H = \{1, 4, 16, 13\}$ and $Z_H(X) = X^4 - 1$
- Honest P: $g(X) = X^5 - X$ is zero on all of $H$, with $q(X) = X$. V picks $r = 3$: $g(3) = 240 \equiv 2$ and $q(3) \cdot Z_H(3) = 3 \cdot 80 = 240 \equiv 2$. Match, accept
- Cheating P: $g(X) = X^5 - X + 1$ isn't zero on $H$ ($g(1) = 1$), so no $q$ works. Whatever $q$ P sends, $g - q \cdot Z_H$ 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 $\frac{12}{17} \approx 71\%$
- That's weak because 17 is tiny. Real fields have $2^{64}$ to $2^{256}$ 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 ($\widetilde{\text{add}}$, $\widetilde{\text{mult}}$, 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
| 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 $\tau$, 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 $45{,}000 + 34{,}000 \cdot k$ gas for $k$ pairings, so $45{,}000 + 34{,}000 \cdot 4 = 181{,}000$ 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 $X$ transactions lands every $Y$ seconds, that's $X/Y$ transactions per second
- These are independent: run several provers in parallel and a proof lands every $Y$ seconds however long each one takes. Faster proving buys lower latency, not more throughput
```manim
from manim import *

class ThroughputVsLatency(Scene):
    def construct(self):
        Y, prove_time, n_batches = 1.0, 3.0, 6
        unit = 1.25
        origin = LEFT * 5.4 + DOWN * 2.8
        title = Text("Batches every Y seconds, each proof takes 3Y", font_size=30).to_edge(UP)
        axis = Arrow(origin, origin + RIGHT * 12.2, buff=0, stroke_width=3, tip_length=0.2)
        ticks = VGroup(*[Text(f"{t}Y", font_size=18).move_to(origin + RIGHT * t * unit + DOWN * 0.3)
                         for t in range(0, 10)])
        legend = VGroup(
            Text("grey: collecting a batch", font_size=20, color=GREY_B),
            Text("blue: proving it", font_size=20, color=BLUE),
            Text("green: proof posted on L1", font_size=20, color=GREEN),
        ).arrange(RIGHT, buff=0.6).next_to(title, DOWN)
        self.play(FadeIn(title), GrowArrow(axis), FadeIn(ticks), FadeIn(legend))

        def bar(t0, t1, row, color):
            y = origin[1] + 0.55 + row * 0.55
            left = origin[0] + t0 * unit
            return Rectangle(width=(t1 - t0) * unit, height=0.4, fill_color=color,
                             fill_opacity=0.7, stroke_width=0)\
                .move_to([left + (t1 - t0) * unit / 2, y, 0])

        posts = VGroup()
        for k in range(n_batches):
            row = k
            collect = bar(k * Y, (k + 1) * Y, row, GREY_B)
            prove = bar((k + 1) * Y, (k + 1) * Y + prove_time, row, BLUE)
            name = Text(f"batch {k + 1}", font_size=18).next_to(collect, LEFT, buff=0.1)
            done = Dot(prove.get_right(), color=GREEN, radius=0.1)
            posts.add(done)
            self.play(FadeIn(collect), FadeIn(name), run_time=0.35)
            self.play(GrowFromEdge(prove, LEFT), run_time=0.45)
            self.play(FadeIn(done), run_time=0.2)

        tput = Text("after warm-up a proof lands every Y: throughput = X / Y",
                    font_size=22, color=GREEN).to_edge(LEFT, buff=0.4).shift(UP * 1.9)
        lat = Text("but each batch still waits 1Y + 3Y: that's latency",
                   font_size=22, color=BLUE).next_to(tput, DOWN, aligned_edge=LEFT)
        self.play(Indicate(posts, color=GREEN), FadeIn(tput))
        self.play(FadeIn(lat))
        self.wait(2)
```
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
```manim
from manim import *

class MerkleCommitAndOpen(Scene):
    def construct(self):
        title = Text("Commit to 8 values, then open value 5", font_size=30).to_edge(UP)
        self.play(FadeIn(title))
        widths = {0: 1.45, 1: 2.9, 2: 5.8}
        levels = []
        for lvl, count in enumerate([8, 4, 2, 1]):
            y = -1.9 + lvl * 1.45
            gap = 1.45 * 2 ** lvl
            row = VGroup()
            for i in range(count):
                x = (i - (count - 1) / 2) * gap
                label = f"v{i}" if lvl == 0 else ("root" if lvl == 3 else "hash")
                box = Rectangle(width=1.1, height=0.55, color=WHITE)
                txt = Text(label, font_size=20)
                row.add(VGroup(box, txt).move_to([x, y, 0]))
            levels.append(row)

        self.play(FadeIn(levels[0]))
        edges = VGroup()
        for lvl in range(1, 4):
            new_edges = VGroup()
            for i, node in enumerate(levels[lvl]):
                for c in (2 * i, 2 * i + 1):
                    new_edges.add(Line(levels[lvl - 1][c].get_top(), node.get_bottom(),
                                       stroke_width=2, color=GREY_B))
            self.play(Create(new_edges), FadeIn(levels[lvl]), run_time=0.8)
            edges.add(new_edges)
        commit = Text("only the root is sent: that's the commitment", font_size=22, color=YELLOW)\
            .next_to(title, DOWN)
        self.play(levels[3][0][0].animate.set_color(YELLOW), FadeIn(commit))
        self.wait(0.5)

        path = [(0, 5), (1, 2), (2, 1), (3, 0)]
        siblings = [(0, 4), (1, 3), (2, 0)]
        self.play(levels[0][5][0].animate.set_fill(GREEN, 0.6))
        for lvl, i in siblings:
            self.play(levels[lvl][i][0].animate.set_fill(ORANGE, 0.6), run_time=0.5)
        for lvl, i in path[1:]:
            self.play(Indicate(levels[lvl][i], color=GREEN), run_time=0.5)
        explain = VGroup(
            Text("green: the opened value 5 and the hashes V recomputes", font_size=20, color=GREEN),
            Text("orange: the 3 sibling hashes P sends (the authentication path)", font_size=20, color=ORANGE),
        ).arrange(DOWN, aligned_edge=LEFT).to_corner(DL, buff=0.3)
        self.play(FadeOut(commit), FadeIn(explain))
        self.wait(2)
```
_Worked example_: $2^{20}$ evaluations make a tree of depth 20. Opening one value costs 20 sibling hashes, $20 \times 32 = 640$ 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 $L \subseteq \mathbb{F}$:
$$
\text{RS}[\mathbb{F}, L, m] = \{ f : L \to \mathbb{F} \;\mid\; f \text{ is the evaluation of some polynomial of degree} < 2^m \}
$$
- A polynomial of degree $< 2^m$ is fixed by $2^m$ values, but we write down $|L|$ of them: built-in redundancy
- Rate $\rho = 2^m / |L|$: rate $\frac{1}{4}$ means 4 times more values than needed
- Two different codewords disagree on more than a $1 - \rho$ 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 $f(X) = f_E(X^2) + X \cdot f_O(X^2)$ into its even and odd coefficients. V sends a random $\alpha$, and P commits to $f_E + \alpha f_O$: half the degree, on a domain half the size (because $x$ and $-x$ 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
```manim
from manim import *

class FriFolding(Scene):
    def construct(self):
        title = Text("FRI: fold, halve, repeat", font_size=30).to_edge(UP)
        rule = Text("f(x) = fE(x^2) + x fO(x^2)   ->   fE + alpha fO", font_size=24)\
            .next_to(title, DOWN)
        self.play(FadeIn(title), FadeIn(rule))

        sizes, degrees = [64, 32, 16, 8, 4], [16, 8, 4, 2, 1]
        rows = VGroup()
        for r, (n, d) in enumerate(zip(sizes, degrees)):
            dots = VGroup(*[Dot(radius=0.045, color=BLUE) for _ in range(n)]).arrange(RIGHT, buff=0.06)
            dots.move_to(UP * (1.4 - r * 0.9) + RIGHT * 1.2)
            label = Text(f"{n} points, degree < {d}" if d > 1 else f"{n} points, a constant",
                         font_size=20).next_to(dots, LEFT, buff=0.3)
            rows.add(VGroup(dots, label))

        self.play(FadeIn(rows[0]))
        for r in range(1, len(rows)):
            self.play(TransformFromCopy(rows[r - 1][0], rows[r][0]), FadeIn(rows[r][1]), run_time=1)

        for d in rows[-1][0]:
            d.set_color(GREEN)
        end = VGroup(
            Text("last layer: all values must be equal, V reads it directly", font_size=22, color=GREEN),
            Text("rate stays 16/64 = 1/4 in every layer", font_size=22),
        ).arrange(DOWN).to_edge(DOWN, buff=0.3)
        self.play(Indicate(rows[-1][0], color=GREEN), FadeIn(end))
        self.wait(2)
```
### Proximity Gaps
Folding mixes functions with a random $\alpha$. Could a lucky $\alpha$ make a bad function look good? A proximity gap says almost never: for a family like $\{f_0 + \alpha f_1\}$, 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, $f_0$ and $f_1$ 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 $1 - \sqrt{\rho}$ (Ben-Sasson, Carmon, Ishai, Kopparty, Saraf). Many deployed systems assumed they hold further, up to $1 - \rho$ ("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 $v$ at point $z$". WHIR (Arnon, Chiesa, Fenzi, Yogev; EUROCRYPT 2025) checks both at once, using a constrained Reed-Solomon code:
$$
\text{CRS}[\mathbb{F}, L, m, \hat{w}, \sigma] = \Big\{ f \in \text{RS}[\mathbb{F}, L, m] \;:\; \sum_{b \in \{0,1\}^m} \hat{w}\big(\hat{f}(b), b\big) = \sigma \Big\}
$$
- $\hat{f}$ = the polynomial behind $f$, read as multilinear in $m$ variables
- $\hat{w}$ = a public weight polynomial saying what to add up; $\sigma$ = the claimed total
- Example: with $\hat{w}(Z, X) = Z \cdot \text{eq}(z, X)$, the sum is exactly $\hat{f}(z)$, so the constraint says "$\hat{f}(z) = \sigma$". 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 $2^{22}$ 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 $\omega^0, \omega^1, \dots, \omega^{n-1}$ in $O(n \log n)$ steps instead of $O(n^2)$
- Why provers need it: the trace arrives as $n$ 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: $(a, b) \to (a + \omega b,\ a - \omega b)$. For $n = 2^{20}$ that's $\frac{n}{2} \log_2 n \approx 10.5$ 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 ($2^{20}$ as $1024 \times 1024$), 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 $p$, and CPUs have no native instruction for it. So provers use primes that reduce cheaply and fit in machine words:
- BabyBear: $p = 2^{31} - 2^{27} + 1 = 2{,}013{,}265{,}921$
- Mersenne31: $p = 2^{31} - 1$ (Circle STARKs)
- Goldilocks: $p = 2^{64} - 2^{32} + 1$ (Plonky2, Boojum)

_Extension fields_: A random challenge from a $2^{31}$-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 $2^{124}$ 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 $\lceil \log_2 1000 \rceil = 10$ levels. The result is still one small proof

_Binary fields_: Fields of size $2^n$, 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
