Plonk零知识证明方案

作者: 雪落无留痕 | 来源:发表于2021-04-22 23:18 被阅读0次

Plonk零知识证明方案
Mina Kimchi
2018.4.21清华学习笔记
Filecoin白皮书分析
StarkNet
Plonky2 简介
零知识证明
零知识证明
零知识证明
零知识证明

Plonk 于2019年由Aztec研究团队提出，和zk-SNARK相比，增强的优势主要有：

（1）通用性，即可信设置与应用无关，仅需要一次可信设置，可以满足所有（电路门数在一定限制内，目前zksync电路门数在 2^20 ~ 2^26之间）的应用；

（2）可更新： setup参数可以任意更新，只要有一个可信参与者，即可保证可信设置的安全性。

原理介绍

Plonk约束系统

与Groth16中采用的R1CS不同，Plonk约束系统的数学表达式为：

$Q_{L_i}\cdot a_i + Q_{R_i}\cdot b_i + Q_{O_i}\cdot c_i + Q_{d_i}\cdot d_i + Q_{M_i}\cdot a_i\cdot b_i + Q_{C_i} = 0$
其中 $L$ 代表左边， $R$ 代表右边， $O$ 代表输出， $M$ 代表乘法， $C$ 代表常量， $a_i$ 代表左输入， $b_i$ 代表右输入， $c_i$ 代表电路输出， $i$ 代表第 $i$ 个门电路。

多项式转换

类似STARKS或QAPs, 可以利用多项式转换将多个约束融合进一个多项式中，可以大幅减化零知识证明验证。利用Lagrange插值或FFT变换，将上述步骤中的电路转化为多项式形式，即

$Q_{L}(x)\cdot a(x) + Q_{R}(x)\cdot b(x) + Q_{O}(x)\cdot c(x) + Q_{d}(x)\cdot d(x) + Q_{M}(x)\cdot a(x)\cdot b(x) + Q_{C}(x) = 0$
其中 $Q_L, Q_R, Q_O, Q_C$ 为选择多项式。

复制约束

上述的约束系统只是单独对每个电路进行约束，对于电路与电路之间的相互约束无法实现，例如如下述电路中，要约束 $c_1 = a_2$ ，就需要复制约束（copy constraints)。

Vitalik通过对坐标累加器实例对复制约束作了介绍，例如对于坐标上的点 $(0, -2) , (1,1), (2,0),(3,1)$

设定 $X(x)= x$ , $Y(x) = x^3 - 5x^2 + 7x -2$ ，定义坐标累加器为：
$P(x+1) = P(x)(v_1 + X(x) + v_2Y(x))$
其中 $P(0) = 1$ , $v_1 = 3$ , $v_2=2$ , 可以得到 $P(4) = -240$ 。

$X(x)$	0	1	2	3	4
$Y(x)$	-2	1	0	1
$v_1+X(x)+v_2Y(x)$	-1	6	5	8
$P(x)$	1	-1	-6	-30	-240

同理对于点： $(0, -2) , (3,1), (2,0),(1,1)$ ，则 $X'(x) = (2/3) x^3-4x^2 + (19/3)x$ , $Y'(x) = x^3 - 5x^2+7x-2$ , 同样可以得到 $P'(4) = -240$ 。

$X'(x)$	0	3	2	1	4
$Y'(x)$	-2	1	0	1
$v_1+X'(x)+v_2Y'(x)$	-1	8	5	6
$P'(x)$	1	-1	-8	-40	-240

$P(4) = P'(4)$ 的原因为 $Y(1)= Y(3)$ 。

上述性质可以推广到跨 $a, b, c$ 集合的复制约束，即对于 $a(x),b(x),c(x)$ 的复制约束，需要保证：

$P_a(n)\cdot P_b(n)\cdot P_c(n) = P'_a(n)\cdot P'_b(n)\cdot P'_c(n)$

例如对于某个电路的输出 $x_{c1}$ ，又作为某些电路的输入 $x_{a2}, x_{a3}, x_{b3}$ , 其中 $x_i$ 代表索引值， $a_i$ 或 $\omega_i$ 电路的值。

生成置换： $\sigma(x_{c1}) = x_{a2},\sigma(x_{a2}) = x_{a3},\sigma(x_{a3}) = x_{b3},\sigma(x_{b3}) = x_{c1}$

为了保证满足复制约束，需要检查：
$(a_1, \cdots, a_n, b_1, \cdots, b_n, c_1, \cdots, c_n) = （\omega_{\sigma(x_{a1})}, \cdots, \omega_{\sigma(x_{an})}, \omega_{\sigma(x_{b1})},\cdots,\omega_{\sigma(x_{bn})}, \omega_{\sigma(x_{c1})},\cdots, \omega_{\sigma(x_{cn})}）$

Plonk证明

检查门电路约束
$Q_L(x)a(x) + Q_R(x)b(x) + Q_O(x)c(x) + Q_M(x)a(x)b(x) + Q_c(x)=Z(x)H(x)$
其中： $Z(x) = (x-1)(x-\omega)\cdot\cdot\cdot(x-\omega^{n-1})$
检查复制约束
$P_a(\omega x)-P_a(x)(v_1 + x + v_2a(x)) = Z(x)H_1(x) \\ P'_a(\omega x)-P'_a(x)(v_1 + \sigma_a(x) + v_2a(x)) = Z(x)H_2(x) \\ P_b(\omega x)-P_b(x)(v_1 + x + v_2b(x)) = Z(x)H_3(x) \\ P'_b(\omega x)-P'_b(x)(v_1 + \sigma_b(x) + v_2b(x)) = Z(x)H_4(x) \\ P_c(\omega x)-P_c(x)(v_1 + x + v_2c(x)) = Z(x)H_5(x) \\ P'_c(\omega x)-P'_c(x)(v_1 + \sigma_c(x) + v_2c(x)) = Z(x)H_6(x) \\$
多项式边界条件为：
$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)$
与应用相关的输入：
- $Q_L(x), Q_R(x), Q_O(x), Q_M(x), Q_C(x)$ ，其中 $Q_C(x)$ 为编码公开输入，需要在运行时计算。
- 置换多项式： $\sigma_a(x), \sigma_b(x), \sigma_c(x)$
用户提供的输入：
- 电路的输入赋值： $a(x), b(x), c(x)$
- 坐标累加器: $P_a(x), P_b(x), P_c(x), P'_a(x), P'_b(x), P'_c(x)$
- 商多项式： $H(x), H_1(x), \cdot\cdot\cdot, H_6(x)$

Plonk协议

置换协议

对于两个长度为 $n$ 的序列 $(f_1, f_2, \cdots, f_n)$ 和 $(g_1, g_2, \cdots, g_n)$ , 证明者要证明 $g_i = f_{\sigma(i)}$ , $1\leq i \leq n$ , $\sigma$ 为某个置换，协议过程如下：

验证者发送随机值 $\beta, \gamma \in \mathbb{F}$ 给证明者；
证明者构造两个新的序列： $(f_1, f_2, \cdots, f_n)$ 和 $(g_1, g_2, \cdots, g_n)$ , 其中
$f_i = f_i + \beta\cdot i + \gamma \\ g_i = g_i + \beta \cdot \sigma(i) + \gamma$
证明者计算新的序列 $s_i$ , 其中
$s_0=1, s_i= s_{i-1}\cdot \frac{f_i}{g_i}$
即
$s_i = \frac{\prod_{1\leq j\leq i}f_j}{\prod_{1\leq j \leq i}g_j}$
$s_i$ 即为所谓的grand product。

证明者将 ${s_i}$ 序列发给验证者。
验证者检查以下方程：
$\hat{s}(w^n) = s_0 = 1 \\ \hat{s}(w^i)\cdot g_i=\hat{s}(w^{i-1})\cdot f_i$
其中 $w^i$ 表示单位元的根， $\hat{s}$ 表示对序列 $s_i$ 的多项式插值。

若验证通过，则验证者确信 $g_i= f_{\sigma(i)}$ 成立， $1\leq i \leq n$ 。

多项式承诺

多项式承诺是plonk证明过程中采用的一个基本工具，在不泄露多项式 $f(x)$ 的情况下，使验证者确信对于某个 $z$ , $f(z)$ 是正确的计算结果。

