Cryptology ePrint Archive: Report 2019/550

Spartan: Efficient and general-purpose zkSNARKs without trusted setup

Srinath Setty

Abstract: This paper describes a new public coin, succinct interactive zero-knowledge argument for NP under standard cryptographic hardness assumptions—without requiring a trusted setup. In particular, our argument enables a prover to prove the satisfiability of arithmetic circuits over a large finite field (an NP-complete language for which there exist efficient reductions from high-level programs of practical interest) to a verifier. We construct this argument through a novel synthesis of techniques from prior work on short PCPs, MIPs, and doubly-efficient IPs. Specifically, our interactive argument is a succinct variant of the sum-check protocol where the protocol is run with a carefully-constructed low-degree polynomial that encodes a given circuit satisfiability instance. Since our interactive argument is public coin, we make it non-interactive in the random oracle model, thereby obtaining a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), which we call Spartan.

Spartan is the first zkSNARK without trusted setup (i.e., a “transparent” zkSNARK) where verifying a proof incurs sub-linear costs without requiring data parallelism (or other homogeneity) in the structure of an arithmetic circuit for which a proof is produced. To achieve this, Spartan introduces a notion of computation commitments—a primitive to create a short cryptographic commitment to a mathematical description of an arithmetic circuit. Finally, Spartan is asymptotically efficient with small constants: the prover performs $O(n)$ cryptographic operations to produce a proof of size $O(n^{1/c})$ that can be verified in $O(n^{1-1/c})$ time (after a one-time, public preprocessing of the circuit to create a computation commitment that takes $O(n)$ time), where $n$ denotes the size of an arithmetic circuit and $c \geq 2$ (Spartan can produce $O(\log{n})$-sized proofs, but the verifier incurs $O(n)$ costs).

Category / Keywords: cryptographic protocols / zkSNARKs, transparent zkSNARKs, SNARKs, zero-knowledge, succinct arguments

Date: received 22 May 2019, last revised 3 Jun 2019

Contact author: srinath at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20190603:173431 (All versions of this report)

Short URL: ia.cr/2019/550


[ Cryptology ePrint archive ]