Kakarot: Exploring Starknet's EVM Compatible Road

Author: Cynic

TL;DR

• A virtual machine is a software-simulated computer system that provides an execution environment for programs. It can emulate various hardware devices, so that programs can run in a controlled and compatible environment. The Ethereum Virtual Machine (EVM) is a stack-based virtual machine used to execute Ethereum smart contracts.
• zkEVM is an EVM that integrates zero-knowledge proof/validity proof technology. It allows the execution of the EVM to be verified using zero-knowledge proofs without requiring all verifiers to re-execute the EVM. There are various zkEVM products on the market, each with its own approach and design.
• The reason for zkEVM is the need for a virtual machine that supports smart contract execution on Layer 2. Additionally, some projects choose to use zkEVM to take advantage of the EVM’s broad user ecosystem and design an instruction set that is more friendly to zero-knowledge proofs.
• Kakarot is zkEVM implemented on Starknet using Cairo language. It simulates the stack, memory, execution, and other aspects of the EVM in the form of Cairo smart contracts. Kakarot faced challenges such as compatibility with the Starknet account system, cost optimization, and stability, as the Cairo language was still experimental.
• Warp is a translator from Solidity code to Cairo code, providing compatibility at a high-level language level. Kakarot, on the other hand, provides compatibility at the EVM level by implementing EVM opcodes and precompilation.

What is a virtual machine?

To clarify what a virtual machine is, we must first talk about the computer execution process under the current mainstream von Neumann architecture. Various programs running on a computer are usually transformed by layers of high-level languages, and finally generate machine-understandable machine codes for execution. According to the way of converting to machine code, high-level languages can be roughly divided into compiled languages and interpreted languages.

A compiled language means that after the code is written, it needs to be processed by a compiler to convert the high-level language code into machine code and generate an executable file. Once compiled, it can be executed multiple times with higher efficiency. The advantage of a compiled language is that the code has been converted into machine code during compilation, so the execution speed is fast, and the program can be run in an environment without a compiler, which is convenient for users to use and does not need to install additional software. Common compiled languages include C, C++, Go, etc.

The counterpart of compiled languages is interpreted languages. An interpreted language means that the code is interpreted and executed line by line through an interpreter, and it runs directly on the computer, and the translation process needs to be re-translated every time it is run. The advantages of interpreted languages are high development efficiency and easy code debugging, but the execution speed is relatively slow. Common interpreted languages include Python, Java, Ruby, etc.

It needs to be emphasized that the language does not distinguish between compiled and interpreted types in essence, but there will be some tendencies in the initial design. C/C++ is compiled and executed in most cases, but it can also be interpreted and executed (Cint, Cling). Many interpreted languages in the traditional sense are now compiled into intermediate codes and executed on virtual machines (Python, Lua).

Knowing the execution process of the physical machine, let’s talk about the virtual machine now.

Virtual machines usually provide a virtual computer environment by simulating different hardware devices. The hardware devices that can be simulated by different virtual machines are different, but generally include CPU, memory, hard disk, network interface and so on.

Take the Ethereum Virtual Machine (EVM) as an example. EVM is a stack-based virtual machine that is used to execute Ethereum smart contracts. EVM provides a virtual computer environment by simulating hardware devices such as CPU, memory, storage and stack.

Specifically, the EVM is a stack-based virtual machine that uses a stack to store data and execute instructions. The instruction set of the EVM includes various opcodes, such as arithmetic operations, logical operations, storage operations, jump operations, etc. These instructions can be executed on the stack of the EVM to complete the execution of smart contracts.

The memory and storage emulated by the EVM are devices used to store the state and data of smart contracts. The EVM treats memory and storage as two distinct areas, and it can access the state and data of smart contracts by reading and writing to memory and storage.

The stack emulated by the EVM is used to store the operands and results of instructions. Most instructions in the EVM’s instruction set are stack-based, reading operands from the stack and pushing results back onto the stack.

In short, EVM provides a virtual computer environment by simulating hardware devices such as CPU, memory, storage and stack, which can execute the instructions of smart contracts and store the state and data of smart contracts. In actual operation, the EVM will load the bytecode of the smart contract into memory, and execute the logic of the smart contract by executing the instruction set. What EVM actually replaces is the part of the operating system + hardware in the above figure.

The design process of EVM is obviously bottom-up. First, the simulated hardware environment (stack, memory) is finalized, and then a set of assembly instruction set (Opcode) and bytecode (Bytecode) are designed according to the corresponding environment. . Although the assembly instruction set is for people to read, it involves a lot of low-level knowledge, has high requirements for developers, and is cumbersome to develop. Therefore, a high-level language is needed to shield obscure and cumbersome low-level calls, and provide developers with better experience. Due to the customized design of EVM’s assembly instruction set, it is difficult to directly use traditional high-level languages, and simply recreate a new high-level language to adapt to the virtual machine. The Ethereum community has designed two compiled high-level languages—Solidity and Vyper—for EVM execution efficiency. Solidity need not be emphasized, Vyper is an EVM high-level language designed by Vitalik after improving some of the defects in Solidity, but it has not been widely adopted in the community, so it gradually fades out of the stage of history.

What is zkEVM

To put it simply, zkEVM is an EVM that uses zero-knowledge proof/validity proof technology, so that the execution process of EVM can be verified more efficiently and at low cost through zero-knowledge proof/validity proof without requiring all verifiers to Carry out the execution process of the EVM.

There are many zkEVM products on the market, and the track is hot. The main players include Starknet, zkSync, Scroll, Taiko, Linea, Polygon zkEVM (formerly Polygon Hermez), etc., which are divided into 5 categories (1, 2, 2.5, 3, 4) by vitalik . The specific content can be viewed on Vitalik’s blog.

