Recursion, folding, and Nova

Understand proof recursion (a proof that verifies another proof), folding schemes such as Nova that make incrementally verifiable computation cheaper, what they add — notably IVC for long or repeated computations — and their current, honest limitations.

Track

Engineering

Module

4 · Zero-Knowledge Proofs

Prerequisites

Proving systems compared · Commitments and setup

Some computations are too long to prove in one shot, or run step after step forever — a virtual machine executing instructions, an agent taking action after action. Proving each step independently and then checking thousands of separate proofs is wasteful. Two ideas address this. Recursion: write a circuit that itself verifies a proof, so one proof can certify "I checked the previous proof, and did one more step" — chaining or compressing arbitrarily many steps into a single final proof. Folding: a lighter-weight alternative that avoids fully proving every step, instead combining ("folding") repeated computation instances together and proving only once at the end.

Both are routes to incrementally verifiable computation (IVC): the ability to maintain a running proof that "everything up to step n was done correctly", updating it cheaply as each new step arrives. Nova (2021) is the best-known folding-based construction and sparked an active line of follow-on work.

Recursive proof composition puts a verifier inside a circuit: the statement becomes "I know a proof pi that the previous verifier would accept, AND I correctly performed step F". Each new proof absorbs the prior one. The catch is that verifying a proof inside a circuit is expensive, so classic recursion carries significant per-step overhead. Folding schemes reduce that overhead by deferring the expensive proving: they define a relaxed form of the constraint system that two instances can be combined into, so N steps collapse into one instance that is proven a single time.

Recursion (proof composition)

A circuit that verifies another proof, letting proofs certify proofs — used to compress many proofs into one or to prove unbounded computation.

IVC (Incrementally Verifiable Computation)

Maintaining a short proof that a step-by-step computation has been correct up to the current step, updatable as each step runs (concept introduced by Valiant, 2008).

Folding scheme

A method to combine two instances of the same constraint relation into a single instance, so a long sequence needs only one final proof rather than one per step. Nova (Kothapalli, Setty & Tzialla, 2021) is the canonical example.

Relaxed R1CS

The adapted constraint form Nova introduced so that two R1CS instances can be folded into one while remaining checkable.

The contrast below is schematic. F is one step of the computation; z_i is the state after step i. "Prove" means running the (expensive) underlying proving system; "fold" means the cheap combine step a folding scheme provides.

Recursion vs folding for IVC (schematic)
Goal (IVC): certify  z_n = F(F(...F(z_0)...))   (n steps)

Naive: prove each step, verify n proofs separately  -> O(n) verify work.

Recursive IVC:
   step i proves:  "z_i = F(z_{i-1})  AND  previous proof pi_{i-1} verifies"
   # a VERIFIER circuit is embedded in each step -> heavy per-step cost
   output: one final proof pi_n certifying all n steps.

Folding (Nova-style):
   keep a running "folded" instance  U  summarizing steps so far.
   at step i:   U_i = Fold( U_{i-1}, u_i )     # u_i = this step's instance
       # Fold is cheap: mostly commitments + a random linear combination,
       # NO full proof generated per step
   only at the END:  produce ONE proof that U_n is satisfied.
   => per-step cost is dominated by cheap folding, not by proving.

The key economic idea: folding moves the expensive "prove" operation out of the per-step loop and performs it once at the end, with each step reduced to a cheap folding operation (commitments plus a random linear combination, justified via Fiat–Shamir). That is why Nova-style IVC can be attractive for very long or repetitive computations. It does not make proving free — the final proof still costs what the underlying system costs — and the folded instance still has to be opened and verified once.

1. 1Express one step F of the computation as a constraint system (e.g. relaxed R1CS) the folding scheme accepts.
2. 2Initialize a running folded instance from the starting state z_0.
3. 3For each step: compute the new state, form this step's instance, and fold it into the running instance — a cheap operation, no full proof yet.
4. 4Carry only the compact folded instance between steps (this is what keeps per-step cost low and state small).
5. 5After the final step, generate a single proof that the accumulated folded instance is satisfied; a verifier checks that one proof to be convinced all steps were correct.

synthetic — an agent proving a long action history with folding
Each step F = "apply one authorized action, update agent state":
   z_i = F(z_{i-1}, action_i, credential_i)

Per action (cheap):
   u_i = instance("action_i was authorized and state updated correctly")
   U   = Fold(U, u_i)          # commitments + random linear combo; no SNARK yet

After the session (once):
   proof = Prove(U)            # single proof over the folded instance
   # A verifier checks 'proof' and is convinced EVERY action in the
   # session was authorized and applied correctly -- without replaying
   # the whole history and without seeing the credentials (witness).

This captures the appeal for agents: a long sequence of authorized actions can be compressed into one end-of-session proof, so an auditor verifies a single artifact rather than re-checking every step. The honesty caveat: the final proof still costs what the base proving system costs, folding adds its own engineering complexity, and the scheme must be instantiated carefully for the soundness guarantees to hold.

Agents produce long streams of actions, and IVC is a natural fit: a worker can maintain a running proof that "every action so far was authorized and correctly applied", folding each new action in cheaply, then emit one proof when a verifier (or auditor) asks. This gives verifiable, tamper-evident action histories without exposing the underlying credentials and without forcing the verifier to replay the entire session — directly relevant to the delegation and audit story in Module 5.

Recursion separately enables cross-boundary composition: an agent can wrap a sub-agent's proof inside its own, certifying "I verified my delegate's proof and added my step", building a chain of accountable delegation. Both techniques are promising, but an architect should treat them as advanced, still-maturing tooling rather than settled infrastructure.

• ▸Recursion and folding do not eliminate the base system's trade-offs: the final proof inherits the setup requirements, assumptions and post-quantum posture of the underlying proving system.
• ▸Folding is comparatively new and evolving rapidly (Nova and numerous follow-on schemes); implementations are less battle-tested than mature non-recursive systems, so audit and implementation risk is higher.
• ▸Correctness is subtle: the relaxed constraint form, the folding randomness (Fiat–Shamir), and the final proof must all be instantiated correctly, or soundness can silently fail.
• ▸Benefits are workload-dependent: folding shines for long, uniform, repeated steps; for a single small computation it can add overhead rather than save it.
• ▸None of this changes the semantic caveat from earlier modules: a valid IVC proof certifies that steps were performed as constrained — not that the underlying policy or actions were wise or safe.

Expected direction: Naive recursion embeds a full proof verifier in every step and generates a proof per step, so the expensive prove/verify work happens in the per-step loop (high per-action cost). Folding replaces the per-step proof with a cheap fold (commitments plus a random linear combination) and defers the single expensive proof to the very end, so per-action cost is dominated by the cheap fold. It would NOT be worth it for a single short/one-off computation: there are no many repeated steps to amortize, so the added complexity and the one final proof can cost more than just proving directly.

What is incrementally verifiable computation (IVC)?

Maintaining a short, updatable proof that a step-by-step computation has been performed correctly up to the current step, so each new step extends the proof cheaply rather than re-proving everything.

How does a folding scheme like Nova reduce per-step cost compared with classic recursion?

It avoids generating a full proof at every step; instead it folds each step's instance into a running one via a cheap operation (commitments plus a random linear combination), and produces just one proof at the end.

Do recursion and folding remove the trusted-setup or post-quantum limitations of the base proving system?

No — they are layered on top of a base system and inherit its setup requirements, cryptographic assumptions, and post-quantum posture; they change proving cost structure, not those underlying trade-offs.