IOSG: Multi-dimensional analysis of the faction dispute between zkVM and zkEVM
Author: Bryan, IOSG Ventures
In the past 2022, the main focus of discussions on rollup seems to be on ZkEVM, but don't forget that ZkVM is also another means of expansion. Although ZkEVM is not the focus of this article, it is worth recalling the differences between ZkVM and ZkEVM in several dimensions:
Compatibility: Although they are all expansions, the focus is different. The focus of ZkEVM is to directly achieve compatibility with the existing EVM, while the positioning of ZkVM is to achieve complete expansion, that is, to optimize the logic and performance of dapps , compatibility is not primary. Once the bottom layer is set up, EVM compatibility can also be achieved.
Performance: Both have relatively predictable performance bottlenecks. The main bottleneck of ZkEVM is compatibility with EVM, which is not suitable for encapsulating the extra cost generated in the ZK proof system. The bottleneck of ZkVM is that the constraints on the final output are more complex due to the introduction of the instruction set ISA.
Developer experience: Type II ZkEVM (such as Scroll, Taiko) focuses on compatibility with EVM Bytecode. In other words, EVM codes at the Bytecode level and above can generate corresponding zero-knowledge proofs through ZkEVM. For ZkVM, there are two directions, one is to make its own DSL (such as Cairo), and the other is to be compatible with existing mature languages such as C++/Rust (such as Risc 0). In the future, we expect that native solidity Ethereum developers will be able to migrate to ZkEVM at no cost, and newer and more powerful applications will run on ZkVM.
Many people should still remember this picture. CairoVM has nothing to do with itself. The essential reason for dissociation from ZkEVM factional struggles is the difference in design ideas.
Before discussing ZkVM, the first thing we think about is how to implement the ZK proof system in the blockchain. Broadly, there are two approaches to implementing circuits - circuit based systems (circuit based) and virtual machine based systems (vm-based).
First of all, the function of the circuit-based system is to directly convert the program into constraints and send it to the proving system; the virtual machine-based system executes the program through the instruction set (ISA), and in the process Generate an execution trace. This execution trajectory is then mapped into constraints, which are then fed into the proof system.
For a circuit-based system, the computation of the program is constrained by each machine that executes the program. For a system based on a virtual machine, the ISA is embedded in a circuit generator and generates program constraints. At the same time, the circuit generator has limitations such as instruction set, operating cycle, and memory. The virtual machine provides generality, that is, any machine can run a program as long as the operating conditions of the program are within the above-mentioned restrictions.
image description
Image credit: Bryan, IOSG Ventures
Advantages and disadvantages:
From a developer's perspective, developing in circuit-based systems often requires a deep understanding of the cost of each constraint. However, for writing virtual machine programs, circuits are static, and developers need to care more about instructions.
From a verifier's perspective, circuit-based systems and virtual machines differ significantly in the generality of circuits, assuming the same pure SNARKs are used as backends. The circuit system produces different circuits for each program, while the virtual machine produces the same circuits for different programs. This means that in a rollup, the circuit system needs to deploy multiple verifier contracts on L1.
From the application point of view, the virtual machine makes the logic of the application more complex by embedding the memory model (memory) into the design, and the purpose of using the circuit system is to improve the performance of the program.
From the perspective of system complexity (complexity), the virtual machine incorporates more complexity into the system, such as the memory model, communication between the host (host) and the client (guest), etc., compared with the simpler circuit system .
image description
first level title
Virtual Machine Design Principles
secondary title
1. ISA instruction set
Specifies how the circuit generator works. Its main responsibility is to correctly map instructions into constraints, which are then fed into the proving system. The zk system uses RISC (Reduced Instruction Set). There are two ISA choices:
The first is to build a custom ISA (custom ISA), which can be seen in Cairo's design. In general, there are four types of constraint logic as follows.
The fundamental design focus of a custom ISA is to ensure that there are as few constraints as possible so that both program execution and verification run quickly.
secondary title
2. Compiler
Broadly speaking, a compiler gradually translates a programming language into machine code. In the context of ZK, it refers to low-level code representations compiled into constraint systems (R 1 CS, QAP, AIR, etc.) using high-level languages such as C, C++, Rust, etc. There are two methods,
Design a compiler based on existing zk circuit representations -- say in ZK, circuit representations start from directly callable libraries like Bellman and low-level languages like Circom. In order to aggregate different representations, a compiler like Zokrates (itself a DSL) aims to provide an abstraction layer that can be compiled into an arbitrary lower-level representation.
Build on (existing) compiler infrastructure. The basic logic is to utilize an intermediate representation for multiple frontends and backends.
The Risc 0 compiler is based on multi-level intermediate representation (MLIR), which can generate multiple IRs (similar to LLVM). Different IRs bring flexibility to developers, because different IRs have their own design focus, for example, some of them are optimized specifically for hardware, so developers can choose according to their own wishes. Similar ideas can be seen in vnTinyRAM and TinyRAM using GCC. ZkSync is also another example of exploiting compiler infrastructure.
In addition, you can also see some compiler infrastructure for zk, such as CirC, which also borrows some design concepts from LLVM.
In addition to the two most critical design steps above, there are some other considerations:
1. The trade-off between system security (security) and verification cost (verifier cost)
The higher the number of bits used by the system (that is, the higher the security), the higher the cost of verification. Security is reflected in key generators (such as in SNARKs representing elliptic curves).
2. Compatibility with front-end and back-end
Compatibility depends on the availability of an intermediate representation for the circuit. IR needs to strike a balance between correctness (does the program's output match the input + does the output match the proof system) and flexibility (supports multiple frontends and backends). If IR was originally designed to solve low-degree constrained systems like R 1 CS , compatibility with other higher-degree constrained systems such as AIR is difficult.
3. To improve efficiency, hand-crafted circuits are required
The disadvantage of using a general purpose model is that it is less efficient for some simple operations that do not require complex instructions.
Briefly describe some of the previous theories,
Before the Pinocchio protocol: verifiable computation was achieved, but the verification time was very slow
Pinocchio protocol: Provides theoretical feasibility in terms of verifiability and verification success rate (that is, the verification time is shorter than the execution time of the program), and it is a circuit-based system
TinyRAM protocol: Compared with the Pinocchio protocol, TinyRAM is more like a virtual machine, introducing ISA, so it gets rid of some restrictions, such as memory access (RAM), control flow (control flow), etc.
vnTinyRAM protocol: Make key generation independent of each program, providing additional versatility. Extended circuit generators, i.e. able to handle larger programs.
The above models all use SNARK as their backend proof system, but especially when dealing with virtual machines, STARK and Plonk seem to be a more suitable backend, fundamentally because their constraint system is more suitable for implementing cpu-like logic .
Next, this article will introduce three STARK-based virtual machines - Risc 0, MidenVM, CairoVM. In short, apart from both using STARK as a proof system, they each have some differences:
Risc 0 leverages Risc-V for simplicity of the instruction set. R 0 compiles in MLIR, a variant of LLVM-IR designed to support several existing general-purpose programming languages such as Rust, C++. Risc-V also has some additional benefits, such as being more friendly to hardware.
Miden aims to be compatible with the Ethereum Virtual Machine (EVM), essentially a rollup of the EVM. Miden now has its own programming language, but is also working on supporting Move in the future.
Cairo VM is developed by Starkware. The STARK proof system used by these three systems was invented by Eli Ben-Sasson, currently the president of Starkware.
Let's take a deeper look at their differences:
* How to read the above form? Some notes...
Word size - Since the constraint system these virtual machines are based on is AIR, it functions similarly to the CPU architecture. So it is more appropriate to choose the CPU word length (32/64 bits).
Memory access (memory read) - The reason why Risc 0 uses registers is mainly because the Risc-V instruction set is based on registers. Miden primarily uses a stack to store data, since AIR functions like a stack. CairoVM does not use general-purpose registers because of the low cost of memory access (main memory) in the Cairo model.
Program feed (program execution) - different methods have trade-offs. For example, for the mast root method, it needs to decode when processing instructions, so the cost of proving is high in programs with many steps
The bootloading approach attempts to strike a balance between prover costs and verifier costs while maintaining privacy.
Non-determinism - Non-determinism is an important property of NP-complete problems. Leveraging non-determinism helps quickly verify past executions. In turn, it adds more constraints, so there will be some compromises in validation.
Acceleration on complex operations - Some calculations run very slowly on the CPU. For example, bit operations like XOR and AND, hash programs like ECDSA, and range-checks... mostly native to blockchain/crypto but not CPU native operations (except bit operations). Implementing these operations directly through the DSL would easily lead to cycle exhaustion of the proof.
Permutation/multiset (permutation / multi-column combination) - used heavily in most zkVM, has two purposes - 1. Reduce the cost of the verifier by reducing the storage of the complete execution trace (execution trace) 2. Prove that the verifier knows full execution trace
At the end of the article, the author would like to talk about the current development of Risc 0 and why it excites me.
R 0 current development:
a. The self-developed "Zirgen" compiler infrastructure is under development. It would be interesting to compare the performance of Zirgen with some existing zk-specific compilers.
b. Some interesting innovations, such as field extension, can achieve more solid security parameters and operate on larger integers.
c. Witnessing the challenges seen in the integration between ZK Hardware and ZK Software companies, Risc 0 uses a hardware abstraction layer for better development on the hardware side.
d.Still a work-in-progress! Still under development!
Supports hand-crafted circuits and multiple hash algorithms. Currently, dedicated SHA 256 circuits are implemented, however not all requirements are met. The author believes that the choice of which circuit to optimize depends on the use case provided by Risc 0. SHA 256 is a very good starting point. On the other hand, ZKVM is positioned to give people the flexibility, for example, to not bother with Keccak if they don't want to :)
Recursion: This is a huge topic, and I tend not to delve into it in this report. Just be aware that as Risc 0 tends to support more complex use cases/programs, the need for recursion is more pressing. To further support recursion, they are currently working on a hardware-side GPU acceleration solution.
Dealing with non-determinism: This is a property that ZKVM has to deal with, while traditional virtual machines do not have this problem. Non-determinism can help virtual machines perform faster. MLIR is relatively better at dealing with traditional virtual machine problems, and how Risc 0 embeds non-determinism into ZKVM system design is worth looking forward to.
WHAT EXCITES ME:
a. Simple and verifiable!
In a distributed system, PoW requires a high level of redundancy because people don't trust others, so the same computation needs to be performed repeatedly to reach consensus. And by utilizing zero-knowledge proofs, state realization should be as easy as agreeing that 1+1=2.
b. More practical use cases:
In addition to the most direct expansion, more interesting use cases will become feasible, such as zero-knowledge machine learning, data analysis, etc. Compared with a specific ZK language like Cairo, Rust/C++ is more versatile and powerful, and more web2 use cases run on Risc 0 VM.
c. More inclusive/mature developer community:
Developers interested in STARK and blockchain don't have to re-learn DSL, just use Rust/C++.
