Recursive proof composition without the abyss: Halo to Nova

The path from Halo's accumulation scheme to Nova's folding scheme, derived from the recurrence relation. Where Halo2, Nova, SuperNova, and HyperNova actually differ, and which one to reach for in 2026.

A recursive SNARK is a proof that proves another proof was checked correctly. A program that runs for $T$ steps and produces a proof of correct execution at each step can — recursively — collapse all $T$ proofs into one. The verifier work goes from $O(T)$ to $O(1)$ . This is the structural reason ZK rollups exist. It is also the reason “incrementally verifiable computation” stopped being a research curiosity in 2020 and became a deployment target.

The two papers that sit underneath every recursive SNARK shipped today are Halo (Bowe, Grigg, Hopwood 2019) and Nova (Kothapalli, Setty, Tzialla 2022). They take very different routes to the same destination. This post is the math of both, the trade-off table for picking one in 2026, and a Rust skeleton for the Nova folding step.

The problem recursive SNARKs are solving

You have a program that runs for $T$ steps. At each step you produce a proof that the step was executed correctly. Naively, the verifier checks all $T$ proofs — verifier cost $O(T)$ , no better than re-running the program. Useless.

The recursive trick: at step $i$ , instead of producing a fresh proof, you produce a proof that says “step $i$ was executed correctly, and the proof from step $i-1$ verifies.” The proof for step $i$ recursively absorbs the proof for step $i-1$ . After $T$ steps you have one proof; the verifier checks one proof; the cost is $O(1)$ in the program length.

The hardest part is making the inner verification cheap. If the verifier work for one proof is $V$ and you embed that work in the circuit for the next proof, you’ve blown up the prover cost by $V$ . Recursion is only useful if $V$ is constant or near-constant in the original circuit size — which is exactly what Groth16, Halo, and Nova all aim for in different ways.

flowchart LR
subgraph S0[Step 0]
  P0[execute step 0]
  P0 --> Pr0[proof pi_0]
end
subgraph S1[Step 1]
  P1[execute step 1] --> V1[verify pi_0]
  V1 --> Pr1[proof pi_1: 'step 1 ran AND pi_0 verified']
end
subgraph S2[Step 2]
  P2[execute step 2] --> V2[verify pi_1]
  V2 --> Pr2[proof pi_2: 'step 2 ran AND pi_1 verified']
end
Pr0 --> V1
Pr1 --> V2
Pr2 --> Final[final verifier checks ONE proof]
classDef step fill:#0a0a0a,stroke:#4ade80,color:#4ade80
class S0,S1,S2 step

The math problem reduces to one question: how cheaply can you verify a SNARK inside a SNARK?

The Halo trick: accumulation without recursion-in-circuit

Pre-Halo recursion required a cycle of pairing-friendly elliptic curves. Two curves $E_1, E_2$ with the property that the scalar field of $E_1$ is the base field of $E_2$ and vice versa, so that arithmetic over one curve can be expressed natively in the other curve’s circuit. Pasta (Pallas / Vesta) and MNT4/6 are the canonical cycles. The reason this matters: if you want to verify a Groth16 proof inside a Groth16 circuit, you need pairing-friendly arithmetic inside the circuit, which means the circuit field has to support the pairing curve. A cycle gives you two curves where each can verify proofs over the other.

The cycle constraint is annoying. Pasta’s curves don’t have efficient pairings (they’re cycle-friendly, not pairing-friendly), so they trade pairing efficiency for cycle availability. MNT cycles have very large fields and slow arithmetic. There’s no free lunch.

Halo (Bowe, Grigg, Hopwood 2019) was the first practical example of recursive proof composition that broke this constraint. The insight: instead of verifying the inner proof inside the circuit, you accumulate the most expensive part of the verification (the multiscalar multiplication, MSM) into a running sum, and defer the actual MSM check to the end of the recursion.

Formally: the verifier of an inner-product-argument-based proof has to check an equation of the form

\sum_i s_i \cdot G_i = P

for some derived scalars $s_i$ and group elements $G_i$ . This is the bottleneck — it’s a multiscalar multiplication of size linear in the circuit. The accumulation-scheme trick is: at step $k$ , instead of checking this equation, you produce a fresh “accumulator” $\text{acc}_k = (G_k^{\text{folded}}, P_k^{\text{folded}})$ that combines the current step’s MSM with the previous accumulator. After $T$ steps you have one accumulator and one MSM check. Verifier cost: $O(\log T)$ for the recursion plus one final MSM.

The Halo paper formalises this as a polynomial commitment with deferred opening. It works because the recursive composition can defer expensive arithmetic, not because it embeds full verification in-circuit. From the abstract:

