Trying out a longer form article this time to allow a deeper dive into some areas of blockchain research. There are a lot of articles on zero knowledge proofs, and a lot of research papers on SNARKs or STARKs, but very little bridging the intermediate gap.
If you haven’t read my introduction to zero knowledge proofs Twitter thread, I strongly recommend it before going further, as a lot of this article builds on top of it.
The first introduction of a zero-knowledge proof was in a 1985 MIT paper (PDF warning) by Shafi Goldwasser and Silvio Micali (who later founded Algorand).
zkSNARKs and zkSTARKs are implementations of non-interactive zero knowledge proofs, which means that the prover does not need to disclose the data to the verifier. Non-interactive means that the prover only needs to send a single message to the verifier, instead of back-and-forth communication. This makes it possible for a blockchain to utilize ZK proofs, as blockchains are one-way. Once the block is produced, it is immutable.
There are two methods of zero-knowledge proofs that are currently being implemented with blockchain tech: zkSNARKs and zkSTARKs. In the Ethereum rollup space, there are two leaders: zkSync is using zkSNARKs, and StarkWare is using zkSTARKs. In addition to these two, there is Loopring, Aztec, Polygon Hermez (SNARKs), Polygon Miden (STARKs), and many more. You can find a full list on zkrollups.xyz. Regardless of the implementation of SNARKs vs STARKs, all rollups solve the same problem and should be thought of less as competitors and more as collaborators both helping advance and scale Ethereum through different means.
Introducing zkSNARKs
zkSNARK is an acronym: Zero-Knowledge Succinct Non-interactive Argument of Knowledge. Stemming from a 2012 UC Berkeley paper by Alessandro Chiesa, zkSNARKs use elliptic curves to secure the randomness required for a proof.
Elliptic curves are collision resistant, which means that it is very hard to find two separate inputs that produce the same output. If you’re interested in learning more about how elliptic curves work in regards to cryptography, this video is a great introduction.
zkSNARKs were first introduced in blockchain by Zcash, a fork of Bitcoin. Because SNARKs have been around longer, they have a lot of documentation, tooling, and are easier to get into as a developer compared to STARKs. There are some downsides to existing implementations, such as no post-quantum resistance (a problem for the next decade) and initial trust requirements. Regardless of the downsides, SNARKs offer much more than optimistic rollups, as shown below.
One issue with SNARKs is that they usually require a trusted setup. To mitigate the trust problem, zkSync has introduced a universal trusted setup for zkSync v1, which is much more secure compared to previous application-specific setups. Previous implementations required a lot more trust, as well as another setup for every future update of the protocol. Recently, DARKs were introduced (and later modified for security) which remove the need for a trusted setup. zkSync has been working on Redshift, which solves both the trusted setup problem as well as provides post-quantum security. Once this has been properly reviewed and battle-tested, it will be implemented into zkSync.
zkSTARKs
Being much more recent, zkSTARKs have less tooling and developer support, but that is starting to change. Introduced in 2018 (PDF warning) by Eli Ben-Sasson, Iddo Bentov, Yinon Horeshy and Michael Riabzev, STARKs operate differently under the hood. zkSTARK is an acronym for Zero-Knowledge Scalable Transparent ARguments of Knowledge. The main difference between SNARKs and STARKs is that a STARK uses collision resistant hash functions instead of elliptic curves. There are some downsides to STARKs as well, mainly that proof sizes are much larger than a SNARK proof, and take longer to verify as well as cost more gas. This tradeoff is worth it, however, because the effective TPS and throughput ceiling is much higher than a SNARK.
STARKs are more scalable than SNARKs, and with Validiums, which store data off-chain, the gas ceiling that developers have had to deal with on L1s is effectively gone. Here’s an example of a 3d model stored on a zkSTARK rollup, something that is impossible on a L1.
Comparisons
The levels in the charts below refer to complexity of arithmetic circuits. Each level is roughly 55x more complex than the previous level. In these examples, the difficulty slope for zkSTARKs rises much slower than SNARKs. As TPS and throughput increase, so does complexity. Even though zkSNARKs are less scalable, they are still magnitudes more scalable than existing L1s. Right now, zkSync can manage 3000 TPS with the same security guarantees as a L1 Ethereum transaction. With zkPorter, zkSync’s Validium solution, it can settle 50,000+ TPS.
Beyond L2s
Scalability is very close to becoming infinite, which will open the doors to a truly trustless, fast, and low-cost application layer secured by Ethereum. StarkWare is working on recursive STARKs known as L3s which stretch scaling even further.
Conclusion
The zero knowledge space is still an area of active research, and there is still a lot of work to be done before we reach the Endgame, but the tech is advancing rapidly and moving away from the Layer 1 wars towards a rollup-centric future.
Thanks for reading this article! This is the summation of a lot of research and my first longer article to help bridge the gap between research and the average user. Follow me on Twitter to get notified about future posts and let me know what you think. My content will remain 100% free, forever, and is licensed under CC BY-SA unless otherwise specified. (Shoutout to Swagtimus and Nisreen for helping out by proofreading!)