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, derived the DFMS20 multi-round Fiat-Shamir bound, 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., 2018). 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 trace commit plus one per fold). The ethSTARK IOP has r_eth = 3 + s rounds, where s is the number of entries in fri_step_list, per Theorem 5 of (Ben-Sasson, 2021) (trace oracle, constraint randomness, DEEP query, plus one challenge per FRI commit-phase layer). 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 derives the count. |
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 codeword. |
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.
AIR is a compact algebraic description of a computation (Ben-Sasson et al., 2018, sec. 2.2). A trace is a function T : {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 codeword 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 close to some degree-less-than-L polynomial passes the FRI proximity test with high probability. A codeword far from every degree-less-than-L 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 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 codeword 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 codeword 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 codeword not close to any polynomial of degree less than the rate-implied bound produces a non-constant final codeword except with probability bounded in Section 5.1.
The operator decision is the tradeoff between queries per round, folding depth, and the grinding bits absorbed into the transcript 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 codeword on N / L = 4 points expected when the initial codeword is close to a polynomial of degree below L = 8. 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 codeword, because beta is bound to the committed codeword 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 favourable 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. Production STARK pipelines grind 20 to 30 bits; 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 randomisation 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’s soundness argument still goes through, because the verifier binds the sent trace to the committed codeword via a consistency check. For every FRI query path j, the codeword opening at the path’s top-layer LDE position must equal t(lde_domain[j]), where t(x) is the Lagrange interpolation of the sent trace.
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 imports the standalone package for the orchestration. Inline re-declaration of every primitive would expand the 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 codeword 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 behaviour 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 codeword. 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 trace-codeword commitment plus one challenge per fold.
The ethSTARK IOP has total round count r_eth = 3 + |fri_step_list| per Theorem 5 of (Ben-Sasson, 2021): three fixed protocol steps (trace oracle, constraint randomness, DEEP query) plus one challenge per FRI commit-phase layer. (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 conditional DFMS20 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 derives the DFMS20 factor at depth. The result is invoked here without rederivation.
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 codeword 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 in both the classical ROM and the QROM. 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 inherited unconditionally through the BCS state-restoration lift. The partition above extends that result with the grinding and Schwartz-Zippel terms. Those terms are not jointly covered at deployment parameters in the published literature. The FRI-specific bound is the one to size a quantum adversary against; the generic (2q + 1)^{2 r_FS} factor of Section 5.3 is the model, which exceeds it by powers of q and drops the corollary’s additive term. Neither is an end-to-end accounting at deployment parameters. See Section 5.6.
The operator decision is which stage to tighten first to absorb the DFMS20 loss while staying within a proof-size budget.
5.6 Deployment-parameter QROM accounting
Section titled “5.6 Deployment-parameter QROM accounting”Asymptotic QROM Fiat-Shamir security for FRI and batched FRI is settled. Block et al. 2023 proves it through the BCS state-restoration lift, and the paper states outright that FRI run non-interactively via Fiat-Shamir is unconditionally secure in the quantum random oracle model (Block et al., 2023). What is not in the literature as of 2026 is an end-to-end QROM accounting at the concrete deployment parameters of any production FRI pipeline: ethSTARK, Plonky2, Starknet. Such an accounting would compose that bound 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 grinding counted and batching, larger folds and recursion left out, and report provable security 21 to 63 bits below conjectured in all but one of the surveyed deployed parameter sets (Block & Tiwari, 2024, sec. 3.3). Two further gaps are specific to this chapter’s cases. Block et al. prove the FRI, batched-FRI and Plonky2-like results formally but only sketch 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). And Stwo’s circle-STARK construction post-dates the paper. An operator reading this section in 2026 therefore inherits a concrete-accounting caveat rather than a missing theorem. Every concrete FRI-based STARK soundness number against a quantum adversary is conditional on that pending composition, not on some future QROM proof for FRI itself.
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 for FRI itself, are upper bounds on forgery probability, and what is missing is their instantiation at deployment parameters. 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. Harvested transcripts contribute nothing to any known attack on FRI soundness. 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 known attack on Fiat-Shamir FRI uses collected transcripts. It is an assurance gap: the QROM bound at the deployed challenge width has not been instantiated, and a legacy verifier keeps accepting proofs until it is replaced.
The exposure at L4 is sized here with the DFMS20-shaped model Section 5.3 introduced. Under that model the per-round parameter-bump rule Ch 33 derived applies: c_bits >= 2 log_2(2q + 1) + k / r_FS. Take a production 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 document recommends e = 4 (extension field of about 244 bits, with 140 FRI query paths and 20 grinding bits) for 128-bit provable knowledge soundness. 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. No deployment-parameter composition of that lighter bound has been published to supersede it, so the 184-bit figure and the per-deployment cushions both read as model outputs, and the concrete CNFL exposure for production FRI-based STARKs is still pending.
Two deployment paths absorb the CNFL bound at L4. The first path replaces the outer-layer cryptography that wraps the STARK; the second adjusts STARK parameters in place via on-chain governance. 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. 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, 2025). 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, 2025). 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). On 7 September 2026 no public record that this change had shipped 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 STARK is conditional on the same deployment-parameter QROM accounting that applies to ZKsync’s inner STARK from Section 5.6. The operator timeline is parameter-bump-driven: when that accounting is published and fixes a concrete challenge-width requirement, the c_bits rule from this section determines the new minimum challenge-space size, and the operator activates the parameter change through on-chain governance.
Stone’s 252-bit Cairo field gives a 67-bit cushion above the model’s 184-bit threshold, so a parameter bump at the root proof alone may not be the binding constraint within the chain’s wider migration plan (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 5. The governance-trigger cadence is the operator decision. Ch 40 derives the cadence.
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 | Matter Labs upgrade pipeline, Ch 40 mechanics | Mosca’s inequality on the chain’s CNFL window |
| Starknet (direct verifier) | Concrete QROM accounting at Starknet’s parameters fails to certify the target margin | Bump per-round challenge-space parameters | On-chain governance vote, Ch 40 mechanics | Deployment-parameter QROM accounting (pending) |
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 term at L2. Grinding attenuates the query-miss part of the soundness budget only (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 the deployment-parameter QROM accounting of Section 5.6 is published.
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: four stages, a composed bound that partitions into a pre-query part, a query-miss part and a binding part, and seven knobs that each move one term. Two results are worth carrying forward as they stand. Grinding attenuates only the query-miss term, so a pipeline that buys soundness with grinding bits 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 bound nobody has yet composed at deployment parameters, which is why Table 34.1 gives Starknet a governance trigger rather than a date.
What the chapter did not do is read a deployed system. Its two deployment rows are an operator-decision summary: ZKsync’s exposure sits at the outer pairing wrapper and is a Shor problem, Starknet’s sits at the inner STARK’s challenge width and is a parameter bump. 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 ethSTARK / 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 n = 16, take the composition polynomial as the constraint polynomial divided, constraint by constraint, by the vanishing polynomial of the rows it applies to: x^n - 1 for the Boolean constraint, which holds on every row, and (x^n - 1) / ((x - g^{n-2})(x - g^{n-1})) for the recurrence, which holds on the first n - 2 rows only. Treat each trace column as a univariate polynomial of degree < n interpolated over the order-n 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 DFMS20 multiplicative reduction 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 is still missing before that bound yields 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: