电路：门约束、线约束、定制门、查找表
Plonk / UltraPlonk 多项式承诺：KZG 承诺、Dan Boneh 承诺 + Fflonk 优化
Halo2 多项式承诺：向量內积承诺。对多项式使用向量内积承诺，不需要基于有毒废料计算 CRS
向量内积承诺
折半打开，并行承诺
证明方知道秘密 4 维向量 $\vec{a} = ( a_1 , a_2 , a_3 , a_4 )$，基于 SystemParameter 计算 $s = hash ( SystemParameter )$，计算 $\vec{b}= (1, s , s^2 , s^3 )$
初始化：系统参数为 $G = ( G_1 , G_2 , G_3 , G_4 )$
承诺：计算多项式承诺与多项式的值
$$ C = A + zU = <\vec{a}, \vec{G} >+ <\vec{a}, \vec{b}> U $$
其中，$A=<\vec{a}, \vec{G} >=\sum^4_{i=1}a_iG_i$ 是多项式承诺，$z=<\vec{a}, \vec{b}>$ 是多项式的值，$U$ 是椭圆曲线的生成元，这样便将多项式承诺和多项式的值放在了一个承诺中，实现并行承诺。
挑战：证明方计算 $x = hash ( SystemParameter , C , A , U )$
折半响应：证明方计算
$$ \begin{align} &a' = x^{-1}(a_1 , a_2)+ x( a_3 , a_4 ) = (x^{-1} a_1 + xa_3 , x^{-1} a_2 + xa_4)\\ &b ' = x( b_1 , b_2 ) + x^{-1} ( b_3 , b_4 ) = (x b_1 + x^{-1}b_3 , x b_2 + x^{-1}b_4)\\ &G ' = x ( G_1 , G_2 ) + x^{-1} ( G_3 , G_4 ) = (xG_1 + x^{-1}G_3 , xG_2 + x^{-1}G_4) \end{align} $$
计算
$$ \begin{align} & <a ', G '> + <a ', b '> U \\ &= [A + x^{-2} L_a + x^2 R_a] + [z + x^{-2}l_z + x^2 r_z]U \\ &= C + x^{-2}( L_a + l_z U )+ x^2 (R_a + r_z U) \\ &= C + x^{-2} L + x^2 R \end{align} $$
其中 $L=L_a + l_zU, R=R_a + r_zU$
发送数据为：$(C, \vec{a'}, L, R)$，长度为 $\frac{n}{2} + 3$
优点：N 次递归后，总共发送 $(C , a , L_1 , R_1 ,..., L_{log_2 n }, R_{log_2 n} )$，数据总量为 $2(1 + log_2 n )$。
验证：基于 $C$ 和 $\vec{G}$ 计算 $s, x, \vec{b'}$，校验
$$ C+x^{-2}L + x^{-2}R= <\vec{a'}, \vec{G'}> + <\vec{a'},\vec{b'}>U $$
多项式承诺和多项式值均正确。
N 次后，校验等式为 $C+ \sum^n_{i=1}(x_i^{-2}L_i + x_i^2R_i)=aG + abU = a(G + bU)$
添加零知识
承诺：添加随机项 $rH = <\vec{r}, \vec{1^4}>H$ ，实现零知识
$$ C = A + zU = <\vec{a}, \vec{G} >+ <\vec{a}, \vec{b}> U + <\vec{r}, \vec{1^4}>H $$
挑战：证明方计算 $x = hash ( SystemParameter , C , A , U )$
折半响应： $L=L_a + l_zU + r_LH, R=R_a + r_zU + r_RH$
发送数据为：$(C, \vec{a'}, L, R)$
N 次递归后，总共发送 $(C , a , r, L_1 , R_1 ,..., L_{log_2 n }, R_{log_2 n} )$
验证：基于 $C$ 和 $\vec{G}$ 计算 $s, x, \vec{b'}$，校验
$$ C+x^{-2}L + x^{-2}R= <\vec{a'}, \vec{G'}> + <\vec{a'},\vec{b'}>U + r'U $$
N 次后，校验等式为 $C+ \sum^n_{i=1}(x_i^{-2}L_i + x_i^2R_i)=aG + abU + rH= a(G + bU) + rH$
对于最后一次 $a(G + bU) + rH$ ，可使用经典的 sigma 协议证明其知道 $a$。
计算均摊
使用递归证明：验证方在验证时，每轮都需要折半 $\vec{G}$，计算复杂度较高，可以改为由证明方额外生成一个 proof，证明确实对 $\vec{G}$ 进行了正确的折叠。
Halo2
四个优点：
- 使用 plonk 的门约束、线约束、定制门、查找表，构造多项式
- 对多项式使用向量內积承诺：不需要基于有毒废料计算 CRS
- 使用 Tweedledum/Tweedledee 曲线，实现递归零知识证明
- 使用累积递归的方式，减少验证复杂度；做均摊
Halo2 的证明系统与 UltraPlonk 有严格的一一对应关系。
UltraPlonk 证明方：
- 对电路赋值进行承诺：电路门管脚数据多项式承诺
- 对查表数据进行承诺
- 对相等约束置换进行承诺：线数据多项式承诺
- 对查表置换进行承诺：公开且正确的 Table 多项式承诺
- 消退证明：保密数据满足门约束、线约束、查找表。计算商多项式承诺
- 多项式求值
- 多点打开证明（用到 6 结果）：计算商多项式值，确保上述所有多项式正确
Halo2 按功能分为 4 部分：
- 数据多项式承诺：对应 UltraPlonk 证明方的步骤 1-4。按打开点集的不同，将多项式划分为不同集合，然后承诺
- 消退证明：对应 UltraPlonk 证明方的步骤 5。将 vanishing argument 中 $h(X)$ 多项式，根据最大阶 $n$ 进行划分，并逐个承诺；然后，计算多项式的值
- 多点打开证明：使用多点打开方案，构造最终多项式 $f_{final} (X)$ = 随机打开点多项式 + 数据多项式
- 内积证明：承诺/验证最终的多项式 $f_{final} (X)$
没有评论