1. 引言

前序博客有：

• STARK入门知识
• STARKs and STARK VM: Proofs of Computational Integrity
• Fast Reed-Solomon Interactive Oracle Proofs of Proximity学习笔记

相关代码见：

• https://github.com/aszepieniec/stark-anatomy/blob/master/code（Python）

测试用例有：

$ pytest
=================================================================== test session starts ====================================================================
platform darwin -- Python 3.9.12, pytest-6.2.5, py-1.11.0, pluggy-1.0.0
rootdir: /Users/lanyu/zyd/stark-anatomy/code
collected 21 items                                                                                                                                         

test_fast_stark.py F                                                                                                                                 [  4%]
test_fri.py .                                                                                                                                        [  9%]
test_ip.py F                                                                                                                                         [ 14%]
test_merkle.py .                                                                                                                                     [ 19%]
test_multivariate.py ..                                                                                                                              [ 28%]
test_ntt.py ......                                                                                                                                   [ 57%]
test_rescue_prime.py ..                                                                                                                              [ 66%]
test_rpsss.py ..                                                                                                                                     [ 76%]
test_stark.py F                                                                                                                                      [ 80%]
test_univariate.py ....                                                                                                                              [100%]

========================================================================= FAILURES =========================================================================
_____________________________________________________________________ test_fast_stark ______________________________________________________________________

    def test_fast_stark( ):
        field = Field.main()
        expansion_factor = 4
        num_colinearity_checks = 2
        security_level = 2
    
        rp = RescuePrime()
        output_element = field.sample(bytes(b'0xdeadbeef'))
    
        for trial in range(0, 20):
            input_element = output_element
            print("running trial with input:", input_element.value)
            output_element = rp.hash(input_element)
            num_cycles = rp.N+1
            state_width = rp.m
    
            stark = FastStark(field, expansion_factor, num_colinearity_checks, security_level, state_width, num_cycles)
            transition_zerofier, transition_zerofier_codeword, transition_zerofier_root = stark.preprocess()
    
            # prove honestly
            print("honest proof generation ...")
    
            # prove
            trace = rp.trace(input_element)
            air = rp.transition_constraints(stark.omicron)
            boundary = rp.boundary_constraints(output_element)
            proof = stark.prove(trace, air, boundary, transition_zerofier, transition_zerofier_codeword)
    
            # verify
            verdict = stark.verify(proof, air, boundary, transition_zerofier_root)
    
            assert(verdict == True), "valid stark proof fails to verify"
            print("success \\o/")
    
            print("verifying false claim ...")
            # verify false claim
            output_element_ = output_element + field.one()
            boundary_ = rp.boundary_constraints(output_element_)
            verdict = stark.verify(proof, air, boundary_, transition_zerofier_root)
    
            assert(verdict == False), "invalid stark proof verifies"
            print("proof rejected! \\o/")
    
            # prove with false witness
            print("attempting to prove with witness violating transition constraints (should not fail because using fast division) ...")
            cycle = 1 + (int(os.urandom(1)[0]) % len(trace)-1)
            register = int(os.urandom(1)[0]) % state_width
            error = field.sample(os.urandom(17))
    
            trace[cycle][register] = trace[cycle][register] + error
    
>           proof = stark.prove(trace, air, boundary, transition_zerofier, transition_zerofier_codeword)

test_fast_stark.py:60: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
fast_stark.py:97: in prove
    quotient = (trace_polynomials[s] - interpolant) / zerofier
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <univariate.Polynomial object at 0x10401b400>, other = <univariate.Polynomial object at 0x10401bc10>

    def __truediv__( self, other ):
        quo, rem = Polynomial.divide(self, other)
>       assert(rem.is_zero()), "cannot perform polynomial division because remainder is not zero"
E       AssertionError: cannot perform polynomial division because remainder is not zero

univariate.py:52: AssertionError
------------------------------------------------------------------- Captured stdout call -------------------------------------------------------------------
running trial with input: 228894434762048332457318
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 58193264164488245767062567324329845625
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 240442014346771117356623971907334212202
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 95249760241169493715201876097323148293
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 45460984185732302940594266735879849714
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 165587666758636920344584355360822203181
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 4978416156855947152397342202659038273
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 31067639684737653452690049877783213369
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 53584232234693103790669953564737900223
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 135431606538579019225905956689564915329
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 112559249994899591330577919758944336055
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 150140559072116678002193196297066253509
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 17074186389844667756333966236643273102
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 82836370955455571146008478781338270694
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 16254124710661698025820423055202445077
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 43769528645735998152380658131815329300
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 211513813789453019359177662714979719288
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 149981298211404449757454909679214149901
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
 ... but verification should fail :D
