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: the public commitment key already carries enough for a future quantum adversary. Shor’s algorithm on secp256k1’s discrete log recovers the discrete-log relations among the IPA commitment-key generators, and with them the adversary can open a commitment to a value it never committed to. A legacy verifier then accepts 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 non-group-based commitment. That is the necessary first task, because the L2 break alone completes the CNFL attack. It does not by itself establish PQ parity at 128 bits: the two replacements below, Merkle-FRI and lattice PCS, both land in the amber column of Figure 35.1. Amber does not mean safe, as Exercise 4 shows for its two hash-based candidates. Nor does the replacement 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 query-miss term $\mu \log_2(1 - \delta_0)$ (per_round in the code), 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.

Priced one at a time from the original illustrative configuration’s $99.9$ bits, the two changes pull in opposite directions. The larger trace alone, at $\mu = 40$, gives $99.6$ bits, 0.3 bits less. The extra queries alone, at the original trace, give $104.0$ bits, 4.1 bits more. Together they give the $101.8$ above, 1.9 bits more than the original.

Why they pull apart 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$ moves the ground query term from $-100.0$ to $-116.0$. Grinding does not touch the bad-beta term, so that term is a floor no number of queries passes. At the original trace the floor sits at $-104.0$; the sixteen bits of queries buy only the $4.1$ between the margin and the floor.

The larger trace raises the floor through $N$ and $r_{\text{FRI}}$: $\log_2(r_{\text{FRI}}(N + 1))$ goes from $24.0$ to $26.2$, so the floor rises to $-101.8$. That costs $0.3$ bits even at $\mu = 40$, and it caps the two changes together at $1.9$. The query terms barely move, because blowup 16 holds the rate at $1/16$. 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.

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)
trace_only = composed(128, 2 ** 18, 2 ** 22, 40, 18, 20)
queries_only = composed(128, 2 ** 16, 2 ** 20, 48, 16, 20)
print(larger)
print(original[0], round(larger[0] - original[0], 1))
print(trace_only[:2], round(trace_only[0] - original[0], 1))
print(queries_only[:2], round(queries_only[0] - original[0], 1))
# ==> (101.8, -101.8, -96.0, -192.0)
# ==> 99.9 1.9
# ==> (99.6, -101.8) -0.3
# ==> (104.0, -104.0) 4.1

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 falls short of the DFMS20-shaped rule’s threshold, which is no verdict on the 80-bit claim either way.

Passing the rule takes $c_{\text{bits}} = 176$ bits per round, which would mean a larger field or several field elements per challenge.

What the number establishes is narrower than “the claim does not hold”. The rule is a stipulated model of a generic reduction loss (Ch 33), 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 chapter’s model does not cover the claim at 96 bits. Only an applicable analysis of the composed protocol could settle it, and that analysis could certify the claim, justify particular changes, or leave the question open.

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 amortize 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 in the (amber, amber) cell of Figure 35.1, where the wrapper they replace sits in (red, red). L2 is amber rather than red, since neither binds through a group whose discrete log Shor solves, and L4 is amber because each uses Fiat-Shamir over a hash transcript. The choice between the two candidates is therefore a gas-cost optimization and not a change of posture. Amber does not mean 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 4, 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.