Folding Scheme

The core mechanism of a folding scheme is to take two independent instances of a constraint system (e.g., two R1CS instances) and compress them into a single, new instance. The prover and verifier interactively compute a random linear combination of the two witnesses and public inputs. The security relies on the fact that if the new, combined instance is satisfiable, then both original instances were satisfiable with high probability. This is fundamentally different from proof recursion, which verifies a proof inside a circuit.

Folding schemes achieve efficiency by deferring expensive group operations to the very end of a computation chain. Instead of performing costly elliptic curve multiplications or pairings at every step of a recursive proof, folding only performs lightweight field arithmetic to combine instances. The heavy cryptographic lifting—such as computing a polynomial commitment—is done only once on the final folded instance. This is the key insight that makes provers like Nova an order of magnitude faster than traditional recursive SNARKs.

A powerful extension of standard IVC, folding schemes enable Non-Uniform IVC (NIVC). In standard IVC, the same function F is applied repeatedly. With NIVC, a folding scheme can prove the correct execution of a chain of different functions F_1, F_2, ..., F_n. This is crucial for real-world applications like a zkVM, where each step of the virtual machine might execute a different opcode (ADD, MUL, STORE), each represented by a distinct circuit that gets folded into the running accumulator.

To enable efficient random linear combination, folding schemes often operate on a relaxed version of the original constraint system. A standard R1CS requires an exact equality check. A relaxed R1CS introduces a slack term or error vector, allowing the combined instance to absorb the cross-terms that arise from the linear combination of two valid witnesses. The final proof then demonstrates that the slack term is correctly accounted for, ensuring the integrity of the original computation without requiring a perfectly homogeneous algebraic structure.

While the core folding interaction is a public-coin protocol, it is transformed into a non-interactive scheme using the Fiat-Shamir heuristic. The prover derives the random challenge for the linear combination by hashing the current accumulator instance and the new incoming instance. This produces a deterministic, verifiable challenge without requiring a live verifier. The resulting non-interactive folding proof is a single, compressed instance that can be verified directly or further folded, forming the backbone of systems like Nova.

Traditional recursive SNARKs (e.g., using Groth16 or Plonk wrappers) verify an entire proof inside a circuit, which is extremely expensive due to the non-native arithmetic of cryptographic operations. Folding schemes avoid this by never verifying a proof. Instead, they fold the instances themselves. This results in:

• Prover time: Dominated by field multiplications, not group exponentiations.
• Recursion overhead: Near-constant, rather than logarithmic or linear.
• Circuit size: The step circuit is just the computation itself, not a proof verifier.