Chapter 31: The four-layer decomposition

A deployed zk-SNARK, a zero-knowledge succinct non-interactive argument of knowledge, is not one cryptographic object. It is a stack with distinct algebraic layers, and each layer can be attacked on its own terms. Saying a system uses elliptic curves, or that it uses STARKs (scalable transparent arguments of knowledge), does not determine whether a quantum adversary collapses it, degrades it, or leaves it alone. Part VI uses a four-layer decomposition to sort out which is which. This chapter introduces the decomposition and states the per-layer quantum-safety posture at survey depth. The deeper analysis is deferred: Ch 32 covers commitment schemes, Ch 33 covers Fiat-Shamir in the quantum random oracle model, Ch 34 covers STARKs from scratch, and Ch 35 covers the Zcash, ZKsync, and Starknet case studies.

Zcash Sapling at quantum landfall

Zcash Sapling uses Groth16 proofs over the pairing-friendly curve BLS12-381 to prove that a shielded transaction is valid without revealing sender, receiver, or amount (Groth, 2016; Hopwood et al., 2026). The Sapling Spend circuit proves Pedersen-hash note-commitment tree membership, BLAKE2s-based nullifier derivation, and the algebraic relationship that fixes the randomized validating key rk as a correct re-randomization of the spending authorization key ak (Hopwood et al., 2026). The spend authorization signature itself is not in the circuit: spendAuthSig is validated outside the proof, against rk, as a separate transaction-validation consensus rule (Zcash Protocol Specification § 4.4) (Hopwood et al., 2026).

The proof compresses the in-circuit bundle to three group elements, roughly 192 bytes on BLS12-381 (two compressed $\mathbb{G}_1$ elements at 48 bytes plus one compressed $\mathbb{G}_2$ element at 96 bytes). The verifier checks one pairing-product equation containing four pairings. Because the $e(\alpha, \beta)$ term depends only on the verification key, implementations precompute it once, so the online check is typically described as three pairings (Groth, 2016).

A quantum adversary with sufficient hardware breaks the discrete logarithm problem on BLS12-381 in polynomial time (Shor, 1994). That alone is enough to forge Groth16 proofs: its knowledge soundness is proved in the generic bilinear group model, and a discrete-logarithm solver recovers the setup’s trapdoor scalars, with which the paper’s own simulator fabricates accepting proofs (Ch 35).

None of the components inside the Sapling circuit save the system. BLAKE2s inside the arithmetization keeps sufficient preimage margin against Grover at 256-bit output: a 256-bit hash gives roughly $2^{128}$ ideal quantum preimage queries (Grover, 1996). That is a query count and not a NIST category: the categories price attacks as gate counts under a depth limit against AES key search, whose ideal Grover query scale is $2^{64}$ for AES-128, and Chapter 14 draws that line (National Institute of Standards and Technology, 2016). The in-circuit Pedersen hashes are discrete-log-based: Shor on the Jubjub curve breaks their collision resistance, which separately weakens the note-commitment tree. The pairing equation at the verifier is the load-bearing break, and an adversary who forges at that layer does not need to touch the circuit. Migration therefore cannot be a matter of swapping a hash function. The verification semantics themselves have to change.

The decomposition below makes that conclusion precise. It names which layer carries the break, which layer inherits the posture of another, and which layer is replaceable without rewriting the statement being proved.

The four layers

A zero-knowledge proof system in the sense used by Part VI is a protocol with three properties. The verifier runs in polynomial time and ends convinced of a statement. The proof is short enough to be practical. The interaction reveals no information beyond validity. The Goldwasser-Micali-Rackoff knowledge-complexity framework established the formal definitions (Goldwasser et al., 1985): completeness, soundness, and zero-knowledge. Only zero-knowledge is quantified against a polynomial-time adversary, a cheating verifier. Soundness holds against any prover, with no bound on its computation, and completeness is a promise about the honest pair. Every deployed system in Part VI weakens that: it is an argument rather than a proof, sound only against a prover that cannot break its computational assumption, which is what the A in SNARK and STARK stands for and what makes a quantum soundness break possible at all. Many modern deployed systems reach soundness amplification through an interactive oracle proof (IOP) structure compiled non-interactively via the Fiat-Shamir transform (Ben-Sasson et al., 2019; Fiat & Shamir, 1987). Pairing-based non-interactive zero-knowledge proofs (NIZKs) such as Groth16 are the main exception covered in Part VI. The four-layer decomposition is a way to factor a deployed system into parts that can be analyzed in isolation.

