• Polygon zkEVM Arithmetic状态机

    1. 引言

    前序博客有：

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

    详细可参看审计培训视频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 ,

    EQ0:x1⋅y1+x2−y2⋅2256−y3=0,EQ1:s⋅x2−s⋅x1−y2+y1+q0⋅p=0,EQ2:2⋅s⋅y1−3⋅x1⋅x1+q0⋅p=0,EQ3:s⋅s−x1−x2−x3+q1⋅p=0,EQ4:s⋅x1−s⋅x3−y1−y3+q2⋅p=0," role="presentation" style="position: relative;">EQ0:x1⋅y1+x2−y2⋅2256−y3=0,EQ1:s⋅x2−s⋅x1−y2+y1+q0⋅p=0,EQ2:2⋅s⋅y1−3⋅x1⋅x1+q0⋅p=0,EQ3:s⋅s−x1−x2−x3+q1⋅p=0,EQ4:s⋅x1−s⋅x3−y1−y3+q2⋅p=0,
    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];

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    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:

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    经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
 }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240

    在这里插入图片描述

    【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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    基本流程为：

    • 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);

      • 1
    • 5）根据requiredMain.Byte4，对’Byte4‘中的隐私多项式赋值。
      await smByte4.execute(cmPols.Byte4, requiredMain.Byte4);

      • 1
    • 6）根据requiredMain.Arith || []，对’Arith’中的隐私多项式赋值。
      await smBinary.execute(cmPols.Binary, requiredMain.Binary || []);

      • 1

    接下来重点关注以上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": {}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    2.1 Main.pil隐私多项式赋值

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

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

    • 1

    smMain.execute的核心流程为：

    • 1）从input.db中加载数据库信息，并基于数据库信息构建sparse merkle树：
      const db = new MemDB(Fr, input.db);
