An Overview of SNARKs
SNARKs vary along a number of dimensions, including proof size, the time it takes to construct and verify a proof, the cryptographic assumptions necessary to prove the soundness of the scheme, and whether the protocol requires a trusted setup. Broadly, the proof systems used in practice fall into three categories:
- Pairing based SNARKs with a trusted setup (this is what people usually think of as "SNARKs")
- Hash-based SNARKs without a trusted setup and plausible post-quantum security (this is what people usually call "STARKs")
- Schemes based on elliptic curves without a pairing and without a trusted setup (this includes Bulletproofs)
Pairing SNARKs
The first category includes proof systems like Plonk, Marlin, and Groth16, which is the proof system most people think of if they are familiar with ZK at all. These proofs are concretely small and constant-sized, are very fast to verify, but are generally slower to prove. This is because they require working over large prime fields, which is slow, and they require using pairing-friendly elliptic curves. Because they use elliptic curves, they are not secure against quantum attacks. It's worth noting that not all trusted setup SNARKs have the same kind of trusted setup; Groth16 requires a trusted setup per circuit, whereas Plonk, Marlin, and other proof systems based on KZG can use a single trusted setup for all circuits of bounded size. This "universal" trusted setup is also updateable: given a trusted setup, anyone can add randomness to the trusted setup later. This is not possible for Groth16, which requires a new setup for every circuit.
Code-Based SNARKs
The second category famously includes STARKs, as well as FRI-based proofs with preprocessing, such as Plonky2. These proof systems typically have excellent prover performance, especially when they use small fields with a special structure like Goldilocks, Babybear, or Mersenne 31, but proofs are much larger. Concretely, a FRI-based proof can be anywhere from 100 to 1000 times larger than a Groth16 proof (200 bytes vs 50-200 kilobytes). Other error-correcting code-based proofs like Bininus (which uses Brakedown instead of FRI) can be even larger or potentially smaller. These protocols do not require a trusted setup and are quantum-resistant when instantiated using suitable hash functions. Their security relies only on the security of the underlying hash function. However, compared to elliptic curve-based SNARKs, the security of FRI-based proof systems offers many more tunable degrees of freedom, which makes analyzing their security more complicated.
Most state-of-the-art proof systems for large circuits optimize for prover time and, therefore, use FRI-based proofs. However, people want to verify these proofs on blockchains, which, even on Ethereum, is very expensive for a pure STARK. As a result, most deployed systems wrap a STARK proof in a pairing-based SNARK like Groth16 or fflonk (a variant of Plonk). This gives the primary benefits of both schemes: a very fast prover and a very small proof, but it sacrifices quantum resistance and requires a trusted setup. It is also an example of a very powerful idea: proof recursion. By verifying a proof inside another proof, we can compress a larger proof, or potentially many larger proofs, into a smaller proof.
Elliptic Curve-Based SNARKs
The third category of SNARK includes Bulletproofs and folding schemes. Bulletproofs have concretely small proofs, proving time comparable to pairing-based SNARKs, and have no trusted setup. Unfortunately, they have very poor verification complexity: the time it takes to verify a Bulletproof is proportional to the time it takes to construct the proof. This meant that Bulletproof-based protocols were limited to small circuits like range proofs, and more fundamentally, it meant that one could not efficiently, recursively verify a Bulletproof with another Bulletproof. This is because the circuit for verifying a Bulletproof would be larger than the original circuit that was being proved!
This changed with Halo, which showed how to recursively "accumulate" Bulletproofs without recursively verifying the whole Bulletproof. This line of work proved to be very fruitful and has ultimately culminated in various folding schemes like Nova, HyperNova, ProtoStar, ProtoGalaxy, etc. (there are a lot of folding schemes). When paired with a folding scheme, one can use Bulletproofs to construct a SNARK that has small proofs, no trusted setup, and fairly fast provers. It is still an open question whether or not folding-based proof systems will be competitive with small field FRI. Some recent work has actually sought to unify the folding and FRI, but is only efficient for small depth recursion.
Sumcheck and GKR
Historically, most SNARKs have used univariate polynomials to encode an arithmetic circuit into an IOP. This was partly due to the structure of the underlying polynomial commitment schemes, particularly FRI and KZG, and also due to the relative simplicity of the approach. In such schemes, the prover must compute a "quotient polynomial" to show that the univariate equation is satisfied. Efficient computation of the quotient polynomial requires a Fast Fourier Transform (FFT) which has super-linear running time, \(O(n\log{}n)\), and is concretely expensive. In particular, when using large fields FFT computation requires a very large amount of memory. This turns out to be a major bottleneck for fast provers.
Recently, practitioners have begun using an alternative protocol called the Sumcheck Protocol. Originally published in 1992 as a purely theoretical result, the sumcheck protocol has reemerged as a solution to one of the main pain points of univariate SNARKs: it is no longer necessary to compute a quotient polynomial. Instead, the prover encodes the witness using multilinear polynomials and uses \(O(\log{}n)\) rounds of interaction with the verifier to "fold" (note: not the same “fold” as in “folding scheme,” more like that of Bulletproofs and FRI) these polynomials. This means that sumcheck-based proofs are generally larger than their univariate counterparts all else being equal, but can be proved in linear time and have lower memory requirements. Some sumcheck-based SNARKs include Spartan, HyperPlonk, and Honk.
In some sense, the sumcheck protocol has been hiding in plain sight all along. The inner product argument that Bulletproofs is based upon shares an essential structure with the sumcheck protocol. In fact, this can be made rigorous. This means that one can use the structure of an inner product argument with a sumcheck-based SNARK very efficiently. This is also true of FRI, as recently observed in BaseFold.
Even more recently, the GKR protocol has also experienced renewed interest from the applied ZK community. The GKR protocol builds on the sumcheck protocol by "layering" different sumcheck instances. This restricts the classes of circuits to which GKR can be applied, but remarkably this allows us to entirely avoid committing to intermediate layers. Recall that committing, especially for elliptic curve-based SNARKs, is the most expensive part of proving. The trade-off is that the verifier must do work proportional to the number of layers in the circuit, and for many classes of circuits, this ends up being \(O(\log^2 n)\) total work. There has been promising new work in fine-tuning this tradeoff by varying the type of sumcheck used to instantiate GKR, for example in Deep Thought.
Lookup Arguments
Traditionally, SNARKs encode the statement to prove as a network of addition and multiplication "gates" in an arithmetic circuit. This is sufficient, in a technical sense, but is not always very efficient. For example, if we want to prove that \(x\) lies in a range, we would likely first need to split the value into bits, check each bit is a valid bit, and then check that combining the bits yields the original value. It would be much simpler if we could simply construct a set of valid values and check that \(x\) is one of these values. This is exactly what lookup arguments allow: to look up a value in some table.
It turns out that lookup tables are an incredibly powerful primitive, and were extensively used by early computers. Look arguments are so powerful that they are a "universal primitive" in the sense that one could implement a SNARK using only lookup tables. This is called the "lookup singularity." While a SNARK using only lookups would likely not be efficient today, lookup arguments do work well for many classes of operations that cannot be efficiently arithmetized (that is, transformed into additions, multiplications, and random queries). Using lookup arguments also simplifies analysis of the SNARK.
There are many different lookup protocols. The simplest protocols just construct the table in the circuit. This works very well when the contents of the table are dynamic but has proving time that depends on the size of the table. These can be constructed using plookup or log derivative lookups. A different family of lookup arguments starting with Caulk through cq works with static tables. In these schemes, we preprocess the table so that at proving time the prover does (cryptographic) work only proportional to the number of values they want to look up. This lets us efficiently construct lookups into very large tables.
Finally, there are lookup arguments like Lasso based on structured tables. In this case, the table is fixed in advance, but it has some structure so that we do not need to precompute anything for the table. Lasso is able to transform lookups into a very large structured table into lookups into a collection of smaller tables. These smaller lookups can be performed using different protocols, and when using GKR it is possible to avoid committing to any "big" values while proving the lookup argument. While the restriction to structured tables may seem like it would limit the protocol, the companion paper Jolt shows that all the RISCV operations can be implemented using structured lookup tables.
BitVM
Unfortunately, none of these developments are natively compatible with Bitcoin, since Bitcoin script and block size limits are too limited to fit a SNARK verifier in a single Bitcoin block. Even verifiers for SNARKs optimized for verifier simplicity like Groth16 or fflonk over BN254 are too complex. This has recently changed with the advent of BitVM and even more recently BitVM2. BitVM is an optimistic protocol, which can be used to "prove" the execution of a much more complex statement that Bitcoin can natively execute. Optimistic means that rather than the prover actually constructing a SNARK, BitVM relies on one of a number of predesignated challengers to submit a fraud proof. BitVM2 relaxes this so that anyone can submit a challenge at the cost of significantly more onchain communication. There have been a number of additional refinements of BitVM-based protocols, including our very own SNARKnado, which can be used to verify a SNARK optimistically, thus bringing the power of zero knowledge proofs to Bitcoin.
Conclusion
Over the last ten to fifteen years, SNARKs have gone from an almost entirely theoretical discipline mostly confined to academia to a practical technology that's been deployed in the world. The proving speed of real computation has improved far faster even than Moore’s law and is now measured in hundreds of kilohertz. As it currently stands, this relentless pace of improvement shows no signs of slowing down. For this, we owe a tremendous debt of gratitude to the tireless work of both theoreticians and practitioners of SNARK cryptography.
We also owe a tremendous debt to the early, pre-bitcoin hackers and cypherpunks whose culture we inherited. Unlike traditional cryptography which tends to be mired by rent-seeking intellectual property which limits its adoption, e.g. Schnorr signatures in Bitcoin, SNARK research has remained free and open. This is a remarkable situation, and one that we cannot take for granted. No doubt it is also a necessary precondition for the extreme pace of improvement. As the space matures, and as more projects seek to make money, it is critically important that we maintain this delicate equilibrium and enforce socially the norm that our work must be free.
Most of this improvement has been driven by blockchain applications. Unlike in traditional settings with a centralized server, there is no trusted third party to whom to we can delegate verification. This makes blockchains, and decentralized protocols broadly, the perfect application for SNARKs. This was understood very early on in the history of Bitcoin, but at the time the technology was not sufficiently mature. This is, or at least very nearly is, no longer the case, as evidenced by the numerous real-world deployments of SNARKs. Now is the time to bring SNARKs back to Bitcoin.
