**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 ]