Polygon zkEVM zkASM 与 以太坊虚拟机opcode 对应集合

1. 引言

结合：

• 以太坊黄皮书 https://ethereum.github.io/yellowpaper/paper.pdf
• https://github.com/comitylabs/evm.codes（以太坊虚拟机opcodes交互索引）

Polygon zkEVM的虚拟机支持的opcode为：【基本与以太坊虚拟机opcode对应】

各opcode详细的zkASM实现参见zkevm-rom项目中的opcodes.zkasm文件。

2. 0x01 ADD opcode

其中：

• $\delta$为从stack中pop出来的value数，因ADD是对stack的top 2 values求和（除非明确说明，否则是对$2^{256}$取模）。
• $\alpha$为向stack push进去的value数。ADD操作会将二值求和结果再push进stack中。

根据上图可知，0x01 ADD opcode所需最小gas为3。

在Polygon zkEVM中，以太坊虚拟机的0x01 ADD opcode对应的zkASM表示为：【分别调用了Memory二级状态机、Binary二级状态机。】

opADD:
	; 检查当前stack中确实有至少2个元素，否则跳转到stackUnderflow。
    SP - 2          :JMPN(stackUnderflow)
    ; 将stack pointer值减一
    SP - 1 => SP
    ; 将stack pointer值加载到A寄存器中；再将stack pointer值减一
    $ => A          :MLOAD(SP--)
    ; 将stack pointer值加载到C寄存器中
    $ => C          :MLOAD(SP)

    ; Add operation with Arith
    ; 将A寄存器的值存储在Memory状态机中的`arithA`变量中
    A               :MSTORE(arithA)
    ; 将C寄存器的值存储在Memory状态机中的`arithB`变量中
    C               :MSTORE(arithB)
    ; 调用`addARITH`子程序，负责执行加法运算
                    :CALL(addARITH)
    ; 从Memory状态机中的`arithRes1`变量中读取加法运算结果 存入在 E寄存器中
    $ => E          :MLOAD(arithRes1)
    ; 将E寄存器的值存储在stack pointer位置，将stack pointer值加一
    E               :MSTORE(SP++)
    ; stack空间为1024，若当前stack pointer值大于1024，则跳转到stackOverflow
    1024 - SP       :JMPN(stackOverflow)
    ; ADD opcode所需最低gas为3，若执行为ADD操作后GAS为负数，则跳转到outOfGas
    GAS-3 => GAS    :JMPN(outOfGas)
    ; 最后但同样重要的是，以下表示继续处理下一指令。
                    :JMP(readCode)

其中addARITH子程序负责执行加法运算，具体实现见：

• zkEVM Rom项目中的utils.zkasm

  ; 其中tmpZkPC、storeTmp、arithA、arithB、arithRes1、loadTmp均为全局变量。
  addARITH:
  	; 将调用addARITH子程序之前的RR值存入tmpZkPC临时全局变量中。
      RR              :MSTORE(tmpZkPC)
      zkPC+1 => RR    :JMP(storeTmp) ; 等效为 CALL(storeTmp)，将A/B/C/D/E寄存器的值存储在临时全局变量tmpVarA/B/C/D/E中。
  
      $ => A          :MLOAD(arithA)
      $ => B          :MLOAD(arithB)
      $ => E          :ADD ; 对应Binary状态机，为byte-wise加法运算。
  
      E               :MSTORE(arithRes1)
  
      zkPC+1 => RR    :JMP(loadTmp) ; 等效为 CALL(loadTmp)，将临时全局变量tmpVarA/B/C/D/E中的值加载到A/B/C/D/E寄存器中。
      ; 重置RR值 为 调用addARITH子程序之前的RR值（从tmpZkPC临时全局变量中取出）
      $ => RR         :MLOAD(tmpZkPC)
                      :JMP(RR) ; 等效为 RETURN
  

  其中storeTmp子程序为将A/B/C/D/E寄存器的值存储在临时全局变量tmpVarA/B/C/D/E中，而loadTmp为将临时全局变量tmpVarA/B/C/D/E中的值加载到A/B/C/D/E寄存器中：

  storeTmp:
      A                   :MSTORE(tmpVarA)
      B                   :MSTORE(tmpVarB)
      C                   :MSTORE(tmpVarC)
      D                   :MSTORE(tmpVarD)
      E                   :MSTORE(tmpVarE)
                          :JMP(RR) ; 等效为 RETURN
  loadTmp:
      $ => A                  :MLOAD(tmpVarA)
      $ => B                  :MLOAD(tmpVarB)
      $ => C                  :MLOAD(tmpVarC)
      $ => D                  :MLOAD(tmpVarD)
      $ => E                  :MLOAD(tmpVarE)
                              :JMP(RR) ; 等效为 RETURN
  

