Polygon zkEVM Arithmetic状态机

1. 引言

前序博客有：

• Polygon zkEVM PIL编译器——pilcom 代码解析
• Polygon zkEVM zkASM编译器——zkasmcom

Polygon zkEVM中将某类特定的计算表示为状态机。 Arithmetic状态机为Polygon zkEVM的6个二级状态机之一，主要由2大部分组成：

• 1）Executor部分：有2个版本，Javascript版本 和 C/C++版本。https://github.com/0xPolygonHermez/zkevm-proverjs/tree/main/src/sm/sm_arith。
• 2）验证规则集（a set of verification rules）程序部分：以PIL语言实现，见 https://github.com/0xPolygonHermez/zkevm-proverjs/blob/main/pil/arith.pil。

详细可参看审计培训视频Polygon zkEVM Training for Auditors - Arith state machine。

Polygon zkEVM的Arithmetic状态机主要是基于Secp256K1椭圆曲线E（ y 2 = x 3 + 7 y^2=x^3+7 y2=x3+7，基域为 p = 2 256 − 2 32 − 2 9 − 2 8 − 2 7 − 2 6 − 2 4 − 1 p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1 p=2256−232−29−28−27−26−24−1）上的如下运算：【二进制表示为0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2fL，与pil实现中eq公式内的p[0]p[1]等常量值对应。】

• 1）域内加法和乘法等运算： x 1 ⋅ y 1 + x 2 = y 2 ⋅ 2 256 + y 3 x_1\cdot y_1+x_2=y_2\cdot 2^{256}+y_3 x1​⋅y1​+x2​=y2​⋅2256+y3​。若 y 1 = 0 y_1=0 y1​=0，则表示的是field addition运算；若 x 2 = 0 x_2=0 x2​=0，则表示的是field multiplication运算。
• 2）椭圆曲线点加运算：椭圆曲线上2个不同点 P = ( x 1 , y 1 ) , Q = ( x 2 , y 2 ) P=(x_1,y_1),Q=(x_2,y_2) P=(x1​,y1​),Q=(x2​,y2​)， x 1 ≠ x 2 x_1\neq x_2 x1​​=x2​, P + Q = ( x 3 , y 3 ) P+Q=(x_3,y_3) P+Q=(x3​,y3​)计算为： x 3 = s 2 − x 1 − x 2 , x_3=s^2-x_1-x_2, x3​=s2−x1​−x2​, y 3 = s ( x 1 − x 3 ) − y 1 y_3=s(x_1-x_3)-y_1 y3​=s(x1​−x3​)−y1​ 其中 s = y 2 − y 1 x 2 − x 1 s=\frac{y_2-y_1}{x_2-x_1} s=x2​−x1​y2​−y1​​。
• 3）椭圆曲线点倍加运算：椭圆曲线上点 P = ( x 1 , y 1 ) P=(x_1,y_1) P=(x1​,y1​)，, 2 P = P + P = ( x 3 , y 3 ) 2P=P+P=(x_3,y_3) 2P=P+P=(x3​,y3​)计算为： x 3 = s 2 − 2 x 1 , x_3=s^2-2x_1, x3​=s2−2x1​, y 3 = s ( x 1 − x 3 ) − y 1 y_3=s(x_1-x_3)-y_1 y3​=s(x1​−x3​)−y1​ 其中 s = 3 x 1 2 2 y 1 s=\frac{3x_1^2}{2y_1} s=2y1​3x12​​。

