Partnered With:

ZkEVM: Design challenges and solutions

Read this article in 29 Minutes

What are the design challenges of zkEVM?

Original title: zkEVM

原文作者：Ye Zhang

Ethereum enthusiasts

We believe zK-Rollup will be the "hot property" -- its cost advantage and extremely high security will put Layer 2 scalability solutions to shame. However, existing zK-rollup implementations are application-specific, so it is difficult to build composable generic DApps within a ZK-rollup, nor to migrate existing applications. We introduced zkEVM to generate zero-knowledge proofs for general EVM validation. This way, we can build a zK-rollup that is fully EVM-compatible so that existing Ethereum applications can easily migrate to this ZK-rollup.

In this article, we have identified the design challenges and why zkEVM is possible today. We also provided more concrete, intuitive insights and outlined how to build zkEVM from the ground up.

background

zk-Rollup It is recognized as the best scalability solution for Ethereum. Not only is it comparable to Ethereum Layer 1 in terms of security, but it is also the top Layer 2 solution in terms of transaction finalization speed (click here for a full comparison).

In the medium to long term, as ZK-SNARK technology continues to evolve, ZK-ROLLup will lead all application scenarios. - Vitalik Buterin

The basic principle of ZK-rollup is to package a large number of transactions into a Rollup block and generate a concise proof for that block down the chain. The smart contract at Layer 1 then simply validates the proof and applies the new state directly, without re-executing the transactions. This can save an order of magnitude in gas costs because the cost of validation of the proof is much lower than the cost of recalculation. Another benefit is that storage space can be saved through data compression (that is, only a minimal amount of data can be stored on the chain for validation).

While ZK-Rollup is secure and efficient, its use is still limited to payments and swaps. General purpose DApps are difficult to build for two main reasons:

- First, if you want to develop dApps within a ZK-rollup, you need to use a special language (i.e., R1CS) to write the logic for all your smart contracts. The language has complex syntax and requires users to be proficient in zero-knowledge proofs.

- Second, the existing ZK-rollup implementation does not support composability 1. As a result, at Layer 2, different ZK-rollup applications cannot interact with each other, severely damaging the composability of DeFi applications.

In short, ZK-Rollup is currently not developer-friendly and has limited features. That's the biggest problem we're trying to solve. We wanted to provide the best developer experience by directly supporting native EVM validation, and by enabling composability at Layer 2, existing Ethereum applications can be migrated to ZK-rollup intact.

Build a generic dApp in zK-rollup

There are two ways to build a generic dApp within zK-rollup:

- One is to build dedicated circuits (" ASics ") for different DApps.

- The other is to build general-purpose "EVM" circuits for executing smart contracts.

"Circuit" means the procedural representation used in zero-knowledge proofs. For example, if you want to prove hash(x) = y, you need to rewrite the hash function in circuit form. Circuit form only supports very limited representations (that is, R1CS only supports addition and multiplication). As a result, writing programs in circuit languages is difficult -- you can only use addition and multiplication to build all the program logic (including if else, loops, and so on).

The first approach requires developers to design dedicated "ASIC" circuits for different Dapps. This is the most traditional way to use zero-knowledge proofs. Custom circuit design helps reduce the cost of each dApp. However, this also creates composability problems because circuits are "static" and a high reliance on circuit design knowledge leads to a poor developer experience 2.

The second method does not require any special design, nor does it require a great deal of developer expertise. The underlying concept behind this machine-based proof is that any program will eventually run on the CPU. Therefore, we only need to build a general-purpose CPU circuit to validate low-level CPU operations. We can then use this CPU circuit to verify any program execution. For the purposes of this article, the program is the smart contract and the CPU is the EVM. However, this method has not been widely adopted in the past few years because of its high cost. For example, even if you only want to prove one operation. add You still have to bear the cost of the entire EVM circuit. If you have thousands of operations in your execution trace, the prover will incur 1000 times the cost of EVM circuit3.

Recently, there are many researches on optimizing zero-knowledge proofs using these two methods, including (I) proposing new zero-knowledge proof-friendly primitives & NBSP; Poseidon hashes (Poseidon hashes are 100 times more efficient in circuits than SHA256); (ii) Continuously improve the efficiency of general-purpose verifiable virtual machines, such as &nbSP; TinyRAM Like that; (iii) More and more common optimization techniques, such as Plookup, as well as faster cryptography libraries.

