## CryptoDB

### Srinath T. V. Setty

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
📺
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 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.

2020

CRYPTO

Spartan: Efficient and general-purpose zkSNARKs without trusted setup
📺
Abstract

This paper introduces Spartan, a new family of zero-knowledge succinct non-
interactive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiabil-
ity (R1CS), an NP-complete language that generalizes arithmetic circuit satisfiability.
A distinctive feature of Spartan is that it offers the first zkSNARKs without trusted
setup (i.e., transparent zkSNARKs) for NP where verifying a proof incurs sub-linear
costs—without requiring uniformity in the NP statement’s structure. Furthermore,
Spartan offers zkSNARKs with a time-optimal prover, a property that has remained
elusive for nearly all zkSNARKs in the literature.
To achieve these results, we introduce new techniques that we compose with the
sum-check protocol, a seminal interactive proof protocol: (1) computation commit-
ments, a primitive to create a succinct commitment to a description of a computation;
this technique is crucial for a verifier to achieve sub-linear costs after investing a
one-time, public computation to preprocess a given NP statement; (2) SPARK, a cryptographic compiler to transform any existing extractable polynomial commitment
scheme for multilinear polynomials to one that efficiently handles sparse multilinear
polynomials; this technique is critical for achieving a time-optimal prover; and (3) a
compact encoding of an R1CS instance as a low-degree polynomial. The end result
is a public-coin succinct interactive argument of knowledge for NP (which can be
viewed as a succinct variant of the sum-check protocol); we transform it into a
zkSNARK using prior techniques. By applying SPARK to different commitment
schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size
range from $O(log^2{n})$ to $O(\sqrt{n})$ depending on the underlying commitment scheme
($n$ denotes the size of the NP statement). These schemes do not require a trusted
setup except for one that requires a universal trusted setup.
We implement Spartan as a library in about 8,000 lines of Rust. We use the library
to build a transparent zkSNARK in the random oracle model where security holds
under the discrete logarithm assumption. We experimentally evaluate it and compare
with recent zkSNARKs for R1CS instance sizes up to 220 constraints. Among
schemes without trusted setup, Spartan offers the fastest prover with speedups of 36--$152\times$ depending on the baseline, produces proofs that are shorter by 1.2--$416\times$, and
incurs the lowest verification times with speedups of 3.6--$1326\times$. When compared
to the state-of-the-art zkSNARK with trusted setup, Spartan’s prover is $2\times$ faster for
arbitrary R1CS instances and $16\times$ faster for data-parallel workloads.

#### Coauthors

- Abhiram Kothapalli (1)
- Ioanna Tzialla (1)