将以上运算以约束形式表示为： EQ 0  ⁣ : x 1 ⋅ y 1 + x 2 − y 2 ⋅ 2 256 − y 3 = 0 , EQ 1  ⁣ : s ⋅ x 2 − s ⋅ x 1 − y 2 + y 1 + q 0 ⋅ p = 0 , EQ 2  ⁣ : 2 ⋅ s ⋅ y 1 − 3 ⋅ x 1 ⋅ x 1 + q 0 ⋅ p = 0 , EQ 3  ⁣ : s ⋅ s − x 1 − x 2 − x 3 + q 1 ⋅ p = 0 , EQ 4  ⁣ : s ⋅ x 1 − s ⋅ x 3 − y 1 − y 3 + q 2 ⋅ p = 0 , \begin{aligned} \text{EQ}_0 \colon \quad &x_1 \cdot y_1 + x_2 - y_2 \cdot 2^{256} - y_3 = 0, \\ \text{EQ}_1 \colon \quad &s \cdot x_2 - s \cdot x_1 -y_2 + y_1 + q_0 \cdot p = 0, \\ \text{EQ}_2 \colon \quad & 2 \cdot s \cdot y_1 - 3 \cdot x_1 \cdot x_1 + q_0 \cdot p = 0, \\ \text{EQ}_3 \colon \quad & s \cdot s - x_1 - x_2 - x_3 + q_1 \cdot p = 0, \\ \text{EQ}_4 \colon \quad & s \cdot x_1 - s \cdot x_3 - y_1 - y_3 + q_2 \cdot p = 0, \end{aligned} EQ0​:EQ1​:EQ2​:EQ3​:EQ4​:​x1​⋅y1​+x2​−y2​⋅2256−y3​=0,s⋅x2​−s⋅x1​−y2​+y1​+q0​⋅p=0,2⋅s⋅y1​−3⋅x1​⋅x1​+q0​⋅p=0,s⋅s−x1​−x2​−x3​+q1​⋅p=0,s⋅x1​−s⋅x3​−y1​−y3​+q2​⋅p=0,​ 其中 q 0 , q 1 , q 2 ∈ Z q_0,q_1,q_2 \in \mathbb{Z} q0​,q1​,q2​∈Z为整数，使得以上等式成立。这种表达可避免对 p p p做除法运算。 这些约束对应3个可能的计算场景：

• 若 E Q 0 EQ_0 EQ0​激活，则其它等式失效；
• 若 E Q 1 , E Q 3 , E Q 4 EQ_1,EQ_3,EQ_4 EQ1​,EQ3​,EQ4​激活，则 E Q 0 , E Q 2 EQ_0,EQ_2 EQ0​,EQ2​等式失效；
• 若 E Q 2 , E Q 3 , E Q 4 EQ_2,EQ_3,EQ_4 EQ2​,EQ3​,EQ4​激活，则 E Q 0 , E Q 1 EQ_0,EQ_1 EQ0​,EQ1​等式失效。

由于在以上任意场景下， E Q 1 EQ_1 EQ1​和 E Q 2 EQ_2 EQ2​最多只能激活一个，因此二者可“共享”相同的 q 0 q_0 q0​。

为实现以上运算，Arithmetic状态机内需包含以下寄存器： x 1 , y 1 , x 2 , y 2 , x 3 , y 3 , s , q 0 , q 1 , q 2 x_1,y_1,x_2,y_2,x_3,y_3,s,q_0,q_1,q_2 x1​,y1​,x2​,y2​,x3​,y3​,s,q0​,q1​,q2​ 这些寄存器均为256-bit field elements，实际构建时，将每个寄存器切分为16个子寄存器，每个子寄存器容量为16-bit（2个字节），为此，PIL中的定义为：

pol commit x1[16];
pol commit y1[16];
pol commit x2[16];
pol commit y2[16];
pol commit x3[16];
pol commit y3[16];

pol commit s[16];
pol commit q0[16];
pol commit q1[16];
pol commit q2[16];

2. arith.zkasm示例

以zkevm-proverjs/test/zkasm/counters/arith.zkasm为例：【$ npm run test:counters:arith】

start:

        STEP => A
        0 :ASSERT

        0 => A
        CNT_ARITH :ASSERT
        CNT_BINARY :ASSERT
        CNT_KECCAK_F: ASSERT
        CNT_MEM_ALIGN :ASSERT
        CNT_POSEIDON_G :ASSERT
        CNT_PADDING_PG :ASSERT

        0 => A,B,C,D    :ARITH #清零

        CNT_ARITH => A
        1               :ASSERT

        CNT_ARITH => A
        1               :ASSERT

        0x2000000000000000000000000000000000000000000000000000000000000001n => A
        0x100    => B
        0x73     => C
        0x20    => D
        0x173   :ARITH #赋值


        2 => A
        CNT_ARITH :ASSERT

        0 => A
        CNT_KECCAK_F: ASSERT
        CNT_MEM_ALIGN :ASSERT
        CNT_POSEIDON_G :ASSERT
        CNT_PADDING_PG :ASSERT

