Skip to content
LumenaryAcademy
Verifiable 90 min

STARKs, FRI, lookups and folding

Proof systems built from hashes and error-correcting codes, the small fields that make them fast, and the tricks — lookups, recursion and folding — that let them scale.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Proofs from hashes alone

The SNARKs of the previous lesson rest on elliptic-curve pairings and, for the smallest proofs, on a trusted setup. Both are uncomfortable. A setup is a ceremony that must be trusted; pairings are slow, need fields of about 255 bits, and would be broken by a large quantum computer. In 2018 Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael Riabzev described STARKs — scalable, transparent arguments of knowledge — that need nothing but a hash function: no setup secrets, no number-theoretic assumptions, and plausible security against quantum computers. The cost is larger proofs, tens to hundreds of kilobytes instead of hundreds of bytes.

STARK-style systems now carry a large share of production proving: StarkWare's StarkEx and Starknet, and many of the zkVMs of 2026 (next lesson) commit with hashes and test low degree with FRI. This lesson builds FRI, explains why these provers compute over surprisingly small fields, and then covers the three ideas that make large proofs practical: lookups (cheap table membership), recursion (proofs that verify proofs) and folding (combining many statements into one before proving anything).

DefinitionsH

Reed–Solomon codes and proximity

A polynomial of degree less than kk is determined by kk values, but evaluating it at many more points, n>kn > k, produces a highly redundant codeword: if two polynomials of degree less than kk differ, they agree on at most k−1k - 1 points, so their codewords differ in at least n−k+1n - k + 1 positions.

Definition— Reed–Solomon code

For a field F\mathbb{F}, an evaluation domain D⊆FD \subseteq \mathbb{F} with ∣D∣=n|D| = n, and k<nk < n, the Reed–Solomon code RS[F,D,k]\mathrm{RS}[\mathbb{F}, D, k] is the set of vectors (f(x))x∈D(f(x))_{x \in D} for polynomials ff of degree less than kk. Its rate is ρ=k/n\rho = k/n. A word w∈FDw \in \mathbb{F}^D is δ\delta-far from the code if every codeword differs from ww in at least a fraction δ\delta of positions.

The STARK idea in one paragraph: the prover encodes its computation as polynomials, evaluates them on a domain several times larger than their degree (a low-degree extension), and commits to each resulting codeword with a Merkle tree (Hashes and Merkle trees). The verifier then needs to know two things. First, that the committed words really are codewords — or at least close to codewords, since checking every position is too expensive; this is a proximity test, and FRI is one. Second, that the polynomials satisfy the computation's constraints, which it checks at a few random positions, each opened with a Merkle path. A Merkle root of a codeword, plus a proximity test, is a polynomial commitment built from hashing alone: transparent, because there is nothing secret in it.

Why "close" is enough: if a committed word is close to a unique codeword, the prover is effectively bound to that polynomial; and if it is far from every codeword, a few random spot checks catch it with high probability. Large distance is what makes spot checks meaningful, which is why the rate is kept low (commonly between 1/21/2 and 1/161/16).

ComputationC

FRI: folding a function down to a constant

FRI (Fast Reed–Solomon Interactive oracle proof of proximity, Ben-Sasson, Bentov, Horesh and Riabzev, 2018) tests proximity with a divide-and-conquer trick reminiscent of the fast Fourier transform. Split any polynomial into its even and odd parts,

f(X)=fe(X2)+X fo(X2),f(X) = f_{\mathrm{e}}(X^2) + X\, f_{\mathrm{o}}(X^2),

where fef_{\mathrm{e}} and fof_{\mathrm{o}} have half the degree. Given a random challenge β\beta from the verifier, define the folded polynomial f′(Y)=fe(Y)+βfo(Y)f'(Y) = f_{\mathrm{e}}(Y) + \beta f_{\mathrm{o}}(Y). If the domain DD is a multiplicative subgroup of even size, then xx and −x-x are both in DD, they have the same square, and

f′(x2)=f(x)+f(−x)2+β f(x)−f(−x)2x,f'(x^2) = \frac{f(x) + f(-x)}{2} + \beta\,\frac{f(x) - f(-x)}{2x},