(1) 首先需要计算多项式承诺，为 $f(s)·G_1$ ，其中 $s$ 为可信设置密秘选取的值， $G$ 为椭圆曲线基点；

(2) 为了验证f(z)，证明者需要计算：

$Q(x) = [f(x) -f(z)] / (x - z)$

然后将 $Q(x), f(z)$ 的承诺发给验证者；

(3) 验证者通过双线性对进行验证：
$e(f(x)·G_1 - G_1·f(z), G_2) = e(Q(x)·G_1, x·G_2 - G_2 ·z)$

$e(f(x)·G_1 - G_1·f(z), G_2) = e(G_1, G_2)^{(f(x) - f(z))}$

$e(Q(x)·G1, x·G_2 - G_2 ·z) = e(G_1, G_2)^{(x - z)*Q(x)}$

Plonk协议

证明约束
$\mathbb{R}_{snark(\lambda)}= \begin{Bmatrix} (x,w,crs)=((w_i)_{i\in [l]},((w_i)_{i=1,i\notin[l]}^{3n}), \\ (q_{M_i}, q_{L_i}, q_{R_i}, q_{O_i})_{i=1}^{n}, n, \sigma(x)) \\ for\ all\ i\in \{1,\cdots, 3n\}: w_i\in \mathbb{F}_p \\ for\ all\ i\in \{1,\cdots,n\}: w_i w_{n+i}q_{M_i}+w_iq_{L_i}+w_{n+i}q_{R_i}+w_{2n+i}q_{O_i}+q_{C_i}=0 \\ for\ all\ i\in \{1,\cdots, 3n\}: w_i = w_{\sigma(i)} \end{Bmatrix} \\$
预处理输入

$n, (x\cdot[1]_1, \cdots, x^{n+5}\cdot[1]_1), (q_{M_i},q_{L_i}, q_{R_i}, q_{O_i}, q_{C_i})_{i=1}^n, \sigma(X), \\ q_M(X)=\sum_{i=1}^n q_{M_i}L_i(X), \\ q_L(X) = \sum_{i=1}^n q_{L_i}L_i(X), \\ q_R(X)=\sum_{i=1}^n q_{R_i}L_i(X), \\ q_O(X)=\sum_{i=1}^n q_{O_i}L_i(X), \\ q_C(X)=\sum_{i=1}^n q_{C_i}L_i(X), \\ S_{\sigma_1}(X)=\sum_{i=1}^n \sigma(i)L_i(X), \\ S_{\sigma_2}(X)=\sum_{i=2}^n \sigma(n+i)L_i(X), \\ S_{\sigma_3}(X)=\sum_{i=3}^n \sigma(2n+i)L_i(X)$

输入数据

公开输入： $l, (w_i)_{i\in [l]}$ , 隐私输入： $(w_i)_{i\in 3n}$
证明过程

证明过程主要分为以下5轮：

（1）

生成随机盲化标量 $(b_i, \cdots, b_9)\in \mathbb{F}_p$

生成多项式 $a(X), b(X), c(X)$ :
$a(X)=(b_1X+b_2)Z_H(X)+\sum_{i=1}^nw_iL_i(X) \\ b(X)=(b_3X+b_4)Z_H(X)+\sum_{i=1}^nw_{n+i}L_i(X) \\ a(X)=(b_5X+b_6)Z_H(X)+\sum_{i=1}^nw_{2n+i}L_i(X)$
计算承诺 $[a]_1:=[a(x)]_1, [b]_1:=[b(x)]_1, [c]_1:=[c(x)]_1$

第1轮的输出为: $([a]_1, [b]_1, [c]_1)$ .

(2)

计算置换挑战 $(\beta, \gamma)\in \mathbb{F}_p$ : $\beta = R(transcript, 0), \gamma = R(transcript, 1)$

