Paper 2021/370

Nova: Recursive Zero-Knowledge Arguments from Folding Schemes

Abhiram Kothapalli, Carnegie Mellon University
Srinath Setty, Microsoft Research
Ioanna Tzialla, New York University

We introduce a new approach to realize incrementally verifiable computation (IVC), in which the prover recursively proves the correct execution of incremental computations of the form $y=F^{(\ell)}(x)$, where $F$ is a (potentially non-deterministic) computation, $x$ is the input, $y$ is the output, and $\ell > 0$. Unlike prior approaches to realize IVC, our approach avoids succinct non-interactive arguments of knowledge (SNARKs) entirely and arguments of knowledge in general. Instead, we introduce and employ folding schemes, a weaker, simpler, and more efficiently-realizable primitive, which reduces the task of checking two instances in some relation to the task of checking a single instance. We construct a folding scheme for a characterization of $\mathsf{NP}$ and show that it implies an IVC scheme with improved efficiency characteristics: (1) the "recursion overhead" (i.e., the number of steps that the prover proves in addition to proving the execution of $F$) is a constant and it is dominated by two group scalar multiplications expressed as a circuit (this is the smallest recursion overhead in the literature), and (2) the prover's work at each step is dominated by two multiexponentiations of size $O(|F|)$, providing the fastest prover in the literature. The size of a proof is $O(|F|)$ group elements, but we show that using a variant of an existing zkSNARK, the prover can prove the knowledge of a valid proof succinctly and in zero-knowledge with $O(\log{|F|})$ group elements. Finally, our approach neither requires a trusted setup nor FFTs, so it can be instantiated efficiently with any cycles of elliptic curves where DLOG is hard.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2022
incrementally verifiable computation zero knowledge arguments recursive proof composition
Contact author(s)
akothapa @ andrew cmu edu
srinath @ microsoft com
it608 @ nyu edu
2022-06-30: revised
2021-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Abhiram Kothapalli and Srinath Setty and Ioanna Tzialla},
      title = {Nova: Recursive Zero-Knowledge Arguments from Folding Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/370},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.