[分享课程]zk, zkVM, zkEVM and their Future

https://mirror.xyz/msfew.eth/Yl64OK3lLG48eJpVB3GxqFEhmWOm6yMlAo9sc1VrQP4

04/2022

TL; DR

Zero-knowledge proof, which can guarantee computational integrity, correctness and privacy, has a lot of use cases in blockchain scaling and privacy.
zk-SNARK and zk-STARK have their own advantages, and the combination of these two has more potential.
zkVM empowers applications with zero-knowledge proofs, and zkVM can be categorized by instruction sets in mainstream, EVM, or newly-built ones.
EVM compatibility includes EVM compatibility, equivalence, and specification-level compatibility.
zkEVM is an EVM-compatible and zero-knowledge proof-friendly environment. It can be divided into native-based and compiler-based solutions.
Native-based zkEVM is the future of Ethereum and blockchain.
A general zkVM supports the Solidity lang is the future of Web3.

0. Zero-knowledge Proof

An easy-to-understand definition to zero-knowledge proofs:

You are in elementary school. The teacher is the verifier, and you, the student, are the prover. How do you prove that you know the formula for solving a quadratic equation? That would require a math exam.

The teacher will give you 10 random questions related to quadratic equation, and if you have mastered them, you can do them all. In the process, you don’t memorize or write down the exact formula, but the teacher can simply verify your comprehension of quadratic equation.

In fact, this is what Tartaglia and Cardano (yes, that’s the name) did when they were fighting over who was the discoverer of the formula for the solution of third-degree equations of the type x 3 + bx = c. Neither of them wanted to tell the other what their formula was, but by doing the random problem sets, it was easy to verify, without revealing knowledge in the process, that they had that knowledge.

What is the use of zero-knowledge proofs? The use is that the whole process saves computational power and compresses space on the blockchain, while also perserving privacy, in line with the trustless and cryptography nature of blockchain.

1. SNARK and STARK

The term “zk” in the blockchain space is usually not a true zero-knowledge proof, but often a validity proof. These “misuses” are appeared in some parts of this article to avoid confusion over related terms.

In the current blockchain world, zk is arguably the most cutting-edge and optimal solution for scaling (validity proof without zk) and privacy (true zk). zk is widely used in projects such as Tornado.cash, ZCash, zkSync, zk.money, Filecoin, and Mina.

The current technical solutions are divided into two main categories: SNARK and STARK. The S in STARK stands for scalable, which implies that the statement being proved has repeated structure, whereas SNARKs support arbitrary circuits that are preprocessed to enable succinct proofs. The technical practice of SNARK is more dominant, and STARK is mainly adopted by StarkWare on a large scale in production. Here is a comparison between them:

In terms of meme, STARK is also better than SNARK (😊, Star Wars, Star Trek).

If SNARK is the future of Ethereum 2.0, then STARK will be the future of Ethereum 3.0. In all, STARK’s advantages are:

Lower gas (scalable)
Larger batch size (scalable * 2)
Faster proving (scalable * 3)
No trusted setup (the generated parameters are only valid for the current application, and need to be re-set up if there are changes)
Post-quantum security

But the proofs generated by STARK are much larger, and quite a bit larger. Due to some limitations of like WASM, which may require additional operations at build time (this example uses SNARK though). Mir gave an AIR-based STARK practice at Starky before, as part of Plonky2 (the relationship between Plonky2 and Starky is complicated…). Personally, I think the large size can be optimized by various approaches, but the time complexity of the algorithm itself is hard to compress further.

These zero-knowledge proof technologies can be combined to build more powerful applications. For example, Polygon Hermez uses SNARK to verify the correctness of STARK, thereby reducing the gas fee when the proof is finally settled.

To sum up, SNARK and STARK are both excellent zero-knowledge proof technologies, each with its own advantages, and their combination has more potential.

2. zkVM

The aforementioned Tornado.cash and zk.money are both similarly zero-knowledge proof applications that only support transfer operations, but not general-purpose computation. By analogy, these applications have only the functionality of Bitcoin, and are nowhere near as Turing-completeness and DApp ecosystem as Ethereum (smart contracts on Bitcoin doesn’t make it well).

zkVM is a virtual machine that guarantees secure and verifiable trustworthiness by zero-knowledge proofs. zkVM is simply the machine that you enter the old state and program, and it return the new state in a trusted manner. It allows all applications to be given the superpower of zero-knowledge proofs.

Miden’s presentation at ETH Amsterdam gave a good overview of what zkVM really is in one chart:

zkVM’s Pro:

Easy to use: Developers can use zkVM to run programs in a trusted manner without learning cryptography or developing with zk circuits (does not mean there is no barrier)
Generality: zkVM can generate proofs for any program or computation.
Simplicity: A relatively small number of constraints can describe the entire VM (no need to repeatedly generate the entire VM’s circuit).
Recursive: Free recursive feature. As with generality, verification of VMs can be performed by VMs. This is fun, for example you can put a zkVM inside a zkVM, similar to what StarkWare says the concept of L3.

zkVM’s Con:

Specificity in computational architecture: Not all zero-knowledge proof systems can be used for zkVM.
Performance issues: Circuits need to be optimized, and optimizations can be performed for specific computations.

