You are looking at a specific version 20190603:173431 of this paper. See the latest version.

Paper 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).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
zkSNARKstransparent zkSNARKsSNARKszero-knowledgesuccinct arguments
Contact author(s)
srinath @ microsoft com
History
2020-08-19: last of 6 revisions
2019-05-23: received
See all versions
Short URL
https://ia.cr/2019/550
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.