Welcome to the resource topic for 2021/370
Title:
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Authors: Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla
Abstract: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.
ePrint: https://eprint.iacr.org/2021/370
Talk: https://www.youtube.com/watch?v=Jj19k2AXH2k
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/334/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .