Appendix D: Solutions for Chapter 34

This page collects solutions and editorial notes for the exercises in Chapter 34: STARKs and FRI revisited. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the starks package under solutions/ch34-starks. From a clone of the companion repository, pytest tests/ch34 runs its suite. Appendix C has the setup.

Exercise 1

Use the pedagogical flat-depth model stipulated in the exercise. Per FRI query path, the cost is 1 trace opening (32 bytes) + 1 Merkle authentication path per FRI round. Each per-round authentication path is $20 \cdot 32 = 640$ bytes: the path is $\log_2 N = 20$ levels deep at $N = 2^{20}$, and each level contributes one 256-bit sibling hash, which is 32 bytes. Total per path is $32 + 18 \cdot 640 = 32 + 11{,}520 = 11{,}552$ bytes.

Proof size $S(\mu) = \mu \cdot 11{,}552$ bytes. At $\mu = 40$: $S = 40 \cdot 11{,}552 = 462{,}080$ bytes $\approx 451$ KB. Production STARKs do better than this estimate by shrinking the per-round path to the round’s actual domain depth (top-layer 20, then 19, 18, …), deduplicating sibling openings, and not including Merkle roots in the per-query cost.

N_bits = 20
hash_bytes = 32
trace_bytes = 32
r_fri = 18
path_bytes = N_bits * hash_bytes
per_query = trace_bytes + r_fri * path_bytes
mu = 40
print("path bytes:", path_bytes, "paths total:", r_fri * path_bytes)
print(per_query, mu * per_query, round(mu * per_query / 1024))
# ==> path bytes: 640 paths total: 11520
# ==> 11552 462080 451

Exercise 2

The chapter’s DFMS20-shaped model rule, computed without the $2 q_{\text{bits}}$ shortcut: $c_{\text{bits}} \ge 2 \log_2(2q + 1) + k / r_{\text{FS}}$. With $q = 2^{80}$, $k = 128$, $r_{\text{FS}} = 8$:

$c_{\text{bits}} \ge 2 \log_2(2^{81} + 1) + 128 / 8$, and $2 \log_2(2^{81} + 1)$ is just above $162$, so the bound sits just above $178.0$ and rounds up to $179$ bits per round. The approximation $2 q_{\text{bits}} + \lceil k / r_{\text{FS}} \rceil = 176$ lands three bits short here, because the boundary falls on an integer.

A 256-bit field comfortably supplies 179 bits per challenge, so one field element per challenge is enough under the model. What the 179 bits do not establish is a deployment’s quantum soundness: the model drops the corollary’s additive challenge-space term and assumes an interactive error the protocol has to supply for itself (Ch 33).

Note where the width actually comes from in a FRI-based pipeline, because the obvious 256-bit candidates are the wrong ones. Chapter 34 Section 5.7 sets out the real pattern: a small base field plus an extension. ethSTARK’s reference configuration is a base field of about 61 bits with $\mathbb{F}_{p^3}$ at about 183 bits, and Starknet’s Stone prover runs FRI over the 252-bit Cairo field directly. The 254-bit BN254 and 255-bit BLS12-381 scalar fields are pairing-curve scalar fields. In this stack they belong to an outer SNARK wrapper, not to the STARK.

import math
q_bits, k, r_fs = 80, 128, 8
exact = 2 * math.log2(2 * 2 ** q_bits + 1) + k / r_fs
c_bits = math.ceil(exact) + (1 if math.ceil(exact) == exact else 0)
print(round(2 * math.log2(2 * 2 ** q_bits + 1), 1), k / r_fs, c_bits)
# ==> 162.0 16.0 179

Exercise 3

Transition constraints (interpreted as polynomials over the trace domain):

• Algebraic: $T_1(x) := \mathrm{trace}(g^2 x) - \mathrm{trace}(g x) - \mathrm{trace}(x) - c(x) = 0$.
• Boolean: $T_2(x) := c(x) (c(x) - 1) = 0$, where $c(x)$ is the polynomial interpolating column $c$ over the trace domain.

Boundary constraints on $c$ are protocol-specific. If the application requires the secondary column to start at zero and end at zero (e.g. a free-input column with bracketing), the boundary constraints are $c(g^0) = 0$ and $c(g^{n-1}) = 0$. If the column is unconstrained at boundaries, no boundary constraints apply.