end:
       0 => A,B,C,D,E,CTX, SP, PC, GAS, MAXMEM, SR

finalWait:
        ${beforeLast()}  : JMPN(finalWait)

                         : JMP(start)
opINVALID:

经const rom = await zkasm.compile(path.join(__dirname, "zkasm", zkasmFile)); zkasmcom 编译后的结果为：

{
 "program": [
  {
   "inSTEP": "1",
   "setA": 1,
   "line": 3,
   "fileName": "arith.zkasm",
   "lineStr": "        STEP => A"
  },
  {
   "CONST": "0",
   "assert": 1,
   "line": 4,
   "fileName": "arith.zkasm",
   "lineStr": "        0 :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "line": 6,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A"
  },
  {
   "inCntArith": "1",
   "assert": 1,
   "line": 7,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH :ASSERT"
  },
  {
   "inCntBinary": "1",
   "assert": 1,
   "line": 8,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_BINARY :ASSERT"
  },
  {
   "inCntKeccakF": "1",
   "assert": 1,
   "line": 9,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_KECCAK_F: ASSERT"
  },
  {
   "inCntMemAlign": "1",
   "assert": 1,
   "line": 10,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_MEM_ALIGN :ASSERT"
  },
  {
   "inCntPoseidonG": "1",
   "assert": 1,
   "line": 11,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_POSEIDON_G :ASSERT"
  },
  {
   "inCntPaddingPG": "1",
   "assert": 1,
   "line": 12,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_PADDING_PG :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "setB": 1,
   "setC": 1,
   "setD": 1,
   "arith": 1,
   "arithEq0": 1,
   "line": 14,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A,B,C,D    :ARITH"
  },
  {
   "inCntArith": "1",
   "setA": 1,
   "line": 16,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH => A"
  },
  {
   "CONST": "1",
   "assert": 1,
   "line": 17,
   "fileName": "arith.zkasm",
   "lineStr": "        1               :ASSERT"
  },
  {
   "inCntArith": "1",
   "setA": 1,
   "line": 19,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH => A"
  },
  {
   "CONST": "1",
   "assert": 1,
   "line": 20,
   "fileName": "arith.zkasm",
   "lineStr": "        1               :ASSERT"
  },
  {
   "CONSTL": "14474011154664524427946373126085988481658748083205070504932198000989141204993",
   "setA": 1,
   "line": 22,
   "fileName": "arith.zkasm",
   "lineStr": "        0x2000000000000000000000000000000000000000000000000000000000000001n => A"
  },
  {
   "CONST": "256",
   "setB": 1,
   "line": 23,
   "fileName": "arith.zkasm",
   "lineStr": "        0x100    => B"
  },
  {
   "CONST": "115",
   "setC": 1,
   "line": 24,
   "fileName": "arith.zkasm",
   "lineStr": "        0x73     => C"
  },
  {
   "CONST": "32",
   "setD": 1,
   "line": 25,
   "fileName": "arith.zkasm",
   "lineStr": "        0x20    => D"
  },
  {
   "CONST": "371",
   "arith": 1,
   "arithEq0": 1,
   "line": 26,
   "fileName": "arith.zkasm",
   "lineStr": "        0x173   :ARITH"
  },
  {
   "CONST": "2",
   "setA": 1,
   "line": 29,
   "fileName": "arith.zkasm",
   "lineStr": "        2 => A"
  },
  {
   "inCntArith": "1",
   "assert": 1,
   "line": 30,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "line": 32,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A"
  },
  {
   "inCntKeccakF": "1",
   "assert": 1,
   "line": 33,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_KECCAK_F: ASSERT"
  },
  {
   "inCntMemAlign": "1",
   "assert": 1,
   "line": 34,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_MEM_ALIGN :ASSERT"
  },
  {
   "inCntPoseidonG": "1",
   "assert": 1,
   "line": 35,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_POSEIDON_G :ASSERT"
  },
  {
   "inCntPaddingPG": "1",
   "assert": 1,
   "line": 36,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_PADDING_PG :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "setB": 1,
   "setC": 1,
   "setD": 1,
   "setE": 1,
   "setCTX": 1,
   "setSP": 1,
   "setPC": 1,
   "setGAS": 1,
   "setMAXMEM": 1,
   "setSR": 1,
   "line": 39,
   "fileName": "arith.zkasm",
   "lineStr": "       0 => A,B,C,D,E,CTX, SP, PC, GAS, MAXMEM, SR"
  },
  {
   "freeInTag": {
    "op": "functionCall",
    "funcName": "beforeLast",
    "params": []
   },
   "inFREE": "1",
   "JMPC": 0,
   "JMPN": 1,
   "offset": 27,
   "line": 42,
   "offsetLabel": "finalWait",
   "fileName": "arith.zkasm",
   "lineStr": "        ${beforeLast()}  : JMPN(finalWait)"
  },
  {
   "JMP": 1,
   "JMPC": 0,
   "JMPN": 0,
   "offset": 0,
   "line": 44,
   "offsetLabel": "start",
   "fileName": "arith.zkasm",
   "lineStr": "                         : JMP(start)"
  }
 ],
 "labels": {
  "start": 0,
  "end": 26,
  "finalWait": 27,
  "opINVALID": 29
 }
}

