Everything you need to know about ZK-Rollups (Part2)
This post is the second part of our ZK-Rollup series, where we discussed Zero Knowledge Proof basics, SNARK and STARK implementations. If you haven’t read Part 1 of this series, it won’t be easy to follow along with Part 2.
Introduction
To explain how zero-knowledge rollups work we need to examine their structure. The typical ZK-rollup is built on Ethereum, maintained by two on-chain smart contracts and an off-chain virtual machine.
1. Smart Contracts
ZK-rollups are controlled by two on-chain smart contracts that represent the core functions of a rollup:
- Main contract: maintains the rollup’s states by storing rollup blocks and monitoring state updates. This contract is also charged to track fund deposits/withdrawals.
- Verifier contract: verifies the validity proofs submitted by block producers.
2. OFF chain Virtual Machine
In this section, we explain how ZKEVM works, how each circuit communicates with the others using a lookup table or a constraint table and how Opcodes are executed. Next, we explained the different types (according to Vitalik Buterin) and the dilemma that arises between the compatibility of each type with the EVM and its performance. Finally, we end with an explanation of ZKVM, its type, followed by a comparative study between those two off-chain virtual machine solutions.
2.1. ZK-EVM
ZkEVM is a virtual machine that executes EVM smart contracts in a way that is compatible with ZKproof computation.
2.1.1 ZK-EVM workflow
In Layer 2, the bytecode of the deployed smart contracts is stored in the storage. Users send their transactions to a centralized zkEVM node (off-chain). zkEVM generates succinct proof to prove the states are updated correctly after applying each transaction. Finally, this proof (validity proof) will be verified by the layer 1 smart contract and layer 1 states will be updated without re-executing the transactions. The following figure schematizes the workflow of zk-evm.
Circuits architecture
Now let’s review the general circuit architecture.
To understand circuit architecture, let’s talk about a table before. A table contains inputs and their corresponding outputs. When we want to prove, we only need to query the corresponding table which the circuit uses. This table looks like the following figure.
To ensure the correctness of the table, we have a circuit for each table, and each circuit has some special polynomial constraints on the table to ensure that the table is completely correct. If it is a read/write operation of memory/stack/storage, the EVM circuit will query the state table. If it is some operation involving opcode, the EVM circuit will query the bytecode table. Similarly, tx and block will query tx table and block table respectively.
The general circuit architecture is shown in the following figure.
To ensure circuits are completely and correctly executed, each of them will have their proof. The number of circuits in this architecture depends on the ZKEVM type, which we will talk about in the next lines.
Now let’s focus on the State Circuit. The State Circuit implements the constraints of Stack, Memory, and Storage. This circuit is used by State proof: State/memory/stack ops have been performed correctly. State proof does not check if the correct location has been read/written. The prover can pick any location here and in the EVM proof confirm it is correct.
The EVM circuit is responsible for all constraints around opcode execution, and it is proven by EVM proof. The EVM proof checks that the correct opcode is called at the correct time. It checks the validity of these opcodes. It also confirms that for each of these opcodes the state proof performed the correct operation.
Opcode execution
The EVM reads the required relevant state via Bus Mapping.
2. The EVM executes the opcode.
3. The EVM writes back to the new state via Bus Mapping.
4. State proof is responsible for the consistency and correctness of the Bus Mapping read and write data, and the EVM proof is responsible for the correctness of the execution of EVM opcodes.
These interactions are shown in the following figure.
2.1.2 ZK-EVM types
For Vitalik Buterin, we have four types of ZK-EVM:
Fully Ethereum-equivalent
This type of ZKEVM does not change any part of the Ethereum system to make it easier to generate proofs. It does not replace hashes, state trees, transaction trees, precompiles, or any other in-consensus logic, no matter how peripheral. It is perfectly compatible with Ethereum.
Fully EVM-equivalent
This type of ZKEVM strives to be exactly equivalent to EVM, but not quite equivalent to Ethereum, as slight modifications have been made to be compatible with existing applications, to facilitate the development and speed up proof generation. It makes changes to data structures that hold things like the Ethereum state.
To reduce the more time the ZKEVM previous type takes to produce proofs, this type removes parts of the Ethereum stack that rely on needlessly complicated and ZK-unfriendly cryptography.
Projects: Scroll’s ZK-EVM.
Almost EVM-equivalent
It focuses on specific changes to the EVM by removing a few features that are exceptionally hard to implement in a ZK-EVM implementation. In this context building applications is easier and the proof generation process is much faster. This evolution was possible thanks to the placement at the top of the list of precompiles, and a different observation of the treatment of smart contracts code, memory, and stack.
Projects: Scroll and Polygon.
High-level-language equivalent
This type of zkevm is for high-level language like solidity, vyper etc. It takes smart contracts source code written in these high-level languages and compiles them to some language that is explicitly designed to be ZK-SNARK or ZK-STARK friendly. Thus, it allows us to avoid proving all the different parts of each EVM execution step, just starting directly with the higher-level code. that would therefore reduce costs and improve proof-generation time.
However, some applications will not work correctly because some of the smart contract addresses are not the same in this type of zkevm, or these applications use handwritten EVM bytecode in some parts for efficiency that is not supported by this type of system.
Project: ZKSync.
2.1.3 ZK-EVM dilemma
Despite all these different types of ZKEVM, a dilemma arises. The more EVM-compatible the ZKEVM type, the less efficient it is, and the more efficient the type, the less EVM-compatible it is. This dilemma is due to the optimization made to speed up the computation time of the proofs.
2.1.3 ZK-EVM general computation difficulties
To do zkEVM for general-purpose computing, there are two major difficulties to be solved:
Circuit Complexity
Different contracts require different circuits to be generated, and these circuits are “complex”. This relies on various optimizations such as proof computing concurrently through distributed clusters or accelerating it through various hardware optimizations.
Design Difficulty
zkEVM is not only a refactoring of the EVM, but also a refactoring of the entire state transition of the Ethereum using zero-knowledge proof techniques.
2.2. ZK-VM
ZKVM is a virtual machine that guarantees secure and verifiable trustworthiness by zero-knowledge proofs. It executes a high-level program (program writes with high level language like solidity) and provides new state and proof. This proof can be used by anyone to verify that the program was executed correctly. This state machine looks like this.
Despite its ease to use, its simplicity relative to the small number of constraints to describe the entire VM, its ability to generate the proof of any computation or program and its advanced techniques for reducing transaction costs such as recursion, ZKVM cannot be used by all zero-knowledge proof systems and presents a performance issue because circuits need to be optimized, and optimizations can be performed for specific computations.
The following figure presents the different types of ZKVM with their instruction sets in parentheses and the comparative characteristics.
The following figure represents the best VM solutions and the steps through which a high-level program passes to be understood by the VM.
2.3. ZK-EVM vs ZK-VM
Benefits
- Much easier to build because there is no need to worry about EVM technical debt.
- More flexible because EVM updates do not pose any problems.
- Much easier to optimize because hardware and software optimization of circuits and provers is much easier and cheaper than building zkEVM.
Downsides
- ZKVM does not support EVM compatibility (at the Solidity language level), then it is very difficult for ZKVM to have the most complete and mature Web3 development ecosystem as EVM does.
ZKVM is perhaps the bigger trend, allowing vertical optimization of EVM to become a horizontal expansion of the EVM ecosystem, going beyond the limitations of EVM.
3. Nodes
A typical ZK-rollup has a supernode, a single operator (aka coordinator), as their sequencer in charge of:
- Transaction Executions
- Batching: Aggregates transactions into batches.
- Proof generation: They also produce validity proofs for each state transition to prove the correctness of their changes and verify it by the Rollup contract on the main chain.
- Layer-1 submissions:
- Submit a summary of the changes required to represent all the transactions in that batch rather than sending each transaction individually.
- Submits a zero-knowledge validity proof: When the operator submits a new state root to Ethereum, the blockchain’s state can only change when the operator proves that the root represents valid updates to the rollup’s state. This prevents operators from making incorrect changes to Ethereum’s state.
- Submit blocks to L1.
The operator is the only entity allowed to produce L2 blocks, submit transactions to the ZK-rollup contract and send state transitions which essentially acts as a two-factor protection layer.
Some of the zk-rollups use a single operator, while others rotate their role among a set of proof-of-stake validators. Current solutions to ZK-Rollups are mostly centralized which can directly affect the order of transactions and sometimes trigger censorship. But there are several suggestions to make the operator decentralized, like sequencer auction, random selection from PoS set, and DPoS voting.
4. Validity Proof
Phase A: Proof generation
Step 1: Before accepting transactions, the operator will perform the usual checks including sender and receiver accounts, public key …etc.
Step 2 & 3: Once the ZK-rollup node has enough transactions, it aggregates them into a batch and compiles inputs for the proving circuit.
Step 4: The proving circuit computes the validity proof by “looping” over each transaction and performing the same checks the operator completed before processing the transaction.
- The process repeats for every transaction; each “loop” creates a new state root from updating the sender’s account and a subsequent new root from updating the receiver’s account. As explained, every update to the state root represents one part of the rollup’s state tree changing.
- The ZK-proving circuit iterates over the entire transaction batch, verifying the sequence of updates that result in a final state root after the last transaction is executed. The last Merkle root computed becomes the newest canonical state root of the ZK-rollup.
Step 5: The transaction contains succinct proof that all these batched transactions are processed faithfully, changing the contract from state1 to state2. This provides cryptographic guarantees that the new state resulted from the addition of valid transactions.
Step 6: After the proving circuit verifies the correctness of state updates, the L2 operator submits the computed validity proof to the verifier contract on L1.
Phase A: Proof verification
A smart contract on the L1 chain performs an operation on the validity proof and checks public inputs that form part of the proof. The results of this operation determine if batched transactions are validated and posted to the main chain.
If the proof satisfies the circuit (i.e., it is valid), it means that there exists a sequence of valid transactions that transition the rollup from the previous state to a new state.
5. Transactions
Like the other scaling solutions, there are various types of transactions used with ZK Rollup
In the next section we will not explore all these types of transactions, we will just focus on a simple example that shows the flow of a transfer transaction between two users using ZK-rollup
Now, suppose that Alice wants to send 5 ETH to Bob using a zk-rollup and that Bob already has an account on Layer 2.
To enter the system the user needs to transfer their funds to the ZK-Rollup. The assets are sent to a smart contract (ZK-Rollup smart contract)
Step 1:
Alice first sends the ETH that she wants to deposit on the ZK-Rollup and that can be used on Layer 2 at the address of the smart contract.
Step 2:
The deposit is stored in a queue to be inserted by a prover. When the accounts are updated by the prover on the smart contract, an index is assigned to Alice’s public key in the Merkle tree of accounts, and the amount she paid is added to the same index in the balance tree.
Step 3:
Once the prover is chosen, the prover receives the transactions from a transaction pool as with a classic blockchain. Thus, Alice just sends her transaction to the prover via the peer-to-peer network, saying she wants to send 5 ETH to Bob’s rollup account by including his index.
The prover receives the fees included in all transactions they prove. After a fixed amount of time or when they reach the maximum number of transactions, they use the Zero-Knowledge arguments to prove the update of the Merkle trees’ root. They prove that the transition from the old state of the accounts to the new one is correct and is included in the transition from the previous state to the new one.
If a user wishes to withdraw their funds from the ZK-Rollup, they can submit their exit request to the operator any time.
Step 4:
Once in a while, the operator bundles the collected transactions together and generates a ZK proof. Then, he submits the transactions and the proof to the verifier.
The prover sends the updated accounts to the smart contract via a single transaction “. The trees can always be reconstructed outside the blockchain by looking at the transaction history. When the smart contract receives the transaction, it verifies that the proof provided is correct by using the previous transactions and account states as the public input. If the proof is correct, it can update the trees’ root.
At this moment, Alice can detect the change and see that her transaction was included on the blockchain.
Step 5:
Bob sends a new transaction on Layer 1 to ask the smart contract to withdraw his funds.
Once it’s done, the transactions are finalized
6. Compression techniques
ZK-Rollup publish compressed transaction data to Ethereum. All the transactions fields can be compressed except the signature.
The account states of Zk-Rollup are managed by a Merkle Tree, whose leaf node contains user status information. The index location of the leaf node might indirectly relate to this account information. Therefore, the Ethereum account address can be modified from an address with 20 bytes to simply 3 bytes.
We can also compress the transfer amount data. The amount in Ethereum is represented by a 256-bit large integer. If we assume that the minimum unit of transfer in the system is 0.001 ETH, and the transfer amount is represented by 4 bytes, we can support the transfer of 0.001–4,294,967.295 ETH, which is enough for the general system.
The actual handling fee will fluctuate within a certain range, so we can also set a minimum unit for the handling fee. Then 1 byte is used to represent the handling fee of 0.001–0.255 ETH is enough.
Similarly, we can assume that the number of transfers of an account based on normal usage will not number in the tens of thousands, so it is almost enough to use two bytes to represent the nonce.
The length of each field in the above transaction is only for reference.
By compressing transaction related data, ZK-rollups significantly increase the number of transactions processed per block and reduce the cost of publishing data on-chain.
7. Fees
To complete transactions on a blockchain, users have to pay gas fees. ZK-rollups try to solve the problem of high gas fees and empower users to pay less.
Gas fees work differently on L2 and are influenced by the following costs
- State write: ZK-Rollup reduce costs by batching transactions to submit on the mainnet and dividing costs across multiple users.
- Data publication: The cost paid on each transaction is proportional to how much calldata will be posted on-chain. With each transaction on Ethereum, an amount of data is published as calldata. Costs depends on the amount of bytes in the Calldata : 16 gas for non-zero bytes calldata 4 gas for zero bytes calldata
- L2 operator fees: fees paid to the rollup operator as a reward for the computation steps he accomplished while processing transactions.
- Proof generation and verification: Zero knowledge proofs require intense computation and mathematical proofs for the verification process which cost around 500,000 gas for zk-SNARK’s proof.
8. Projects
There are multiple implementations of ZK-rollups that increase scalability and security allowing developers to build products with high speeds and low fees. The table below presents the different existing ZK-Rollups projects.
Conclusion
Zk-rollups are one of the most convenient Ethereum Layer 2 scaling solutions. Their attractive improvement over typical scaling solutions lies in the mathematical conceptual foundation behind them, called ZKP, which results in cheaper and faster transactions. This type of rollup scales Ethereum efficiently through bulk transfer processing bundled into a single transaction to save data and time. Because of the benefits they offer, many popular examples of zk-rollups are being developed today to serve productive use cases across different blockchain networks.
Thanks for reading this deep dive on zk-rollups! Leave a comment below if you have any questions.