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

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。n n无论是哪种方案,都需要用zk去约束VM的所有的行为,这些行为包括: 

• 执行合约计算逻辑 

• 执行内存访问 

• 执行哈希计算 

• 执行世界状态更新 

• ...

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

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

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

Memory的设计

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

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

图片来源:ethereum_evm_illustrated, page 51

在EVM中,和Memory相关的指令有: 

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

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

•  MSTORE8(x,y): 从地址x开始,写入8字节的y(低位开始)n有兴趣的读者可以在EVM Playground上感受下,上述内存操作带来的内存和栈的变化。

Memory的约束

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

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

在OlaVM中,RAM的所有操作组成一个独立的table,table里的内容由memory和storage两种类型组成。在这里,我们只关注对于memory的约束。n内存的操作类型大体可以分为三类: 

• 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在读取这个内存地址的值之前,这个地址的值没有被修改,因此需要增加一个相等性校验,如下图所示:

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

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

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

注意:这可能会增加虚拟机的实现难度,因为这是一个不常用的内存模型;并且,我们应该不会首先在这个虚拟机上面去定义一个高级DSL,因为这个语言对Dapp开发者会有些不友好,需要在编译器层面去消除,使得这些不友好,对开发者不可见。n n所以,如果采用上述内存模型,内存模块的约束,将只剩下针对write操作的约束,即使用copy constraints来保证写入的值是对的即可。无须约束: 

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

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

内存的初始化值为0(两种内存都没必要)

参考

ethereum_evm_illustrated, page 51

关于我们

Sin7y成立于2021年,由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队,探索EVM、Layer2跨链隐私计算、自主支付解决方案等最重要和最前沿的技术。

微信公众号:Sin7Y

GitHub | Twitter | Telegram | MediumMirror | HackMD | HackerNoon

如有疑问联系邮箱:
*本文转载自网络转载,版权归原作者所有。本站只是转载分享,不代表赞同其中观点。请自行判断风险,本文不构成投资建议。*