Sin7Y 团队深度解读:Plookup 在 ZKEvm设计中的应用

我们可以采用Aggregative Proof技术,将多个Proof聚合在一起,链上仅需要一次配对,就可以完成所有Proof的有效性校验。

实现 ZKEvm 是一个伟大的工作,也是一个巨大的工程,不是一个单独的团队就能正确实现的,这需要行业中多个伟大团队的协作与努力。由于没有成熟的方案参考,因此,大家都是在探索的过程中去实现它,Sin7Y 团队发表的相关内容,仅代表我们对 ZKEvm 方案的理解,不保证完全正确,我们真诚的希望且渴望能和专业的人士进行交流,互相学习改进,一起推动这项伟大工程的实现。————Sin7Y 团队

在文章 ZKEVM 设计概览中,我们初步分析对比了 Hermez、ZKsync 和 Appliedzkp 等团队的 ZKEvm 方案框架。它们存的一个共同的地方,就是分开处理 EVM 的执行过程,包括逻辑计算、状态读取等。那么,当一个整体的过程被分开单独处理后,就需要保证:

  1. 各部分之间的数据是一致的,比如,参与逻辑计算的 data 与状态读写的 data 相同;
  2. 对执行的 op 的顺序和合约的逻辑完全一致,保证执行的程序的正确性。 图片1.png <center>图一:ZKEvm 处理过程</center>

这是因为在目前的 Rollup 方案中(不兼容 EVM,特定的电路),合约的逻辑被写在了电路里面,因此不需要 Prover 证明执行的合约逻辑的正确性。而在 ZKEvm 中,电路里包含的仅仅是每个 op,合约的逻辑往往有多个 op,按照一定的顺序的执行,我们需要用一种方法确认这个执行的顺序和合约一致。

以上的二个要求,均可以用 Plookup 技术来得以实现(如图1所示)。关于 Plookup 技术的原理介绍可以参考之前的文章Plookup:An Algorithm Widely Used in zkEVM。简单来说,就是证明集合 f € t,且 f中的元素至少在 t 中出现一次。

<font color="#6155D4">确保执行正确的程序</font><br />

合约在 Layer2 的 EVM 部署时,会将字节码存在 Storage 里(为了简单,先考虑一个合约的场景,多个合约可以按照合约地址区分),然后用户发起一笔交易,调用合约里的一个方法(如图 1 里的 1、2 所示),EVM 会根据方法签名,匹配合约部署时的方法,一旦匹配上,EVM 就会根据匹配到的方法和用户传进去的参数来执行对应的逻辑,并形成最终的执行轨迹(The entire execution traces)。

但是,这可能存在一个问题,如文章前面所述,在特定电路的 Rollup 方案里,特定电路对应特定的功能,因此功能的正确性已经由电路保证,且被安全公司审计和公开。因此,Verifier 只需要拿着对应的输入输出来校验数据是否满足电路功能即可。

然而, 在 ZKEvm 的方案里,电路只约束底层单个 opcode 的执行正确,opcode 之间的顺序不能保证,比如,ZKevm 的电路只能保证 add op 和 Mul op 的正确性,但是先 add, 后 Mul 和先mul 后 add 完全是不同的结果,我们需要保证他们的顺序和合约本身一致。

因此,我们应该采用 Plookup 技术,来保证 prover 执行的 op 顺序和合约里的真实一致。关于这部分的原理及思想,可以参考Hermez的视频。不过这里,需要注意的是,如果合约的计算逻辑很复杂,那么 Table 可能会占用大量的内存空间,应该需要一些手段来优化这些指令数量,比如用 Register 替换 Stack 操作等,但是这又会增加对编译器的修改。

还有一种实现方法,就是利用 Merkel Tree 来证明。如下图所示: 图片2.png <center>图二</center> 需要用一个 ZK-Friendly的hash去实现这个过程,以尽量减少这部分电路的规模。(也可以用基于Class group的Accumulator来校验,相比于 Merkel 树,它可以更快的判断元素的存在性,而且还可以实现批量校验)

<font color="#6155D4">确保数据读写的正确性</font><br />

根据前面所述,当EVM根据函数签名匹配到对应的函数时,基于用户输入的参数,形成了一个真实的执行轨迹(execute traces)。如图 1 中间部分所示,完整的 Traces 包含了,stack 的操作,memory 操作,Storage 操作以及一些 Arithmetic 计算操作。

如果用一个电路证明,那这个电路需要证明:

  1. Stack 操作的有效性,sp value的范围限制,操作类型限制(write/read)等;
  2. Memory 操作的有效性,相同地址的 pc value 限制(单调递增),操作类型限制(write/read)等;
  3. Arithmetic op 的计算正确性,以及其输入的有效性等 ; ......

这将是一个复杂且庞大的电路。因此,我们需要做一个功能切分,一个电路的功能是,保证数据读写(read/write)操作的有效性。另外一个电路保证,这些读写的值是经过正确的数学计算的(add、mul、sub…),并且需要确保参与数学计算的 value 与第一个电路保持一致,如图 1 下方所示。

因此,需要一个缓存,即 Busmapping。Busmapping 里存入有效的 stack、memory、storage 数据。在执行数学计算时,需要校验参与计算的 value 在这个 Busmapping 中。

比如,Add 操作(a + b = c),需要校验,a、b、c 都在busmapping 里(这里依然要用到 plookup 技术)然后再校验它们之间是否满足加法关系(可以用加法电路 + lookup table,也可以单独用 Lookup table,第一个方法的 lookup table 是用来校验数据的合法性,第二个方法的 lookup table 是用来校验数据的合法性和计算的正确性。可以根据真实的计算类型,来择优选择两种方案)。

需要说明的是:交易执行完毕,对应位置的 Storage value 已经更新,但是 new state root 还没有更新,需要在计算好 new state root 之后,把这个 value 写入到 busmapping 里。并且,生成对应的电路,证明这个 new state root 更新的正确性。

<font color="#6155D4">结尾</font><br />

从图 1 中可以看出,我们设计了大概有 4、5 个电路,如果每个电路的 proof 都放在 L1 去验证,那验证的成本将会很昂贵。但是,我们可以采用 Aggregative Proof 技术,将多个 Proof 聚合在一起,链上仅需要一次配对,就可以完成所有 Proof 的有效性校验。

文章写到这里,我们已经对 ZKEvm 的处理框架有了稍微细节一些的描述,当然,仍然还是有一些细节没有涉及到,且仍需进一步研究。再一次说明,由于 ZKEvm 尚且没有成熟的方案,因此,本文更多的目的是想抛砖引玉,借助各位读者的力量,一起完成这个伟大且庞大的工作,真诚欢迎各位读者,给出批评、意见和交流。

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 5天前
  • 阅读 ( 53 )
  • 学分 ( 0 )
  • 分类:Rollup

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
ZKSwap
ZKSwap

25 篇文章, 167 学分