Composition-polynomial degree at trace length $n = 16$: the trace polynomial has degree $\le n - 1 = 15$, so $\mathrm{trace}(x)$ is degree 15 and $c(x)$ is degree 15. $T_1$ is a linear combination of trace polynomials evaluated at $x, g x, g^2 x$, all degree 15. $T_2$ is degree $2 \cdot 15 = 30$ (the bottleneck). The recurrence $T_1$ holds on rows $0$ to $n - 3$ only, so its divisor is the vanishing polynomial of those $n - 2$ rows, $(x^n - 1) / ((x - g^{n-2})(x - g^{n-1}))$ of degree $14$, and its quotient has degree $15 - 14 = 1$. Dividing $T_1$ by the full $x^n - 1$ would require the recurrence to wrap around from rows $n - 2$ and $n - 1$ back to rows $0$ and $1$, which the exercise does not impose and a Fibonacci trace does not satisfy. The Boolean constraint $T_2$ holds on every row, so its divisor is $\prod_i (x - g^i) = x^n - 1$ of degree $16$ and its quotient has degree $30 - 16 = 14$. The composition polynomial’s degree is the maximum, $14$, set by the Boolean constraint.

n = 16
deg_trace = n - 1              # each column interpolates to degree < n
deg_t1 = deg_trace             # linear in trace(x), trace(gx), trace(g^2 x), c(x)
deg_t2 = 2 * deg_trace         # Boolean constraint c(x)(c(x) - 1): the bottleneck
deg_vanishing = n              # x^n - 1: the divisor for T2, which holds on every row
print(deg_t1, deg_t2, max(deg_t1, deg_t2) - deg_vanishing)
# ==> 15 30 14

Exercise 4

(i) CNFL exposure: L4 (Fiat-Shamir transform) carries the chapter’s CNFL exposure under its narrow model, and the exposure is an assurance gap rather than an attack mechanism. The published QROM results for FRI-based Fiat-Shamir (DFMS20 generically, Block et al. 2023 for FRI) are upper bounds on forgery probability that have not been instantiated at deployment parameters, so a legacy verifier still in service in 2040 accepts proofs whose post-quantum soundness has not been established at its parameters. No published attack on Fiat-Shamir FRI exists. L2 (Merkle binding) is a related but distinct future-verifier / hash-lifetime concern. A quantum collision-search attack on SHA-256 (BHT / CNPS budgets) does not depend on which transcripts were harvested. It does affect any verifier still trusting SHA-256 Merkle roots at the CNFL crossover.

(ii) DFMS20 multiplicative loss for $r_{\text{FS}} = 20$: $2q + 1 = 2^{81} + 1 \approx 2^{81}$, so $(2q + 1)^{2 r} \approx (2^{81})^{2 \cdot 20} = 2^{3240}$. Combined with the per-round interactive soundness $\varepsilon^{r}$, the chapter’s model carries this multiplicative factor. It is the model’s figure and not DFMS20’s corollary, which adds a challenge-space term the model drops (Ch 33).

(iii) 252-bit adequacy at 128-bit PQ under the simplified DFMS rule: Apply the per-round rule from E2 with $r_{\text{FS}} = 20$. Then $c_{\text{bits}} \ge 2 \log_2(2^{81} + 1) + 128 / 20$, just above $162 + 6.4 = 168.4$, so $169$ bits per round. The rule sizes challenge entropy, and the 252-bit Cairo prime supplies $\log_2 P = 251.0$ bits of it, 82 bits above 169, so the challenge space is adequate at the per-round granularity under the chapter’s DFMS-shaped per-round model rule. This is not an end-to-end STARK security proof. The 25 grinding bits attenuate only the query-miss term (Section 5.5 of Chapter 34). The proximity-gap and bad-beta terms follow the BCIKS regime-dependent error from Section 5.1. A concrete deployment-parameter analysis (e.g. ethSTARK Documentation §5.10.2 for provable IOP knowledge soundness) is the load-bearing argument, not the per-round $c_{\text{bits}}$ inequality alone.

(iv) The citation that supplies the QROM bound: (Block et al., 2023). Block et al. 2023 is the dedicated Fiat-Shamir analysis for FRI, and its QROM half is inherited through the BCS state-restoration lift, so the quantum bound for FRI is published rather than pending. What is missing is the composition: no published work carries that bound through Merkle binding, hash-output width, grinding, batching, and recursion at any production pipeline’s parameters. (Don et al., 2020) is the reference whose arithmetic parts (i) to (iii) use. Ch 34 Section 5.3 labels its DFMS20-shaped rule a stipulated model rather than the gating result: applying DFMS20 directly exceeds the published QROM loss by additional powers of $q$, and the model also drops the corollary’s additive challenge-space term.

