Nova: Recursive Zero-Knowledge Arguments from Folding Schemes

Disclaimer: This page is an educational summary of a cryptographic research paper. It is not investment, legal, or security advice. Read the original paper before relying on a technical claim.

Paper at a glance

Authors Abhiram Kothapalli (Carnegie Mellon University), Srinath Setty (Microsoft Research), and Ioanna Tzialla (New York University)
First published 2021 IACR Cryptology ePrint 2021/370; a version appeared at CRYPTO 2022
Subject Folding schemes and incrementally verifiable computation (IVC)
Paper license CC BY 4.0 on the IACR ePrint version. The separate Microsoft Nova software repository uses the MIT license.
Official paper IACR ePrint record and paper versions

The original ePrint record identifies the authors and affiliations, describes the construction, lists CRYPTO 2022 as the conference publication, and links the paper license. This summary treats the paper and the later software implementation as separate things. [1][2][3]

What problem does Nova address?

Some computations happen as a long sequence of similar steps: a virtual machine processes instructions, a service updates a running result, or a system applies state transitions over time. A verifier may want evidence that every step followed the rules without asking a prover to start the explanation from the beginning after every update.

Incrementally verifiable computation gives the prover a way to extend evidence as the computation advances. In Nova, each new step is folded into a running instance. The goal is to keep the additional work per step bounded independently of how many earlier steps have already been processed. The paper gives examples of long-running computations and explains how a final succinct proof can be built from the accumulated work; it does not establish that a particular blockchain or application has deployed Nova. [1][2]

Folding, in plain language

A folding scheme combines two compatible statements into one statement of the same general size. Nova applies this idea to a relaxed form of a rank-1 constraint system (R1CS). In a standard R1CS, a witness must satisfy constraints such as (Az) ∘ (Bz) = Cz. A relaxed R1CS adds a scalar and an error vector, commonly written (Az) ∘ (Bz) = u(Cz) + E, so instances can be combined while preserving a relation the verifier can check. [1][2]

Rather than build a new large proof that verifies the previous proof at every step, Nova folds the current computation instance together with the next one. Repeating the fold creates an incrementally verifiable computation. The “error” term in relaxed R1CS is part of the algebraic relation; it does not mean the computation is accepted with an arbitrary error. The security argument is about whether the folded relation still corresponds to valid original instances.

What the paper’s efficiency claims mean

The paper reports constant recursion overhead per step, dominated by two group scalar multiplications expressed in the circuit. It describes the prover’s per-step work as dominated by two multiexponentiations whose size is linear in the computation’s constraint size. Before an optional compression step, the proof contains a number of group elements that grows with that size; the paper also describes using a variant of an existing zk-SNARK to produce a succinct zero-knowledge proof. These are results under the paper’s model and assumptions, not a promise of a fixed speedup, a particular proof time, or lower costs in every implementation. [1][2]

In particular, “constant overhead” refers to the recursion overhead as the number of computation steps grows. It does not mean that proving a larger computation takes constant time or memory. Circuit size, curve choice, commitment scheme, hardware, implementation, and any final compression all affect practical performance.

Zero-knowledge and setup are separate questions

The paper develops a zero-knowledge folding scheme and an IVC construction. A folding step is a cryptographic building block; the properties of a deployed proof system still depend on its complete protocol, what data is public, how commitments are made, and how any final proof is generated. “Uses Nova” alone is not enough to conclude that an application hides every input or produces a particular proof format. [1][2]

The paper’s construction avoids a trusted setup and FFTs under its stated discrete-logarithm and elliptic-curve assumptions. That statement should not be copied blindly onto every later Nova implementation. The Microsoft repository describes multiple commitment options: its Pedersen/IPA option is distinct from its HyperKZG and Mercury options, which the repository says require a universal setup. The repository’s MIT license applies to that code, not to the IACR paper. [1][3]

Nova and later folding research

HyperNova is a later, separate paper. It changes the constraint-system setting to customizable constraint systems and includes results beyond the 2021 Nova construction. The current Microsoft repository also discusses later papers and implementation choices. These developments are related, but they are not interchangeable names for the original Nova paper. [3][4]

It is also safer to describe Nova as a research construction and a family of implementations than to claim that named zkVMs or rollups use it unless a current primary source documents that specific integration. The original paper establishes a cryptographic design; it does not by itself establish production adoption, user-facing privacy, or end-to-end performance.

Community Sentiment

A small archived discussion in r/crypto shows a recurring reader question: what real task benefits from incrementally verifiable computation? Replies offered examples such as updating a verified result from new data instead of recomputing the whole history. The exchange is a narrow, older discussion, not a current poll, a measure of adoption, or evidence for or against claims made in a separate security analysis. It does show why explanations of Nova should connect the folding mechanics to concrete repeated computations. [5]

Last updated: 2026-10

Related Terms

  • Recursive Proofs — the broader family of proofs that can verify earlier proofs.
  • Zero-Knowledge Proof — a proof with privacy properties defined by its protocol.
  • ZK-SNARK — a succinct proof system used in the paper’s optional proof-compression discussion.

See Also

Sources

  1. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla, “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes,” IACR Cryptology ePrint 2021/370 — primary source for the construction, authors, abstract, version history, assumptions, and paper license.
  2. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla, “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes,” CRYPTO 2022 proceedings — the conference version of the research paper.
  3. Microsoft, Nova software repository and README — current implementation overview, commitment-scheme options, setup notes, related work, and code license.
  4. Abhiram Kothapalli and Srinath Setty, “HyperNova: Recursive Arguments for Customizable Constraint Systems,” IACR Cryptology ePrint 2023/573 — a later, distinct folding-based research construction.
  5. r/crypto participants, discussion asking about practical uses of IVC in the context of Nova, July 2023 — a small historical discussion sample used only for the community section, not as technical evidence.