计算置换多项式 $Z(X)$ :
$Z(X)=(b_7X^2+b_8X+b_9)Z_H(X)+L_1(X)+ \\ \sum_{i=1}^{n-1}(L_{i+1}(X)\prod_{j=1}^i\frac{(w_j+\beta w^{j-1}+\gamma)(w_{n+j}+\beta k_1w^{j-1}+\gamma)(w_{2n+j}+\beta k_2w^{j-1}+\gamma)}{(w_j+\sigma(j)\beta +\gamma)(w_{n+j}+\sigma(n+j)\beta+\gamma)(w_{2n+j}+\sigma(2n+j)\beta+\gamma)})$
计算 $[z]_1:=[z(x)]_1$

第2轮的输出为: $([z]_1)$

(3) 计算商多项式挑战 $\alpha \in \mathbb{F}_p$ : $\beta = R(transcript)$

计算商多项式 $t(X)$ ：

$t(X)=(a(X)b(X)q_M(x)+a(X)q_L(X)+b(X)q_R(X)+c(X)q_O(X)+PI(X)+q_C(X))\frac{1}{Z_H(X)} \\ + ((a(X)+\beta X+\gamma)(b(X)+\beta k_1X+\gamma)(c(X)+\beta k_2X+\gamma)Z(X))\frac{\alpha}{Z_H(X)} \\ - ((a(X)+\beta S_{\sigma1}(X)+\gamma)(b(X)+\beta S_{\sigma2}(X)+\gamma)(c(X)+\beta S_{\sigma3}(X)+\gamma)Z(Xw))\frac{\alpha}{Z_H(X)} \\ + (Z(X)-1)L_1(X)\frac{\alpha}{Z_H(X)}$

将 $t(X)$ 分割为次数小于 $n$ 的多项式 $t_{lo}(X), t_{mid}(X)$ 和次数小于等于 $n+5$ 的多项式 $t_{hi}(X)$ , 即
$t(X) = t_{lo}(X)+X^nt_{mid}(X)+X^{2n}t_{hi}(X)$
计算 $[t_{lo}]_1:=[t_{lo}(x)]_1, [t_{mid}]_1:=[t_{mid}(x)]_1, [t_{hi}]_1:=[t_{hi}(x)]_1$

第3轮输出为： $([t_{lo}]_1, [t_{mid}]_1,[t_{hi}]_1)$

(4) 计算挑战值 $\xi \in \mathbb{F}_p$ : $\xi = R(transcript)$

计算多项式打开的值：
$\bar{a}=a(\xi), \bar{b} = b(\xi), \bar{c}=c(\xi), \bar{s}_{\sigma1}=S_{\sigma1}(\xi), \bar{s}_{\sigma2}=S_{\sigma2}(\xi), \\ \bar{t} = t(\xi), \bar{z}_w=z(\xi w)$
计算线性多项式 $r(X)$ :
$r(X)= (\bar{a}\bar{b}\cdot q_M(X)+\bar{a}\cdot q_L(X)+\bar{b}\cdot q_{R}(X)+\bar{c}\cdot q_O(X)+q_C(X)) \\ +((\bar{a}+\beta\xi+\gamma)(\bar{b}+\beta k_1\xi+\gamma)(\bar{c}+\beta k_2\xi+\gamma)\cdot Z(X))\alpha \\ - ((\bar{a}+\beta\bar{s}_{\sigma1}+\gamma)(\bar{b}+\beta\bar{s}_{\sigma2}+\gamma)\beta \bar{z}_w\cdot S_{\sigma3}(X))\alpha\\ +(Z(X))L_1(\xi)\alpha^2$
计算线性多项值： $\bar{r}=r(\xi)$

第4轮的输出为： $(\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma1}, \bar{s}_{\sigma2}, \bar{z}_w, \bar{t}, \bar{r})$

(5) 计算挑战值 $v\in \mathbb{F}_p$ ： $v=R(transcript)$

计算打开证明的多项式 $W_{\xi}(X)$ :
$W_{\xi}(X)=\frac{1}{X-\xi}\begin{pmatrix} (t_{lo}(X)+\xi^nt_{mid}(X)+\xi^{2n}t_{hi}(X)-\bar{t}) \\ +v(r(X)-\bar{r}) \\ +v^2(a(X)-\bar{a}) \\ +v^3(b(X)-\bar{b}) \\ +v^4(c(X)-\bar{c}) \\ +v^5(S_{\sigma1}(X)-\bar{s}_{\sigma1}) \\ +v^6(S_{\sigma2}(X)-\bar{s}_{\sigma2}) \end{pmatrix}$
计算打开证明的多项式 $W_{\xi w}(X)$ :
$W_{\xi w}(X)=\frac{(Z(X)-\bar{z}_w)}{X-\xi w}$
计算承诺 $[W_{\xi}]_1:=[W_{\xi}(x)]_1, [W_{\xi w}]_1:=[W_{\xi w}(x)]_1$

