Nova folding with nova-snark: a beginner's guide

Picture this: your program takes one million sequential steps to finish. Maybe it is a blockchain, a smart contract, or a scientific simulation. Now someone asks you: "How do I know it ran correctly?"

You could ask them to re-run the whole thing. That defeats the purpose. They would spend as much time verifying as you spent computing.

What if, instead, you could hand them a tiny piece of paper, a "proof," that they could check in a fraction of a second? That proof would mathematically guarantee that every single one of those million steps was executed correctly. And what if generating that proof did not require any expensive cryptography at each individual step, but only once at the very end?

That is the promise of Nova. The technique that makes it possible is called a folding scheme.

This guide teaches Nova folding from first principles. You will learn why it works, how to use it, and see real Rust code with the nova-snark library.

​Why proving long computations is so hard

Before we talk about Nova's solution, we need to understand the problem it solves. The problem is called Incrementally Verifiable Computation, or IVC for short.

​The million-step dilemma

Think of your computation as a treadmill. At each step, you are in some state, you process some input, and you transition to a new state. Let us call your step function $F$. You start at state $Z_0$, apply $F$ with input $\omega_1$ to get $Z_1$, then apply $F$ with $\omega_2$ to get $Z_2$, and so on:

$$Z_1 = F(Z_0, \omega_1)$$ $$Z_2 = F(Z_1, \omega_2)$$ $$\vdots$$ $$Z_n = F(Z_{n-1}, \omega_n)$$

Now you want to prove that $Z_n$ really is the correct result after $n$ steps. In classical zero-knowledge proof systems (SNARKs), you have two bad options.

Option A: one giant proof. You express the entire million-step computation as one massive arithmetic circuit, generate one proof, and hand it over. The problem? The circuit has millions of constraints. The memory required to hold the witness grows linearly with the number of steps. For large enough computations, your machine simply runs out of RAM.

Option B: prove step by step. At each step, you generate a proof that the step was correct and that the previous proof verified. This sounds elegant, but it hides a devastating cost. At every single step, you are proving the verification of a SNARK proof inside another SNARK circuit. This is called recursive SNARK verification, and it is expensive.

To understand just how expensive, we need to talk about bilinear pairings.

A bilinear pairing is a special mathematical operation that lives on elliptic curves. Think of an elliptic curve as a set of points with a very specific addition rule. A pairing is like a magical lens. It takes two points from one curve, shines them through the lens, and produces a number on a completely different mathematical object. The magic property is bilinearity: if you double one input point, the output doubles too.

Here is an everyday analogy. You have two colored flashlights, red and blue. Normally, shining them on a wall just makes a purple spot. But a "pairing lens" is special. The exact shade of purple encodes a mathematical relationship between the red and blue lights. Change the red light slightly, and the purple shifts in a perfectly predictable, linear way.

Modern SNARKs (like Groth16) use pairings to make verification extremely fast. The verifier just checks one pairing equation. Done.

The problem arises when you need to verify a pairing inside a circuit. Encoding a pairing as arithmetic constraints requires thousands of multiplication gates. Verifying a single pairing in-circuit can take roughly 52 seconds of proving time per step. For 1,000 steps, you are looking at hours of proving time just for the recursive overhead.

Nova avoids pairings entirely for its recursive steps. That is a huge part of why it is so fast.

​What about Halo and accumulation?

The cryptocurrency community knew this was a problem. Around 2019, the Halo protocol introduced an idea called accumulation. Instead of fully verifying the previous proof at each step, Halo deferred the expensive part (polynomial evaluations) to the end. It accumulated the "hard work" in a running aggregate and only checked it once.

This helped, but Halo still generated a full SNARK proof at every step. The prover still did the hard crypto work 1,000 times.

What the field needed was a way to defer not just part of the verification, but the entire proof generation itself. A way to combine computational steps together cheaply, without any expensive cryptography, and only generate a proof at the very end.

That way is called folding.

---

​The big idea: folding, explained with receipts

Let us step away from cryptography and think about something mundane: receipts.

You are a freelancer who completes 1,000 small tasks for a client. At the end of the month, the client wants proof that you did all the work. Here are three ways you could handle it.

The naive way. You hand over 1,000 individual receipts. The client must examine every single one. This is slow and tedious. This is like Option A above: re-executing the whole computation.

