1. 引言

前序博客有：

• STARK入门知识
• STARKs and STARK VM: Proofs of Computational Integrity
• STARK中的FRI代码解析
• Rescue-Prime hash STARK

相关代码见：

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

以Rescue-Prime hash STARK为例。
Rescue-Prime STARK 针对的场景为：

• public info：$h,H$
• private info：$x$
• 待证明relation：$h=H(x)$

其中$H(\ast )$ 为Rescue-Prime hash函数。

Rescue-Prime hash运算中涉及：

• trace：witness信息，Rescue-Prime hash算法中每一轮的输入输出；
• boundary constraints：公开信息，Rescue-Prime hash函数算法中第一轮的补0，以及最后的hash结果；
• transition constraints（又称为AIR constraints）：公开信息，Rescue-Prime hash算法中每一轮的函数运算。

2. Rescue-Prime hash函数

根据Alan Szepieniec等人2020年论文《Rescue-Prime: a Standard Specification (SoK)》可知，Rescue-Prime哈希函数主要参数有$(p,m,c_p,s)$：

• $p$：定义了素数域${\mathbb{F}}_p$，$p$为素数且具有a binary expansion of at least 32 bits。
• $m$：定义了哈希函数的state width。状态由$m>1$个field elements确定。
• $c_p$：为arithmetic sponge的capacity。
  $r_p=m-c_p$
  $r_p$：为该arithmetic sponge的rate，决定了Recue-XLIX permutation之间absorb的field elements数量。
• $80\le s\le 512$：为 target security level，以bits为单位。

此外，还有如下参数：

