Recursive proofs

In a recursive proof, one proof attests to the validity of another or several others. It is implemented by encoding the system's verification algorithm, the verifier circuit, inside the very circuit being proven. At each step a new proof is generated certifying that the latest batch of computation is correct and that the previous proof was valid. The result is a single constant-size final proof backing a computation chain of any length. Associated concepts are incrementally verifiable computation (IVC) and proof-carrying data.

It is the basis of massive scaling and rollup aggregation: it lets thousands of transactions or many individual proofs be compressed into one, verifiable on-chain at fixed cost, and keeps blockchain state at a constant size. Modern accumulation or folding techniques defer the expensive part of verification, the polynomial commitment opening, and accumulate it into a single operation at the end, which makes recursion cheaper.

The milestones illustrate this. Halo (Bowe, Grigg and Hopwood, 2019) was the first practical example of recursive composition without a trusted setup. Nova (Kothapalli, Setty and Tzialla, CRYPTO 2022) introduces IVC through folding with the smallest verifier circuit in the literature. Zcash's Halo 2 implements recursive composition without a trusted setup, and Mina Protocol keeps a constant-size blockchain of around 22 KB thanks to recursion via its Pickles system.