(v) What the transcripts contribute: nothing, for L4 soundness. Neither DFM20’s bound nor Block et al.’s depends on how many honest transcripts the adversary holds, and no published attack on Fiat-Shamir FRI consumes them. The 10,000 transcripts play no part in any answer above; CNFL, as Chapter 34 frames it, is a verifier-lifetime problem.

import math
q_bits, k, r_fs = 80, 128, 20
loss_exponent = (q_bits + 1) * 2 * r_fs     # (2q+1)^{2r} with 2q+1 ~ 2^81
exact = 2 * math.log2(2 * 2 ** q_bits + 1) + k / r_fs
c_bits = math.ceil(exact) + (1 if math.ceil(exact) == exact else 0)
log2_p = math.log2(2 ** 251 + 17 * 2 ** 192 + 1)   # challenge entropy, not storage width
print("loss exponent:", loss_exponent, "c_bits:", c_bits, "headroom:", math.floor(log2_p) - c_bits)
# ==> loss exponent: 3240 c_bits: 169 headroom: 82

Exercise 5 (optional extension)

The container: subsection 4.1, arithmetization, and Block 2 inside it. A multi-column trace stops being a list of field elements and becomes a list of columns, so a transition constraint has to name which columns its window spans, and the AIR container has to carry that. Block 2 declares TransitionConstraint as ("window", "evaluator", "name") and BoundaryConstraint as ("row", "expected", "name"), and evaluate_air iterates a flat trace. A multi-column version adds a column selector to both records, for example TransitionConstraint("window", "columns", "evaluator", "name") and a column field on BoundaryConstraint, and evaluate_air indexes trace[col][row] rather than trace[row]. That much is a change of container rather than of mathematics: the AIR is still a set of polynomial constraints that must vanish on the trace domain.

What the container change does not buy. Subsection 4.5 is where the extension stops being free, and an answer that stops at 4.1 has answered half the question. The toy prover sends one flat trace, and the verifier binds it to one committed codeword: for every query path the codeword opening at that path’s top-layer position must equal $t(\texttt{lde\_domain}[j])$, where $t$ is the interpolation of the sent trace. One trace, one interpolation, one binding. Several columns have to be bound too, and this chapter has no machinery for it. So extending the container leaves three things unbuilt. The commitment has to bind every column, whether as one Merkle tree whose leaves carry a whole row or as a tree per column; a single root over rows binds several columns perfectly well, so the choice is a layout question and the requirement is that each column is opened at each query position. The prover and verifier wiring in 4.5 has to produce and check those openings. And the soundness accounting has to be redone, because the toy’s $((L - 1) / N)^{\mu}$ consistency bound covers one binding, and several bindings carry error terms of their own. A strong answer says this rather than asserting an unchanged budget.

The composition polynomial is a separate mechanism, and worth ruling out by name. Subsection 4.5 says outright that this chapter drops it, and a tempting wrong answer is that the dropped step is what would have collapsed the columns. It is not. The composition polynomial is a random linear combination of the constraint quotients, so what it aggregates is constraints, and a production pipeline commits the trace whatever its column count. The step that collapses several committed polynomials into the single codeword FRI runs on is a later random combination of their out-of-domain quotients, taken after both the trace and the composition polynomial have been committed: the DEEP consistency 4.5 names alongside it. Dropping the composition polynomial is why this chapter’s verifier checks the constraints against a sent trace rather than against a committed quotient. It is not what makes the container single-column.

Subsection 4.2 is the near-miss and worth ruling out explicitly. Multi-column traces do change what 4.2 does: each column interpolates to its own polynomial and gets its own low-degree extension, so the work multiplies by the column count. But interpolate_trace and extend_polynomial operate on one column at a time either way, and neither signature changes. Multiplying a call is not extending a type. Subsections 4.3 and 4.4 are the ones genuinely blind to the column count: FRI folds a codeword and the transcript absorbs roots, neither of which knows how the codeword was built.

One distinction the exercise turns on. How many columns a trace has is not how many variables its polynomials have. E3’s second column is interpolated as its own univariate polynomial of degree less than $n$, exactly as the single Fibonacci column is, and a proof system that commits multilinear polynomials over a Boolean hypercube has changed the representation rather than the column count. Nothing in this chapter’s pipeline changes representation.

References

Block, A. R., Garreta, A., Katz, J., Thaler, J., Tiwari, P. R., & Zajac, M. (2023). Fiat-Shamir Security of FRI and Related SNARKs. IACR ePrint 2023/1071. https://eprint.iacr.org/2023/1071

Don, J., Fehr, S., & Majenz, C. (2020). The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More. Advances in Cryptology — CRYPTO 2020. https://doi.org/10.1007/978-3-030-56877-1_21