探索 zk(E)vm
- OlaVM 小白
- 更新于 2023-05-08 11:56
- 阅读 1739
探索 zk(E)vm , 各团队zkevm方案介绍
背景
注：原文发表于 2022-04-25
随着2021年DEFI概念的火热，ETH变得异常拥堵，因此对ETH实现高效扩容成为了热门领域；随后，就出现了各种各样的扩容技术，ZRU,ORU,ARU等等；当五花八门的扩容技术出现之后，市场上出现了两级分化，如果想要和Layer1同级别的安全，那就就得使用zkRollup（ZRU），但丢失了可编程性；如果想要实现和Layer1一样的可编程性，那就得使用Optimistic Rollup(ORU)，但是丢失了安全性。
因此，要想既拥有Layer1同级别的安全性，又想要Layer1一样的可编程性，就不得不用zk技术实现EVM的逻辑，或者基于zk技术实现一个支持通用计算的vm，如上图所示；这也是目前多个团队正在做的事情，下面让我们对于这个工作做些简单的介绍和总结。
各团队zkevm方案介绍
appliedzkp
因为是对EVM的原生兼容，则需要包括：
- 输入是solidity的bytecode；
- Memory和Storage模型和EVM保持一致，即得到的新的世界状态和EVM保持一致
如上图所示，当合约完成部署后，应当把合约的Bytecode写到一个Read-only Memory(ROM)里，用于保证在Execution Trace里的程序和合约Bytecode保持一致（使用Plookup技术）；作为prover，对于给定的一些交易，应该本地生成对应的执行轨迹（Execution Trace），这个Trace里包含了所有交易执行时涉及到所有信息（包括合约逻辑，哈希计算，签名验证，内存访问，Storage更新等），根据这些不同的分组，我们可以预先定义具备特定功能的circuit，比如专门用来校验Hash的电路和专门用来校验算术计算的电路等。 电路的生成证明的过程可以并行，并且这些子模块的Trace之间和主要执行轨迹（execution trace）要通过Plooup技术联系在一起，最终聚合成一个Proof，发送给部署在L1的验证合约去验证，并且更新全局状态。 Prover生成的执行轨迹，可以用到某些技术进行优化，比如对于 nondeterminism computation（例如$$y = \sqrt {x}$$），Prover不必给出具体square()算法的trace，只需要给出$$x^2 = y $$的trace，$$x$$的有效性会被其他约束保证（注意：$$-x$$同样满足这个等式，但是会被range proof校验拒绝）。
Zksync
因为是对EVM的兼容，则需要包括：
- 输入是solidity的bytecode；
- 但Memory和Storage模型没有与EVM保持一致（因为这些都不是zk友好的设计）；
由上图可以看到，zksync的zkEVM架构的输入是支持solidity，经过LLVM编译器后，得到能被zkEVM处理的bytecodes。
对于zkEvm部分的设计，大概如下图所示：
可以看出，也是分为不同功能的电路模块单独处理，然后经过recursive aggreative，最终一个区块得到一个最终的Proof。其中，上图中，绿色标记的交易处理部分（合约逻辑计算）是基于Tinyram实现的，相比于原始的Tinyram框架，做了一些优化（引入复杂的operation），如下图所示：
zkEVM的设计和挑战文章里给出了zksync zkEVM设计的一些优化点和技术挑战（zk-friendly），感兴趣的同学可以仔细理解一下。
Hermez
因为是对EVM的兼容，则需要包括：
- 输入是solidity的bytecode；
- 但Memory和Storage模型没有与EVM保持一致（因为这些都不是zk友好的设计）；
上图给出了 Hermez的zkEVM设计框架，其实到目前为止，读者可以发现，所有的zkEVM框架都是模块化的思想。这确实很有用，因为当prover生成执行轨迹后，这些执行轨迹所实现的功能有所不同，如果在一个电路里处理所有的功能场景，那这个电路规模非常的大且复杂，因此会出现约束逻辑不严谨的情况，因此，把他们进行模块化的处理，再通过一种技术手段把他们连接在一起是一个高效的做法。
Hermez的zkEVM算法数据流如上图所示，其中PIL全称为Polynomial identity Language，它是一套多项式约束。基于这个PIL语言，定义了多个状态机（具备特定功能的），比如Ari-SM，专门用于算术操作，RAM-SM专门处理memory操作等，某种意义上，它的功能和前面appliZkp和zksync方案里定义的specific circuit类似。
evm_ROM.zkASM是用自定义的汇编指令模拟了evm的实现，和交易一起发送给zkExecutor，由zkExecutor生成主执行轨迹（main execution trace），然后把根据不同的功能模块，把对应的Trace发送给对应的状态机去验证，最后形成一个STARK proof；由于STARK的验证逻辑复杂（verifier需要大量的hash计算），这里又使用GROTH16/PLONK算法进行一个递归验证。
注：
- 由于Hermez的方案是兼容EVM的，因此，应该存在一个编译器模块，实现把solidity btyecode转换成zkEvm支持的bytecode，类似于zksync里的LLVM编译器功能。
- 因为需要校验执行正确的程序，因此需要对应的ROM来保存部署的合约逻辑
ConsenSys
因为是对EVM的兼容，则需要包括：
- 输入是solidity的bytecode；
- 但Memory和Storage模型没有与EVM保持一致（因为这些都不是zk友好的设计）；
ConsenSys团队在2021年12月份发布了自己的zkEVM设计说明书，其zkEVM的模块化架构如上图所示，设计思想上和前面几个团队的大概一致。在一些细节上，借鉴了cairo里的概念，比如virual column，read-only memory，跟多的细节可以直接阅读原论文.
Cairo-VM
因为不是对EVM的兼容，所以：
- 输入是solidity的bytecode 输入是汇编程序或者由自定义DSL编写的程序；
- Memory和Storage模型没有与EVM保持一致（因为这些都不是zk友好的设计）；
Cairo指令的VM结构如下所示：
- Case: 000
$ op1 = m(op0 + off_{op1}) $
- Case: 001
$ op1 = m(pc + off_{op1}) $
- Case: 010
$ op1 = m(fp + off_{op1}) $
- Case: 100
$ op1 = m(ap + off_{op1}) $
- $res_{logic} [ bit53..54]$：计算逻辑
- Case: 00
$ res =op1 $
- Case: 01
$ res = op0 + op1 $
- Case: 10
$ res = op0 * op1 $
- $ pc_update[ bit55..57] $：pc的更新逻辑
- Case: 000 // common
$ next_pc = pc + instruction_{size} $
- Case: 001 // absolute jump
$ next_pc = res $
- Case: 010 // relative jump
$ next_pc = pc + res $
- Case: 100 // conditional relative jump
$ next_pc = pc + op1(or instruction_size if dst == 0) $
- $ ap_update [ bit58..59] $：ap的更新逻辑
- Case: 00
$ next_ap = ap ( or \ ap + 2 \ if \ opcode == 1) $
- Case: 01
$ next_ap = ap + res $
- Case: 10
$ next_ap = ap + 1 $
- $ opcode [bit60..62] $：opcode类型
- Case: 000 // jmp
- Case: 001 // call
- Case: 010 // ret
- Case: 100 // assert
这些指令构成了一个基本的状态转换函数，针对这个状态转换函数，定义了一套AIR（多项式约束）；将执行轨迹和AIR结合，生成一个STARK proof。
参考
-
Hermez:
-
Zksync：
-
ConsenSys
-
AppliedZkp
-
Cairo VM
-
Plookup
-
Tinyram
