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 所示为元器件和导线添加下标：

50.png

对于 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 的优化

51.png

情况 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$ 存到以太坊一层合约。

参考

zkSnark--Plonk证明系统（P1）

zkSnark--Plonk证明系统（P2）

zkSnark--Plonk证明系统（P3）

zkSnark--Plonk证明系统（P4）

FFlonk算法

PLONK 理解