The notarized way. After every task, you visit a notary who stamps a certificate saying "task $i$ is complete, and the certificate for task $i-1$ is valid." After 1,000 tasks, you have 1,000 notarized certificates. The client checks the last one. This works, but you visited the notary 1,000 times. The notary is expensive. This is like recursive SNARKs.

The Nova way. You keep a running summary log. After task 1, you write a summary of task 1. After task 2, you fold the summary of task 2 into the same log. The log stays the same size. You repeat this 1,000 times. The log never grows. At the end, you visit the notary once. The notary checks the log and says, "If this log is valid, all 1,000 tasks were done correctly." This is folding.

That is the core intuition. Folding is a way to take two "instances" of a computation and merge them into one instance of the same size. Proving the merged instance is equivalent to proving both original instances.

The diagram above shows this contrast visually. The top row is the traditional approach. Every step generates a new proof, and the chain of proofs grows heavier. The bottom row is Nova. Each step folds into a running accumulator that stays the same size, and you only generate one proof at the end.

---

​The math that makes folding work

Now let us peek under the hood. Do not worry. We will build up slowly, using analogies for every mathematical concept before showing the real notation.

​Step 1: how computers represent math (R1CS)

Before Nova can fold anything, it needs the computation expressed in a form it understands. That form is called a Rank-1 Constraint System, or R1CS.

Think of R1CS as a very strict kind of spreadsheet. Your computation breaks down into a series of equations where each equation has the exact same shape:

$$(A \cdot z) \circ (B \cdot z) = C \cdot z$$

Let us decode this.

• $A$, $B$, and $C$ are fixed matrices. They define the "shape" of your computation. Think of them as the blueprint of a factory assembly line.
• $z$ is a vector that contains everything: your public inputs, your public outputs, and your secret witness values. Think of $z$ as a shipping manifest.
• $\circ$ means "multiply element by element." If you have two columns of numbers, you multiply the first number in column one by the first number in column two, the second by the second, and so on.
• The dot $\cdot$ means normal matrix-vector multiplication.

So the equation says four things. First, take the manifest $z$ and run it through blueprint $A$. That gives you one column of numbers. Then run $z$ through blueprint $B$ for a second column. Multiply those two columns element by element. The result should match what you get from blueprint $C$.

Every step of your IVC computation uses the same blueprints ($A$, $B$, $C$) but with a different manifest ($z$). The inputs and outputs change at each step.

​Step 2: why you cannot just add two R1CS instances

Here is where things get interesting. Suppose you have two steps of your computation, each with its own manifest $z_1$ and $z_2$. You want to fold them together. The most natural idea is to take a random linear combination:

$$z = z_1 + r \cdot z_2$$

where $r$ is a random number chosen by the verifier. This is like saying, "Instead of checking both receipts separately, let me check one combined receipt."

The problem? R1CS is quadratic. Substitute $z = z_1 + r \cdot z_2$ into the R1CS equation. The left-hand side expands into a mess:

$$(A \cdot z_1 + r \cdot A \cdot z_2) \circ (B \cdot z_1 + r \cdot B \cdot z_2)$$

When you multiply this out, you get three terms:

$$(A \cdot z_1) \circ (B \cdot z_1) + r \cdot \big[(A \cdot z_1) \circ (B \cdot z_2) + (A \cdot z_2) \circ (B \cdot z_1)\big] + r^2 \cdot (A \cdot z_2) \circ (B \cdot z_2)$$

This is a disaster for three reasons.

1. The cross term. The middle chunk, $(A \cdot z_1) \circ (B \cdot z_2) + (A \cdot z_2) \circ (B \cdot z_1)$, has no business being there. R1CS only allows $A \circ B = C$, not mixed products.

2. The squared randomness. We have $r^2$ multiplying the second instance, but the right-hand side of R1CS would only give us $r$. The degrees do not match.

3. The constant term. In R1CS, the first entry of $z$ is always $1$. But $1 + r \cdot 1 = 1 + r$, which is not $1$ anymore.

So standard R1CS is not "closed" under random linear combinations. You cannot fold two standard R1CS instances into another standard R1CS instance.

​Step 3: just relax (introducing Relaxed R1CS)

Nova's authors had a brilliant insight. What if we loosen the rules of R1CS just enough to absorb those extra terms?

They introduced Relaxed R1CS, which changes the equation to:

$$(A \cdot z) \circ (B \cdot z) = u \cdot (C \cdot z) + E$$

Two new ingredients appear.

