关于在 ZKEVM 中移除内存限制的一些想法

2022-09-1609:57

Sin7y

2022-09-16 09:57

Sin7y

2022-09-16 09:57

收藏文章

订阅专栏

ZKEVM 是一个具有可编程性，以 ZK 技术为基础的虚拟机，它可以为虚拟机执行的所有操作生成一个零知识证明（zk proof），用来证明虚拟机执行操作的正确性。有关 ZKEVM 的几种实现方案介绍及优劣对比，可以参考 V 神的文章：The different types of ZK-EVMs；如果你想了解更多的设计细节，你也可以阅读 PSE 的 ZKEVM 方案 (native-level)：privacy-scaling-explorations/zkevm-specs Polygon 的 ZKEVM 设计 (bytecode-level)：Polygon zkEVM Documentation；Sin7y 的 ZKEVM 设计 (language-level)：OlaVM: An Ethereum compatible ZKVM。

无论是哪种方案，都需要用 zk 去约束 VM 的所有的行为，这些行为包括：

• 执行合约计算逻辑

• 执行内存访问

• 执行哈希计算

• 执行世界状态更新

• ...

众所周知，zk 在计算压缩领域，具有极大的应用的前景；无论原始的计算多么复杂，其验证过程都十分高效，这是所有 zk 算法的基本技能。因此，对于 VM 执行过程中的计算部分（比如合约逻辑，哈希计算等），zk 可以很好的发挥作用；而在 VM 执行的过程中，除了计算本身外，还存在一些内存访问操作，我们需要把一些数据提前放在内存里，然后在执行计算的时候取出来。

而由于大部分的 VM 都是读写内存，因此不得不约束这些内存访问操作的正确性（比如，从某个地址读出的数据和上一次写入的数据相同的一致性校验）；对于内存访问的约束本身并不复杂（case 比较少），但是由于内存访问的次数很高，所以导致多项式的阶数很高，使得内存相关的约束证明耗时比较可观。

在 ZK(E)VM 的方案中，我们更应该把 zk 主要应用在对于计算本身的证明，对于 EVM 的其他行为（比如内存访问），我们可以在 VM 层面去优化（比如使用 write-once 内存），以减少 zk 约束的规模（避免了内存访问的一致性校验约束）。

Memory 的设计

以EVM为例， EVM 的内存是一块很简单的字节数组，可以存储 32 字节或者 1 字节的数据，也可以读取 32 字节的数据。

图片来源：ethereum_evm_illustrated, page 51

在 EVM 中，和 Memory 相关的指令有：

• MLOAD(x): 从地址 x 处加载 32 字节的数据到调用栈 (stack)

• MSTORE(x,y): 从地址 x 开始，写入 32 字节的 y

• MSTORE8(x,y): 从地址 x 开始，写入 8 字节的 y( 低位开始 )

有兴趣的读者可以在EVM Playground上感受下，上述内存操作带来的内存和栈的变化。

Memory 的约束

在OlaVM的 5.3.5 节，你可以看到关于 Memory 约束的设计原则 (OlaVM 内存相关的指令和 EVM 类似 )。

在 OlaVM 中，RAM 的所有操作组成一个独立的 table，table 里的内容由 memory 和 storage 两种类型组成。在这里，我们只关注对于 memory 的约束。

内存的操作类型大体可以分为三类：

• Init 操作

• write 操作

• read 操作

触发 Init 的场景有三种，分别是 ctx 的变换，type 的变化，addr 的变化；当任何一个场景触发时，需要约束，操作类型为 w(write)，v(value) 为 0。

当上述三种场景没有触发时，则需要根据当前的操作类型来约束；

• 如果是 w(write) 操作，需要约束 clk 是递增的（调用 rangecheck 模块），写入的值 v 是对的（调用 copy constraints，OlaVM 里，内存指令所有的值都来源于寄存器）。

• 如果是 r(read) 操作，需要约束 clk 是递增的（调用 rangecheck 模块），读取的值和上次写入的值是相同的。

一些可能性的提升（更加 zk 友好）

• 对于 Init 操作，需要约束一个内存地址的初始化的值为 0 么？

我认为没有必要对初始化的操作进行约束；实际上，对于任何地址，你可以约束它的第一次访问必须是 write 操作，而不是 read 操作；而如果是 write-once 内存模型，这个限制将天然存在，因此，如果虚拟机的内存模型改为 write-once 模型，将减少对内存的访问约束。

• 对于 read 操作，能否避免对应的约束，即避免校验读取的值和上次写入的值一致？

由于 VM 本身定义的 memory 类型的读写内存，无法保证，VM 在读取这个内存地址的值之前，这个地址的值没有被修改，因此需要增加一个相等性校验，如下图所示：

由此可以看出，产生这个约束的核心原因，内存模型是读写内存，地址的值存在被改写的可能，因此，如果尝试使用只读内存（只写一次），那么就不需要在 memory 的约束去实现上述的一致性约束。

注意：这可能会增加虚拟机的实现难度，因为这是一个不常用的内存模型；并且，我们应该不会首先在这个虚拟机上面去定义一个高级 DSL，因为这个语言对 Dapp 开发者会有些不友好，需要在编译器层面去消除，使得这些不友好，对开发者不可见。

所以，如果采用上述内存模型，内存模块的约束，将只剩下针对 write 操作的约束，即使用 copy constraints 来保证写入的值是对的即可。无须约束：

• 读取的值等于写入的值，因为内存只能被写一次

• 读的 clk 大于写的 clk，因为只能先写再读

• 内存的初始化值为 0（两种内存都没必要）

参考

1.The different types of ZK-EVMs:
https://vitalik.ca/general/2022/08/04/zkevm.html

2.privacy-scaling-explorations/zkevm-specs:
https://github.com/privacy-scaling-explorations/zkevm-specs

3.Polygon zkEVM Documentation:
https://docs.hermez.io/zkEVM/Overview/Overview/

4.OlaVM: An Ethereum compatible ZKVM:
https://olavm.org/whitepaper/OlaVM-07-25.pdf

5.EVM:
https://ethereum.github.io/yellowpaper/paper.pdf

6.ethereum_evm_illustrated, page 51:
https://takenobu-hs.github.io/downloads/ethereum_evm_illustrated.pdf

7.EVM Playground:
https://www.evm.codes/playground

8.OlaVM:
https://olavm.org/whitepaper/OlaVM-07-25.pdf