Comparing General Purpose zk-SNARKs
The zk-SNARK space is moving so fast, it’s hard to keep up. Just the last two months, a number of new breakthrough zk-SNARK constructs were announced. What’s new is that the infamous ‘trusted setup’ is now redundant, meaning that any arbitrary computation can now be used (hello smart contracts!). However, it’s hard to find an easy digestible information on these new constructs. In this blog post, I compare the new constructs. Multiple teams behind the constructs have already shared that further improvements are forthcoming. I will update this blog post when I receive new information
Zero knowledge proofs like zk-SNARKs have a wide variety of applications: Zcash uses zero knowledge for privacy, Coda and Mir to compress an entire blockchain into only a few kilobytes, and 0x and Matter to roll up many transactions into a single proof on Ethereum. (For those unfamiliar with zero knowledge proofs, see this explanation)
Trusted setup
Traditional zk-SNARKs, like Groth16 have one major drawback: they relied on a public reference string that was created using a one-time trusted setup. This setup creates a reference string used by both prover and verifier. There were three major issues:
- The setup generated ‘toxic waste’ that, if leaked, can be used to generate undetectable fake proofs. Multi-party computations (often referred to as ceremonies) negate the issue for the most part, but the coordinating such ceremonies is extremely complex.
- The reference string that a trusted setup creates was always tied to one circuit (program, basically). It was impossible to have one single setup for any arbitrary computation. That made many applications impossible, like smart contracts.
- The setup was a one-time event and the reference string produced wasn’t upgradable. What that means is that if, for instance, Zcash needed to fix even a tiny bug in their zk-SNARK circuit, a new ceremony would be needed to deploy the bug fix.
General Purpose zk-SNARKs
The new zk-SNARK constructs fix the setup limitations, and that means arbitrary code like smart contracts can be run as zk-SNARKs. There are two different approaches:
- Transparent setup: The setup creates a Common Reference String, is public and doesn’t create toxic waste. This is similar how zk-STARK (with a T) works. Fractal, Halo, and SuperSonic-CG use transparent setups. The downside of this approach is that the proof sizes can be big. Fractal and zk-STARK proofs can be up to 250kB, which can be impractical for blockchain applications. The Fractal team told me they are working on reducing the proof size. Halo and SuperSonic have small 10 kB proof sizes or smaller. (Note: zk-STARK is the name of a specific zero knowledge construct, similar to, say, Groth16 or Fractal. zk-SNARKs on the other hand is the name of a class of constructs. That’s why Fractal is called a zk-SNARK, not a zk-STARK)
- Universal setup: The setup creates a Structured Reference String, does create toxic waste, but the setup isn’t limited to only one single circuit anymore. Instead, one reference string can be used with an unlimited number of arbitrary circuits (of a certain maximum size). Examples are Marlin, SuperSonic-RSA, and Plonk. The reference string of these three constructs can be updated after the ceremony to improve security: in the event the current toxic waste leaks, only an update to the setup is needed to secure the system again. (Some general purpose zk-SNARKs, like AuroraLight and Libra use a static non-updatable universal setup. We don’t cover these in this blog post).
Zk-SNARK classification
How do the new zk-SNARKs compare? On the prover side, creating a proof takes O(n log n) time for every zk-SNARK construct. The differences are mainly the proof size, the verification time, and the size of the reference string.
The following classification is based on Alessandro Chiesa’s presentation at ZKSummit zk0x04 in San Francisco. Leading is the type of reference string created in the setup. (Note that Zk-SNARK constructs based on static circuit specific reference strings are not general-purpose, but are included for comparison.)
Underneath the hood all these zk-SNARKs use one of three types of compilers: Pre-processing, DARK and traditional (non-general purpose) SNARK. Note to reviewers: Naming of the three compilers could be improved. Suggestions welcome.
The existing constructs
For reference, I’ll include descriptions of three existing constructs. One (Groth16) is a non-universal and relies on a one-time non-updatable setup for specific circuits. The second one, Sonic is a general purpose zk-SNARK.
Groth16
Currently the fastest and smallest known zk-SNARK. It’s used in Zcash, amongst others. Groth16 is non-universal; the setup is always tied to one specific circuit. Because of the speed and small proof size, performance of new zk-SNARKS is often compared to Groth16.
Paper: https://eprint.iacr.org/2016/260
Sonic
Sonic is an early general purpose zk-SNARK protocol. The paper was published in January 2019, 10 months before this blog post was written, which is an eternity in zk-SNARK time. Sonic supports a universal and updatable common reference string. Sonic proofs are constant size, but verification is expensive. In theory, multiple proofs can be verified in batches to achieve better performance. Many of the new zk-SNARKs listed below are based on Sonic.
Paper: https://eprint.iacr.org/2019/099
The new constructs
Fractal
Fractal is a zk-SNARK that allows recursion without need for pairing-friendly elliptic curves. By pre-processing the circuits, a succinct verification with transparent setup becomes possible. The proof size is currently up to 250 kB and notably larger than other constructs. The size will decrease in forthcoming updates.
Paper: https://eprint.iacr.org/2019/1076
Halo
Halo is a zk-SNARK that supports recursive proof composition without a trusted setup. Recursion works using “nested amortization”: repeatedly collapsing multiple proofs together over cycles of elliptic curves.
Unlike the other new constructs, Halo’s verification time is linear, making it the only new construct that isn’t succinct. However, improvements are forthcoming.
Paper: https://eprint.iacr.org/2019/1021
SuperSonic
SuperSonic is, as you already guessed, an improvement on Sonic. SuperSonic is the first transparent zk-SNARK that has both a practical prover time as well as the asymptotically logarithmic proof size and verification time.
Paper: https://eprint.iacr.org/2019/1229
Marlin
Marlin is an improvement on Sonic with 10x better prover time and 4x better verification times.
Paper: https://eprint.iacr.org/2019/1047
Plonk
Plonk is an improvement on Sonic with a 5x better prover time.
Paper: https://eprint.iacr.org/2019/953
Performance
The big question is: how do the constructs compare in terms of performance? Unfortunately, I am not aware of any benchmark for zk-SNARKs and even if there was one, not all new constructs have a reference implementation yet. The constructs that do have reference implementations are without exception unoptimized. The numbers in the table below, therefore, should be taken with a grain of salt. They’re based on benchmarks in the papers, or based on estimates provided by the inventors.
Looking at the proof size, ballpark prover runtime, and ballpark verification runtime, a few things are notable:
- Constructs with a transparent setup usually have much bigger proof sizes
- Verification time in Halo is not constant, unlike the other new constructs
- Groth16 is still unbeatable in terms of proof size and runtime
What’s next?
I will update this blog post when new information or improved constructs come out. I’d love to hear from you about what you’d like to learn about zk-SNARKs. An introduction for engineers to zk-SNARKs? Recursive zk-SNARKs? Let me know in the comments or send me an email.
Thanks to
A huge thanks to Dev Ojha at UC Berkeley for tirelessly explaining the details of Fractal and other projects. Thanks to Howard Wu, J Ayo Akinyele, and Lorenz Breidenbach for proofreading and providing feedback.
We’re hiring!
If you’re a Rust developer who’s interested in learning zk-SNARKs (but not necessarily have experience with zk-SNARKS): Starling Protocol is hiring. Starling is a programmable succinct layer one protocol based in Berkeley, CA. Starling Protocol is a diverse and inclusive workplace. We encourage people of color, LGBTQ individuals, and women to apply. Email ronald@starlingprotocol.com for more information.
