As computational complexity in distributed systems expands to encompass entire blockchain histories or verifiable machine learning inferences involving billions of parameters, monolithic proofs become intractable. In 2008, Paul Valiant introduced Incrementally Verifiable Computation (IVC): a proof (pi_i) demonstrating that step (i) was executed correctly and that prior proof (pi_{i-1}) was valid. In this part, we examine the evolution from recursive SNARKs on Cycles of Elliptic Curves (Pasta) to Abhiram Kothapalli, Srinath Setty, and Riad Wahby’s revolutionary Nova Folding Scheme.
1. The Mechanics of Classical Recursive SNARKs
To prove step (i+1) recursively, an arithmetic circuit must execute the SNARK verification algorithm of step (i) inside its own constraints: ( ext{Verify}(vk, x_i, pi_i) = 1). However, an immediate algebraic obstacle emerges: The Field Mismatch Problem.
A SNARK over curve (E_1) has scalar field (mathbb{F}_q) and base field (mathbb{F}_p). The circuit computes over (mathbb{F}_q), but curve group operations inside the verifier require arithmetic over (mathbb{F}_p). Emulating non-native field arithmetic requires over 10,000 gates per multiplication.
The breakthrough solution was the discovery of Cycles of Elliptic Curves (e.g., the Pasta curves Pallas and Vesta):
[
#E_1(mathbb{F}_p) = q quad ext{and} quad #E_2(mathbb{F}_q) = p
]
By alternating between (E_1) and (E_2), each curve verifies the proof generated by the other with zero non-native arithmetic overhead, enabling systems like Mina Protocol and Zcash’s Halo2.
2. The Nova Folding Scheme: Eliminating Circuit Verifiers
Despite cycles of curves, verifying a full SNARK verifier inside an arithmetic circuit requires (sim 20,000) to (50,000) constraints at every step. In 2021, Nova shattered this bottleneck by introducing Folding Schemes.
Instead of generating and verifying a SNARK at every step, Nova folds two instances of the same problem into a single instance of identical size, deferring expensive cryptographic proofs to the very end of computation. Nova reformulates R1CS into Relaxed R1CS:
[
A z circ B z = u cdot C z + E
]
where (u in mathbb{F}) is a scalar slack variable and (E) is an error/slack vector. Given two relaxed instances ((u_1, x_1, E_1, W_1)) and ((u_2, x_2, E_2, W_2)) with commitments ((overline{E}_1, overline{W}_1)) and ((overline{E}_2, overline{W}_2)):
- The verifier sends random challenge (r leftarrow mathbb{F}_p).
- The cross-term vector (T) is computed:
[
T = A z_1 circ B z_2 + A z_2 circ B z_1 – u_1 C z_2 – u_2 C z_1
] - The prover folds witnesses using a simple linear combination:
[
W_{f} = W_1 + r W_2, quad E_{f} = E_1 + r T + r^2 E_2, quad u_{f} = u_1 + r u_2
]
The resulting folded instance ((u_f, x_f, E_f, W_f)) strictly satisfies the Relaxed R1CS relation! The verifier only performs two scalar-point multiplications to fold the commitments: (overline{W}_f = overline{W}_1 + [r]overline{W}_2). The entire recursive step overhead drops from 50,000 gates to under 2,000 gates, accelerating IVC by orders of magnitude.
3. HyperNova & Frontiers of Multi-Folding
While Nova folded R1CS (degree-2 gates), HyperNova (2023) generalized folding to high-degree, customizable constraints (Plonkish arithmetization) via multilinear polynomial sum-check protocols. By decoupling recursion from SNARK verification, folding schemes have established a new paradigm for scaling verifiable computing to arbitrary depths.
