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

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

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

各部分之间的数据是一致的，比如，参与逻辑计算的 data 与状态读写的 data 相同；

对执行的 op 的顺序和合约的逻辑完全一致，保证执行的程序的正确性。

图一：ZKEvm 处理过程

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

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

确保执行正确的程序

合约在 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 来证明。如下图所示：

图二

需要用一个 ZK-Friendly的hash去实现这个过程，以尽量减少这部分电路的规模。（也可以用基于Class group的Accumulator来校验，相比于 Merkel 树，它可以更快的判断元素的存在性，而且还可以实现批量校验）

确保数据读写的正确性

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

如果用一个电路证明，那这个电路需要证明：

Stack 操作的有效性，sp value的范围限制，操作类型限制（write/read）等；

Memory 操作的有效性，相同地址的 pc value 限制（单调递增），操作类型限制（write/read）等；

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 更新的正确性。

结尾

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

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

查看更多

—-

编译者/作者：ZKSwap

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。