We present Halo, the first practical example of recursive proof composition without a trusted setup, using only the discrete logarithm assumption over normal cycles of elliptic curves. Recursion is achieved by amortizing away the expensive verification procedures from within the proof verification cycle, deferring them until the end of the recursion.

Bowe, Grigg, Hopwood ↗ source

Halo2, the Zcash production deployment, uses the same construction over Pasta and ships it in Orchard (Zcash’s NU5 upgrade in 2022). Halo2 is also the basis of Aztec Connect, the Scroll zkEVM, and the Filecoin Snark-pack.

The Nova trick: folding instead of accumulating

Two years after Halo, Nova (Kothapalli, Setty, Tzialla 2022) reframed the problem entirely. Instead of accumulating an MSM, Nova introduces a folding scheme: a primitive that takes two instances of a relation and folds them into a single instance, with prover cost $O(|F|)$ for some step circuit $F$ and no SNARK at all in the recursion.

The Nova relation is a relaxed R1CS instance:

\mathbf{A} \mathbf{z} \circ \mathbf{B} \mathbf{z} = u \mathbf{C} \mathbf{z} + \mathbf{e}

where $\mathbf{A}, \mathbf{B}, \mathbf{C}$ are the constraint matrices, $\mathbf{z}$ is the witness extended with public inputs, $u$ is a slack scalar (1 in the standard R1CS case), and $\mathbf{e}$ is an error vector (zero in the standard case). The “relaxed” part is that $u$ and $\mathbf{e}$ are allowed to be nonzero — that’s what makes folding possible.

Given two relaxed R1CS instances $(u_1, \mathbf{z}_1, \mathbf{e}_1)$ and $(u_2, \mathbf{z}_2, \mathbf{e}_2)$ , the folding scheme produces a single instance $(u, \mathbf{z}, \mathbf{e})$ via a random challenge $r$ :

u = u_1 + r \cdot u_2, \quad \mathbf{z} = \mathbf{z}_1 + r \cdot \mathbf{z}_2, \quad \mathbf{e} = \mathbf{e}_1 + r \cdot \mathbf{T} + r^2 \cdot \mathbf{e}_2

with $\mathbf{T}$ a “cross-term” the prover sends to the verifier. The folded instance is satisfying iff both originals were (with overwhelming probability). Crucially, folding does not require the verifier to do any expensive cryptographic work: $\mathbf{T}$ is a vector commitment, $r$ is a Fiat-Shamir challenge, and the new $(u, \mathbf{z}, \mathbf{e})$ is a linear combination. No pairings. No SNARK.

The Nova incrementally verifiable computation (IVC) recurrence is then:

(u_{i+1}, \mathbf{z}_{i+1}, \mathbf{e}_{i+1}) = \text{Fold}\big( (u_i, \mathbf{z}_i, \mathbf{e}_i), \; (u_F, \mathbf{z}_F^{(i)}, \mathbf{0}) \big)

where the second instance is a fresh R1CS encoding of “step $i$ of the program $F$ executed correctly.” After $T$ steps, you have one relaxed R1CS instance, and you produce a single SNARK that proves it’s satisfying. The SNARK runs once, at the end. Every step in between is folding.

The cost asymmetry is the entire pitch. Halo’s per-step cost is $O(|F|)$ for the step plus $O(\log T)$ for the recursion. Nova’s per-step cost is just $O(|F|)$ — no recursion overhead. For long computations ( $T \gg 1$ ) Nova is significantly cheaper. The trade-off: Nova gives you one final SNARK to verify, while Halo gives you a SNARK at every step.

flowchart LR
subgraph N0[Nova step 0]
  F0[execute F at step 0] --> R0[R1CS instance z_0]
end
subgraph N1[Nova step 1]
  F1[execute F at step 1] --> R1[fresh R1CS z_1]
  Acc0[accumulator U_0] --> Fold1[fold]
  R1 --> Fold1
  Fold1 --> Acc1[accumulator U_1]
end
subgraph N2[Nova step 2]
  F2[execute F at step 2] --> R2[fresh R1CS z_2]
  Acc1 --> Fold2[fold]
  R2 --> Fold2
  Fold2 --> Acc2[accumulator U_2]
end
R0 --> Acc0
Acc2 --> SNARK[final SNARK proves U_T satisfying]
classDef step fill:#0a0a0a,stroke:#4ade80,color:#4ade80
class N0,N1,N2 step

The folding scheme is the entire idea. Everything else in Nova is bookkeeping around it.

Halo2, Nova, SuperNova, HyperNova — what’s the difference

Four production-grade recursive systems, four design points.

