Detailed proof of validity Rollup and Cairo VM technical characteristics

Original: Scaling Ethereum Efficiently

Translation and proofreading: "Starknet Chinese Community"

overview

• Proof of Validity Rollup is the most potential way to increase the throughput of Ethereum in a safe and decentralized way; zkEVM and Cairo VM (CVM) are the two virtual machines (VM) used in Rollup of Validity Proof type.
• zkEVM focuses on Ethereum compatibility at the expense of performance and scalability.
• The Cairo VM adopted by Starknet prioritizes performance and scalability over compatibility.

Rollups were a hot topic this year about scaling Ethereum. Among various types of Rollup, we believe that Validity Proof Rollup (hereinafter referred to as VR, or zk-rollup) is the most promising expansion solution to increase the throughput of Ethereum in a safe and decentralized way. The core of this expansion scheme is the use of validity proofs for verifiable calculations. Here's how it works:

• Unlike processing each transaction on the Ethereum mainnet, the operator executes the transaction in an off-chain environment. The off-chain environment is L2, the operating layer running on top of Ethereum.
• After the bulk transaction processing is complete, the L2 operator returns the result to the Ethereum state, along with a proof of validity to verify the integrity of the off-chain execution. This proof guarantees that all transactions in the same batch are valid and autonomously verified by the on-chain verification contract. This operation allows Ethereum to apply the result to its state.

Validity Proof Rollup

Please note: Proof of Validity Rollups are often mistakenly called Zero-Knowledge Rollups (zkRollup), which is not accurate. Most Validity Proofs Rollup does not employ zero-knowledge proofs, nor are they used to ensure privacy. Therefore, the term "Validity Proof Rollup" is more accurate.

off-chain virtual machine

Before we go any further, we need to answer the first question: what is a virtual machine (VM)? In short, a virtual machine is an environment in which programs can run, such as a Windows operating system running on a Mac. The VM transitions between states after performing computations on some input. The Ethereum Virtual Machine (EVM) is the VM that runs Ethereum smart contracts.

A zero-knowledge virtual machine (zkVM) is a program execution environment that, together with program output, generates easily verifiable proofs of validity. Proof of validity is used to prove that a program has been executed correctly. When the term "zkEVM" is used, it usually refers to a Rollup that runs the Ethereum Virtual Machine (EVM) and can attest to the execution of the EVM. This terminology can be misleading because the EVM itself cannot generate these proofs; instead, the proofs are produced by a separate prover mechanism that takes the result of the EVM's execution as its starting point. In addition, the above proofs are all related to validity and have nothing to do with privacy. Therefore, it cannot be called a zero-knowledge proof to be precise. For consistency, the traditional term "zkEVM" is still used in this article.

While all Proof-of-Validity Rollups aim to scale Ethereum with Proof-of-Validity, different schemes make different choices about how the VM executes off-chain transactions. Many proofs of validity Rollup chose to replicate the EVM design (hence the name "zkEVM rollup"), attempting to replicate Ethereum on an L2 rollup. Starknet uses Cairo VM (CVM), a brand new VM designed to optimize the efficiency of proof of validity.

The above two methods have their own advantages and disadvantages and trade-offs, but zkEVM sacrifices performance for Ethereum compatibility, while Cairo VM puts performance above compatibility and prioritizes scalability.

Understand how zkEVM works

zkEVM is a proof-of-validity rollup designed to fully introduce the Ethereum experience on the L2 blockchain. The purpose is to replicate the Ethereum developer environment into Rollup. With zkEVM, developers do not need to adjust the code or abandon the original EVM tools (and smart contracts) when writing or porting smart contracts to expansion solutions.

This approach has a key flaw, which reduces the scalability of validity proofs. Due to the focus on being compatible with Ethereum, zkEVM is slower and more resource intensive. Unlike CVM, EVM is not designed with proof efficiency in mind. This limits the use of optimizations in improving efficiency and scalability, ultimately affecting the overall performance of the system.

Provability of the EVM

The core challenge of the zkEVM approach lies in the ingrained original blueprint of the EVM, which was not originally designed to run in a proof-of-validity environment. Therefore, if all the effort is put on realizing the functions of Ethereum, the full potential of the validity proof cannot be released, resulting in unsatisfactory efficiency. This inefficiency ultimately drags down the overall performance of the system. Compatibility of EVM with validity proofs is hampered by:

• The EVM uses a stack-based model, while the validity proves to be more efficient for a register-based model. The stack-based nature of the EVM makes it inherently more difficult to prove the correctness of its execution and provides direct support for its native toolchain.
• The storage layout of Ethereum relies heavily on Keccak and large Merkle Patricia trees, both of which are non-validity proof-friendly and bring a huge proof burden. For example, Keccak is very fast for x86 architectures (typically used to run the EVM), but takes 90k steps to prove (requires special built-ins). Whereas Pedersen (a zero-knowledge-friendly hash function) requires only 32 steps. Even with recursive compression, using Keccak in zkEVM still consumes a lot of prover resources, and the cost is ultimately borne by the user.

