1. 引言
Halo2中，采用不同语言来描述PLONK概念：
- 1）将类似PLONK argument都想象成table，每一列对应a “wire”，将table中的entries称为“cells”。
- 2）将“selector polynomials”称为“fixed columns”，当a cell in a fixed column is being used to control whether a particular constraint is enable in that row时，则使用a “selector constraint”。
- 3）将仅由Prover掌握的其他polynomials统称为“advice columns”。
- 4）将“gate”称为rule，如： A ( X ) ⋅ q A ( X ) + B ( X ) ⋅ q B ( X ) + A ( X ) ⋅ B ( X ) ⋅ q M ( X ) + C ( X ) ⋅ q C ( X ) = 0 A(X) \cdot q_A(X) + B(X) \cdot q_B(X) + A(X) \cdot B(X) \cdot q_M(X) + C(X) \cdot q_C(X) = 0 A(X)⋅qA(X)+B(X)⋅qB(X)+A(X)⋅B(X)⋅qM(X)+C(X)⋅qC(X)=0
- 5）将 Z ( X ) Z(X) Z(X)多项式（the grand product argument polynomial for the permutation argument）称为"permutation product" column。
Halo2中的proving system可分为以下5个阶段：
- Commit to polynomials encoding the main components of the circuit:
- Cell assignments.
- Permuted values and products for each lookup argument.
- Equality constraint permutations.
- Construct the vanishing argument to constrain all circuit relations to zero:
- Standard and custom gates.
- Lookup argument rules.
- Equality constraint permutation rules.
- Evaluate the above polynomials at all necessary points:
- All relative rotations used by custom gates across all columns.
- Vanishing argument pieces.
- Construct the multipoint opening argument to check that all evaluations are consistent with their respective commitments.
- Run the inner product argument to create a polynomial commitment opening proof for the multipoint opening argument polynomial.
为了便于解释，接下来以如下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
详细可参看Halo2论文，整个Halo2协议可简化描述为：【注意，如下协议不具有zero-knowledge属性。】
ProverVerifier ← \larr ← t ( X ) = ( X n − 1 ) t(X) = (X^n - 1) t(X)=(Xn−1) ← \larr ← F = [ F 0 , F 1 , … , F m − 1 ] F = [F_0, F_1, \dots, F_{m - 1}] F=[F0,F1,…,Fm−1] A = [ A 0 , A 1 , … , A m − 1 ] \mathbf{A} = [A_0, A_1, \dots, A_{m - 1}] A=[A0,A1,…,Am−1] → \rarr → ← \larr ← θ \theta θ L = [ ( A 0 ′ , S 0 ′ ) , … , ( A m − 1 ′ , S m − 1 ′ ) ] \mathbf{L} = [(A'_0, S'_0), \dots, (A'_{m - 1}, S'_{m - 1})] L=[(A0′,S0′),…,(Am−1′,Sm−1′)] → \rarr → ← \larr ← β , γ \beta, \gamma β,γ Z P = [ Z P , 0 , Z P , 1 , … ] \mathbf{Z_P} = [Z_{P,0}, Z_{P,1}, \ldots] ZP=[ZP,0,ZP,1,…] → \rarr → Z L = [ Z L , 0 , Z L , 1 , … ] \mathbf{Z_L} = [Z_{L,0}, Z_{L,1}, \ldots] ZL=[ZL,0,ZL,1,…] → \rarr → ← \larr ← y y y h ( X ) = gate 0 ( X ) + ⋯ + y i ⋅ gate i ( X ) t ( X ) h(X) = \frac{\text{gate}_0(X) + \dots + y^i \cdot \text{gate}_i(X)}{t(X)} h(X)=t(X)gate0(X)+⋯+yi⋅gatei(X) h ( X ) = h 0 ( X ) + ⋯ + X n ( d − 1 ) h d − 1 ( X ) h(X) = h_0(X) + \dots + X^{n(d-1)} h_{d-1}(X) h(X)=h0(X)+⋯+Xn(d−1)hd−1(X) H = [ H 0 , H 1 , … , H d − 1 ] \mathbf{H} = [H_0, H_1, \dots, H_{d-1}] H=[H0,H1,…,Hd−1] → \rarr → ← \larr ← x x x e v a l s = [ A 0 ( x ) , … , H d − 1 ( x ) ] evals = [A_0(x), \dots, H_{d - 1}(x)] evals=[A0(x),…,Hd−1(x)] → \rarr →Checks h ( x ) h(x) h(x) ← \larr ← x 1 , x 2 x_1, x_2 x1,x2Constructs h ′ ( X ) h'(X) h′(X) multipoint opening poly U = Commit ( h ′ ( X ) ) U = \text{Commit}(h'(X)) U=Commit(h′(X)) → \rarr → ← \larr ← x 3 x_3 x3 q evals = [ Q 0 ( x 3 ) , Q 1 ( x 3 ) , … ] \mathbf{q}_\text{evals} = [Q_0(x_3), Q_1(x_3), \dots] qevals=[Q0(x3),Q1(x3),…] → \rarr → u eval = U ( x 3 ) u_\text{eval} = U(x_3) ueval=U(x3) → \rarr → ← \larr ← x 4 x_4 x4然后，Prover和Verifier：
- 构建 finalPoly ( X ) \text{finalPoly}(X) finalPoly(X) as a linear combination of Q ⃗ \vec{Q} Q and U U U using powers of x 4 x_4 x4；
- 构建 finalPolyEval \text{finalPolyEval} finalPolyEval as the equivalent linear combination of q ⃗ e v a l s \vec{q}_{evals} q evals and u e v a l u_{eval} ueval；
- Perfrom InnerProduct ( finalPoly ( X ) , x 3 , finalPolyEval ) \text{InnerProduct}(\text{finalPoly}(X),x_3,\text{finalPolyEval}) InnerProduct(finalPoly(X),x3,finalPolyEval)。
[1] Halo2之Proving system
