A SNARK is a cryptographic primitive that enables a prover to prove to a verifier the knowledge of a satisfying witness to an statement by producing a proof such that the size of and the cost to verify it are both sub-linear (ideally, at most polylogarithmic) in the size of the witness. Given their many applications, constructing SNARKs with excellent asymptotics and concrete efficiency is a highly active area of research. Still, one of the key bottlenecks preventing application of existing SNARKs to large statements is the prover's asymptotic and concrete cost. This has limited practical uses of SNARKs to applications in which statements of interest are relatively small (for example, cryptocurrencies).

As with much of the literature on SNARKs, we focus on the following -complete problems: rank-1 constraint satisfiability (R1CS)  and arithmetic circuit satisfiability over a finite field . These problems are powerful "intermediate representations", in that they are amenable to efficient checking via SNARKs and are highly expressive. For example, in theory, any non-deterministic random access machine running in time can be transformed into an R1CS or an arithmetic-circuit-satisfiability instance of size "close" to In practice, there exist efficient transformations and compiler toolchains to transform applications of interest to these representations. [SVP+12, PGHR13, BFR+13, BCGT13, WSR+15, SAGL18a, LNS20, OBW20]

Our focus in this work is designing SNARKs for these problems with the fastest possible prover. We also wish to avoid a trusted setup, and desire a verifier that runs in time sub-linear in the size of the R1CS instance. Since the verifier must at least read the statement that is being proven, we allow a one-time public preprocessing phase for general (unstructured) R1CS or circuit-satisfiability instances. In this phase, the verifier computes a computation commitment, a cryptographic commitment to the structure of a circuit or R1CS instance. After the pre-processing phase, the verifier must run in time sub-linear in the size of the R1CS instance. Furthermore, the pre-processing phase should be at least as efficient as the SNARK prover. Subsequent works to Spartan [Set20] refer to such public preprocessing to achieve fast verification as leveraging holography [CHM+20, COS20,BCG20].

• Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Proceedings of the International Cryptology Conference (CRYPTO), 2020.
• Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2020.
• Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2020.
• Jonathan Bootle, Alessandro Chiesa, and Jens Groth. Linear-time arguments with sub-linear verification from tensor codes. In Theory of Cryptography Conference (TCC), 2020.

A second focus of our work is designing SNARKs that can operate over arbitrary (sufficiently large) finite fields. Prior SNARKs apply over fields that are "discrete-log friendly" or "FFT-friendly", or otherwise require one or many multiplicative or additive subgroups of specified sizes. Yet many cryptographic applications naturally work over fields that do not satisfy these properties. Examples include proofs regarding encryption or signature schemes that themselves work over fields that do not satisfy the properties needed by the SNARK. Indeed, most practically relevant elliptic curve groups are defined over fields that are not FFT-friendly. Even in applications where SNARK designers do have flexibility in field choice, field size restrictions can still create engineering challenges or inconveniences, as well as performance overheads. For example, they may limit the size of R1CS statements that can be handled over the chosen field, or force instance sizes to be padded to a length corresponding to the size of a subgroup.

In this work we design transparent SNARKs that asymptotically have the fastest possible prover, are plausibly post-quantum secure, and work over arbitrary (sufficiently large) finite fields. To the best of our knowledge, this latter property is new amongst implemented arguments with sublinear proof size and even quasilinear runtime. We optimize and implement these SNARKs, and demonstrate the fastest prover performance in the SNARK literature (even compared to SNARKs that require FFT-friendly or discrete-log-friendly fields).

• Formalizing "fastest possible" provers. How fast can we hope for the prover in a SNARK to be? Letting denote the size of the R1CS or arithmetic-circuit-satisfiability instance over an arbitrary finite field , a lower bound on the prover's runtime is operations in . This is because any prover that knows a witness for the instance has to at least convince itself (much less the verifier) that is valid. We refer to this procedure as native evaluation of the instance. So the natural goal, roughly speaking, is to achieve a SNARK prover that is only a constant factor slower than native evaluation. Such a prover is said to run in linear-time. Achieving a linear-time prover may sound like a simple and well-defined goal, but it is in fact quite subtle to formalize, because one must be precise about what operations can be performed in one "time-step", as well as the soundness error achieved and the choice of the finite field.

  In known SNARKs, the bottleneck for the prover (both asymptotically and concretely) is typically one or more of the following operations (we discuss exceptions later):

1. Performing an FFT over a vector of length .
2. Building a Merkle-hash tree over a vector consisting of elements of
3. Performing a multiexponentiation of size in a cryptographic group in this case, the field is of prime order and is typically an elliptic curve group (or subgroup) of order .

Should any of these operations count as "linear-time"?

• FFTs. It is clear that an FFT of length over should not count as linear-time, because the fastest known algorithms require operations over , which is a factor, rather than a constant factor, larger than native evaluation.

However, the remaining operations are somewhat trickier to render judgment upon, because they do not refer to field operations.

• Merkle-hashing. Regarding 2, a first observation is that to build a Merkle tree over a vector of elements of , computing cryptographic hashes is necessary and sufficient, assuming the hash function takes as in put elements of . However, this is only "linear-time" if hashing elements of can be done in time comparable to operations over It is not clear whether or not applying a standard hash function such as SHA-256 or BLAKE to hash a field element should be considered comparable to performing a single field operation.

  Theoretical work of  [BCG+17] sidesteps this issue by observing that (assuming the intractability of certain lattice problems over , specifically finding a low-Hamming vector in the kernel of a sparse matrix), a collision-resistant hash family of [ANI+17] is capable of hashing strings consisting of bits in bit operations, with security parameter . This means that a vector of elements of can be Merkle-hashed in bit operations, which [BCG+17] consider comparable to the cost of operations in .

  The aforementioned hash functions appear to be of primarily theoretical interest because they can be orders of magnitude slower than standard hash functions (e.g., SHA-256 or BLAKE). Hence, in this paper our implementations make use of standard hash functions, and with this choice, Merkle-hashing is not the concrete bottleneck in our implementations. Accordingly, and to simplify discussion, we consider our implemented Merkle-hashing procedure to be linear-time, even if this may not be strictly justified from a theoretical perspective for the reasons described above.

• Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth, Mohammad Hajiabadi, and Sune K. Jakobsen. Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), 2017.