• $\alpha 和{\alpha }^{-1}$：为S-boxes的幂乘系数。对于所有的$x\in {\mathbb{F}}_p$，有$(x^{\alpha }{)}^{{\alpha }^{-1}}=x$成立。
• $M\in {\mathbb{F}}_p^{m\times m}$：为$m\times m$ MDS矩阵。
• $N\in \mathbb{N}$为round数，一个单一的Rescue-XLIX permutation中包含了$N$个simpler base permutation迭代，这种simpler base permutation称为a round。
• $2mN$个field elements { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​：round constants。

2.1 sponge函数

Rescue-Prime hash函数本质是将任意长的field elements序列 映射为 $r_p$个field elements：
$$f_{R^{\prime }}:{\mathbb{F}}_p^{\ast }\to {\mathbb{F}}_p^{r_p}$$
其在sponge构造中使用了Rescue-XLIX permutation。最终sponge函数会将任意长的序列 映射为 任意长的field elements序列：
$$f_{R^{\prime }-sponge}:{\mathbb{F}}_p^{\ast }\to {\mathbb{F}}^{\star }$$
然后对该sponge函数裁剪，仅获取其前$r_p$个elements作为结果。

在sponge函数的evaluation过程中，包含了：

• 1）a permutation $f_{R^{XLIX}}:{\mathbb{F}}_p^m\to {\mathbb{F}}_p^m$
• 2）具有$m$个field elements的register，称为state。state的初始状态为全零序列 $0\in {\mathbb{F}}_p^m$。
• 3）two phases：absorbing phase以及squeezing phase。

  • 3.1）absorbing阶段：会重复以下流程，直到所有的input elements都吸收完毕：

    • 3.1.1）将input序列中的next $r_p$个elements 与 state的前$r_p$个elements相加；
    • 3.1.2）以与$r_p$个input elements相加后的state为输入，运用permutation $f_{R^{XLIX}}$，获得新的state。

  • 3.2）squeezing阶段：state的前$r_p$个elements即为输出。理论上，可对state递归调用$f_{R^{XLIX}}$获得任意长的output elements序列，不过本文限制为output elements数量最多为$r_p$个。

以input elements长度为$2\ast r_p$为例，相应的absorbing阶段具有2次迭代，示意为：

填充Padding：当inputs为任意长度时，sponge函数需要进行填充操作——在inputs之后附加一个$1\in {\mathbb{F}}_p$以及一堆$0\in {\mathbb{F}}_p$，使得填充后的inputs长度为$r_p$的整数倍。
相应的SageMath算法示例为：

2.2 Rescue-XLIX Permutation

Rescue-XLIX Permutation $f_{R^{XLIX}}$中包含了$N$次Rescue-XLIX round函数迭代，单个round中包含了以下6步：

• 1）S-box layer：对state中的每个元素进行power map $(\cdot {)}^{\alpha }$。
• 2）Linear layer：将MDS矩阵 与 state进行 矩阵向量乘法运算。
• 3）Constants injection：从round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​中取next $m$ constants，将其与state中的$m$个元素分别相加。（state中共有$m$个元素。）
• 4）Inverse S-box layer：对state中的每个元素进行inverse power map $(\cdot {)}^{{\alpha }^{-1}}$。
• 5）Linear layer：将MDS矩阵 与 state进行 矩阵向量乘法运算。
• 6）Constants injection：从round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​中取next $m$ constants，将其与state中的$m$个元素分别相加。（state中共有$m$个元素。）

以$m=3$为例，Rescue-XLIX permutation中第$i$轮示意为：

相应的SageMath代码示例为：

2.3 MDS矩阵选择

令$g$为${\mathbb{F}}_p$的smallest primitive element，通常取$g=2$，基于此找到order为$p-1$的最小$g$。详细的生成算法参见SageMath代码：

2.4 round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​选择

round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​选择，见SageMath算法：

2.5 计算$\alpha$和${\alpha }^{-1}$

$\alpha$为the smallest integer that is coprime with $p-1$，${\alpha }^{-1}$为其multiplicative inverse in the ring $\mathbb{Z}/<p-1>$。
当$\gcd (p-1,3)=1$时，有$\alpha =3,{\alpha }^{-1}=\frac{2p-1}{3}$。
详细的SageMath算法为：

2.6 计算round数

当$|p|\ge 32$且$80\le s\le 512$时，Gr¨obner basis攻击效率最高，要基于该攻击来选择round数。
详细SageMath算法见：

2.7 Rescue-Prime哈希算法

Rescue-Prime哈希SageMath算法见：

3. Rescue-Prime hash STARK证明

以https://github.com/aszepieniec/stark-anatomy/blob/master/code/rescue_prime.py中的Rescue-Prime哈希函数实现为例，其设置input length固定为1，$r_b=1,m=1,c_p=1,N=27,p=407\ast (1<<119)+1$ 等：【本例只需要一次absorb】

class RescuePrime:
    def __init__( self ):
        self.p = 407 * (1 << 119) + 1
        self.field = Field(self.p)
        self.m = 2
        self.rate = 1
        self.capacity = 1
        self.N = 27
        self.alpha = 3
        self.alphainv = 180331931428153586757283157844700080811
        self.MDS = [[FieldElement(v, self.field) for v in [270497897142230380135924736767050121214, 4]],
                    [FieldElement(v, self.field) for v in [270497897142230380135924736767050121205, 13]]]
        self.MDSinv = [[FieldElement(v, self.field) for v in [210387253332845851216830350818816760948, 60110643809384528919094385948233360270]],
                       [FieldElement(v, self.field) for v in [90165965714076793378641578922350040407, 180331931428153586757283157844700080811]]]
        self.round_constants = [FieldElement(v, self.field) for v in [174420698556543096520990950387834928928,
                                        109797589356993153279775383318666383471,
                                        228209559001143551442223248324541026000,
                                        268065703411175077628483247596226793933,
                                        250145786294793103303712876509736552288,
                                        154077925986488943960463842753819802236,
                                        204351119916823989032262966063401835731,
                                        57645879694647124999765652767459586992,
                                        102595110702094480597072290517349480965,
                                        8547439040206095323896524760274454544,
                                        50572190394727023982626065566525285390,
                                        87212354645973284136664042673979287772,
                                        64194686442324278631544434661927384193,
                                        23568247650578792137833165499572533289,
                                        264007385962234849237916966106429729444,
                                        227358300354534643391164539784212796168,
                                        179708233992972292788270914486717436725,
                                        102544935062767739638603684272741145148,
                                        65916940568893052493361867756647855734,
                                        144640159807528060664543800548526463356,
                                        58854991566939066418297427463486407598,
                                        144030533171309201969715569323510469388,
                                        264508722432906572066373216583268225708,
                                        22822825100935314666408731317941213728,
                                        33847779135505989201180138242500409760,
                                        146019284593100673590036640208621384175,
                                        51518045467620803302456472369449375741,
                                        73980612169525564135758195254813968438,
                                        31385101081646507577789564023348734881,
                                        270440021758749482599657914695597186347,
                                        185230877992845332344172234234093900282,
                                        210581925261995303483700331833844461519,
                                        233206235520000865382510460029939548462,
                                        178264060478215643105832556466392228683,
                                        69838834175855952450551936238929375468,
                                        75130152423898813192534713014890860884,
                                        59548275327570508231574439445023390415,
                                        43940979610564284967906719248029560342,
                                        95698099945510403318638730212513975543,
                                        77477281413246683919638580088082585351,
                                        206782304337497407273753387483545866988,
                                        141354674678885463410629926929791411677,
                                        19199940390616847185791261689448703536,
                                        177613618019817222931832611307175416361,
                                        267907751104005095811361156810067173120,
                                        33296937002574626161968730356414562829,
                                        63869971087730263431297345514089710163,
                                        200481282361858638356211874793723910968,
                                        69328322389827264175963301685224506573,
                                        239701591437699235962505536113880102063,
                                        17960711445525398132996203513667829940,
                                        219475635972825920849300179026969104558,
                                        230038611061931950901316413728344422823,
                                        149446814906994196814403811767389273580,
                                        25535582028106779796087284957910475912,
                                        93289417880348777872263904150910422367,
                                        4779480286211196984451238384230810357,
                                        208762241641328369347598009494500117007,
                                        34228805619823025763071411313049761059,
                                        158261639460060679368122984607245246072,
                                        65048656051037025727800046057154042857,
                                        134082885477766198947293095565706395050,
                                        23967684755547703714152865513907888630,
                                        8509910504689758897218307536423349149,
                                        232305018091414643115319608123377855094,
                                        170072389454430682177687789261779760420,
                                        62135161769871915508973643543011377095,
                                        15206455074148527786017895403501783555,
                                        201789266626211748844060539344508876901,
                                        179184798347291033565902633932801007181,
                                        9615415305648972863990712807943643216,
                                        95833504353120759807903032286346974132,
                                        181975981662825791627439958531194157276,
                                        267590267548392311337348990085222348350,
                                        49899900194200760923895805362651210299,
                                        89154519171560176870922732825690870368,
                                        265649728290587561988835145059696796797,
                                        140583850659111280842212115981043548773,
                                        266613908274746297875734026718148328473,
                                        236645120614796645424209995934912005038,
                                        265994065390091692951198742962775551587,
                                        59082836245981276360468435361137847418,
                                        26520064393601763202002257967586372271,
                                        108781692876845940775123575518154991932,
                                        138658034947980464912436420092172339656,
                                        45127926643030464660360100330441456786,
                                        210648707238405606524318597107528368459,
                                        42375307814689058540930810881506327698,
                                        237653383836912953043082350232373669114,
                                        236638771475482562810484106048928039069,
                                        168366677297979943348866069441526047857,
                                        195301262267610361172900534545341678525,
                                        2123819604855435621395010720102555908,
                                        96986567016099155020743003059932893278,
                                        248057324456138589201107100302767574618,
                                        198550227406618432920989444844179399959,
                                        177812676254201468976352471992022853250,
                                        211374136170376198628213577084029234846,
                                        105785712445518775732830634260671010540,
                                        122179368175793934687780753063673096166,
                                        126848216361173160497844444214866193172,
                                        22264167580742653700039698161547403113,
                                        234275908658634858929918842923795514466,
                                        189409811294589697028796856023159619258,
                                        75017033107075630953974011872571911999,
                                        144945344860351075586575129489570116296,
                                        261991152616933455169437121254310265934,
                                        18450316039330448878816627264054416127]]

    def hash( self, input_element ):
        # absorb
        state = [input_element] + [self.field.zero()] * (self.m - 1)

        # permutation
        for r in range(self.N):
            
            # forward half-round
            # S-box
            for i in range(self.m):
                state[i] = state[i]^self.alpha
            # matrix
            temp = [self.field.zero() for i in range(self.m)]
            for i in range(self.m):
                for j in range(self.m):
                    temp[i] = temp[i] + self.MDS[i][j] * state[j]
            # constants
            state = [temp[i] + self.round_constants[2*r*self.m+i] for i in range(self.m)]

            # backward half-round
            # S-box
            for i in range(self.m):
                state[i] = state[i]^self.alphainv
            # matrix
            temp = [self.field.zero() for i in range(self.m)]
            for i in range(self.m):
                for j in range(self.m):
                    temp[i] = temp[i] + self.MDS[i][j] * state[j]
            # constants
            state = [temp[i] + self.round_constants[2*r*self.m+self.m+i] for i in range(self.m)]

        # squeeze
        return state[0]
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

3.1 execution trace表示

上述哈希运算，对应的execution trace表示为：【将absorb之后的state、以及Rescue-XLIX Permutation $f_{R^{XLIX}}$中每轮round函数执行后的state，记录在trace中。即trace中有$m$个field elements】
【以下execution trace表示法，共有$N+1$条记录。】

	def trace( self, input_element ):
        trace = []

        # absorb
        state = [input_element] + [self.field.zero()] * (self.m - 1)

        # explicit copy to record state into trace
        trace += [[s for s in state]]

        # permutation
        for r in range(self.N):
            
            # forward half-round
            # S-box
            for i in range(self.m):
                state[i] = state[i]^self.alpha
            # matrix
            temp = [self.field.zero() for i in range(self.m)]
            for i in range(self.m):
                for j in range(self.m):
                    temp[i] = temp[i] + self.MDS[i][j] * state[j]
            # constants
            state = [temp[i] + self.round_constants[2*r*self.m+i] for i in range(self.m)]

            # backward half-round
            # S-box
            for i in range(self.m):
                state[i] = state[i]^self.alphainv
            # matrix
            temp = [self.field.zero() for i in range(self.m)]
            for i in range(self.m):
                for j in range(self.m):
                    temp[i] = temp[i] + self.MDS[i][j] * state[j]
            # constants
            state = [temp[i] + self.round_constants[2*r*self.m+self.m+i] for i in range(self.m)]
            
            # record state at this point, with explicit copy
            trace += [[s for s in state]]

        # squeeze
        # output = state[0]

        return trace
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

3.2 boundary constraints

以上execution trace表示法，共有$N+1$条记录，即总步数$T=N+1$。
边界约束条件为：

• 1）初始absorb时，即trace中的第一条记录，其capacity初始化为0。
• 2）最后一轮时，即trace中的第$N+1$条记录，其第一个值即为指定的output element。

	def boundary_constraints( self, output_element ):
        constraints = []

        # at start, capacity is zero
        constraints += [(0, 1, self.field.zero())]

        # at end, rate part is the given output element
        constraints += [(self.N, 0, output_element)]

        return constraints
1
2
3
4
5
6
7
8
9
10

3.3 transition constraints（AIR）

以上execution trace表示法，共有$N+1$条记录，即总步数cycles $T=N+1$。
令$D_{trace}$为trace evaluation domain。$D_{trace}$的generator为$o$，其order为$2^k\ge T+1$。
令 D t r a c e = { ο i ∣ i ∈ Z } D_{trace} = \lbrace \omicron^i \vert i \in \mathbb{Z}\rbrace Dtrace​={οi∣i∈Z}。

本例中，$T=27+1=28$，设置了co-linearity check等参数为：

	expansion_factor = 4
    num_colinearity_checks = 2
    security_level = 2
1
2
3

为实现zero-knowledge STARK，引入的randomizer数为：

self.num_randomizers = 4*num_colinearity_checks
1

transition_constraints_degree默认为2。
相应的trace evaluation domain 和 FRI evaluation domain参数为：

		randomized_trace_length = self.original_trace_length + self.num_randomizers # 28+8=36
        omicron_domain_length = 1 << len(bin(randomized_trace_length * transition_constraints_degree)[2:]) # 离（36*2）最近的2^k，从而结果为2^7=128。
        fri_domain_length = omicron_domain_length * expansion_factor
1
2
3

transition constraints约束表达的基本流程为：

• 1）基于trace evaluation domain $D_{trace}$，对Rescue-XLIX Permutation $f_{R^{XLIX}}$中每轮round函数执行时的$2\ast m$个round constants参数进行插值，获得相应的first_step_constants（多变量）多项式表示 以及 second_step_constants（多变量）多项式表示。

  def round_constants_polynomials( self, omicron ):
      first_step_constants = []
      for i in range(self.m):
          domain = [omicron^r for r in range(0, self.N)]
          values = [self.round_constants[2*r*self.m+i] for r in range(0, self.N)]
          univariate = Polynomial.interpolate_domain(domain, values)
          multivariate = MPolynomial.lift(univariate, 0)
          first_step_constants += [multivariate]
      second_step_constants = []
      for i in range(self.m):
          domain = [omicron^r for r in range(0, self.N)]
          values = [self.field.zero()] * self.N
          #for r in range(self.N):
          #    print("len(round_constants):", len(self.round_constants), " but grabbing index:", 2*r*self.m+self.m+i, "for r=", r, "for m=", self.m, "for i=", i)
          #    values[r] = self.round_constants[2*r*self.m + self.m + i]
          values = [self.round_constants[2*r*self.m+self.m+i] for r in range(self.N)]
          univariate = Polynomial.interpolate_domain(domain, values)
          multivariate = MPolynomial.lift(univariate, 0)
          second_step_constants += [multivariate]
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 2）以具有$2m+1$个变量的多项式transition polynomials $\mathbf{c}(X)=\mathbf{p}(\text{cycle\_index},{\text{prev\_state}}_1,\cdots ,{\text{prev\_state}}_m,{\text{next\_state}}_1,\cdots ,{\text{next\_state}}_m)$来表示，对于permutation内每个round函数的取值，其满足$\mathbf{p}(\text{cycle\_index},{\text{prev\_state}}_1,\cdots ,{\text{prev\_state}}_m,{\text{next\_state}}_1,\cdots ,{\text{next\_state}}_m)=0$。对$\mathbf{c}(X)$的AIR表示为：

  	air = []
      for i in range(self.m):
          # compute left hand side symbolically
          # lhs = sum(MPolynomial.constant(self.MDS[i][k]) * (previous_state[k]^self.alpha) for k in range(self.m)) + first_step_constants[i]
          lhs = MPolynomial.constant(self.field.zero())
          for k in range(self.m):
              lhs = lhs + MPolynomial.constant(self.MDS[i][k]) * (previous_state[k]^self.alpha)
          lhs = lhs + first_step_constants[i]
  
          # compute right hand side symbolically
          # rhs = sum(MPolynomial.constant(self.MDSinv[i][k]) * (next_state[k] - second_step_constants[k]) for k in range(self.m))^self.alpha
          rhs = MPolynomial.constant(self.field.zero())
          for k in range(self.m):
              rhs = rhs + MPolynomial.constant(self.MDSinv[i][k]) * (next_state[k] - second_step_constants[k])
          rhs = rhs^self.alpha
  
          # equate left and right hand sides
          air += [lhs-rhs]
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

3.4 生成STARK证明

基于execution trace、boundary constraints、transition constraints（AIR），基于FRI evaluation domain，调用stark.prove生成STARK证明。

# prove
trace = rp.trace(input_element)
air = rp.transition_constraints(stark.omicron)
boundary = rp.boundary_constraints(output_element)
proof = stark.prove(trace, air, boundary)
1
2
3
4
5

num_registers实际就是Rescue-Prime的state width，本例中为2。
num_randomizers = 4*num_colinearity_checks
生成STARK proof的基本流程为：

• 1）在trace中附加num_randomiers行随机值，以实现zero-knowledge：

  	# concatenate randomizers
      for k in range(self.num_randomizers):
          trace = trace + [[self.field.sample(os.urandom(17)) for s in range(self.num_registers)]]
  1
  2
  3

• 2）基于附加了随机值之后的trace，构建trace domain和trace polynomials：

  	# interpolate
      trace_domain = [self.omicron^i for i in range(len(trace))]
      trace_polynomials = []
      for s in range(self.num_registers):
          single_trace = [trace[c][s] for c in range(len(trace))]
          trace_polynomials = trace_polynomials + [Polynomial.interpolate_domain(trace_domain, single_trace)]	
  1
  2
  3
  4
  5
  6

• 3）所谓boundary constraints，是指对trace中特定行特定列寄存器值的约束，如本例的boundary constraints为：

  boundary = rp.boundary_constraints(output_element)
  # -------------------
  def boundary_constraints( self, output_element ):
      constraints = []
  
      # at start, capacity is zero
      constraints += [(0, 1, self.field.zero())]
  
      # at end, rate part is the given output element
      constraints += [(self.N, 0, output_element)]
  
      return constraints
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

  boundary constraints的组成格式为（trace_row, trace_column, register_value），基于trace domain，只取boundary中该列包含的行的domain和value值，逐列插值获得boundary polynomials：

  def boundary_interpolants( self, boundary ):
      interpolants = []
      for s in range(self.num_registers):
          points = [(c,v) for c, r, v in boundary if r == s]
          domain = [self.omicron^c for c,v in points]
          values = [v for c,v in points]
          interpolants = interpolants + [Polynomial.interpolate_domain(domain, values)]
      return interpolants
  1
  2
  3
  4
  5
  6
  7
  8

• 4）根据boundary constraints，获取各列boundary polynomial对应的zerofier 多项式：

  def zerofier_domain( domain ):
      field = domain[0].field
      x = Polynomial([field.zero(), field.one()])
      acc = Polynomial([field.one()])
      for d in domain:
          acc = acc * (x - Polynomial([d]))
      return acc
  1
  2
  3
  4
  5
  6
  7

• 5）逐列，(trace_polynomial - boundary_polynomial) / zerofier，获得boundary_quotient多项式：

  	# subtract boundary interpolants and divide out boundary zerofiers
      boundary_quotients = []
      for s in range(self.num_registers):
          interpolant = self.boundary_interpolants(boundary)[s]
          zerofier = self.boundary_zerofiers(boundary)[s]
          quotient = (trace_polynomials[s] - interpolant) / zerofier
          boundary_quotients += [quotient]
  1
  2
  3
  4
  5
  6
  7

• 6）接下来，采用FRI协议来证明以上boundary_quotient结果是多项式。
  FRI evaluation domain为Coset-FRI，取值为：

  fri_domain_length = omicron_domain_length * expansion_factor
  self.omega = self.field.primitive_nth_root(fri_domain_length)
  self.generator = self.field.generator()
  self.fri = Fri(self.generator, self.omega, fri_domain_length, self.expansion_factor, self.num_colinearity_checks)
  
  fri_domain = self.fri.eval_domain()
  # --------------
  def eval_domain( self ):
      return [self.offset * (self.omega^i) for i in range(self.domain_length)]
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 7）逐列，基于FRI evaluation domain，对每个boundary quotient多项式进行commit：

  	# commit to boundary quotients
      boundary_quotient_codewords = []
      boundary_quotient_Merkle_roots = []
      for s in range(self.num_registers):
          boundary_quotient_codewords = boundary_quotient_codewords + [boundary_quotients[s].evaluate_domain(fri_domain)]
          merkle_root = Merkle.commit(boundary_quotient_codewords[s])
          proof_stream.push(merkle_root)
  1
  2
  3
  4
  5
  6
  7

• 8）将trace_polynomials及其偏移多项式放入多项式数组point中，格式为$[X,t_1(X),t_2(X),\cdots ,t_m(X),t_1(o\cdot X),t_2(o\cdot X),\cdots ,t_m(o\cdot X)]$共$2m+1$项：【若tp=t(X)，则tp.scale(w)=t(wX)。】

  point = [Polynomial([self.field.zero(), self.field.one()])] + trace_polynomials + [tp.scale(self.omicron) for tp in trace_polynomials]
  1

• 9）针对transition constraints，相应的transition polynomials表示为： $\mathbf{c}(X)=\mathbf{p}(X,t_0(X)),\dots ,t_{\mathsf{m}-1}(X),t_0(o\cdot X),\dots ,t_{\mathsf{m}-1}(o\cdot X))$，逐列，对transition polynomial进行symbolically evaluate：

  	# symbolically evaluate transition constraints
      point = [Polynomial([self.field.zero(), self.field.one()])] + trace_polynomials + [tp.scale(self.omicron) for tp in trace_polynomials]
      transition_polynomials = [a.evaluate_symbolic(point) for a in transition_constraints]
  1
  2
  3