【Executor本质上是一种名为zkASM的汇编语言解释器。 使用zkASM语言来构建名为zkROM的程序，Executor运行zkROM程序来提供合适的execution trace。 在zkROM程序中，每个EVM opcode都以一组zkASM指令集来实现。 每个zkASM指令利用了execution trace矩阵中的一行，又名zkEVM的一个“step”。】即意味着const rom = await zkasm.compile(path.join(__dirname, "zkasm", zkasmFile)); zkasm编译的结果，会作为rom.pil的输入：

• await smRom.buildConstants(constPols.Rom, rom);：给rom.pil的常量多项式赋值。【实际上，Rom中全是常量多项式，为只读模式】
• const requiredMain = await smMain.execute(cmPols.Main, input, rom);：根据zkasm编译的.rom.json文件和input（如../tools/build-genesis/input-executor.json），获得main.pil的execution trace。

以zkevm-proverjs中的 "test:counters:arith": "mocha -max-old-space-size=51200 test/counters/arith.js",为例：

describe("Test Arith Counter", async function () {
    this.timeout(10000000);

    it("Verify Arith Zkasm Test", async () => {
        await verifyZkasm("../zkasm/counters/arith.zkasm", true,
                { defines: {N: 2 ** 21},
                  namespaces: ['Global', 'Main', 'Rom', 'Byte4', 'Arith'], //只对这些namespace操作。
                  verbose: true,
                  color: true,
                  disableUnusedError: true});
    });
});

基本流程为：

• 1）对main.pil编译，结果为main.pil.json。
• 2）对arith.zkasm编译，结果为arith.rom.json。
• 3）依次对上面定义的namespace（‘Global’, ‘Main’, ‘Rom’, ‘Byte4’, ‘Arith’）常量多项式赋值，其中’Rom’中的所有常量多项式赋值取决于arith.rom.json。而其它namespace中的常量多项式赋值是固定不变的。
• 4）对’Main’中的隐私多项式赋值，取决于具体的input和arith.rom.json。

  const requiredMain = await smMain.execute(cmPols.Main, input, rom);
  

• 5）根据requiredMain.Byte4，对’Byte4‘中的隐私多项式赋值。

  await smByte4.execute(cmPols.Byte4, requiredMain.Byte4);
  

• 6）根据requiredMain.Arith || []，对’Arith’中的隐私多项式赋值。

  await smBinary.execute(cmPols.Binary, requiredMain.Binary || []);
  

接下来重点关注以上4）5）6）步骤的execution trace赋值细节。 其中的input为../tools/build-genesis/input-executor.json：

