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