• 10）对未附加随机值的所有有效trace行（本例为$0N$行，不包含后续附加的8行随机值），基于trace domain构建transition_zerofier：

  self.original_trace_length = num_cycles
  
  def transition_zerofier( self ):
      domain = self.omicron_domain[0:(self.original_trace_length-1)]
      return Polynomial.zerofier_domain(domain)
  1
  2
  3
  4
  5

• 11）逐列，transition_polynomial / transition_zerofier，获得transition_quotient多项式：

  # divide out zerofier
  transition_quotients = [tp / self.transition_zerofier() for tp in transition_polynomials]
  1
  2

• 12）为实现zero-knowledge，引入degree为self.max_degree(transition_constraints)的随机多项式randomizer_polynomial（来对transition polynomials进行hide），并对其进行commit：

  	# commit to randomizer polynomial
      randomizer_polynomial = Polynomial([self.field.sample(os.urandom(17)) for i in range(self.max_degree(transition_constraints)+1)])
      randomizer_codeword = randomizer_polynomial.evaluate_domain(fri_domain) 
      randomizer_root = Merkle.commit(randomizer_codeword)
      proof_stream.push(randomizer_root)
  1
  2
  3
  4
  5

• 13）获取随机weight值（为randomizer多项式提供1个随机weight值；为每个transition_quotient多项式提供2个随机weight值；为每个boundary_quotient多项式提供2个随机weight值）：

  # get weights for nonlinear combination
  #  - 1 randomizer
  #  - 2 for every transition quotient
  #  - 2 for every boundary quotient
  weights = self.sample_weights(1 + 2*len(transition_quotients) + 2*len(boundary_quotients), proof_stream.prover_fiat_shamir())
  
  def sample_weights( self, number, randomness ):
      return [self.field.sample(blake2b(randomness + bytes(i)).digest()) for i in range(0, number)]
  1
  2
  3
  4
  5
  6
  7
  8

