Chapter 34: STARKs and FRI revisited
A STARK is four stages of composition: arithmetization at L1, low-degree extension at the L1-to-L2 bridge, FRI proximity testing at L2, Fiat-Shamir compilation at L4. Ch 31 named the layers. Ch 32 built L2’s FRI primitive at survey-plus-toy depth. Ch 33 built L4’s QROM analysis, stated DFMS20’s multi-round bound and the model this Part sizes against, and flagged the FRI-based SNARK QROM composition as pending at deployment parameters. This chapter assembles those pieces into a complete end-to-end system. The operator leaves knowing which parameter governs which stage of soundness and how the stages compose.
A STARK is four stages, one proof
Section titled “A STARK is four stages, one proof”A STARK verifier receives a non-interactive proof and accepts or rejects. The proof certifies a public claim of the form: some trace satisfies an arithmetic computation. The prover-verifier structure behind that certificate is a four-stage pipeline. Stage one is arithmetization: the computation is compiled into an AIR (Algebraic Intermediate Representation) that names transition and boundary constraints over a row-by-row trace (Ben-Sasson et al., 2018b). Stage two is the low-degree extension: the trace is interpolated to a polynomial and evaluated on a larger Reed-Solomon domain. Stage three is FRI proximity: the codeword is Merkle-committed and proved to be close to a low-degree polynomial. Stage four is Fiat-Shamir: every verifier challenge is replaced by a hash of the transcript so far, making the protocol non-interactive in the random oracle model.
Each stage contributes a soundness term that feeds into the composed bound derived in Section 5. Table 34.2, in the closing section on parameter knobs, names the knobs an operator turns to tighten any specific term.
The operator decision is which of the four stages dominates the composed bound at a chosen parameter point. Section 5.5 gives the summation.
Eight Fibonacci steps, one non-interactive proof
Section titled “Eight Fibonacci steps, one non-interactive proof”The running example is a length-8 Fibonacci trace over the field F_97. The trace starts from (1, 1) and applies the recurrence trace[i+2] = trace[i+1] + trace[i], producing (1, 1, 2, 3, 5, 8, 13, 21). The values are small and nontrivial modulo 97. The initial value 1 appears twice because the trace starts from (1, 1). The AIR records one transition constraint trace[i+2] - trace[i+1] - trace[i] == 0 for i in 0..5 and two boundary constraints trace[0] == 1, trace[1] == 1. Six transition residues plus two boundary residues yield an all-zero residue list for the honest trace.
The field F_97 is chosen deliberately. Its multiplicative group has order 96 = 2^5 * 3. The 2-adic factor 2^5 = 32 is exactly large enough to support a size-32 LDE domain at blowup factor four over an order-8 trace domain. The FRI module in Ch 32 uses the same prime. The folding conventions carry over without adjusting field arithmetic.
The trace domain is the order-8 subgroup generated by g_8 = 64 (derived from the primitive root 5 via 5^12 mod 97 = 64). The LDE domain is a coset 5 * <g_32> of the order-32 subgroup generated by g_32 = 28, shifted outside the subgroup by multiplying through by 5. Two properties of that coset are load-bearing. It is disjoint from the trace domain, which keeps the trace-domain vanishing polynomial nonzero on every LDE point. It is closed under negation, because -1 = g_32^16 lies inside the order-32 subgroup, and FRI folding only requires negation-closure on the LDE domain.
# Block 1: pedagogical slice of starks.arithmetization.fibonacci_air and# evaluate_air (stdlib only).
PRIME = 97TRACE_LENGTH = 8
def fibonacci_trace(length, prime): if length < 2: raise ValueError("length must be at least two") trace = [1, 1] for _ in range(length - 2): trace.append((trace[-1] + trace[-2]) % prime) return trace
def transition_residue(trace, i, prime): return (trace[i + 2] - trace[i + 1] - trace[i]) % prime
def boundary_residues(trace, prime): return [(trace[0] - 1) % prime, (trace[1] - 1) % prime]
trace = fibonacci_trace(TRACE_LENGTH, PRIME)transitions = [transition_residue(trace, i, PRIME) for i in range(TRACE_LENGTH - 2)]boundaries = boundary_residues(trace, PRIME)
print("trace:", trace)print("transition residues:", transitions)print("boundary residues:", boundaries)# ==> trace: [1, 1, 2, 3, 5, 8, 13, 21]# ==> transition residues: [0, 0, 0, 0, 0, 0]# ==> boundary residues: [0, 0]Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch34/, one file per block. Appendix C covers the clone and the environment they run on.
The residue list is all zeros. A prover claims this trace satisfies the AIR and constructs a non-interactive proof. A verifier accepts after three checks: the AIR check on the sent trace, the FRI proximity check on the committed codeword, and a consistency check between the codeword and the Lagrange interpolation of the trace at every query position. Sections 3 and 4 build each piece.
AIR, LDE, and the Reed-Solomon lift
Section titled “AIR, LDE, and the Reed-Solomon lift”The following symbols are reserved throughout the chapter. Later sections assume these definitions without reintroduction.
| Symbol | Meaning |
|---|---|
p | Field prime (97 in the running example). |
L | Trace length (8). |
N | LDE domain size (32). |
rho | Code rate L / N (1/4). |
r_FRI | Number of FRI folding rounds, log_2 L for a degree bound L (3 for the toy). |
r_FS | Number of distinct public-coin Fiat-Shamir rounds. The count is configuration-dependent. The toy collapses to r_FRI + 1 = 4 (one challenge per fold, then the query round). The ethSTARK IOP has r_eth rounds, three plus one per entry of fri_step_list, per Theorem 5 of (Ben-Sasson, 2021), whose proof counts one more. On the theorem’s count, the r_FS = 6 figure used in Section 5.7 corresponds to a three-layer FRI step list. A different step list shifts the count by one per added or removed FRI layer. Section 5.3 lists the draws and gives both counts. |
mu | Number of independent FRI query paths. Each path picks one LDE position and follows it through every fold layer. Running mu paths gives mu independent draws against a delta_0-far word. |
g | Grinding bits on the transcript. |
q | Adversary’s quantum query budget. |
k | Target post-quantum soundness in bits. |
delta_0 | Proximity-gap threshold (relative Hamming distance). |
The symbol r is never used bare. When the fold-round count and the Fiat-Shamir-round count appear together, each carries its subscript.
Chapter 32 writes the degree bound as d. Here the degree bound is the trace length, so this chapter writes it L.
AIR is a compact algebraic description of a computation (Ben-Sasson et al., 2018b, sec. 2.2). A trace is a function trace : {0, ..., L - 1} -> F_p for trace length L and field prime p. A transition constraint is a polynomial over a sliding window of rows that must be zero at every starting position. The polynomial expression is syntactic, in the sense that it names no specific field element. A boundary constraint also names concrete row/value pairs (e.g. trace[0] == 1). An operator designing an AIR chooses the trace length, the window width, the polynomial expression for each transition constraint, and the row/value pairs for each boundary constraint. The choices reflect the computation’s structure, not its general-case input.
The Reed-Solomon low-degree extension turns the trace into a codeword. Let T = {omega^i : i = 0..L-1} be the trace domain, where omega is a generator of order L in F_p^*. Lagrange interpolation produces the unique polynomial t(x) of degree less than L satisfying t(omega^i) = trace[i]. The LDE domain D is a larger set of size N = L / rho, where rho is the code rate and rho^{-1} is the blowup factor. Evaluating t(x) on D yields the Reed-Solomon codeword c = (t(x) : x in D) of length N. The codeword sits inside the Reed-Solomon code of degree less than L, relative distance at least 1 - rho.
The operator decision is the blowup factor 1/rho, which sets the proximity-gap threshold in Section 5.1 and thereby the per-query catch probability on a word far from the code.
t(x) is evaluated on the size-32 LDE coset, producing a Reed-Solomon codeword at rate 1/4.Reed-Solomon encoding is not a cryptographic step. It is a redundancy injection: a size-L trace becomes a size-N codeword, and any L of the N evaluations suffice to reconstruct t(x). The redundancy is what FRI exploits. A codeword, the evaluation of a polynomial of degree less than L, passes the FRI proximity test. A word far from every such polynomial fails with high probability. Section 5.1 quantifies the threshold.
Three papers are involved and the credit is worth stating precisely. FRI and its first soundness analysis are due to Ben-Sasson, Bentov, Horesh, and Riabzev (Ben-Sasson et al., 2018a). That analysis needed a query count that stays large even at small rates. DEEP-FRI improved it by sampling outside the evaluation domain (Ben-Sasson, Goldberg, et al., 2020). The proximity-gap theorem is a separate and later result, due to Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf (BCIKS), who prove it for Reed-Solomon codes out to the Johnson / Guruswami-Sudan list-decoding bound 1 - sqrt(rho) (Ben-Sasson, Carmon, et al., 2020). It is often credited to the FRI paper instead. The FRI paper is where the protocol comes from, not the gap.
BCIKS Theorem 1.2 bounds Pr[delta(f_beta, C) <= delta_0] by a regime-dependent error eps_gap(rho, N, |F_p|, delta_0). In the unique-decoding regime delta_0 <= (1 - rho) / 2 the bound is O(N / |F_p|). In the Johnson regime (1 - rho) / 2 < delta_0 < 1 - sqrt(rho) it is O(N^2 / (|F_p| * poly(rho, eta))) with eta = (1 - sqrt(rho)) - delta_0, which requires |F_p| at least quadratic in N to stay non-trivial.
The unique-decoding radius (1 - rho) / 2 and the Johnson bound 1 - sqrt(rho) are routinely conflated in informal STARK writeups. The BCIKS proximity gap holds out to the larger Johnson bound, but with the larger Johnson-regime error term, not the simpler O(N / |F_p|) form. Over mu independent FRI query paths, the soundness error against a delta_0-far word is at most (1 - delta_0)^mu: each path catches a faulty position with probability at least delta_0, and the verifier accepts a faulty word only if all mu paths miss.
Building the proof
Section titled “Building the proof”Five subsections follow: arithmetization, LDE, FRI with Fiat-Shamir challenges, transcript and grinding, prover and verifier wiring.
4.1 Arithmetization
Section titled “4.1 Arithmetization”The AIR type lives in the ch34-starks package under solutions/. The core types are TransitionConstraint (with a window width and an evaluator callback), BoundaryConstraint (with a row index and an expected value), and AIR (a container). The Fibonacci AIR is produced by a single helper that wires the recurrence and the two boundaries together.
# Block 2: pedagogical slice of starks.arithmetization.AIR and# TransitionConstraint (stdlib only).
from collections import namedtuple
TransitionConstraint = namedtuple("TransitionConstraint", ["window", "evaluator", "name"])BoundaryConstraint = namedtuple("BoundaryConstraint", ["row", "expected", "name"])
def fib_rec(trace, i, p): return (trace[i + 2] - trace[i + 1] - trace[i]) % p
fibonacci_transition = TransitionConstraint(window=3, evaluator=fib_rec, name="fib_rec")fibonacci_boundaries = [ BoundaryConstraint(row=0, expected=1, name="fib_init_0"), BoundaryConstraint(row=1, expected=1, name="fib_init_1"),]
def evaluate_air(trace, transitions, boundaries, prime): if len(trace) < max((t.window for t in transitions), default=0): raise ValueError("trace shorter than largest window") residues = [] for t in transitions: for i in range(len(trace) - t.window + 1): residues.append(t.evaluator(trace, i, prime)) for b in boundaries: residues.append((trace[b.row] - b.expected) % prime) return residues
trace = [1, 1, 2, 3, 5, 8, 13, 21]residues = evaluate_air(trace, [fibonacci_transition], fibonacci_boundaries, 97)print(len(residues), "constraints;", "all zero" if not any(residues) else "violations")# ==> 8 constraints; all zeroA malformed trace (length mismatched to AIR, window larger than trace) raises ValueError eagerly. The error contract throughout the package is: raise on structural malformation, return a nonzero residue on a trace that fails the constraint. The inline blocks in this chapter follow the same contract.
4.2 LDE
Section titled “4.2 LDE”The trace polynomial is interpolated via Lagrange on the trace domain, then evaluated on the LDE domain. The LDE module exposes the domain constructors and the polynomial-evaluation routine. Block 3 interpolates the Fibonacci trace and evaluates it at the first four LDE points.
# Block 3: pedagogical slice of starks.lde.extend_polynomial and# starks.arithmetization.interpolate_trace (stdlib only).
PRIME = 97TRACE_GEN = 64 # order 8LDE_GEN = 28 # order 32COSET_SHIFT = 5 # outside the order-32 subgroup
def power_sequence(g, n, p): seq, x = [1], 1 for _ in range(n - 1): x = (x * g) % p seq.append(x) return seq
def lagrange_coeffs(ys, xs, p): n = len(ys) coeffs = [0] * n for j in range(n): num = [1] denom = 1 for m in range(n): if m == j: continue new = [0] * (len(num) + 1) for idx, c in enumerate(num): new[idx] = (new[idx] - c * xs[m]) % p new[idx + 1] = (new[idx + 1] + c) % p num = new denom = (denom * (xs[j] - xs[m])) % p scale = (ys[j] * pow(denom, -1, p)) % p for idx, c in enumerate(num): coeffs[idx] = (coeffs[idx] + scale * c) % p return coeffs
def eval_poly(coeffs, x, p): result = 0 for c in reversed(coeffs): result = (result * x + c) % p return result
trace = [1, 1, 2, 3, 5, 8, 13, 21]trace_dom = power_sequence(TRACE_GEN, 8, PRIME)lde_dom = [(COSET_SHIFT * x) % PRIME for x in power_sequence(LDE_GEN, 32, PRIME)]
coeffs = lagrange_coeffs(trace, trace_dom, PRIME)codeword = [eval_poly(coeffs, x, PRIME) for x in lde_dom]
print("trace domain size:", len(trace_dom), "LDE domain size:", len(lde_dom))print("first four codeword values:", codeword[:4])# ==> trace domain size: 8 LDE domain size: 32# ==> first four codeword values: [95, 73, 80, 45]The codeword has 32 values. Four appear in Block 3. The full 32-point codeword is the Reed-Solomon encoding of t(x) on the coset. Every LDE point is a nonzero residue modulo 97, and the vanishing polynomial Z_T(x) = prod_{w in T} (x - w) is nonzero on every LDE point by the coset construction. This simplified pipeline does not need Z_T (Section 4.5 covers the simplification), but the disjointness is load-bearing for any future extension with a composition polynomial.
4.3 FRI with Fiat-Shamir challenges
Section titled “4.3 FRI with Fiat-Shamir challenges”FRI folds the codeword in rounds. Each round halves the domain by pairing (x, -x) and replacing them with a single value at x^2. The folded value is even + beta * odd / x, where even = (f(x) + f(-x)) / 2, odd = (f(x) - f(-x)) / 2, and beta is the round’s challenge. The interactive version of this mechanic appears in Ch 32. Here the verifier’s beta is drawn from the Fiat-Shamir transcript. In the full protocol Section 4.4 absorbs each round’s Merkle root into the transcript before the next beta is squeezed. Block 4 drops the per-round absorb for compactness and shows only the squeeze-and-fold loop; Block 5 uses the full production prover, which performs the absorb step.
# Block 4: pedagogical slice of starks.fri_full.fri_prove folding loop# plus starks.transcript.Transcript.squeeze_int (stdlib only).
import hashlib
class Transcript: def __init__(self, sep): self.state = hashlib.sha256(b"ch34-tx|" + sep).digest() self.counter = 0
def absorb(self, label, data): length = len(data).to_bytes(8, "big") self.state = hashlib.sha256(self.state + label + length + data).digest()
def squeeze_int(self, label, modulus): ctr = self.counter.to_bytes(8, "big") self.counter += 1 buf = hashlib.sha256(self.state + label + ctr).digest() self.state = hashlib.sha256(self.state + buf).digest() return int.from_bytes(buf, "big") % modulus
def fold_once(cw, dom, beta, p): if len(cw) != len(dom) or len(cw) & 1: raise ValueError("codeword must be even-length and match domain") half = len(cw) // 2 two_inv = pow(2, -1, p) new_cw, new_dom = [], [] # In a cyclic-group domain laid out as powers of a single generator, # x and -x sit half the domain apart, so cw[i + half] is f(-x). for i in range(half): fx, f_neg, x = cw[i], cw[i + half], dom[i] even = ((fx + f_neg) * two_inv) % p odd = ((fx - f_neg) * two_inv) % p odd = (odd * pow(x, -1, p)) % p new_cw.append((even + beta * odd) % p) new_dom.append((x * x) % p) return new_cw, new_dom
PRIME = 97codeword = [95, 73, 80, 45, 24, 3, 63, 18, 38, 81, 79, 6, 9, 53, 69, 41, 75, 50, 76, 28, 2, 78, 54, 93, 46, 92, 33, 46, 56, 12, 85, 68]domain = [5, 43, 40, 53, 29, 36, 38, 94, 13, 73, 7, 2, 56, 16, 60, 31, 92, 54, 57, 44, 68, 61, 59, 3, 84, 24, 90, 95, 41, 81, 37, 66]
tx = Transcript(b"ch34-stark")betas = []for j in range(3): beta = tx.squeeze_int(b"fri-beta-" + j.to_bytes(4, "big"), PRIME) betas.append(beta) codeword, domain = fold_once(codeword, domain, beta, PRIME)
print("betas mod 97:", betas)print("folded codeword after 3 rounds:", codeword)# ==> betas mod 97: [35, 40, 48]# ==> folded codeword after 3 rounds: [85, 85, 85, 85]After three folds, the codeword is the constant 85 on a size-4 domain. Three folds already suffice for a degree-bound-8 codeword on a 32-point domain: each fold halves the codeword’s degree bound, so three folds drop the bound from 8 to 1 (constant). The standalone package also stops at three, and the count is load-bearing rather than a convenience: a fourth fold would collapse every polynomial of degree below 16 to a constant as well, so a verifier that folds four times and checks constancy accepts a rate-1/2 code where the STARK claims rate 1/4. The fold count is log_2 L for a degree bound L, and the final codeword lives on N / L points. A FRI verifier checks three things: every round’s Merkle commitment opens consistently at the queried positions and at their fold partners, every round-to-round fold-consistency equation holds, and the final codeword is constant. The fold partner is not optional. The fold equation has two inputs, and a verifier that authenticates only the queried leaf lets the prover choose the other one freely, which is enough to fold any codeword onto any committed successor. A starting word not close to any polynomial of degree less than the rate-implied bound produces a non-constant final word except with probability bounded in Section 5.1.
The operator decision is the tradeoff between the number of queries, the folding depth, and the grinding difficulty, whose nonce the transcript absorbs before the query positions are drawn.
beta is derived from the transcript that absorbed the previous round's Merkle root. The green final box marks the constant that three folds make of a codeword of degree below L = 8, on N / L = 4 points. A fourth fold would flatten degree below 16 as well.4.4 Transcript and grinding
Section titled “4.4 Transcript and grinding”Every FRI fold challenge and every query position is squeezed from the same transcript. The transcript absorbs every Merkle root as it is produced, so later squeezes depend on every commitment the prover has made. A prover cannot choose beta to cancel out a flawed word, because beta is bound to the committed word before the prover sees it.
Grinding adds a per-proof proof-of-work (PoW) in front of the query-selection phase. After the last Merkle root is absorbed and before any query position is squeezed, the prover searches for a nonce such that sha256(state || nonce) has at least g trailing zero bits and absorbs it. The verifier checks the nonce against the same state, absorbs it, and only then derives the positions, so the nonce decides which positions are queried. That order is load-bearing. Grinding attenuates the query-miss term of the soundness budget by a factor of 2^{-g} because every query set a classical forger gets to see costs about 2^g hash evaluations on average to reach (Section 5.4 gives the quantum figure). A nonce found after the positions are fixed prices nothing: the forger searches for a favorable query set for free and pays the proof-of-work once at the end. ethSTARK places its proof-of-work at the same point, after all of the prover’s commitments and before the query phase (Ben-Sasson, 2021, sec. 3.11.3 and §6.3). Grinding does not attenuate the proximity-gap or bad-beta terms, because those challenges were squeezed before the nonce existed. Section 5.4 gives the rule that decides which terms a nonce reaches.
Deployed and near-deployed FRI pipelines differ widely in how many bits they grind. Block and Tiwari’s survey of parameters current on 6 May 2024 found none in RISC Zero’s, 16 in Plonky2’s, 24 in Stone’s example configuration, 31 in the SHARP verifier’s and 32 in dYdX’s (Table 2 in Block & Tiwari, 2024). The toy sets g = 4 or g = 6 to keep the example fast.
4.5 Prover and verifier wiring
Section titled “4.5 Prover and verifier wiring”The toy prover sends the trace in the clear alongside the FRI proof. A production STARK does not send it: the verifier checks the constraints through a composition polynomial (a random linear combination of the transition and boundary constraint quotients) that FRI also proves low-degree. Not sending the trace is not the same as hiding it. Zero knowledge needs a separate randomization of the trace and its commitments, which this chapter, like its toy, leaves out. This chapter drops the composition polynomial for pedagogical compactness.
The toy checks the AIR directly on the transmitted trace. Its additional consistency check ensures that the committed low-degree word encodes that trace. For every FRI query path, the committed word’s opening at the path’s top-layer LDE point x must equal t(x), where t(x) is the Lagrange interpolation of the sent trace. A production STARK proves the constraint relations without sending the full trace, using polynomial checks omitted from this toy.
The consistency miss probability is at most (L - 1) / N per path. Two distinct polynomials of degree less than L agree at no more than L - 1 points on the N-element LDE domain, and the FRI-query top-layer position is uniform on that domain under Fiat-Shamir. Over mu independent paths the compound miss probability is at most ((L - 1) / N)^mu. The route a production STARK closes (composition polynomial plus DEEP consistency) is left open in the toy by design.
# Block 5: pedagogical slice of starks.prover.stark_prove and# starks.verifier.stark_verify (stdlib only).
import syssys.path.insert(0, "solutions/ch34-starks/src")from starks.arithmetization import fibonacci_air, fibonacci_tracefrom starks.prover import stark_provefrom starks.verifier import stark_verify
air = fibonacci_air()trace = fibonacci_trace()honest_proof = stark_prove(air, trace, num_queries=6, grinding_bits=4)print("honest proof accepted:", stark_verify(air, honest_proof, num_queries=6, grinding_bits=4))
forged_proof = stark_prove(air, trace, num_queries=6, grinding_bits=4)forged_proof.trace[4] = (forged_proof.trace[4] + 1) % 97print("forged proof accepted:", stark_verify(air, forged_proof, num_queries=6, grinding_bits=4))# ==> honest proof accepted: True# ==> forged proof accepted: FalseBlock 5’s forgery changes one trace value, which breaks the recurrence, so the verifier’s AIR check rejects it before FRI or the consistency check runs. A proof that only the consistency check can catch keeps the honest trace and commits a different word: the LDE of a trace with one value changed. Block 6 builds it from the package’s primitives, seeding the transcript as the prover and the verifier do.
# Block 6: the honest trace sent with the LDE of another trace committed# (stdlib only).
import syssys.path.insert(0, "solutions/ch34-starks/src")from starks.arithmetization import (evaluate_air, fibonacci_air, fibonacci_trace, interpolate_trace)from starks.fri_full import fri_prove, fri_verifyfrom starks.lde import eval_poly, extend_polynomial, lde_domain, trace_domainfrom starks.prover import STARKProoffrom starks.transcript import Transcriptfrom starks.verifier import stark_verify
air, trace = fibonacci_air(), fibonacci_trace()other = list(trace)other[4] = (other[4] + 1) % 97 # the trace Block 5 forgedt_dom, l_dom = trace_domain(), lde_domain()honest_word = extend_polynomial(interpolate_trace(trace, t_dom, 97), l_dom, 97)swapped_word = extend_polynomial(interpolate_trace(other, t_dom, 97), l_dom, 97)
def seeded_transcript(): # What stark_prove and stark_verify absorb before FRI starts. tx = Transcript(domain_sep=b"ch34-stark") for label, value in [(b"prime", 97), (b"trace-length", 8), (b"lde-size", 32)]: tx.absorb_int(label, value, num_bytes=8) for v in trace: tx.absorb_int(b"trace-value", v, num_bytes=8) return tx
fri = fri_prove(initial_codeword=swapped_word, initial_domain=l_dom, prime=97, transcript=seeded_transcript(), num_queries=6, grinding_bits=4, degree_bound=8)proof = STARKProof(trace=list(trace), trace_commitment=fri.commitments[0], fri_proof=fri)
fri_ok = fri_verify(proof=fri, initial_domain=l_dom, prime=97, transcript=seeded_transcript(), num_queries=6, grinding_bits=4, degree_bound=8)coeffs = interpolate_trace(trace, t_dom, 97)mismatches = sum(eval_poly(coeffs, l_dom[o.leaf_index], 97) != o.leaf_value for o in fri.query_openings[0])differ = sum(a != b for a, b in zip(honest_word, swapped_word))
print("AIR residues on the sent trace all zero:", not any(evaluate_air(air, proof.trace)))print("FRI accepts the committed word:", fri_ok)print("consistency fails at", mismatches, "of 6 query positions")print("the two words differ at", differ, "of 32 LDE points")print("proof accepted:", stark_verify(air, proof, num_queries=6, grinding_bits=4))# ==> AIR residues on the sent trace all zero: True# ==> FRI accepts the committed word: True# ==> consistency fails at 6 of 6 query positions# ==> the two words differ at 32 of 32 LDE points# ==> proof accepted: FalseThe committed word is a codeword, the LDE of a polynomial of degree less than L, so FRI accepts it, and the sent trace satisfies the AIR. Only the consistency check rejects the proof, and here it rejects at every query position. Changing one trace value changes the interpolant by a multiple of one Lagrange basis polynomial, whose roots are the other points of the trace domain. The LDE coset avoids the trace domain, so the two words disagree at all 32 of its points. The (L - 1) / N bound above is for the worst case, a different polynomial of degree less than L that agrees with t(x) at L - 1 of the N points. Block 6’s proof is an inconsistent proof of the toy’s true statement, not an accepted proof of a false one.
Blocks 5 and 6 import the standalone package for the orchestration. Inline re-declaration of every primitive would expand either block past its pedagogical scope. The package itself re-implements each primitive stdlib-only. Blocks 1 through 4 remain self-contained so a reader can follow each mechanic without the full pipeline in scope.
Composing the soundness budget
Section titled “Composing the soundness budget”Each stage of the pipeline contributes a separate soundness term. The composed bound partitions into a pre-query part, a query-miss part, and a binding part. Under QROM, the result is multiplied at L4 by the DFMS20-shaped factor of the model Section 5.3 introduces, which is stipulated rather than conservative (Ch 33). The notation follows the symbol table introduced earlier.
5.1 Per-round FRI soundness
Section titled “5.1 Per-round FRI soundness”Let C be the Reed-Solomon code over F_p of rate rho on the LDE domain D of size N. Let f : D -> F_p be a function and delta(f, C) its relative Hamming distance from the code. The tight form of the proximity-gap theorem (Ben-Sasson, Carmon, et al., 2020) bounds the probability over a uniformly random fold challenge beta in F_p that the folded function f_beta has delta(f_beta, C') <= delta_0, given delta(f, C) > delta_0. Theorem 1.2 of BCIKS gives the regime-dependent error eps_gap(rho, N, |F_p|, delta_0) defined above: O(N / |F_p|) for delta_0 in the unique-decoding regime, and O(N^2 / (|F_p| * poly(rho, eta))) for delta_0 in the Johnson regime (with eta = (1 - sqrt(rho)) - delta_0 the slack from the Johnson bound). Over mu independent FRI query paths, the query-path miss probability on a delta_0-far word is at most (1 - delta_0)^mu.
Three thresholds appear in the coding-theory literature and are routinely conflated. The unique-decoding radius is (1 - rho) / 2. Below this radius every received word decodes to at most one codeword. The Johnson / Guruswami-Sudan list-decoding radius is 1 - sqrt(rho). Below this radius the list is polynomial-size and BCIKS Theorem 1.2 gives a proven proximity gap. The capacity bound is 1 - rho, and production STARK pipelines have set parameters above the Johnson bound on the strength of conjectured list-decoding behavior reaching up to roughly that radius.
At rate rho = 1/4 (the toy’s blowup factor four) the Johnson bound is 1 - sqrt(1/4) = 0.5, so delta_0 < 0.5 applies under the proven bound. At rho = 1/8 the Johnson bound rises to 1 - sqrt(1/8) ≈ 0.646. At rho = 1/16 it rises to 1 - 1/4 = 0.75. The unique-decoding values at the same rates are 0.375, 0.4375, and 0.46875 respectively. The chapter uses the Johnson bound throughout because BCIKS proves the proximity gap for every radius strictly below it. Theorem 1.2’s interval is open at 1 - sqrt(rho), and its Johnson-regime error grows as the slack eta shrinks. Chapter 35 evaluates its margin model at the radius itself, which is why its figures are labelled as the model’s output rather than as the theorem’s.
5.2 Composition across folding rounds
Section titled “5.2 Composition across folding rounds”For r_FRI folding rounds, the union-bound composition from (Ben-Sasson et al., 2018a), with the per-round term from (Ben-Sasson, Carmon, et al., 2020), yields
eps_FRI <= r_FRI * eps_gap(rho, N, |F_p|, delta_0) + (1 - delta_0)^mu.
The first term bounds the aggregate bad-beta probability across r_FRI fold rounds via the union bound. Each round’s contribution eps_gap follows the regime split from Section 5.1. The second term bounds the probability that mu independent FRI query paths all miss the faulty positions of a delta_0-far word. Only the second term decreases in mu: the bad-beta union-bound term is independent of mu and is controlled by |F_p|, N, rho, and the chosen regime. Increasing mu tightens the query-miss term exponentially at the cost of proof size. Tightening the bad-beta term requires either a larger field, a smaller domain, or operating in the unique-decoding regime where eps_gap is only O(N / |F_p|). Under the BCIKS bound used here, the Johnson regime needs |F_p| quadratic in N to stay non-trivial. That is a limitation of this bound rather than of the regime: Ben-Sasson, Carmon, Haböck, Kopparty and Saraf (ePrint 2025/2055, November 2025) reduce the number of exceptional challenges up to the Johnson radius from quadratic to linear in N, at zero proximity loss, a result Chapter 35 names and whose constants this chapter’s arithmetic does not instantiate (Ben-Sasson et al., 2025).
For the F_97 toy parameters, the toy’s numerical soundness bound is trivially vacuous: the field is far too small to support the BCIKS gap term at any reasonable delta_0. The toy demonstrates the mechanics of AIR, LDE, FRI folding, transcript binding, and consistency checks; it is not a security parameter set. Production systems rely on concrete parameter analyses combining a large base field, a higher-degree challenge field where needed, substantial query repetition, Merkle binding, and grinding. Real parameter sets must evaluate the BCIKS / FRI error terms directly rather than infer security from mu and g alone. ethSTARK Documentation §5.10 carries the worked example for both conjectured and provable IOP knowledge soundness (Ben-Sasson, 2021).
5.3 Fiat-Shamir compilation via DFMS20
Section titled “5.3 Fiat-Shamir compilation via DFMS20”The interactive STARK protocol absorbs r_FS Fiat-Shamir transcripts, where r_FS counts the distinct public-coin rounds the verifier challenges. The mapping between r_FRI fold rounds and r_FS depends on the protocol’s internal structure, not on r_FRI alone. The toy collapses to r_FS = r_FRI + 1 = 4: one challenge per fold, then the query round.
Theorem 5 of (Ben-Sasson, 2021) gives the ethSTARK IOP a total round count r_eth = 3 + |fri_step_list|. Its verifier draws the constraint randomness, the DEEP query and the FRI combination randomness, then one challenge per FRI commit-phase layer and the query round. The theorem’s proof counts each draw, |fri_step_list| + 4 in all, one more than the theorem states, and this chapter uses the theorem’s count. (r_eth is the ethSTARK-paper symbol k, renamed here to avoid colliding with the chapter’s k for target post-quantum soundness in bits.)
The r_FS = 6 figure used in Section 5.7 corresponds to a three-layer FRI step list. Adding or removing one FRI layer shifts r_FS by one, and the per-challenge width under the DFMS20-shaped model rule c_bits >= 2 log_2(2q + 1) + k / r_FS, which at q = 2^80 is just above 162 + k / r_FS and rounds up to the next integer (Ch 33 Table 33.1), shifts accordingly. At k = 128, going from r_FS = 6 to r_FS = 7 lowers the per-challenge width from 184 to 181 bits, a 3-bit change.
Ch 33 sets FRI-based SNARKs apart from the generic DFMS20 application for a specific reason. FRI has a dedicated Fiat-Shamir analysis that exploits its round-by-round soundness, and applying DFMS20 directly overshoots the published QROM loss by additional powers of q (Block et al., 2023). The rule in this subsection is therefore a stipulated model rather than the tight instrument, and it is not a conservative one either: Ch 33 records that DFMS20’s corollary carries an additive challenge-space term the model drops, so the widths the model produces are its own outputs and not certified minima. It is used here because it is protocol-agnostic and easy to size against. For q quantum oracle queries and interactive soundness error eps_interactive, the chapter’s stipulated multiplicative model, cut from DFMS20’s corollary as Ch 33 sets out (Don et al., 2020), is
eps_FS <= (2q + 1)^{2 r_FS} * eps_interactive.
The interactive soundness error combines the FRI term and the AIR consistency term. For the toy, eps_interactive <= eps_FRI + ((L - 1) / N)^mu. The ((L - 1) / N)^mu term is the mu-times-repeated Schwartz-Zippel bound derived in Section 4.5: each of the mu FRI-query positions is uniform on the N-element LDE domain under Fiat-Shamir, and two distinct polynomials of degree less than L agree at no more than L - 1 points. The multi-round Fiat-Shamir subsection of Ch 33 states DFMS20’s Corollary 13 and defines the stipulated model cut from it. This section invokes that model, not a theorem-backed bound for this STARK.
5.4 Grinding
Section titled “5.4 Grinding”At a grinding difficulty of g bits, a candidate nonce passes the check with probability 2^{-g}, so a classical forger pays about 2^g hash evaluations on average for every query set a transcript-forging attempt gets to see, because the nonce is absorbed before the positions are drawn (Section 4.4). g is the difficulty, not the length of the nonce: the toy encodes its nonce in 8 bytes, ethSTARK searches a 64-bit nonce, and ethSTARK names the difficulty proof_of_work_bits and states the honest prover’s cost as an expectation (Ben-Sasson, 2021, sec. 3.11.3 and §6.3). What grinding attenuates is decided by where the nonce sits in the transcript. A proof-of-work inserted before a round multiplies that round’s soundness error by 2^{-g} and touches nothing squeezed before it (Theorem 6 in Ben-Sasson, 2021, sec. 6.3). The toy’s nonce sits after the last commitment and before the query draw, so it attenuates the whole of eps_query: the query-path miss, and the trace-consistency check of Section 4.5, which is evaluated at the same drawn positions. It does not attenuate the proximity-gap or bad-beta terms, because the fold challenges were squeezed before the nonce existed. ethSTARK’s parameter section places grinding at the same point, before the query selection (Ben-Sasson, 2021, sec. 5.10). Its 128-bit provable-soundness configuration goes further: s = 141 queries, a grinding parameter of 4 on every round from the third up to the one before the queries, and 20 on the query round, which is the same theorem applied earlier in the transcript (Ben-Sasson, 2021, sec. 7.1.1, pp. 50-51, and Theorem 6 in §6.3). Section 5.5 reflects the partition.
Against a quantum forger the per-attempt figure is not 2^g. The marked-nonce density is 2^{-g} whatever the number of valid nonces, so amplitude amplification finds one in about 2^{g/2} oracle queries (Grover, 1996), and the query-model margin grinding buys halves accordingly. That is a query-model figure rather than a cost figure. Each amplification step evaluates the hash circuit coherently rather than once, and the search parallelizes only as the square root of the machine count where classical grinding parallelizes linearly, so the realized margin sits above the naive halving. The 2^{-g} attenuation of eps_query is the part that survives the change of adversary model; the per-attempt work factor is not. Every composed bound in Section 5.5 is stated in the classical ROM, and Section 5.6 gives the standing caveat on the quantum composition.
5.5 Summation formula
Section titled “5.5 Summation formula”Combining Sections 5.1 through 5.4, the soundness budget partitions into a pre-query part, a query-miss part, and a binding part:
eps_total <= eps_pre + 2^{-g} * eps_query + eps_bind
The three terms are:
eps_pre = r_FRI * eps_gap(rho, N, |F_p|, delta_0)is the aggregate bad-fold-challenge / proximity-gap term across fold rounds, witheps_gapfollowing the unique-decoding-vs-Johnson-regime split from Sections 5.1 and 5.2.eps_query = (1 - delta_0)^mu + ((L - 1) / N)^muis the query-path miss probability against adelta_0-far word plus the Schwartz-Zippel consistency miss (Sections 5.1 and 4.5).eps_bindbounds the Merkle commitment binding error under the hash function’s collision-resistance assumption.
The grinding factor 2^{-g} attenuates only eps_query. Grinding raises the per-attempt cost of the query-selection brute force; it does not attenuate the proximity-gap or bad-beta failure modes (Section 5.4). The classical-ROM soundness level is then
k_classical ≈ -log_2(eps_total).
Block et al. 2023 (Block et al., 2023) proves Fiat-Shamir security of the FRI compilation and Merkle binding, for FRI that folds by two over a smooth multiplicative subgroup, in both the classical ROM and the QROM, under the paper’s parameter hypotheses. Its Corollary 1.2 states adaptive soundness and knowledge error q * eps_rbr + O(q^2 / 2^kappa) against classical q-query adversaries and Theta(q * eps_fs) against O(q)-query quantum adversaries. The quantum half comes, with no computational assumption, from Chiesa, Manohar and Spooner’s QROM theorem for the BCS transformation (Chiesa et al., 2019). The partition above extends that result with the grinding and Schwartz-Zippel terms. Section 5.6 records that no published work had composed those terms with the QROM bound at the deployment parameters of the production FRI pipelines this Part reads.
Where its hypotheses hold, the FRI-specific bound is the tighter instrument, though its constants are unstated. The generic (2q + 1)^{2 r_FS} factor of Section 5.3 is the model, which exceeds it by powers of q and drops DFMS20’s additive challenge-space term. Neither is an end-to-end accounting at deployment parameters. See Section 5.6.
Section 5.7 works that model’s challenge-width arithmetic as a teaching exercise rather than as an operator decision.
5.6 Deployment-parameter QROM accounting
Section titled “5.6 Deployment-parameter QROM accounting”This section records what had been published on the QROM security of FRI’s Fiat-Shamir step, and what had not, for the production FRI pipelines this Part reads: Stone, Starknet’s Stwo, ZKsync Era’s Boojum, Plonky2 and Plonky3. It keeps five gaps apart, because they are not interchangeable, and each carries the date of the search or the reading it rests on. The literature search covered the record as it stood on 19 October 2026, through ePrint’s own search, arXiv and the web, Alexander Block’s publication page, and StarkWare’s repositories.
The published two-to-one result. Block et al. 2023, in the ePrint version read on 10 October 2026, prove asymptotic QROM Fiat-Shamir security for FRI and batched FRI that fold by two over a smooth multiplicative subgroup, under the paper’s parameter hypotheses. They obtain it by proving FRI’s round-by-round soundness and applying Chiesa, Manohar and Spooner’s QROM theorem (Block et al., 2023; Chiesa et al., 2019). The paper states outright that FRI run non-interactively via Fiat-Shamir is unconditionally secure, that is, with no computational assumption, in the quantum random oracle model (Block et al., 2023). The quantum bound’s constants are unstated, so it fixes no deployment parameters. The paper proves the FRI, batched-FRI and Plonky2-like results formally but only sketches the round-by-round knowledge soundness of ethSTARK and RISC Zero. StarkWare’s own concurrent ethSTARK documentation supplies a finer-grained Fiat-Shamir analysis of the later FRI rounds and of grinding (Ben-Sasson, 2021).
The deployed rate. One of the paper’s parameter hypotheses is a rate condition that conflicts with the parameters it goes on to analyze. Block et al.’s preliminaries assume that the degree bound and the evaluation domain’s size are powers of two, with the degree bound at most the square root of the domain size (§3.1 in Block et al., 2023). Taken literally, that caps the rate at the inverse square root of the domain size. Their Appendix A.2 applies Theorem 4.1, their round-by-round soundness theorem, to degree bounds , , and at rates 1/2, 1/4, 1/8 and 1/16, and none of those sixteen pairs meets the condition (Appendix A.2 in Block et al., 2023).
Block and Tiwari 2024 price FRI at deployed and near-deployed parameters in the classical ROM, and the same conflict appears there. They repeat the condition and then assess parameter sets that violate it (§2.1 and Table 2 in Block & Tiwari, 2024). Both papers were read for this on 1 October 2026 and again on 10 October 2026, and each states the condition once, in its preliminaries, with no reason given. This book therefore treats whether the theorems reach deployed rates as an open question, neither settled nor excluded.
Larger folds and transcript extensions. Block et al.’s FRI is narrower than Stone’s and Boojum’s. They state their theorems for FRI that folds by two down to a constant (Theorem 4.1 in Block et al., 2023). The Solidity verifier StarkWare publishes for Ethereum accepts only folds of 4, 8 or 16 (step sizes 2 to 4) after an unfolded first layer (StarkWare Industries, 2026). Every Stone proof it accepts therefore folds by more than two at each later step. The ethSTARK documentation proves round-by-round soundness for a general step schedule, for an IOP that commits one trace (Theorem 5 in Ben-Sasson, 2021), while every Cairo layout that verifier accepts commits a second, interaction trace (StarkWare Industries, 2026).
Boojum folds by more than two as well. In the source as it stood on 19 October 2026, its prover and verifiers compute the FRI schedule from the security target, grinding bits, Merkle cap size, LDE factor and trace length. The prover rejects a configuration that supplies a schedule of its own. Every step folds by 8, except that the last may fold by 4 or 2 (Matter Labs, 2026). For Stone, for Boojum, and for any other pipeline that folds by more than two, the asymptotic QROM bound is therefore an extension of published theorems, and for Stone the extension has to cover the interaction trace too. No paper had stated it by 19 October 2026.
Circle FRI. Block et al.’s theorems assume a smooth multiplicative subgroup of the field, so they do not cover Stwo’s circle FRI. StarkWare’s S-two whitepaper proves round-by-round knowledge soundness for it, the input Chiesa, Manohar and Spooner’s lift takes, but draws no quantum conclusion (Carmon et al., 2026). It states its non-interactive bound only in the classical random oracle model, notes without proof that the BCS analysis adapts to its mixed-domain Merkle trees, and defers the QROM to a future version (Carmon et al., 2026). As it stood on 19 October 2026 the whitepaper had no revision after 24 March 2026, and the search found no QROM statement for circle FRI elsewhere.
End-to-end composition. In the record as it stood on 19 October 2026, the search found no end-to-end QROM accounting at the concrete deployment parameters of any of the five pipelines. Such an accounting would compose a QROM bound for the pipeline’s FRI variant with Merkle binding, hash-output width, grinding, batching, recursion, and per-system parameter choices. Block and Tiwari 2024 perform the plain-FRI part of that composition in the classical ROM, with query-round grinding counted and batching and larger folds left out (Block & Tiwari, 2024, sec. 3.3). They report provable security 21 to 63 bits below conjectured in all but one of the surveyed parameter sets (Block & Tiwari, 2024).
Outside the literature, a project has published an accounting of its own system. Parano1d, a proof-of-work chain, publishes an end-to-end soundness theorem in the quantum random oracle model for the parameters its main network ran in September 2026, and concludes that they meet NIST Category 1 (Nemo, 2026). Its bound counting oracle queries alone reaches one half near queries, far short of the this Part sizes against. The Category 1 conclusion instead prices gates and circuit depth against AES-128 key search, and it rests on a declared minimum cost for each quantum query to its Poseidon2b hash, which the article states as a premise rather than proves.
The bound also assumes an idealized hash interface. It stands in for the fixed Poseidon2b permutation production uses and for the hashing its recursive verifier does inside the circuit, and the error that substitution introduces is stated as a condition, not evaluated. The round-by-round analysis of its commitments is the project’s own and lies outside Block et al.’s theorems. Its sequential query-count bound specializes the Chiesa-Manohar-Spooner lift that Block et al. also use. Its Category 1 main term specializes Chung, Fehr, Huang and Liao’s parallel compressed-oracle transition bound instead (Nemo, 2026). It supplies no number for any pipeline this Part reads.
An operator reading this section therefore inherits a concrete-accounting caveat for every pipeline this Part reads. On top of it come the open rate question for FRI over a smooth multiplicative subgroup, an unstated extension for larger folds such as Stone’s and Boojum’s and for Stone’s interaction trace, and a missing QROM statement for circle FRI. Every concrete soundness number against a quantum adversary for these pipelines is conditional on that pending composition and on whichever of those three apply to each pipeline.
5.7 CNFL specialization
Section titled “5.7 CNFL specialization”CNFL (Collect Now, Forge Later) threatens the integrity of future verification (Renz, 2026). At L4 the published results for FRI-based Fiat-Shamir (DFMS20 generically, and Block et al. 2023 specifically for FRI) are upper bounds on forgery probability. Section 5.6 records that no QROM instantiation of either at the deployment parameters of the production FRI pipelines this Part reads had been published. A bound too loose to certify 128 bits means the proof does not establish 128 bits at that parameter point. It constructs no attack. A loose bound is not evidence that an attack exists, and it is not evidence that none does.
A literature search of the record as it stood on 19 October 2026 found no published attack on FRI soundness that uses harvested transcripts. The risk is that a legacy verifier remains in service past the quantum crossover and accepts whatever a quantum adversary can then forge, which is a verifier-lifetime problem rather than a harvesting problem. HNDL threatens confidentiality of past data; CNFL threatens integrity of future verification.
The four-layer decomposition from Ch 31 lets the analysis route CNFL through a STARK layer by layer. L1 (AIR) is pure syntax with no cryptographic binding, so CNFL does not apply at L1. L3 (protocol orchestration) is information-theoretic for a STARK, with no long-term secret state. That leaves L2 and L4, and neither is a harvesting problem: both are questions about what a verifier still in service will accept.
L2 (FRI proximity and Merkle) combines an information-theoretic proximity check with collision-resistant Merkle commitments. FRI proximity carries no computational hardness assumption, so CNFL does not route through FRI’s soundness argument. Merkle binding is computational, and its quantum collision-security budget decays under the BHT and CNPS bounds (Brassard et al., 1998), (Chailloux et al., 2017). That decay is a future-verifier and hash-lifetime concern: a hash chosen today must hold against the quantum collision budget of any verifier still running at the CNFL crossover. It is not a transcript-harvesting concern, because a collision found in 2040 was already a collision in 2026, regardless of which transcripts were harvested.
L4 (Fiat-Shamir) is where the chapter’s narrow CNFL model puts the remaining exposure. It is not a harvesting route, since no attack on Fiat-Shamir FRI published by 19 October 2026 uses collected transcripts. It is an assurance gap: Section 5.6 records that no QROM bound had been instantiated at the deployment parameters of a production FRI pipeline this Part reads, and a legacy verifier keeps accepting proofs until it is replaced.
This section works the L4 challenge-width arithmetic with the DFMS20-shaped model Section 5.3 introduced. Ch 33 does not apply its multi-round rule to FRI. Used here as a teaching model, that per-round challenge-width rule gives c_bits >= 2 log_2(2q + 1) + k / r_FS. Take a worked example: r_FS = 6 (Section 5.3’s three-layer-FRI step list), q = 2^80, k = 128. Each Fiat-Shamir challenge must then draw from a space of c_bits >= 2 log_2(2^81 + 1) + 128 / 6, just above 162 + 21.33 = 183.33, so 184 bits.
This c_bits arithmetic is the simplified DFMS-style challenge-space rule from Ch 33, not an end-to-end ethSTARK soundness analysis. The ethSTARK base field is p = 2^61 + 20 * 2^32 + 1 (approximately 61 bits) per Section 5.10 of (Ben-Sasson, 2021). ethSTARK draws its FRI challenges from an extension field, with F_{p^3} giving approximately 183 bits. Under the conjectured-soundness setting from §5.10.1 of (Ben-Sasson, 2021), e = 3 reaches 128-bit security. Under the provable-IOP-knowledge-soundness setting from §5.10.2 the e = 3 pre-query bound is roughly 2^{-122}, falling short of 128 bits. The same section recommends e = 4 (extension field of about 244 bits, with 140 FRI query paths and 20 grinding bits) for 128-bit provable knowledge soundness, and §7.1.1 of (Ben-Sasson, 2021) gives 141 query paths. The 183-bit F_{p^3} figure falls one bit short of the model’s 184-bit threshold, but that comparison is a toy DFMS challenge-space calculation and should not be conflated with ethSTARK’s concrete provable analysis.
Starknet’s Stone prover, which proves the recursion root on the deployed path Chapter 35 reads first, runs FRI over the Cairo field itself, the 252-bit prime P = 2^251 + 17 * 2^192 + 1: its shipped Cairo parameters name that field and set use_extension_field to false, and every verifier challenge is an element of it (StarkWare, 2023). The cushion is measured on challenge entropy log_2 |C| rather than on storage width, and log_2 P = 251.0, so the field sits 67 bits above the model’s 184-bit threshold. The same caveat applies (concrete Starknet analyses are separate from the DFMS toy rule). A sub-128-bit base field at the same r_FS, without an extension-field upgrade, would fall below the threshold entirely.
The 184-bit requirement is the threshold of a model that is neither tight nor conservative (Ch 33): it comes from the protocol-agnostic DFMS20 rule, and Ch 33 shows the dedicated FRI loss is the lighter of the two. Section 5.6 records what that lighter bound covers and that its composition at the deployment parameters of the production FRI pipelines this Part reads had not been published. The 184-bit figure and the per-deployment cushions therefore both read as model outputs, and the concrete CNFL exposure for those pipelines is still pending.
Two kinds of response apply to CNFL at L4. Where a pairing-based wrapper sits over the STARK, the wrapper is replaced, because Shor breaks it. Inside the STARK, only an applicable analysis of the composed deployment can say whether the deployed parameters meet the target. Changing them in place is a candidate route, and that analysis would also have to say whether it suffices or whether the STARK needs more. ZKsync and Starknet are the two reference cases.
ZKsync Era under the Boojum upgrade runs a FRI-based inner STARK proof. The final implementation stage pairs the inner STARK with a non-transparent pairing-based SNARK that compresses it to an Ethereum-verifiable proof. This hybrid architecture is documented in the ZKsync Boojum announcement (ZKsync, 2023). (The precise wrapper construction beyond “non-transparent pairing-based SNARK” is an implementation detail the announcement does not pin down.)
CNFL at L4 in the inner STARK is conditional on the deployment-parameter QROM accounting from Section 5.6, on the open rate question, and on the extension to Boojum’s larger folds. CNFL at the outer wrapper is not conditional on anything: it is a Shor problem at the pairing assumption, and a Shor-capable adversary forges proofs at the wrapper layer regardless of the inner STARK’s parameters. The operator timeline is therefore driven by wrapper replacement. The outer wrapper migrates to a post-quantum scheme on the chain’s CNFL timeline under Mosca’s inequality, and Ch 40 derives the migration mechanics.
Starknet’s own documentation describes its L1 verification path. SHARP (SHARed Prover), StarkWare’s proof aggregator, verifies each proof it receives off-chain with a verifier program written in Cairo, aggregates those verifications recursively, and sends the last proof in the series to the Solidity verifier on Ethereum (StarkWare, 2025a). From Starknet version 0.14.0 Stwo generates every proof SHARP aggregates except the roots of its recursion trees, which Stone still proves so that SHARP’s on-chain verifiers did not have to change (StarkWare, 2025a). Chapter 35 records the prover switch of late 2025 (StarkWare, 2025b) and reads both parameter points. On that documented path no outer pairing-SNARK wrapper exists, and the proof the L1 contract reads is Stone’s proof of the recursion root. Stwo’s proofs terminate in the recursive Cairo verifier below it.
The path is documented as about to change: StarkWare wrote on 31 March 2026 that SHARP “will soon incorporate circuit-based recursive proving, and the L1 verifier (solidity) will be changed to verify a S-two circuit proof” (StarkWare, 2026). No public record that this change had shipped by 19 October 2026 was found, so the Stone-root design is the last publicly documented state of the path, not a claim about the contract deployed on any later day.
CNFL at L4 in Starknet’s STARKs is conditional on the same accounting and open rate question from Section 5.6 that apply to ZKsync’s inner STARK. For the Stone root it is also conditional on the extension to larger folds and to an interaction trace, and Boojum needs the first of those too. For the Stwo leaves it is also conditional on a QROM statement for circle FRI.
The operator timeline starts from that accounting, and Mosca’s inequality on the chain’s CNFL window bounds how long the operator can wait for it (Ch 40). Here the CNFL window is the exposure window Ch 36 defines from Mosca’s inequality, with X read as the verifier parameter-set reuse window, as in Ch 40. An applicable analysis of the composed deployment must determine whether the existing parameters meet the target and, if not, what changes suffice. It could certify the existing parameters, justify particular changes, or leave the assurance question unresolved, so its publication alone is not a favorable result. The illustrative challenge-width rule above supplies no certified deployment minimum. Parameter changes are candidates, and any resulting verifier upgrade ships through the upgrade authority of the contracts it touches, which Chapter 35 records for Starknet.
Stone’s 252-bit Cairo field gives a 67-bit cushion above the model’s 184-bit threshold, so the model shows no challenge-width shortfall at the root proof (subject to the toy-DFMS-versus-concrete-analysis caveat above). Stwo’s leaf proofs are a second parameter point on the same path, enforced by the recursive Cairo verifier rather than by the L1 contract, which Chapter 35 reads at Block 3. The verifier-upgrade cadence is the operator decision, and Ch 40 derives it.
Table 34.1. Operator-decision summary for CNFL on deployed STARK pipelines.
| Deployment | CNFL trigger | Operator action | Governance path | Timeline driver |
|---|---|---|---|---|
| ZKsync (Boojum) | Shor breaks outer pairing wrapper | Replace outer wrapper with PQ scheme | ZK Nation governance (Ch 35), Ch 40 mechanics | Mosca’s inequality on the chain’s CNFL window |
| Starknet (direct verifier) | An applicable QROM analysis at Starknet’s deployed parameters does not certify the target margin, or none is published in time under Mosca’s inequality on the chain’s CNFL window | If one arrives in time, act on what it determines. If none does, the upgrade decision is made with assurance unresolved. Parameter changes are candidates, not a certified remedy | Contract multisigs and Security Council (Ch 35), Ch 40 mechanics | An applicable QROM analysis of the composed deployment (unpublished, as Section 5.6 records), bounded by Mosca’s inequality on the chain’s CNFL window |
Parameter knobs and what they buy
Section titled “Parameter knobs and what they buy”Every operator choice in a FRI-based STARK deployment affects one or more terms of the composed bound in Section 5.5. Table 34.2 names the seven primary knobs with their effect on proof size, soundness, and prover time, along with an ethSTARK reference value (Ben-Sasson, 2021). The toy deliberately omits the composition polynomial present in production deployments. The toy’s tradeoff profile is a strict subset of the production profile.
Table 34.2. STARK parameter knobs and what they buy.
| Parameter | Operator knob | Proof size effect | Soundness effect | Prover time | ethSTARK reference |
|---|---|---|---|---|---|
Blowup factor 1/rho | Sets LDE size N = L / rho | At fixed mu: larger domains and Merkle paths. At fixed target soundness: may reduce required mu | Raises the Johnson-bound threshold (larger admissible delta_0), reducing per-query miss probability at fixed mu | Higher: more LDE evaluations | 4 to 8 |
FRI queries mu | Sets independent FRI query paths. Each path induces openings across fold layers | Linear in mu (per-path openings plus Merkle paths) | Reduces (1 - delta_0)^mu exponentially | Mild-to-moderate verifier and proof-size overhead. Prover overhead is dominated by opening generation | 31 / 41 / 55 conjectured at 80 / 100 / 128 bits (§5.10.1); 79 / 105 / 141 provable (§7.1.1) |
Folding rounds r_FRI | Derived from domain size, degree bound, and fri_step_list | Logarithmic | Union-bound term grows linearly in r_FRI | Logarithmic | derived from fri_step_list |
Grinding bits g | Per-proof PoW | Constant (one nonce) | Attenuates eps_query by 2^{-g} when applied at the final query round, as the toy does; does not affect eps_pre or eps_bind. Applied at an earlier round it attenuates that round’s term instead | Exponential in g: about 2^g hashes | 20 at the final query round (§5.10.1 and §7.1.1). The 128-bit provable setting adds 4 bits at each round from the third to the one before the queries (§7.1.1) |
| Merkle hash width | Sets collision threshold | Linear per path | Governs BHT and CNPS PQ bounds on eps_bind | Significant but parallelizable. Depends on arity and hash choice | BLAKE2s at a 160-bit digest in the 80-bit reference measurements (§3.5) |
| Challenge space size | Sets field width per round | Minor | Enters eps_pre as a per-round factor of one over the challenge-space size. The model’s DFMS20-shaped factor (2q+1)^{2 r_FS} multiplies the composed eps_total | Negligible | base F_p ~61-bit, F_{p^3} ~183-bit for FRI |
Trace length L | Computation-dependent | Linear in L | Adds ((L - 1) / N)^mu consistency term to eps_query | Dominant at large L | computation-bound |
The reference column is the document’s. The toy uses SHA-256 for its Merkle hash and its transcript throughout, a pedagogical choice. The tradeoff discussion in Ch 32 covered only L2: hash width and Merkle arity. This chapter adds the L1 and L4 knobs. The blowup factor and FRI query count control the proximity-gap and query-miss terms at L2. Grinding placed before the query draw, as the toy places it, attenuates only the query-miss part of the soundness budget (Section 5.5); challenge-space size enters the stipulated DFMS20-shaped composition. Both grinding and challenge-space sit at L4 and therefore carry CNFL exposure until an analysis at deployment parameters, which Section 5.6 records as unpublished, shows that the deployed values, or changed ones, meet the target.
Where Chapter 34 ends and Chapter 35 picks up
Section titled “Where Chapter 34 ends and Chapter 35 picks up”This chapter built one STARK end to end and priced it. It has four stages, a composed bound that partitions into a pre-query part, a query-miss part and a binding part, and seven knobs, each moving one or more of its terms (Table 34.2). Two results are worth carrying forward as they stand. Grinding placed before the query draw, as in the toy, attenuates only the query-miss term, so a pipeline that buys soundness with query-round grinding alone is buying it in one column of the budget. And the DFMS20-shaped factor at L4 is a stipulated model standing in for a FRI-specific QROM analysis. Section 5.6 records that no published work had carried one out at the deployment parameters of the production FRI pipelines this Part reads. That is why Table 34.1 ties Starknet’s row to an analysis rather than a fixed date, with Mosca’s inequality bounding the wait.
What the chapter did not do is read a deployed system. Its two deployment rows are an operator-decision summary. ZKsync’s dominant exposure sits at the outer pairing wrapper and is a Shor problem, and its inner STARK carries a pending QROM question of its own (Ch 35). Starknet’s sits in the QROM soundness of its STARKs at their deployed parameters. There an analysis Section 5.6 records as unpublished has to say whether any change is needed and which would suffice, and parameter changes are candidates rather than a settled remedy. That is the shape of the answer rather than the answer.
Chapter 35 takes the three systems apart. Zcash, which this chapter never mentions, returns as a full case study running Groth16 in Sapling and Halo 2 in Orchard, two different cryptographic routes to the same verdict. ZKsync Era is decomposed as the composite it is, amber inside and red outside. Starknet splits in two, because its prover moved from Stone to Stwo on mainnet in late 2025 (announced on 3 November 2025, with L2BEAT dating the switch to 19 October), and the Circle STARK arithmetization Stwo runs over Mersenne-31 is not the arithmetization built here. Each system is placed in the two-axis grid of Figure 35.1 and given a bit margin, then read against this chapter’s toy, starting with the composition polynomial the toy drops and every deployed pipeline keeps. Chapter 35 computes those margins under this chapter’s stipulated model, at configurations it flags as illustrative rather than as verified deployment parameters.
Exercises
Section titled “Exercises”E1. A STARK has LDE domain size N = 2^20, blowup factor 4, FRI folding rounds r_FRI = 18, hash output width 256 bits, and trace elements of 32 bytes each. Each FRI query path contributes one trace opening (32 bytes) plus one Merkle authentication path per FRI round. For the worked answer in Appendix D, take each per-round authentication path as a flat log_2 N = 20 hashes deep (a pedagogical upper bound: in production each round’s path is the current domain’s depth, dropping by one per round). Ignore Merkle roots themselves (a constant the verifier already holds), paired-opening sibling-deduplication, and final-layer constants. Write proof size in bytes as a function of mu, then state it in kilobytes at mu = 40.
E2. A STARK pipeline targets 128 bits of post-quantum soundness against a quantum adversary with query budget q = 2^80. The protocol has r_FS = 8 Fiat-Shamir rounds. Apply the chapter’s DFMS20-shaped model rule, computed without the 2 q_bits shortcut, c_bits >= 2 log_2(2q + 1) + k / r_FS. Compute the minimum integer c_bits. State whether a 256-bit field meets the model’s width and whether one field element per challenge does, and say what the model’s answer does and does not certify (Ch 33).
E3. Extend the Fibonacci AIR to include a secondary column c[i] with values in {0, 1}. The transition becomes trace[i+2] = trace[i+1] + trace[i] + c[i]. Write two transition constraints: one algebraic (the modified recurrence) and one Boolean (the constraint that c[i] is zero or one). State the boundary constraints on c. At trace length L = 16, take the composition polynomial as the constraint polynomial divided, constraint by constraint, by the vanishing polynomial of the rows it applies to: x^L - 1 for the Boolean constraint, which holds on every row, and (x^L - 1) / ((x - omega^{L-2})(x - omega^{L-1})) for the recurrence, which holds on the first L - 2 rows only. Treat each trace column as a univariate polynomial of degree < L interpolated over the order-L trace subgroup. State the resulting composition-polynomial degree, using the Boolean constraint as the worst-case constraint (its product structure dominates the algebraic recurrence’s degree).
E4. A production STARK is deployed with SHA-256 Merkle hashes, mu = 40 independent FRI query paths, 25 grinding bits, and per-round Fiat-Shamir challenges drawn from a 252-bit field. A future quantum adversary collects 10,000 transcripts today and queries a QROM oracle with budget q = 2^80 in 2040. State (i) which of the four STARK layers carries the chapter’s CNFL exposure and what that exposure consists of, (ii) the model’s DFMS20-shaped multiplicative loss for r_FS = 20 rounds. Then state (iii) whether the 252-bit challenge space is adequate at a 128-bit PQ target under the chapter’s DFMS-shaped per-round model rule, computed without the 2 q_bits shortcut (not under an end-to-end ethSTARK-style provable IOP analysis). Name (iv) the one citation in Chapter 34 that supplies the QROM Fiat-Shamir bound for FRI, and state what Section 5.6 records as missing for a number at deployment parameters. Finally, state (v) what the 10,000 collected transcripts contribute to any known attack on the L4 soundness.
E5 (optional extension). Section 4’s AIR container assumes a single trace column: evaluate_air iterates a flat trace, and a transition constraint carries no field naming which column its window reads. E3 already needs a second column, and interpolates it as its own univariate polynomial, so this is a question about how many columns a trace has and not about the number of variables in the polynomials. The scope is the container alone. Name the subsection of Section 4 that holds the AIR container and the inline code block that declares it, and give the record fields a multi-column version would need. Then state what the container change on its own does not buy: name the subsection whose prover and verifier wiring still commits a single codeword, and say what a multi-column trace needs there that a single-column one does not. Integration is out of scope here, and saying why is part of the answer.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 34. A separate track, for rebuilding rather than reading: the package exercises/ch34-starks has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch34 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: