Exploring Popular zkEVM Solutions: AppliedZKP, Matter Labs, Hermez, and Sin7Y

Since the technology explosion of the Ethereum ZK-Rollups (ZKR), various ZKR-based Layer2 schemes have blossomed, including decentralized exchange (DEX) Loopring that utilizes the order-list solution, the AMM-featured DEX ZKSwap, and the privacy-supporting zk.money. These ZK-Rollups schemes have enriched the Ethereum Layer2 ecosystem with Layer1 security, which can be called the "most" secure Ethereum scaling schemes. However, these schemes can only support specific application scenarios. They cannot support common contract development because zero-knowledge proof (ZKP)'s general circuit itself is very complicated and the design and implementation can be very complex due to the limitation of Ethereum gas fees/data. It can be said that zkEVM is the crown jewel of Ethereum scaling schemes.

At present, multiple teams are working on the research of zkEVM. Our 5th article compares and contrasts current zkEVM solutions proposed by AppliedZKP, Matter Labs, Hermez, and Sin7Y. To begin with, let's take a look at the basic process of zkEVM.

• Firstly, execute transactions in the EVM executer (execution requires transaction-related pre_state + tx, etc.) to get post_state
• Input pre_state, tx, and post_state to zkEVM, and the proof will be obtained after execution
• Upload the proof and public input (key transaction data) to the L1 contract for verification

zkEVM, the focus of this article, is roughly divided into two categories according to the objects of zk proof:

• Proof of native EVM, with zk implementation of the native opcode. Teams using this scheme include AppliedZKP, Sin7Y, and so on.
• Proof of custom EVM, with zk implementation of custom opcodes. Teams using this scheme include Hermez, Matter Labs, and so on.

Before introducing the zkEVM scheme of each team, it is necessary to talk about the basic model of EVM, which is mainly of the relationship between operation and state, as shown in the following figure:

The opcode of the EVM needs to interact with Stack, Memory, and Storage during execution. There should also be some contexts, such as gas/program counter, etc. Stack is only used for Stack access, and Memory and Storage can be accessed randomly. The definition of these opcodes can be found on Ether VM.

AppliedZKP divides proofs into two types:
1. State proof, used to check the correctness of the state transition in Stack/Memory/Storage.
2. EVM proof, used to check that the correct opcode is used at the correct time, the correctness of the opcode itself, the validity of the opcode, and all the abnormal conditions (such as out_of_gas) that may be encountered during the execution of the opcode.

The former proof checks the state, and the latter checks the operation. It also requires bus mapping to connect the two proofs, which does not use Merkle Tree but plookup k-v mapping.

The framework of zkEVM is as follows:

Evm proof uses the slot method to separate opcode, the operation values of opcode, and the context. As shown in the figure below, a circuit is composed of multiple slots. q_op is the selector, o_n is the opcode value, c_n is the context, and v_n is the operation value.

The zkEVM scheme by Matter Labs is a different design. It compiles the contract code written in solidity and vyper languages into Yul, and then translates the Yul code into bytecode supported by zkEVM through LLVM.

A few days ago, Matter Labs open-sourced its Yul compiler, which can compile the intermediate code YUL into bytecode of a custom syntax, and the bytecode can be run in zkEVM (Link to the source code).

The circuit implementation of Matter Labs uses TinyRAM to implement ordinary opcodes, such as ADD, PUSH, etc.; opcodes that consume a lot of gas, such as SHA256/keccak, implement this circuit especially; finally, Matter Labs uses recursive aggregation technology to aggregate all proofs into one proof.

The zkEVM program of Hermez is also refreshing. Hermez designed the uVM framework, which is similar to that of the Intel X86. It has modules such as ROM/RAM, and uses Main State Machine to synchronize the state between the modules. The uVM framework uses Register instead of Stack, which accomplishes the same work. Since the number of instructions used by Register-based VMs is less than that of Stack-based VMs, using Register can improve execution efficiency. Furthermore, uVM uses a large number of cryptographic tools to achieve the completeness of zk.

Hermez's most innovative design is to translate the EVM instruction set into an intermediate instruction (micro opcode), which can be executed in uVM. And it uses a large number of plookup algorithms to improve the efficiency of proof and verification.

Our zkEVM plan draws on the above three designs and separates state verification and execution verification into state proof and evm proof.

Where:
state proof:
• Stack proof verifies Stack operations such as pop and push
• Memory proof verifies memory operations such as mload and mstore
• Storage proof verifies storage operations such as sload and sstore.
evm proof:
This tentatively uses the slot/custom gate method to implement the opcode of evm.

A slot implements all opcodes and can express any opcode. There will be multiple opcodes in the contract, and you can use the selector to select which opcode to activate. The final contract circuit will contain multiple rows of slots to fully support the EVM opcode.

Nevertheless, while designing and implementing this project, there are still many problems to be determined and resolved, such as:

1. As for native and customized EVMs, which is better?
2. For Arithmetic ops, is the lookup table better designed separately or publicly?
3. How to constrain the op of a variable?
4. How many custom circuits are suitable? If the number is too large, recursive aggregative must be used, which will greatly increase circuit design complexity.
5. Should we consider using Register instead of Stack to reduce circuit scale and improve execution efficiency of zkEVM?
6. Given that zkEVM has not been officially launched yet, should the BLS12-381 curve be used directly?
7. Custom slot needs to process all Arithmetic ops calculations, including correct calculations and incorrect calculations. The op type is specified by the selector, so how to specify the correct or incorrect result?
8. Can TinyRAM really optimize Arithmetic ops?
...

We will continue zkEVM research in our subsequent articles and try to find answers to the above questions. Stay tuned to Sin7Y's Twitter, Medium, and Hacker Noon accounts and join our discussions on #THIS IS WHAT'S HAPPENING IN BLOCKCHAIN.

[1] Ethereum EVM Illustrated
[2] zkEVM EVM Circuit Explore
[3] 'zkEVM' - Alex Gluchowski at ETHGlobal
[4] Compiler-yul
[5] Introducing Hermez zkEVM