ZK Proofs 101: the basics of zero-knowledge rollups
Table of Contents
What you need to know about ZK proofs, zkEVMs, and Layer 2 tech
Let’s face it: blockchain tech can get complicated.
For those of us who aren’t coders or computer scientists, understanding the technology that powers blockchain ecosystems can be a daunting task. These concepts get even more challenging at the bleeding edge of invention where many crypto projects exist. However, it’s crucial for us as users, investors, and community members to understand the technology as best we can.
In this article, we’ll look at the basics of one of the most fascinating and cutting-edge concepts in crypto: zero-knowledge (ZK for short).
What is zero-knowledge?
At the heart of this complex topic lies a rather elegant problem: how can I prove to you that I know a secret, without telling you the secret?
The solution to this problem is known as a “zero-knowledge proof.” Here’s an example:
Suppose we have a box like this one, with a lock and a slot at the top. I want to prove to you that I know the lock’s combination without telling you what it is. How can I do that? Well, I can have you write a secret on a piece of paper, something that I would never know. Then, you drop that piece of paper in the slot. If I unlock the lock, read the paper, and tell you your secret, then I have proven that I know how to open the box. And in this process, I have proven that I know the combination without revealing it to you (giving you “zero knowledge” of the combination). This is a zero-knowledge proof.
This idea was first developed in the 1980s by Shafi Goldwasser, Silvio Micali and Charles Rackoff at MIT. They were working on interactive proof systems: systems in which a “Prover” attempts to convince a “Verifier” that a statement is true. Prior to their work, much of the research on interactive proof systems focused on what the Verifier could do to root out a malicious Prover trying to trick them. Goldwasser, Micali, and Rackoff asked a different question: what if the Prover doesn’t trust the Verifier with this information?
Let’s look at an example of this situation: passwords.
To log into a website, we must prove that we know our password. In doing so, we tacitly prove that we are ourselves (just as you put a secret into the box that only you could know.) In theory, we can log in by sending our password to the website, where it can be verified on their servers. But this is not ideal. Our password is now being transmitted over the Internet and stored on the website’s servers, which might even be operated by a third party. Our sensitive information is made vulnerable. A more secure login option would be one that uses a zero-knowledge proof: confirm to the server that we know our password, without trusting the server with our password.
The Three Color Problem
After the problem of zero-knowledge was first introduced, a solution was discovered by Silvio Micali (one of the authors of the original paper), Oded Goldreich, and Avi Wigderson.
Suppose we have a graph with many nodes, each of which is connected by a line. We need each node to be one of three colors, with no line connecting two nodes of the same color.
If it helps to imagine a scenario, pretend each node is a storage unit containing a hazardous chemical. They cannot be stored next to more of the same chemical, as it is extra dangerous in large quantities. (This is why we can’t have two of the same color next to each other.) I want to prove to you that the chemicals are stored safely, without telling you where they are in order to keep our plan more secure. Thus, I need a zero-knowledge proof!
Micali, Goldreich, and Wigderson derived a clever solution: I can cover up the entire graph. Then, you can ask me to show you two connecting nodes. If they are the same color, I’ve obviously failed and don’t know how to solve the problem. If they are different colors, then I increase your confidence that I am right.
Then, you can ask me to show you another two nodes. If those are also different colors, your confidence in my solution increases further. As we repeat this, you become more and more convinced that I know the solution, without ever seeing my entire arrangement. (Here’s a great interactive tool to try this for yourself.)
The beautiful thing about this solution is that it is NP-complete; that is, by solving this problem, the solvers proved that every problem like this is solvable, too. In doing so, zero-knowledge proofs were proven possible.
If we recreate this mathematically and use computers to solve it, we can create massive arrays to represent complex problems, and perform thousands of reveals to give the Verifier extremely high confidence. Scientists have been developing new applications and more efficient solutions for zero-knowledge proofs ever since.
Practical uses for ZK in crypto
The uses of zero-knowledge in crypto are vast and various. Even the word “crypto” is derived from cryptography, and zero-knowledge is itself a cryptographic concept: a method for transmitting information secretly.
Trust (or lack thereof) is a massive idea in crypto. One of the chief aims of cryptocurrency and decentralized finance is to be able to exchange money between two strangers who do not trust each other, without trusting a centralized entity to handle the transaction, either. Zero-knowledge -- a trustless method for verifying information -- is everywhere in crypto for this reason.
Zero-Knowledge Layer 2s
ZK is being explored and developed for countless purposes, but the most visible is probably in Layer 2s.
A Layer 1 blockchain is a standalone network which can validate and finalize transactions on its own. When you think of a blockchain, you’re almost certainly thinking of a Layer 1: Ethereum, Bitcoin, Aptos, Solana, Avalanche, BNB Chain, etc. Layer 1s are decentralized by design, and their chief function is to process transactions immutable and record them indelibly. This makes them hard to upgrade by design. The Merge, in which Ethereum was upgraded from a Proof-of-Work consensus mechanism to cheaper, greener Proof-of-Stake, was a risky engineering marvel which required years of planning. Instead, it is easier to scale a Layer 1 by creating additional systems which run on top of it: Layer 2s.
On Ethereum, one of the most common types of Layer 2s is “rollups.” Rollups make Ethereum faster and cheaper by processing a bunch of transactions, then executing them together on Ethereum in one single transaction. This splits the gas fees across all of the sub-transactions and is quicker, since Ethereum throughput maxes out at 15-30 transactions per second. (Far lower than other chains like Aptos.) There are two main types of Ethereum rollups: optimistic and zero-knowledge. (See where we’re headed?)
Since these rolled-up transactions are happening off the network, they are not verified like other Ethereum transactions as they happen. Instead, they must be verified as a batch when the rollup transaction is processed back on Layer 1.
Optimistic rollups optimistically assume that nobody is trying to lie. They submit all of the transactions to Ethereum without verification. But users stake ETH in order to use the rollup, and can also contest transactions. If they incorrectly contest a valid transaction or are caught submitting an invalid one, they lose their staked ETH.
Zero-knowledge rollups replace this system with zero-knowledge proofs. The rolled-up batch is compressed into a simple list of changes to Ethereum’s state that are required to put the transactions into effect. A smart contract is deployed on Ethereum which maintains the state of the ZK rollup. A ZK rollup node submits a ZK proof to this smart contract, verifying that the proposed changes to the network state are the actual results of running the batched transactions. The smart contract then executes the transactions on Ethereum. Transacted funds are controlled by the smart contract on Ethereum, while computation and storage happen off-chain.
There are several advantages of zero-knowledge over optimistic rollups. First, zk-proofs are trustless, as opposed to the more vulnerable dispute system. Instead of trusting incentivized actors, pure math verifies the validity. Second, the compression of transaction data into a list of proposed changes makes the time-to-finality of transactions much faster and reduces fees substantially. Third, optimistic rollups often require waiting periods of up to a week before funds can be withdrawn as a security measure. This can be bypassed through the use of a liquidity provider, but this costs a fee. Withdrawal waiting periods on ZK rollup are far shorter (hours or minutes) because the only constraint is the time for the verification of the validity proof.
The most prominent ZK rollup is zkSync, developed by Matter Labs. zkSync uses a trustless ZK rollup to scale Ethereum to massive throughput and sub-second transaction times, without compromising Ethereum’s security or finality. Nodes are divided between Validators, who run the consensus and generate proofs, and Guardians, who monitor for censorship activity, a less computationally-intensive role which can be performed on a normal computer. Validators are incentivized with a percentage of transaction fees (paid in any transacted token), while Guardians are rewarded in the ZK Sync native token.
Recently, zkSync has been upgraded to zkSync Era (formerly zkSync 2.0). Era upgrades the existing rollup (now known as zkSync Lite) from just transactions, to a complete zero-knowledge EVM, enabling a far wider range of uses based on smart contracts. zkEra is currently in the Fair Onboarding Alpha stage of its roadmap. This period allows certain projects to test their dapps on zkSync Era, with limited token bridging and continued audits, bug bounties, and testing. We’ll cover ZK EVMs in depth in our next article.
Pontem Network is a product studio building foundational dApps for Aptos. Our products include: Pontem Wallet, Liquidswap (the first DEX/AMM for Aptos), Move Playground, a Move browser code editor, the Move IntelliJ IDE plugin for developers; and the ByteBabel Solidity-Move code translator -- the first implementation of the Ethereum Virtual Machine for Aptos.