{
  "oldStateRoot": "0x2dc4db4293af236cb329700be43f08ace740a05088f8c7654736871709687e90",
  "db": {
    "0x2dc4db4293af236cb329700be43f08ace740a05088f8c7654736871709687e90": [
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0d1f0da5a7b620c8",
      "43fd1e18e59fd724",
      "d428d25da0cb1888",
      "e31f5542ac227c06",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000"
    ],
    "0xe31f5542ac227c06d428d25da0cb188843fd1e18e59fd7240d1f0da5a7b620c8": [
      "ed22ec7734d89ff2",
      "b2e639153607b7c5",
      "42b2bd6ec2788851",
      "b781932941084783",
      "3e63658ee0db910d",
      "0b3e34316e81aa10",
      "e0dc203d93f4e3e5",
      "e10053d0ebc64602",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000"
    ],
    "0xb78193294108478342b2bd6ec2788851b2e639153607b7c5ed22ec7734d89ff2": [
      "16dde42596b907f0",
      "49015d7e991a1528",
      "94dd9dadd060910b",
      "60b4d5e9af514018",
      "b69b044f5e694795",
      "f57d81efba5d4445",
      "339438195426ad0a",
      "3efad1dd58c2259d",
      "0000000000000001",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000"
    ],
    "0x3efad1dd58c2259d339438195426ad0af57d81efba5d4445b69b044f5e694795": [
      "00000000dea00000",
      "0000000035c9adc5",
      "0000000000000036",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000"
    ],
    "0xe10053d0ebc64602e0dc203d93f4e3e50b3e34316e81aa103e63658ee0db910d": [
      "66ee2be0687eea76",
      "6926f8ca8796c78a",
      "4c2f3e938869b82d",
      "649e63bfe1247ba4",
      "b69b044f5e694795",
      "f57d81efba5d4445",
      "339438195426ad0a",
      "3efad1dd58c2259d",
      "0000000000000001",
      "0000000000000000",
      "0000000000000000",
      "0000000000000000"
    ]
  },
  "sequencerAddr": "0x617b3a3528F9cDd6630fd3301B9c8911F7Bf063D",
  "batchL2Data": "0xee80843b9aca00830186a0944d5cf5032b2a844602278b01199ed191a86c93ff88016345785d8a0000808203e880801cee7e01dc62f69a12c3510c6d64de04ee6346d84b6a017f3e786c7d87f963e75d8cc91fa983cd6d9cf55fff80d73bd26cd333b0f098acc1e58edb1fd484ad731b",
  "newStateRoot": "0xbff23fc2c168c033aaac77503ce18f958e9689d5cdaebb88c5524ce5c0319de3",
  "oldLocalExitRoot": "0x17c04c3760510b48c6012742c540a81aba4bca2f78b9d14bfd2f123e2e53ea3e",
  "newLocalExitRoot": "0x0000000000000000000000000000000000000000000000000000000000000000",
  "globalExitRoot": "0x090bcaf734c4f06c93954a827b45a6e8c67b8e0fd1e0a35a1c5982d6961828f9",
  "numBatch": 1,
  "timestamp": 1944498031,
  "contractsBytecode": {}
}

2.1 Main.pil隐私多项式赋值

基于input-executor.json和arith.rom.json，对main.pil中的 隐私多项式赋值：

const requiredMain = await smMain.execute(cmPols.Main, input, rom);

smMain.execute的核心流程为：

• 1）从input.db中加载数据库信息，并基于数据库信息构建sparse merkle树：

  const db = new MemDB(Fr, input.db);
  const smt = new SMT(db, poseidon, Fr);
  

• 2）对main.pil中的部分隐私多项式（A0-A7\B0-B7\C0-C7\D0-D7\E0-E7\SR0-SR7\CTX\SP\PC\MAXMEM\HASHPOS\GAS\RR\zkPC\cntArith\cntBinary\cntKeccakF\cntMemAlign\cntPaddingPG\cntPoseidonG）的第0个值初始化为0：

  initState(Fr, pols);
  

• 3）交易预处理preprocessTxs，取input-executor.json中的sequencerAddr、batchL2Data、newStateRoot、oldLocalExitRoot、newLocalExitRoot、globalExitRoot、numBatch、timestamp、oldStateRoot信息：
  • 3.1）根据batchL2Data、globalExitRoot和sequencerAddr，计算batchHashData：【本质是调用ethers.utils.solidityKeccak256进行哈希运算】

    ctx.input.batchHashData = calculateBatchHashData(
        ctx.input.batchL2Data,
        globalExitRoot,
        sequencerAddr
    );
    

  • 3.2）根据oldStateRoot、oldLocalExitRoot、newStateRoot、newLocalExitRoot、numBatch、timestamp，计算STARK input：【本质也是调用ethers.utils.solidityKeccak256进行哈希运算】

    ctx.globalHash = calculateStarkInput(
            oldStateRoot,
            oldLocalExitRoot,
            newStateRoot,
            newLocalExitRoot,
            ctx.input.batchHashData,
            numBatch,
            timestamp
    );
    

  • 3.3）对touchedAddress和touchedStorageSlots赋值为[]。