• $u$ is a scalar, just a single number. It replaces the fixed constant $1$ at the beginning of $z$. Think of $u$ as a scaling factor that can stretch or shrink the right-hand side.
• $E$ is an error vector (also called a "slack vector"). It is a column of numbers whose sole job is to soak up the extra terms that appear during folding.

Here is the beautiful part. Standard R1CS is just a special case of Relaxed R1CS. If you set $u = 1$ and $E = 0$, you get the original equation back. So Relaxed R1CS is strictly more general.

​Step 4: the folding operation

Now we can fold. Given two Relaxed R1CS instances:

• Instance 1: $(u_1, E_1, x_1, W_1)$ with manifest $z_1 = (u_1, x_1, W_1)$
• Instance 2: $(u_2, E_2, x_2, W_2)$ with manifest $z_2 = (u_2, x_2, W_2)$

The verifier picks a random challenge $r$. Both parties compute the folded instance:

$$u = u_1 + r \cdot u_2$$ $$x = x_1 + r \cdot x_2$$ $$W = W_1 + r \cdot W_2$$ $$E = E_1 + r \cdot T + r^2 \cdot E_2$$

What is the cross-term?

The value $T$ is the cross-term:

$$T = (A \cdot z_1) \circ (B \cdot z_2) + (A \cdot z_2) \circ (B \cdot z_1) - u_1 \cdot (C \cdot z_2) - u_2 \cdot (C \cdot z_1)$$

Why this works

Work through the algebra and you will see: if the folded instance satisfies Relaxed R1CS, both original instances must have been valid. The Nova paper proves this rigorously. The error vector $E$ has done its job. It absorbed the cross terms and the $r^2$ coefficient.

The key takeaway: two instances become one. The new instance is the same size as either original. No blow-up. No growth.

​Step 5: hiding the witness with commitments

There is one remaining problem. In the folding operation above, the verifier needs to know $E$ to check the equation. But $E$ depends on the secret witnesses $W_1$ and $W_2$. If the prover just sends $E$ in the clear, there is no zero-knowledge. The verifier learns the secrets.

Nova solves this using commitments. A commitment is like a sealed envelope. You put a value inside, seal it, and send the envelope to someone. They cannot see what is inside (hiding). You cannot change what is inside after sealing (binding).

But what kind of envelope are we talking about? Let us open one.

Inside a Pedersen commitment

A Pedersen commitment is a specific kind of sealed packet built from elliptic curve points. Here is how it works in plain terms.

Think of an elliptic curve as a special set of points on a graph. There are two publicly known "base points" on this curve, called $G$ and $H$. To commit to a secret number $s$, you do the following:

1. Pick a random "blinding factor" $r$.
2. Compute $C = s \cdot G + r \cdot H$.

The result $C$ is a point on the curve. It is your commitment.

Why is this safe? Because of the elliptic curve discrete logarithm problem. Finding $s$ from $C$ is like being handed the result of a massive multiplication and being asked to figure out what you started with. No one knows how to do this efficiently, not even with a quantum computer (for well-chosen curves).

Why is it binding? Because finding two different pairs $(s, r)$ and $(s', r')$ that produce the same $C$ would also solve the discrete logarithm problem. You are locked into your original values.

Now for the magical part. Pedersen commitments are additively homomorphic. This means:

$$\text{Commit}(a + b) = \text{Commit}(a) + \text{Commit}(b)$$

Think of it like sealed packets that can be added together without being opened. If I have a packet containing $5$ and you have a packet containing $3$, we can create a packet containing $8$ without either of us opening ours. The arithmetic happens on the outside of the packets.

In the folding protocol:

1. The prover computes the cross-term $T$ and sends a commitment to it, $\overline{T}$.
2. The verifier picks $r$ (or it is derived deterministically via the Fiat-Shamir heuristic).
3. Both parties compute the folded commitments using only the homomorphic property:

$$\overline{E}_{\text{folded}} = \overline{E}_1 + r \cdot \overline{T} + r^2 \cdot \overline{E}_2$$ $$\overline{W}_{\text{folded}} = \overline{W}_1 + r \cdot \overline{W}_2$$

The verifier never sees the witnesses. They only see commitments, constant-sized values, and do simple arithmetic on them.

​Step 6: making it non-interactive (Fiat-Shamir)

In the interactive version of the protocol, the verifier sends a random $r$ after seeing the commitment to $T$. But in practice, we want a non-interactive protocol where the prover can generate everything in one go, without waiting for a verifier to respond.

The Fiat-Shamir transform achieves this. Here is the idea in simple terms.