so each value of f′f' on the squared domain D′={x2}D' = \{x^2\}, half the size of DD, is computed from two values of ff. Halving the degree and the domain at once keeps the rate the same.

  1. Commit phase. The prover commits to f0=ff_0 = f on DD; receives β1\beta_1; commits to f1f_1 on D′D'; and so on, until the degree is 0 and the last layer is a constant, which it sends in the clear.
  2. Query phase. The verifier picks random positions xx and checks every fold along the path: from f0(x)f_0(x) and f0(−x)f_0(-x) it computes what f1(x2)f_1(x^2) must be and compares with the committed value, then continues down to the constant. Each check needs two Merkle openings per layer.
x−xf₁ on 64 points (root 1)f₂ on 32 points (root 2)f₃ on 16 points (root 3)f₄: a constant, sent in the clearf₀ on 128 points (root 0)
FRI folds a word on 128 points down to a constant on 8 points, each layer half the size of the one before and committed by its own Merkle root. A query follows one path: the values at x and −x in a layer determine one value in the next.

The program runs FRI over the toy field F257\mathbb{F}_{257}, whose multiplicative group has order 256=28256 = 2^8 and so contains subgroups of every power-of-two size. It encodes a random polynomial of degree less than 16 on 128 points (rate 1/81/8), folds four times, and checks the folds at random queries. The verifier reads the layers directly, standing in for Merkle openings. A random word, folded honestly, does not end in a constant; and a prover who corrupts about 10% of a real codeword and then lies in the first fold to hide it is caught by the consistency checks, at a rate that grows with the number of queries.

python
import random