第5轮的输出为： $([W_{\xi}]_1, [W_{\xi w}]_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_{\xi w}]_1, \\ \bar{a}, \bar{b},\bar{c},\bar{s}_{\sigma1}, \bar{s}_{\sigma2},\bar{r}, \bar{z}_w \end{pmatrix}$
最后计算多点估值挑战 $u\in \mathbb{F}_p$ : $u=R(transcript)$

生成的证明约为800 Byte.

验证过程

验证者预处理的输入为：
$[q_M]_1:=q_M(x)\cdot[1]_1, [q_L]_1:=q_L(x)\cdot[1]_1,[q_R]_1:=q_R(x)\cdot[1]_1,[q_O]_1:=q_O(x)\cdot[1]_1, \\ [s_{\sigma1}]_1:=S_{\sigma1}(x)\cdot[1]_1, [s_{\sigma2}]_1:=S_{\sigma2}(x)\cdot[1]_1,[s_{\sigma3}]_1:=S_{\sigma3}(x)\cdot[1]_1$
验证密钥约为576 Byte.

验证 $V((w_i)_{i\in [l]}, \pi_{SNARK})$ 的过程如下：

(1) 验证 $([a]_1,[b]_1,[c]_1,[z]_1,[t_{lo}]_1,[t_{mid}]_1,[t_{hi}]_1,[W_z]_1,[W_{zw}]_1)\in \mathbb{G}_1$ ;

(2) 验证 $(\bar{a}, \bar{b},\bar{c}, \bar{s}_{\sigma1},\bar{s}_{\sigma2},\bar{r},\bar{z}_w)\in \mathbb{F}_p^7$ ;

（3) 验证 $(w_i)_{i\in [l]}\in \mathbb{F}_p^l$ ;

(4) 计算挑战值 $\beta, \gamma, \alpha, \xi, v, u\in \mathbb{F}_p$ ;

(5) 计算零值多项式： $Z_{H}(\xi)=\xi^n-1$ ;

(6) 计算拉格朗日多项式： $L_1(\xi)=\frac{\xi^n-1}{n(\xi-1)}$ ;

(7) 计算公开输入多项式: $PI(\xi)=\sum_{i\in l}w_iL_i(\xi)$ ;

(8) 计算商多项式：
$\bar{t}=\frac{\bar{r}+PI(\xi)-((\bar{a}+\beta \bar{s}_{\sigma1}+\gamma)(\bar{b}+\beta \bar{s}_{\sigma2}+\gamma)(\bar{c}+\gamma)\bar{z}_w)\alpha -L_1(\xi)\alpha^2}{Z_H(\xi)}$
（9）计算部分批量多项式承诺： $[D]_1:=v\cdot[r]_1+u\cdot[z]_1$ :
$[D]_1:=\bar{a}\bar{b}v\cdot[q_M]_1+\bar{a}v\cdot[q_L]_1+\bar{b}v\cdot[q_R]_1+\bar{c}v\cdot[q_O]_1+v\cdot[q_C]_1 \\ \qquad\qquad\qquad\qquad + ((\bar{a}+\beta\xi +\gamma)(\bar{b}+\beta k_1 \xi +\gamma)(\bar{c}+\beta k_2\xi+\gamma)\alpha v+L_1(\xi)\alpha^2v+u)\cdot[z]_1 \\ -(\bar{a}+\beta\bar{s}_{\sigma1}+\gamma)(\bar{b}+\beta s_{\sigma2}+\gamma)\alpha v\beta \bar{z}_w[s_{\sigma3}]_1$
（10）计算全部多项式承诺 $[F]_1$ :
$[F]_1:=[t_{lo}]_1+\xi^n\cdot[t_{mid}]_1+\xi^{2n}\cdot[t_{hi}]_1+[D]_1 \\ \qquad\qquad\qquad\qquad\qquad +v^2\cdot[a]_1+v^3\cdot[b]_1+v^4\cdot[c]_1+v^5\cdot[s_{\sigma1}]_1+v^6\cdot[s_{\sigma2}]_1$
(11) 计算批量多项式估计 $[E]_1$ :
$[E]_1:=\begin{pmatrix} \bar{t}+v\bar{r}+v^2\bar{a}+v^3\bar{b}+v^4\bar{c} \\ +v^5\bar{s}_{\sigma1}+v^6\bar{s}_{\sigma2}+u\bar{z}_w \end{pmatrix}\cdot[1]_1$
(12) 采用双线性对进行验证：
$e([W_{\xi}]_1+u\cdot[W_{\xi w}]_1,[x]_2)=e(\xi\cdot[W_{\xi}]_1+u\xi w\cdot[W_{\xi w}]_1 +[F]_1-[E]_1,[1]_2)$