In our previous article, we proposed designing an "ASIC" circuit for each dApp and having them communicate through a cryptographic promise. However, based on feedback from the community, we have changed the focus of our research and will focus on using a second approach to build general-purpose EVM circuits (the so-called "zkEVM"). ZkEVM brings exactly the same development experience as Layer 1. Instead of leaving design complexity to developers, we use custom EVM circuit designs instead to solve efficiency problems.

Design challenges for zkEVM

ZkEVM is hard to build. Although this intuition has been clear for years, no one has yet managed to build a native EVM circuit. Unlike TinyRAM, zkEVM is more challenging to design and implement for the following reasons:

- First, EVM has limited support for elliptic curves.Currently, EVM only supports BN254 pairs. EVM is difficult to prove recursion because it does not directly support cyclic elliptic curves. It is also difficult to use other proprietary protocols in this setting. The validation algorithm must be EVM friendly.

- Second, EVM word size is 256 bits.While EVM runs on 256-bit integers (like most normal virtual machines that run on 32-bit to 64-bit integers), zero-knowledge proofs "naturally" run on a field of bits. Doing "mismatch domain arithmetic" in a circuit requires proof of range, which in turn adds about 100 constraints to each EVM operation. This increases the EVM circuit size by two orders of magnitude.

- Third, EVM has many special opcodes.Different from traditional virtual machines, EVM has many special opcodes, such as CALL , and error types related to the execution environment and GAS. This creates new challenges for circuit design.

- Fourth, EVM is a stack-based virtual machine.SyncVM (zksync) and The Cario (Starkware) architecture defines its IR/AIR in a register-based model. They built a specialized compiler to compile smart contract code into a new zero-knowledge proof-friendly IR. This method is language compatible, not native EVM compatible. Either proving stack-based models or directly supporting native toolchains becomes more difficult.

- Fifth, the ethereum storage layout carries high costs.Ethereum storage layout is highly dependent & NBSP; Keccak And a giant. MPT4. Neither of them is zero-knowledge proof friendly and will incur high proof cost. For example, the circuit size of the Keccak hash is 1000 times larger than the Poseidon hash. However, if you replace the Keccak hash with another hash, you can introduce some compatibility issues into the existing Ethereum infrastructure.

- Sixth, machine-based proofs come with high costs.Even if you can handle all of the above, you still need to find an efficient way to put them together to get a complete EVM circuit. As I mentioned in the last section, even things like add Such simple opcodes may require you to cover the cost of the entire EVM circuit.

Why is zkEVM possible now

Thanks to significant advances made by researchers, more and more efficiency issues have been addressed over the past two years, and the cost of proving zkEVM is finally no longer an obstacle! The most important technological progress is reflected in the following aspects:

- Use of polynomial commitment.For the past few years, most compact zero-knowledge proof protocols have used R1CS, and PCP queries are encoded in application-specific Trusted Setup. This tends to increase the size of the circuit, making many custom optimizations impossible because each constraint must have a degree of 2 (Bilinear pairing allows only one exponential multiplication). With a polynomial commitment scheme, you can increase your constraints to any degree through universal setup and even transparent setup, greatly increasing the flexibility of back-end choices.

- Appearance of lookup table parameters and custom widgets.Another important optimization is the use of lookup tables. This optimization was first proposed in Arya, then in Plookup Is implemented in. For zero-knowledge proof-unfriendly primitives (i.e., AND AND XOR alleles), lookup tables can be a lot easier. Custom widgets can efficiently implement higher-order constraints. TurboPlonk And & have spent UltraPlonk Elegant program syntax is defined, making it easier to use lookup tables and define custom widgets. This helps greatly in reducing the cost of EVM circuits.

- Recursive proof is becoming more and more feasible.In the past, recursive proofs were costly because they relied on special pairwise cyclic elliptic curves (i.e., mnt-based structures). This creates a high computational cost. However, a growing number of techniques make recursion proof possible without sacrificing efficiency. For example, Halo You can also use special inner product parameters to amortize recursive costs without pairing friendly curves. Aztec demonstrated that proofs of existing protocols can be aggregated directly (lookup tables can reduce the cost of non-native domain operations, thereby reducing the size of validation circuits). The same circuit size now enables more functionality.