Think of a game of rock-paper-scissors played through the mail. Normally, Alice sends her move, Bob sees it, then Bob replies with his move. But Bob could cheat by waiting to see Alice's move first. To fix this, they use a commitment. Alice writes her move on paper, locks it in a box, and sends the box to Bob. Bob sends his move in the open. Then Alice sends the key. Bob can verify Alice did not change her move, because the box was already in transit.

The Fiat-Shamir transform does something conceptually similar. Instead of the verifier picking $r$ randomly and sending it, the prover computes $r$ by running a hash function over all the public information so far:

$$r = \text{Hash}(\overline{T}, \text{public\_inputs})$$

Think of a hash function as a random oracle, a theoretical perfect randomness generator. Feed it any input, and it spits out a number that looks completely random. Feed it the same input twice, and you get the exact same number. Crucially, there is no way to predict the output without actually running the hash function.

So the prover "locks in" the challenge $r$ by deriving it from the public data. The verifier, looking at the same public data later, can recompute the exact same $r$. There is no back-and-forth needed. The prover can now generate the entire folded instance in a single message.

Because the hash function behaves like a random oracle, the result is just as safe as a randomly picked $r$. The prover cannot cheat by choosing favorable data, because any change to the public inputs would unpredictably change $r$.

---

​From folding to incrementally verifiable computation

So far we have learned how to fold two instances into one. But IVC requires folding thousands of sequential steps. How does Nova bridge this gap?

​The augmented function

At each step of IVC, Nova does not just run your step function $F$. It runs an augmented function $F'$ that does two things simultaneously:

1. It executes your actual step: $Z_{i+1} = F(Z_i, \omega_i)$.
2. It runs the folding verifier. It takes the accumulated instance $U_{\text{acc},i}$ (which represents all previous steps folded together) and folds it with the current step's instance $u_i$ to produce $U_{\text{acc},i+1}$.

At every step, the prover makes two claims. First, step $i$ executed correctly. Second, the history of all prior steps was folded correctly into the new accumulator.

​Two instances at every step

At step $i$, Nova maintains:

1. The running accumulator $U_{\text{acc},i}$: a Relaxed R1CS instance that encodes the folded history of steps $1$ through $i-1$.
2. The current step instance $u_i$: a standard R1CS instance ($u = 1$, $E = 0$) that encodes the execution of $F'$ at step $i$.

The folding scheme combines them:

$$U_{\text{acc},i+1} = \text{Fold}(U_{\text{acc},i}, u_i)$$

The accumulator never grows. It is the same size at step 1 as it is at step 1,000,000.

​The hash trick (avoiding a time paradox)

There is a subtle circularity problem. The output of $F'$ includes $U_{\text{acc},i+1}$. But $U_{\text{acc},i+1}$ is also part of the public input to the next step's instance $u_{i+1}$. This means $U_{\text{acc},i+1}$ would need to be folded into itself, creating a logical loop.

The circularity problem

If the accumulator were passed directly into the next step, the circuit would try to prove something about itself. That is a paradox.

How the hash breaks the loop

Nova breaks this loop using a collision-resistant hash. Instead of outputting $U_{\text{acc},i+1}$ directly, $F'$ outputs:

$$u_i.x = \text{Hash}(i, Z_0, Z_i, U_{\text{acc},i})$$

The next step uses this hash as its public input. Because finding two different inputs that produce the same hash output is computationally infeasible, the hash acts as an unforgeable fingerprint. The circuit can verify the hash without needing to fold the full accumulator into itself.

​Proving and verifying the IVC chain

After $n$ steps, the prover holds:

• The final accumulator $U_{\text{acc},n}$ and its secret witness
• The final step instance $u_n$ and its secret witness

The verifier checks four things:

1. Does $U_{\text{acc},n}$ satisfy the Relaxed R1CS equation?
2. Does $u_n$ satisfy the standard R1CS equation (with $u = 1$ and $E = 0$)?
3. Does $u_n.x$ equal $\text{Hash}(n, Z_0, Z_n, U_{\text{acc},n})$?
4. Are the commitments in $U_{\text{acc},n}$ valid?

If all four checks pass, the verifier is convinced that all $n$ steps were executed correctly.

​Wait, is the IVC proof small?

Not yet. The IVC proof described above contains the full witnesses for the accumulator and the final step. The witness size grows with the number of steps, so this proof is not small.