const smt = new SMT(db, poseidon, Fr);

      • 1
      • 2
    • 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);

      • 1
    • 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
);

        • 1
        • 2
        • 3
        • 4
        • 5
      • 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
);

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 8
        • 9
      • 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"
},

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPC
          0l.inSTEP10000000000000
          1op0op1op2op3op4op5op6op71
      • 4.1）arith.rom.json中program第1个元素 l l l：
        {
"CONST": "0",
"assert": 1,
"line": 4,
"fileName": "arith.zkasm",
"lineStr": "        0 :ASSERT"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7
          0l.inSTEP10000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST0000000
          2op0(同上一行)op1op2op3op4op5op6op72
      • 4.2）arith.rom.json中program第2个元素 l l l：
        {
"CONST": "0",
"setA": 1,
"line": 6,
"fileName": "arith.zkasm",
"lineStr": "        0 => A"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7
          0l.inSTEP10000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST0000000
          201op0(同上一行)op1op2op3op4op5op6op720000l.CONST0000000
          3op0op1op2op3op4op5op6op73
      • 4.3）arith.rom.json中program第3个元素 l l l：
        {
"inCntArith": "1",
"assert": 1,
"line": 7,
"fileName": "arith.zkasm",
"lineStr": "        CNT_ARITH :ASSERT"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArith
          0l.inSTEP1000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST000000000
          201op0(同上一行)op1op2op3op4op5op6op720000l.CONST000000000
          300op0op1op2op3op4op5op6op73000100000000l.inCntArith0
          4op0(同上一行)op1op2op3op4op5op6op74
      • 4.4）arith.rom.json中program第4个元素 l l l：
        {
"inCntBinary": "1",
"assert": 1,
"line": 8,
"fileName": "arith.zkasm",
"lineStr": "        CNT_BINARY :ASSERT"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinary
          0l.inSTEP100000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST00000000000
          201op0(同上一行)op1op2op3op4op5op6op720000l.CONST00000000000
          300op0op1op2op3op4op5op6op73000100000000l.inCntArith000
          400op0(同上一行)op1op2op3op4op5op6op7400010000000000inCntBinary0
          5op0(同上一行)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"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakF
          0l.inSTEP10000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST0000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST0000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith00000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF0
          6op0(同上一行)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"
},

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAlign
          0l.inSTEP1000000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST000000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000
          600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign0
          7op0(同上一行)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"
},

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonG
          0l.inSTEP100000000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST00000000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST00000000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith000000000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary0000000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF00000
          600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign000
          700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG0
          8op0(同上一行)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"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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。
          iinSTEPsetAA0A1A2A3A4A5A6A7isNegzkPCJMPJMPNJMPCassertCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7inCntArithcntArithinCntBinarycntBinaryinCntKeccakFcntKeccakFinCntMemAligncntMemAligninCntPoseidonGcntPoseidonGinCntPaddingPGcntPaddingPG
          0l.inSTEP10000000000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST0000000000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST0000000000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith00000000000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary000000000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF0000000
          600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign00000
          700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG000
          800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG0
          9op0(同上一行)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"
},

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 8
        • 9
        • 10
        • 11
        • 12
        • 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-D7
          0l.inSTEP1000000000000000000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST000000000000000000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000000000000000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000000000000000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000000000000000
          600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign0000000000000
          700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG00000000000
          800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG000000000
          901op0(同上一行)op1op2op3op4op5op6op70900000000000001000000000011101010
          10op0op1op2op3op4op5op6op70101op0-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"
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 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-D7
          0l.inSTEP1000000000000000000000000000000000000000000
          100op0op1op2op3op4op5op6op7010001l.CONST000000000000000000000000000
          201op0(同上一行)op1op2op3op4op5op6op7020000l.CONST000000000000000000000000000
          300op0op1op2op3op4op5op6op703000100000000l.inCntArith0000000000000000000
          400op0(同上一行)op1op2op3op4op5op6op70400010000000000inCntBinary00000000000000000
          500op0(同上一行)op1op2op3op4op5op6op7050001000000000000l.inCntKeccakF000000000000000
          600op0(同上一行)op1op2op3op4op5op6op706000100000000000000l.inCntMemAlign0000000000000
          700op0(同上一行)op1op2op3op4op5op6op707000100000000000000000l.inCntPoseidonG00000000000
          800op0(同上一行)op1op2op3op4op5op6op7080001000000000000000000l.inCntPaddingPG000000000
          901op0(同上一行)op1op2op3op4op5op6op70900000000000001000000000011101010
          1001op0op1op2op3op4op5op6op7010000000000000l.inCntArith10000000000000op0-op70op0-op70op0-op7
          11op0op1op2op3op4op5op6op70111op0-op7(同上一行)op0-op7(同上一行)op0-op7(同上一行)

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    如本例中：

    • 1）给Byte4的input为：
      {
 "0": true,
 "4294967295": true
}

      • 1
      • 2
      • 3
      • 4
    • 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});

      • 1

    2.2 Byte4.pil隐私多项式赋值

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

    • 1

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

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

    • 1
    • 2
    • 3
    • 4

    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<N) {
        pols.freeIN[p] = 0n;
        pols.out[p] = 0n;
        p++;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    byte4常量多项式逻辑为：

    module.exports.buildConstants = async function (pols) {
    const N = pols.SET.length;

    for ( let i=0; i<N; i++) pols.SET[i] = (i % 2 == 0) ? 1n : 0n;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    即本例实际赋值情况为：

    indexSETpols.freeINpols.out
    0100
    1000
    21655350
    406553565535
    5104294967295
    6000
    7100
    ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮

    根据byte4.pil可知，相应的约束逻辑为：

    /*
This state machine is able to builds any number of 4 bytes (32 bits)


Example for building numbers: 0x00030007, 0x12345678, 0x00050009 and 0
        SET     freeIN  out        out'
w^0     1       3       0          3
w^1     0       7       3          0x00030007
w^2     1       0x1234  0x00030007 0x1234
w^3     0       0x5678  0x1234     0x12345678
w^4     1       5       0x12345678 5
w^5     0       9       5          0x50009
w^6     1       0       0x50009    0
w^7     0       0       0          0

*/

include "global.pil";

namespace Byte4(%N);
    /// Constant Polynomials
    pol constant SET;    // 1, 0, 1, 0, 1, 0 ......

    /// State Polynomials
    pol commit freeIN;
    pol commit out;

    freeIN in Global.BYTE2;  // 0, 1, 2,       , 65535

    out' = SET*freeIN +
           (1-SET)*(out * 2**16 + freeIN);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    2.3 Arith.pil隐私多项式赋值

    给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});

    • 1

    本例中具体值为：

    A: 14474011154664524427946373126085988481658748083205070504932198000989141204993 (0x2000000000000000000000000000000000000000000000000000000000000001)