proof rejected! \o/
running trial with input: 196164108357361058832227489249577920500
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with witness violating transition constraints (should not fail because using fast division) ...
______________________________________________________________________ test_serialize ______________________________________________________________________

    def test_serialize( ):
        proof1 = ProofStream()
        proof1.push(1)
        proof1.push({1: '1'})
        proof1.push([1])
        proof1.push(2)
    
        serialized = proof1.serialize()
>       proof2 = ProofStream.deserialize(serialized)
E       TypeError: deserialize() missing 1 required positional argument: 'bb'

test_ip.py:11: TypeError
________________________________________________________________________ test_stark ________________________________________________________________________

    def test_stark( ):
        field = Field.main()
        expansion_factor = 4
        num_colinearity_checks = 2
        security_level = 2
    
        rp = RescuePrime()
        output_element = field.sample(bytes(b'0xdeadbeef'))
    
        for trial in range(0, 20):
            input_element = output_element
            print("running trial with input:", input_element.value)
            output_element = rp.hash(input_element)
            num_cycles = rp.N+1
            state_width = rp.m
    
            stark = Stark(field, expansion_factor, num_colinearity_checks, security_level, state_width, num_cycles)
    
            # prove honestly
            print("honest proof generation ...")
    
            # prove
            trace = rp.trace(input_element)
            air = rp.transition_constraints(stark.omicron)
            boundary = rp.boundary_constraints(output_element)
            proof = stark.prove(trace, air, boundary)
    
            # verify
            verdict = stark.verify(proof, air, boundary)
    
            assert(verdict == True), "valid stark proof fails to verify"
            print("success \\o/")
    
            print("verifying false claim ...")
            # verify false claim
            output_element_ = output_element + field.one()
            boundary_ = rp.boundary_constraints(output_element_)
            verdict = stark.verify(proof, air, boundary_)
    
            assert(verdict == False), "invalid stark proof verifies"
            print("proof rejected! \\o/")
    
        # verify with false witness
        print("attempting to prove with false witness (should fail) ...")
        cycle = int(os.urandom(1)[0]) % len(trace)
        register = int(os.urandom(1)[0]) % state_width
        error = field.sample(os.urandom(17))
    
        trace[cycle][register] = trace[cycle][register] + error
    
>       proof = stark.prove(trace, air, boundary) # should fail

test_stark.py:59: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
stark.py:111: in prove
    transition_quotients = [tp / self.transition_zerofier() for tp in transition_polynomials]
stark.py:111: in <listcomp>
    transition_quotients = [tp / self.transition_zerofier() for tp in transition_polynomials]
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <univariate.Polynomial object at 0x104086130>, other = <univariate.Polynomial object at 0x10407d1c0>

    def __truediv__( self, other ):
        quo, rem = Polynomial.divide(self, other)
>       assert(rem.is_zero()), "cannot perform polynomial division because remainder is not zero"
E       AssertionError: cannot perform polynomial division because remainder is not zero

univariate.py:52: AssertionError
------------------------------------------------------------------- Captured stdout call -------------------------------------------------------------------
running trial with input: 228894434762048332457318
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 58193264164488245767062567324329845625
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 240442014346771117356623971907334212202
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 95249760241169493715201876097323148293
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 45460984185732302940594266735879849714
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 165587666758636920344584355360822203181
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 4978416156855947152397342202659038273
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 31067639684737653452690049877783213369
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 53584232234693103790669953564737900223
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 135431606538579019225905956689564915329
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 112559249994899591330577919758944336055
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 150140559072116678002193196297066253509
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 17074186389844667756333966236643273102
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 82836370955455571146008478781338270694
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 16254124710661698025820423055202445077
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 43769528645735998152380658131815329300
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 211513813789453019359177662714979719288
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 149981298211404449757454909679214149901
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 196164108357361058832227489249577920500
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
running trial with input: 141980557567619100445655384257862983893
honest proof generation ...
success \o/
verifying false claim ...
proof rejected! \o/
attempting to prove with false witness (should fail) ...
================================================================= short test summary info ==================================================================
FAILED test_fast_stark.py::test_fast_stark - AssertionError: cannot perform polynomial division because remainder is not zero
FAILED test_ip.py::test_serialize - TypeError: deserialize() missing 1 required positional argument: 'bb'
FAILED test_stark.py::test_stark - AssertionError: cannot perform polynomial division because remainder is not zero
======================================================== 3 failed, 18 passed in 2663.71s (0:44:23) =========================================================
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
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429