To fix this, Nova wraps the IVC proof in a proper zkSNARK. The prover generates a SNARK proving: "I know a valid IVC proof $\Pi$ such that $\text{IVC.V}(vk, n, Z_0, Z_n, \Pi) = 1$."

Nova uses a variant of Spartan for this compression. Spartan is a SNARK that does not require a trusted setup and has a fast prover. There are two variants:

• Standard Spartan: the verifier time depends on the circuit size.
• MicroSpartan (from the MicroNova paper): uses preprocessing so the verifier time is constant, regardless of circuit size.

Before compression, the IVC proof is folded with a random instance to achieve zero-knowledge. This technique comes from the HyperNova paper.

---

​Building with nova-snark: a hands-on tour

Now that you understand why folding works, let us see how to actually build with it.

​What is nova-snark?

nova-snark is the reference Rust implementation of Nova, maintained by Microsoft Research. At the time of writing, the latest version is 0.71.1. It is a production-grade library that handles all the cryptographic details (elliptic curve arithmetic, commitment schemes, the folding protocol, and Spartan compression) while exposing a relatively simple API for circuit authors.

The library is organized into several modules:

Module	Purpose
nova	The IVC scheme and folding scheme core
frontend	Bellman-style circuit construction (think: Lego blocks for constraints)
r1cs	R1CS types and the folding scheme for Relaxed R1CS
spartan	SNARK compression (RelaxedR1CSSNARK)
provider	Elliptic curve implementations (Pallas/Vesta, BN254/Grumpkin, secp/secq)
gadgets	Reusable circuit building blocks
traits	Core abstractions you will implement

​Adding nova-snark to your project

In your Cargo.toml:

[dependencies]
nova-snark = "0.71"
ff = "0.13"
num-bigint = "0.4"

Feature flags to know about:

Feature	What it does
io (default)	Lets you load commitment keys from Powers of Tau ceremony files
evm	Enables serialization formats friendly to Ethereum smart contracts
experimental	Enables bleeding-edge features like NeutronNova
test-utils	Insecure random setup for testing only. Never use in production.

​The StepCircuit trait

Once nova-snark is in your project, the first thing you build is a step circuit. This is the Rust representation of your step function $F$.

You implement the StepCircuit trait:

pub trait StepCircuit<F: PrimeField> {
    fn arity(&self) -> usize;
    
    fn synthesize<CS: ConstraintSystem<F>>(
        &self,
        cs: &mut CS,
        z: &[AllocatedNum<F>],
    ) -> Result<Vec<AllocatedNum<F>>, SynthesisError>;
}

Two methods:

1. arity() returns how many field elements your state vector contains. If your state is a pair of numbers $(x, y)$, arity is 2.

2. synthesize() is where you describe the constraints for one step. You receive the current state z and return the next state. Inside this function, you use cs.enforce() to add constraints.

​A concrete example: the MinRoot VDF

To see what a real step circuit looks like, let us walk through MinRoot, the canonical example from the Nova repository. MinRoot is a verifiable delay function (VDF). A VDF is a computation that is deliberately slow to execute but fast to verify. MinRoot works by repeatedly computing fifth roots in a finite field.

Here is the step circuit, simplified for clarity:

#[derive(Clone, Debug)]
struct MinRootCircuit<G: Group> {
    seq: Vec<MinRootIteration<G>>,  // Precomputed advice for each iteration
}

impl<G: Group> StepCircuit<G::Scalar> for MinRootCircuit<G> {
    fn arity(&self) -> usize { 2 }
    
    fn synthesize<CS: ConstraintSystem<G::Scalar>>(
        &self,
        cs: &mut CS,
        z: &[AllocatedNum<G::Scalar>],
    ) -> Result<Vec<AllocatedNum<G::Scalar>>, SynthesisError> {
        let mut x_i = z[0].clone();
        let mut y_i = z[1].clone();
        
        for i in 0..self.seq.len() {
            // We precomputed the fifth root outside the circuit.
            // Now we allocate it as "advice" -- a hint that the prover provides.
            let x_i_plus_1 = AllocatedNum::alloc(
                cs.namespace(|| format!("x_i_plus_1_iter_{i}")),
                || Ok(self.seq[i].x_i_plus_1)
            )?;
            
            // Constraint: x_i_plus_1^5 = x_i + y_i
            // We check this by computing x_i_plus_1^4 and then multiplying by x_i_plus_1 again.
            let sq = x_i_plus_1.square(cs.namespace(|| "sq"))?;
            let quad = sq.square(cs.namespace(|| "quad"))?;
            
            cs.enforce(
                || "x_i_plus_1^5 = x_i + y_i",
                |lc| lc + quad.get_variable(),      // left: x_i_plus_1^4
                |lc| lc + x_i_plus_1.get_variable(), // middle: x_i_plus_1
                |lc| lc + x_i.get_variable() + y_i.get_variable(), // right: x_i + y_i
            );
            
            // Update state for next iteration
            y_i = x_i;
            x_i = x_i_plus_1;
        }
        
        Ok(vec![x_i, y_i])
    }
}