B: 256 (0x100)
C: 115 (0x73)
D: 32 (0x20)
op: 371 (0x173)

    • 1
    • 2
    • 3
    • 4
    • 5

    满足的EQ0关系为： A ∗ B + C = D ∗ 2 256 + o p A*B+C=D*2^{256}+op A∗B+C=D∗2256+op。

    arith.pil中的常量多项式赋值见：Polygon zkEVM中的常量多项式 中“7. arith.pil中的常量多项式”。

    仍然以EQ0为例， EQ 0  ⁣ : x 1 ⋅ y 1 + x 2 − y 2 ⋅ 2 256 − y 3 = 0

    EQ0:x1⋅y1+x2−y2⋅2256−y3=0" role="presentation" style="position: relative;">EQ0:x1⋅y1+x2−y2⋅2256−y3=0
    EQ0​:​x1​⋅y1​+x2​−y2​⋅2256−y3​=0​，将每个寄存器以16个16bit寄存器表示，并借助school multiplication算法：
    在这里插入图片描述
    从而有：

    • 第0步： e q 0 = ( x 1 [ 0 ] ⋅ y 1 [ 0 ] ) + x 2 [ 0 ] − y 3 [ 0 ] \mathbf{eq}_0 = (x_1[0] \cdot y_1[0]) + x_2[0] - y_3[0] eq0​=(x1​[0]⋅y1​[0])+x2​[0]−y3​[0].
    • 第1步： e q 1 = ( x 1 [ 0 ] ⋅ y 1 [ 1 ] ) + ( x 1 [ 1 ] ⋅ y 1 [ 0 ] ) + x 2 [ 1 ] − y 3 [ 1 ] \mathbf{eq}_1 = (x_1[0] \cdot y_1[1]) + (x_1[1] \cdot y_1[0]) + x_2[1] - y_3[1] eq1​=(x1​[0]⋅y1​[1])+(x1​[1]⋅y1​[0])+x2​[1]−y3​[1].
    • 第2步： e q 2 = ( x 1 [ 0 ] ⋅ y 1 [ 2 ] ) + ( x 1 [ 1 ] ⋅ y 1 [ 1 ] ) + ( x 1 [ 2 ] ⋅ y 1 [ 0 ] ) + x 2 [ 2 ] − y 3 [ 2 ] \mathbf{eq}_2 = (x_1[0] \cdot y_1[2]) + (x_1[1] \cdot y_1[1]) + (x_1[2] \cdot y_1[0]) + x_2[2] - y_3[2] eq2​=(x1​[0]⋅y1​[2])+(x1​[1]⋅y1​[1])+(x1​[2]⋅y1​[0])+x2​[2]−y3​[2].
    • 第15步： e q 15 = ( x 1 [ 0 ] ⋅ y 1 [ 15 ] ) + ( x 1 [ 1 ] ⋅ y 1 [ 14 ] ) + ⋯ + x 2 [ 15 ] − y 3 [ 15 ] \mathbf{eq}_{15} = (x_1[0] \cdot y_1[15]) + (x_1[1] \cdot y_1[14]) + \dots + x_2[15] - y_3[15] eq15​=(x1​[0]⋅y1​[15])+(x1​[1]⋅y1​[14])+⋯+x2​[15]−y3​[15].
    • 第16步，此时才会引入 y 2 y_2 y2​，且 x 2 , y 3 x_2,y_3 x2​,y3​已处理完毕： e q 16 = ( x 1 [ 1 ] ⋅ y 1 [ 15 ] ) + ( x 1 [ 2 ] ⋅ y 1 [ 14 ] ) + ⋯ − y 2 [ 0 ] \mathbf{eq}_{16} = (x_1[1] \cdot y_1[15]) + (x_1[2] \cdot y_1[14]) + \dots - y_2[0] eq16​=(x1​[1]⋅y1​[15])+(x1​[2]⋅y1​[14])+⋯−y2​[0]
    • 第17步： e q 17 = ( x 1 [ 2 ] ⋅ y 1 [ 15 ] ) + ( x 1 [ 3 ] ⋅ y 1 [ 14 ] ) + ⋯ − y 2 [ 1 ] \mathbf{eq}_{17} = (x_1[2] \cdot y_1[15]) + (x_1[3] \cdot y_1[14]) + \dots - y_2[1] eq17​=(x1​[2]⋅y1​[15])+(x1​[3]⋅y1​[14])+⋯−y2​[1]
    • ⋯ \cdots ⋯
    • 第31步： e q 31 = − y 2 [ 15 ] \mathbf{eq}_{31}=-y_2[15] eq31​=−y2​[15]。

    相应的计算见：sm_arith_eq0.js。
    不过，以上计算中未考虑进位（carry）的情况。需引入临时变量let carry = [0n, 0n, 0n];来存储进位信息（ e q + carry = carry ′ ⋅ 2 16 \mathbf{eq}+\text{carry}=\text{carry}'\cdot 2^{16} eq+carry=carry′⋅216），并将每一步累计的进位信息分别存储在carryL和carryH两个寄存器中： carry = carry L + carry H ⋅ 2 18 \text{carry} = \text{carry}_L + \text{carry}_H \cdot 2^{18} carry=carryL​+carryH​⋅218。

     		let carry = [0n, 0n, 0n];
        const eqIndexToCarryIndex = [0, 0, 0, 1, 2];
		for (let step = 0; step < 32; ++step) {
            eqIndexes.forEach((eqIndex) => {
                let carryIndex = eqIndexToCarryIndex[eqIndex];
                eq[eqIndex] = eqCalculates[eqIndex](pols, step, offset); //调用sm_arith_eq0.js
                pols.carryL[carryIndex][offset + step] = Fr.e((carry[carryIndex]) % (2n**18n));
                pols.carryH[carryIndex][offset + step] = Fr.e((carry[carryIndex]) / (2n**18n));
                carry[carryIndex] = (eq[eqIndex] + carry[carryIndex]) / (2n ** 16n);
            });
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    arith.pil中包含的约束有：

    • 1）使用CLK[31]寄存器，对x1,y1,x2,y2,x3,y3,s,q0,q1,q2,selEq[0-3]进行锁存。
    • 2）限定x1,y1,x2,y2,x3,y3,s,q0,q1,q2（为16个16-bit寄存器）中每个寄存器的取值范围为 [ 0 , 2 16 − 1 ] [0,2^{16}-1] [0,216−1]，使用plookup约束。如：
      x1[0]*CLK[0] + x1[1]*CLK[1] + x1[2]*CLK[2] + x1[3]*CLK[3] + x1[4]*CLK[4] + x1[5]*CLK[5] + x1[6]*CLK[6] + x1[7]*CLK[7]
   + x1[8]*CLK[8] + x1[9]*CLK[9] + x1[10]*CLK[10] + x1[11]*CLK[11] + x1[12]*CLK[12] + x1[13]*CLK[13] + x1[14]*CLK[14] + x1[15]*CLK[15]
   + y1[0]*CLK[16] + y1[1]*CLK[17] + y1[2]*CLK[18] + y1[3]*CLK[19] + y1[4]*CLK[20] + y1[5]*CLK[21] + y1[6]*CLK[22] + y1[7]*CLK[23]
   + y1[8]*CLK[24] + y1[9]*CLK[25] + y1[10]*CLK[26] + y1[11]*CLK[27] + y1[12]*CLK[28] + y1[13]*CLK[29] + y1[14]*CLK[30] + y1[15]*CLK[31] in Global.BYTE2;

      • 1
      • 2
      • 3
      • 4
    • 3）以eq0为例，按以上0~31步计算：EQ0: A(x1) * B(y1) + C(x2) = D (y2) * 2 ** 256 + op (y3)
    • 4）将每一步的eq0_i求和：
      pol eq0 = eq0_0*CLK[0] + eq0_1*CLK[1] + eq0_2*CLK[2] + eq0_3*CLK[3] + eq0_4*CLK[4] + eq0_5*CLK[5] + eq0_6*CLK[6] + eq0_7*CLK[7]
   + eq0_8*CLK[8] + eq0_9*CLK[9] + eq0_10*CLK[10] + eq0_11*CLK[11] + eq0_12*CLK[12] + eq0_13*CLK[13] + eq0_14*CLK[14] + eq0_15*CLK[15]
   + eq0_16*CLK[16] + eq0_17*CLK[17] + eq0_18*CLK[18] + eq0_19*CLK[19] + eq0_20*CLK[20] + eq0_21*CLK[21] + eq0_22*CLK[22] + eq0_23*CLK[23]
   + eq0_24*CLK[24] + eq0_25*CLK[25] + eq0_26*CLK[26] + eq0_27*CLK[27] + eq0_28*CLK[28] + eq0_29*CLK[29] + eq0_30*CLK[30] + eq0_31*CLK[31];

      • 1
      • 2
      • 3
      • 4
    • 5）限定selEq[0]、selEq[1]、selEq[2]、selEq[3]的取值只能为0或1：
      selEq[0] * (1-selEq[0]) = 0;
selEq[1] * (1-selEq[1]) = 0;
selEq[2] * (1-selEq[2]) = 0;
selEq[3] * (1-selEq[3]) = 0;

      • 1
      • 2
      • 3
      • 4
    • 6）使用CLK[0]寄存器，对carryL[0-2]以及carryH[0-2]进行锁存。与CLK[31]的锁存逻辑相反。
    • 7）限定carryL[0-2]的取值范围为 [ 0 , 2 18 − 1 ] [0,2^{18}-1] [0,218−1]，使用plookup约束。
      carryL[0] in GL_SIGNED_18BITS;
carryL[1] in GL_SIGNED_18BITS;
carryL[2] in GL_SIGNED_18BITS;

      • 1
      • 2
      • 3
    • 8）限定carryH[0]、carryH[1]、carryH[2]的取值，使用plookup约束：
      {carryH[0], carryH[1], carryH[2]} in {GL_SIGNED_4BITS_C0, GL_SIGNED_4BITS_C1, GL_SIGNED_4BITS_C2}; // 3 * (4+1) = 15 bits

      • 1
    • 9）对各步中的进位进行约束：
      // eq + carry = carry' * 2**16
// carry = cl + ch * 2**18
// eq + cl + ch * 2**18 = cl 2**16 + ch * 2**34

selEq[0] * (eq0 + carryL[0] + 2**18 * carryH[0]) = selEq[0] * (carryL[0]' * 2**16 + carryH[0]' * 2**34);

      • 1
      • 2
      • 3
      • 4
      • 5

    参考资料

    [1] The Arithmetic State Machine

    附录：Polygon Hermez 2.0 zkEVM系列博客

  • 相关阅读:
    源启容器平台KubeGien 打造云原生转型的破浪之舰
    腾讯云~docker onlyoffice7.1.1 word excel ppt在线编辑、在线预览_部署01
    C++ vector使用数组进行初始化
    【Java】Spring scurity + JWT 前后端分离
    uview picker 组件实现只要省和市的两级数据联动选择器
    [鹏城杯 2022]简单的php - 无数字字母RCE+取反【*】
    井字棋游戏
    Android绘制的Window和View
    【C++航海王：追寻罗杰的编程之路】C++11(二)
    Bloc入门之Cubit详解
  • 原文地址：https://blog.csdn.net/mutourend/article/details/126603577