# Sin7Y Tech Review(30):Thoughts on removing Memory constraints in the ZKEVM
![](https://hackmd.io/_uploads/HJdQy9dgo.png)
ZKEVM is a programmable virtual machine based on ZK technology. It can generate a ZK proof for all operations perfwormed 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](https://vitalik.ca/general/2022/08/04/zkevm.html). If you want more design details, you can also read PSE's ZKEVM Scheme (native-level)： [privacy-scaling-explorations/zkevm-specs](https://github.com/privacy-scaling-explorations/zkevm-specs) Polygon's ZKEVM Design (bytecode-level)： [Polygon zkEVM Documentation](https://docs.hermez.io/zkEVM/Overview/Overview/). Sin7y’s ZKEVM Design (language-level)：[OlaVM: An Ethereum compatible ZKVM](https://olavm.org/whitepaper/OlaVM-07-25.pdf).
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](https://ethereum.github.io/yellowpaper/paper.pdf) 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.
![](https://hackmd.io/_uploads/S1i-lc_xs.png)
[<center>Image Source: ethereum_evm_illustrated, page 51</center>](https://takenobu-hs.github.io/downloads/ethereum_evm_illustrated.pdf)
<br/><br/>
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](https://www.evm.codes/playground).
## The Constraint of Memory
In Section 5.3.5 of [OlaVM](https://olavm.org/whitepaper/OlaVM-07-25.pdf), you'll find the design principles for Memory constraints (OlaVM memory-related instructions are similar to those of EVM).
![](https://hackmd.io/_uploads/BkGGxqdeo.png)
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:
![](https://hackmd.io/_uploads/Hy5Ml9dli.png)
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.
![](https://hackmd.io/_uploads/rJAMxcuej.png)
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)**

TL;DR We are working on building the first ZKVM based on a parallel execution architecture and achieving higher TPS through the improvement of ZK-friendly design and ZK algorithms. The technical features are as follows: Fast proof generation ZK-friendly: smaller circuit scale and simplified bottom constraint units Fast ZK: further optimization on Plonky2 Fast execution: Utilizing parallel execution to significantly shorten the proof generation time

11/14/2022References Zcash - Zcash protocol specification Aleo - Zexe protocol specification Zcash 1. About Zcash ? A short video to learn about Zcash. Features:

9/2/2022Last month we were pleased to announce the OlaVM Whitepaper, an EVM-compatible ZKVM solution, released the 25th of July, 2022. ZKEVM has been a hot topic itself over the past couple of weeks, and upon the release of OlaVM, the paper managed to receive some honorable attention from prominent people in the industry, amongst them, one being Daira Hopwood (who also is the main author of the Zcash protocol), we would like to thank Daira for her feedback. Daira brought up a few important questions in regards to the design decisions, one of them relating to the choice of hash function in ECDSA and Schnorr signature algorithms. The exact comment can be seen in the tweet attached below. What Daira is referencing can in simple terms be described with the following: The security level of Sinsemilla hash is collision resistant, so it cannot be regarded as a Random Oracle. For the ECDSA and Schnorr signature algorithms, in order to satisfy sufficient security, the choice of hash function needs to be regarded as Random Oracle. In order to understand this better, we need to understand some cryptographic concepts first. 1. Security properties of a cryptographic hash function (CHF) According to the definition in the paper Cryptographic Hash-Function Basics, the security properties corresponding to a CHF are divided into the following three categories: Preimage Resistance - Given H(x), it is computationally difficult to determine x, i.e., it is computationally infeasible to discover any input which created a specific output. Second Preimage Resistance - Given x, it is computationally difficult to find some different value x' such that H(x) == H(x'), i.e., it is computationally infeasible to find any second input which has the same output as any specified input. Collision Resistance - Expanding the concept of Second Preimage Resistance, it is computationally infeasible to find any two arbitrary inputs, x and y such that H(x) == H(y), i.e., different inputs which hash to the same output.

8/5/2022Arkworks for Marlin Marlin Fractal R1CS Zero-knowledge proof algorithm Marlin is a R1CS based proof system, that, given a coefficient matrix parameter $I = (F, n, m, A, B, C)$ and a set of valid assignments $z =(x, w) \in F^n$，among which x is public information, namely Instance and is private information, namely, witness if $Az \circ Bz = Cz$is established, R1CS is established. If we let $z_A = Az, z_B = Bz, z_C = Cz$ the above formula can be transformed into $z_A \circ z_B= z_C$。 Therefore, if we can prove that there are four vectors $z_A, z_B,z_C,z$ that satisfy

7/22/2022
Published on ** HackMD**