2. FRI代码解析

$ pytest test_fri.py -s
================================================ test session starts =================================================
platform darwin -- Python 3.9.12, pytest-6.2.5, py-1.11.0, pluggy-1.0.0
rootdir: /Users/lanyu/zyd/stark-anatomy/code
collected 1 item                                                                                                     

test_fri.py testing valid codeword ...

success! \o/
testing invalid codeword ...
last codeword does not correspond to polynomial of low enough degree
observed degree: 127
but should be: 31
success! \o/
.

================================================= 1 passed in 16.26s =================================================
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

以test_fri.py为例：

• 基于的域为p = 1 + 407 * ( 1 << 119 ) # 1 + 11 * 37 * 2^119
• 待证明的多项式degree $d=63$，待证明多项式为：$f(X)=c_0+c_{1}X+c_2{X}^2+\cdots +c_{63}{X}^{63}$，测试用例中的系数$[c_0,c_1,c_2,\cdots ,c_{63}]=[0,1,2,\cdots ,63]$。
• rate $\rho =1/4$，expansion factor为 $1/\rho =4$
• codeword length $N=(d+1)\ast \text{expansion\_factor}$，对应为evaluation set $S$的 size，evaluation set S = { ω 0 , ω 1 , ω 2 , ⋯   , ω 63 } S=\{\omega^0, \omega^1, \omega^2,\cdots,\omega^{63}\} S={ω0,ω1,ω2,⋯,ω63}，其中$\omega$为$N$-th root of unity，$S$对应为代码中的domain，$\omega$对应为代码中的omega。
  codeword为 待证明多项式$f(X)$基于evaluation set $S$的 evaluation值集合，即 { f ( ω 0 ) , f ( ω 1 ) , f ( ω 2 ) , ⋯   , f ( ω 63 ) } \{f(\omega^0),f(\omega^1),f(\omega^2),\cdots,f(\omega^{63})\} {f(ω0),f(ω1),f(ω2),⋯,f(ω63)}。
• 根据FRI论文：
  
  可知，query complexity为$q=2\log N=16$，设置num_colinearity_tests=17。
  根据FRI论文可知，在query complexity（$q$）和 round complexity（$r$）之间做权衡，如$r=\log d/\log q$，$r$对应为代码中的num_rounds，实际计算方式为：

  	def num_rounds( self ):
          codeword_length = self.domain_length
          num_rounds = 0
          while codeword_length > self.expansion_factor and 4*self.num_colinearity_tests < codeword_length:
              codeword_length /= 2
              num_rounds += 1
          return num_rounds
  1
  2
  3
  4
  5
  6
  7