- Hardware acceleration is improving proof efficiency.To our knowledge, we have built the fastest GPU and ASIC/FPGA accelerators for proof programs. Our paper on ASIC proof program has been accepted by the top computer science conference ISCA this year. Our GPU prover than NBSP; The implementation of Filecoin is about five to 10 times faster and can greatly improve the computational efficiency of the validator.

How does zkEVM work and build?

In addition to strong intuition and technical improvements, we had to figure out what we needed to prove and come up with a more concrete architecture. More technical details and comparative analysis will be presented in a later article. In this article, we introduce the overall workflow and some of the core concepts.

Developer and user workflow

Developers can implement smart contracts using EVM compatible languages and deploy compiled bytecode on Scroll. Users can then send transactions to interact with deployed smart contracts. Users and developers will have the same experience they have at Layer 1. However, gas charges will be significantly lower and transactions will be pre-confirmed on Scroll in real time (withdrawal only takes a few minutes).

ZkEVM workflow

Even if the external workflow remains the same, the underlying processing at Layer 1 and Layer 2 is completely different:

- Layer 1 relies on re-executing smart contracts.

- Layer 2 relies on the validity verification of zkEVM circuits

Let's explain in detail how transactions at Layer 1 differ from those at Layer 2.

At Layer 1, the bytecodes for deployed smart contracts are stored in Ethereum Storage (store items). Transactions will spread across a peer-to-peer network. For each transaction, each full node needs to load the corresponding bytecode and execute it on EVM to get the same state (the transaction will be the input data).

At Layer 2, the bytecode is also stored in the storage item and the user operates in the same way. Transactions are sent down the chain to a centralized zkEVM node. ZkEVM then not only executes the bytecode, but also generates a succinct proof that the status has been updated correctly since the transaction was made. Finally, the Layer 1 contract validates the proof and updates the status without re-executing the transaction.

Let's take a closer look at the implementation and see what zkEVM ultimately needs to prove. In native execution, EVM loads the bytecode and executes the opcodes in the bytecode one by one from scratch. Each opcode can be thought of as performing three steps :(I) reading an element from the stack, memory, or storage item; (ii) Perform calculations based on these elements; (iii) Write the result to the stack, memory, or store item 5. For example, add The opcode requires reading two elements from the stack, adding them up and writing the result to the stack.

Therefore, it is obvious that zkEVM's proof needs to include the following aspects (corresponding to the execution process) :

- Bytecode loads correctly from the permanent storage entry (you are running the correct opcode loaded from an address)

- Opcodes in the bytecode are always executed one by one (the bytecode is executed sequentially and no opcodes are omitted or skipped)

- Each opcode executes correctly (all three suboperations in each opcode are executed correctly, R/W + calculation)

ZkEVM design highlights

When designing the architecture for zkEVM, we needed to take steps to address these three requirements.

1. We need to design a circuit for a cryptographic accumulator.

In order to function as a "verifiable memory," we need some kind of technology to prove that the reading process is accurate. Cryptographic accumulators can do this more efficiently. 6. Let's take the Merkle tree. The deployed bytecode is stored as a leaf node in the Merkle tree. The verifier can then use a concise proof to verify that the bytecode is correctly loaded from an address (that is, merkle path in the validation circuit). For Ethereum storage, we need this circuit to be compatible with both Merkel-Patricia and Keccak hash functions.

2. We need to design a circuit to associate bytecode with actual execution tracing.

Moving bytecode to static circuits presents a problem: jump Such conditional opcodes (as opposed to loop and if else statements in smart contracts) can jump anywhere. The jump destination is uncertain until someone runs the bytecode with a particular input. This is why we need to verify the actual execution trail. An execution trace can be thought of as "expanded bytecode", containing opcodes in the order of actual execution (that is, if you jump to another location, the trace will contain the target opcode and location).

The prover will directly provide the execution trail as the witness data of the circuit. We need to prove that the execution trace is indeed "expanded" by a particular bytecode with a particular input. The idea is to force the values of program counters to be consistent. For the problem of uncertain destination, the solution is to let the prover provide all the data. You can then use lookup parameters to efficiently check for consistency (that is, prove that the opcodes with accurate global counters are contained in the "bus").

3. We need to design circuits for each opcode (to prove that the reads, writes, and calculations in each opcode are correct).

This is the most important part -- proving that each opcode in the execution trace is correct and consistent. If you just put everything together, it's expensive. The important optimization ideas here are:

- We can divide R/W and the calculation into two proofs. A proof puts all the elements used by the opcode into the bus. Another proof will prove that the evaluation of the elements on the bus was performed correctly. This dramatically reduces the cost of each part (i.e., you don't need to consider the entire EVM store when generating the computational proof). In a more detailed specification, the former is referred to as "state proof" and the latter as "EVM proof". Another finding is that lookup declarations can effectively handle "bus mapping."

- We can design more degree customization constraints for each opcode (i.e., we can split an EVM Word into multiple data blocks for more efficient processing). We can choose whether to "open" a constraint with a selector polynomial as required. This avoids the cost of consuming the entire EVM circuit for each operation.

The architecture, originally proposed by the Ethereum Foundation, is still in its early stages and under active development. We are working closely with the Ethereum Foundation to find the best way to implement the EVM circuit. So far, we have defined the most important features of the EVM circuit and implemented some opcodes (using UltraPlonk syntax in the Halo2 library) (see here). More details will be covered in a follow-up article. We recommend that interested readers read this document. The development process will be transparent. This will be a completely open source design with the help of the entire community. I hope more people will join in and make a contribution.

What else can zkEVM bring us?

ZkEVM is much more than Layer 2 expansion. We can think of it as a straightforward way to extend Ethereum Layer 1 with Layer 1 validation. This means that you don't need any special Layer 2 to extend existing Layer 1.

For example, you can use zkEVM as a full node. The proof can be used to directly prove transitions between existing states. Without having to migrate anything to Layer 2, you can directly prove all Layer 1 transactions! More broadly, you can use zkEVM to generate concise proofs for the entire Ethereum, as Mina does. The only thing that needs to be added is proof recursion (that is, embedding the block's validation circuit into zkEVM) 7.

conclusion

ZkEVM provides the same experience for developers and users, and can reduce costs by orders of magnitude without sacrificing security. An architecture has been proposed to build zkEVM in a modular manner. This architecture takes advantage of the latest breakthroughs in zero-knowledge proofs to reduce costs (including custom constraints, lookup parameters, proof recursion, and hardware acceleration). We look forward to seeing more people contribute to the zkEVM community and brainstorm with us!

Note:

1. Starkware announced composability in its September 1, 2021 announcement (click here to view the announcement).

2. The circuit is fixed and static. For example, when implementing a program as a circuit, you cannot use a variable upper bound loop. The upper limit must be fixed at the maximum value. The circuit cannot handle dynamic logic.

3. The cost of EVM circuits is explained in detail for readers' understanding. As mentioned above, circuits are fixed and static. Therefore, EVM circuits need to contain all possible logic (this volume is contained only & NBSP; add 10000 times the circuitry). Which means, even if you just want to prove it. Add, you still have to cover the cost of all the logic that might be included in the EVM circuit. In other words, the cost is magnified by 10,000 times. In execution tracing, you need to prove a series of opcodes, and each opcode carries a high cost.

4. EVM itself is not closely bound to Merkel-Patricia Tree (MPT). Currently, MPT is only used to store Ethereum state. It's easy to change one. Verkle tree replaces MPT).

This is a highly simplified abstraction. Technically, the list of "EVM states" is longer, including program counters, gas margin, call stack (all of the above plus the address and static of each call in the stack), a set of log and transaction range variables (hot slot, refund, self-destruct). We can also directly support composability by introducing additional identifiers for different calling environments.

6. Because of the large storage capacity, we use accumulator for storage. The memory and stack can use editable Plookup (we can effectively implement "RAM" this way).

7. It is not easy to add a complete recursive proof to a zkEVM circuit. The best way to do this recursion is to use cyclic elliptic curves (that is, Pasta curves). We need to introduce some sort of "wrapping" process to make recursion verifiable on Ethereum Layer 1.