• Polygon zkEVM的pil-stark Fibonacci状态机代码解析

    1. 引言

    前序博客有：

    开源代码见：

    中的test/sm_fibonacci/Fibonacci状态机，对应的序列为：
    1 , 2 , 5 , 29 , ⋯ 1,2,5,29,\cdots 1,2,5,29,⋯
    对应的逻辑为： a i + 2 = a i 2 + a i + 1 2 a_{i+2}=a_{i}^2+a_{i+1}^2 ai+2​=ai2​+ai+12​。需要判定第 2 10 = 1024 2^{10}=1024 210=1024个元素是否为 74469561660084004 74469561660084004 74469561660084004。
    将其execution trace表示为：具有寄存器 A = ( A 0 , A 1 , A 2 , … , A 1023 ) \mathbf{A} = ( A_0, A_1, A_2, \dots , A_{1023} ) A=(A0​,A1​,A2​,…,A1023​)和 B = ( B 0 , B 1 , B 2 , … , B 1023 ) \mathbf{B} = ( B_0, B_1, B_ 2, \dots , B_{1023} ) B=(B0​,B1​,B2​,…,B1023​)的状态机，第 i i i个状态为 ( A i , B i ) (A_i,B_i) (Ai​,Bi​)，初始状态为 A 0 = i n 1 = 1 , B 0 = i n 2 = 2 A_0=in_1=1,B_0=in_2=2 A0​=in1​=1,B0​=in2​=2。相应的约束为：

    • 1）Transition constraints： A i + 1 = B i , B i + 1 = A i 2 + B i 2 A_{i+1}=B_i,B_{i+1}=A_{i}^2+B_{i}^2 Ai+1​=Bi​,Bi+1​=Ai2​+Bi2​（ i = { 0 , ⋯   , 1022 } i=\{0,\cdots,1022\} i={0,⋯,1022}）
    • 2）Boundary constraints： A 0 = 1 , B 0 = 2 , B 1023 = o u t = 74469561660084004 A_0=1,B_0=2,B_{1023}=out=74469561660084004 A0​=1,B0​=2,B1023​=out=74469561660084004

    为了便于设置STARK的polynomial identities，需额外再引入2个常量寄存器 i s I n i t i a l = ( 1 , 0 , 0 , ⋯   , 0 ) , i s L a s t = ( 0 , 0 , 0 , ⋯   , 1 ) \mathbf{isInitial}=(1,0,0,\cdots,0), \mathbf{isLast}=(0,0,0,\cdots,1) isInitial=(1,0,0,⋯,0),isLast=(0,0,0,⋯,1)，将以上transition和boundary约束表示为：（ i = { 0 , ⋯   , 1023 } i=\{0,\cdots,1023\} i={0,⋯,1023}）
    ( A i + 1 − B i ) ∗ ( 1 − isLast i ) = 0 (A_{i+1}-B_i)*(1-\text{isLast}_i)=0 (Ai+1​−Bi​)∗(1−isLasti​)=0
    ( B i + 1 − ( A i 2 + B i 2 ) ) ∗ ( 1 − isLast i ) = 0 (B_{i+1}-(A_i^2+B_i^2))*(1-\text{isLast}_i)=0 (Bi+1​−(Ai2​+Bi2​))∗(1−isLasti​)=0
    isInitial i ∗ ( A i − i n 1 ) = 0 \text{isInitial}_i*(A_i-in_1)=0 isInitiali​∗(Ai​−in1​)=0
    isInitial i ∗ ( B i − i n 2 ) = 0 \text{isInitial}_i*(B_i-in_2)=0 isInitiali​∗(Bi​−in2​)=0
    isLast i ∗ ( B i − o u t ) = 0 \text{isLast}_i*(B_i-out)=0 isLasti​∗(Bi​−out)=0

    将寄存器 A , B , i s I n i t i a l , i s L a s t \mathbf{A}, \mathbf{B}, \mathbf{isInitial}, \mathbf{isLast} A,B,isInitial,isLast 分别插值为多项式 l 2 ( x ) , l 1 ( x ) , L 1 ( x ) , L L A S T l_2(x),l_1(x),L_1(x),LLAST l2​(x),l1​(x),L1​(x),LLAST表示。【其中 ω \omega ω为 1024 1024 1024-th root of unity。】

    序号 x x x A \mathbf{A} A（ l 2 ( x ) l_2(x) l2​(x)多项式） B \mathbf{B} B（ l 1 ( x ) l_1(x) l1​(x)多项式） i s I n i t i a l \mathbf{isInitial} isInitial（ L 1 ( x ) L_1(x) L1​(x)多项式） i s L a s t \mathbf{isLast} isLast（ L L A S T ( x ) LLAST(x) LLAST(x)多项式）
    0 ω 0 \omega^0 ω01210
    1 ω 1 \omega^1 ω12500
    2 ω 2 \omega^2 ω252900
    ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
    1023 ω 1023 \omega^{1023} ω1023…7446956166008400401

    该状态机核心代码见fibonacci.pil文件：

    	constant %N = 2**10;
	
	namespace Fibonacci(%N);

    pol constant L1, LLAST;
    pol commit l1,l2;
    
    pol l2c = l2;

    public in1 = l2c(0);
    public in2 = l1(0);
    public out = l1(%N-1);

    (l2' - l1)*(1-LLAST) = 0;

    pol next = l1*l1 + l2*l2;

    (l1' - next)*(1-LLAST) = 0;

    L1 * (l2 - :in1) = 0;
    L1 * (l1 - :in2) = 0;
    LLAST * (l1 - :out) = 0;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    初始状态见fibonacci.input.json文件：

    [1, 2]

    • 1

    STARK待证明的场景为：

    • 公开信息：常量多项式 L 1 ( x ) L_1(x) L1​(x)和 L L A S T ( x ) LLAST(x) LLAST(x)，commitment值 c o m ( l 1 ( x ) ) com(l_1(x)) com(l1​(x))和 c o m ( l 2 ( x ) ) com(l_2(x)) com(l2​(x))，Fibonacci数列第一二项为 i n 1 = 1 , i n 2 = 2 in_1=1,in_2=2 in1​=1,in2​=2，第1024项输出为 o u t = 74469561660084004 out=74469561660084004 out=74469561660084004
    • witness：多项式 l 1 ( x ) , l 2 ( x ) l_1(x),l_2(x) l1​(x),l2​(x)
    • 待证明relation：对于 x = { ω 0 , ω 1 , ⋯   , ω 1023 } x=\{\omega^0,\omega^1,\cdots, \omega^{1023}\} x={ω0,ω1,⋯,ω1023}，有：
      • ( l 2 ( ω ⋅ x ) − l 1 ( x ) ) ⋅ ( 1 − L L A S T ( x ) ) = 0 (l_2(\omega\cdot x)-l_1(x))\cdot (1-LLAST(x))=0 (l2​(ω⋅x)−l1​(x))⋅(1−LLAST(x))=0
      • ( l 1 ( ω ⋅ x ) − ( ( l 2 ( x ) ) 2 + ( l 1 ( x ) ) 2 ) ) ⋅ ( 1 − L L A S T ( x ) ) = 0 (l_1(\omega\cdot x)-((l_2(x))^2+(l_1(x))^2))\cdot (1-LLAST(x))=0 (l1​(ω⋅x)−((l2​(x))2+(l1​(x))2))⋅(1−LLAST(x))=0
      • L 1 ( x ) ⋅ ( l 2 ( x ) − i n 1 ) = 0 L_1(x)\cdot (l_2(x)-in_1)=0 L1​(x)⋅(l2​(x)−in1​)=0
      • L 1 ( x ) ⋅ ( l 1 ( x ) − i n 2 ) L_1(x)\cdot (l_1(x)-in_2) L1​(x)⋅(l1​(x)−in2​)
      • L L A S T ( x ) ⋅ ( l 1 ( x ) − o u t ) = 0 LLAST(x)\cdot (l_1(x)-out)=0 LLAST(x)⋅(l1​(x)−out)=0

    基于的域const F = new F1Field();即为Goldilocks域 p = 2 64 − 2 32 + 1 p=2^{64}-2^{32}+1 p=264−232+1，详细参见：

    代码中根据 f ( x ) f(x) f(x)表达 f ( ω ⋅ x ) f(\omega \cdot x) f(ω⋅x)多项式为：

    r = pols.cm[exp.id].v_n;
if (exp.next) r = getPrime(r);

function getPrime(p) {
	const r = p.slice(1);
	r[p.length-1] = p[0];
	return r;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    2. 编译pil生成constant多项式

    debug运行fibonacci buildconst：运行状态机中main_buildconst_fibonacci.js，输出为fibonacci.const：

    /usr/local/bin/node --max-old-space-size=32000 test/sm_fibonacci/main_buildconst_fibonacci.js -o tmp/fibonacci.const
file Generated Correctly

    • 1
    • 2

    main_buildconst_fibonacci.js核心代码为：

    async function run() {

    const outputFile = typeof(argv.output) === "string" ?  argv.output.trim() : "fibonacci.const";

    const F = new F1Field();
    const pil = await compile(F, path.join(__dirname, "fibonacci_main.pil"));

    const constPols = newConstantPolsArray(pil);

    await smFibonacci.buildConstants(constPols.Fibonacci);

    await constPols.saveToFile(outputFile);

    console.log("file Generated Correctly");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.1 编译pil文件

    const pil = await compile(F, path.join(__dirname, "fibonacci_main.pil"));

    • 1

    compile是对.pil文件进行编译：

    # $ cd pilcom
pilcom lanyu$ node src/pil.js ../pil-stark/test/sm_fibonacci/fibonacci_main.pil -o fibonacci.compile.json
Input Pol Commitmets: 2
Q Pol Commitmets: 1
Constant Pols: 2
Im Pols: 2
plookupIdentities: 0
permutationIdentities: 0
connectionIdentities: 0
polIdentities: 5

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

    编译后的结果为：

    {
 "nCommitments": 2, # 即pil中，以`poly commit`标记的多项式数量。
 "nQ": 1, # 即pil中以多项式为粒度，degree为2的多项式总数。如`pol next = l1*l1 + l2*l2;`，会 nQ++。
 "nIm": 2, # 非`poly constant`或`poly commit`标记的多项式数量。即pil中，仅以`poly`标记的中间多项式总数。
 "nConstants": 2, # 即pil中，以`poly constant`标记的多项式数量。
 "publics": [ # 对应pil中的`public`关键字
  { # 对应`public in1 = l2c(0);`
   "polType": "imP",
   "polId": 0,
   "idx": 0,
   "id": 0,
   "name": "in1"
  },
  { # 对应`public in2 = l1(0);`
   "polType": "cmP",
   "polId": 0,
   "idx": 0,
   "id": 1,
   "name": "in2"
  },
  { # 对应`public out = l1(%N-1);`
   "polType": "cmP",
   "polId": 0,
   "idx": 1023,
   "id": 2,
   "name": "out"
  }
 ],
 "references": {
  "Fibonacci.L1": {
   "type": "constP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.LLAST": {
   "type": "constP",
   "id": 1,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l1": {
   "type": "cmP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l2": {
   "type": "cmP",
   "id": 1,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l2c": {
   "type": "imP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.next": {
   "type": "imP",
   "id": 2,
   "polDeg": 1024,
   "isArray": false
  }
 },
 "expressions": [
  { # 0. l2，对应中间赋值 `pol l2c = l2;`？？？
   "op": "cm",
   "deg": 1,
   "id": 1,
   "next": false
  },
  { # 1. 对应约束 `(l2' - l1)*(1-LLAST) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    {
     "op": "mul",
     "deg": 2,
     "values": [
      { # l2'-l1
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2'
         "op": "cm",
         "deg": 1,
         "id": 1,
         "next": true
        },
        { # l1
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        }
       ]
      },
      {
       "op": "sub",
       "deg": 1,
       "values": [
        { # 1-LLAST
         "op": "number",
         "deg": 0,
         "value": "1"
        },
        { # LLAST
         "op": "const",
         "deg": 1,
         "id": 1,
         "next": false
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 2. 对应中间赋值 `pol next = l1*l1 + l2*l2;`
   "op": "add",
   "deg": 1,
   "idQ": 0,
   "values": [
    { # l1*l1
     "op": "mul",
     "deg": 2,
     "values": [
      { # l1
       "op": "cm",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # l1
       "op": "cm",
       "deg": 1,
       "id": 0,
       "next": false
      }
     ]
    },
    { # l2*l2
     "op": "mul",
     "deg": 2,
     "values": [
      { # l2
       "op": "cm",
       "deg": 1,
       "id": 1,
       "next": false
      },
      { # l2
       "op": "cm",
       "deg": 1,
       "id": 1,
       "next": false
      }
     ]
    }
   ]
  },
  { # 3. 对应约束`(l1' - next)*(1-LLAST) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # 对应 `(l1' - next)*(1-LLAST)`
     "op": "mul",
     "deg": 2,
     "values": [
      { # l1'-next
       "op": "sub",
       "deg": 1,
       "values": [
        { # l1'
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": true
        },
        { # next
         "op": "exp", 
         "deg": 1,
         "id": 2,
         "next": false
        }
       ]
      },
      {
       "op": "sub",
       "deg": 1,
       "values": [
        { # 1
         "op": "number",
         "deg": 0,
         "value": "1"
        },
        { # LLAST
         "op": "const",
         "deg": 1,
         "id": 1,
         "next": false
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ],
   "deps": [ # 表示依赖的中间多项式id，此处对应为next。
    2
   ]
  },
  { # 4. 对应约束为`L1 * (l2 - :in1) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # 对应 `L1*(l2-in1)`
     "op": "mul",
     "deg": 2,
     "values": [
      { # L1
       "op": "const",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # 对应`l2-in1`
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2
         "op": "cm",
         "deg": 1,
         "id": 1,
         "next": false
        },
        { # in1
         "op": "public",
         "deg": 0,
         "id": 0
        }
       ]
      }
     ]
    },
    { # 0
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 5. 对应约束`L1 * (l1 - :in2) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # L1*(l1-in2)
     "op": "mul",
     "deg": 2,
     "values": [
      { # L1
       "op": "const",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # l1-in2
       "op": "sub",
       "deg": 1,
       "values": [
        { # l1
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        },
        { # in2
         "op": "public",
         "deg": 0,
         "id": 1
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 6. 对应约束`LLAST * (l1 - :out) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # LLAST*(l2-out)
     "op": "mul",
     "deg": 2,
     "values": [
      { # LLAST
       "op": "const",
       "deg": 1,
       "id": 1,
       "next": false
      },
      { # l2-out
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        },
        { # out
         "op": "public",
         "deg": 0,
         "id": 2
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  }
 ],
 "polIdentities": [
  {
   "e": 1, # 对应”expressions“中的序号。即`(l2' - l1)*(1-LLAST) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 13 # 代码所在行号。即`(l2' - l1)*(1-LLAST) = 0;`
  },
  {
   "e": 3, # 对应”expressions“中的序号。即` (l1' - next)*(1-LLAST) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 17 # 代码所在行号。即` (l1' - next)*(1-LLAST) = 0;`
  },
  {
   "e": 4, # 对应”expressions“中的序号。即`L1 * (l2 - :in1) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 19 # 代码所在行号。即`L1 * (l2 - :in1) = 0;`
  },
  {
   "e": 5, # 对应”expressions“中的序号。即`L1 * (l1 - :in2) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 20 # 代码所在行号。即`L1 * (l1 - :in2) = 0;`
  },
  {
   "e": 6, # 对应”expressions“中的序号。即`LLAST * (l1 - :out) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 21 # 代码所在行号。即`LLAST * (l1 - :out) = 0;`
  }
 ],
 "plookupIdentities": [],
 "permutationIdentities": [],
 "connectionIdentities": []
}

    • 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
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375

    2.2 从编译结果中获取常量多项式

    const constPols = newConstantPolsArray(pil);

    • 1

    本质为从编译的json文件中，取“references”中标记为“constP”的多项式。

    2.3 对常量多项式赋值

    await smFibonacci.buildConstants(constPols.Fibonacci);

    • 1

    对各常量多项式赋值：

    module.exports.buildConstants = async function (pols) {

    const N = pols.L1.length;


    for ( let i=0; i<N; i++) {
        pols.L1[i] = (i == 0) ? 1n : 0n;
        pols.LLAST[i] = (i == N-1) ? 1n : 0n;
    }
}

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

    2.4 存储赋值后的常量多项式

    await constPols.saveToFile(outputFile);

    • 1

    3. 根据输入生成隐私多项式赋值

    debug运行fibonacci exec：运行main_exec_fibonacci.js，输入有fibonacci.input.json，输出为fibonacci.commit：【本质存储的就是execution trace。】

    /usr/local/bin/node --max-old-space-size=32000 test/sm_fibonacci/main_exec_fibonacci.js -i test/sm_fibonacci/fibonacci.input.json -o tmp/fibonacci.commit
Result: 74469561660084004
file Generated Correctly

    • 1
    • 2
    • 3

    首先仍然是编译pil文件：

    const pil = await compile(F, path.join(__dirname, "fibonacci_main.pil"));

    • 1

    然后读取输入值：

    const input = JSON.parse(await fs.promises.readFile(inputFile, "utf8"));

    • 1

    输入fibonacci.input.json内容为：

    [1, 2]

    • 1

    3.1 从编译结果中获取隐私（承诺）多项式

    const cmPols =  newCommitPolsArray(pil);

    • 1

    本质为从编译的json文件中，取“references”中标记为“cmP”的多项式。

    3.2 基于输入对隐私多项式赋实际运行值

    const result = await smFibonacci.execute(cmPols.Fibonacci, input);

    • 1

    基于输入获得实际运行结果pols.l1[N-1] 以及 对隐私多项式赋实际运行值pols.l2[i], pols.l1[i]：

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

    const N = pols.l1.length;

    const Fr = new F1Field("0xFFFFFFFF00000001");

    pols.l2[0] = BigInt(input[0]);
    pols.l1[0] = BigInt(input[1]);

    for (let i=1; i<N; i++) {
        pols.l2[i] =pols.l1[i-1];
        pols.l1[i] =Fr.add(Fr.square(pols.l2[i-1]), Fr.square(pols.l1[i-1]));
    }

    return pols.l1[N-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    3.3 存储赋值后的隐私多项式

    await cmPols.saveToFile(outputFile);

    • 1

    4. 验证常量多项式和隐私多项式的赋值是否正确

    验证常量多项式和隐私多项式的赋值是否正确，本质是验证基于输入的executiion trace是否正确。
    debug运行fibonacci PIL verify：运行node_modules/pilcom/src/main_pilverifier.js，输入有：

    • 4.1）fibonacci.commit【基于输入获得的隐私多项式的值】：为基于fibonacci.input.json运行状态机中main_exec_fibonacci.js获得的输出。
    • 4.2）fibonacci_main.pil程序。
    • 4.3）fibonacci.const【常量多项式的值】：为运行状态机中main_buildconst_fibonacci.js获得的输出。
    	/usr/local/bin/node --max-old-space-size=32000 node_modules/pilcom/src/main_pilverifier.js tmp/fibonacci.commit -p test/sm_fibonacci/fibonacci_main.pil -c tmp/fibonacci.const
	loading tmp/fibonacci.const.. 0 of 0.001953125
	loading tmp/fibonacci.commit.. 0 of 0.001953125
	Preparing public 1/3
	calculateExpression: 0
	Preparing public 2/3
	Preparing public 3/3
	Checking identities 1/5
	calculateExpression: 1
	Checking identities 2/5
	calculateExpression: 3
	calculateExpression: 2
	Checking identities 3/5
	calculateExpression: 4
	Checking identities 4/5
	calculateExpression: 5
	Checking identities 5/5
	calculateExpression: 6
	PIL OK!!

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    pilcom main_pilverifier.js的核心代码为：【核心思想为根据编译文件内的规则加载值，然后依次验证：

    • 1）连接约束（connectionIdentities）：又名copy-constraints，格式类似为[a, b, c] connect [Sa, Sb, Sc]
    • 2）plookup约束（plookupIdentities）：格式类似为a in b
    • 3）permutation约束（permutationIdentities）：格式类似为[a, b] is [c, d]
    • 4）多项式约束（polIdentities）：格式类似为a' = a + 5*b + c
    async function run() {

    const F = new F1Field("0xFFFFFFFF00000001");

    let commitFile; //必须且仅允许有一个已赋值隐私多项式文件，此处为tmp/fibonacci.commit
    if (argv._.length == 0) {
        console.log("You need to specify a commit file file file");
        process.exit(1);
    } else if (argv._.length == 1) {
        commitFile = argv._[0];
    } else  {
        console.log("Only one commit file at a time is permited");
        process.exit(1);
    }

    const pilFile = typeof(argv.pil) === "string" ?  argv.pil.trim() : "main.pil.json"; //pil代码文件，此处为test/sm_fibonacci/fibonacci_main.pil
    const constantFile = typeof(argv.constant) === "string" ?  argv.constant.trim() : "constant.bin"; //已赋值常量多项式文件，此处为tmp/fibonacci.const

    const config = typeof(argv.config) === "string" ? JSON.parse(fs.readFileSync(argv.config.trim())) : {};

    if (argv.verbose) {
        config.verbose = true;
        if (typeof config.color === 'undefined') {
            config.color = tty.isatty(process.stdout.fd);
        }
    }

    const pil = await compile(F, pilFile, null, config); //编译pil文件，获得相应的json结构

    const n = pil.references[Object.keys(pil.references)[0]].polDeg; //读取多项式的degree

    const constPols =  newConstantPolsArray(pil); //从编译文件中获取常量多项式结构
    const cmPols =  newCommitPolsArray(pil); //从编译文件中获取隐私多项式结构

    await constPols.loadFromFile(constantFile); //加载已赋值的常量多项式
    await cmPols.loadFromFile(commitFile); //加载已赋值的隐私多项式

    const res = await verifyPil(F, pil, cmPols, constPols);

    if (res.length != 0) {
        console.log("Pil does not pass");
        for (let i=0; i<res.length; i++) {
            console.log(res[i]);
        }
    } else {
        console.log("PIL OK!!")
    }
}

    • 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

    verifyPil的核心代码为：

    module.exports = async function verifyPil(F, pil, cmPols, constPols, config = {}) {

    const res = [];

    const refCm = {};
    const refConst = {};
    const refIm = {};
    for (let k of Object.keys(pil.references)) { //从pil代码编译的结果的“references”中，分类常量多项式、隐私多项式 和 中间多项式 的索引信息。
        const r  = pil.references[k];
        r.name = k;
        if (r.type == "cmP") {
            refCm[r.id] =r;
        } else if (r.type == "constP") {
            refConst[r.id] = r;
        } else if (r.type == "imP") {
            refIm[r.id] = r;
        } else {
            throw new Error("Reference type not handled: " + r.type);
        }
    }

    const pols = { //多项式集合
        cm: [],  //隐私多项式
        exps:[], //中间多项式
        const: [], //常量多项式
        publics: [] //公开输入
    };

    const N = cmPols.$$n;//隐私多项式数量
	//根据编译结果初始化各多项式数组大小
    for (let i=0; i<pil.nCommitments; i++) pols.cm[i] = {};
    for (let i=0; i<pil.expressions.length; i++) pols.exps[i] = {};
    for (let i=0; i<pil.nConstants; i++) pols.const[i] = {};

// 1.- Prepare commited polynomials.
    for (let i=0; i<cmPols.$$nPols; i++) { //将已赋值隐私多项式的值加载到相应的数组中
        pols.cm[i].v_n = cmPols.$$array[i];
    }

    for (let i=0; i<constPols.$$nPols; i++) { //将已赋值常量多项式的值加载到相应的数组中
        pols.const[i].v_n = constPols.$$array[i];
    }

    for (let i=0; i<pil.publics.length; i++) { //将编译结果的“publics”的各项与相应多项式的index值关联。
        console.log(`Preparing public ${i+1}/${pil.publics.length}`);

        if (pil.publics[i].polType == "cmP") {//如`public out = l1(%N-1);`，l1为隐私多项式
            pols.publics[i] = pols.cm[pil.publics[i].polId].v_n[pil.publics[i].idx];
        } else if (pil.publics[i].polType == "imP") { //如`public in1 = l2c(0);`，l2c为中间多项式
            await calculateExpression(pil.publics[i].polId); //为中间多项式赋值，找到中间多项式的赋值依赖，如`pol l2c = l2;`，相应的依赖关系见"expressions"中的index为`pil.publics[i].polId`的表达；并通过`eval`根据规则对中间多项式赋值。
            pols.publics[i] = pols.exps[pil.publics[i].polId].v_n[pil.publics[i].idx];
            delete pols.exps[pil.publics[i].polId].v_n; //中间多项式，用完即扔，节约资源。
        } else {
            throw new Error(`Invalid public type: ${polType.type}`);
        }
    }

    for (let i=0; i<pil.connectionIdentities.length; i++) { // 1）验证连接约束
        console.log(`Checking connectionIdentities ${i+1}/${pil.connectionIdentities.length}`);
        ci = pil.connectionIdentities[i];
        for (let j=0; j<ci.pols.length; j++) {
            await calculateExpression(ci.pols[j]);
        }
        for (let j=0; j<ci.connections.length; j++) {
            await calculateExpression(ci.connections[j]);
        }

        console.log("start generating cm");
        let cm = getConnectionMap(F, N, ci.pols.length);

        for (let j=0; j<ci.pols.length; j++) {
            for (let k=0; k<N; k++) {
                if (k%10000 == 0) console.log(`${k+1}/${N}`);
                const v1 = pols.exps[ci.pols[j]].v_n[k];

                const a = pols.exps[ci.connections[j]].v_n[k]
                const a1 = Number(a >> 48n);
                const a2 = Number((a >> 32n)&0xFFFFn );
                const a3 = Number(a&0xFFFFFFFFn );


                const [cp, cw] = cm[a1][a2][a3];
                if (typeof cp == "undefined") {
                    res.push(`${ci.fileName}:${pil.polIdentities[i].line}: invalid copy value w=${j},${k} val=${F.toString(v1)} `);
                    console.log(res[res.length-1]);
                }
                const v2 = pols.exps[ci.pols[cp]].v_n[cw];

                if (!F.eq(v1, v2)) {
                    res.push(`${ci.fileName}:${pil.polIdentities[i].line}: connection does not match p1=${j} w1=${k} p2=${cp}, w2=${cw} val= ${F.toString(v1)} != ${F.toString(v2)}`);
                    console.log(res[res.length-1]);
                    k=N;
                    j=ci.pols.length;
                }
            }
        }

        for (let j=0; j<ci.pols.length; j++) {
            delete pols.exps[ci.pols[j]].v_n;
        }
        for (let j=0; j<ci.connections.length; j++) {
            delete pols.exps[ci.connections[j]].v_n;
        }

    }

    for (let i=0; i<pil.plookupIdentities.length; i++) { //2）验证plookup约束
        console.log(`Checking plookupIdentities ${i+1}/${pil.plookupIdentities.length}`);
        const pi =pil.plookupIdentities[i];

        for (let j=0; j<pi.t.length; j++) {
            await calculateExpression(pi.t[j]);
        }
        if (pi.selT !== null) {
            await calculateExpression(pi.selT);
        }
        for (let j=0; j<pi.f.length; j++) {
            await calculateExpression(pi.f[j]);
        }
        if (pi.selF !== null) {
            await calculateExpression(pi.selF);
        }

        let t = {};
        for (let j=0; j<N; j++) {
            if ((pi.selT==null) || (!F.isZero(pols.exps[pi.selT].v_n[j]))) {
                const vals = []
                for (let k=0; k<pi.t.length; k++) {
                    vals.push(F.toString(pols.exps[pi.t[k]].v_n[j]));
                }
                t[vals.join(",")] = true;
            }
        }

        for (let j=0; j<N; j++) {
            if ((pi.selF==null) || (!F.isZero(pols.exps[pi.selF].v_n[j]))) {
                const vals = []
                for (let k=0; k<pi.f.length; k++) {
                    vals.push(F.toString(pols.exps[pi.f[k]].v_n[j]));
                }
                const v = vals.join(",");
                if (!t[v]) {
                    res.push(`${pil.plookupIdentities[i].fileName}:${pil.plookupIdentities[i].line}:  plookup not found w=${j} values: ${v}`);
                    console.log(res[res.length-1]);
                    if (!config.continueOnError) j=N;  // Do not continue checking
                }
            }
        }

        for (let j=0; j<pi.t.length; j++) {
            delete pols.exps[pi.t[j]].v_n;
        }
        if (pi.selT !== null) {
            delete pols.exps[pi.selT].v_n;
        }
        for (let j=0; j<pi.f.length; j++) {
            delete pols.exps[pi.f[j]].v_n;
        }
        if (pi.selF !== null) {
            delete pols.exps[pi.selF].v_n;
        }

    }


    for (let i=0; i<pil.permutationIdentities.length; i++) { // 3）验证permutation约束
        console.log(`Checking permutationIdentities ${i+1}/${pil.permutationIdentities.length}`);

        const pi =pil.permutationIdentities[i];

        for (let j=0; j<pi.t.length; j++) {
            await calculateExpression(pi.t[j]);
        }
        if (pi.selT !== null) {
            await calculateExpression(pi.selT);
        }
        for (let j=0; j<pi.f.length; j++) {
            await calculateExpression(pi.f[j]);
        }
        if (pi.selF !== null) {
            await calculateExpression(pi.selF);
        }

        let t = {};
        for (let j=0; j<N; j++) {
            if ((pi.selT==null) || (!F.isZero(pols.exps[pi.selT].v_n[j]))) {
                const vals = []
                for (let k=0; k<pi.t.length; k++) {
                    vals.push(F.toString(pols.exps[pi.t[k]].v_n[j]));
                }
                t[vals.join(",")] = true;
            }
        }

        for (let j=0; j<N; j++) {
            if ((pi.selF==null) || (!F.isZero(pols.exps[pi.selF].v_n[j]))) {
                const vals = []
                for (let k=0; k<pi.f.length; k++) {
                    vals.push(F.toString(pols.exps[pi.f[k]].v_n[j]));
                }
                const v = vals.join(",");
                if (!t[v]) {
                    res.push(`${pi.fileName}:${pi.line}:  permutation not found w=${j} values: ${v}`);
                    console.log(res[res.length-1]);
                    if (!config.continueOnError) j=N;  // Do not continue checking
                }
                delete t[v];
            }
        }

        if (Object.keys(t).length !=0) {
            res.push(`${pi.fileName}:${pi.line}:  permutation failed. values remaining: ${Object.keys(t).length}`);
            console.log(res[res.length-1]);
        }

        for (let j=0; j<pi.t.length; j++) {
            delete pols.exps[pi.t[j]].v_n;
        }
        if (pi.selT !== null) {
            delete pols.exps[pi.selT].v_n;
        }
        for (let j=0; j<pi.f.length; j++) {
            delete pols.exps[pi.f[j]].v_n;
        }
        if (pi.selF !== null) {
            delete pols.exps[pi.selF].v_n;
        }

    }

    for (let i=0; i<pil.polIdentities.length; i++) { // 4）验证多项式约束
        console.log(`Checking identities ${i+1}/${pil.polIdentities.length}`);
        await calculateExpression(pil.polIdentities[i].e);

        for (let j=0; j<N; j++) {
            const v = pols.exps[pil.polIdentities[i].e].v_n[j]
            if (!F.isZero(v)) {
                res.push(`${pil.polIdentities[i].fileName}:${pil.polIdentities[i].line}: identity does not match w=${j} val=${F.toString(v)} `);
                console.log(res[res.length-1]);
                if (!config.continueOnError) j=N;
            }
        }

        delete pols.exps[pil.polIdentities[i].e].v_n;
    }


    return res;

    • 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
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248

    5. 基于已赋值常量多项式进行Low Degree Extension evaluation并构建Merkletree

    【pil中的所有const多项式构建一个merkle tree。详细参看 STARKs and STARK VM: Proofs of Computational Integrity，本质为将const多项式在trace domain的evaluation值扩展到low degree extension domain的evaluation值，然后将所有const多项式的low degree extension domain的evaluation值构建一棵merkle tree。】
    STARK证明是基于Merkle树构造的，STARK的基本配置信息见fibonacci.starkstruct.json：

    {
            "nBits": 10, # trace domain为2^{10}
            "nBitsExt": 11, # Low Degree Extension evaluation domain为2^{11}
            "nQueries": 8, # STARK query次数
            "verificationHashType": "GL", # 使用的域，GL表示使用Goldilocks域。
            "steps": [
                {"nBits": 11}, # 必须与nBitsExt相等
                {"nBits": 7},
                {"nBits": 3}
            ]
}

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

    基于已赋值常量多项式构建Merkletree：
    debug运行fibonacci build constree：运行main_buildconsttree.js，输入有：

    • 5.i.1）fibonacci.const：为运行状态机中main_buildconst_fibonacci.js获得的输出。
    • 5.i.2）状态机中fibonacci_main.pil程序
    • 5.i.3）状态机中fibonacci.starkstruct.json

    输出为：

    • 5.o.1）fibonacci.consttree【为常量多项式在Low Degree Extension domain evaluation值的Merkle树】
    • 5.o.2）fibonacci.verkey.json 【为相应Merkle树的root】
    	/usr/local/bin/node --max-old-space-size=32000 src/main_buildconsttree.js -c /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.const -p /Users/lanyu/zyd/0xPolygonHermez/pil-stark/test/sm_fibonacci/fibonacci_main.pil -s /Users/lanyu/zyd/0xPolygonHermez/pil-stark/test/sm_fibonacci/fibonacci.starkstruct.json -t /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.consttree -v /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.verkey.json
	loading /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.const.. 0 of 0.001953125
	Interpolating reverse....
	Layer ifft0
	start block 10 0
	end block 10 0
	Interpolating prepare....
	linear interpolatePrepare start.... 0/0
	linear interpolatePrepare end.... 0/0
	Bit reverse....
	Layer fft 0
	start block 11 0
	end block 11 0
	interpolation terminated
	pool terminated
	Start merkelizing..
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/2048
	merkelizing hash start.... 0/1024
	merkelizing hash end.... 0/1024
	merkelizing hash start.... 0/512
	merkelizing hash end.... 0/512
	merkelizing hash start.... 0/256
	merkelizing hash end.... 0/256
	merkelizing hash start.... 0/128
	merkelizing hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	writting tree.. 0 / 4096
	writting tree.. 0 / 16380
	files Generated Correctly

    • 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

    main_buildconsttree.js的核心代码为：

    async function run() {
    const F = new F1Field();

    const pilFile = typeof(argv.pil) === "string" ?  argv.pil.trim() : "mycircuit.pil";
    const pilConfig = typeof(argv.pilconfig) === "string" ? JSON.parse(fs.readFileSync(argv.pilconfig.trim())) : {};
    const constFile = typeof(argv.const) === "string" ?  argv.const.trim() : "mycircuit.const";
    const starkStructFile = typeof(argv.starkstruct) === "string" ?  argv.starkstruct.trim() : "mycircuit.stark_struct.json";
    const constTreeFile = typeof(argv.consttree) === "string" ?  argv.consttree.trim() : "mycircuit.consttree";
    const verKeyFile = typeof(argv.verkey) === "string" ?  argv.verkey.trim() : "mycircuit.verkey.json";

    const starkStruct = JSON.parse(await fs.promises.readFile(starkStructFile, "utf8")); //读取STARK配置信息
    const pil = await compile(F, pilFile, null, pilConfig);

    const nBits = starkStruct.nBits;
    const nBitsExt = starkStruct.nBitsExt;
    const n = 1 << nBits; //trace domain
    const nExt = 1 << nBitsExt; //Low Degree Extension domain

    const constPols = newConstantPolsArray(pil);
    await constPols.loadFromFile(constFile); //加载已赋值常量多项式，即trace domain的evaluation值。

    const constBuff  = constPols.writeToBuff(); //将各常量多项式的trace domain的evaluation值写入buff

    const constPolsArrayE = new BigBuffer(nExt*pil.nConstants); //分配存储所有常量多项式Low Degree Extension domain的evaluation值所需空间。

    await interpolate(constBuff, pil.nConstants, nBits, constPolsArrayE, nBitsExt ); //计算各常量多项式Low Degree Extension domain的evaluation值

    let MH;
    if (starkStruct.verificationHashType == "GL") {
        MH = await buildMerkleHashGL(); //基于Goldilocks域的哈希函数
    } else if (starkStruct.verificationHashType == "BN128") {
        MH = await buildMerkleHashBN128(); //基于BN128域的哈希函数
    } else {
        throw new Error("Invalid Hash Type: "+ starkStruct.verificationHashType);
    }


    console.log("Start merkelizing..");
    const constTree = await MH.merkelize(constPolsArrayE, pil.nConstants, nExt);//基于所有常量多项式Low Degree Extension domain的evaluation值构建一棵Merkle树

    const constRoot = MH.root(constTree); //计算相应的Merkle root
	// 由于Goldilocks域的最大值为2**64-2**32+1-1，而poseidon哈希结果为256bit，因此，一个哈希结果需用4个Goldilocks域值来表示。最终的Merkle root也是由4个Goldilocks域值来表示。
    const verKey = {
        constRoot: constRoot
    };

    await fs.promises.writeFile(verKeyFile, JSONbig.stringify(verKey, null, 1), "utf8"); //存储Merkle root

    await MH.writeToFile(constTree, constTreeFile); //存储整个Merkle树

    console.log("files Generated Correctly");
}

    • 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

    6. 生成STARK证明

    debug运行fibonacci prove：运行main_prover.js，输入有：

    • 6.i.1）fibonacci.commit【已赋值隐私多项式（基于trace domain）】：为基于fibonacci.input.json运行状态机中main_exec_fibonacci.js获得的输出。
    • 6.i.2）fibonacci.const【已赋值常量多项式（基于trace domain）】：为运行状态机中main_buildconst_fibonacci.js获得的输出。
    • 6.i.3）fibonacci.consttree【常量多项式重新基于Low Degree Extension domain插值构建的Merkle树】：为运行main_buildconsttree.js获得的输出。
    • 6.i.4）fibonacci_main.pil：状态机程序
    • 6.i.5）fibonacci.starkstruct.json：状态机STARK结构配置文件

    输出有：

    • 6.o,1）fibonacci.proof.json：STARK证明
    • 6.o.2）fibonacci.proof.zkin.json：隐私输入
    • 6.o.3）fibonacci.public.json：公开输入
    	/usr/local/bin/node --max-old-space-size=32000 src/main_prover.js -m /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.commit -c /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.const -t /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.consttree -p /Users/lanyu/zyd/0xPolygonHermez/pil-stark/test/sm_fibonacci/fibonacci_main.pil -s /Users/lanyu/zyd/0xPolygonHermez/pil-stark/test/sm_fibonacci/fibonacci.starkstruct.json -o /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.proof.json -z /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.proof.zkin.json -b /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.public.json
	loading /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.const.. 0 of 0.001953125
	loading /Users/lanyu/zyd/0xPolygonHermez/pil-stark/tmp/fibonacci.commit.. 0 of 0.001953125
	Loading tree.. 0/4096
	Loading tree.. 0/16380
	Merkelizing 1....
	Interpolating reverse....
	Layer ifft0
	start block 10 0
	end block 10 0
	Interpolating prepare....
	linear interpolatePrepare start.... 0/0
	linear interpolatePrepare end.... 0/0
	Bit reverse....
	Layer fft 0
	start block 11 0
	end block 11 0
	interpolation terminated
	pool terminated
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/2048
	merkelizing hash start.... 0/1024
	merkelizing hash end.... 0/1024
	merkelizing hash start.... 0/512
	merkelizing hash end.... 0/512
	merkelizing hash start.... 0/256
	merkelizing hash end.... 0/256
	merkelizing hash start.... 0/128
	merkelizing hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	start exec step2prev... 0/1024
	end exec step2prev... 0/1024
	Merkelizing 2....
	Interpolating reverse....
	Layer ifft0
	start block 10 0
	end block 10 0
	Interpolating prepare....
	Bit reverse....
	Layer fft 0
	linear interpolatePrepare start.... 0/0
	linear interpolatePrepare end.... 0/0
	start block 11 0
	end block 11 0
	interpolation terminated
	pool terminated
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/2048
	merkelizing hash start.... 0/1024
	merkelizing hash end.... 0/1024
	merkelizing hash start.... 0/512
	merkelizing hash end.... 0/512
	merkelizing hash start.... 0/256
	merkelizing hash end.... 0/256
	merkelizing hash start.... 0/128
	merkelizing hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	start exec step3prev... 0/1024
	end exec step3prev... 0/1024
	Merkelizing 3....
	Interpolating reverse....
	Layer ifft0
	start block 10 0
	end block 10 0
	Interpolating prepare....
	Bit reverse....
	linear interpolatePrepare start.... 0/0
	linear interpolatePrepare end.... 0/0
	Layer fft 0
	start block 11 0
	end block 11 0
	interpolation terminated
	pool terminated
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/2048
	merkelizing hash start.... 0/1024
	merkelizing hash end.... 0/1024
	merkelizing hash start.... 0/512
	merkelizing hash end.... 0/512
	merkelizing hash start.... 0/256
	merkelizing hash end.... 0/256
	merkelizing hash start.... 0/128
	merkelizing hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	start exec step4... 0/1024
	end exec step4... 0/1024
	Interpolating reverse....
	Layer ifft0
	start block 10 0
	end block 10 0
	linear interpolatePrepare start.... 0/1
	linear interpolatePrepare end.... 0/1
	start block 11 0
	Interpolating prepare....
	Bit reverse....
	Layer fft 0
	end block 11 0
	interpolation terminated
	pool terminated
	start exec step42ns... 0/2048
	end exec step42ns... 0/2048
	Merkelizing 4....
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/2048
	merkelizing hash start.... 0/1024
	merkelizing hash end.... 0/1024
	merkelizing hash start.... 0/512
	merkelizing hash end.... 0/512
	merkelizing hash start.... 0/256
	merkelizing hash end.... 0/256
	merkelizing hash start.... 0/128
	merkelizing hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	start exec step52ns... 0/2048
	end exec step52ns... 0/2048
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/128
	linear hash end.... 0/128
	merkelizing hash start.... 0/64
	merkelizing hash end.... 0/64
	merkelizing hash start.... 0/32
	merkelizing hash end.... 0/32
	merkelizing hash start.... 0/16
	merkelizing hash end.... 0/16
	merkelizing hash start.... 0/8
	merkelizing hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	slicing buff 0
	creating thread 0
	waiting..
	linear hash start.... 0/8
	linear hash end.... 0/8
	merkelizing hash start.... 0/4
	merkelizing hash end.... 0/4
	merkelizing hash start.... 0/2
	merkelizing hash end.... 0/2
	merkelizing hash start.... 0/1
	merkelizing hash end.... 0/1
	files Generated Correctly

    • 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

    main_prover.js核心代码为：

    async function run() {
    const F = new GL3();

    const commitFile = typeof(argv.commit) === "string" ?  argv.commit.trim() : "mycircuit.commit";
    const constFile = typeof(argv.const) === "string" ?  argv.const.trim() : "mycircuit.const";
    const constTreeFile = typeof(argv.consttree) === "string" ?  argv.consttree.trim() : "mycircuit.consttree";
    const pilFile = typeof(argv.pil) === "string" ?  argv.pil.trim() : "mycircuit.pil";
    const pilConfig = typeof(argv.pilconfig) === "string" ? JSON.parse(fs.readFileSync(argv.pilconfig.trim())) : {};
    const starkStructFile = typeof(argv.starkstruct) === "string" ?  argv.starkstruct.trim() : "mycircuit.stark_struct.json";
    const proofFile = typeof(argv.proof) === "string" ?  argv.proof.trim() : "mycircuit.proof.json";
    const zkinFile = typeof(argv.zkin) === "string" ?  argv.zkin.trim() : "mycircuit.proof.zkin.json";
    const publicFile = typeof(argv.public) === "string" ?  argv.public.trim() : "mycircuit.public.json";

    const pil = await compile(F, pilFile, null, pilConfig); //编译pil程序
    const starkStruct = JSON.parse(await fs.promises.readFile(starkStructFile, "utf8")); //读取STARK配置文件

    const nBits = starkStruct.nBits;
    const n = 1 << nBits; // trace domain

    const constPols =  newConstantPolsArray(pil); 
    await constPols.loadFromFile(constFile); //加载常量多项式trace domain的evaluation值。

    const cmPols =  newCommitPolsArray(pil);
    await cmPols.loadFromFile(commitFile); //加载隐私多项式trace domain的evaluation值。

    let MH;
    if (starkStruct.verificationHashType == "GL") {
        MH = await buildMerklehashGL(); //基于Goldilocks域的哈希函数
    } else if (starkStruct.verificationHashType == "BN128") {
        MH = await buildMerklehashBN128(); //基于BN128域的哈希函数
    } else {
        throw new Error("Invalid Hash Type: "+ starkStruct.verificationHashType);
    }

    const constTree = await MH.readFromFile(constTreeFile); //加载常量多项式Low Degree Extension domain的evaluation值所构建的Merkle树。

    const starkInfo = starkInfoGen(pil, starkStruct); //基于pil编译文件和STARK配置文件，生成STARK约束表达。

    const resP = await starkGen(cmPols, constPols, constTree, starkInfo); //基于 隐私多项式trace domain evaluation值、常量多项式trace domain evaluation值 以及 常量多项式Low Degree Extension domain evaluation值的Merkle树，生成STARK证明。

    await fs.promises.writeFile(proofFile, JSONbig.stringify(resP.proof, null, 1), "utf8"); //存储STARK证明


    const zkIn = proof2zkin(resP.proof);
    zkIn.publics = resP.publics;

    await fs.promises.writeFile(publicFile, JSONbig.stringify(resP.publics, null, 1), "utf8"); //存储STARK的公开信息
    if (starkStruct.verificationHashType == "BN128") { //为何对于BN128需单独指定proverAddr？

        if (!argv.proverAddr) throw new Error("Prover Address not specified");
        zkIn.proverAddr = BigInt(argv.proverAddr);


        let b= zkIn.proverAddr.toString(16);
        while (b.length < 40) b = "0" + b;

        for (let i=0; i<resP.publics.length; i++) {
            let b2 = resP.publics[i].toString(16);
            while (b2.length<16) b2 = "0" + b2;
            b = b + b2;
        }

        const publicsHash = BigInt("0x" + createHash('sha256').update(b, 'hex').digest("hex")) % 21888242871839275222246405745257275088548364400416034343698204186575808495617n;

        console.log(`Publics Hash: 0x${publicsHash.toString()}`);
    }


    await fs.promises.writeFile(zkinFile, JSONbig.stringify(zkIn, (k, v) => { //存储STARK的隐私输入
        if (typeof(v) === "bigint") {
            return v.toString();
        } else {
            return v;
        }
    }, 1), "utf8");

    console.log("files Generated Correctly");
}

    • 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

    6.1 基于PIL编译文件和STARK配置信息生成Prover和Verifier的约束表达

    基于PIL编译文件和STARK配置信息生成约束表达：

    const starkInfo = starkInfoGen(pil, starkStruct); //基于pil编译文件和STARK配置文件，生成STARK约束表达。
await fs.promises.writeFile("zydSTARKInfo.json", JSONbig.stringify(starkInfo, null, 1), "utf8"); //存储，便于分析。

    • 1
    • 2

    starkInfoGen核心代码为：

    module.exports = function starkInfoGen(_pil, starkStruct) {
    const pil = JSON.parse(JSON.stringify(_pil));    // Make a copy as we are going to destroy pil
    const F = new F1Field();
    const pilDeg = Object.values(pil.references)[0].polDeg; //获取pil编译文件中的多项式degree。
    const starkDeg = 2 ** starkStruct.nBits; //获取STARK配置文件中的多项式degree。

    if ( starkDeg != pilDeg) { //要求 pil编译文件中的多项式degree 与 STARK配置文件中的多项式degree，二者相等。
        throw new Error(`Starkpil and pil have degree mismatch (starkpil:${starkDeg} pil:${pilDeg})`);
    }

    if ( starkStruct.nBitsExt != starkStruct.steps[0].nBits) { //要求STARK配置文件中的nBitsExt与steps中的nBits相等。
        throw new Error(`Starkpil.nBitsExt and first step of Starkpil have a mismatch (nBitsExt:${starkStruct.nBitsExt} pil:${starkStruct.steps[0].nBits})`);
    }

    const res = { //所生成的STARK基本信息的结构
        varPolMap: [], //多项式约束
        puCtx: [], //plookup约束
        peCtx: [], //permutation约束
        ciCtx: [] //connection约束
    };

    res.starkStruct = starkStruct; //记录STARK配置信息
    res.nConstants = pil.nConstants; //记录常量多项式数量
    res.nPublics = pil.publics.length; //记录publics数量

    generatePublicCalculators(res, pil); //针对中间多项式的"publics"项进行处理。
    res.nCm1 = pil.nCommitments; //记录隐私多项式数量

    const ctx = { //Ctx结构
        pil: pil, //pil编译文件
        calculated: {
            exps: {},
            expsPrime: {}
        },
        tmpUsed: 0,
        code: []
    };

    const ctx2ns = { //Ctx结构
        pil: pil, //pil编译文件
        calculated: {
            exps: {},
            expsPrime: {}
        },
        tmpUsed: 0,
        code: []
    };


    generateStep2(res, pil, ctx);                        // H1, H2。主要处理plookup约束。
    res.nCm2 = pil.nCommitments - res.nCm1; 
	//主要处理permutataion约束多项式LC，和plookup、permutation以及connection约束多项式Z。
    generateStep3(res, pil, ctx);                        // Z Polynomials and LC of permutation chcks.
    res.nCm3 = pil.nCommitments - res.nCm1 - res.nCm2; 
	//主要处理polIdentities多项式约束
    generateConstraintPolynomial(res, pil, ctx, ctx2ns);            // Step4. 主要为约束多项式表达。
    res.nCm4 = pil.nCommitments - res.nCm3 -res.nCm2-res.nCm1; //step4中处理的隐私多项式数量。即此时已处理完所有的约束。
    res.nQ = pil.nQ; //记录pil编译文件中的nQ。

    generateConstraintPolynomialVerifier(res, pil); //主要为对polIdentities约束的Linear Combination组合合并后的约束cExp进行处理。

    generateFRIPolynomial(res, pil, ctx2ns); //构建FRI多项式。

    generateVerifierQuery(res, pil); //Verifier query值的计算规则，与上面构建的FRI多项式呼应。

    map(res, pil); //map，建立tree和约束之间的映射关系。

//    cPolBuilder(pil, res.cExp);

    res.publics = pil.publics;

    return res;

}

    • 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

    当前支持的challenge类型有：

    const challengeMap = {
    "u": 0,
    "defVal": 1,
    "gamma": 2,
    "beta": 3,
    "vc": 4,
    "vf1": 5,
    "vf2": 6,
    "xi": 7
};

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

    map函数中，建立tree和约束之间的映射关系为：

    • 1）polyIdentities -> cm1_2ns -> tree1
    • 2）plookupIdentities -> cm2_2ns -> tree2
    • 3）permutationLC&plookupZ&permutationZ&connectionZ -> cm3_2ns -> tree3
    • 4）q（中间多项式）-> tree4
    • 5）constantPoly（常量多项式）-> constTree

    6.2 生成STARK证明

    输入有：

    • 1）隐私多项式trace domain evaluation值：comPols
    • 2）常量多项式trace domain evaluation值：constPols
    • 3）常量多项式Low Degree Extension domain evaluation值的Merkle树：constTree
    • 4）Prover生成证明以及Verifier验证证明所需的逻辑表达：starkInfo

    各变量基本含义为：

    • cm1_n：为commit多项式trace domain的evaluation值。
    • cm1_2ns：为commit多项式low degree extension domain的evaluation值。
    • tree1：为commit多项式扩域上evaluation值构建的Merkle树。
    • cm2_n/cm2_2ns/tree2：为plookup约束相关evaluation值及Merkle树。
    • cm3_n/cm3_2ns/tree3：为plookup/permutation/connection约束Z多项式* evaluation值及Merkle树。
    • exps_withq_n/exps_withq_2ns/q_2ns/tree4：为polIdentities约束相关evaluation值及Merkle树。
    const resP = await starkGen(cmPols, constPols, constTree, starkInfo);

    • 1

    starkGen的核心代码为：

    module.exports = async function starkGen(cmPols, constPols, constTree, starkInfo) {
    const starkStruct = starkInfo.starkStruct;
    const N = 1 << starkStruct.nBits;
    const extendBits = starkStruct.nBitsExt - starkStruct.nBits;
    const nBitsExt = starkStruct.nBitsExt;
    const nBits = starkStruct.nBits;
    assert(1 << nBits == N, "N must be a power of 2");

    const F = new GL3();

    let MH;
    let MHS;
    let transcript;
    if (starkStruct.verificationHashType == "GL") { // 选择相应域对应的哈希函数、Merkle哈希函数、非交互随机challenge生成器transcript函数。
        const poseidon = await buildPoseidonGL();
        MH = await buildMerklehashGL();
        transcript = new Transcript(poseidon);
    } else if (starkStruct.verificationHashType == "BN128") {
        const poseidonBN128 = await buildPoseidonBN128();
        MH = await buildMerklehashBN128();
        transcript = new TranscriptBN128(poseidonBN128);
    } else {
        throw new Error("Invalid Hash Type: "+ starkStruct.verificationHashType);
    }

    const fri = new FRI( starkStruct, MH ); // 初始化FRI协议信息：域、inNbits、maxDegNBits、nQueries、MH、steps。

    if (cmPols.$$nPols != starkInfo.nCm1) { // 约束隐私多项式的数量相等。
        throw new Error(`Number of Commited Polynomials: ${cmPols.length} do not match with the starkInfo definition: ${starkInfo.nCm1} `)
    };

    const ctx = {}
    ctx.F = F;

    const pool = workerpool.pool(__dirname + '/starkgen_worker.js');

    ctx.nBits = starkInfo.starkStruct.nBits; //10
    ctx.nBitsExt = starkInfo.starkStruct.nBitsExt; //11
    ctx.N = 1 << starkInfo.starkStruct.nBits; //1024
    ctx.Next = 1 << starkInfo.starkStruct.nBitsExt; //2048
    ctx.starkInfo = starkInfo;
    ctx.tmp = [];
    ctx.challenges = [];
    let nCm = starkInfo.nCm1; //2

    ctx.cm1_n = new BigBuffer(starkInfo.mapSectionsN.cm1_n*ctx.N); //polyIdentities约束，为2*1024
    cmPols.writeToBigBuffer(ctx.cm1_n, 0);
    ctx.cm2_n = new BigBuffer(starkInfo.mapSectionsN.cm2_n*ctx.N); //plookupIdentities约束。
    ctx.cm3_n = new BigBuffer(starkInfo.mapSectionsN.cm3_n*ctx.N); //permutationLC、plookupZ、permutationZ、connectionZ约束
    ctx.exps_withq_n = new BigBuffer(starkInfo.mapSectionsN.exps_withq_n*ctx.N); //表达式中带idQ的序号
    ctx.exps_withoutq_n = new BigBuffer(starkInfo.mapSectionsN.exps_withoutq_n*ctx.N); //表达式中keep为1的序号
    ctx.cm1_2ns = new BigBuffer(starkInfo.mapSectionsN.cm1_n*ctx.Next);//polyIdentities约束，为2*1024
    ctx.cm2_2ns = new BigBuffer(starkInfo.mapSectionsN.cm2_n*ctx.Next);//plookupIdentities约束。
    ctx.cm3_2ns = new BigBuffer(starkInfo.mapSectionsN.cm3_n*ctx.Next);//permutationLC、plookupZ、permutationZ、connectionZ约束
    ctx.q_2ns = new BigBuffer(starkInfo.mapSectionsN.q_2ns*ctx.Next);//中间多项式
    ctx.exps_withq_2ns = new BigBuffer(starkInfo.mapSectionsN.exps_withq_2ns*ctx.Next);
    ctx.exps_withoutq_2ns = new BigBuffer(starkInfo.mapSectionsN.exps_withoutq_2ns*ctx.Next); //keep2ns为1

    ctx.x_n = new BigBuffer(N);
    let xx = F.one;
    for (let i=0; i<N; i++) { //为trace domain {1,w,w^2,...,w^{N-1}}，其中w为N-th generator。
    // N为2^{nBits}
        ctx.x_n.setElement(i, xx);
        xx = F.mul(xx, F.w[nBits])
    }

    ctx.x_2ns = new BigBuffer(N << extendBits);
    xx = F.shift; // g
    // 为low-degree extension domain {g,gW,gW^2,...,gW^{M-1}}
    // 其中W为M-th generator，M为扩展域size。
    // M为2^{nBits + extendBits}
    for (let i=0; i<(N << extendBits); i++) {
        ctx.x_2ns.setElement(i, xx);
        xx = F.mul(xx, F.w[nBits + extendBits]);
    }


    // Build ZHInv
    const zhInv = buildZhInv(F, nBits, extendBits);
    // zhInv为函数，offset为0：
    // function (i) {
    //    return ZHInv[(i + offset) % ZHInv.length];
    // }
    ctx.Zi = zhInv;


    ctx.const_n = new BigBuffer(starkInfo.nConstants*ctx.N); //常量多项式，2*1024
    constPols.writeToBigBuffer(ctx.const_n, 0);

    ctx.const_2ns = constTree.elements; //常量多项式在Low Degree Extension domain的evaluation

// This will calculate all the Q polynomials and extend commits

//    calculateExps(F, pols, starkInfo.step1prev);

    ctx.publics = [];//获取公开变量值
    for (let i=0; i<starkInfo.publics.length; i++) {
        if (starkInfo.publics[i].polType == "cmP") {
        	// 公开变量若源自commit多项式，则直接从cm1_n中获取。
            ctx.publics[i] = ctx.cm1_n.getElement( starkInfo.publics[i].idx * starkInfo.mapSectionsN.cm1_n + starkInfo.publics[i].polId   );
        } else if (starkInfo.publics[i].polType == "imP") {
            // EDU: Do not implement this in the firs version.
            //      we will not use it.
            // 公开变量若源自中间多项式，则调用calculateExpAtPoint计算。
            ctx.publics[i] = calculateExpAtPoint(ctx, starkInfo.publicsCode[i], starkInfo.publics[i].idx);
//            ctx.publics[i] = ctx.exps[starkInfo.publics[i].polId][starkInfo.publics[i].idx];
        } else {
            throw new Error(`Invalid public type: ${polType.type}`);
        }
    }

    console.log("Merkelizing 1....");
    const tree1 = await extendAndMerkelize(MH, ctx.cm1_n, ctx.cm1_2ns, starkInfo.mapSectionsN.cm1_n, ctx.nBits, ctx.nBitsExt );
    transcript.put(MH.root(tree1));

///
// 2.- Caluculate plookups h1 and h2
///
    ctx.challenges[0] = transcript.getField(); // u
    ctx.challenges[1] = transcript.getField(); // defVal


    if (parallelExec) {
        await calculateExpsParallel(pool, ctx, "step2prev", starkInfo);
    } else {
        calculateExps(ctx, starkInfo.step2prev, "n");
    }


    for (let i=0; i<starkInfo.puCtx.length; i++) {
        const puCtx = starkInfo.puCtx[i];
        const fPol = getPol(ctx, starkInfo, starkInfo.exps_n[puCtx.fExpId]);
        const tPol = getPol(ctx, starkInfo, starkInfo.exps_n[puCtx.tExpId]);
        const [h1, h2] = calculateH1H2(F, fPol, tPol);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], h1);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], h2);
    }

    console.log("Merkelizing 2....");
    const tree2 = await extendAndMerkelize(MH, ctx.cm2_n, ctx.cm2_2ns, starkInfo.mapSectionsN.cm2_n, ctx.nBits, ctx.nBitsExt );
    transcript.put(MH.root(tree2));

///
// 3.- Compute Z polynomials
///
    ctx.challenges[2] = transcript.getField(); // gamma
    ctx.challenges[3] = transcript.getField(); // betta


    if (parallelExec) {
        await calculateExpsParallel(pool, ctx, "step3prev", starkInfo);
    } else {
        calculateExps(ctx, starkInfo.step3prev, "n");
    }

    for (let i=0; i<starkInfo.puCtx.length; i++) {
        console.log(`Calculating z for plookup ${i}`);
        const pu = starkInfo.puCtx[i];
        const pNum = getPol(ctx, starkInfo, starkInfo.exps_n[pu.numId]);
        const pDen = getPol(ctx, starkInfo, starkInfo.exps_n[pu.denId]);
        const z = calculateZ(F,pNum, pDen);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], z);
    }
    for (let i=0; i<starkInfo.peCtx.length; i++) {
        console.log(`Calculating z for permutation check ${i}`);
        const pe = starkInfo.peCtx[i];
        const pNum = getPol(ctx, starkInfo, starkInfo.exps_n[pe.numId]);
        const pDen = getPol(ctx, starkInfo, starkInfo.exps_n[pe.denId]);
        const z = calculateZ(F,pNum, pDen);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], z);
    }
    for (let i=0; i<starkInfo.ciCtx.length; i++) {
        console.log(`Calculating z for connection ${i}`);
        const ci = starkInfo.ciCtx[i];
        const pNum = getPol(ctx, starkInfo, starkInfo.exps_n[ci.numId]);
        const pDen = getPol(ctx, starkInfo, starkInfo.exps_n[ci.denId]);
        const z = calculateZ(F,pNum, pDen);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], z);
    }

    console.log("Merkelizing 3....");
    const tree3 = await extendAndMerkelize(MH, ctx.cm3_n, ctx.cm3_2ns, starkInfo.mapSectionsN.cm3_n, ctx.nBits, ctx.nBitsExt );
    transcript.put(MH.root(tree3));

///
// 4. Compute C Polynomial
///
    ctx.challenges[4] = transcript.getField(); // vc
	// 计算ctx.exps_withq_n数组，长度为starkInfo.mapSectionsN.exps_withq_n*ctx.N。
    if (parallelExec) {
        await calculateExpsParallel(pool, ctx, "step4", starkInfo);
    } else {
        calculateExps(ctx, starkInfo.step4, "n");
    }

    await extend(ctx.exps_withq_n, ctx.exps_withq_2ns, starkInfo.mapSectionsN.exps_withq_n, ctx.nBits, ctx.nBitsExt);
    if (parallelExec) {
        await calculateExpsParallel(pool, ctx, "step42ns", starkInfo);
    } else {
        calculateExps(ctx, starkInfo.step42ns, "2ns");
    }

    console.log("Merkelizing 4....");
    tree4 = await merkelize(MH, ctx.q_2ns , starkInfo.mapSectionsN.q_2ns, ctx.nBitsExt);
    transcript.put(MH.root(tree4));


///
// 5. Compute FRI Polynomial
///
    ctx.challenges[5] = transcript.getField(); // v1
    ctx.challenges[6] = transcript.getField(); // v2
    ctx.challenges[7] = transcript.getField(); // xi

// Calculate Evals

    let LEv = new Array(N);
    let LpEv = new Array(N);
    LEv[0] = 1n;
    LpEv[0] = 1n;
    const xis = F.div(ctx.challenges[7], F.shift);
    const wxis = F.div(F.mul(ctx.challenges[7], F.w[nBits]), F.shift);
    for (let k=1; k<N; k++) {
        LEv[k] = F.mul(LEv[k-1], xis);
        LpEv[k] = F.mul(LpEv[k-1], wxis);
    }
    LEv = F.ifft(LEv);
    LpEv = F.ifft(LpEv);

    ctx.evals = [];
    for (let i=0; i<starkInfo.evMap.length; i++) {
        const ev = starkInfo.evMap[i];
        let p;
        if (ev.type == "const") {
            p = {
                buffer: ctx.const_2ns,
                deg: 1<<nBitsExt,
                offset: ev.id,
                size: starkInfo.nConstants,
                dim: 1
            };
        } else if (ev.type == "cm") {
            p = getPolRef(ctx, starkInfo, starkInfo.cm_2ns[ev.id]);
        } else if (ev.type == "q") {
            p = getPolRef(ctx, starkInfo, starkInfo.qs[ev.id]);
        } else {
            throw new Error("Invalid ev type: "+ ev.type);
        }
        l = ev.prime ? LpEv : LEv;
        let acc = 0n;
        for (let k=0; k<N; k++) {
            let v;
            if (p.dim==1) {
                v = p.buffer.getElement((k<<extendBits)*p.size + p.offset);
            } else {
                v = [
                    p.buffer.getElement((k<<extendBits)*p.size + p.offset),
                    p.buffer.getElement((k<<extendBits)*p.size + p.offset+1),
                    p.buffer.getElement((k<<extendBits)*p.size + p.offset+2)
                ];
            }
            acc = F.add(acc, F.mul(v, l[k]));
        }
        ctx.evals[i] = acc;
    }

// Calculate xDivXSubXi, xDivX4SubWXi

    const xi = ctx.challenges[7];
    const wxi = F.mul(ctx.challenges[7], F.w[nBits]);

    ctx.xDivXSubXi = new BigBuffer((N << extendBits)*3);
    ctx.xDivXSubWXi = new BigBuffer((N << extendBits)*3);
    let tmp_den = new Array(N << extendBits);
    let tmp_denw = new Array(N << extendBits);
    let x = F.shift;
    for (let k=0; k< N<<extendBits; k++) {
        tmp_den[k] = F.sub(x, xi);
        tmp_denw[k] = F.sub(x, wxi);
        x = F.mul(x, F.w[nBits + extendBits])
    }
    tmp_den = F.batchInverse(tmp_den);
    tmp_denw = F.batchInverse(tmp_denw);
    x = F.shift;
    for (let k=0; k< N<<extendBits; k++) {
        const v = F.mul(tmp_den[k], x);
        ctx.xDivXSubXi.setElement(3*k , v[0]);
        ctx.xDivXSubXi.setElement(3*k +1 , v[1]);
        ctx.xDivXSubXi.setElement(3*k +2, v[2]);

        const vw = F.mul(tmp_denw[k], x);
        ctx.xDivXSubWXi.setElement(3*k , vw[0]);
        ctx.xDivXSubWXi.setElement(3*k +1, vw[1]);
        ctx.xDivXSubWXi.setElement(3*k +2, vw[2]);

        x = F.mul(x, F.w[nBits + extendBits])
    }


    if (parallelExec) {
        await calculateExpsParallel(pool, ctx, "step52ns", starkInfo);
    } else {
        calculateExps(ctx, starkInfo.step52ns, "2ns");
    }

    const friPol = getPol(ctx, starkInfo, starkInfo.exps_2ns[starkInfo.friExpId]);

    const queryPol = (idx) => {
        return [
            MH.getGroupProof(tree1, idx),
            MH.getGroupProof(tree2, idx),
            MH.getGroupProof(tree3, idx),
            MH.getGroupProof(tree4, idx),
            MH.getGroupProof(constTree, idx),
        ];
    }

    const friProof = await fri.prove(transcript, friPol, queryPol);

    await pool.terminate();

    return {
        proof: {
            root1: MH.root(tree1),
            root2: MH.root(tree2),
            root3: MH.root(tree3),
            root4: MH.root(tree4),
            evals: ctx.evals,
            fri: friProof
        },
        publics: ctx.publics
    }

}

    • 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
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334

    7. 验证STARK证明

    const resV = await starkVerify(proof, public, constRoot, starkInfo);

    • 1

    此处的constRoot为常量多项式在Low Degree Extension domain evaluation值构建的Merkle树的root。
    pubic为公开输入和输出：

    [
 1,
 2,
 74469561660084004
]

    • 1
    • 2
    • 3
    • 4
    • 5

    附录：Polygon Hermez 2.0 zkEVM系列博客

  • 相关阅读:
    MySQL运维11-Mycat分库分表之应用指定分片
    【计算机基础】优雅的PPT就应该这样设计
    linux下对sh文件的基本操作总结
    2023-10-20 LeetCode每日一题（根据规则将箱子分类）
    【工作中问题解决实践 一】最小单元染色法的应用
    Hello World分析
    camtasia 2023怎么导出mp4
    计算机网络---第四章网络层---ipv4---选择题
    从零开始，开发一个 Web Office 套件（9）：拖动鼠标选中文字 Edge Case
    基于信息增强传输的时空图神经网络交通流预测
  • 原文地址：https://blog.csdn.net/mutourend/article/details/126488740