LibraryPrivacy2021Design paperCorpus record
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Nova. Abhiram Kothapalli, Srinath Setty and Ioanna Tzialla.
Incrementally verifiable computation without putting a SNARK inside a SNARK. A folding scheme compresses two instances of a computation into one instance of the same size. Repeating that fold is the recursion. The paper is about prover cost, not about a chain.
Nova proves a long computation by folding each step into a single instance, instead of verifying a SNARK inside another SNARK. The folding scheme is the primitive. Recursion is what you get by repeating it. There is no trusted setup in the construction the paper gives.
- Evidence
- Primary paper
- Re-measured
- No
- Assumptions
- 4
- Records linked
- 3
Code
Source, repository, and what is actually hosted
- ePrint 2021/370https://eprint.iacr.org/2021/370
- The source URL is not a GitHub repository. No code remote is invented.
- Full text is not mirrored. Public availability is not a licence to copy the file onto this site.
- Add to a reading list
01 Claim ledger
What the paper is allowed to say
Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.
Claim 01 · Paper model
Folding, not a SNARK cycle
Two instances become one instance of the same size. The prover does not produce a full succinct proof at every step. That is the cost claim.
Claim 02 · Paper model
Relaxed R1CS
The paper folds a particular generalisation of rank-1 constraint systems. A computation that is not written in that form is not yet a Nova statement.
Claim 03 · Paper model
Constant overhead
The extra circuit work per step is constant and, in the paper, dominated by two group scalar multiplications. Constant does not mean negligible for a tiny step. It means it does not grow with the number of steps.
Claim 04 · Paper model
No FFT, no setup
The construction is designed to avoid a structured reference string and to avoid fast Fourier transforms. Those are reasons an implementer might choose it over a recursive SNARK. They are not reasons to skip the cryptographic assumptions.
02 Three cuts
Observation, model, falsifier
A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.
01 Folding, not a SNARK cycle
Observation
What the study says
Two instances become one instance of the same size. The prover does not produce a full succinct proof at every step. That is the cost claim.
Model
What has to hold
The cycle of curves, if the implementation uses one, matches what the proof needs. The paper discusses this. An arbitrary curve pair is not automatically sound.
Falsifier
What would retire it
Does each step verify a SNARK, or fold an instance?
02 Relaxed R1CS
Observation
What the study says
The paper folds a particular generalisation of rank-1 constraint systems. A computation that is not written in that form is not yet a Nova statement.
Model
What has to hold
The cycle of curves, if the implementation uses one, matches what the proof needs. The paper discusses this. An arbitrary curve pair is not automatically sound.
Falsifier
What would retire it
Are the steps uniform? The paper's cheapest claim assumes a repeated step shape.
03 Constant overhead
Observation
What the study says
The extra circuit work per step is constant and, in the paper, dominated by two group scalar multiplications. Constant does not mean negligible for a tiny step. It means it does not grow with the number of steps.
Model
What has to hold
The cycle of curves, if the implementation uses one, matches what the proof needs. The paper discusses this. An arbitrary curve pair is not automatically sound.
Falsifier
What would retire it
Are the steps uniform? The paper's cheapest claim assumes a repeated step shape.
04 No FFT, no setup
Observation
What the study says
The construction is designed to avoid a structured reference string and to avoid fast Fourier transforms. Those are reasons an implementer might choose it over a recursive SNARK. They are not reasons to skip the cryptographic assumptions.
Model
What has to hold
Data the computation read is available to whoever cares. Folding does not provide it.
Falsifier
What would retire it
Is there a structured setup?
03 Sequence
One action, as an operating tape
- 01A step of the computation is written as a constraint system.
- 02The prover folds that step into the running instance.
- 03The folded instance is satisfiable only if the steps so far were.
- 04At the end, one instance is checked.
- 05Zero knowledge, if used, hides the witness. Incremental verification does not require that hiding.
04 Load-bearing
The argument, and where a pitch drops it
Composition is the product
The cut
Nova does not make a single step cheaper than a direct proof. It makes a sequence of steps cheaper to verify as a sequence. A one-shot proof does not need it.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
Folding proves the steps that were folded. It does not fetch the data those steps read.
Assumptions moved, they did not vanish
The cut
Avoiding a trusted setup is real. Soundness still depends on the group and the folding argument. 'No setup' is not 'no assumption'.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
Folding proves the steps that were folded. It does not fetch the data those steps read.
05 Register
What has to be true
Model · Not re-measured
Each step is correctly expressed in the relation the fold expects.
Cryptography · Not re-measured
The cycle of curves, if the implementation uses one, matches what the proof needs. The paper discusses this. An arbitrary curve pair is not automatically sound.
Model · Not re-measured
The final verifier actually checks the folded instance.
Data · Not re-measured
Data the computation read is available to whoever cares. Folding does not provide it.
06 Divergence
What happened after the paper
Nova is the citation for folding as a way to do incremental proofs. Halo is the earlier recursive-proof citation with a different method. A system that says 'we recurse' should be able to say which of those it means.
A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.
07 Pre-mortem
What to check before you use the idea
- 0 of 4 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.
08 Anatomy
The paper, in the order a builder needs
The problem it names
Recursive proofs let a verifier check a long computation by checking a small proof that itself checked the previous proof. Doing that with a general SNARK is expensive. Nova asks for a cheaper combiner.
What the design proposes
- A folding scheme reduces two relaxed-R1CS instances to one.
- Each step of a long computation is folded in, so the prover's extra work stays small.
- The construction avoids a trusted setup and avoids FFTs, at the cost of its own cryptographic assumptions.
How the mechanism is specified
- The verifier at the end checks one folded instance, not every step.
- The recursion overhead in the paper is dominated by a constant amount of group work inside the circuit. That is a complexity statement.
- Zero knowledge is available. Incremental verification does not require it. Hiding the trace is a separate switch.
What this page does not treat as proven
- Folding proves the steps that were folded. It does not fetch the data those steps read.
- A later implementation can choose curves, a non-uniform step, or a different fold. That is no longer this theorem.
- Nothing here is a privacy policy for a user. It is a proof composition method.
Why the desk still reads it
When a system says 'recursive proofs', ask whether each step verifies a full SNARK or folds an instance. Nova is the second. The distinction is the prover's cost and the assumptions, not a slogan.
09 Lexicon
Terms, opened into the record
- Folding scheme
- A way to combine two instances of a relation into one instance of the same size.
- Incrementally verifiable computation
- A long computation whose correct prefix can be checked without rechecking every earlier step in full.
10 Repository
Every linked record on this page
Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.
Concepts
Papers
This is Blockchain Lab's reading of a public design paper. It is not the paper, not a copy of it, and not an offer of tokens, equity, custody or a partnership. Later network behaviour can diverge from the text. Nothing here is investment, legal or technical advice.
Research status: Design paper. Last reviewed: 1 October 2026. This is a reading of a public paper, not investment, legal or security advice.