Why zkEVM is needed

This question needs to be looked at from two perspectives.

The initial zk Rollup attempts can only achieve relatively simple transfer and transaction functions, such as zkSync Lite, Loopring, etc. But once the sea was too difficult, people used to use the Turing-complete EVM on Ethereum. When it was impossible to create various applications through programming, people began to call for virtual machines on L2. The need to write smart contracts is one.

Since some designs in the EVM are not friendly to generating zero-knowledge proof/validity proof, some players choose to use an instruction set that is friendly to zero-knowledge proof/validity proof at the bottom layer, such as Starknet’s Cairo Assembly and zkSync’s Zinc Instruction. But at the same time, everyone is unwilling to give up the huge user ecology of EVM, so they choose to be compatible with EVM on the upper layer, which is type 3 and 4 zkEVM. Some players still insist on the traditional EVM instruction set Opcode, and focus on generating more efficient proofs for Opcode, which are Type 1 and Type 2 zkEVM. The huge ecology of EVM is divided into two.

Kakarot: A virtual machine on a virtual machine?

Why can another virtual machine be made on the virtual machine? This thing is commonplace to computer practitioners, but it may not be so obvious to users who do not understand computers. In fact, it is easy to understand. This is like building blocks. As long as the lower layer is strong enough (with a Turing-complete execution environment), building blocks can be stacked on the upper layer without limit. But no matter how many layers are built, the final execution still has to be handled by the lowest-level physical hardware, so increasing the number of layers will lead to a decrease in efficiency. At the same time, due to the different designs of different building blocks (different virtual machine designs), as the building blocks are built higher and higher, the possibility of the building blocks collapsing (running errors) is greater, which requires a higher level of technical support.

Kakarot is an EVM implemented in Cairo language on Starknet. It uses Cairo smart contracts to simulate the stack, memory, execution, etc. in the EVM. Relatively speaking, it is not difficult to implement EVM. In addition to the EVM written in Golang in Go-Ethereum, which has the highest usage rate, there are also existing EVMs written in Python, Java, Java, and Rust.

The technical difficulty of Kakarot zkEVM is that the protocol exists as a contract on the Starknet chain, which brings about two key problems.

1. Compatibility Starknet uses a completely different account system from Ethereum. Accounts in Ethereum are divided into EOA (externally owned account) and CA (contract account). However, Starknet supports native account abstraction, and all accounts are contracts. account. At the same time, due to the different cryptographic algorithms used, users cannot use the same entropy to generate the same address in Starknet as in Ethereum.
2. Cost Since kakarot zkEVM exists on the chain as a contract, it has high requirements for code implementation and needs to be optimized for Gas as much as possible to reduce interaction costs.
3. Stability Unlike using traditional high-level languages such as Golang, Rust, Python, etc., the Cairo language is still in the experimental stage, from Cairo 0 to Cairo 1 to Cairo 2 (or if you prefer, Cairo 1 version 2), the official team is still Language features are constantly being revised. At the same time, Cairo VM has not been tested enough, and the possibility of subsequent large-scale rewrites cannot be ruled out.

The kakarot protocol consists of five main components (four are written in the GitHub document, EOA is not included, this article has been adjusted for the convenience of readers):

• Kakarot (Core): responsible for executing transactions in the form of Ethereum, and providing corresponding Starknet accounts for Ethereum users
• Contract Accounts: CA in the sense of Ethereum, responsible for storing the bytecode of the contract and the state of variables in the contract
• Externally Owned Accounts: EOA in the sense of Ethereum, responsible for forwarding Ethereum transactions to Kakarot Core
• Account Registry: Stores the correspondence between Ethereum accounts and Starknet accounts.
• Blockhash Registry: As a special Opcode, Blockhash needs past block data, and Kakarot cannot directly obtain the data on the chain. This component stores the mapping relationship of block_number -> block_hash, which is written by the administrator and provided to Kakarot Core.

According to feedback from kakarot CEO Elias Tazartes, in the latest version of the team, the design of Account Resister was abandoned, and instead, a mapping from a 31bytes Starknet address to a 20-bit EVM address was used directly to save the corresponding relationship. In the future, to improve interoperability and allow Starknet contracts to register their own EVM addresses, the Account Register design may be reused.

Compatible with EVM on Starknet: What is the difference between Warp and kakarot

According to the zkEVM type defined by Vitalik, Warp belongs to Type-4, while kakarot currently belongs to Type-2.5.

Warp is a translator that converts Solidity code into Cairo code. The reason why it is not called a compiler is probably because the output Cairo is still a high-level language. Through Warp, Solidity developers can maintain the original development status without having to learn the new Cairo language. For many project parties, Warp lowers the threshold for entering the Starknet ecosystem, and does not need to use Cairo to rewrite a large amount of engineering code.

Although the idea of translation is simple, the compatibility is also the worst. Some Solidity codes cannot be translated into Cairo well. The code logic involving account system, cryptographic algorithm, etc. needs to modify the source code to complete the migration. The specific unsupported features can be seen Warp documentation. For example, many projects will distinguish the execution logic of EOA accounts and contract accounts, but all accounts in Starknet are contract accounts, and this part of the code needs to be modified before translation.

Warp is compatible at the high-level language level, and kakarot is compatible at the EVM level.

The complete rewriting of EVM and the one-by-one implementation of Opcode and Pre-compile allow kakarot to have higher native compatibility. After all, execution in the same virtual machine (EVM) is always more compatible than execution in a different virtual machine (Cairo VM). Account Registry and Blockhash Registry cleverly shield the differences under different systems and minimize the friction of user migration.

Kakarot Team

Thanks to the kakarot team for their valuable comments on this article, especially Elias Tazartes. Thank you, sir!