实现过程

可信设置

可信设置主要生成CRS (Common Reference String), 对于 $n$ 个电路的可信设置，需要生成 $n + 5$ 个元素：
$1\cdot G_1, s\cdot G_1, s^2\cdot G_1, \cdot\cdot\cdot, s^{n+2}\cdot G_1; \\ 1\cdot G_1, s\cdot G_2$
其中 $G_1$ , $G_2$ 为椭圆曲线的生成元， $s$ 秘密参数，即需要丢弃的有毒废料。可信设置与应用无关。

pub struct Crs<E: Engine, T: CrsType> {
    pub g1_bases: Arc<Vec<E::G1Affine>>,
    pub g2_monomial_bases: Arc<Vec<E::G2Affine>>,

    _marker: std::marker::PhantomData<T>
}

实际生成的 g1_bases 的长度为 $2^k$ ，即 $k$ 为使 $2^k > (n+2)$ 的最小整数。

应用相关设置

电路生成

为了便于R1CS转化为了Plonk约束系统，zksync 1.0 在实现Plonk的时候对算法进行了部分改进，见文档, Plonk约束系统的数学表达式为：

$Q_{L_i}\cdot a_i + Q_{R_i}\cdot b_i + Q_{O_i}\cdot c_i + Q_{d_i}\cdot d_i + Q_{M_i}\cdot a_i\cdot b_i + Q_{C_i} + Q_{d_{next_i}}\cdot d_{next_i} = 0$
其中 $L$ 代表左边， $R$ 代表右边， $O$ 代表输出， $M$ 代表乘法， $C$ 代表常量， $a_i$ 代表左输入， $b_i$ 代表右输入， $c_i$ 代表电路输出， $d_{next_i}$ 代表 $d_i$ 的下一步， $i$ 代表第 $i$ 个门电路。

#[derive(Debug, Clone)]
pub struct GeneratorAssembly<E: Engine, P: PlonkConstraintSystemParams<E>> {
    m: usize,      // 
    n: usize,      // 电路个数
    input_gates: Vec<(P::StateVariables, P::ThisTraceStepCoefficients, P::NextTraceStepCoefficients)>,    //公开输入的电路，第一个状态变量赋值为-1， 其余为0   
    aux_gates: Vec<(P::StateVariables, P::ThisTraceStepCoefficients, P::NextTraceStepCoefficients)>,   //隐私输入的电路，包括状态变量和系数值
 
    num_inputs: usize,      // 公开输入的个数，起始值为1
    num_aux: usize,         //隐私输入的个数，起始值为1

    inputs_map: Vec<usize>,

    is_finalized: bool      //标记电路是否生成完毕
}

多项式计算

将上述步骤中的电路转化为多项式形式，即

$Q_{L}(x)\cdot a(x) + Q_{R}(x)\cdot b(x) + Q_{O}(x)\cdot c(x) + Q_{d}(x)\cdot d(x) + Q_{M}(x)\cdot a(x)\cdot b(x) + Q_{C}(x) + Q_{d_{next}}(x)\cdot d_{next}(x) = 0$
其中 $Q_L, Q_R, Q_O, Q_C$ 为选择多项式， $Q_{d_{next}}$ 为下一步多项式， $\sigma_a(x), \sigma_b(x), \sigma_c(x)$ 为置换多项式。