• 14）要求每个transition_quotient多项式的degree与期待值相符：

  assert([tq.degree() for tq in transition_quotients] == self.transition_quotient_degree_bounds(transition_constraints)), "transition quotient degrees do not match with expectation"
  1

• 15）将randomizer_polynomial与所有的transition_quotient及其偏移多项式、所有的boundary_quotient及其偏移多项式非线性组合（各多项式分别乘以不同的weight）在一起：

   	# compute terms of nonlinear combination polynomial
      x = Polynomial([self.field.zero(), self.field.one()])
      max_degree = self.max_degree(transition_constraints)
      terms = []
      terms += [randomizer_polynomial]
      for i in range(len(transition_quotients)):
          terms += [transition_quotients[i]]
          shift = max_degree - self.transition_quotient_degree_bounds(transition_constraints)[i]
          terms += [(x^shift) * transition_quotients[i]]
      for i in range(self.num_registers):
          terms += [boundary_quotients[i]]
          shift = max_degree - self.boundary_quotient_degree_bounds(len(trace), boundary)[i]
          terms += [(x^shift) * boundary_quotients[i]]
  	
  	# take weighted sum
      # combination = sum(weights[i] * terms[i] for all i)
      combination = reduce(lambda a, b : a+b, [Polynomial([weights[i]]) * terms[i] for i in range(len(terms))], Polynomial([]))
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 16）对非线性weighted组合后的多项式combination，基于FRI evaluation domain计算相应的codeword，并调用FRI协议证明“非线性weighted组合后的combination确实是low-degree多项式”：【其中Prover会提供针对combination多项式，相应query indices的leaf及其相应的Merkle证明：】

  # compute matching codeword
      combined_codeword = combination.evaluate_domain(fri_domain)
  
      # prove low degree of combination polynomial, and collect indices
      indices = self.fri.prove(combined_codeword, proof_stream)
  1
  2
  3
  4
  5