• Multiexponentation. Pippenger's algorithm can perform an -sized multiexponentiation in a group of size by performing group operations. Typically, one thinks of the security parameter as (so that is superpolynomial in , ensuring the intractability of problems such as discrete logarithm in ), and so group operations is considered group operations. Each group operation is in practice at least as expensive (in fact, several times slower) than a field operation and hence for purposes of this work, we do not consider this to be linear time.

  However, note that for a fixed value of the security parameter , the cost of a multiexponentiation of size performed using Pippenger's algorithm scales only linearly (in fact, sublinearly) with . That is, Pippenger's algorithm incurs group operations and in turn this cost is comparable up to a constant factor to the same number of operations over a field of size . In practice, protocol designers fix a cryptographic group (and hence fix ), and then apply the resulting protocol to R1CS instances of varying sizes . For this reason, systems (such as Spartan [Set20] whose dominant prover cost is a multiexponentiation of size will scale (sub-)linearly as a function of Specifically, in the experimental results [Set20], Spartan's prover exhibits the behavior of a linear-time prover (as the cost of native evaluation of the instance also scales linearly as a function of ).

  Nonetheless, as a theoretical matter, should be thought of as , and hence we do not consider a multiexponentation of size to be a linear-time operation.

In summary, in this paper we consider FFTs and multiexponentations of size not to be linear-time operations, but do consider Merkle-hashing of vectors of size to be linear-time.

Part1Results and contributions

We address the above problems with Brakedown, a new linear-time SNARK that we design, implement, optimize, and experimentally evaluate. Concretely, Brakedown achieves the fastest SNARK prover in the literature, with additional important properties such as the ability to prove and verify R1CS instances over arbitrary fields and plausible post-quantum security. In addition, we implement and evaluate Shockwave, a variant of Brakedown that reduces proof sizes and verification times at the cost of sacrificing a linear-time prover, but nonetheless provides a faster prover than prior plausibly post-quantum secure SNARKs.

1Design of linear-time SNARKs.

We first distill from [BCG20] a polynomial commitment scheme with a linear-time commitment procedure, and show that it satisfies extractability, a key property required in the context of SNARKs (the commitment scheme itself is little more than a rephrasing of the results in  [BCG20], though  [BCG20] did not analyze extractability). This improves over the prior state-of-the-art polynomial commitment schemes by offering the first in which the time to commit to a polynomial is linear in the size of the polynomial.

We then describe a linear-time polynomial IOP for R1CS that is implicit in Spartan [Set20], a work that predates [BCG20]. Finally, we combine the linear-time polynomial IOP for R1CS with the linear-time polynomial commitment scheme in a standard way to obtain linear-time SNARKs.

From an asymptotic perspective, the above methodology recovers the main result of [BCG20], namely an IOP with a linear-time prover that, for security parameter , and for an -sized R1CS instance over any field of size and any fixed produces a proof of size that can be verified in time after a one-time preprocessing step, which requires finite field operations. As a secondary asymptotic result, we observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to at most polylogarithmic-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.

We believe that our approach is simpler and more direct than [BCG20]. In particular, we are able to reuse an existing high-speed, linear-time polynomial IOP for R1CS from Spartan [Set20]. This is important both for simplicity and for concrete efficiency. Moreover, it means that our goal of building a concretely fast SNARK prover boils down to optimizing our linear-time polynomial commitment scheme.

2A new and concretely fast linear-time encodable code.

A major component in the linear-time polynomial commitment scheme that we distill from [BCG20] is a linear-time encodable linear code. Unfortunately, to the best of our knowledge, existing linear-time encodable codes are highly impractical. We therefore design a new linear-time encodable code that is concretely fast in our context. Our code is based on classic results [GDP73, Spi96, DI14] , but designing this code was non-trivial and represents a significant technical contribution.

• Erez Druk and Yuval Ishai. Linear-time encodable codes meeting the Gilbert-Varshamov bound and their cryptographic applications. In Proceedings of the Innovations in Theoretical Computer Science (ITCS), pages 169–182, 2014.

We achieve a fast linear code that works over any (sufficiently large) field by leveraging the following four observations:

1. In our setting, to achieve sublinear sized proofs, it is sufficient for the code to achieve **relative Hamming distance **only a small constant, rather than very close to 1 (higher minimum distance would improve Brakedown's proof length by a constant factor, but would not meaningfully reduce the prover time);
2. Efficient decoding is not necessary, as the prover and verifier only execute the encoding procedure of the code (this observation also appears in prior work [BCG20]);
3. We can (and indeed want to) work over large fields, say, of size at least and
4. We can use randomized constructions instead of deterministic constructions of pseudorandom objects, so long as the probability that the construction fails to satisfy the necessary distance properties is cryptographically small (e.g., .

Observations (1)-(4) together allow us to strip out much of the complexity of prior constructions. For example, [Spi96] is focused on achieving both linear-time encoding and decoding, while [DI14] focus on improving the minimum distance of Spielman's code. On top of the this, we further optimize and simplify the code construction, and provide a detailed, quantitative analysis to show that the probability our code fails to achieve the necessary minimum distance is cryptographically small.

3Implementation, optimization, and experimental results.

We implement the aforementioned lineartime SNARK, yielding a system we call Brakedown. Because our linear-time code works over any (sufficiently large) field, and the polynomial IOP from Spartan does as well, Brakedown also works over any field; Brakedown is the first built system to achieve this property. It is also the first built system with a linear-time prover and sub-linear proof sizes and verification times.

We also implement Shockwave, a variant of Brakedown that uses Reed-Solomon codes instead of the fast linear-time code introduced above. Since Shockwave uses Reed-Solomon codes, it is not a linear-time SNARK and requires an FFT-friendly finite field, but it provides concretely shorter proofs and lower verification times than Brakedown and is faster than prior plausibly post-quantum secure SNARKs.

Both Shockwave and Brakedown contain simple but crucial concrete optimizations to the polynomial commitment scheme to reduce proof sizes. Neither Shockwave's nor Brakedown's implementations are currently zero-knowledge. However, Shockwave can be rendered zero-knowledge using standard techniques with minimal overhead. Brakedown could be rendered zero-knowledge while maintaining linear prover time by using one layer of recursive composition with zkShockwave (or another zkSNARK); it is also plausible that it could be rendered zero-knowledge more directly using techniques from [BCL20]. We leave the completion of zero-knowledge implementations to near-term future work.

• Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. Zero-knowledge succinct arguments with a linear-time prover. ePrint Report 2020/1527, 2020.

In terms of experimental results, Brakedown achieves a faster prover than all prior SNARKs for R1CS. Its primary downside relative to prior SNARKs is that its proofs are on the larger side, but they are still far smaller than the size of the -witness for R1CS instance sizes beyond several million constraints. Shockwave reduces Brakedown's proof sizes and verification times by about a factor of , at the cost of a slower prover (both asymptotically and concretely). Nonetheless, Shockwave already features a concretely faster prover than prior plausibly post-quantum SNARKs. Furthermore, although Shockwave's proof sizes are somewhat larger than most prior schemes with sublinear proof size, they are surprisingly competitive with prior post-quantum schemes such as Fractal [COS20] and Aurora [BCR+19] that have lower asymptotic proof size rather than Its verification times are competitive with discrete-logarithm based schemes, and in fact superior to prior plausibly post-quantum SNARKs.

4On knowledge soundness and extractable polynomial commitments.

The work of [BCG20] is concerned only with obtaining an IOP for R1CS satisfying standard soundness; it does not consider knowledge soundness. To transform the IOP into a succinct non-interactive argument of knowledge (SNARK), one actually requires the IOP to satisfy knowledge soundness (equivalently, one requires the polynomial commitment scheme that we derive from [BCG20] to satisfy a property called extractability). As mentioned earlier, in this work, we observe that this is indeed the case.

The polynomial commitment scheme that we derive from [BCG20] makes use of any linear error-correcting code with constant rate and relative distance. We provide two different knowledge extractors, depending on whether or not the code used has a polynomial-time decoding procedure. The first knowledge extractor uses the code's decoding procedure, and is extremely simple and moreover "straight-line" (the extractor need not rewind the prover). The second knowledge extractor is more complex and non-straight-line, but works without invoking the code's decoding procedure.

The Reed-Solomon code used in Shockwave does have efficient decoding (e.g., via the Berlekamp-Welch algorithm) and hence Shockwave is a SNARK for which the knowledge extractor is straight-line. The code used in Brakedown does not have a (known) efficient decoding procedure. However, Brakedown is still a SNARK, but not via a straight-line extractor.