The four layers are summarized in Table 31.1.

Table 31.1. The four layers.

Layer	Name	Role
L1	Arithmetization / encoding	Expresses a computation as algebraic constraints or polynomials over a finite field.
L2	Commitment + consistency	Binds the prover to witness data and exposes a consistency-check mechanism the verifier can run on a small number of queries.
L3	Protocol logic	The IOP or argument structure that reduces a statement to a sequence of oracle-access checks.
L4	Non-interactivity + extraction	The Fiat-Shamir transform, the oracle model (ROM or QROM), and the extractability assumption.

This decomposition is Encryptorium’s analytical framing and not a standard literature taxonomy. Two conflations are common in the literature. STARK analyses tend to merge L2 and L3 because FRI plays both roles: the Merkle-tree commitment to the evaluation table is the L2 polynomial commitment, and the proximity-test rounds are the L3 IOP that interrogates it. Groth16 analyses tend to merge L3 and L4 because Groth16 has no Fiat-Shamir or QROM surface. Its non-interactivity and extractability come from the structured reference string (SRS) and the algebraic shape of the three-element proof, so the L4 transcript-hash layer is absent: Groth16’s L4 is the SRS itself, and its post-quantum break is the same Shor computation that breaks L2. The decomposition clarifies those cases by requiring each layer to state what it binds, what it reduces, and what assumption it rests on. Chapters 32 to 35 analyze each layer in depth; this chapter surveys each layer and points forward.

The four layers in a toy running example

Take the statement “I know x such that sha256(x) = y” for a public 32-byte target y. At L1, the computation is the SHA-256 compression function applied to x, then an equality check against y. To prove it with an R1CS-based SNARK like Groth16, the computation is expressed as rank-1 constraints over a field F_p of about 255 bits (BLS12-381’s scalar field). Each constraint has the form (A·z) * (B·z) = C·z, where A, B, C are coefficient rows and z is a witness vector holding every intermediate bit. A full SHA-256 unrolls into tens of thousands of such constraints in typical libsnark / bellman benchmarks. The pedagogical point here is only the format. The chapter does not attempt to encode SHA-256 in full.

The block below shows the R1CS format on a small system. The statement is “I know a, b in F_p such that a * b = 35 and a + b = 12”. The witness z = (1, a, b, 35, 12) satisfies two constraints.

# Block 1: pedagogical slice of the R1CS format used at L1 (stdlib only).
# A pairing-based SNARK like Groth16 uses a ~256-bit prime field. Other
# systems in this Part do not: Boojum runs over Goldilocks and Stwo over
# Mersenne-31 (Ch 35), and Binius commits over binary-field towers (Ch 32).
P = 97  # toy prime, small enough to check by hand