• FRI协议中，Split-and-Fold过程中，Split-and-Fold多项式为：$f^{\star }(X)=2^{-1}\cdot \left((1+\alpha X^{-1})\cdot f(X)+(1-\alpha X^{-1})\cdot f(-X)\right)$，其中A point为$({\omega }^i),f({\omega }^i)$，B point为$({\omega }^{\frac{N}{2}+i},f({\omega }^{\frac{N}{2}+i}))$，C point为$(\alpha ,f^{\star }({\omega }^{2i}))$；
  不过，当采用coset FRI时，Split-and-Fold多项式为$f^{\star }(X)=2^{-1}\cdot \left((1+\alpha (gX{)}^{-1})\cdot f(X)+(1-\alpha (gX{)}^{-1})\cdot f(-X)\right)$，但其中A point为$(g\cdot {\omega }^i),f({\omega }^i)$，B point为$(g\cdot {\omega }^{\frac{N}{2}+i},f({\omega }^{\frac{N}{2}+i}))$，C point为$(\alpha ,f^{\star }((g{\omega }^i{)}^2))$。

  # split and fold
  codeword = [two.inverse() * ( (one + alpha / (offset * (omega^i)) ) * codeword[i] + (one - alpha / (offset * (omega^i)) ) * codeword[N//2 + i] ) for i in range(N//2)]
  omega = omega^2
  offset = offset^2
  
  # compute interpolant
  last_domain = [last_offset * (last_omega^i) for i in range(len(last_codeword))]
  poly = Polynomial.interpolate_domain(last_domain, last_codeword)
  1
  2
  3
  4
  5
  6
  7
  8

Prover的基本流程为：

• 1）Commit阶段：

  • 1.1）在每一轮中，将该轮codeword构建为Merkle tree，将相应的root存入proof_stream中——发送给Verifier，将codeword存入codewords中——供后续提供query证明使用。

    	# compute and send Merkle root
        root = Merkle.commit(codeword)
        proof_stream.push(root)
        # collect codeword
        codewords += [codeword]
    1
    2
    3
    4
    5

    而最后一轮，则会将codeword root和codeword本身都发送给Verifier，同时也记录在codewords中。

    # send last codeword
    proof_stream.push(codeword)
    # collect last codeword too
    codewords = codewords + [codeword]
    1
    2
    3
    4

  • 1.2）在每一轮的Split-and-Fold过程中，challenge $\alpha$的计算方式为：

    # get challenge
    alpha = self.field.sample(proof_stream.prover_fiat_shamir())
    1
    2

  • 1.3）当将FRI与STARK一起结合使用时，由于STARK protocol中也定义了Reed-Solomon codeword，可能会存在point evaluation 相交的问题。
    因此，定义coset subgroup D = { g ⋅ ω i ∣ i ∈ Z } D = \lbrace g \cdot \omega^i \vert i \in \mathbb{Z}\rbrace D={g⋅ωi∣i∈Z}，其中$g$为整个multiplicative group F \ { 0 } \mathbb{F} \backslash \lbrace 0\rbrace F\{0}的generator。而下一轮codeword所选择的evaluation domain 为the set of squares of $D$：
    D ⋆ = { d 2 ∣ d ∈ D } = { g 2 ⋅ ω 2 i ∣ i ∈ Z } D^\star = \lbrace d^2 \vert d \in D\rbrace = \lbrace g^2 \cdot \omega^{2i} \vert i \in \mathbb{Z}\rbrace D⋆={d2∣d∈D}={g2⋅ω2i∣i∈Z}
    其中，$g$对应为代码中的generator和offset。
    因此，在除第一轮之外的各轮中，codeword为对$f^{\star }(X)=2^{-1}\cdot \left((1+\alpha X^{-1})\cdot f(X)+(1-\alpha X^{-1})\cdot f(-X)\right)$ 基于coset subgroup D = { g ⋅ ω i ∣ i ∈ Z } D = \lbrace g \cdot \omega^i \vert i \in \mathbb{Z}\rbrace D={g⋅ωi∣i∈Z}的evaluation值集合，即 { f ⋆ ( g ⋅ ω i ) } i = 0 , ⋯   , N / 2 \{f^\star(g\cdot \omega^i)\}_{i=0,\cdots,N/2} {f⋆(g⋅ωi)}i=0,⋯,N/2​：

    N = len(codeword)
    # split and fold
    codeword = [two.inverse() * ( (one + alpha / (offset * (omega^i)) ) * codeword[i] + (one - alpha / (offset * (omega^i)) ) * codeword[N//2 + i] ) for i in range(N//2)]
    1
    2
    3

• 2）根据query complexity 获取num_colinearity_tests个不同的query index——top_level_indices：

  	# get indices
      top_level_indices = self.sample_indices(proof_stream.prover_fiat_shamir(), len(codewords[1]), len(codewords[-1]), self.num_colinearity_tests)
      indices = [index for index in top_level_indices]
      
  def sample_indices( self, seed, size, reduced_size, number ):
      assert(number <= reduced_size), f"cannot sample more indices than available in last codeword; requested: {number}, available: {reduced_size}"
      assert(number <= 2*reduced_size), "not enough entropy in indices wrt last codeword"
  
      indices = []
      reduced_indices = []
      counter = 0
      while len(indices) < number:
          index = Fri.sample_index(blake2b(seed + bytes(counter)).digest(), size)
          reduced_index = index % reduced_size
          counter += 1
          if reduced_index not in reduced_indices:
              indices += [index]
              reduced_indices += [reduced_index]
      return indices
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 3）Query阶段：所有的轮之间的共用相同的query indices，原因见Anatomy of a STARK, Part 3: FRI中的“Index Folding”分析。对所有的轮之间，分别都做num_colinearity_tests次query co-linearity test。

  	# query phase
      for i in range(len(codewords)-1):
          indices = [index % (len(codewords[i])//2) for index in indices] # fold
          self.query(codewords[i], codewords[i+1], indices, proof_stream)
  1
  2
  3
  4

  其中query函数，是open相应的A/B/C point的值，以及A/B point在当前codeword的merkle proof，以及C point在下一codeword的merkle proof。open的这些信息均记录在proof_stream中：

  def query( self, current_codeword, next_codeword, c_indices, proof_stream ):
      # infer a and b indices
      a_indices = [index for index in c_indices]
      b_indices = [index + len(current_codeword)//2 for index in c_indices]
  
      # reveal leafs
      for s in range(self.num_colinearity_tests):
          proof_stream.push((current_codeword[a_indices[s]], current_codeword[b_indices[s]], next_codeword[c_indices[s]]))
  
      # reveal authentication paths
      for s in range(self.num_colinearity_tests):
          proof_stream.push(Merkle.open(a_indices[s], current_codeword))
          proof_stream.push(Merkle.open(b_indices[s], current_codeword))
          proof_stream.push(Merkle.open(c_indices[s], next_codeword))
  
      return a_indices + b_indices
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

Verifier的基本流程为：

points = [] # 记录原始codeword对应所有query indices的A/B point值，包含相应的x和y坐标。
verdict = fri.verify(proof_stream, points)
1
2

• 1）从proof_stream中提取出每一轮的codeword root以及challenge $\alpha$、最后一轮的codeword：

  	# extract all roots and alphas
      roots = []
      alphas = []
      for r in range(self.num_rounds()):
          roots += [proof_stream.pull()]
          alphas += [self.field.sample(proof_stream.verifier_fiat_shamir())]
  
      # extract last codeword
      last_codeword = proof_stream.pull()
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 2）检查最后一轮的codeword与最后一个root是否匹配：

  # check if it matches the given root
  if roots[-1] != Merkle.commit(last_codeword):
  	print("last codeword is not well formed")
      return False
  1
  2
  3
  4

• 3）检查最后一轮的codeword对应某low degree polynomial $f^{\prime }(X)$，即${\mathrm{deg}}_{f^{\prime }(X)}<\rho \ast \text{len(last\_codeword)}$。

  • 3.1）最后一轮的codeword对应的degree上限为：

    # check if it is low degree
    degree = (len(last_codeword) // self.expansion_factor) - 1
    1
    2

  • 3.2）由于采用coset-FRI，最后一轮的last_omega和last_offset为：

    last_omega = omega
    last_offset = offset
    for r in range(self.num_rounds()-1):
    	last_omega = last_omega^2
        last_offset = last_offset^2
    1
    2
    3
    4
    5

  • 3.3）校验last_omega的order正确：

    # assert that last_omega has the right order
    assert(last_omega.inverse() == last_omega^(len(last_codeword)-1)), "omega does not have right order"
    1
    2

  • 3.4）基于last_omega和last_offset组成的last_domain，对最后一轮的codeword进行插值，获得相应的多项式$f^{\prime }(X)$，对应代码中的poly：

    # compute interpolant
    last_domain = [last_offset * (last_omega^i) for i in range(len(last_codeword))]
    poly = Polynomial.interpolate_domain(last_domain, last_codeword)
    #coefficients = intt(last_omega, last_codeword)
    #poly = Polynomial(coefficients).scale(last_offset.inverse())
    1
    2
    3
    4
    5

  • 3.5）基于last_domain，对多项式$f^{\prime }(X)$进行evaluate，反向验证所有evaluation值 与 最后一轮的codeword对应。

    # verify by  evaluating
    assert(poly.evaluate_domain(last_domain) == last_codeword), "re-evaluated codeword does not match original!"
    1
    2

  • 3.6）要求多项式$f^{\prime }(X)$的degree 小于等于degree：

    if poly.degree() > degree:
      	print("last codeword does not correspond to polynomial of low enough degree")
        print("observed degree:", poly.degree())
        print("but should be:", degree)
        return False
    1
    2
    3
    4
    5

• 4）根据query complexity 获取num_colinearity_tests个不同的query index——top_level_indices：【此时的size和reduced_size分别为self.domain_length >> 1和self.domain_length >> (self.num_rounds()-1)。】

  	# get indices
      top_level_indices = self.sample_indices(proof_stream.verifier_fiat_shamir(), self.domain_length >> 1, self.domain_length >> (self.num_rounds()-1), self.num_colinearity_tests)
      
  def sample_indices( self, seed, size, reduced_size, number ):
      assert(number <= reduced_size), f"cannot sample more indices than available in last codeword; requested: {number}, available: {reduced_size}"
      assert(number <= 2*reduced_size), "not enough entropy in indices wrt last codeword"
  
      indices = []
      reduced_indices = []
      counter = 0
      while len(indices) < number:
          index = Fri.sample_index(blake2b(seed + bytes(counter)).digest(), size)
          reduced_index = index % reduced_size
          counter += 1
          if reduced_index not in reduced_indices:
              indices += [index]
              reduced_indices += [reduced_index]
      return indices
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 5）验证每一轮之间的所有query indices 的co-linearity check，以及，验证每一轮的所有query indices的A/B/C point的Merkle proof：

  	# for every round, check consistency of subsequent layers
      for r in range(0, self.num_rounds()-1):
  
          # fold c indices
          c_indices = [index % (self.domain_length >> (r+1)) for index in top_level_indices]
  
          # infer a and b indices
          a_indices = [index for index in c_indices]
          b_indices = [index + (self.domain_length >> (r+1)) for index in a_indices]
  
          # read values and check colinearity
          aa = []
          bb = []
          cc = []
          for s in range(self.num_colinearity_tests):
              (ay, by, cy) = proof_stream.pull()
              aa += [ay]
              bb += [by]
              cc += [cy]
  
              # record top-layer values for later verification
              if r == 0:
                  polynomial_values += [(a_indices[s], ay), (b_indices[s], by)]
              
              # colinearity check
              ax = offset * (omega^a_indices[s])
              bx = offset * (omega^b_indices[s])
              cx = alphas[r]
              if colinearity_test([(ax, ay), (bx, by), (cx, cy)]) == False:
                  print("colinearity check failure")
                  return False
  
          # verify authentication paths
          for i in range(self.num_colinearity_tests):
              path = proof_stream.pull()
              if Merkle.verify(roots[r], a_indices[i], path, aa[i]) == False:
                  print("merkle authentication path verification fails for aa")
                  return False
              path = proof_stream.pull()
              if Merkle.verify(roots[r], b_indices[i], path, bb[i]) == False:
                  print("merkle authentication path verification fails for bb")
                  return False
              path = proof_stream.pull()
              if Merkle.verify(roots[r+1], c_indices[i], path, cc[i]) == False:
                  print("merkle authentication path verification fails for cc")
                  return False
  
          # square omega and offset to prepare for next round
          omega = omega^2
          offset = offset^2
  
  def colinearity_test( points ):
      domain = [p[0] for p in points]
      values = [p[1] for p in points]
      polynomial = Polynomial.interpolate_domain(domain, values)
      return polynomial.degree() == 1
  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

• 6）第一轮的codeword为基于 D = { ω i } D=\{\omega^i\} D={ωi}对$f(X)$进行evaluate，而除此之外的每一轮，都是基于 D ⋆ = { g ω i } D^\star=\{g\omega^i\} D⋆={gωi}对$f^{\star }(X)$进行evaluate。在步骤5）中已对 D ⋆ = { g ω i } D^\star=\{g\omega^i\} D⋆={gωi}各轮之间的co-linearity进行了check。接下来是校验第一轮codeword的值：

  points = [] # 记录原始codeword对应所有query indices的A/B point值，包含相应的x和y坐标。
  verdict = fri.verify(proof_stream, points)
  if verdict == False:
      print("rejecting proof, but proof should be valid!")
      return
  
  for (x,y) in points: # 验证第一轮的codeword值是否正确。
      if polynomial.evaluate(omega^x) != y:
          print("polynomial evaluates to wrong value")
          assert(False)
  # -----------------------------
  def verify( self, proof_stream, polynomial_values ):
  	.....
  	# get indices
      top_level_indices = self.sample_indices(proof_stream.verifier_fiat_shamir(), self.domain_length >> 1, self.domain_length >> (self.num_rounds()-1), self.num_colinearity_tests)
  
      # for every round, check consistency of subsequent layers
      for r in range(0, self.num_rounds()-1):
  
          # fold c indices
          c_indices = [index % (self.domain_length >> (r+1)) for index in top_level_indices]
  
          # infer a and b indices
          a_indices = [index for index in c_indices]
          b_indices = [index + (self.domain_length >> (r+1)) for index in a_indices]
  
          # read values and check colinearity
          aa = []
          bb = []
          cc = []
          for s in range(self.num_colinearity_tests):
              (ay, by, cy) = proof_stream.pull()
              aa += [ay]
              bb += [by]
              cc += [cy]
  
              # record top-layer values for later verification
              if r == 0:
                  polynomial_values += [(a_indices[s], ay), (b_indices[s], by)]
             .......
  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