Appendix D: Solutions for Chapter 31

This page collects solutions and editorial notes for the exercises in Chapter 31: The four-layer decomposition. 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_layers package under solutions/ch31-zk-layers. From a clone of the companion repository, pytest tests/ch31 runs its suite. Appendix C has the setup.

Exercise 1

Halo 2: L2 = IPA over a discrete-log-hard group (typically Pasta curves), L4 = Fiat-Shamir accumulation. The IPA commitment’s binding rests on discrete-log hardness, so it falls to Shor. The Fiat-Shamir accumulation has classical-rewinding soundness arguments that need re-establishment in the QROM.

Audit L2 first: it is the structural break. The IPA-DL assumption is what Shor breaks directly, and a successful Shor attack on the curve order recovers commitment-opening trapdoors that compromise binding. L4 audits matter (the QROM gap from Ch 33), but they are quantitative rather than structural; L2 is the qualitative break. Migration: replace the IPA over an elliptic curve with a Merkle-FRI commitment (STARK family) or a lattice-based polynomial commitment scheme (PCS, the 2024-2026 line in Ch 32).

Exercise 2

32 multiplication constraints for one 32-bit XOR when the inputs are already represented as boolean-constrained wires.

R1CS works with multiplicative gates in $\mathbb{F}_p$ (for $p$ a large prime). XOR is bitwise, not multiplicative, so each bit of the 32-bit XOR needs decomposition. For two bit variables $a, b$ with $a, b \in \{0, 1\}$, the standard encoding is $a \oplus b = a + b - 2 a b$, which costs one multiplication constraint $a \cdot b = ab$ per output bit. Across 32 bits that is 32 multiplication constraints.

# Exercise 2: R1CS cost of one 32-bit XOR, by the standard per-bit encoding.
WIDTH = 32

# a XOR b = a + b - 2ab. The product ab is the only multiplication; the
# additions and the doubling are linear and cost nothing.
xor_only = 1 * WIDTH

# Booleanity, a(1 - a) = 0, is one constraint per input bit, charged once
# when a value first enters the circuit as bits. Two 32-bit operands here.
with_booleanity = xor_only + 2 * WIDTH

print(f"inputs already boolean-constrained: {xor_only}")
print(f"counting booleanity on both operands: {with_booleanity}")
# ==> inputs already boolean-constrained: 32
# ==> counting booleanity on both operands: 96

The booleanity constraints $a (1 - a) = 0$ and $b (1 - b) = 0$ are not counted again: the exercise assumes the inputs are already bit-constrained. In a real SHA-256 circuit each input bit is constrained once when it first appears and then reused across every XOR, AND, ROT, and SHR the bit participates in. In arithmetization frameworks like Circom or Halo 2’s PLONKish columns, that amortization is automatic.

Exercise 3

Placing arithmetization at L1 makes it the constraint-system layer that L3 (the IOP) consumes. The IOP is an oracle interaction over an algebraic structure, and the constraint system is what gets compiled into that algebraic structure. Treating arithmetization as part of L3 would conflate the question “what does the prover commit to and the verifier query?” with the question “how does a high-level computation become a constraint system?”

The two questions have different design surfaces: arithmetization choices (R1CS vs PLONKish vs AIR) interact with the prover’s witness encoding and the verifier’s query strategy independently of whether the IOP is sumcheck, FRI, or polynomial-IOP. Nesting arithmetization inside L3 would mean every IOP framework re-derives the same arithmetization tradeoffs, which is precisely the redundancy that the four-layer decomposition exists to avoid.

Exercise 4

• Groth16: L2 (pairing-based commitment with structured-reference-string trapdoor). Shor breaks discrete log on the underlying curve, recovering the trapdoor and trivially forging proofs. No deployment parameter rescues this. The entire scheme is structurally broken.
• PLONK with KZG: L2 (KZG commitment over a pairing-friendly curve, same Shor break as Groth16’s L2). Migration replaces L2 with a quantum-safe commitment.
• STARKs with Merkle+FRI: no layer is structurally broken here, which is why the question changes shape. The layer whose security is set by generic quantum collision search rather than by a hardness assumption is L2, the collision resistance of the Merkle hash. Deployment must use a hash with $3n$-bit output to maintain $n$-bit post-quantum collision security under BHT, since BHT gives a $2^{n/3}$-query collision attack in the quantum-accessible-memory model. For 128-bit PQ collision security the hash output width must therefore be at least 384 bits (so SHA-384 or SHA3-384). The bound on a 256-bit hash is only $2^{85}$, which falls short. That is a necessary condition on the Merkle binding budget, and it is not a claim that L2 carries the thinnest margin of a deployed STARK. Ranking the four margins would need a stated deployment, its FRI query count and per-query error, its Fiat-Shamir quantum query budget, and a bound composed across all four layers, none of which this exercise supplies. Chapters 33 to 35 develop that accounting, and Chapter 34 §5.6 records what is still missing before it yields a number at deployment parameters.
• Bulletproofs: L2 (IPA on a discrete-log-hard group). Same break as Halo 2.

# Exercise 4: sizing a Merkle hash for 128-bit post-quantum collision
# security under the Brassard-Hoyer-Tapp query-model bound.
TARGET = 128


def bht_bits(n):
    """Collision-resistance bits an n-bit hash delivers under BHT."""
    return n // 3


# BHT costs about 2^(n/3) queries on an n-bit hash, so reaching a target
# of t bits needs an output width of at least 3t. The classical birthday
# relation would say 2t; that is the wrong bound to size against here.
required = 3 * TARGET

print(f"SHA-256 delivers {bht_bits(256)} bits, short of {TARGET}")
print(f"minimum output width for {TARGET} bits: {required}")
print(f"a {required}-bit hash delivers {bht_bits(required)} bits")
# ==> SHA-256 delivers 85 bits, short of 128
# ==> minimum output width for 128 bits: 384
# ==> a 384-bit hash delivers 128 bits

The pattern: L2 is the load-bearing quantum-safety axis across every modern SNARK family.