不过，实际实现时，Polygon zkEVM中设定了一些常量上限值：

; COUNTERS
CONST %MAX_CNT_STEPS = 2**21 ; 最大STEP数

CONST %MAX_CNT_ARITH = %MAX_CNT_STEPS / 32 ; 最多ARITH计算数
CONST %MAX_CNT_BINARY = %MAX_CNT_STEPS / 32 ; 最多BINARY计算数
CONST %MAX_CNT_MEM_ALIGN = %MAX_CNT_STEPS / 32 ; 最多MemAlign计算数
CONST %MAX_CNT_KECCAK_F = (%MAX_CNT_STEPS / 158418) * 9 ; 最多Keccakf计算数
CONST %MAX_CNT_PADDING_PG = (%MAX_CNT_STEPS / 56) ; 最多padding pg计算数，针对Poseidon哈希
CONST %MAX_CNT_POSEIDON_G = (%MAX_CNT_STEPS / 30) ; 最多PoseidonG计算数，针对Poseidon哈希
CONST %MIN_CNT_KECCAK_BATCH = 2 ; 最少Keccak_batch数
; ETHEREUM CONSTANTS
CONSTL %MAX_NONCE = 0xffffffffffffffffn ; 以太坊nonce最大值为2^{64}-1。

因此，实际在zkevm-rom的opcodes.zkasm中对0x01 ADD opcode的实际实现为：【借助了Binary状态机默认是对A和B寄存器进行运算的，进行了优化，使代码更简洁；同时考虑实际应用场景，对相关计数器进行了约束。】

opADD:

    %MAX_CNT_BINARY - CNT_BINARY - 1 :JMPN(outOfCounters) ; 对相关计算计数器进行了约束。
    %MAX_CNT_STEPS - STEP - 120 :JMPN(outOfCounters) ; 约束了计算复杂度。

    SP - 2          :JMPN(stackUnderflow)
    SP - 1 => SP
    $ => A          :MLOAD(SP--)
    $ => B          :MLOAD(SP)

    ; Add operation with Arith
    $ => E          :ADD

    E               :MSTORE(SP++)
    1024 - SP       :JMPN(stackOverflow)
    GAS-3 => GAS    :JMPN(outOfGas)
                    :JMP(readCode)

参考资料

[1] zkASM示例
[2] 以太坊黄皮书 https://ethereum.github.io/yellowpaper/paper.pdf
[3] 理解以太坊黄皮书
[3] EVM.Codes

附录：Polygon Hermez 2.0 zkEVM系列博客

• ZK-Rollups工作原理
• Polygon zkEVM——Hermez 2.0简介
• Polygon zkEVM网络节点
• Polygon zkEVM 基本概念
• Polygon zkEVM Prover
• Polygon zkEVM工具——PIL和CIRCOM
• Polygon zkEVM节点代码解析
• Polygon zkEVM的pil-stark Fibonacci状态机初体验
• Polygon zkEVM的pil-stark Fibonacci状态机代码解析
• Polygon zkEVM PIL编译器——pilcom 代码解析
• Polygon zkEVM Arithmetic状态机
• Polygon zkEVM中的常量多项式
• Polygon zkEVM Binary状态机
• Polygon zkEVM Memory状态机
• Polygon zkEVM Memory Align状态机
• Polygon zkEVM zkASM编译器——zkasmcom
• Polygon zkEVM哈希状态机——Keccak-256和Poseidon
• Polygon zkEVM zkASM语法
• Polygon zkEVM可验证计算简单状态机示例