Spartan: Efficient and general-purpose zkSNARKs without trusted setup

This paper introduces Spartan, a new family of zero-knowledge succinct noninteractive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (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 commitments, 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 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 four zkSNARKs where the verifier’s costs and the proof size range from O(log^2n) to O(√n) depending on the underlying commitment scheme (n denotes the size of the NP statement). Three of these schemes do not require a trusted setup and one requires a one-time trusted setup that is universal and updateable.

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 it with recent zkSNARKs for R1CS instance sizes up to 220">2^{20} constraints. Among schemes without trusted setup, Spartan offers the fastest prover with speedups of 36">36—152×">152x depending on the baseline, produces proofs that are shorter by 1.2–416x, and incurs lowest verification times with speedups of 3.6–1326x. When compared to the state-of-the-art zkSNARK with trusted setup, Spartan’s prover is 2x faster for arbitrary R1CS instances and 16x faster for data-parallel workloads.2×">