Paper 2021/1043

Brakedown: Linear-time and post-quantum SNARKs for R1CS

Alexander Golovnev and Jonathan Lee and Srinath Setty and Justin Thaler and Riad S. Wahby

Abstract

This paper introduces Brakedown, the first built system that provides linear-time SNARKs for NP, 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. Brakedown does not require a trusted setup and is plausibly post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new amongst implemented arguments 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 (it also provides a faster prover than prior plausibly post-quantum SNARKs). As a modest additional contribution, we observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time from $O(\sqrt{N})$ to $polylog(N)$---while maintaining a linear-time prover---by outsourcing the verifier’s work via one layer of proof composition with an existing zkSNARK as the "outer" proof system.