Notice a critical pattern here: compute outside, constrain inside.

The prover computes the fifth root $x_{i+1} = (x_i + y_i)^{1/5}$ using normal Rust arithmetic outside the circuit. Then, inside the circuit, they constrain the relationship: $x_{i+1}^5 = x_i + y_i$. The circuit never directly computes the fifth root (which would be expensive in constraints). It only verifies that the prover's claimed value is correct.

This pattern, allocating advice and then constraining it, is the bread and butter of circuit design.

​Choosing your curve cycle

Nova runs over a cycle of elliptic curves. One curve handles your step circuit. The other handles the verifier circuit. The cycle enables efficient recursion because arithmetic on one curve is efficient to verify in constraints over the other curve.

nova-snark supports three curve cycles:

1. Pallas / Vesta (no trusted setup needed)

   • Best for: general-purpose applications where you want simplicity.
   • Commitment: Pedersen + IPA (Inner Product Argument).
   • Trade-off: proof sizes are larger than KZG-based schemes.

2. BN254 / Grumpkin (EVM-friendly)

   • Best for: applications that need to verify proofs on Ethereum.
   • Commitment: HyperKZG or Mercury (both require Powers of Tau ceremony).
   • Trade-off: requires a trusted setup, but proofs are smaller.

3. secp / secq

   • An alternative cycle with different security properties.

Here is how you configure the BN254/Grumpkin cycle with HyperKZG:

type E1 = Bn256EngineKZG;   // Primary curve
type E2 = GrumpkinEngine;   // Secondary curve
type EE1 = nova_snark::provider::hyperkzg::EvaluationEngine<E1>;
type EE2 = nova_snark::provider::ipa_pc::EvaluationEngine<E2>;
type S1 = nova_snark::spartan::snark::RelaxedR1CSSNARK<E1, EE1>;
type S2 = nova_snark::spartan::snark::RelaxedR1CSSNARK<E2, EE2>;

Understanding IPA and the Powers of Tau

When you read "Pedersen + IPA" above, you might wonder what IPA actually does. Let us unpack both commitment styles.

The Inner Product Argument (IPA) is a way to prove that a commitment contains the correct data without revealing the data itself. Think of a long grocery list. You want to prove to a friend that the total cost is exactly $100 without showing them the list. IPA works by repeatedly halving the list. You split it in half, commit to each half, and your friend picks one half at random. You repeat this process log(n) times until you are down to a single item. At each step, the commitments get smaller. Your friend is convinced because the probability that you could cheat across all those random challenges is astronomically small.

IPA produces proofs whose size grows logarithmically with the amount of data. It is simple and does not require any trusted setup. The trade-off is that verification takes logarithmic time, not constant time.

HyperKZG, used with BN254/Grumpkin, takes a different approach. It uses polynomial commitments where the proof is constant-sized and verification is constant-time. But this magic requires a trusted setup.

A trusted setup is a one-time ceremony where multiple participants collectively generate a set of public parameters. The security guarantee is elegant: as long as at least one participant was honest and destroyed their secret randomness, the setup is safe forever. The specific parameters generated are called the Powers of Tau.

Think of Powers of Tau like a communal recipe book. In the ceremony, each participant adds a secret ingredient to the book, then passes it along. No single participant knows all the ingredients. The final book can be used by anyone to create or verify proofs, but no one can forge a proof because no one knows the full recipe inside the book.

For production deployments, you should use parameters from an established ceremony like the Ethereum Perpetual Powers of Tau. For testing, nova-snark provides a test-utils feature that generates fake parameters. As the name implies, these are completely insecure and must never be used in production.

​Setting up public parameters

With your curve cycle chosen, the next step is setup. Before you can prove anything, Nova needs to set up public parameters based on your circuit structure:

let pp = PublicParams::<E1, E2, MinRootCircuit<<E1 as Engine>::GE>>::setup(
    &circuit,
    &*S1::ck_floor(),
    &*S2::ck_floor(),
).unwrap();