pub struct SetupPolynomials<E: Engine, P: PlonkConstraintSystemParams<E>> {
    pub n: usize,    // 电路总个数
    pub num_inputs: usize,   //公开输入的个数
    pub selector_polynomials: Vec<Polynomial<E::Fr, Coefficients>>, //选择多项式
    // 下一步多项式
    pub next_step_selector_polynomials: Vec<Polynomial<E::Fr, Coefficients>>,  
    //置换多项式
    pub permutation_polynomials: Vec<Polynomial<E::Fr, Coefficients>>,
    pub(crate) _marker: std::marker::PhantomData<P>,
}

生成验证密钥

根据setup生成的验证密钥为：
$[Q_M]_1:= Q_M(x)\cdot [1]_1, [Q_L]_1:= Q_L(x)\cdot [1]_1, [Q_R]_1:= Q_R(x)\cdot [1]_1,[Q_O]_1:= Q_O(x)\cdot [1]_1, \\ [Q_{d_{next}}]_1:= Q_{d_{next}}(x)\cdot [1]_1 \\ [\sigma_a(x)]_1, [\sigma_b(x)]_1, [\sigma_c(x)]_1$

#[derive(Clone, Debug)]
pub struct VerificationKey<E: Engine, P: PlonkConstraintSystemParams<E>> {
    pub n: usize,     //总的电路门数
    pub num_inputs: usize,   // 公开输入的个数
    pub selector_commitments: Vec<E::G1Affine>, //选择多项式承诺
    pub next_step_selector_commitments: Vec<E::G1Affine>,  // 下一步多项式承诺
    pub permutation_commitments: Vec<E::G1Affine>,        // 置换多项式承诺
    pub non_residues: Vec<E::Fr>,                        // 二次非剩余

    pub g2_elements: [E::G2Affine; 2],                  //可信设置生成的参数 

    pub(crate) _marker: std::marker::PhantomData<P>,
}

证明过程

证明主要包括五步，主要思路为计算多项式的整除，生成Kate 多项式的承诺及估值。

#[derive(Clone, Debug)]
pub struct Proof<E: Engine, P: PlonkConstraintSystemParams<E>> {
    pub num_inputs: usize,              // 公开输入个数
    pub n: usize,                       // 总的电路门数
    pub input_values: Vec<E::Fr>,       // 公开输入的值
    pub wire_commitments: Vec<E::G1Affine>,   // witness的承诺
    pub grand_product_commitment: E::G1Affine,  // z多项式的承诺
    pub quotient_poly_commitments: Vec<E::G1Affine>,  //商多项式t的承诺
 
    pub wire_values_at_z: Vec<E::Fr>,     //witness多项式式在z点的值  
    pub wire_values_at_z_omega: Vec<E::Fr>,  //witness多项式在zw点的值
    pub grand_product_at_z_omega: E::Fr,     //z多项式在zw点的值
    pub quotient_polynomial_at_z: E::Fr,      //商多项式在z点的值
    pub linearization_polynomial_at_z: E::Fr,    //线性多项式r在z点的值
    pub permutation_polynomials_at_z: Vec<E::Fr>,  //置换多项式在z点的值
 
    pub opening_at_z_proof: E::G1Affine,          //在z点的承诺证明
    pub opening_at_z_omega_proof: E::G1Affine,    //在zw点的承诺证明
 
    pub(crate) _marker: std::marker::PhantomData<P>,
}

验证过程

验证主要是对商多项式 $t(x)$ 和Kate多项式承诺的检查。

pub fn verify<E: Engine, P: PlonkConstraintSystemParams<E>, T: Transcript<E::Fr>>(
    proof: &Proof<E, P>,       // 验证的证明
    verification_key: &VerificationKey<E, P>,  //验证密钥
    transcript_init_params: Option< <T as Prng<E::Fr> >:: InitializationParameters>,
) -> Result<bool, SynthesisError> {
    let (valid, _) = verify_and_aggregate::<E, P, T>(proof, verification_key, transcript_init_params)?;

    Ok(valid)
}