• 17）针对相同的query indices，Prover还需提供之前所commit的boundary多项式 以及 randomizer多项式 相应的leaf和Merkle证明：

  	# process indices
      duplicated_indices = [i for i in indices] + [(i + self.expansion_factor) % self.fri.domain_length for i in indices]
      quadrupled_indices = [i for i in duplicated_indices] + [(i + (self.fri.domain_length // 2)) % self.fri.domain_length for i in duplicated_indices]
      quadrupled_indices.sort()
  
      # open indicated positions in the boundary quotient codewords
      for bqc in boundary_quotient_codewords:
          for i in quadrupled_indices:
              proof_stream.push(bqc[i])
              path = Merkle.open(i, bqc)
              proof_stream.push(path)
  
      # ... as well as in the randomizer
      for i in quadrupled_indices:
          proof_stream.push(randomizer_codeword[i])
          path = Merkle.open(i, randomizer_codeword)
          proof_stream.push(path)
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 18）最终的proof为对proof_stream的序列化：

  # the final proof is just the serialized stream
      return proof_stream.serialize()
  1
  2

3.5 验证STARK证明

Rescue-Prime hash运算中涉及：

• trace：witness信息，Rescue-Prime hash算法中每一轮的输入输出；
• boundary constraints：公开信息，Rescue-Prime hash函数算法中第一轮的补0，以及最后的hash结果；
• transition constraints（又称为AIR constraints）：公开信息，Rescue-Prime hash算法中每一轮的函数运算。

因此，验证STARK证明的输入有：

• proof：STARK证明
• air：transition constraints（又称为AIR constraints）
• boundary：boundary constraints

# verify
verdict = stark.verify(proof, air, boundary)
# -----
def verify( self, proof, transition_constraints, boundary, proof_stream=None ):
。。。。。。
1
2
3
4
5

验证STARK证明的基本流程为：

• 1）基于boundary constraints中的最大index，推断出相应的trace length：

  # infer trace length from boundary conditions
  original_trace_length = 1 + max(c for c, r, v in boundary)
  randomized_trace_length = original_trace_length + self.num_randomizers
  1
  2
  3

• 2）对proof进行反序列化：

  	# deserialize with right proof stream
      if proof_stream == None:
          proof_stream = ProofStream()
      proof_stream = proof_stream.deserialize(proof)
  1
  2
  3
  4

• 3）读取各boundary quotient merkle root 和 randomizer多项式的merkle root，基于这些root派生出相应的weights信息：

  	# get Merkle roots of boundary quotient codewords
      boundary_quotient_roots = []
      for s in range(self.num_registers):
          boundary_quotient_roots = boundary_quotient_roots + [proof_stream.pull()]
  
      # get Merkle root of randomizer polynomial
      randomizer_root = proof_stream.pull()
  
      # get weights for nonlinear combination
      weights = self.sample_weights(1 + 2*len(transition_constraints) + 2*len(self.boundary_interpolants(boundary)), proof_stream.verifier_fiat_shamir())
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 4）调用FRI协议，验证非线性weighted组合后的combination多项式为low-degree多项式：【返回的polynomial_values（[indices/values]）后续要进行polynomial evaluate检查。indices为所query的位置 】

  	# verify low degree of combination polynomial
      polynomial_values = []
      verifier_accepts = self.fri.verify(proof_stream, polynomial_values)
      polynomial_values.sort(key=lambda iv : iv[0])
      if not verifier_accepts:
          return False
  
      indices = [i for i,v in polynomial_values]
      values = [v for i,v in polynomial_values]
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 5）对所有query的indices位置，验证各boundary_quotient的merkle证明成立：

  	# read and verify leafs, which are elements of boundary quotient codewords
      duplicated_indices = [i for i in indices] + [(i + self.expansion_factor) % self.fri.domain_length for i in indices]
      duplicated_indices.sort()
      leafs = []
      for r in range(len(boundary_quotient_roots)):
          leafs = leafs + [dict()]
          for i in duplicated_indices:
              leafs[r][i] = proof_stream.pull()
              path = proof_stream.pull()
              verifier_accepts = verifier_accepts and Merkle.verify(boundary_quotient_roots[r], i, path, leafs[r][i])
              if not verifier_accepts:
                  return False
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

• 6）对所有query的indices位置，验证randomizer多项式的merkle证明成立：

  	# read and verify randomizer leafs
      randomizer = dict()
      for i in duplicated_indices:
          randomizer[i] = proof_stream.pull()
          path = proof_stream.pull()
          verifier_accepts = verifier_accepts and Merkle.verify(randomizer_root, i, path, randomizer[i])
          if not verifier_accepts:
              return False
  1
  2
  3
  4
  5
  6
  7
  8

• 7）针对 各boundary_quotient多项式 以及 randomizer多项式 query所公开的leaf value，结合weights参数 和 transition constraints（为公开信息，可获得各transition_quotients），重构combination evaluate值，验证其与self.fri.verify返回的values值是否匹配：

  	# verify leafs of combination polynomial
      for i in range(len(indices)):
          current_index = indices[i] # do need i
  
          # get trace values by applying a correction to the boundary quotient values (which are the leafs)
          domain_current_index = self.generator * (self.omega^current_index)
          next_index = (current_index + self.expansion_factor) % self.fri.domain_length
          domain_next_index = self.generator * (self.omega^next_index)
          current_trace = [self.field.zero() for s in range(self.num_registers)]
          next_trace = [self.field.zero() for s in range(self.num_registers)]
          for s in range(self.num_registers):
              zerofier = self.boundary_zerofiers(boundary)[s]
              interpolant = self.boundary_interpolants(boundary)[s]
  
              current_trace[s] = leafs[s][current_index] * zerofier.evaluate(domain_current_index) + interpolant.evaluate(domain_current_index)
              next_trace[s] = leafs[s][next_index] * zerofier.evaluate(domain_next_index) + interpolant.evaluate(domain_next_index)
  
          point = [domain_current_index] + current_trace + next_trace
          transition_constraints_values = [transition_constraints[s].evaluate(point) for s in range(len(transition_constraints))]
  
          # compute nonlinear combination
          counter = 0
          terms = []
          terms += [randomizer[current_index]]
          for s in range(len(transition_constraints_values)):
              tcv = transition_constraints_values[s]
              quotient = tcv / self.transition_zerofier().evaluate(domain_current_index)
              terms += [quotient]
              shift = self.max_degree(transition_constraints) - self.transition_quotient_degree_bounds(transition_constraints)[s]
              terms += [quotient * (domain_current_index^shift)]
          for s in range(self.num_registers):
              bqv = leafs[s][current_index] # boundary quotient value
              terms += [bqv]
              shift = self.max_degree(transition_constraints) - self.boundary_quotient_degree_bounds(randomized_trace_length, boundary)[s]
              terms += [bqv * (domain_current_index^shift)]
          combination = reduce(lambda a, b : a+b, [terms[j] * weights[j] for j in range(len(terms))], self.field.zero())
  
          # verify against combination polynomial value
          verifier_accepts = verifier_accepts and (combination == values[i])
          if not verifier_accepts:
              return False
  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

参考资料

[1] Anatomy of a STARK, Part 5: A Rescue-Prime STARK