Abstract
Recursive ZK proof composition is the technique of writing a ZK circuit that verifies another ZK proof, producing a new proof that attests to the correctness of the inner verification. The resulting proof has the same size as any single proof, but it encodes knowledge of an arbitrarily long chain of prior proofs. Recursion is what enables proof systems like Nova, Halo2, and Plonky2 to accumulate hundreds or thousands of computation steps into a single compact proof, and it is the mechanism behind succinct blockchain designs that compress the entire history of a chain into a single constant-size proof. Getting recursion right requires careful attention to field compatibility, circuit efficiency of the inner verifier, and the distinction between native and non-native field arithmetic.
Why Field Compatibility Matters
A ZK proof produced over the BLS12-381 scalar field contains group elements on BLS12-381 and a verification equation over that field. Verifying it inside a Groth16 circuit means the circuit’s native field must be the field over which the outer proof is being produced. If the outer proof uses a different curve, verifying the inner proof requires non-native field arithmetic - simulating field operations of field F_p inside a circuit over field F_q where p != q. Non-native arithmetic requires range decomposition and carry handling, inflating the constraint count by roughly 10-50x per field operation. Pasta curves (Pallas and Vesta) were designed specifically so that the scalar field of Pallas equals the base field of Vesta and vice versa, enabling efficient 2-cycle recursion where proving over each curve is native. Halo2, developed by the Electric Coin Company for Zcash’s Orchard upgrade, uses Pasta curves precisely for this cycle property.
Nova and Incrementally Verifiable Computation
Nova (Kothapalli, Setty, and Tzialla, 2021) introduced a folding scheme-based approach to recursive proof composition that avoids the expensive inner-verifier circuit entirely. Rather than verifying one proof inside a circuit, Nova’s prover folds two relaxed R1CS instances into one, accumulating computation incrementally. The resulting accumulated instance can be verified with a standard R1CS proof at the end of the computation. Nova achieves near-linear prover time per computation step, making it practical for long sequential computations like virtual machine execution. The nova-snark Rust crate from the Microsoft Research team provides the reference implementation, and SuperNova extends the approach to support multiple different circuit types in the same accumulation - useful for zkEVM designs where different EVM opcodes have different constraint structures.
Plonky2 and Hash-Based Recursion
Plonky2 from Polygon combines PLONK with FRI polynomial commitments to enable recursion over a single field without a 2-cycle. Because both the inner and outer proofs use the same Goldilocks field (p = 2^64 - 2^32 + 1), verifying a Plonky2 proof inside a Plonky2 circuit is native. The resulting recursive prover generates a proof in approximately 170ms on a modern laptop, fast enough for on-chain recursion where proofs are generated per-block. Plonky3 iterates on this design with a more modular architecture that supports multiple polynomial commitment schemes, including Brakedown for linear-time proving and FRI for compact proofs. The Polygon zkEVM type 1 prover uses a Plonky2 recursive layer to wrap its EVM execution proofs before submitting them to Ethereum.
Practical Limits and Ongoing Work
Recursion adds proving overhead because verifying an inner proof inside a circuit contributes additional constraints. For pairing-based proofs like Groth16, the inner verifier circuit contains pairing computations that translate to hundreds of thousands of constraints, making one level of recursion already expensive and two levels prohibitive without aggressive optimization. Aggregation schemes like SnarkPack (Gabizon and Williamson) and HALO-style accumulation amortize this cost across many proofs by deferring the expensive pairing check to a single batch verification at the end. As of late 2025, the boundary between recursive composition and aggregation is blurring in production systems, with most zkEVM rollups using a hybrid: Nova-style accumulation for execution steps, wrapped in a Plonky2 or Groth16 proof for the final on-chain submission.