在完成对circuit assignment进行commit之后，Prover需要证明满足如下多种circuit关系：
- custom gates：以多项式 gate i ( X ) \text{gate}_i(X) gatei(X)表示。
- lookup arguments中的rules。
- equality constraint permutations中的rules。
每种关系都以degree为 d d d的的多项式来表示，对应为circuit中的一列（其中 d d d为the maximum degree of any of the relations）。 若已知每列对应的assignment多项式的degree为 n − 1 n-1 n−1，则相应的关系多项式对应变量 X X X的degree为 d ( n − 1 ) d(n-1) d(n−1)。
以如下constraint system为例：
- 有4个advice columns： a , b , c , d a,b,c,d a,b,c,d
- 有1个fixed column： f f f
- 有3个custom gates：
- a ⋅ b ⋅ c − 1 − d = 0 a\cdot b\cdot c_{-1}-d=0 a⋅b⋅c−1−d=0
- f − 1 ⋅ c = 0 f_{-1}\cdot c=0 f−1⋅c=0
- f ⋅ d ⋅ a = 0 f\cdot d\cdot a =0 f⋅d⋅a=0
以上例子中，对应的gate polynomial degree为 3 n − 3 3n-3 3n−3：
- gate 0 ( X ) = a 0 ( X ) ⋅ a 1 ( X ) ⋅ a 2 ( X ω − 1 ) − a 3 ( X ) \text{gate}_0(X) = a_0(X) \cdot a_1(X) \cdot a_2(X \omega^{-1}) - a_3(X) gate0(X)=a0(X)⋅a1(X)⋅a2(Xω−1)−a3(X)
- gate 1 ( X ) = f 0 ( X ω − 1 ) ⋅ a 2 ( X ) \text{gate}_1(X) = f_0(X \omega^{-1}) \cdot a_2(X) gate1(X)=f0(Xω−1)⋅a2(X)
- gate 2 ( X ) = f 0 ( X ) ⋅ a 3 ( X ) ⋅ a 0 ( X ) \text{gate}_2(X) = f_0(X) \cdot a_3(X) \cdot a_0(X) gate2(X)=f0(X)⋅a3(X)⋅a0(X)
若以上多项式等于0，则上例中的relation is satisfied。 方法之一是，将以上每个多项式都除以vanishing polynomial t ( X ) = ( X n − 1 ) t(X)=(X^n-1) t(X)=(Xn−1)，该vanishing polynomial为the lowest-degree monomial that has roots at every ω i \omega^i ωi。若relation的polynomial可整除 t ( X ) t(X) t(X)，则其equal to zero over the domain (as desired)。
最简单的方式是为每个relation创建一个polynomial commitment，可同时对所有的circuit relations进行commit；Verifier发送challenge y y y；Prover构建quotient polynomial： h ( X ) = gate 0 ( X ) + y ⋅ gate 1 ( X ) + ⋯ + y i ⋅ gate i ( X ) + … t ( X ) h(X) = \frac{\text{gate}_0(X) + y \cdot \text{gate}_1(X) + \dots + y^i \cdot \text{gate}_i(X) + \dots}{t(X)} h(X)=t(X)gate0(X)+y⋅gate1(X)+⋯+yi⋅gatei(X)+… 其中分子为a random linear combination of the circuit relations。（因为Prover commits to the cell assignments before the Verifier samples y y y。）
- 若分子多项式（in formal indeterminate X X X）可整除 t ( X ) t(X) t(X)，则大概率所有的relations都satisfied。
- 相反，若至少一个relation未satisfy，则大概率 h ( x ) ⋅ t ( x ) h(x)\cdot t(x) h(x)⋅t(x) 不会等于分子多项式evaluate at x x x的值。此时，分子多项式无法整除 t ( X ) t(X) t(X)。
由于分子多项式的degree为 d ( n − 1 ) d(n-1) d(n−1)，分母 t ( X ) t(X) t(X)的degree为 n n n，因此 h ( X ) h(X) h(X)的degree为 ( d − 1 ) n − d (d-1)n-d (d−1)n−d。但是，Halo2中的polynomial commitment scheme仅支持对degree为 n − 1 n-1 n−1的多项式进行commit（其中 n − 1 n-1 n−1为the maximum degree that the rest of the protocol needs to commit to）。为了不增加polynomial commitment scheme的开销，Prover可将 h ( X ) h(X) h(X)切分为多个degree为 n − 1 n-1 n−1的多项式，将 h ( X ) h(X) h(X)切分表示为： h 0 ( X ) + X n h 1 ( X ) + ⋯ + X n ( d − 1 ) h d − 1 ( X ) h_0(X) + X^n h_1(X) + \dots + X^{n(d-1)} h_{d-1}(X) h0(X)+Xnh1(X)+⋯+Xn(d−1)hd−1(X) 然后Prover再对每个子多项式进行blinding commit： H = [ Commit ( h 0 ( X ) ) , Commit ( h 1 ( X ) ) , … , Commit ( h d − 1 ( X ) ) ] \mathbf{H} = [\text{Commit}(h_0(X)), \text{Commit}(h_1(X)), \dots, \text{Commit}(h_{d-1}(X))] H=[Commit(h0(X)),Commit(h1(X)),…,Commit(hd−1(X))]
3. Evaluating the polnomials此时，circuit中的所有属性均已commit to。Verifier需要看Prover是否committed to the correct h ( X ) h(X) h(X) polynomial。 Verifier提供challenge x x x，Prover生成多个多项式在 x x x的evaluations值，以上面2中例子为例，有：
- a 0 ( x ) a_0(x) a0(x)
- a 1 ( x ) a_1(x) a1(x)
- a 2 ( x ) a_2(x) a2(x), a 2 ( x ω − 1 ) a_2(x \omega^{-1}) a2(xω−1)
- a 3 ( x ) a_3(x) a3(x)
- f 0 ( x ) f_0(x) f0(x), f 0 ( x ω − 1 ) f_0(x \omega^{-1}) f0(xω−1)
- h 0 ( x ) h_0(x) h0(x), …, h d − 1 ( x ) h_{d-1}(x) hd−1(x)
Verifier会验证以上evaluations是否满足 h ( X ) h(X) h(X)的form： gate 0 ( x ) + ⋯ + y i ⋅ gate i ( x ) + … t ( x ) = h 0 ( x ) + ⋯ + x n ( d − 1 ) h d − 1 ( x ) \frac{\text{gate}_0(x) + \dots + y^i \cdot \text{gate}_i(x) + \dots}{t(x)} = h_0(x) + \dots + x^{n(d-1)} h_{d-1}(x) t(x)gate0(x)+⋯+yi⋅gatei(x)+…=h0(x)+⋯+xn(d−1)hd−1(x)
此时，content that the evaluations collectively satisfy the gate constraints, the verifier needs to check that the evaluations themselves are consistent with the original circuit commitments, as well as H \mathbf{H} H。 为了提升效率，Halo2中引入了a multipoint opening argument。
参考资料[1] Halo2 之 Vanishing argument