# Columns of z: (one, a, b, a*b, a+b)
#   Constraint 1: (a) * (b) = (a*b)
#   Constraint 2: (a + b) * (1) = (a+b)
A = [[0, 1, 0, 0, 0], [0, 1, 1, 0, 0]]
B = [[0, 0, 1, 0, 0], [1, 0, 0, 0, 0]]
C = [[0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]


def dot(row, z):
    return sum(r * v for r, v in zip(row, z)) % P


def check_r1cs(A, B, C, z):
    for i, (a_row, b_row, c_row) in enumerate(zip(A, B, C)):
        lhs = (dot(a_row, z) * dot(b_row, z)) % P
        rhs = dot(c_row, z)
        if lhs != rhs:
            raise ValueError(f"constraint {i} failed: {lhs} != {rhs}")
    return True


z = (1, 5, 7, 35, 12)  # witness for a=5, b=7
print(check_r1cs(A, B, C, z))
# ==> True

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch31/, one file per block. Appendix C covers the clone and the environment they run on.

L1 by itself is quantum-safe. It is a statement about finite-field arithmetic. No cryptographic assumption enters at this layer. Arithmetic modulo a prime is the carrier for the statement, not a hardness assumption the adversary can attack.

At L2, the prover commits to the witness z or to polynomials encoding z. The commitment itself is short: a single group element for KZG, a single hash digest for Merkle. The opening proof scales with the structure: constant-size for KZG, logarithmic in the number of leaves for Merkle, and polylogarithmic for FRI which wraps a proximity-test proof around Merkle-committed evaluation tables. Binding is the property that carries soundness: a prover who commits to z must be unable to later open the commitment to a different value.

For KZG, binding reduces to the $t$-Strong Diffie-Hellman assumption (and related pairing-group assumptions) in a pairing-friendly group (Kate et al., 2010). For a Merkle commitment over a collision-resistant hash, binding follows from collision resistance. Two distinct openings at the same leaf index traverse the same sequence of parent positions. Any divergence in sibling values along those positions forces a hash collision. FRI replaces the polynomial commitment interface with a proximity-testing protocol that ensures the committed evaluation table is close to a low-degree polynomial (Ben-Sasson et al., 2018, 2020). The block below shows a pedagogical Merkle commitment and a single-leaf opening.

# Block 2: pedagogical slice of a Merkle commitment at L2 (stdlib only).
# Production trees domain-separate leaves and internal nodes,
# e.g. H(b"\x00" + leaf) vs H(b"\x01" + left + right); omitted here.
import hashlib


def H(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()


def commit(leaves):
    if len(leaves) == 0 or (len(leaves) & (len(leaves) - 1)) != 0:
        raise ValueError("leaves must be a nonempty power of two")
    nodes = [H(leaf) for leaf in leaves]
    while len(nodes) > 1:
        nodes = [H(nodes[i] + nodes[i + 1]) for i in range(0, len(nodes), 2)]
    return nodes[0]


def open_path(leaves, index):
    path = []
    nodes = [H(leaf) for leaf in leaves]
    while len(nodes) > 1:
        path.append(nodes[index ^ 1])
        nodes = [H(nodes[i] + nodes[i + 1]) for i in range(0, len(nodes), 2)]
        index //= 2
    return path


def verify_path(leaf, index, path, root):
    # The index is public input, so the verifier derives the left/right
    # position at each level from it rather than trusting the prover.
    acc = H(leaf)
    for sibling in path:
        acc = H(sibling + acc) if index & 1 else H(acc + sibling)
        index //= 2
    return acc == root


leaves = [b"x0", b"x1", b"x2", b"x3"]
root = commit(leaves)
path = open_path(leaves, 2)
print(verify_path(b"x2", 2, path, root))
# ==> True

L2 is the load-bearing layer for post-quantum analysis. The cryptanalysis section below states the quantum-safety posture of each common choice.

At L3, the prover and verifier run a protocol that reduces the statement “I know a witness satisfying the R1CS” to a sequence of oracle-access checks against the L2 commitment. The same holds for the other two arithmetizations, the algebraic intermediate representation (AIR) and the PLONKish gates. For a STARK, L3 is the low-degree test plus a consistency check between the arithmetized trace and the claimed polynomial evaluations (Ben-Sasson et al., 2018). For Groth16, L3 is the algebraic structure of the three-element proof, which the verifier pairs against the structured reference string (Groth, 2016).

In IOP-style or polynomial-protocol-style systems such as STARKs and PLONKish systems, much of L3 is information-theoretic once the L2 polynomial-commitment interface is fixed. Soundness at L3 composes from the binding of L2 plus an oracle-query argument, and does not rest on a separate computational assumption (Ben-Sasson et al., 2019). In pairing SNARKs such as Groth16, the algebraic protocol logic and the SRS-based commitment are more tightly coupled, so the L3/L2 boundary is analytical rather than literally modular. In either case the post-quantum posture of L3 is inherited from L2. L3 rarely receives its own post-quantum analysis in the literature.

At L4, the protocol is made non-interactive by replacing the verifier’s random challenges with hash digests over the transcript, following Fiat-Shamir (Fiat & Shamir, 1987). Classical security proofs work in the random oracle model; the quantum setting requires the quantum random oracle model, in which the adversary may query the hash oracle in superposition. Don-Fehr-Majenz-Schaffner 2019 established that Fiat-Shamir preserves both soundness and proof of knowledge in the QROM for any three-round Sigma-protocol (Don et al., 2019). Ch 33 states the theorem, the side conditions a concrete scheme has to discharge, and what justifies them. The measure-and-reprogram reduction loses roughly q_H^2 in the QROM, compared to the q_H factor in the ROM proof, and the final extractor inherits the underlying Sigma-protocol’s own quantum extraction loss on top of it (Don et al., 2019). Multi-round IOPs, recursive proof composition, and FRI-style proximity arguments need their own QROM analyses. Ch 33 works through the three cases.

Not every deployed system uses Fiat-Shamir at L4. Groth16 is an exception: its non-interactivity and extractability come from the structured reference string and the algebraic shape of the three-element NIZK rather than from a transcript-hash compilation (Groth, 2016). In this decomposition Groth16’s L4 is the CRS rather than a Fiat-Shamir transform, and its post-quantum break is the same Shor break as L2’s: the SRS trapdoor is a set of discrete logarithms in the public string, and Shor recovers it. Systems that do use Fiat-Shamir at L4 include PLONK, STARKs, Bulletproofs, and Halo 2 (Ben-Sasson et al., 2018; Gabizon et al., 2019).

Cryptanalysis: per-layer quantum-safety

The per-layer threat model is stated here at survey depth. Ch 32 to Ch 34 derive the details.

L1 carries no cryptographic assumption. Arithmetizations over F_p or F_{2^k} are closed under any polynomial-time adversary, quantum or otherwise. The only quantum-relevant question at L1 is whether the field choice enables small-field attacks on the commitment layer, a question that lives at L2.

L2 partitions into three regimes.

The first regime is pairing-based and discrete-log-based commitments. Examples include KZG for PLONK, the pairing-based commitment encoded in the SRS for Groth16, the inner-product argument (IPA) for Halo 2 and Bulletproofs, and Pedersen-based commitments in folding schemes such as Nova. Groth16 does not use KZG: its commitment is fixed by the circuit-specific SRS and checked by a single pairing equation, with no polynomial-commitment module to swap. KZG, IPA and Pedersen binding reduce to variants of the discrete logarithm problem in a prime-order group, and Groth16’s knowledge soundness is proved in the generic bilinear group model with a trapdoor a discrete-logarithm solver recovers. Shor solves discrete log in quantum polynomial time, and the binding of all of them therefore collapses (Shor, 1994). The break is structural when the L2 interface is not separable from the verifier (Groth16) and modularly replaceable when the L2 interface is an exposed polynomial commitment module that can be swapped (PLONK) (Gabizon et al., 2019; Groth, 2016).

The second regime is hash-based commitments. Examples include Merkle for STARKs and FRI for Plonky2, Plonky3, and Circle STARKs. Binius is in the same regime by a different route: the paper this book cites commits with a Brakedown-style Merkle commitment over a Reed-Solomon-encoded matrix rather than with FRI (Diamond & Posen, 2025). Binding reduces to the collision resistance of the underlying hash function. Under the Brassard-Hoyer-Tapp quantum collision search the query-model bound is roughly $2^{n/3}$ for an $n$-bit hash, assuming quantum random-access classical memory (QRACM) (Brassard et al., 1998); without QRACM the small-quantum-memory variant gives roughly $2^{2n/5}$ time with about $2^{n/5}$ classical memory (Chailloux et al., 2017). A 256-bit hash delivers about 85 bits of post-quantum collision resistance under the BHT query-model bound. A STARK deployment targeting 128 bits of collision margin under the same query model therefore moves to a 384-bit or larger hash output (Ben-Sasson, 2021). The query-model bound is a worst-case theoretical target, not a literal deployment-cost figure.

Figure 31.1. Audit the red cell first: if the L2 mechanism is not separable from the verifier (Groth16), a Shor-capable adversary forces full verifier replacement rather than a commitment swap. For PLONK the red cell is isolable and points to a polynomial-commitment migration. For STARKs the green cell sets the migration question to hash-output sizing rather than algebraic replacement.

The third regime is lattice-based commitments, covered in Ch 32 and not in scope here.

FRI adds a second component at L2: the proximity gap. The proximity test is information-theoretic, in the sense that its analysis does not depend on any computational assumption (Ben-Sasson et al., 2020). The quantum adversary enters the FRI argument through two paths. The first is Merkle binding: can the prover equivocate on committed evaluations? The second is the QROM compilation of the interactive protocol: does the Fiat-Shamir transform survive?

Block, Garreta, Katz, Thaler, Tiwari, and Zajac prove Fiat-Shamir security for FRI, batched FRI, and the Plonk-like members of a class of low-degree-proximity protocols, with Plonky2 the worked case, and sketch the argument for ethSTARK and RISC Zero (Block et al., 2023). Block and Tiwari then carry that analysis into a concrete-parameter regime. They examine deployed and near-deployed FRI parameter settings and report that in all but one of the surveyed sets, provable non-interactive FRI security lags conjectured security by 21 to 63 bits (Block & Tiwari, 2024). Against the conjectured target itself those same parameters come within a bit.

What is still open at deployment parameters

The remaining gap is a full deployment-level QROM accounting that composes interactive FRI soundness, Fiat-Shamir loss, Merkle binding, hash-output width, grinding, recursion, transcript binding, and per-system parameter choices for any one production pipeline. Concrete post-quantum security numbers at deployment parameters are therefore best read as “formal Fiat-Shamir analysis exists; full end-to-end accounting is system-specific and pending” rather than “FRI is unanalyzed” (Ben-Sasson, 2021). Ch 33 returns to it for the QROM proofs and Ch 35 for the deployed pipelines.

In the IOP-style systems Part VI covers, L3 is largely information-theoretic once the L2 binding interface is fixed. Its post-quantum posture is the posture of the L2 it is built on. A PLONK argument with KZG at L2 inherits KZG’s Shor break at L3; the same PLONK argument with a lattice commitment at L2 inherits the lattice commitment’s assumption at L3. In Groth16 the L2/L3 boundary is analytical rather than modular, so the post-quantum break is still best assigned to the pairing-and-SRS layer rather than to arithmetization or Fiat-Shamir. L3 is not where the post-quantum analysis lives.

L4 splits into two cases. Groth16 has no Fiat-Shamir/QROM surface at L4: its L4 is the CRS, and both L2 and L4 fall to one Shor computation on the pairing curve (BLS12-381 for Sapling), which is why Chapter 35 colours both cells red. Systems that apply Fiat-Shamir require a QROM proof, and the proof depends on the protocol shape. Three-round Sigma-protocols have the Don-Fehr-Majenz-Schaffner result: soundness and proof of knowledge both survive the transform in the QROM, at an $O(q_H^2)$ loss in the measure-and-reprogram reduction (Don et al., 2019). The knowledge statement asks that the Sigma-protocol already be a quantum proof of knowledge. Quantum computationally unique responses together with $t$-soundness is the route DFMS19 gives for establishing that, and each scheme has to justify it from its own algebra. Multi-round IOPs with state that the prover can branch on are harder to analyze. The measure-and-reprogram technique addresses some cases, but a per-system QROM reduction is still needed. Classical Fiat-Shamir security does not transfer automatically to the QROM. Ch 33 covers which transforms survive and which need restructuring.

Figure 31.2. Read a column to answer one operator question: parameter fix, structural replacement, or pending concrete-parameter accounting. A red cell forces a structural replacement at that layer for the system class it names. An amber cell indicates a parameter bump restores the margin (hash size at L2, grinding at L4) or end-to-end concrete QROM accounting may still be pending for that protocol shape. A green cell needs no action under the given attack. L3 inherits L2's posture, so auditing L3 in isolation is not useful.

Tradeoffs across commitment and non-interactivity choices

A two-axis classification sorts deployed systems by L2 commitment choice and L4 non-interactivity transform. Table 31.2 shows how common choices land.

Table 31.2. Two-axis tradeoffs across representative L2 and L4 choices.

L2 choice	L4 transform	L2 under Shor	L2 under Grover / BHT	Prover	Verifier	Proof size
Pairing + SRS	Algebraic NIZK (Groth16)	broken	not applicable	fast	very fast (pairings)	smallest (~192 B)
KZG (pairing)	Fiat-Shamir (PLONK)	broken	not applicable	fast	very fast (pairings)	small (sub-KB)
IPA (discrete-log)	Fiat-Shamir (Halo 2, Bulletproofs)	broken	not applicable	medium	O(N) multi-exp (batchable)	medium (log-size)
Merkle + FRI (hash-based)	Fiat-Shamir (STARKs, Plonky2)	not at L2 (hash-based)	Grover / BHT degrades; n >= 384 restores under BHT worst case	slow	medium	large (~100s of KB)
Lattice (module-SIS / ring-SIS)	Fiat-Shamir	post-quantum assumption	not applicable	slow	medium	large (shrinking in recent literature)

The table is coarse. Per-system numbers at deployment parameters appear in Ch 32 (commitments) and Ch 35 (case studies). L2 is the load-bearing quantum-safety axis: every entry in the Shor column reflects the row’s L2 commitment choice, not L1 and not L3. The absence of a Fiat-Shamir surface in Groth16’s L4 is not a safety advantage; it is the shape that makes the L2 break structural rather than modularly replaceable.

Where Chapter 31 ends and Chapter 32 picks up

This chapter named four layers and assigned each deployed family a posture at each of them. It derived none of those postures. Every cell of Table 31.2 summarizes a result argued elsewhere, which is why the table says outright that it is coarse and points at the two chapters that make it precise.

Chapter 32 derives the L2 column. Three commitment families reach a common depth of commitment definition, opening protocol, binding reduction, and quantum adversary analysis: KZG, Merkle, and FRI. Lattice polynomial commitments get the definition, the Module-SIS binding reduction and the quantum posture, but the evaluation protocols the recent constructions rely on rest on ring structure Chapter 32 puts out of scope, so a coefficient-commitment toy stands in for the opening protocol there. A coda covers inner-product arguments, which need no trusted setup and are Shor-broken all the same. Table 32.2 extends Table 31.2 with concrete parameters. The binary Merkle tree printed above becomes a tree of configurable arity and configurable hash-output width, which is where the 384-bit figure stops being an inequality and starts being a deployment choice.

The remaining layers are spread across the rest of the Part. L4 is Chapter 33, where the Fiat-Shamir results cited above are derived rather than named. L3 never gets a chapter to itself, for the reason the cryptanalysis section gives: the decomposition assigns it no separate computational hardness assumption, so its posture is inherited from L2. Its information-theoretic contribution is analyzed all the same, in Chapter 34’s soundness budget, where the proximity gap, the decoding regime and the query error each get a term. Chapter 34 assembles L1, L2, and L4 into one end-to-end STARK and composes the stages into a single soundness budget, and Chapter 35 reads the decomposition off Zcash, ZKsync, and Starknet.

Part VII picks up the four-layer decomposition at the systems level for blockchain operators. Each layer carries an operator-facing analogue. L1 arithmetization sits behind circuit-design governance: the choice of R1CS, PLONKish, or AIR is fixed in the verifier contract bytecode at deployment, so any change requires a redeploy or a proxy upgrade. L2 commitment is where the deployed-rollup tradeoff lands: KZG against FRI, with Shor-driven L2 replacement on the pairing-based side and BHT hash-width sizing on the FRI side. L4 Fiat-Shamir carries the pending-QROM conditional that Ch 33 derives. The operator response is the governance machinery covered in Ch 41. The hash primitive is the on-chain hash: SHA-256 for Bitcoin, Keccak-256 for Ethereum, and Poseidon for zk-rollup circuits. Ch 40 derives the per-layer operational decomposition for production L2 rollups and names the operator decision at each layer.

Exercises

1. Halo 2 combines PLONKish arithmetization with an inner-product argument (IPA) commitment and a Fiat-Shamir accumulation scheme for recursion. Classify Halo 2 under the two-axis taxonomy of L2 choice and L4 transform. State which layer you would audit first for a quantum-safety review and why.

2. Take the toy statement “I know x such that sha256(x) = y” with y the SHA-256 digest of the 4-byte ASCII string "open". At L1, count the additional R1CS constraints needed to compute one 32-bit XOR gate (used inside the SHA-256 compression function) when the two 32-bit inputs are already represented as boolean-constrained wires (so booleanity constraints on the inputs are not counted again). Use the standard per-bit encoding $a \oplus b = a + b - 2ab$. You do not need to encode full SHA-256.

3. The chapter places arithmetization at L1 rather than nesting it inside L3. Defend the choice. Identify a consequence that would follow if arithmetization were instead treated as part of the IOP framework rather than as a separate layer. One paragraph.

4. For each of Groth16, PLONK with KZG, and Bulletproofs, name the layer that Shor’s algorithm breaks structurally, which is the layer left with no post-quantum margin at all. STARKs with Merkle+FRI have no such layer, so ask a different question of them: name the layer whose security is set by generic quantum collision search rather than by a hardness assumption, and name the parameter the deployment must adjust to maintain 128-bit post-quantum collision security under the Brassard-Hoyer-Tapp bound. Then state why that answer is a necessary condition on one layer’s budget and not a ranking of the pipeline’s end-to-end margins, naming two quantities a ranking would need that this exercise does not supply.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 31. A separate track, for rebuilding rather than reading: the package exercises/ch31-zk-layers has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch31 to grade your version against the suite that proves the reference one.

References

Ben-Sasson, E. (2021). ethSTARK Documentation. IACR ePrint 2021/582. https://eprint.iacr.org/2021/582

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, Transparent, and Post-Quantum Secure Computational Integrity. IACR ePrint 2018/046. https://eprint.iacr.org/2018/046

Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., & Ward, N. P. (2019). Aurora: Transparent Succinct Arguments for R1CS. Advances in Cryptology — EUROCRYPT 2019. https://doi.org/10.1007/978-3-030-17653-2_4

Ben-Sasson, E., Goldberg, L., Kopparty, S., & Saraf, S. (2020). DEEP-FRI: Sampling Outside the Box Improves Soundness. Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.5

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

Block, A. R., & Tiwari, P. R. (2024). On the Concrete Security of Non-interactive FRI. Security and Cryptography for Networks — SCN 2024. https://doi.org/10.1007/978-3-031-71070-4_13

Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum Cryptanalysis of Hash and Claw-Free Functions. LATIN ’98: Theoretical Informatics, 1380, 163–169. https://doi.org/10.1007/bfb0054319

Chailloux, A., Naya-Plasencia, M., & Schrottenloher, A. (2017). An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. Advances in Cryptology — ASIACRYPT 2017, 211–240. https://doi.org/10.1007/978-3-319-70697-9_8

Diamond, B. E., & Posen, J. (2025). Succinct Arguments over Towers of Binary Fields. Advances in Cryptology — EUROCRYPT 2025. https://doi.org/10.1007/978-3-031-91134-7_4

Don, J., Fehr, S., Majenz, C., & Schaffner, C. (2019). Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Advances in Cryptology — CRYPTO 2019. https://doi.org/10.1007/978-3-030-26951-7_13

Fiat, A., & Shamir, A. (1987). How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In A. M. Odlyzko (Ed.), Advances in Cryptology — CRYPTO ’86 (pp. 186–194). Springer. https://doi.org/10.1007/3-540-47721-7_12

Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive Arguments of Knowledge. IACR ePrint 2019/953. https://eprint.iacr.org/2019/953

Goldwasser, S., Micali, S., & Rackoff, C. (1985). The Knowledge Complexity of Interactive Proof-Systems. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC ’85), 291–304. https://doi.org/10.1145/22145.22178

Groth, J. (2016). On the Size of Pairing-based Non-interactive Arguments. Advances in Cryptology — EUROCRYPT 2016. https://doi.org/10.1007/978-3-662-49896-5_11

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. https://doi.org/10.1145/237814.237866

Hopwood, D.-E., Bowe, S., Hornby, T., & Wilcox, N. (2026). Zcash Protocol Specification, Version v2026.7.0 [NU6.2] [Protocol Specification]. Electric Coin Company. https://zips.z.cash/protocol/protocol.pdf

Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-Size Commitments to Polynomials and Their Applications. In Advances in Cryptology — ASIACRYPT 2010 (Vol. 6477, pp. 177–194). Springer. https://doi.org/10.1007/978-3-642-17373-8_11

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 124–134. https://doi.org/10.1109/SFCS.1994.365700