International Association
for Cryptologic Research

This paper introduces a SNARK called Brakedown. Brakedown targets R1CS, a popular NP-complete problem that generalizes circuit-satisfiability. It is the first built system that provides a linear-time prover, meaning the prover incurs O(N) finite field operations to prove the satisfiability of an N-sized R1CS instance. Brakedown’s prover is faster, both concretely and asymptotically, than prior SNARK implementations. It does not require a trusted setup and may be post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new among built proof systems with sublinear proof sizes. To design Brakedown, we observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 2020) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 2020), yields linear-time IOPs and SNARKs for R1CS (a similar theoretical result was previously established by BCG, but our approach is conceptually simpler, and crucial for achieving high-speed SNARKs). A core ingredient in the polynomial commitment scheme that we distill from BCG is a linear-time encodable code. Existing constructions of such codes are believed to be impractical. Nonetheless, we design and engineer a new one that is practical in our context. We also implement a variant of Brakedown that uses Reed-Solomon codes instead of our linear-time encodable codes; we refer to this variant as Shockwave. Shockwave is not a linear-time SNARK, but it provides shorter proofs and lower verification times than Brakedown, and also provides a faster prover than prior plausibly post-quantum SNARKs.

This paper presents Dory, a transparent setup, public-coin interactive argument for inner-pairing products between committed vectors of elements of two source groups. For a product of vectors of length $n$, proofs are $6 \log n$ target group elements and $O(1)$ additional elements. Verifier work is dominated by an $O(\log n)$ multi-exponentiation in the target group and $O(1)$ pairings. Security is reduced to the standard SXDH assumption in the standard model. We apply Dory to build a multivariate polynomial commitment scheme via the Fiat-Shamir transform. For a dense polynomial with $n$ coefficients, Prover work to compute a commitment is dominated by a multi-exponentiation in one source group of size $n$. Prover work to show that a commitment to an evaluation is correct is $O(n^{\log{8}/\log{25}})$ in general ($O(n^{1/2})$ for univariate or multilinear polynomials); communication complexity and Verifier work are both $O(\log n)$. These asymptotics previously required trusted setup or concretely inefficient groups of unknown order. Critically for applications, these arguments can be batched, saving large factors on the Prover and improving Verifier asymptotics: to validate $\ell$ polynomial evaluations for polynomials of size at most $n$ requires $O(\ell + \log n)$ exponentiations and $O(\ell \log n)$ field operations. Dory is also concretely efficient: Using one core and setting $n = 2^{20}$, commitments are 192 bytes. Evaluation proofs are ~18kb, requiring ~3s to generate and ~25ms to verify. For batches at $n=2^{20}$, the marginal cost per evaluation is <1kb communication, ~300ms for the prover and ~1ms for the verifier.