ZK101: Intro to Zero Knowledge Proofs
Since 2020’s DeFi summer and the NFT craze, high gas fees on the Ethereum network have been the norm. New users entering the crypto space may be shocked to see fees north of $50 per transaction and discouraged to participate. With these fees, many crypto natives have resorted to using alternative layer one chains or layer two solutions built on top of Ethereum. In this article, we’ll take a look at the latter, specifically at an innovation that allows L2s to scale Ethereum while maintaining privacy and Ethereum’s high level of security: zero knowledge proofs.
Zero Knowledge
Zero knowledge proofs (ZKPs) are ways for a person or party to prove to another person/party that they know some information or secret without revealing exactly what that information or secret is. It is the ability to prove that the prover owns the key or password without the verifier knowing what the key could be. This is usually done with complex polynomials and algorithms that can become quite complicated in practice, so let’s use two examples to illustrate this concept.
Where’s Waldo is a fun example to demonstrate ZKPs. Given that you know where Waldo’s location is on a page, you want to convince your friend that you know where Waldo is without spoiling the game. You take a large piece of paper many times the size of the Where’s Waldo page and cut out a small circle near the middle, just enough to see Waldo and nothing else. With Waldo peeking through the cutout, you are able to prove that you know where Waldo is, without giving your friend any contextual hints.
Another example is the case of two different colored balls and a colorblind friend. You, assuming that you are not colorblind, are able to easily differentiate between the green and red balls, except the balls are identical to your friend. You want to prove that the balls are different and distinguishable from one another. To do this, you give your friend one ball in each hand and tell them to put both behind their back. Tell them they can either swap the balls or choose not to, and after swapping (or not), they show you the balls. Seeing the colors, you tell them whether or not they switched the balls behind their backs.
Clearly, you could have guessed this with 50% accuracy, and your friend will be rightfully skeptical. Yet, repeat this process and this drops to 25%. Run it ten times and your chance of guessing all ten correctly is (0.5^10) = 0.977%. Redo this a hundred times and there is near zero chance that you could have it all right, therefore “proving” that the balls are indeed different. Proving is in quotes because though extremely unlikely, it is possible to get a hundred in a row correct. Note that you did not have to reveal the colors to your friend to conduct your proof, making this a form of ZKP.
By definition, zero knowledge proofs must satisfy three properties:
1. Completeness - An honest verifier will be convinced by an honest prover.
2. Soundness - A prover cannot convince an honest verifier by lying or cheating.
3. Zero knowledge - The verifier does not learn anything other than the fact that the statement is true.
The examples above, albeit in a simplified way, both meet these requirements.
The concept of ZKP was actually first proposed in 1985 in the paper “The Knowledge Complexity of Interactive Proof-Systems”, written by three professors from MIT and the University of Toronto. It has since regained substantial traction in the past few years because of its power in blockchain. Let’s explore some of the different types of ZKPs that L2 scaling solutions are implementing -
SNARK
The most commonly discussed form of zero knowledge proofs, being one of the first, are ZK-SNARKs, which stands for Zero Knowledge Succinct Non-interactive ARgument of Knowledge. Breaking down these words:
- Succinct - Proof is small and easy/fast to verify
- Non-interactive - The prover can give the verifier the proof and the verifier can validate the proof. No communication is necessary between the parties
- Argument of Knowledge - The prover has knowledge / information and can “prove” it. “Proof” is not used here because ZKPs do not technically “prove” as mentioned earlier.
What is important about SNARKs (and the other ZKPs covered below) is their non-interactivity. Of the two examples, Where’s Waldo represents a ZK-SNARK protocol as the proof of showing Waldo in the cutout does not require interaction between the parties. Applying this to blockchains, it would be inefficient for each validator to communicate back and forth with the prover. SNARKs allow the prover to submit a single proof that is forwarded to all validators to be verified, allowing the validation process to execute at a comparatively faster speed. SNARKs are especially useful in scenarios where there are many verifiers who all need to verify the proof.
The problem with SNARKs is the need for a trusted setup. To prevent the prover from generating fake proofs, the verifier must in some indirect way understand what is being proven. With ZK-SNARKs, this is the trusted setup’s role, who creates private keys that ensure the legitimacy of the proof. Being that people participate in the process of creating these keys, it is crucial that these people never disclose the key-generation process or the keys themselves. If the key is ever attacked or somehow made known, fake proofs can be generated, effectively dismantling the system.
STARK
STARK is an acronym for Scalable and Transparent Argument of Knowledge. Developed to combat the issue of the trusted setup, STARKs instead use hashing algorithms similar to Bitcoin mining, meaning the setup is randomized. This randomness is also public information - transparency - creating trust that can be verifiable by anyone. An additional benefit to STARKs is their scalability. Compared to SNARKs, as computation size increases, STARKs are much faster on the prover side and approximately equal in speed on the verifier side. Being that prover times (1.6s STARKs vs 2.3s SNARKs) are much higher than verification times (16ms STARKs vs 10ms SNARKs), STARKs are faster in terms of total time spent, particularly when the number of transactions are high.
However, the drawbacks of STARKs are in its proof size. For a single transaction, the estimated size for a SNARK is 200 bytes compared to 5.6 kilobytes for STARKs. This is a significant consequence for use in blockchains because gas fees increase as more data is required to be processed, making it unsuitable with current STARK block sizes.
PLONK
Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Unlike SNARKs and STARKs, the words that make up the backronym PLONK specify the mathematical techniques used in this ZKP. Dissecting this one would get technical very quickly.
At a high level, PLONK returns to the trusted setup, except this time, it is a “universal and updateable” setup. Instead of having one party being the trusted setup, participants can add themselves to the trusted setup. Furthermore, PLONK is organized such that as long as one party among all participants is honest, the entire trusted setup is secure.
Compared to SNARKs and STARKs, PLONK falls between the two in terms of proof size and security assumptions. Although PLONK is slower, the proof size is more manageable compared to STARKs while being “safer” than SNARKs with its single trusted setup.
Future of Ethereum Scalability
In his blog titled “Endgame”, Vitalik describes his vision for the future of the average “big block chain” - one with very high block frequency and block size with many transactions per second. In order to make such a blockchain acceptably trustless and censorship resistant, one of the attributes he mentions is to introduce either fraud proofs or ZK-SNARKs to allow for direct and cheap validation. Zero knowledge proofs and rollups through L2 solutions on Ethereum are the future of scalability, and projects such as Starkware, zkSync and Polygon are building towards this prospect.
Polygon’s Role in ZK
Currently, Polygon’s main L2 solution is the Proof of Stake (POS) Chain. Sharing Vitalik’s vision on scalability, Polygon is investing towards new products that will make use of zero knowledge technology in the form of rollups. Here are one-liners for three upcoming solutions to look out for that use ZKPs:
Hermez - The first decentralized ZK rollup, uses ZK-SNARKs
Zero - Focused on speed, a ZK proof using Plonky2 - a recursive SNARK combining PLONK and FRI (Fast RS IOPP)
Miden - A STARK-based VM to be plugged into any ZK implementation
Conclusion
Although zero knowledge proofs are mostly still in the works, we will surely see this technology implemented on a large scale in the next few years or even months. ZK-SNARKs were first coined in 2012 and since then, we’ve seen research aimed at combating the troublesome trusted setup - leading to alternatives such as ZK-STARKs and PLONK. With progress being made each week, improvements in speed, size and security will open up the doors to ZK scalability very soon. With this, I leave with you two questions: Do you agree with Vitalik’s ZK Endgame? What do you think the future of DeFi will look like?
Author is a Decentralized Finance (DeFi) intern at Polygon, highly interested in Tokenomics, Web3, and blockchain applicability in the real world. They’re a student at New York University – College of Arts and Sciences, studying Economics and Data Science. Other interests include golf, anime and poker. Feel free to reach out on Twitter @charlesgnuhc.