Option	Cost	Latency	Blast radius	Notes
Halo2 (Zcash, Pasta curves)	Per-step prover ~constant in T; verifier O(log T) MSM	Step proof ~5-15s for non-trivial circuits	Production since 2022 (Zcash NU5); audited	Best for protocols that already use the IPA / Pasta stack. Wide deployment.
Nova (Pallas/Vesta cycle)	Per-step prover O(\|F\|) with NO SNARK; one final SNARK	Per-step ~100ms-1s; final SNARK ~5-15s	Production via microsoft/Nova, Lurk; younger than Halo2	Best when T is very large and you can defer the SNARK. The right choice for a zkVM step circuit.
SuperNova	Per-step proportional to the SIZE of the invoked instruction circuit	Per-step ~50ms-300ms (varies by instruction)	Newer; production zkVMs (RISC0, Jolt-shape) are exploring it	Right answer for instruction-set machines (EVM, RISC-V) where steps don't all use the same circuit.
HyperNova (CCS)	Folds CCS instead of R1CS; supports Plonkish/AIR/R1CS uniformly	Comparable to Nova with a richer constraint system	Newest of the four; CRYPTO 2024	The unification target. Drop-in upgrade for protocols that want CCS flexibility without rewriting.
Plain Groth16 + cycle	Per-step verifier embedding ~10k constraints	Per-step ~10s+	What everyone did before Halo and Nova	Mostly historical now. Don't reach for this in 2026.

The two questions that decide which one to reach for in 2026:

Is your computation a uniform step that repeats, or a heterogeneous instruction set? Uniform: Nova. Heterogeneous: SuperNova. (HyperNova handles both via CCS.)
Do you need a SNARK at every step, or can you defer to one final SNARK? Every step: Halo2. Defer: Nova / SuperNova / HyperNova.

For a privacy-pool transfer, neither of these is the right shape — you want a single SNARK per spend, no recursion. For zera-sdk we ship Groth16 and don’t recurse. For a rollup settling many transfers in a batch, Nova-flavoured folding is the right structural answer because the per-step cost is dominated by the transfer logic and the final SNARK only runs once per epoch.

A Nova folding step, in Rust

The cleanest way to see what’s actually happening in a folding step is to write one out. The skeleton below is a Nova-shaped folding step over a toy R1CS — no pairings, no real curve, no soundness, but the linear-combination structure is the real thing.

Nova folding step (skeleton) [ rust ]

open

Runnable playground (requires JavaScript)

src/main.rs

// A Nova-shaped folding step over a toy "relaxed R1CS" instance.
// This is INTENTIONALLY toy-shaped: scalars are u128 mod a prime, the
// "commitment" is a hash, and there's no curve arithmetic. The shape of
// the linear combinations is real; the soundness is not.
//
// Reference: Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
// https://eprint.iacr.org/2021/370

const MODULUS: u128 = (1u128 << 61) - 1; // toy Mersenne prime

#[derive(Clone, Debug)]
struct RelaxedR1CS {
  /// Slack scalar: 1 for a fresh instance, accumulates after folding.
  u: u128,
  /// Witness extended with public inputs.
  z: Vec<u128>,
  /// Error vector: 0 for a fresh instance, accumulates after folding.
  e: Vec<u128>,
  /// Vector commitment to z. (Toy: just a checksum.)
  com_z: u128,
  /// Vector commitment to e.
  com_e: u128,
}

fn add(a: u128, b: u128) -> u128 { (a.wrapping_add(b)) % MODULUS }
fn mul(a: u128, b: u128) -> u128 { (a.wrapping_mul(b)) % MODULUS }
fn vec_add(a: &[u128], b: &[u128]) -> Vec<u128> {
  a.iter().zip(b.iter()).map(|(x, y)| add(*x, *y)).collect()
}
fn vec_scale(a: &[u128], s: u128) -> Vec<u128> {
  a.iter().map(|x| mul(*x, s)).collect()
}
// Toy "commitment": rolling hash. A real Nova uses Pedersen commitments.
fn commit(v: &[u128]) -> u128 {
  let mut h: u128 = 0xCAFE_BABE_DEAD_BEEF;
  for x in v {
      h = h.wrapping_mul(0x100000001b3).wrapping_add(*x);
  }
  h % MODULUS
}

