circuit基于的域为 F = F p \mathbb{F}=\mathbb{F}_p F=Fp。
令 n = 2 k n=2^k n=2k， ω \omega ω为a primitive root of unity of order n n n in F × \mathbb{F}^{\times} F×，则 F × \mathbb{F}^{\times} F×有a multiplicative subgroup H = { 1 , ω , ω 2 , ⋯ , ω n − 1 } \mathcal{H}=\{1,\omega,\omega^2,\cdots,\omega^{n-1}\} H={1,ω,ω2,⋯,ωn−1}，该subgroup即可构建a Lagrange basis。
2. Polynomial rulesa polynomial rule定义了a constraint that must hold between its specified columns at every row（即，at every element in the multiplicative subgroup）。 如：
a * sa + b * sb + a * b * sm + c * sc + PI = 0
- fixed columns：fixed for all instance of a particular circuit。这里面包含了selector columns，用于切换parts of a polynomial rule “on” or “off” to form a “custom gate”. 同时也可包含任意其它fixed data。
- advice columns：为variable values assigned in each instance of the circuit，对应为Prover的secret witness。
- public input：类似advice columns，但是为publicly known values。
每列对应为a vector of n n n values，如 a ⃗ = [ a 0 , a 1 , ⋯ , a n − 1 ] \vec{a}=[a_0,a_1,\cdots,a_{n-1}] a =[a0,a1,⋯,an−1]，可将该vector想象成是the evaluation form of the column polynomial a ( X ) , X ∈ H a(X), X\in\mathcal{H} a(X),X∈H。为了恢复相应column polynomial a ( X ) a(X) a(X)的系数，可使用Lagrange interpolation，使得 a ( ω i ) = a i a(\omega^i)=a_i a(ωi)=ai。
4. Equality constraintsequality constraints，用于：
- 定义a set of columns之间的permutation，如 σ ( a , b , c ) \sigma(a,b,c) σ(a,b,c)。
- assert equalities between specific cells in these columns，如 b 1 = c 0 b_1=c_0 b1=c0。
- 构建permuted columns which should evaluate to same value as origin columns。
Z ( ω i ) : = ∏ 0 ≤ j ≤ i C k ( ω j ) + β δ k ω j + γ C k ( ω j ) + β S k ( ω j ) + γ Z(\omega^i) := \prod_{0 \leq j \leq i} \frac{C_k(\omega^j) + \beta\delta^k \omega^j + \gamma}{C_k(\omega^j) + \beta S_k(\omega^j) + \gamma} Z(ωi):=∏0≤j≤iCk(ωj)+βSk(ωj)+γCk(ωj)+βδkωj+γ
其中 i = 0 , ⋯ , n − 1 i=0,\cdots,n-1 i=0,⋯,n−1 indexes over the size of the multiplicative subgroup， k = 0 , ⋯ , m − 1 k=0,\cdots,m-1 k=0,⋯,m−1 indexes over the advice columns involved in the permutation。 δ \delta δ的作用为：keep columns linearly independent。 这是a running product, where each term includes the cumulative（累积的）product of the terms before it。
Check the constraints：
- 1）第一个term为1： L 0 ( X ) ⋅ ( 1 − Z ( X ) ) = 0 \mathcal{L}_0(X) \cdot (1 - Z(X)) = 0 L0(X)⋅(1−Z(X))=0
- 2）Running product is well-constructed。对于每一行，check： Z ( ω i ) ⋅ ( C ( ω i ) + β S k ( ω i ) + γ ) − Z ( ω i − 1 ) ⋅ ( C ( ω i ) + δ k β ω i + γ ) = 0 Z(\omega^i) \cdot{(C(\omega^i) + \beta S_k(\omega^i) + \gamma)} - Z(\omega^{i-1}) \cdot{(C(\omega^i) + \delta^k \beta \omega^i + \gamma)} = 0 Z(ωi)⋅(C(ωi)+βSk(ωi)+γ)−Z(ωi−1)⋅(C(ωi)+δkβωi+γ)=0 重新组合为： Z ( ω i ) = Z ( ω i − 1 ) C ( ω i ) + β δ k ω i + γ C ( ω i ) + β S k ( ω i ) + γ Z(\omega^i) = Z(\omega^{i-1}) \frac{C(\omega^i) + \beta\delta^k \omega^i + \gamma}{C(\omega^i) + \beta S_k(\omega^i) + \gamma} Z(ωi)=Z(ωi−1)C(ωi)+βSk(ωi)+γC(ωi)+βδkωi+γ 即可定义相应的grand product polynomial。
TODO
5.2 Vanishing argument需check由：
- gate constraints
- permutation constraints
- lookup constraints
定义的所有expression都evaluate to zero at all elements in the multiplicative subgroup。为此，Prover需collapse all the expressions into one polynomial： H ( X ) = ∑ i = 0 e y i E i ( X ) H(X) = \sum_{i=0}^e y^i E_i(X) H(X)=∑i=0eyiEi(X) 其中， e e e为expression的数量， y y y为用于keep the constraints linearly independent的random challenge。Prover需divide this by the vanishing polynomial and commits to the resulting quotient： Commit ( Q ( X ) ) , where Q ( X ) = H ( X ) Z H ( X ) \text{Commit}(Q(X)), \text{where } Q(X) = \frac{H(X)}{Z_H(X)} Commit(Q(X)),where Q(X)=ZH(X)H(X)
Verifier发送random evaluation point x x x，Prover回复the claimed evaluations q = Q ( x ) , { e i } i = 0 e = { E i ( x ) } i = 0 e q = Q(x), \{e_i\}_{i=0}^e = \{E_i(x)\}_{i=0}^e q=Q(x),{ei}i=0e={Ei(x)}i=0e。
Verifier验证： q = ? ∑ i = 0 e y i e i Z H ( x ) q \stackrel{?}{=} \frac{\sum_{i=0}^e y^i e_i}{Z_H(x)} q=?ZH(x)∑i=0eyiei
注意，此时仍需check that the committed polynomials indeed evaluate to the claimed values at： x , q = ? Q ( x ) , { e i } i = 0 e = ? { E i ( x ) } i = 0 e . x, q \stackrel{?}{=} Q(x), \{e_i\}_{i=0}^e \stackrel{?}{=} \{E_i(x)\}_{i=0}^e. x,q=?Q(x),{ei}i=0e=?{Ei(x)}i=0e. 该check可由polynomial commitment scheme来处理。