There are three main types of zkVMs, with their instruction sets in parentheses: mainstream (WASM, RISC-V), EVM (EVM bytecode), and ZK-Optimized (new instruction sets optimized for zero-knowledge proofs, such as Cairo and zkSync’s). Below is a comparison of the types based on Miden’s presentation at ETH Amsterdam:

Much of what the zero-knowledge proof development ecosystem does is mostly allow developers to use Circom libraries (and snarkyjs for that matter) or other newly created languages (Leo or Cairo, which have odd limitations) to do zk DApp development, but it’s not as straightforward and easy to learn as using Solidity on Ethereum.

In addition, there are many projects, such as zkSync, Scroll, or several under the Polygon umbrella that are trying to make zkEVM or other zkVMs.

3. EVM

EVM is an Ethereum virtual machine, which can also be understood as the execution environments for running smart contracts.

For several years, various blockchains have been trying to be EVM-compatible to access the Ethereum development ecosystem. For this concept, EVM compatibility, equivalence and some other definitions have been derived.

EVM Compatibility: Solidity and other language level compatibility.
EVM Equivalence: compatibility at the EVM bytecode level.
EVM Specification-level Compatibility: what is commonly referred to as true zkEVM. In most cases, it’s even backwards compatible optimized supersets, providing account abstraction (i.e. each account is a smart contract) and other features that Layer1 EVMs do not provide.

4. zkEVM

Let’s take a look at zkEVM. By definition, zkEVM is an EVM-compatible and zero-knowledge proof-friendly virtual machine that guarantees the correctness of programs, operations, and inputs and outputs.

To do zkEVM for general-purpose computing, there are two main difficulties to be solved:

a) Circuit Complexity

Different contracts require different circuits to be generated, and these circuits are “complex”.

This relies on various optimizations, such as Aleo (but it is not a direct ZK… Just to have an example of the optimizations) to compute proof concurrently through distributed clusters, or to accelerate it through various hardware optimizations.

b) Design Difficulty

zkEVM is not only a refactoring of the EVM, but also a refactoring of the entire state transition of the Ethereum using zero-knowledge proof techniques.

When the EVM was designed, it was not expected that zkEVM would be done later, which made it very difficult to implement. The result is that there are two routes. Both of which are in the diagram.

Or in terms of VM architecture, it looks like this (super thanks to Scroll Tech for the original summary!). The Opcode refers to the EVM Opcode. The StarkWare part is to use Warp to convert Solidity to Cairo contracts, or to write contracts directly in Cairo for a good development experience and a better set of tools.

At the developer and user level, I think these solutions are basically indistinguishable, but in terms of infrastructure, the further to the right EVM is, the better the compatibility and seamless access to infrastructure such as Geth, but also the slower the development.

5. zkEVM and zkVM

The existence of zkEVM I see as a way to refurbish and patch the Ethereum ecosystem and add to its prosperity, while the existence of zkVM is not necessarily an enhancement to Ethereum, but also has greater potential.

StarkNet’s Cairo VM may not be the perfect zkVM I thought it would be, but it can do a lot more than EVM or zkEVM, and more than just extend the functionality at the EIP level. Machine learning models can be run on Cairo VM, and there is even a machine learning modeling platform being built on StarkNet right now.

Compared to zkEVM, a zkVM is much easier to build (no need to worry about EVM technical debt), much more flexible (no need to worry about EVM updates), and much easier to optimize (hardware and software optimization of circuits and provers is much easier and cheaper than building zkEVM).

Of course, one of the smallest but fatal drawbacks of zkVM is that if zkVM does not support EVM compatibility (at the Solidity language level), then it is very difficult for zkVM to have the most complete and mature Web3 development ecosystem as EVM does.

zkVM is perhaps the bigger trend, allowing vertical optimization of EVM to become a horizontal expansion of the EVM ecosystem, going beyond the limitations of EVM.

6. zkVM’s Future

What if there was a universal zkVM that would allow smart contracts in all programming languages, not just Solidity, not just Cairo, but Rust, C++, Go, to run with zero knowledge proofs? (Stellar tried, but failed.)

As what @kelvinfichter said: Why zkEVM if zkMIPS? As what @KyleSamani said: EVM is a bug not a feature. Why zkEVM if zkVM?

zkVM like Winterfall, Distaff or Miden VM are not very developer friendly. Nervos has RISC-V VM, but Nervos does not use zero-knowledge proof technology.

The optimal solution is to build a WASM or RISC-V zkVM, preferably with support for Rust, Go, C++, or even Solidity (zkSync can help on that!). If there is such a general zkVM, then it would be a zkEVM killer.

The number of Web3 developers is about 0.07% of all developers, which means that the number of Solidity developers is actually even smaller than 0.07%. The number of Cairo and Leo developers is even smaller. Such a perfect zkVM targets almost 100% of developers, and any developer in almost any language can get a perfect zero-knowledge runtime environment.

If Web3 and Crypto ever rule the world, I don’t think it will be the EVM ecosystem that takes over 100% of all developers, but rather all developers will slowly be convert to Web3 and Crypto developers. This is the beauty of the universal zkVM.

Native zkEVM is the future of the blockchain.

General zkVM is the future of Web3.