Paper 2021/370

Nova: Recursive Zero-Knowledge Arguments from Folding Schemes

Abhiram Kothapalli and Srinath Setty and Ioanna Tzialla

Abstract

We introduce folding schemes for $\mathsf{NP}$, an interactive protocol between a prover and a verifier to combine two $N$-sized $\mathsf{NP}$ instances over a finite field $\mathbb{F}$ into a single $N$-sized instance such that the folded instance is satisfiable only if the original instances are satisfiable. In particular, we devise a folding scheme for relaxed R1CS, a characterization of $\mathsf{NP}$ that is especially amenable to folding. The verifier's cost and the communication in the folding scheme are both $O_\lambda(1)$, where $\lambda$ is the security parameter, assuming any additively-homomorphic commitment scheme that provides $O_\lambda(1)$-sized commitments to $N$-sized vectors over $\mathbb{F}$. Additionally, the protocol is honest-verifier zero-knowledge and public coin, so it can be made non-interactive in the ROM using the Fiat-Shamir transform. We then construct incrementally verifiable computation (IVC) from folding schemes by using a "verifier circuit" that at each recursive step folds an entire R1CS instance representing computation (including a copy of the verifier circuit) at its prior step into a running relaxed R1CS instance. A distinctive aspect of our approach to IVC is that it achieves the smallest verifier circuit (a key metric to minimize in IVC) in the literature: the circuit is constant-sized and its size is dominated by two group scalar multiplications. We then show that the running relaxed R1CS instance can be proven in zero-knowledge with a succinct proof using a variant of an existing zkSNARK. Putting these together, we obtain Nova, a new zero-knowledge proof system for incremental computations, where for an $N$-sized computation with $C$-sized steps, the prover runs in $O_\lambda(N)$ time to produce $O_\lambda(\log{C})$-sized proofs that can be verified in $O_\lambda(C)$ time. Nova does not require a trusted setup nor performs FFTs, so it can be efficiently instantiated with any cycles of elliptic curves where DLOG is hard. Furthermore, at each step, the prover time is dominated by two $\approx$$C$-sized multiexponentiations. Finally, Nova can achieve $O_\lambda(\log{C})$ verification time at the cost of employing a pairing-friendly elliptic curve where SXDH is hard.