This step analyzes your circuit, determines the commitment key sizes, and prepares the parameters. It is a one-time cost per circuit.

​Running the IVC prover

With public parameters in hand, you create the recursive SNARK and step through your computation:

// Start with the initial state z0 and the first step circuit
let mut recursive_snark = RecursiveSNARK::<E1, E2, C>::new(
    &pp, &circuits[0], &z0
).unwrap();

// For each subsequent step, fold it into the accumulator
for (i, circuit) in circuits.iter().enumerate().skip(1) {
    recursive_snark.prove_step(&pp, circuit).unwrap();
}

At each prove_step, Nova:

1. Executes the step circuit to get the new state.
2. Computes the cross-term $T$.
3. Derives the random challenge $r$ via Fiat-Shamir.
4. Updates the accumulated instance and witness.

No SNARK proof is generated during these steps. Only commitments and linear combinations are performed. This is why Nova is so fast.

​Verifying the recursive SNARK

Verification is a single call:

recursive_snark.verify(&pp, num_steps, &z0).unwrap();

This checks the final accumulated instance and the final step instance, including the hash chain consistency. It does not re-execute any steps.

​Compressing with Spartan

The recursive SNARK is fast to generate and verify, but it is not zero-knowledge and not fully succinct. For deployment, you compress it:

// Setup compression keys
let (pk, vk) = CompressedSNARK::<_, _, _, S1, S2>::setup(&pp).unwrap();

// Generate the compressed proof
let compressed_snark = CompressedSNARK::prove(&pp, &pk, &recursive_snark).unwrap();

// Verify the compressed proof
compressed_snark.verify(&vk, num_steps, &z0).unwrap();

The compressed SNARK is small, zero-knowledge, and has constant verification time. This is what you would post to a blockchain or send to a client.

---

​Worked example: folding two R1CS instances by hand

To really cement the intuition, let us walk through a tiny numerical example of folding. This is adapted from the excellent "Nova by Hand" notes by the Privacy Scaling Explorations team.

Suppose we have a trivial R1CS with $A = [0, 1, 0]$, $B = [0, 1, 0]$, $C = [0, 0, 1]$. The equation is:

$$(A \cdot z) \circ (B \cdot z) = C \cdot z$$

For our two instances:

Instance 1: $z_1 = [1, 5, 25]$, so $A \cdot z_1 = 5$, $B \cdot z_1 = 5$, $C \cdot z_1 = 25$. Check: $5 \times 5 = 25$. Valid.

Instance 2: $z_2 = [1, 3, 6]$, so $A \cdot z_2 = 3$, $B \cdot z_2 = 3$, $C \cdot z_2 = 6$. Check: $3 \times 3 = 9 \neq 6$. Wait, let us adjust: $B = [2, 0, 0]$, so $B \cdot z_2 = 2$. Then $3 \times 2 = 6$. Valid.

Now the verifier picks $r = 2$. We fold:

$$A_{\text{folded}} = A \cdot z_1 + r \cdot A \cdot z_2 = 5 + 2 \cdot 3 = 11$$ $$B_{\text{folded}} = B \cdot z_1 + r \cdot B \cdot z_2 = 5 + 2 \cdot 2 = 9$$ $$C_{\text{folded}} = C \cdot z_1 + r \cdot C \cdot z_2 = 25 + 2 \cdot 6 = 37$$

If we naively check $A_{\text{folded}} \times B_{\text{folded}} = C_{\text{folded}}$, we get $11 \times 9 = 99$, but $C_{\text{folded}} = 37$. They do not match. This confirms that standard R1CS cannot be folded directly.

Now let us use Relaxed R1CS. We set $u_1 = 1$, $E_1 = 0$ and $u_2 = 1$, $E_2 = 0$.

Compute the cross-term:

$$T = (A \cdot z_1)(B \cdot z_2) + (A \cdot z_2)(B \cdot z_1) - u_1(C \cdot z_2) - u_2(C \cdot z_1)$$ $$T = (5)(2) + (3)(5) - (1)(6) - (1)(25) = 10 + 15 - 6 - 25 = -6$$

Compute the folded scalar and error:

$$u = u_1 + r \cdot u_2 = 1 + 2 \cdot 1 = 3$$ $$E = E_1 + r \cdot T + r^2 \cdot E_2 = 0 + 2 \cdot (-6) + 4 \cdot 0 = -12$$

Now check the Relaxed R1CS equation:

$$A_{\text{folded}} \times B_{\text{folded}} = 11 \times 9 = 99$$ $$u \cdot C_{\text{folded}} + E = 3 \cdot 37 + (-12) = 111 - 12 = 99$$

They match. The folded instance is valid, which means both original instances were valid. Folding works.

---

​Best practices and common pitfalls

As you start building with Nova, here are some hard-won lessons from the community.

Do make your step circuits meaningfully large. If your step circuit is tiny, say a single CPU instruction, the overhead of the recursive verifier circuit will dominate your costs. Folding shines when each step does substantial work. Aim for step circuits that are significantly larger than the ~10,000-gate verifier circuit.

Do use offline memory checking for zkVMs. If you are building a virtual machine with Nova, memory operations are a major cost. Do not use Merkle trees inside the circuit. They require thousands of hash constraints per memory access. Instead, use offline memory checking with multiset hashes. The Nebula paper (2024) shows how to adapt this technique specifically for folding-based systems.

Do choose your curve cycle based on your deployment target. If you need to verify proofs in an Ethereum smart contract, use BN254/Grumpkin with HyperKZG. If you want the simplest possible setup with no trusted ceremony, use Pallas/Vesta with Pedersen commitments.

Do run benchmarks in release mode. The underlying curve library uses assembly optimizations that provide up to 50% speedups. Always use cargo run --release or cargo test --release.

Do not use test-utils in production. This feature generates random Powers of Tau parameters, which are completely insecure. For production, download parameters from an established ceremony like the Ethereum Perpetual Powers of Tau.

Do not build universal circuits that pay for every instruction. If your VM has 100 possible instructions but each step only uses one, a universal circuit that encodes all 100 is wasteful. Research non-uniform IVC techniques (SuperNova, NeutronNova) if your step function varies.

---

​Where to go from here

You now have a solid conceptual foundation and a practical understanding of how to use nova-snark. Here are the natural next steps.

Read the Nova paper. The original paper by Kothapalli, Setty, and Tzialla (CRYPTO 2022) is remarkably accessible. It walks through the security proofs and formal definitions with clarity. eprint.iacr.org/2021/370

Work through "Nova by Hand." The Privacy Scaling Explorations team maintains a step-by-step mathematical walkthrough that derives every equation from scratch. It is the perfect companion to this guide. github.com/privacy-scaling-explorations/nova-by-hand

Study the MinRoot example in the Nova repo. Run it. Modify it. Add more iterations per step. Profile it. There is no substitute for hands-on experimentation.

Explore the folding scheme family. Nova was the first, but the field has exploded since then. SuperNova generalizes IVC to non-uniform step functions. HyperNova introduces Customizable Constraint Systems (CCS) and works with sum-check protocols. NeutronNova offers the best asymptotic efficiency and handles complex statements like VM executions. LatticeFold brings folding into the post-quantum realm using lattice cryptography.

---

​Sources

1. Kothapalli, A., Setty, S., & Tzialla, I. (2022). "Nova: Recursive Zero-Knowledge Arguments from Folding Schemes." CRYPTO 2022. eprint.iacr.org/2021/370

2. Nguyen, W., Boneh, D., & Setty, S. (2023). "Revisiting the Nova Proof System on a Cycle of Curves." IACR ePrint 2023/969.

3. Zhao, J., Setty, S., Cui, W., & Zaverucha, G. (2025). "MicroNova: Folding-based arguments with efficient (on-chain) verification." IEEE S&P 2025.

4. Kothapalli, A., & Setty, S. (2024). "HyperNova: Recursive arguments for customizable constraint systems." CRYPTO 2024.

5. Microsoft Research. "nova-snark: High-speed recursive arguments from folding schemes." github.com/microsoft/Nova

6. Privacy Scaling Explorations. "Nova by Hand: Notes on the Nova folding scheme explained from scratch." github.com/privacy-scaling-explorations/nova-by-hand

7. Veridise. "Intro to Nova & ZK Folding Schemes" (four-part blog series). veridise.com/blog

8. LambdaClass. "Incrementally verifiable computation: NOVA." blog.lambdaclass.com

9. 0xrafal. "Nova Folding and Recursive Proofs." 0xrafal Substack, 2024.

10. Srinath Setty. "Folding Schemes: Why they matter and how they are not employed in the best way possible." HackMD, 2025.

11. Berkeley RDI. "ZKP MOOC Lecture 10: Recursive SNARKs." rdi.berkeley.edu/zkp-course