Notes on the Composability of ZK Proof Systems

When people say a proof system is “composable” they rarely mean the same thing. Sometimes they mean that a proof can verify another proof. Sometimes they mean that many proofs can be merged into one. And sometimes they mean something closer to what smart-contract developers mean: that independent parties can build on each other’s statements without coordinating. These are three different properties, with three different costs, and conflating them leads to confused designs.

Three meanings of “composable”

1. Proof composition. A proof $\pi_2$ attests that a verifier accepted an earlier proof $\pi_1$. This is recursion, and it is what makes incrementally verifiable computation possible.¹
2. Accumulation. Instead of verifying each proof, the expensive part of verification is deferred and merged into a running accumulator that is checked once, at the end.
3. Application-level composition. Statements refer to other statements. A proof about a rollup’s state transition can be consumed by a bridge, which is consumed by an exchange, and none of the three teams needs to know about the others in advance.

The first two are properties of a proof system. The third is a property of how statements are designed, and no amount of recursion will give it to you for free.

Recursion: a verifier inside a circuit

To prove “I verified $\pi_1$”, the verifier $V$ of the inner proof system has to be expressed as a circuit of the outer one. If the computation being proved has size $|F|$ and the verifier circuit has size $|V|$, every step of an incremental computation pays for $|F| + |V|$ constraints, so the quantity that matters is the overhead ratio $|V| / |F|$.

For pairing-based SNARKs the verifier is dominated by a few pairings, which are expensive to arithmetise because the pairing’s field is not the circuit’s native field. Cycles of elliptic curves avoid the non-native arithmetic, at the price of either giving up pairings on at least one curve of the cycle or using pairing-friendly cycles whose fields are very large.²

A proof system composes well when verifying a proof inside another proof is cheap compared to the computation being proved. Everything else is engineering around that ratio.

Accumulation and folding

The observation behind accumulation schemes is that the verifier does not have to be run inside the circuit; it is enough to postpone its expensive part.³ In Halo this is the linear-time check of an inner-product argument; each step adds the claim to an accumulator with a random linear combination, and only the final accumulator is checked by a “decider”.⁴

Folding schemes push this further. Nova folds a fresh R1CS instance, with witness commitment $\bar{W}_2$ and public input $\mathbf{x}_2$, into a running relaxed instance using one random challenge $r \gets \F$ and the commitment $\bar{T}$ to a cross term sent by the prover. The per-step cost of recursion becomes a constant number of group operations rather than a verifier circuit:⁵

$$(\bar{E},\, u,\, \bar{W},\, \mathbf{x}) \;=\; (\bar{E}_1 + r\,\bar{T},\;\; u_1 + r,\;\; \bar{W}_1 + r\,\bar{W}_2,\;\; \mathbf{x}_1 + r\,\mathbf{x}_2).$$

The table hides an important asymmetry: in the last two rows the object that comes out of step $i$ is not yet a succinct proof. Succinctness is restored only at the very end, by a final SNARK.

Application-level composition

A proof composes with the outside world through its public inputs, in the same way a function composes through its signature. If the public input of a state-transition proof is a pair of state roots $(\mathsf{root}_{\text{old}}, \mathsf{root}_{\text{new}})$, anyone can chain proofs, aggregate them, or build a bridge on top. If instead the statement hard-codes a verification key, a fixed batch size, or a particular hash of the calldata, every consumer must be redeployed when the producer changes.

Two design rules follow:

• Treat the public-input layout as an API. Version it, document it, and keep it small.
• Separate aggregation (many proofs, one verification, no semantic relationship) from composition (one statement refers to another). The former is an optimisation and can be changed at will; the latter is a contract between systems.

What it costs

Recursion is not free even when the prover overhead is small. Knowledge soundness of a recursive proof is argued by extracting witnesses layer by layer, and the extractor’s running time can grow exponentially with the depth of the recursion, which is why the classical guarantees are stated for constant depth.⁶ Deployed systems recurse far deeper than that and rely on the absence of known attacks.

A rough cost checklist

• Non-native field arithmetic, or a curve cycle with its own constraints.
• Hashing the accumulator or the running instance inside the circuit (Fiat–Shamir in-circuit).
• One final “compression” proof, often in a different proof system, to obtain a small proof.
• A larger trusted computing base: the verifier circuit is now security-critical code.

Footnotes

1. Paul Valiant, “Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency”, TCC 2008. ↩︎

2. Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer and Madars Virza, “Scalable Zero Knowledge via Cycles of Elliptic Curves”, CRYPTO 2014. ↩︎

3. Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra and Nicholas Spooner, “Proof-Carrying Data from Accumulation Schemes”, TCC 2020. ↩︎

4. Sean Bowe, Jack Grigg and Daira Hopwood, “Recursive Proof Composition without a Trusted Setup”, IACR ePrint 2019/1021. ↩︎

5. Abhiram Kothapalli, Srinath Setty and Ioanna Tzialla, “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes”, CRYPTO 2022. ↩︎

6. Nir Bitansky, Ran Canetti, Alessandro Chiesa and Eran Tromer, “Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data”, STOC 2013. ↩︎