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

1. 引言

结合：

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

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

opcodenamecnt_arithcnt_binarycnt_mem_aligncnt_keccak_fcnt_padding_pgcnt_poseidon_gis_dynamic0x00STOP000000false0x01ADD010000false0x02MUL100000false0x03SUB010000false0x04DIV120000false0x05SDIV180000false0x06MOD120000false0x07SMOD180000false0x08ADDMOD130000false0x09MULMOD220000false0x0aEXP51210250000true0x0bSIGNEXTEND060000false0x10LT010000false0x11GT010000false0x12SLT010000false0x13SGT010000false0x14EQ010000false0x15ISZERO010000false0x16AND010000false0x17OR010000false0x18XOR010000false0x19NOT010000false0x1aBYTE240000false0x1bSHL120000false0x1cSHR130000false0x1dSAR2100000false0x20SHA319219322010true0x30ADDRESS000000false0x31BALANCE000009false0x32ORIGIN000000false0x33CALLER000000false0x34CALLVALUE000000false0x35CALLDATALOAD64660000true0x36CALLDATASIZE000000false0x37CALLDATACOPY---000true0x38CODESIZE00000252true0x39CODECOPY0--00255true0x3aGASPRICE000000false0x3bEXTCODESIZE00000255true0x3cEXTCODECOPY0--011510true0x3dRETURNDATASIZE010000false0x3eRETURNDATACOPY--2000true0x3fEXTCODEHASH00000255true0x40BLOCKHASH000109false0x41COINBASE000000false0x42TIMESTAMP000000false0x43NUMBER000000false0x44DIFFICULTY000000false0x45GASLIMIT000000false0x46CHAINID000000false0x47SELFBALANCE00000255true0x50POP000000false0x51MLOAD3232100255true0x52MSTORE3232100255true0x53MSTORE8321100255false0x54SLOAD00000255true0x55SSTORE0-000255true0x56JUMP0-0000true0x57JUMPI0-0000true0x59MSIZE130000false0x5aGAS000000false0x5bJUMPDEST000000false0x60PUSH1030000true0x61PUSH2040000true0x62PUSH3050000false0x63PUSH4020000false0x64PUSH5040000false0x65PUSH6050000false0x66PUSH7060000false0x67PUSH8030000false0x68PUSH9050000false0x69PUSH10060000false0x6aPUSH11070000false0x6bPUSH12040000false0x6cPUSH13060000false0x6dPUSH14070000false0x6ePUSH15080000false0x6fPUSH16050000false0x70PUSH17070000false0x71PUSH18080000false0x72PUSH19090000false0x73PUSH20060000false0x74PUSH21080000false0x75PUSH22090000false0x76PUSH230100000false0x77PUSH24070000false0x78PUSH25090000false0x79PUSH260100000false0x7aPUSH270110000false0x7bPUSH28080000false0x7cPUSH290100000false0x7dPUSH300110000false0x7ePUSH310120000false0x7fPUSH32090000false0x80DUP1000000false0x81DUP2000000false0x82DUP3000000false0x83DUP4000000false0x84DUP5000000false0x85DUP6000000false0x86DUP7000000false0x87DUP8000000false0x88DUP9000000false0x90SWAP1000000false0x91SWAP2000000false0x92SWAP3000000false0x93SWAP4000000false0x94SWAP5000000false0x95SWAP6000000false0x96SWAP7000000false0xa0LOG00-0000true0xa1LOG10-0000true0xa2LOG20-0000true0xa3LOG30-0000true0xa4LOG40-0000true0xf0CREATE--0-0-true0xf1CALL--00--true0xf2CALLCODE--00--true0xf3RETURN000000false0xf4DELEGATECALL--00--true0xf5CREATE2--0-0-true0xfaSTATICCALL--00--true0xfdREVERT000000false0xfeINVALID010000false

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

2. 0x01 ADD opcode

其中：

• δ \delta δ为从stack中pop出来的value数，因ADD是对stack的top 2 values求和（除非明确说明，否则是对 2 256 2^{256} 2256取模）。
• α \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可验证计算简单状态机示例