ZKEVM is a programmable virtual machine based on ZK technology. It can generate a ZK proof for all operations performed by the virtual machine to prove the correctness of the operations performed by the virtual machine. For the introduction of several implementation schemes of ZKEVM and the comparison of advantages and disadvantages, you can refer to the article of Vitalik Buterin: The different types of ZK-EVMs. If you want more design details, you can also read:

PSE’s ZKEVM Scheme (native-level): privacy-scaling-explorations/zkevm-specs

Polygon’s ZKEVM Design (bytecode-level): Polygon zkEVM Documentation.

Sin7y’s ZKEVM Design (language-level): OlaVM: An Ethereum compatible ZKVM.

Regardless of the scheme, zk is required to constrain all VM behaviors, including:

• Executing contract computational logic
• Executing memory access
• Executing hash calculation
• Executing world state updates

It is well known that ZK has great application prospect in the field of computing compression. No matter how complex the original computation is, the verification process is very efficient, which is fundamental to all zk algorithms. Therefore, ZK works well for computational parts of VM execution (such as contract logic, hash calculation, etc.). In the process of VM execution, in addition to the computing itself, there are also some memory access operations. We need to place some data in the memory in advance, and then pull it out when the computation is performed.

Since most VM memory is read/write memory, the correctness of these memory access operations has to be constrained (for example, consistency check of the data read from an address and the data written last time). The constraint on memory access itself is not complicated (with few cases), but because the number of memory accesses is very high, the order of polynomials is very high, which makes the proof of memory-related constraints relatively time-consuming.

In the ZK(E)VM scheme, we should apply zk mainly to the proof of the computation itself. For other EVM behaviors (such as memory access), we can optimize them at the VM level (such as using write-once memory), to reduce the scale of ZK constraints (avoiding the consistency check constraint of memory access).

The Design of Memory

Taking EVM as an example, the memory of EVM is a very simple block of byte array, which can store 32-byte or 1-byte data, and can also read 32-byte data.

Image Source: ethereum_evm_illustrated, page 51

In EVM, memory-related instructions are:

• MLOAD(x): Load 32 bytes of data from address x onto the call stack (stack)
• MSTORE(x,y): Starting at address x, write 32 bytes of y
• MSTORE8(x,y): Starting at address x, write 8 bytes of y (starting from low-order)

Interested readers can experience the memory and stack changes using the mentioned memory operations in the EVM Playground.

The Constraint of Memory

In OlaVM, all RAM operations form a single table, and the contents 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 broadly divided into three categories:

• Init operation

• Write operation

• Read operation

  There are three scenarios that may trigger Init, namely the transformation of ctx, the change of type, and the change of addr. When any scenario is triggered, constraints are required: the operation type is w(write), and v(value) is 0. When the above three scenarios are not triggered, it needs to constrained based on the current operation type.

• If it is a w(write) operation, the clk constraints need to be incremented (calling the rangecheck module), and the written value v is correct (calling copy constraints, in OlaVM, all values of memory commands come from registers)

• If it is a r(read) operation, the clk constraints need to be incremented (calling the rangecheck module), the value read is the same as the value written last time

Potential Improvements in “ZK Friendliness”

• For the Init operation, is it necessary to constrain the initialized value of a memory address to 0?
  

  I don’t think it’s necessary to constrain the initialization operation. In fact, for any address, you can constrain its first access to be a write operation, not a read operation, and in the case of a write-once memory model, this constraint will naturally exist. Therefore, if the memory model of the virtual machine is changed to the write-once model, the access constraints on the memory will be reduced.

  
  

• For the read operation, is it possible to avoid the corresponding constraint, that is, to avoid the “read value consistent with the last written value” check.
  

  Since the memory type defined by the VM itself is read/write memory, there is no guarantee that the value of this memory address has not been modified before the VM reads the value of this memory address. Therefore, an equality check is required, as shown below:

  

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

Please note: This may increase the difficulty of the virtual machine implementation, as this is not a commonly used memory model. Also, we should not define a high-level DSL on the virtual machine in the first place, because the language will be somewhat unfriendly to dApp developers and will need to be removed at the compiler level, making these unfriendly and invisible to developers.

So, using the above memory model, the only constraint on the memory module is that for write operations, that is “use copy constraints to ensure that the written value is correct”. Without the restraints:

• The read value is equal to the written value, because memory can only be written once.
• The read clk is larger than the written clk, because you can only write and then read.
• Memory initialization value is 0, (neither memory is necessary)