ZKEVM is a programmable virtual machine based on ZK technology. It can generate a zero-knowledge proof (zk proof) for all operations performed by the virtual machine to prove the correctness of the virtual machine's operations. For the introduction of several implementation schemes of ZKEVM and the comparison of advantages and disadvantages, you can refer to the article of V God:The different types of ZK-EVMs; If you want to know more design details, you can also read PSE's ZKEVM scheme (native-level):privacy-scaling-explorations/zkevm-specsPolygon's ZKEVM design (bytecode-level):Polygon zkEVM Documentation; Sin7y's ZKEVM design (language-level):OlaVM: An Ethereum compatible ZKVM. Regardless of the solution, zk needs to be used to constrain all behaviors of the VM, including:

• Execute contract calculation logic

• perform memory access

• Perform hash calculations

• Perform world state updates

• ...

As we all know, zk has great application prospects in the field of computing compression; no matter how complex the original calculation is, its verification process is very efficient, which is the basic skill of all zk algorithms. Therefore, zk can play a good role in the calculation part (such as contract logic, hash calculation, etc.) Some data needs to be placed in memory in advance, and then fetched when performing calculations.

Since most VMs read and write memory, the correctness of these memory access operations has to be constrained (for example, the consistency check that the data read from a certain address is the same as the data written last time); for The memory access constraints themselves are not complicated (there are fewer cases), but due to the high number of memory accesses, the order of the polynomial is very high, which makes memory-related constraints prove to be time-consuming.

first level title

text

byEVMimage description

text

text

text

•  MSTORE(x,text

•  MSTORE8(x,y): Starting from address x, write 8 bytes of y (lower bit start) Interested readers can findEVM Playgroundtext

exist

existOlaVMIn Section 5.3.5, you can see the design principles of Memory constraints (OlaVM memory-related instructions are similar to EVM).

In OlaVM, all RAM operations form an independent table, and the content in the table consists of two types: memory and storage. Here, we only focus on constraints on memory. The types of memory operations can be roughly divided into three categories:

• Init operation

• write operation

• read operation

There are three scenarios that trigger Init, namely the transformation of ctx, the change of type, and the change of addr; when any one of the scenarios is triggered, constraints are required,The operation type is w (write), v (value) is 0。 

When the above three scenarios are not triggered, it needs to be restricted according to the current operation type;

• If it is a w (write) operation, it is necessary to constrain that clk is incremented (call the rangecheck module), and the written value v is correct (call copy constraints, in OlaVM, all values ​​​​of memory instructions come from registers).

• If it is an r(read) operation, it is necessary to constrain clk to increase (call the rangecheck module),The read value is the same as the last written value。

Some possibility improvements (more zk friendly)

• For the Init operation, do you need to constrain the initialization value of a memory address to 0?

I don't think it is necessary to constrain the initialization operation; in fact, for any address, you can constrain its first access must be a write operation, not a read operation; and if it is a write-once memory model, this restriction will be natural Therefore, if the memory model of the virtual machine is changed to a write-once model, the access constraints on memory will be reduced.

• For the read operation, can the corresponding constraints be avoided, that is, to avoid verifying that the read value is consistent with the last written value?

Since the read-write memory of the memory type defined by the VM itself cannot be guaranteed, the value of this memory address has not been modified before the VM reads the value of this memory address, so an equality check needs to be added, as shown in the following figure:

It can be seen from this that the core reason for this constraint is that the memory model is to read and write memory, and the value of the address may be rewritten. Therefore, if you try to use read-only memory (write only once), then you do not need to write in memory. Constraints to achieve the above consistency constraints.

Note: This may increase the difficulty of virtual machine implementation, because this is an uncommon memory model; and, we should not first define an advanced DSL on this virtual machine, because this language will be somewhat unfamiliar to Dapp developers Friendly needs to be eliminated at the compiler level, making these unfriendly and invisible to developers. Therefore, if the above memory model is adopted, the constraints of the memory module will only be the constraints for the write operation, that is, use copy constraints to ensure that the written value is correct.no constraints： 

• The value read is equal to the value written because the memory can only be written once

• The read clk is greater than the write clk, because it can only be written first and then read

• WeChat public account: Sin7Y

refer to

ethereum_evm_illustrated, page 51

about Us

Sin7y was established in 2021 and is composed of top blockchain developers. We are both a project incubator and a blockchain technology research team, exploring the most important and cutting-edge technologies such as EVM, Layer2, cross-chain, privacy computing, and autonomous payment solutions.

WeChat public account: Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon