An Exploration of zkEVM

10 min readApr 10, 2024

Abstract

Before we delve into the topic, let’s take a moment to explore what zkEVM is, the theoretical foundations of zero-knowledge proofs, and how it’s rapidly advancing in various Layer 2 projects. This article aims to compare the characteristics of ZK rollups currently utilizing zkEVM, assuming the reader has a basic understanding of Ethereum, Layer 2 solutions, and zero-knowledge proofs.

Scaling Ethereum
ZK-SNARK
What is zkEVM?
The architecture of zkEVM
Types of zkEVM
Optimization
Conclusion

1. Scaling Ethereum

The Blockchain Trilemma refers to the difficulty of simultaneously achieving decentralization, security, and scalability within a blockchain system. The concept of the Blockchain Trilemma was introduced around 2014, yet it remains an unresolved challenge for Layer 1 solutions to this day. Various strategies have been proposed to enhance the scalability of Layer 1, and in the case of Ethereum, it is considered to offer the highest level of decentralization and security among blockchains. However, it faces challenges in scalability due to high transaction fees and slow processing speeds.

One of the most critical solutions for enhancing Ethereum’s scalability is Layer 2, which improves speed and reduces costs by processing transactions off-chain. Layer 2 solutions can be categorized into several types, such as Rollups, Plasma, and Validium, based on their validation methods and data availability. Among these, Rollups are a method that posts transaction data on-chain.

Rollups can be broadly classified into ZK-Rollups and Optimistic Rollups, with the main distinction being whether a validity proof is submitted. Optimistic Rollups operate on a ‘presumption of innocence,’ not submitting any proof of validity on Layer 2 and instead passively accepting challenges. In contrast, ZK-Rollups actively submit a validity proof for the Layer 2 data each time it is posted to a Layer 1 block.

This article will focus specifically on Universal ZK-Rollups, which use zkEVM or zkVM to generate proofs.

2. ZK-SNARK

Before delving into zkEVM, it’s important to understand ZK-SNARK, which is primarily used in zkEVM to generate validity proofs. ZK-SNARK stands for Zero-Knowledge Succinct Non-interactive Argument of Knowledge, a proof construction where one can prove possession of certain information, e.g., a secret key, without revealing that information, and without any interaction between the prover and verifier. It satisfies both properties of ZK (Hiding) and SNARK (Non-interactive), allowing for succinct verification.

Terms and Concepts Explained

Setup
A agreed-upon setup where the prover and verifier each have parameters for proof generation and verification, respectively.

Prover
Converts the function they wish to prove into an arithmetic circuit. This circuit is then transformed into an Oracle (usually a polynomial) form. The Oracle is cryptographically compiled into a specific form of a Commitment value, which is then submitted to the verifier.

Verifier
The verifier computes the proof value received from the prover through a verification logic, and then decides whether to accept or reject the proof.

ZK-SNARK can be divided into two parts: one that represents the validity of a program as a set of constraints, known as a Circuit, and another that cryptographically transforms the Circuit into a Proof value.

Characteristics of ZK-SNARK

There are various schemes within ZK-SNARK, each with its own advantages and disadvantages. Therefore, when selecting a proving scheme for zkEVM, it’s important to carefully consider the form of zkEVM and the trade-offs involved. The characteristics to consider mainly include:

1.Setup:
Trusted setup per circuit — Requires a different trusted setup for each circuit (e.g., Groth16).
- Universal Trusted Setup — A single trusted setup can be used for all circuits (e.g., KZG).
- Transparent Setup — Does not require a trusted party, a transparent setup (e.g., FRI).

2.Proving cost: The complexity involved for the prover to generate the proof.

3.Verifying cost: Since ZK rollup verification typically occurs on-chain, it directly affects gas fees.
- Proof size — The size of the proof relative to the size of the circuit (e.g., KZG — O(1), IPA — O(log N)).
- Verifier time — The time complexity of the verifier’s proof verification logic (e.g., KZG — O(1), IPA — O(N)).

Cryptosystems and Proving Schemes

The proving schemes can be categorized based on the cryptosystem they utilize. The cryptographic foundation of each scheme affects its cost (proof size and verifier time).

Pairing based: Schemes that utilize Bilinear pairing on elliptic curves (e.g., KZG).
Discrete log based: Schemes that rely on the Elliptic Curve Discrete Logarithm Problem (ECDLP) (e.g., Bulletproofs).
Hash based: Schemes that use hashing (e.g., FRI).

Furthermore, these crypto systems require a setup to generate the parameters used in the protocol. The setup can be broadly classified into three types:

Non-universal setup: Requires a trusted party and a unique setup for each circuit.
Universal setup: Requires a trusted party, but parameters generated from a single setup can be reused across all circuits.
Transparent setup: Does not require a trusted party.

Since the security of the parameters in a trusted setup depends on the trusted party, it is considered less secure compared to a transparent setup. Moreover, a non-universal setup requires a new setup for each circuit, making transparent, universal, and non-universal setups preferred in that order.

Below is a table illustrating the complexity and setup method of each scheme.

Taxonomy of the proving schemes | source: zk-learning.org

Thus, given the varying complexities and setup methods of each scheme, it is crucial to select a scheme that best matches the characteristics of the protocol in use.

3. What is zkEVM?

Generating a proof for zero-knowledge proofs requires a significant amount of computation, but advancements in ZKP technology, such as Lookup and Recursion, have made it possible to efficiently generate proofs for larger circuits.
First-generation ZK-Rollups like Polygon Hermez v1.0 were app-specific rollups, capable of handling only certain functions like transfers.
The progress in ZK technology has laid the groundwork for building Universal ZK-Rollups.
Universal ZK-Rollups utilize zkEVM, which can prove the computational validity of operations on the Ethereum Virtual Machine.

Now, it’s time to take a closer look at zkEVM.

4. The architecture of zkEVM

As mentioned earlier, ZK-SNARK is a proving method that generates a proof from a set of constraints, known as a Circuit, using cryptographic protocols. In zkEVM, the program can be considered the Ethereum Virtual Machine (EVM) itself, and the constraints related to the logical validity of the EVM can be considered the zkEVM Circuit.

zkEVM proving data

zkEVM is a Circuit that proves whether all transactions have been executed correctly, essentially verifying the correctness of the EVM’s Execution Trace. The aspects to be proven include whether the words in the EVM are 256 bits, whether the results of Opcode executions are correct, and whether values in the stack and memory have been read and written correctly, covering all aspects of EVM execution validity.

The input data that the zkEVM Prover works with are as follows:
- Input: Ethereum’s current World state t, the new World state t+1, and L2 transactions.
- Witness: Execution trace.

Using these data, the prover verifies the validity of all execution traces, including the Codehash, Gas usage, and data read & written at the Program Counter and Stack Pointer, along with Opcodes and all other aspects of execution validity

Example — ADD

The figure above is an example demonstrating the validity of an ADD operation. In the zkEVM Circuit, there are three main types of constraints for each step of the execution trace:

Step context
Constraints related to the context, such as the Program Counter and Stack Pointer, and gas usage. In the example, it verifies whether the Program Counter and Stack Pointer have both increased by one and whether 3 units of gas have been consumed.
Case switch
This checks the Opcode used in that step. Every Opcode exists as a Selector, and it verifies that only one Opcode was used in each step.
Opcode specific witness
These are additional constraints for issues that need to be verified for each Opcode. In the example, it checks whether the size of the Carry generated by the addition operation is 2¹²⁸.

Moreover, to determine if the values at each step have been correctly read and written in the STACK, MEMORY, and STORAGE, a Lookup argument is used. The Lookup argument is a method that proves the existence of a certain value in a Lookup table.

zkEVM structure

The structure of zkEVM varies from project to project, but one of the factors that make it possible to prove such large circuits is the aforementioned Lookup argument.
Lookup is an innovative method that does not directly process operations within the Circuit but instead proves the existence of values in precompiled tables.
Most zkEVMs essentially have an EVM circuit to prove the correctness of the EVM trace and several precompiled Lookup tables for the values they wish to prove. For example, computing the Keccak hash function used in Ethereum within the Circuit would be costly, but using a precompiled Keccak table for Lookups can reduce the constraints.
Thus, zkEVM typically consists of the main EVM circuit for verifying the Execution trace and auxiliary circuits for Lookups.

Another crucial mission in zkEVM is how to reduce the number of proofs, which varies depending on the proving scheme used. In the case of Halo2 (IPA) used by ZCash, proofs are accumulated through recursion using the Pasta curve. Meanwhile, Scroll, which uses Halo2 (KZG), employs the BN254 curve that does not support cycling, necessitating another Aggregation circuit to combine the proofs.

5. Optimization

Thus, zkEVM leverages the characteristic of ZK-SNARKs — minimal proof size and verification cost — to submit validity proofs to Layer 1, effectively addressing scalability issues. However, the primary challenge facing ZK-Rollups that use zkEVM is the high proving cost. Efforts are underway to optimize zkEVM from various angles to overcome this. Optimization approaches can be broadly classified into two categories:

Theoretical Optimization: Research aimed at theoretically optimizing existing schemes or designing more efficient proving schemes. Recent developments include research on Folding techniques, like Hyper Nova and Protostar, and new Lookup schemes such as MVLookup and Baloo.
Engineering Optimization: This includes software-level optimizations such as memory optimization and parallel processing, as well as hardware optimizations extending to GPUs, FPGAs, and ASICs.

6. Types of zkEVM

The different types of ZK-EVMs | source: Vitalik’s blog

Vitalik Buterin’s classification system for zkEVM divides it into four categories:

Type 1: Ethereum-compatible zkEVMs that are compatible all the way up to the Ethereum consensus layer. This type inherits the security and all infrastructure of Ethereum, offering significant benefits. However, the proving cost is considerably high. Taiko is currently developing a Type 1 zkEVM.
Type 2: EVM-compatible zkEVMs. These involve changes made for ZK, such as replacing Ethereum’s MPT with a ZK-friendly structure like ZK-Trie, while still maintaining compatibility at the EVM level. Scroll is a leading project in this category.
Type 3: This type removes ZK-unfriendly opcodes or structures, meaning Ethereum DApps cannot be onboarded directly without some modifications.
Type 4: Utilizes its own ZK-friendly language and virtual machine, making it incompatible with Ethereum. However, it offers the advantage of much faster proof generation compared to other types. StarkNet and zkSync are prominent examples of this type.

From Type 1 to Type 4, compatibility with Ethereum decreases, but the benefit is a reduction in the cost of generating proofs.
Although Type 1 zkEVMs, which are fully compatible with Ethereum, have not yet been commercialized, it’s likely that the future will bring their use as optimizations in computation, such as Lookup and Recursion, become sufficiently advanced.

7. Conclusion

ZK-Rollup is still an emerging technology, and there is a long way to go. Despite numerous attempts to optimize computation, the generation of proofs still requires high costs, and the hardware requirements are significant.
Moreover, the technical complexity of this field presents a high barrier to entry, resulting in a shortage of experts who can lead this area and a lack of support.
Nonetheless, it is undeniable that ZK-Rollup is developing at a very rapid pace and represents one of the promising solutions contributing to the scalability of Ethereum.