KZG 多项式承诺
https://aping-dev.com/index.php/archives/464/
多项式个数越多，验证越复杂；打开点数越多，验证越复杂。
Dan Boneh 承诺 (Shplonk)
验证复杂度仅与多项式个数有关，与随机打开点数无关。
高阶多项式 $f$ 在集合 $S \subset F $ 上函数值等于低阶多项式 $r \in F_{< |S|}[X]$ 在 $z \in S$ 点上的函数值 $r(z) = f(z)$，即两个阶不同的多项式，函数值有交集。$F_{<d}[X]$ 指多项式 $F[X]$ 中元素的阶小于 $d$。
以下 3 个条件等价
- 条件 1：对于 $|S|$ 个打开点 $z \in S$，两个多项式的值相等 $r(z) = f(z)$（验证复杂度与打开点数相关、与多项式个数相关）
- 条件 2：目标多项式 $Z_S(X)=\prod_{z \in S}(X-z)$ 是多项式 $g(X) = f(X) - r(X)$ 的因子，即 $Z_S(X) | g(X)$（验证复杂度仅与多项式个数相关）
- 条件 3：子集 $S \subset T \subset F$，有 $Z_{T}(X) | Z_{T / S} \cdot g(X)$（验证复杂度仅与多项式个数相关，但复杂度进一步降低）
条件 2 中，$Q = \frac{f(X)-r(X)}{Z_{S}(X)}$ 称为商多项式；分母为目标多项式，也称为消失多项式
条件 3 推导： $Z_{S}(X)|g(X) \iff Z_{T/S}(X) \cdot Z_{S}(X) | Z_{T/S}(X) \cdot g(X) \iff Z_T(X)|Z_{T/S}(X) \cdot g(X)$
Dan Boneh 承诺使用条件 2、3。如果 2 或 3 成立，则条件 1 成立。
t 个多项式打开 s 个随机点，使用条件 3
系统初始化：双线性群为 $\sigma=(e, G_1, G_2, G_T)$，随机数 $\alpha \in Z_P^*$，$d+2$ 元组 $(G_1, \alpha G_1, ..., \alpha^{d-1}G_1; G_2, \alpha G_2) \in (G_1^d, G_2^2)$，令输出为
$$ PK=(\sigma, G_1, \alpha G_1, ..., \alpha^{d-1}G_1; G_2, \alpha G_2) $$
承诺：计算 $t$ 个多项式 $f_i(x)=\sum_{j=0}^{deg(f_i)}f_{i,j} \cdot X^j, i \in [1,t]$ 的承诺
$$ C_i = f_i(\alpha) \cdot G_1 = \sum_{j=0}^{deg(f_i)}f_{i,j} \cdot \alpha^j G_1, i \in [1,t] $$
打开 S 个随机点：基于上述多项式承诺和 transcript 计算随机数 $\gamma$，计算商多项式
$$ h(X) = \frac{\sum_{i\in[k]} \gamma^{i-1} \cdot Z_{T/S_i}(X) \cdot (f_i(X) - r_i(X))}{Z_T(X)} $$
计算并发送 1 个商多项式承诺 $W_1$
$$ W_1 = h(\alpha) \cdot G_1 $$
基于上述多项式承诺计算随机数 $z$
计算一个辅助多项式
$$ \begin{align} & f_z(X) = \sum_{i \in [k]}\gamma^{i-1} \cdot Z_{T / S_i}(z) \cdot (f_i(X) - r_i(z)) \\ & L(X) = f_z(X) - Z_T(z) \cdot h(X) \end{align} $$
由于 $L(z) = f_z(z) - Z_T(z) \cdot h(z)= 0$，则 $(X - z) | L(X)$
计算并发送 1 个辅助多项式的商多项式承诺 $W_2$
$$ W_2 = \frac{L(\alpha)}{\alpha - z} \cdot G_1 $$
验证 S 个随机点：基于 transcript 计算随机数 $\gamma$，如果以下等式成立，则接受，否则拒绝
$$ e(F + z \cdot W_2, G_2) = e(W_2, \alpha \cdot G_2) $$
其中，$F=-Z_T(z) \cdot W_1 + \sum_{i \in [k]} \gamma^{i-1} Z_{T/S_i}(z) \cdot C_i - \begin{pmatrix} \sum_{i \in [k]} \gamma ^{i-1} \cdot Z_{T/S_i(z)}(z) \cdot r_i(z) \end{pmatrix} \cdot G_1$
验证复杂度为 k + 3 个标量乘（倍点运算）；if k = 1，则一共 4 个标量乘。
使用归一化技术进一步降低复杂度
计算并发送 1 个辅助多项式的商多项式承诺 $W_2$
$$ W_2 = \frac{L(\alpha)}{Z_{T/S_1}(z) \cdot (\alpha - z)} \cdot G_1 $$
验证 S 个随机点：基于 transcript 计算随机数 $\gamma$，如果以下等式成立，则接受，否则拒绝
$$ e(F + z \cdot W_2, G_2) = e(W_2, \alpha \cdot G_2) $$
其中，$F=\frac{-Z_T(z)}{Z_{T/S_1}(z)} \cdot W_1 + \sum_{i \in [k]} \gamma^{i-1} \frac{Z_{T/S_i}(z)}{Z_{T/S_1}(z)} \cdot C_i - \sum_{i \in [k]} \gamma ^{i-1} \cdot \frac{Z_{T/S_i}(z)}{Z_{T/S_1}(z)} \cdot r_i(z) \cdot G_1$
if k = 1，then $F=\frac{-Z_T(z)}{Z_{T/S_1}(z)} \cdot W_1 + C_i - r_i(z) \cdot G_1$，仅有 3 个倍点运算，计算复杂度最低。
但是一般 $k > 1$，解决方案：Fflonk 将多个多项式单点打开等价转化为 1 个多项式多点打开，即 $k=1$。
Fflonk 多个多项式的组合
核心思想：$n$ 个相对简单的多项式 $f_1, ..., f_n$ 与 1 个相对复杂的多项式 $g$ 能够等价表达。
以两个多项式 $f_0,f_1$ 举例，希望在 $x$ 处揭示这两个多项式。主要思想是快速傅氏变换 FFT，构造一个多项式
$f(X) = f_0(X^2) + X \cdot f_1(X^2)$，这里需要反向利用这个等式，从右到左，利用 $f_0,f_1$ 构造 $f$
符号定义
- $F$ 是阶为素数 $p$ 的域
- $[<t]$ 表示非负整数集合 $\left\{0,...,t-1 \right\}$
- $F_{<d}[X]$ 是度小于 $d$ 的单变量多项式集合
- $f \in F_{<d}[X]$ 是度小于 $d$ 的单变量多项式
- $D^{(i)}$ : $D$ 为某一域，$i$ 表示嵌套层数，比如 $D^{(1)}$ 表示域 $D$ 上的向量集合，$D^{(2)}=(D^{1})^{(1)}$ 表示向量的向量构成的集合，依次类推
- $\bar{S} \in F^{(1)}$ 表示元素 $\bar{S}$ （是一个向量）来自有限域向量 $F^{(1)}$，同理 $\bar{\bar{S}}$ 来自向量的有限域向量 $F^{(2)}$
- $\bar{f} \in D^t$ 表示长度为 $t$ 的向量，元素 $f_i \in D, i \in [0,t]$，同理 $\bar{\bar{f}} \in D^{(2)}$ 表示向量的向量，每个向量都来自 $D^{(1)}$
- $\bar{f}(x) = (f_0(x), ..., f_{t-1}(x))$，其中 $\bar{f} \in F[X]^t$ 为多项式向量，$X=x \in F$
- $\bar{f}(\bar{Z}) \in F^{(2)}$：对于向量 $\bar{f}$ 确定的多项式和一个点集向量 $\bar{Z} \in F^l$，$\bar{f}(\bar{Z})=(\bar{f}(Z_j))_{j<l}$，大小为 $t \cdot l$
多项式的组合与分解
定义：$t$ 个多项式的组合 $combine_t(\bar{f}): F[X]^t \rightarrow F[X]$
具体映射：$t$ 个多项式 $f_i(X), i \in [1,t]$ 组合为一个多项式
$$ g(X) = \sum_{i<t}f_i(X^t) \cdot X^i $$
定义：一个多项式的分解 $decompose_t(g): F[X] \rightarrow F[X]^t$
具体映射：一个多项式分解为 $t$ 个多项式
$t$ 个多项式组合为一个多项式，可再分解为 $t$ 个多项式
$$ decompose_t(combine_t(\bar{f})) == \bar{f} $$
定义
$p=|F|$ 表示域的大小，对于正整数 $t | (p-1)$，令 $\omega_t \in F$ 为 $t$ 次单位根，即对任意 $i < t$，存在 $\omega_t^t=1, \omega_t^i \ne 1$。
对于 $z, x \in F$，满足 $z^t=x, z^i \ne x, i < t$，则称 $z$ 为最小整数表达。
定义向量 $root_s(x)=(z \omega_t^i)_{i<t}$
对于向量 $v \in F^t$ 和点 $x \in F$，多项式求值表示为 $v(x)=\sum_iv_i \cdot x^i$，多项式在点集 $S \in F^{(1)}$ 上的求值表示为 $v(S)=(v(x))_{x \in S}$
定理
对于任意 $x \in F, \bar{S} \in F^t, \bar{f} \in F[X]^t$，定义 $\bar{Z} = roots_t(x), g=combine_t(\bar{f}), \bar{S}' = \bar{S}(\bar{Z})$
以下 2 个条件等价：
- $t$ 个多项式 $\bar{f}(x)$ 在 1 个点 $x$ 处求值
- 1 个多项式 $g(x)$ 在 $t$ 个点 $\bar{Z}$ 处求值
$$ g(\bar{Z})=\bar{S}' \iff \bar{f}(x) = \bar{S} $$
证明：对于 $z \in \bar{Z}$（从 $t$ 个值中随便挑一个），有
$$ g(z) = \sum_{i<t}z^i \cdot f_i(z^t) = \sum_{i<t}z^i \cdot f_i(x) = (z) \cdot \bar{f}(x) $$
将 $z$ 替换为 $\bar{Z}$，则有 $g(\bar{Z})=(\bar{Z}) \cdot \bar{f}(x)$ （任意一个元素相等，则集合中每个元素都相等）
因为 $g(\bar{Z})=\bar{S}'$，所以 $\bar{S}'=(\bar{Z}) \cdot \bar{f}(x)$
因为 $\bar{S}' = \bar{S}(\bar{Z})$，所以 $\bar{S}(\bar{Z})=(\bar{Z}) \cdot \bar{f}(x)$，所以 $\bar{f}(x)=\bar{S}$
结论
$n$ 个多项式 1 点打开（有 $n$ 个值）可等价转化为 1 个多项式 $n$ 点打开（有 $n$ 个值）
$$ g(X) = \sum_{i<t}f_i(X^t) \cdot X^i $$
是满射关系，数据量不会有任何损失
一般化 1：$n$ 个多项式 $m$ 点打开可等价转化为 1 个多项式 $n \cdot m$ 点打开
一般化 2：
- $n_1$ 个多项式 $m_1$ 个点打开
- $n_2$ 个多项式 $m_2$ 个点打开
- $n_3$ 个多项式 $m_3$ 个点打开
等价转化为 1 个多项式 $(n_1+n_2+n_3) \cdot (m_1+m_2+m_3)$ 点打开
Plonk 证明系统
电路化：门约束和线约束
电路化：将任意算法等价转换为多项式。
例子：任意一个多项式时间算法 $P(x) = x^3 + x + 5 = 35$，求解 $x$
使用电路对 $P(x)$ 进行图 1 所示表达，然后如图 2 所示为元器件和导线添加下标：
对于 Grouth16，基于 R1CS 电路约束构造多项式 $a \cdot b = c$，可以表达比较复杂的多项式，如
$$ (a_1 + ...,+a_{1000}) \cdot (b_1+...b_{200}) = (c_1 +...+c_{10}) $$
而对于 Plonk，基于门约束和线约束构造多项式，门只能表达单一的加法或乘法：
$$ \begin{align} &a \cdot b = c \\ & a + b = c \end{align} $$
Plonk 门的约束力不够，还需要线约束（对数据信号的相等的约束），如 $c_1=a_2,c_2=b_3,c_3=a_5$
R1CS 表达能力强，Plonk 门表达能力弱。R1CS 电路门为 $n$ 个，而 Plonk 门通常为 $8n$ 到 $12n$ 个。
门约束
创建一个通用方程
$$ Q_{A_i} \cdot a_i + Q_{B_i} \cdot b_i + Q_{C_i} \cdot c_i + Q_{M_i} \cdot a_i \cdot b_i + Q_{Const_i} = 0 $$
方程组中的系数 $Q_{L_i}, Q_{R_i},Q_{O_i}, Q_{M_i}, Q_{C_i}$ 取特定的的值，例如 0, 1, -1，则能表达特定的加法门、乘法门等。
为了减少方程的个数，可求出 $Q_{L_i}, Q_{R_i},Q_{O_i}, Q_{M_i}, Q_{C_i}$ 的多项式表达。
例如
$$ \begin{align} & 2x_1 - x_2 + 3x_3 - 8 = 0\\ & x_1 + 4x_3 - 5x_3 - 5 = 0\\ & 8x_1 - x_2 - x_3 + 2 = 0 \end{align} $$
横坐标索引 $x=(0,1,2)$，纵坐标分别为
$$ Q_A=(2,1,8), Q_B=(-1,4,-1),Q_C=(3,-5,-1), Q_{Const}=(-8,-5,2) $$
因此可以使用 FFT 算出 $Q_A(x),Q_B(x),Q_C(x),Q_{Const}(x)$
从而得到一个多项式方程
$$ \begin{align} &Q_A(x) \cdot x_1 + Q_B(x) \cdot x_2 + Q_C(x) \cdot x_3 + Q_{Const} = 0,\\ &x=(0,1,2) \end{align} $$
上述约束系统中，$x_1,x_2,x_3$ 在每个方程中是相同的，如果在每个方程中不同，可令 $x_1=(a_1,a_2,a_3),x_2=(b_1,b_2,b_3),x_3=(c_1,c_2,c_3)$，则线性方程变为
$$ \begin{align} & 2a_1 - b_1 + 3c_1 - 8 = 0\\ & a_2 + 4b_2 - 5c_2 - 5 = 0\\ & 8a_3 - b_3 - c_3 + 2 = 0 \end{align} $$
横坐标为 $x=(0,1,2)$，纵坐标分别为 $(a_1,a_2,a_3),(b_1,b_2,b_3),(c_1,c_2,c_3)$，则可得到 3 个多项式 $a(x),b(x),c(x)$，从而得到一般化的多项式约束系统
$$ \begin{align} &Q_A(x) \cdot a(x) + Q_B(x) \cdot b(x) + Q_C(x) \cdot c(x) + + Q_M(x) \cdot a(x) \cdot b(x) + Q_{Const} = 0,\\ &x=(0,1,2) \end{align} $$
- 电路多项式 $Q_A(x),Q_B(x),Q_C(x),Q_M(x),Q_{Const}(x)$
- 数据多项式 $a(x),b(x),c(x)$
因此，完成了线性运算系统到多项式约束系统的转换。
另外，基于横坐标 $x=(0,1,2)$，可构造出一个公开的目标多项式 $Z(x)=(x-0)(x-1)(x-2)$，有
$$ Q_A(x) \cdot a(x) + Q_B(x) \cdot b(x) + Q_C(x) \cdot c(x) + + Q_M(x) \cdot a(x) \cdot b(x) + Q_{Const} = Z(x) \cdot H(x) $$
大数范围内线约束
使用坐标对累加器表达信号在同一条导线之间的处处相等。
在同一条导线上信号处处相等，则两个相等的信号在运算上是可以进行置换的，所以线约束也称为置换约束。
核心概念：坐标对累加器
给定多项式 $P(x)$ 的值表达，横坐标 $x=(0,1,2,3)$，纵坐标 $y=(-2,1,0,1)$
可使用 FFT 算出 $x$ 的系数表达 $X(x)=x$，$y$ 的系数表达 $Y(x)=x^3-5x^2+7x-2$
定义坐标对累加器 $P(x)$ 递归表达
$$ \begin{align} & P(n+1)=P(n) \cdot (u + X(n) + v \cdot Y(n)) \\ & P(0) = 1\\ & n=0,1,2,... \end{align} $$
其中，$u,v$ 是两个随机常量。
将上式展开后，可推出累机器的通用表达
$$ P(n)=\prod_{i=0}^{n-1}(u+X(i) + v \cdot Y(i)) $$
对于本例，可以得到 $P(4) = (u+x_0+v \cdot y_0)\cdot(u+x_1+v \cdot y_1) \cdot (u+x_2+v \cdot y_2) \cdot (u+x_3+v \cdot y_3)$
关键结论：
- 如果横坐标索引 $x_i,x_j$ 互换，如果对应纵坐标 $y_i=y_j$，则对应的坐标对累加器的函数值不变 $P(n)=P(n)'$，其中 $n=max \left\{i,j\right\} + 1$
例如，如果 $x_1,x_3$ 互换，如果 $y_1=y_3$，则 $P(4)=P(4)'$
- 反之，如果横坐标索引 $x_i,x_j$ 互换，如果坐标对累加器的函数值相等 $P(n)=P(n)'$，则两个纵坐标 $y_i=y_j$ 相等，确保线约束成立。
证明：将 $x_1,x_3$ 互换，且 $P(4)=P(4)'$，则
$$ (u+x_0+v \cdot y_0)\cdot(u+x_1+v \cdot y_1) \cdot (u+x_2+v \cdot y_2) \cdot (u+x_3+v \cdot y_3) \\ =\\ (u+x_0+v \cdot y_0)\cdot(u+x_3+v \cdot y_1) \cdot (u+x_2+v \cdot y_2) \cdot (u+x_1+v \cdot y_3) $$
由于 $u,v$ 为随机数，根据 Schwartz-Zippel 引理和乘积一致性定理，只可能有如下 2 种情况：
情况 1：
$$ u+x_1+v\cdot y_1=u+x_3+v \cdot y_1\\ u+x_3+v\cdot y_1=u+x_1+v \cdot y_1 $$
不可能成立，因为索引 $x_1,x_3$ 是不同的值
情况 2：
$$ u+x_1+v\cdot y_1=u+x_1+v \cdot y_3\\ u+x_3+v\cdot y_3=u+x_3+v \cdot y_1 $$
化简后得到 $y_1=y_3$，成立
将 1 条导线上的线约束扩展为 3 条导线上的线约束，则三条导线 $a,b,c$ 的横坐标分别为 $X_a=(0,1,2,3),X_b=(4,5,6,7),X_c(8,9,10,11)$，对应的纵坐标为 $a=(a_0,a_1,a_2,a_3),b=(b_0,b_1,b_2,b_3),c=(c_0,c_1,c_2,c_3)$
证明方：证明 $a_2=b_3$，则生成坐标值累加器 $P_a(3),P_a(4)',P_b(3),P_b(4)'$
验证方：验证 $P_a(3)\cdot P_b(4)=P_a(3)' \cdot P_b(4)'$
实际应用中，为提高变换速度，使用快速傅立叶变换 FFT。横坐标不再使用数字索引 0, 1, 2, ..., n-1，而应该使用 n 次单位根 $\omega^n = 1$。对于 n 次单位根，有如下重要等式
$$ Z(X)=(x- \omega^0)(x- \omega^1)(x- \omega^2)...(x- \omega^{n-1})=x^n-1=0 $$
坐标值累加器对应修改如下
$$ P(\omega^n)= \prod_{i=0}^{n-1}(u + X(\omega^i) + v \cdot Y(\omega^i)) $$
约束汇总
门约束
三端口数据 $a(x),b(x),c(x)$ 多项式的门约束系统：
$$ \begin{align} & Q_A(x) \cdot a(x) + Q_B(x) \cdot b(x) + Q_C(x) \cdot c(x) + Q_M(x) \cdot a(x) \cdot b(x) + Q_{Const} = Z(x) \cdot H(x) \\ & x=\omega^0, \omega^1,..., \omega^{n-1} \end{align} $$
线约束
门和门之间的连线正确。确保累加计算在 X 编号变化前后的计算正确
$$ \begin{align} & P_a(\omega x) - P_a(x)(u + x + va(x)) = Z(x)H_1(x)\\ & P_{a}'(\omega x) - P_{a}'(x)(u + \sigma_a(x) + va(x)) = Z(x)H_2(x)\\ & P_b(\omega x) - P_b(x)(u + gx + vb(x)) = Z(x)H_3(x)\\ & P_{b}'(\omega x) - P_b'(x)(u + \sigma_bx + vb(x)) = Z(x)H_4(x)\\ & P_c(\omega x) - P_c(x)(u + g^2x + vc(x)) = Z(x)H_5(x)\\ & P_{c}'(\omega x) - P_c'(x)(u + \sigma_cx + vc(x)) = Z(x)H_6(x)\\ & x=\omega^0, \omega^1,..., \omega^{n-1} \end{align} $$
$P_a(\omega x) - P_a(x)(u + x + va(x)) = Z(x)H_1(x)$ 表示某一行数据 a 管脚与下一行数据 a 管脚信号相等，即有一条导线连接。
起始约束和结束约束
$$ \begin{align} & P_a(1) = P_b(1)=P_c(1)=P_a'(1)=P_b'(1)=P_c'(1)=1 \\ & P_a(\omega^n) P_b(\omega^n)P_c(\omega^n)=P_a'(\omega^n)P_b'(\omega^n)P_c'(\omega^n) \\ \end{align} $$
Plonk 证明系统
乘法群上的线约束
阶为 $n$ 的群 G，生成元为 $G$。$\left\{L_i\right\}_{i \in [n]}$ 是群 G 上的拉格朗日基
$$ \begin{align} & L_i(j \cdot G) = 1, i = j \\ & L_i(j \cdot G) = 0, i \ne j \end{align} $$
对于 $f, g \in F_{<n}[X]$，置换 $\sigma: [n] \rightarrow [n], i \cdot G \in $ G，$i = 1,..., n$
记为 $g = \sigma(f)$
$$ \begin{align} & index = i \cdot G \\ & index' = \sigma(i) \cdot G \\ & g(i \cdot G) = f(\sigma(i) \cdot G) \end{align} $$
多项式预处理：（双方都知道导线多项式的值）在域 $F_{<n}[X]$ 上的多项式 $S_{ID}(g^i)=i, S_{\sigma}(g^i)=\sigma(i), i \in [n]$
输入多项式：（证明方知道保密数据多项式）$f,g \in F_{<n}[X]$
验证方：选择并发送随机数 $\beta, \gamma$
证明方：多项式 $f'(i \cdot G) = f(i \cdot G) + \beta \cdot i + \gamma, g'(i \cdot G)=g(i \cdot G) + \beta \cdot \sigma(i) + \gamma$，计算
$$ Z(i \cdot G) = \prod_{1 \le j \le i} \frac{f'(i \cdot G)}{g'(i \cdot G)}, i=2,...,n $$
其中，$Z(G)=1$。发送坐标对累加器的值 $Z$
验证方：对于所有 $a \in G$，即 $a= i \cdot G, i=1,2,...,n$
$$ \begin{align} &L_1(a)(Z(a)-1)=0\\ &Z(a)f'(a)=g'(a)Z(a \cdot G) \end{align} $$
推导：
如果 $a=1 \cdot G$，则 $L_1(1 \cdot G)=1$，则
$$ L_1(G)(Z(G)-1)=0 \rightarrow Z(G)=1 $$
如果 $a=i \cdot G, i=2,...,n$，则
$$ L_1(i \cdot G)=0 $$
所以 $L_1(a)(Z(a)-1)=0$ 成立。
群的阶为 $n$，则 $G=(n+1)\cdot G$，所以
$$ \begin{align} 1&=Z(G)=Z((n+1)\cdot G)=Z(n \cdot G)\frac{f'(n \cdot G)}{g'(n \cdot G)}\\ &=...\\ &=\prod_{i=1}^i\frac{f(i \cdot G) + \beta \cdot i + \gamma}{g(i \cdot G) + \beta \cdot \sigma(i) + \gamma} \end{align} $$
说明横坐标 index 为 $i$ 的函数值 $g(i \cdot G)$ 等于横坐标 index 为 $\sigma(i)$ 的函数值 $f(\sigma(i) \cdot G)$
$$ g(i \cdot G) = f(\sigma(i) \cdot G) $$
所以满足置换关系 $g=\sigma(f)$，实现线约束。
Plonk 核心协议
核心协议
本节涉及的公式较多，省略，详见：zkSnark--Plonk证明系统（P4）
符号表达
$g_1,g_2$ 分别是群 $G_1,G_2$ 的生成元，如下式子表示倍点运算
$[g]_1 = [g(\chi)]_1 = [g(X)] \cdot g_1 \in G_1$
$[g]_2 = [g(\chi)]_2 = [g(X)] \cdot g_2 \in G_1$
公共预处理信息
- 系统初始化 $(PK1, VK1)=(\chi \cdot [1]_1,...\chi^{n+5} \cdot [1]_1)$，其中 $\chi$ 是有毒废料
- 门多项式 $Q_L(x), Q_R(x), Q_M(x), Q_O(x), Q_C(x)$
- 线多项式 $S_{\sigma1(x)}, S_{\sigma2(x)}, S_{\sigma3(x)}$
证明过程
- Round1: 计算门数据多项式 $a(x),b(x),c(x)$，并输出承诺 $[a]_1, [b]_1, [c]_1$
- Round2: 计算线数据多项式 $z(x)$（会用到坐标累加器），并输出承诺 $[z]_1$
- Round3: 确保门约束和线约束成立。将门多项式、门数据多项式、线多项式、线数据多项式融合到一个多项式 $f(x)$ 中，然后除以目标多项式 $Z_H(x)$ 得到商多项式 $t(x)$，并输出承诺。因为 $t(x)$ 的阶较高，超出了 $2^{256}$，无法对多项式进行承诺，所以拆分成 3 项（例如，将 $x+x^2+x^3$ 拆成 $x,\chi \cdot x,\chi^2 \cdot x$)，并输出 3 个多项式承诺 $[t_{lo}]_1,[t_{mid}]_1,[t_{hi}]_1$
- Round4: 计算多项式 $r(x)=f(x) - Z_H(x)t(x)$ 的随机打开点 $\bar{r}$。因为 $r(x)$ 的阶比较高，所以中间还用到了一些多项式值 $\bar{a}, \bar{b}, \bar{c}, \bar{S_{\sigma_1}}, \bar{S_{\sigma_2}}, \bar{z_{\omega}}$，这些值也要被公开
- Round5: 计算商多项式 $W_{\xi}(x),W_{\omega\xi}(x)$，其中 $W_{\xi}(x)$ 确保 $t(x),r(x),a(x),b(x),c(x),S_{\sigma_1}(x), S_{\sigma_2}(x)$ 正确，$W_{\omega\xi}(x)$ 确保 $z(x)$ 正确，并输出商多项式承诺 $[W_{\xi}]_1,[W_{\omega\xi}]_1$
最终发送数据
$$ \pi_{SNARK} = \begin{pmatrix} [a]_1, [b]_1, [c]_1, [z]_1, [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1, [W_{\xi}]_1, [W_{\omega \xi}]_1,\\ \bar{a}, \bar{b}, \bar{c}, \bar{S_{\sigma1}}, \bar{S_{\sigma2}}, \bar{z_{\omega}} \end{pmatrix} $$
验证 VK
验证 VK 预习存储到以太坊一层合约
$$ [Q_M]_1,[Q_A]_1,[Q_B]_1,[Q_C]_1,[S_{\sigma_1}]_1,[S_{\sigma_2}]_1,[S_{\sigma_3}]_1,[\chi]_1 $$
其中 $[\chi]_1$ 是 VK1，其余是 VK2
验证过程
检查群元素合法性 $[a]_1,[b]_1,[c]_1,[z]_1,[t_{lo}]_1,[t_{mid}]_1,[t_{hi}]_1,[W_{\xi}]_1,[W_{\omega\xi}]_1 \in G_1^9$
函数值范围检测 $\bar{a},\bar{b},\bar{c},\bar{S_{\sigma_1}},\bar{S_{\sigma_2}},\bar{z_{\omega}} \in F_p^6$
L 个公共输入范围检测 $(w_i){i \in [l]} \in F_p^l$
基于多项式承诺计算随机数 $v$ 等
计算多项式 $r(x)$ 函数值的承诺 $[D]_1$（优化见下一节）。因为 $r(x)$ 阶较高，无法直接计算承诺，所以中间还用到了一个辅助多项式。
计算多项式承诺的线性组合：
$$ [F]_1 = [D_1] + v \cdot [a]_1 + v^2 \cdot [b]_1 + v^3 \cdot [c]_1 + v^4 \cdot [S_{\sigma1}]_1 + v^5 \cdot [S_{\sigma2}]_1 $$
计算函数值的承诺：
$$ [E]_1 = [-r_0 + v\bar{a} + v^2\bar{b} + v^3\bar{c} + v^4\bar{S_{\sigma1}} + v^5\bar{S_{\sigma2}} + u\bar{z_{\omega})}]_1 $$
基于双线性进行验证
$$ e([W_{\xi}]_1 + u \cdot [W_{\omega\xi}]_1, \space [\chi]_2) = e(\xi \cdot [W_{\xi}]_1 + u \xi \omega \cdot [W_{\omega\xi}]_1 + [F]_1 - [E]_1, \space [1]_2) $$
如果通过，说明前面的打开点正确，说明商多项式 $W_{\xi}(x),W_{\omega\xi}(x)$ 正确，说明 $t(x)$ 正确，说明门约束和线约束成立。
Plonk 的优化
情况 1：KZG 承诺
- 多个多项式、多点打开：绿色下划线是群 $G_1$ 上的 18 个倍点运算
情况 2：Dan 承诺
- 与打开点数无关，所以第 12 步的黄色部分合并，共 16 个倍点运算
情况3：Fflonk + Dan 承诺
- Fflonk 组合：n 个多项式 1 个打开点组合为 1 个多项式 n 个打开点
- Dan 承诺：第 9 步减少为 2 个倍点运算，再加上第 12 步的 3 个倍点运算，一共 5 个倍点运算
聚合证明
多个算法 $Algo_i$ 对应多个电路 $Circuit_i$ 和 $VK_i$，如果把所有 $VK_i$ 都存下来，代价较大。
可以将 Plonk 验证算法电路 $Circuit_0$ 存下来，只需要将 $VK_0$ 存到以太坊一层。
证明方：基于验证电路 $Circuit_0$，将多组 $(Proof_i,VK_i)_{i\in[1,n]}$ 聚合起来，生成一个 $Proof_0$
验证方：如果 $(Proof_0, VK_0)$ 正确，则说明多组 $(Proof_i,VK_i)_{i\in[1,n]}$ 都正确。
关键点 1：Plonk 验证算法包含一个双线性映射
在电路上表达双线性映射原理，涉及 millier-loop。循环次数取决于计算出来的随机数，而不是固定值。
解决：只验证固定部分，不严重双线性映射。将多个双线性映射耦合到 $Proof_0$ 中。
关键点 2：取值范围
Bn256 曲线的标量域小于基域。椭圆曲线点的取值范围是基域，而电路上的随机数取值范围是标量域，所以会有大量检测。
解决：基域和标量域之间的进制转换，使用 2 个标量域表达 1 个基域。
任意 for 循环的电路约束
任意 for 循环，循环次数不一样，则对应的 $Circuit_1$ 会变化，对应的 $VK_1$ 会变化，无法提前存到以太坊一层合约中。
解决：聚合证明
将 $Proof_1, VK_1$ 作为数据，输入到验证电路 $Circuit_2$ 中，它只表达 plonk 验证算法的固定部分，则对应的 $VK_2$ 是固定的，所以可以将 $VK_2$ 存到以太坊一层合约。
只有一条评论 (QwQ)
怎么收藏这篇文章？