• 4）逐个处理arith.rom.json文件中program的各元素：【i为相应的序号】
  • 4.0）arith.rom.json中program第0个元素 l l l：

    {
    "inSTEP": "1",
    "setA": 1,
    "line": 3,
    "fileName": "arith.zkasm",
    "lineStr": "        STEP => A"
    },
    

    • inSTEP：若非空，设置op0=op0+inSTEP*i，且inSTEP[i]=l.inSTEP；否则，inSTEP[i]=0。
    • setA：若非空，则setA[i]=1,A0’=op0,A1’=op1,A2’=op2,A3’=op3,A4’=op4,A5’=op5,A6’=op6,A7’=op7；否则setA[i]=0, A0’=A0,A1’=A1,A2’=A2,A3’=A3,A4’=A4,A5’=A5,A6’=A6,A7’=A7。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPC0l.inSTEP100000000000001op0op1op2op3op4op5op6op71
  • 4.1）arith.rom.json中program第1个元素 l l l：

    {
    "CONST": "0",
    "assert": 1,
    "line": 4,
    "fileName": "arith.zkasm",
    "lineStr": "        0 :ASSERT"
    }
    

    • CONST：若设置，则CONST0[i]=l.CONST，op0=op0+l.CONST，CONST1[i]=0,CONST2[i]=0,CONST3[i]=0,CONST4[i]=0,CONST5[i]=0,CONST6[i]=0,CONST7[i]=0；否则若亦未设置CONSTL，则CONST0/1/2/3/4/5/6/7[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST70l.inSTEP10000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST00000002op0(同上一行)op1op2op3op4op5op6op72
  • 4.2）arith.rom.json中program第2个元素 l l l：

    {
    "CONST": "0",
    "setA": 1,
    "line": 6,
    "fileName": "arith.zkasm",
    "lineStr": "        0 => A"
    }
    

    • CONST：若设置，则CONST0[i]=l.CONST，op0=op0+l.CONST，CONST1[i]=0,CONST2[i]=0,CONST3[i]=0,CONST4[i]=0,CONST5[i]=0,CONST6[i]=0,CONST7[i]=0；否则若亦未设置CONSTL，则CONST0/1/2/3/4/5/6/7[i]=0。
    • setA：若非空，则setA[i]=1,A0’=op0,A1’=op1,A2’=op2,A3’=op3,A4’=op4,A5’=op5,A6’=op6,A7’=op7；否则setA[i]=0, A0’=A0,A1’=A1,A2’=A2,A3’=A3,A4’=A4,A5’=A5,A6’=A6,A7’=A7。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST70l.inSTEP10000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST0000000201op0(同上一行)op1op2op3op4op5op6op720000l.CONST00000003op0op1op2op3op4op5op6op73
  • 4.3）arith.rom.json中program第3个元素 l l l：

    {
    "inCntArith": "1",
    "assert": 1,
    "line": 7,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_ARITH :ASSERT"
    }
    

    • inCntArith：若设置，则op0=op0+l.inCntArith*cntArith[i]，inCntArith[i]=l.inCntArith；否则inCntArith[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArith0l.inSTEP1000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST000000000201op0(同上一行)op1op2op3op4op5op6op720000l.CONST000000000300op0op1op2op3op4op5op6op73000100000000l.inCntArith04op0(同上一行)op1op2op3op4op5op6op74
  • 4.4）arith.rom.json中program第4个元素 l l l：

    {
    "inCntBinary": "1",
    "assert": 1,
    "line": 8,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_BINARY :ASSERT"
    }
    

    • inCntBinary：若设置，则op0=op0+l.inCntBinary*cntBinary[i]，inCntBinary[i]=l.inCntBinary；否则inCntBinary[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinary0l.inSTEP100000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST00000000000201op0(同上一行)op1op2op3op4op5op6op720000l.CONST00000000000300op0op1op2op3op4op5op6op73000100000000l.inCntArith000400op0(同上一行)op1op2op3op4op5op6op7400010000000000inCntBinary05op0(同上一行)op1op2op3op4op5op6op75
  • 4.5）arith.rom.json中program第5个元素 l l l：

    {
    "inCntKeccakF": "1",
    "assert": 1,
    "line": 9,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_KECCAK_F: ASSERT"
    }
    

    • inCntKeccakF：若设置，则op0=op0+l.inCntKeccakF*cntKeccakF[i]，inCntKeccakF[i]=l.inCntKeccakF；否则inCntKeccakF[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakF0l.inSTEP10000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST0000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST0000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith00000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF06op0(同上一行)op1op2op3op4op5op6op706
  • 4.6）arith.rom.json中program第6个元素 l l l：

    {
    "inCntMemAlign": "1",
    "assert": 1,
    "line": 10,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_MEM_ALIGN :ASSERT"
    },
    

    • inCntMemAlign：若设置，则op0=op0+l.inCntMemAlign*cntMemAlign[i]，inCntMemAlign[i]=l.inCntMemAlign；否则inCntMemAlign[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAlign0l.inSTEP1000000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST000000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign07op0(同上一行)op1op2op3op4op5op6op707
  • 4.7）arith.rom.json中program第7个元素 l l l：

    {
    "inCntPoseidonG": "1",
    "assert": 1,
    "line": 11,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_POSEIDON_G :ASSERT"
    },
    

    • inCntPoseidonG：若设置，则op0=op0+l.inCntPoseidonG*cntPoseidonG[i]，inCntPoseidonG[i]=l.inCntPoseidonG；否则inCntPoseidonG[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonG0l.inSTEP100000000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST00000000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST00000000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith000000000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary0000000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF00000600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign000700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG08op0(同上一行)op1op2op3op4op5op6op708
  • 4.8）arith.rom.json中program第8个元素 l l l：

    {
    "inCntPaddingPG": "1",
    "assert": 1,
    "line": 12,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_PADDING_PG :ASSERT"
    }
    

    • inCntPaddingPG：若设置，则op0=op0+l.inCntPaddingPG*cntPaddingPG[i]，inCntPaddingPG[i]=l.inCntPaddingPG；否则inCntPaddingPG[i]=0。
    • assert：若设置，则assert[i]=1；否则，assert[i]=0。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonGinCntPaddingPGcntPaddingPG0l.inSTEP10000000000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST0000000000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST0000000000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith00000000000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary000000000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF0000000600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign00000700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG000800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG09op0(同上一行)op1op2op3op4op5op6op709
  • 4.9）arith.rom.json中program第9个元素 l l l：

    {
    "CONST": "0",
    "setA": 1,
    "setB": 1,
    "setC": 1,
    "setD": 1,
    "arith": 1,
    "arithEq0": 1,
    "line": 14,
    "fileName": "arith.zkasm",
    "lineStr": "        0 => A,B,C,D    :ARITH"
    },
    

    • CONST：若设置，则CONST0[i]=l.CONST，op0=op0+l.CONST，CONST1[i]=0,CONST2[i]=0,CONST3[i]=0,CONST4[i]=0,CONST5[i]=0,CONST6[i]=0,CONST7[i]=0；否则若亦未设置CONSTL，则CONST0/1/2/3/4/5/6/7[i]=0。
    • setA：若非空，则setA[i]=1,A0’=op0,A1’=op1,A2’=op2,A3’=op3,A4’=op4,A5’=op5,A6’=op6,A7’=op7；否则setA[i]=0, A0’=A0,A1’=A1,A2’=A2,A3’=A3,A4’=A4,A5’=A5,A6’=A6,A7’=A7。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。
    • arith：若非空，则cntArith’=cntArith+1；否则，cntArith’=cntArith。
    • arithEq0：即计算上面的EQ0，若非空，则arith[i]=1，arithEq0[i]=1；否则视具体的计算设定。同时会在required.Arith中存入required.Arith.push({x1: A, y1: B, x2: C, y2: D, x3: Fr.zero, y3: op, selEq0: 1, selEq1: 0, selEq2: 0, selEq3: 0});。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonGinCntPaddingPGcntPaddingPGaritharithEq0setBB0-B7setCC0-C7setDD0-D70l.inSTEP1000000000000000000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST000000000000000000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000000000000000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000000000000000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000000000000000600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign0000000000000700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG00000000000800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG000000000901op0(同上一行)op1op2op3op4op5op6op7090000000000000100000000001110101010op0op1op2op3op4op5op6op70101op0-op7op0-op7op0-op7
  • 4.10）arith.rom.json中program第10个元素 l l l：

    {
    "inCntArith": "1",
    "setA": 1,
    "line": 16,
    "fileName": "arith.zkasm",
    "lineStr": "        CNT_ARITH => A"
    }
    

    • inCntArith：若设置，则op0=op0+l.inCntArith*cntArith[i]，inCntArith[i]=l.inCntArith；否则inCntArith[i]=0。
    • setA：若非空，则setA[i]=1,A0’=op0,A1’=op1,A2’=op2,A3’=op3,A4’=op4,A5’=op5,A6’=op6,A7’=op7；否则setA[i]=0, A0’=A0,A1’=A1,A2’=A2,A3’=A3,A4’=A4,A5’=A5,A6’=A6,A7’=A7。
    • 不包含JMP/JMPC/JMPN：isNeg[i]=0，zkPC’=zkPC+1，JMP[i]=0，JMPN[i]=0，JMPC[i]=0。 iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonGinCntPaddingPGcntPaddingPGaritharithEq0setBB0-B7setCC0-C7setDD0-D70l.inSTEP1000000000000000000000000000000000000000000100op0op1op2op3op4op5op6op7010001l.CONST000000000000000000000000000201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000000000000000300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000000000000000400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000000000000000500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000000000000000600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign0000000000000700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG00000000000800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG000000000901op0(同上一行)op1op2op3op4op5op6op709000000000000010000000000111010101001op0op1op2op3op4op5op6op7010000000000000l.inCntArith10000000000000op0-op70op0-op70op0-op711op0op1op2op3op4op5op6op70111op0-op7(同上一行)op0-op7(同上一行)op0-op7(同上一行)

。。。。。 以此类推，给各个二级状态机的input信息见required内容：

	const required = {
        Byte4: {},
        Arith: [],
        Binary: [],
        PaddingKK: [],
        PaddingPG: [],
        PoseidonG: [],
        Mem: [],
        MemAlign: [],
        Storage: []
    };

如本例中：

• 1）给Byte4的input为：

  {
   "0": true,
   "4294967295": true
  }
  

• 2）给Arith的input为：

  required.Arith.push({x1: A, y1: B, x2: C, y2: D, x3: Fr.zero, y3: op, selEq0: 1, selEq1: 0, selEq2: 0, selEq3: 0});
  

2.2 Byte4.pil隐私多项式赋值

smByte4.execute(cmPols.Byte4, requiredMain.Byte4);

如本例中，给Byte4的input为：【 4294967295 = 2 32 − 1 4294967295=2^{32}-1 4294967295=232−1】

{
	"0": true,
	"4294967295": true
}

byte4 execution trace执行逻辑为：

module.exports.execute = async function (pols, input) {

    const N = pols.freeIN.length;

    let p=0;
    let last = 0;
    Object.keys(input).forEach( (n) => {
        const num = Number(n);
        pols.freeIN[p] = BigInt(num >>> 16);//存储num的高16位
        pols.out[p] = BigInt(last);//存储上一num值
        p++;
        pols.freeIN[p] = BigInt(num & 0xFFFF); //存储num的低16位
        pols.out[p] = BigInt(num >>> 16);//存储num的高16位，即等于freeIN[p-1]
        p++;
        last = num;
    });
    pols.freeIN[p] = 0n;
    pols.out[p] = BigInt(last);//存储上一num值
    p++;
    pols.freeIN[p] = 0n;
    pols.out[p] = 0n;
    p++;

    if (p >= N) {
        throw new Error("Too many byte4");
    }

    while (p