/// Fold two relaxed R1CS instances into one, using random challenge r.
/// Returns the folded instance and the cross-term T (which the prover
/// sends to the verifier in a real protocol).
fn fold(
  inst1: &RelaxedR1CS,
  inst2: &RelaxedR1CS,
  r: u128,
) -> (RelaxedR1CS, Vec<u128>) {
  // Cross term T. In real Nova: T = Az_1 o Bz_2 + Az_2 o Bz_1
  //                                 - u_1 * C z_2 - u_2 * C z_1.
  // Toy: just a placeholder of the right shape.
  let len = inst1.e.len();
  let cross_term: Vec<u128> = (0..len)
      .map(|i| {
          let t1 = mul(inst1.u, inst2.z.get(i).copied().unwrap_or(0));
          let t2 = mul(inst2.u, inst1.z.get(i).copied().unwrap_or(0));
          add(t1, t2)
      })
      .collect();

  // Folded slack scalar: u = u_1 + r * u_2
  let u = add(inst1.u, mul(r, inst2.u));
  // Folded witness: z = z_1 + r * z_2
  let z = vec_add(&inst1.z, &vec_scale(&inst2.z, r));
  // Folded error: e = e_1 + r * T + r^2 * e_2
  let r2 = mul(r, r);
  let e = vec_add(
      &vec_add(&inst1.e, &vec_scale(&cross_term, r)),
      &vec_scale(&inst2.e, r2),
  );
  let folded = RelaxedR1CS {
      u,
      com_z: commit(&z),
      com_e: commit(&e),
      z,
      e,
  };
  (folded, cross_term)
}

fn fresh_instance(z: Vec<u128>) -> RelaxedR1CS {
  let e = vec![0u128; z.len()];
  let com_z = commit(&z);
  let com_e = commit(&e);
  RelaxedR1CS { u: 1, z, e, com_z, com_e }
}

fn main() {
  // Step 0: fresh instance with witness z_0.
  let acc = fresh_instance(vec![3, 5, 7, 11]);
  println!("step 0: u={}, |z|={}, com_z={:#x}", acc.u, acc.z.len(), acc.com_z);

  // Step 1: fold in a fresh R1CS instance from running F at step 1.
  let step1 = fresh_instance(vec![13, 17, 19, 23]);
  let r1: u128 = 0xDEADBEEF; // Fiat-Shamir challenge in real protocol
  let (acc, _t) = fold(&acc, &step1, r1);
  println!("step 1: u={}, com_z={:#x}, |e|={}", acc.u, acc.com_z, acc.e.len());

  // Step 2: fold in another step.
  let step2 = fresh_instance(vec![29, 31, 37, 41]);
  let r2: u128 = 0xFEEDFACE;
  let (acc, _t) = fold(&acc, &step2, r2);
  println!("step 2: u={}, com_z={:#x}", acc.u, acc.com_z);

  // After T steps, the final accumulator is one relaxed R1CS instance.
  // The protocol proves it's satisfying via a single SNARK at the end.
  println!("\nfinal accumulator captures all 3 steps in one instance.");
  println!("a SNARK proves this instance is satisfying — 1 proof for any T.");
}

Open this snippet on the Rust Playground

The shape is the thing. The fold is just three linear combinations: $u' = u_1 + r u_2$ , $\mathbf{z}' = \mathbf{z}_1 + r \mathbf{z}_2$ , $\mathbf{e}' = \mathbf{e}_1 + r \mathbf{T} + r^2 \mathbf{e}_2$ . The cross-term $\mathbf{T}$ is what the prover sends; the challenge $r$ is Fiat-Shamir over the transcript. In real Nova the witness $\mathbf{z}$ is replaced by a Pedersen commitment to it (so the verifier never sees the witness), and the error vector $\mathbf{e}$ is replaced by a commitment as well. The linear structure of the fold is preserved by the additive-homomorphic property of the Pedersen commitment, which is the entire reason Pedersen is the right primitive here.

Where this lands for ZERA

The honest answer about recursion in zera-sdk v1: we don’t use it. A privacy transfer is one Groth16 proof per spend, and there’s nothing to recurse over. The advantage of recursion shows up when:

You’re settling many transfers in a batch (rollup shape) and want to compress them into one proof.
You’re running a zkVM (Lurk, Jolt, RISC0) where the program has many uniform steps.
You’re building a light client that has to verify a long chain of proofs cheaply.

For ZERA’s transfer flow, none of these apply. For the eventual settlement layer that sits underneath a chain of ZERA transfers (think: a state-root proof every epoch), Nova-style folding is the right shape, and the design seam is in crates/zera-sdk-core/src/recursion.rs. Empty file today. We’ve left the door open.

The reason I wrote this post anyway is that recursion is the part of the ZK stack that’s most actively moving in 2026. HyperNova landed at CRYPTO 2024 with a CCS-based unification of R1CS / AIR / Plonkish that was supposed to take five more years. The next two years are going to compress IVC primitives down to “one folding scheme, three commitment choices, pick your poison.” Anyone deploying a ZK system today should know what shape that compressed primitive will be, because the migration cost will be the difference between a clean refactor and a rewrite.