Therefore, various types of zkEVM are designed to provide different levels of support for Ethereum tools, but the higher the compatibility of zkEVM with Ethereum, the lower the performance. (see end of article for more zkEVM types)

Understand how Cairo-VM works

The zkEVM solution has invested a lot of development time in "making EVM suitable for Validity Proof Rollup", prioritizing compatibility over long-term performance and scalability. There is another option: adopt a new dedicated virtual machine, and add an additional layer to support Ethereum tools. That’s the step Starknet is taking, launching a permissionless proof-of-validity Rollup in November 2021. Starknet is the first proof-of-validity Rollup that implements a general-purpose smart contract platform in a fully composable network.

Starknet adopts Cairo-VM (CVM) and creates the high-level language Cairo of the same name. Cairo-VM is designed for efficient generation of validity proofs of program execution.

With Cairo (VM and programming language) it is possible to:

1. Proof of optimization effectiveness, each instruction has a valid algebraic expression
2. A modern Rust-like language for writing provable programs
3. Intermediate expressions (Sierra) between high-level Cairo language and Cairo assembly (VM instructions), which can execute Cairo code efficiently

Developing a completely new language can be tailored to specific needs, can include features that were not available before, and meet new needs.

Cairo and coding pluralism

In order to create a proof of the validity of some computation, that computation must first be expressed as a series of mathematical constraints describing the computation. The process is complex, the difficulty lies in optimizing calculations for efficiency, and specific tools are required.

The Cairo language was designed to simplify this task so that StarkEx can easily add functionality and complex business logic. Cairo programs are compiled into algebraic machine code, a sequence of numbers, executed by a single, fixed VM. With Cairo, the complex process of generating mathematical constraints describing computations (very tricky for validity proofs) is abstracted and expressed as a fixed set of constraints (less than 50 constraints in total). This allows developers to extend applications with validity proofs by writing code in a familiar syntax without understanding the underlying mathematics and infrastructure.

Starknet's commitment to innovation is evident in its approach to code pluralization. Cairo adopts STARK technology to achieve optimal extension functions, not limited to writing contracts with Cairo local environment. Developers can also choose the most suitable method:

• Local coding in Cairo: Inspired by Rust, Cairo 1.0 is more in line with developers' usage habits and safer, and writing program logic becomes easier and less error-prone.
• Solidity Compatibility: Solidity developers can write code that supports Cairo VM. This approach provides a developer experience similar to Ethereum and supports the migration of Solidity smart contracts to Starknet. There are two ways to implement migration:
• Translation: Translation is the process of converting the source code of one programming language into another language. The Nethermind team built the Warp transpiler for transpiling Solidity code to Cairo. Warp makes Solidity smart contracts portable to Starknet, making it effectively a fourth type of zkEVM. It is currently used to translate and deploy Uniswap contracts with minimal changes.
• zkEVM on Starknet: The Cairo VM can be used to attest to the execution of another VM. Kakarot is a zkEVM written in Cairo that can be used to run Ethereum smart contracts on Starknet. Cairo VM and zkEVM are not in competition, rather than choosing between the two, it's better to have both!

Although Cairo has not been around for a long time, according to TVL rankings, Cairo is the fourth most popular smart contract programming language, with a valuation of over $350 million.

Summarize

zkEVM aims to replicate the Ethereum developer environment into Rollup and allow developers to use familiar Ethereum tools. But this approach limits the potential for validity proofs and is resource intensive.

The Cairo VM, designed for validity proofs, is not subject to the limitations of the EVM. Cairo VM supports Cairo 1.0. Inspired by the Rust language, Cairo 1.0 is more in line with developer habits and safer, forming a powerful tool designed to use STARK to prove efficient expansion of Ethereum.

It's exciting to see how Cairo develops every week, and the options for developers like Kakarot zkEVM and Warp are growing. With Starknet dApps in production, demonstrating the power of Cairo, we firmly believe that in the future, Cairo will spawn outstanding projects that have never been seen before.

Three paths for SATRK expansion have been outlined above, and there will no doubt be more innovations to come in the coming months. Developers now have unprecedented control over scaling blockchains.

zkEVM type

Vitalik divides zkEVM into four main types:

• The first category is fully equivalent to Ethereum: does not change any part of the Ethereum ecosystem.
• The second type of fully equivalent EVM: Compatible with existing dApps, and makes some adjustments to the design of Ethereum to speed up proof generation.
• The third category is roughly equivalent to EVM: supports most EVM opcodes, and removes some functions that zkEVM is difficult to implement (such as precompilation and hash functions).
• The fourth type of equivalent high-level language: write smart contract code in Solidity/Vyper, and translate it into a valid proof-friendly language.