探索 zk(E)vm

探索 zk(E)vm , 各团队zkevm方案介绍

背景

注:原文发表于 2022-04-25

随着2021年DEFI概念的火热,ETH变得异常拥堵,因此对ETH实现高效扩容成为了热门领域;随后,就出现了各种各样的扩容技术,ZRU,ORU,ARU等等;当五花八门的扩容技术出现之后,市场上出现了两级分化,如果想要和Layer1同级别的安全,那就就得使用zkRollup(ZRU),但丢失了可编程性;如果想要实现和Layer1一样的可编程性,那就得使用Optimistic Rollup(ORU),但是丢失了安全性。

img

因此,要想既拥有Layer1同级别的安全性,又想要Layer1一样的可编程性,就不得不用zk技术实现EVM的逻辑,或者基于zk技术实现一个支持通用计算的vm,如上图所示;这也是目前多个团队正在做的事情,下面让我们对于这个工作做些简单的介绍和总结。

各团队zkevm方案介绍

appliedzkp

因为是对EVM的原生兼容,则需要包括:

  1. 输入是solidity的bytecode;
  2. Memory和Storage模型和EVM保持一致,即得到的新的世界状态和EVM保持一致

img

如上图所示,当合约完成部署后,应当把合约的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的兼容,则需要包括:

  1. 输入是solidity的bytecode;
  2. 但Memory和Storage模型没有与EVM保持一致(因为这些都不是zk友好的设计);

img

由上图可以看到,zksync的zkEVM架构的输入是支持solidity,经过LLVM编译器后,得到能被zkEVM处理的bytecodes。

对于zkEvm部分的设计,大概如下图所示:

img

可以看出,也是分为不同功能的电路模块单独处理,然后经过recursive aggreative,最终一个区块得到一个最终的Proof。其中,上图中,绿色标记的交易处理部分(合约逻辑计算)是基于Tinyram实现的,相比于原始的Tinyram框架,做了一些优化(引入复杂的operation),如下图所示:

img

zkEVM的设计和挑战文章里给出了zksync zkEVM设计的一些优化点和技术挑战(zk-friendly),感兴趣的同学可以仔细理解一下。

Hermez

因为是对EVM的兼容,则需要包括:

  1. 输入是solidity的bytecode;
  2. 但Memory和Storage模型没有与EVM保持一致(因为这些都不是zk友好的设计);

img

上图给出了 Hermez的zkEVM设计框架,其实到目前为止,读者可以发现,所有的zkEVM框架都是模块化的思想。这确实很有用,因为当prover生成执行轨迹后,这些执行轨迹所实现的功能有所不同,如果在一个电路里处理所有的功能场景,那这个电路规模非常的大且复杂,因此会出现约束逻辑不严谨的情况,因此,把他们进行模块化的处理,再通过一种技术手段把他们连接在一起是一个高效的做法。

img

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算法进行一个递归验证。

img

注:

  1. 由于Hermez的方案是兼容EVM的,因此,应该存在一个编译器模块,实现把solidity btyecode转换成zkEvm支持的bytecode,类似于zksync里的LLVM编译器功能。
  2. 因为需要校验执行正确的程序,因此需要对应的ROM来保存部署的合约逻辑

ConsenSys

因为是对EVM的兼容,则需要包括:

  1. 输入是solidity的bytecode;
  2. 但Memory和Storage模型没有与EVM保持一致(因为这些都不是zk友好的设计);

img

ConsenSys团队在2021年12月份发布了自己的zkEVM设计说明书,其zkEVM的模块化架构如上图所示,设计思想上和前面几个团队的大概一致。在一些细节上,借鉴了cairo里的概念,比如virual column,read-only memory,跟多的细节可以直接阅读原论文.

Cairo-VM

因为不是对EVM的兼容,所以:

  1. 输入是solidity的bytecode 输入是汇编程序或者由自定义DSL编写的程序;
  2. Memory和Storage模型没有与EVM保持一致(因为这些都不是zk友好的设计);

Cairo指令的VM结构如下所示:

img

image-20230508111809118

  • 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。

参考

原文首发于 :https://zhuanlan.zhihu.com/p/504904602

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

0 条评论

请先 登录 后评论
OlaVM 小白
OlaVM 小白
A ZKVM-based, High-performance, and Privacy-focused Layer2 platform.