Paper 2021/1043

Brakedown: Linear-time and field-agnostic SNARKs for R1CS

Alexander Golovnev
Jonathan Lee
Srinath Setty, Microsoft Research
Justin Thaler
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).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Keywords
linear-time SNARKssuccinct argumentsproof systems
Contact author(s)
srinath @ microsoft com
History
2023-08-24: last of 2 revisions
2021-08-16: received
See all versions
Short URL
https://ia.cr/2021/1043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1043,
      author = {Alexander Golovnev and Jonathan Lee and Srinath Setty and Justin Thaler and Riad S.  Wahby},
      title = {Brakedown: Linear-time and field-agnostic SNARKs for R1CS},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1043},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1043}},
      url = {https://eprint.iacr.org/2021/1043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.