p = 257                       # toy field: p - 1 = 256 = 2^8, so F_257 has subgroups of every size 2^j
N, K = 128, 16                # evaluate polynomials of degree < 16 on 128 points: rate 1/8
omega = pow(3, (p - 1) // N, p)                 # 3 generates F_257^*, so omega has order 128
domain = [pow(omega, i, p) for i in range(N)]
inv2 = pow(2, -1, p)

def evaluate(coeffs, x):
    acc = 0
    for c in reversed(coeffs):
        acc = (acc * x + c) % p
    return acc

def fold(layer, beta, size):
    """f(x) = fe(x^2) + x fo(x^2)  ->  f'(y) = fe(y) + beta fo(y), on the squared domain."""
    w = pow(omega, N // size, p)                # generator of the current domain
    half = size // 2
    out = []
    for i in range(half):
        x = pow(w, i, p)
        a, b = layer[i], layer[i + half]        # f(x) and f(-x): -x is x * w^(size/2)
        even = (a + b) * inv2 % p
        odd = (a - b) * inv2 * pow(x, -1, p) % p
        out.append((even + beta * odd) % p)
    return out

def commit_phase(word, rng, cheat=None):
    layers, betas, size = [word], [], N
    while size > N // K:                        # 4 folds take degree < 16 down to a constant
        beta = rng.randrange(p)                 # verifier's challenge (Fiat-Shamir in practice)
        nxt = fold(layers[-1], beta, size)
        if cheat is not None and len(layers) == 1:
            nxt = cheat(beta)                   # a cheating prover may send any next layer
        layers.append(nxt); betas.append(beta); size //= 2
    return layers, betas

def query_phase(layers, betas, queries, rng):
    if len(set(layers[-1])) != 1:
        return False                            # the last layer must be a constant
    for _ in range(queries):
        i, size = rng.randrange(N), N
        for j, beta in enumerate(betas):
            i %= size
            half = size // 2
            x = pow(pow(omega, N // size, p), i % half, p)
            a, b = layers[j][i % half], layers[j][i % half + half]
            expected = ((a + b) * inv2 + beta * (a - b) * inv2 * pow(x, -1, p)) % p
            if layers[j + 1][i % half] != expected:
                return False                    # folding was not done consistently
            size = half
    return True

rng = random.Random(2018)
poly = [rng.randrange(p) for _ in range(K)]
codeword = [evaluate(poly, x) for x in domain]
layers, betas = commit_phase(codeword, rng)
print("honest codeword: layer sizes", [len(L) for L in layers], " last layer", layers[-1],
      " accepted:", query_phase(layers, betas, 20, rng))

noise = [rng.randrange(p) for _ in range(N)]    # a word far from every low-degree polynomial
layers, betas = commit_phase(noise, rng)
print("random word, folded honestly: last layer", layers[-1], " accepted:", query_phase(layers, betas, 20, rng))

# A subtler cheat: corrupt 13 of the 128 values of a real codeword (about 10%), then hide the
# damage by sending the fold of the ORIGINAL codeword as layer 1. Only queries that touch a
# corrupted position can notice.
bad = list(codeword)
for i in rng.sample(range(N), 13):
    bad[i] = (bad[i] + 1 + rng.randrange(p - 1)) % p
print("\ncorrupted codeword, cheating prover; acceptance rate over 2000 runs:")
for q in [1, 5, 20, 60]:
    wins = 0
    for _ in range(2000):
        layers, betas = commit_phase(bad, rng, cheat=lambda beta: fold(codeword, beta, N))
        wins += query_phase(layers, betas, q, rng)
    print(f"  {q:2} quer{'y' if q == 1 else 'ies'}: {wins / 2000:.3f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

From FRI to a STARK

A STARK proves that a computation ran correctly, described as an algebraic intermediate representation (AIR):

  1. Trace. The prover writes the computation as a table, the execution trace: one row per step, one column per register. A trace with TT rows becomes one polynomial per column, interpolated over a subgroup of size TT (with a generator gg, row ii sits at gig^i).
  2. Constraints. Correct execution is a set of polynomial identities between a row and the next: for example P(col(X),col(gX))=0P(\text{col}(X), \text{col}(gX)) = 0 for every row, plus boundary constraints on the first and last rows. "Holds on every row" means "is divisible by the vanishing polynomial XT−1X^T - 1" — the same trick as the QAP.
  3. Commit and test. The prover evaluates the trace polynomials and the quotient of the constraints by the vanishing polynomial on a larger domain (a low-degree extension, typically 2 to 16 times larger), Merkle-commits them, and proves with FRI that the quotient is close to a low-degree polynomial. If any constraint failed on any row, the "quotient" would not be a polynomial at all, and FRI would reject.
  4. Spot checks. At random points, the verifier checks that the committed trace and quotient values satisfy the constraint equation, using Merkle openings (refined by the DEEP technique, which samples outside the domain).

Everything is public-coin and made non-interactive by hashing the Merkle roots into the challenges. The verifier does only hashing and a little field arithmetic, polylogarithmic in TT. Proofs are typically tens to a couple of hundred kilobytes, too large to post on Ethereum cheaply, so many systems end by wrapping: a final, small SNARK (Groth16 or PLONK) proves "I verified this STARK". The next lesson builds a trace and its transition constraints for a small stack machine.

ExplanationH

Why small fields?

Pairing-based SNARKs must work over a field of about 255 bits, the scalar field of the curve. Hash-based systems have no such constraint, and since 2022 they have moved to small fields whose elements fit in a machine word:

FieldSizeWhere used (examples)Why it is convenient
Goldilocksp=264−232+1p = 2^{64} - 2^{32} + 1Plonky264-bit words; 2322^{32} divides p−1p - 1, so FFTs up to 2322^{32} points; fast reduction
BabyBearp=231−227+1=15⋅227+1p = 2^{31} - 2^{27} + 1 = 15 \cdot 2^{27} + 1RISC Zero, Plonky3-based provers31 bits fit in 32-bit lanes of CPUs and GPUs; FFTs up to 2272^{27} points
KoalaBearp=231−224+1p = 2^{31} - 2^{24} + 1some Plonky3-based proverssimilar; x3x^3 is a permutation, so algebraic hashes need fewer multiplications
Mersenne-31p=231−1p = 2^{31} - 1StarkWare's Stwo proverthe fastest reduction of all; FFTs use the "circle" group of order 2312^{31} (Circle STARKs)
Binary towersF22k\mathbb{F}_{2^{2^k}}Biniusaddition is XOR; bits cost one bit, not a whole field element

Small fields make every operation several times cheaper, use memory and bandwidth better, and map onto GPU and vector instructions. They also match computation: a 32-bit register of a RISC-V program is stored as two 16-bit limbs or four bytes, each in a 31-bit element, instead of one value padded into a 254-bit element.

The catch is soundness. Every random challenge must come from a set large enough that luck is negligible, and 2312^{31} is not. So the data stay in the base field while challenges come from an extension field: for BabyBear, the degree-4 extension Fp4\mathbb{F}_{p^4} has about 21242^{124} elements. Only the values that mix in challenges (folds, random linear combinations) need extension arithmetic, which costs several times more per operation but touches far fewer values. (Extension fields are polynomials modulo an irreducible polynomial; see fields and Galois theory.)

ComputationC

Lookup arguments

Arithmetic constraints are bad at non-arithmetic facts: "this value is a byte", "this is the XOR of those two bytes", "this 32-bit word is that instruction's encoding". The bit decomposition of the previous lesson costs nine constraints per byte. A lookup argument proves instead that every value in a witness column aa appears in a fixed table tt, at a cost of roughly one committed value per lookup plus one per table entry, however complex the relation the table encodes.

  • Plookup (Gabizon and Williamson, 2020) sorts the witness values together with the table and checks, with a grand product like PLONK's, that consecutive entries of the sorted list either repeat or follow the table.
  • LogUp (Haböck, 2022) uses logarithmic derivatives. The multiset {ai}\{a_i\} is contained in the set {tj}\{t_j\}, with tjt_j used mjm_j times, exactly when ∑i1X−ai=∑jmjX−tj\sum_i \frac{1}{X - a_i} = \sum_j \frac{m_j}{X - t_j} as rational functions, which the verifier tests at a random XX. Sums are easier to prove than products, especially with sumcheck.
  • Lasso (Setty, Thaler and Wahby, 2023) handles tables far too large to write down, such as all 2642^{64} results of a 64-bit addition, by requiring the tables to be decomposable into small subtables, and pays only for the entries actually looked up. The zkVM Jolt builds a whole processor from such lookups.
python
import random
from collections import Counter

p = 2**61 - 1                                   # a toy-sized prime field for the challenge

def inv(a):
    return pow(a % p, -1, p)

def logup_sides(values, table, mult, X):
    """LogUp: the multiset 'values' lies in 'table' (with multiplicities 'mult') iff
       sum_i 1/(X - values_i) == sum_j mult_j/(X - table_j) as rational functions of X."""
    lhs = sum(inv(X - a) for a in values) % p
    rhs = sum(m * inv(X - t) for t, m in zip(table, mult)) % p
    return lhs, rhs

table = list(range(256))                        # an 8-bit range-check table
rng = random.Random(4)
values = [rng.randrange(256) for _ in range(1000)]      # 1000 witness values to range-check
counts = Counter(values)
mult = [counts[t] for t in table]               # the prover supplies how often each entry is used
X = rng.randrange(p)                            # the verifier's random challenge
lhs, rhs = logup_sides(values, table, mult, X)
print("all values are bytes:      sides equal:", lhs == rhs)

values_bad = values[:-1] + [300]                # one value out of range
counts = Counter(v for v in values_bad if v < 256)
mult_bad = [counts[t] for t in table]           # the best the prover can do with this table
lhs, rhs = logup_sides(values_bad, table, mult_bad, X)
print("one value is 300:          sides equal:", lhs == rhs)

# Even choosing the multiplicities freely does not help: 1/(X - 300) has a pole that no
# combination of the table's terms has. For example, put the extra weight on entry 255:
mult_try = list(mult_bad); mult_try[255] += 1
lhs, rhs = logup_sides(values_bad, table, mult_try, X)
print("300 counted as 255 instead: sides equal:", lhs == rhs)
print(f"LogUp terms: {len(values)} + {len(table)};  bit decomposition: {9 * len(values)} constraints")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The cheating prover cannot balance the identity, because 1X−300\frac{1}{X - 300} has a pole at 300 that no combination of 1X−tj\frac{1}{X - t_j} with tj≤255t_j \le 255 can produce; at a random XX the two sides differ except with probability about (number of terms)/p/p. A phrase from the Ethereum research community captures the ambition: the lookup singularity, the point at which a circuit is mostly lookups into precomputed tables, so that writing a proof system's front end feels like writing ordinary code.

ExplanationH

Recursion and proof composition

A proof verifier is itself a computation, so it can be proved. Recursion proves the statement "I verified proof π\pi, and it was valid", which opens three doors:

  • Compression. Prove with a fast system that produces large proofs (a STARK), then prove the verification of that proof with a system whose proofs are small (Groth16). Many zkVMs end exactly this way for Ethereum.
  • Aggregation. One proof that nn proofs verified, so a blockchain checks one proof instead of nn; a tree of aggregations handles thousands.
  • Incrementally verifiable computation (IVC), defined by Paul Valiant in 2008, and its generalisation proof-carrying data (Chiesa and Tromer, 2010): at each step of a long computation, prove "this step was correct, and so was the proof of everything before". A blockchain whose every block carries a proof of the entire history can be checked from a single, constant-size proof; Mina is designed this way.

Recursion is expensive when the verifier's arithmetic does not match the proof system's field. A pairing check involves arithmetic in the curve's base field while the circuit computes in its scalar field, so simulating it means emulating one field inside another, costing hundreds of constraints per multiplication. Solutions include cycles of curves (two curves, each with base field equal to the other's scalar field, like the Pasta curves used by Zcash's Halo 2), recursion-friendly hashes such as Poseidon2 inside FRI verifiers over the same small field, and Halo's accumulation idea (Bowe, Grigg and Hopwood, 2019): postpone the expensive part of each verification and batch all of them into one check at the end.

ComputationC

Folding: Nova and its successors

Accumulation taken to its logical end gives folding schemes. Nova (Kothapalli, Setty and Tzialla, first posted in 2021) observed that for IVC you do not need to prove each step at all: you can fold the statement "step ii is correct" into a running statement "steps 1,…,i−11, \ldots, i - 1 are correct" so that one satisfying the folded statement implies (with high probability) both. Only at the end is one SNARK produced, for the final folded statement.

Plain R1CS does not fold: the constraints are quadratic, so a random combination z1+rz2z_1 + r z_2 of two solutions is not a solution. Nova uses relaxed R1CS, which adds a scalar uu (stored in the constant slot of zz) and an error vector EE:

(Az)∘(Bz)=u⋅(Cz)+E.(Az) \circ (Bz) = u \cdot (Cz) + E.

A fresh instance has u=1u = 1 and E=0E = 0. To fold two instances, the prover sends the cross term T=Az1∘Bz2+Az2∘Bz1−u1Cz2−u2Cz1T = Az_1 \circ Bz_2 + Az_2 \circ Bz_1 - u_1 Cz_2 - u_2 Cz_1, the verifier picks a random rr, and both compute

z=z1+rz2,u=u1+ru2,E=E1+rT+r2E2.z = z_1 + r z_2, \qquad u = u_1 + r u_2, \qquad E = E_1 + rT + r^2 E_2.

Expanding (Az)∘(Bz)(Az) \circ (Bz) shows that the folded instance is satisfied whenever both inputs are, and if either is not, the folded one fails except with probability about 2/∣F∣2/|\mathbb{F}| (a degree-2 polynomial in rr). In real Nova, zz's witness part and EE are never sent: they are hidden in Pedersen commitments, which are additively homomorphic, so the verifier folds the commitments with a few group operations, and that tiny folding verifier is all that each step's circuit must contain. The program folds ten steps of the iteration x↦(x+3)5x \mapsto (x + 3)^5 (a toy version of a hash round) and then one incorrect step.

python
import random

p = 2**61 - 1                      # toy prime field; real Nova uses the scalar field of a curve

# One step of an iterated computation: x_next = (x + 3)^5, as an R1CS with Z = (u, x, y, s1, s2):
#   (x + 3u)(x + 3u) = s1,   s1 * s1 = s2,   s2 * (x + 3u) = y
A = [[3, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]
B = [[3, 1, 0, 0, 0], [0, 0, 0, 1, 0], [3, 1, 0, 0, 0]]
C = [[0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0]]

def mv(M, Z):
    return [sum(a * z for a, z in zip(row, Z)) % p for row in M]

def satisfied(inst):
    """Relaxed R1CS: (A Z) o (B Z) == u (C Z) + E, where Z[0] = u."""
    Z, E = inst
    u = Z[0]
    return all(a * b % p == (u * c + e) % p for a, b, c, e in zip(mv(A, Z), mv(B, Z), mv(C, Z), E))

def step(x):
    s1 = (x + 3) ** 2 % p
    s2 = s1 * s1 % p
    return ([1, x, s2 * (x + 3) % p, s1, s2], [0, 0, 0])     # a fresh instance: u = 1, E = 0

def fold(inst1, inst2, r):
    (Z1, E1), (Z2, E2) = inst1, inst2
    u1, u2 = Z1[0], Z2[0]
    AZ1, BZ1, CZ1 = mv(A, Z1), mv(B, Z1), mv(C, Z1)
    AZ2, BZ2, CZ2 = mv(A, Z2), mv(B, Z2), mv(C, Z2)
    T = [(a1 * b2 + a2 * b1 - u1 * c2 - u2 * c1) % p              # the cross term
         for a1, b1, c1, a2, b2, c2 in zip(AZ1, BZ1, CZ1, AZ2, BZ2, CZ2)]
    Z = [(z1 + r * z2) % p for z1, z2 in zip(Z1, Z2)]
    E = [(e1 + r * t + r * r * e2) % p for e1, t, e2 in zip(E1, T, E2)]
    return Z, E

rng = random.Random(7)
# Fold ten steps of the computation, one after another, into a single running instance.
x, acc = 5, None
for i in range(10):
    inst = step(x)
    acc = inst if acc is None else fold(acc, inst, rng.randrange(p))
    x = inst[0][2]                                             # this step's output feeds the next
print("10 steps folded; the accumulator is still", len(acc[0]), "variables and", len(acc[1]),
      "constraints; satisfied:", satisfied(acc))

# A wrong step poisons the accumulator: folding cannot hide it.
wrong = step(x)
wrong[0][2] = (wrong[0][2] + 1) % p                            # a step with an incorrect output
print("one wrong step folded in; satisfied:", satisfied(fold(acc, wrong, rng.randrange(p))))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The successors broaden what can be folded: SuperNova (2022) lets each step run a different circuit (a different instruction), HyperNova (2023) folds higher-degree constraint systems (CCS, which captures R1CS, PLONKish and AIR) and many instances at once, ProtoStar and ProtoGalaxy (2023) fold any special-sound protocol, and CycleFold reduces the cost of the curve cycle. Since 2024, lattice-based folding (LatticeFold, Boneh and Chen; Neo, 2025) replaces Pedersen commitments with lattice commitments over small fields, aiming at folding that is both fast and plausibly post-quantum. As of 2026, folding libraries serve long, repetitive computations, while the fastest zkVMs mostly rely on FRI-style STARKs or sumcheck-based designs with recursion; which approach wins where is an open, empirical question.

ExplanationH

Are hash-based proofs post-quantum?

Shor's algorithm would break every scheme whose security rests on discrete logarithms or factoring: KZG, Groth16, Bulletproofs and the Pedersen commitments inside Nova. Hash-based systems rest on collision resistance and on modelling the hash as a random oracle for Fiat–Shamir. Against quantum computers, the best known generic attacks on hashes give only polynomial speed-ups (Grover's square-root speed-up for search, smaller ones for collisions), so doubling hash output sizes is believed to compensate, and FRI-based SNARKs have been proven secure in the quantum random oracle model (Chiesa, Manohar and Spooner, 2019). Hence the usual phrase: STARKs are plausibly post-quantum. "Plausibly" is honest: the security proofs are in idealised models, concrete parameters often rely on conjectures about Reed–Solomon codes (some of which were refuted in late 2025, see the frontier), and a STARK wrapped in Groth16 for cheap verification is only as post-quantum as Groth16, which is not at all.

Common misconceptionsH

Common misconceptions

Misconception

"Transparent means the proofs reveal everything." Transparent refers to the setup: no secret randomness is needed to create the public parameters. Whether proofs hide the witness (zero knowledge) is a separate property; STARKs add it by masking the trace with random values.

Misconception

"FRI proves the committed polynomial has low degree." It proves the committed word is close to a low-degree codeword, with some probability of error; the protocol is designed so that closeness is all that the rest of the proof needs. Exact degree checking would mean reading every position.

Misconception

"A 31-bit field gives 31-bit security." Security depends on the field the challenges come from and on the number of queries, not on the base field. BabyBear provers take challenges from a degree-4 or degree-5 extension. Conversely, a 256-bit field with too few FRI queries is insecure.

Misconception

"Folding is a proof system." A folding scheme reduces two statements to one; it proves nothing until the final folded statement is proved with an ordinary SNARK. Its soundness also depends on the commitments: folded witnesses must stay bound to the original ones.

Exercises

Exercises

1. STARKs, FRI, lookups and folding

Warm-upHuman

What does it mean that a STARK is transparent?

Choose one

2. STARKs, FRI, lookups and folding

CoreHuman

A STARK runs FRI on a polynomial of degree less than 2202^{20}, evaluated on a domain of 2232^{23} points (rate 1/81/8). Each round folds by a factor of 2. How many folding rounds are needed to reach a constant (degree less than 1)?

3. STARKs, FRI, lookups and folding

CoreHuman

Suppose that at rate ρ\rho each FRI query gives 12log⁡2(1/ρ)\tfrac12 \log_2(1/\rho) bits of security (the regime covered by proven bounds, up to the Johnson radius 1−ρ1 - \sqrt\rho). With rate ρ=1/16\rho = 1/16, how many queries are needed for 100 bits?

4. STARKs, FRI, lookups and folding

CoreHuman

Which statements about small-field provers are true? Select all that apply.

Choose all that apply

5. STARKs, FRI, lookups and folding

CoreHuman

Fold two instances of the one-constraint relaxed R1CS x⋅x=u⋅y+Ex \cdot x = u \cdot y + E, with Z=(u,x,y)Z = (u, x, y), working over the integers. Instance 1: u1=1u_1 = 1, x1=3x_1 = 3, y1=9y_1 = 9, E1=0E_1 = 0. Instance 2: u2=1u_2 = 1, x2=4x_2 = 4, y2=16y_2 = 16, E2=0E_2 = 0. The challenge is r=2r = 2. What is the folded error E=E1+rT+r2E2E = E_1 + rT + r^2E_2?

6. STARKs, FRI, lookups and folding

CoreComputational

Implement one FRI folding step. fri_fold(values, beta, w, p) receives the values f(wi)f(w^i) for i=0,…,n−1i = 0, \ldots, n - 1 of a polynomial on the subgroup generated by w (of even order nn, so wn/2=−1w^{n/2} = -1), a challenge beta, and the prime p. Return the n/2n/2 values f′(w2i)f'(w^{2i}) of the folded polynomial f′(Y)=fe(Y)+βfo(Y)f'(Y) = f_{\mathrm e}(Y) + \beta f_{\mathrm o}(Y), using only the given values (not the coefficients).

The tests compare your output with the fold computed from the coefficients, over F257\mathbb{F}_{257} and over BabyBear.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. STARKs, FRI, lookups and folding

StretchComputational

Implement Nova folding for relaxed R1CS. nova_fold(A, B, C, inst1, inst2, r, p) receives the constraint matrices (lists of rows), two instances (Z, E) where Z[0] is the relaxation scalar uu and E is the error vector, a challenge r and the prime p. Return the folded instance (Z1+rZ2, E1+rT+r2E2)(Z_1 + rZ_2,\ E_1 + rT + r^2E_2) with the cross term T=AZ1∘BZ2+AZ2∘BZ1−u1 CZ2−u2 CZ1T = AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1 - u_1\,CZ_2 - u_2\,CZ_1, all modulo p.

The tests check the hand-worked example, fold twelve steps of the lesson's computation, and fold in a bad instance.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources