Appendix D: Solutions for Chapter 35

This page collects solutions and editorial notes for the exercises in Chapter 35: Case studies: Zcash, ZKsync, Starknet. 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 zk_case_studies package under solutions/ch35-case-studies. From a clone of the companion repository, pytest tests/ch35 runs its suite. Appendix C has the setup.

Exercise 1

Grid placement: the L2 column is IPA over a discrete-log group and the L4 row is Fiat-Shamir over that same group, so the cell is (red, red) and the dominant posture is red. Note the axes: Figure 35.1 runs L2 across the columns and L4 down the rows.

CNFL route: today’s transcripts already carry enough for a future quantum adversary. Shor’s algorithm on secp256k1’s discrete log recovers the IPA opening trapdoor. The trapdoor forges an opening for any past commitment. Substituting that opening for the original makes a legacy verifier accept a statement never proved. The L2 break is the structural fault. L4’s QROM-tightness gap is a separate quantitative concern but the L2 break alone is sufficient for the CNFL attack.

Minimum-cost migration step: replace L2 with a quantum-safe commitment. That is the necessary first task, because the L2 break alone completes the CNFL attack. What it does not do is leave L4 untouched. A Merkle-FRI opening protocol replaces IPA’s group-element messages and scalar challenges with a commitment root, a sequence of folding messages, and query openings, so the object Fiat-Shamir hashes is a different transcript. The compilation method carries over and the concrete transcript does not, which means the replacement needs its own protocol-specific soundness and QROM instantiation (Ch 33) rather than inheriting IPA’s. On cost, the verifier work moves from group operations to hash evaluations, which lets an on-chain verifier (if any) reuse existing SHA-256 precompiles. A lattice PCS replacement (the 2024-2026 line in Ch 32) gives smaller proofs at the cost of additional verifier ring arithmetic. Which of the two is cheapest is not settled by this exercise’s inputs: it turns on the polynomial degree, the proof shape, the verifier’s cost model, and whether on-chain gas or off-chain bandwidth is the binding constraint.

Exercise 2

Run the chapter’s own function rather than a separate estimate: the three terms are logarithms of probabilities that get summed and then negated, so they do not add as bits, and grinding does not enter all three alike.

The three terms of the Ch 34 Section 5.5 formula are the bad-beta union bound $\log_2(r_{\text{FRI}}(N+1)) - \text{field bits}$, the FRI per-round proximity term $\mu \log_2(1 - \delta_0)$, and the query-consistency term $\mu \log_2((L-1)/N)$. At the stated configuration they are $-101.8$, $-96.0$ and $-192.0$. Grinding attenuates only the last two, so the quantities that actually compete in the sum are $-101.8$, $-96.0 - 20 = -116.0$ and $-192.0 - 20 = -212.0$. The bad-beta union bound dominates, and the model’s composed figure is $101.8$ bits.

The original illustrative configuration gives $99.9$ bits, so the answer to the comparison is 1.9 bits.

Where those $1.9$ bits went is the point of the exercise. At blowup 16 the Johnson radius is $\delta_0 = 1 - \sqrt{1/16} = 0.75$, so each query path is worth exactly two bits, and $\mu = 40 \to 48$ raises the ground query term from $-100.0$ to $-116.0$. That is sixteen bits, and almost none of it reaches the margin, because the bad-beta term sits at $-101.8$ and grinding does not touch it. The original configuration was already within four bits of its own floor at $-104.0$; the larger one starts fourteen bits below its floor and buys nothing. This is Ch 34’s closing point in numbers: the bad-beta term is the one $\mu$ cannot tighten, and past the crossover only a wider field, a smaller evaluation domain, or a more conservative regime moves the margin. The larger trace does not help either, since $L$ enters only the two terms grinding has already buried.

import math


def composed(field_bits, L, N, mu, r_FRI, grinding):
    rho = L / N
    delta_0 = 1.0 - math.sqrt(rho)                       # Johnson radius
    bad_beta = math.log2(r_FRI * (N + 1)) - field_bits
    per_round = mu * math.log2(1.0 - delta_0)
    consistency = mu * math.log2((L - 1) / N)
    # Grinding attenuates the query terms only (Ch 34 Section 5.5).
    total = -math.log2(2.0 ** bad_beta
                       + 2.0 ** -grinding * (2.0 ** per_round
                                             + 2.0 ** consistency))
    return round(total, 1), round(bad_beta, 1), per_round, round(consistency, 1)


larger = composed(128, 2 ** 18, 2 ** 22, 48, 18, 20)
original = composed(128, 2 ** 16, 2 ** 20, 40, 16, 20)
print(larger)
print(original[0], round(larger[0] - original[0], 1))
# ==> (101.8, -101.8, -96.0, -192.0)
# ==> 99.9 1.9

Exercise 3

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}}$. At $q = 2^{80}, k = 80, r_{\text{FS}} = 6$: $2 \log_2(2^{81} + 1)$ is just above $162$ and $80 / 6 = 13.33$, so the minimum is just above $175.33$, which rounds up to $176$ bits. The approximation $2 q_{\text{bits}} + \lceil k / r_{\text{FS}} \rceil$ gives 174, two bits short.

The system publishes $c_{\text{bits}} = 96$, well below 176, so the parameter point fails the DFMS20 rule: the generic bound does not certify the 80-bit claim.

To pass the rule: minimum $c_{\text{bits}} = 176$ bits per round. The system needs to grow the per-round challenge space from 96 to 176 bits, which means using a larger field or multiple field elements per challenge.

What the number establishes is narrower than “the claim does not hold”. The rule is a generic reduction loss, not an analysis of this system’s protocol. Failing it exhibits no forgery, and passing it at 176 bits would not have established the claim either. The chapter’s CNFL routing paragraph for Starknet says the same of the model at a deployed parameter point. The calculation says that the generic bound does not cover the claim at 96 bits, and that a published analysis of the composed protocol is what would.

import math
q_bits, k, r = 80, 80, 6
exact = 2 * math.log2(2 * 2 ** q_bits + 1) + k / r
print(math.ceil(exact) + (1 if math.ceil(exact) == exact else 0))
# ==> 176

Exercise 4

Recursive STARK folding: L2 = Merkle-FRI, L4 = Fiat-Shamir over the FRI transcript. The on-chain verifier evaluates a series of FRI rounds plus Merkle paths. Per-proof gas cost on Ethereum mainnet is dominated by the hash evaluations and Merkle-path opens, typically in the millions-of-gas range for a verifier serving a high-throughput rollup. Folding lets multiple proofs share verifier work, amortizing the per-proof cost.

Transparent recursive SNARK (Fractal): L2 = Merkle-FRI (Fractal uses FRI internally for the recursion), L4 = Fiat-Shamir. The verifier is a single SNARK that batches the recursive proofs. Gas cost is closer to a fixed verifier overhead plus per-aggregated-proof marginal cost. Fractal’s verifier is structurally similar to a STARK verifier, so the gas profile resembles STARK folding’s but with different constants.

Operator-facing tradeoff: both amortise a roughly fixed, hash-dominated verifier cost over a batch, so per-proof gas falls with batch size in either. The constants differ by implementation, and no published rollup-scale benchmark compares the two, so the gas-cost choice is measured on the operator’s own workload rather than read off the constructions. Both candidates sit at amber L2 rather than red, since neither binds through a group whose discrete log Shor solves, so the choice between them is a gas-cost optimization rather than a change of posture. Amber is not safe: both inherit the hash-width question and the QROM-pending caveat.

Exercise 5

Editorial note. The exercise has no canonical answer because the system is the reader’s choice. A strong response cites a primary source for each claim, meaning a whitepaper section, a codebase commit, or a specification document rather than a blog post. It uses the same (L2, L4) cell-naming convention as Block 6, and it identifies the CNFL route specific to that system. Three pitfalls recur. Confusing the rollup’s outer wrapper with its inner proof system, as when Polygon zkEVM uses different L2 choices in different layers. Citing a blog summary rather than the technical specification. Missing a recursive cell, where one L2 sits at the inner layer and a different L2 at the outer wrapper. The case-study procedure in this chapter is to place each layer of the system separately in the grid and report the dominant cell for the on-chain verifier. That placement defines the operator-facing security posture.