约束系统

PLONK的约束系统首先由两个整数$m,n$固定，$m$表示电路中导线的数量，$n$表示电路中门的数量，PLONK主要针对的是扇入为2、扇出不受限的算术电路

PLONK的约束系统有两个，门约束（Gate Constraint）和拷贝约束（Copy Constraint）

门约束系统

这里将门约束系统记为$C=(V,Q)$，具体如下

  • $V=(\boldsymbol a,\boldsymbol b,\boldsymbol c)$：$V$实际上是一个向量三元组，$\boldsymbol a,\boldsymbol b,\boldsymbol c\in [m]^n$分别表示电路的左输入、右输入和输出序列
  • $Q=(q_L,q_R,q_O,q_M,q_C)\in (\mathbb F^n)^5$：$Q$是一个向量五元组，其中每个向量都称为选择器向量

这里的五个选择器向量很好理解，前三个$q_L,q_R,q_O$是电路中的门约束，也即分别用于约束一个门的左输入（Left）、右输入（Right）和输出（Output）导线

然后$q_M$是PLONK约束系统中最常见约束，又称为为算数约束，下标的M代表Multiplication，该约束用于表示电路中的加法门和乘法门，若电路中的第$i$个门为乘法门，则$(q_M)_i=1$，否则$(q_M)_i=0$

最后的$q_C$是常量约束（Constant Constraint），一般来说这个约束为0

PLONK的约束系统可满足性要求，若statement $\boldsymbol x$满足$C$，则对于$\forall i\in [n]$，都有

$$ (q_L)_i\cdot x_{\boldsymbol a_i}+(q_R)_i\cdot x_{\boldsymbol b_i}+(q_O)_i\cdot x_{\boldsymbol c_i}+(q_M)_i\cdot (\boldsymbol x_{\boldsymbol a_i}\boldsymbol x_{\boldsymbol b_i})+(q_C)_i=0\tag1 $$

举个例子，如果讨论的是算术电路，则对于第$i$个门而言，若其是乘法门，则

$$ (q_L)_i=(q_R)_i=0,(q_M)_i=1,(q_O)_i=-1 $$

我们可以得到$a_i\cdot b_i-c_i=0$

若其是加法门，则有

$$ (q_L)_i=(q_R)_i=1,(q_M)_i=0,(q_O)_i=-1 $$

得到$a_i+b_i-c_i=0$

如果讨论的是布尔电路，根据布尔电路的特点，对于某些$j\in [m]$，需要确保$x_j\in \{0,1\}$，因此在PLONK下讨论布尔电路时，有

$$ \boldsymbol a_i=\boldsymbol b_i=j\\(q_L)_i=-1,(q_M)_i=1\\(q_R)_i=(q_O)_i=(q_C)_i=0 $$

此时可以得到$-j+j\cdot j=0$，目的是约束下标为$j$的输入取值为$\{0,1\}$

除了上述这些语数外，PLONK中还有一个约束，称为公共输入增强约束，因为公共输入时Prover和Verifier都知道的，因此需要将公共输入在约束系统中体现出来

比如要求下标为$j$的输入的值为$v$，此时就用到了常量约束，可以令

$$ a_i=j\\(q_L)_i=1\\(q_M)_i=(q_R)_i=(q_O)_i=0\\(q_C)_i=-v $$

此时可以得到$j-v=0$

注意到，上面这些东西都带了一个下标$i$，看起来不太友善，我们需要消去这个下标，具体的做法是利用拉氏插值法

由于电路是公开的，因此五个选择器向量的每个值都是知道的，因此我们可以利用拉氏插值法可以得到五个多项式$q_L(x),q_R(x),q_O(x),q_M(x),q_C(x)$

同理，左输入$a_i$、右输入$b_i$，输出$c_i$也可以用拉氏插值法，得到三个多项式$a(x).b(x),c(x)$

这样一来，我们就有了八个多项式，原来的约束条件等式右侧是0，但是我们知道多项式不是恒等于零的，因此我们最初的约束条件（式(1)）就会变成下面这样

$$ q_L\cdot a(x)+a_R\cdot b(x)+q_O\cdot c(x)+q_M\cdot a(x)\cdot b(x)+q_C=something $$

左边这个something其实和之前R1CS里面介绍的差不多，有一个目标多项式和商多项式，这里目标多项式记为$Z_H(x)$，$H$表示该多项式的根都在乘法子群$H$里面，商多项式记为$t(x)$，商多项式会保密，因此约束条件就变成了

$$ q_L\cdot a(x)+a_R\cdot b(x)+q_O\cdot c(x)+q_M\cdot a(x)\cdot b(x)+q_C=t(x)\cdot Z_H(x)\tag2 $$

式(2)就是PLONK所用到的门约束

拷贝约束

由于电路中很可能会存在下列几种情况

  • 一个值作为不同门的输入
  • 一个门的输出作为另一个门的输入

拷贝约束就是为了确保这种情况下，每个导线的赋值不会出错

PLONK拷贝约束的目的是约束三个赋值向量$V=(\boldsymbol a,\boldsymbol b,\boldsymbol c)$，使上述情况发生时，导线的值不会改变

而验证拷贝约束的方式是上一篇文章提到的置换检查，利用置换检查，确保$\sigma(\boldsymbol a,\boldsymbol b,\boldsymbol c)=(\boldsymbol a,\boldsymbol b,\boldsymbol c)$

最终协议

这一节就是把前面所有的东西缝合起来，但是在缝合之前，有一些小说明

  • 前面的内容都没有在协议中引入零知识，这一节为协议添加零知识性，做法是为Prover的多项式乘一个随机倍数即可
  • 仍然在乘法子群$H$中讨论，并假设电路中门的数量不超过这个子群的阶$n$（原文把生成元的记号由$\mathtt g$替换为了$\omega$，其他都不变）
  • 引入一个Hash函数，记为$\mathcal H$，该函数将任意输入映射到域上的一个元素，引入Hash函数的目的是利用FS变换将协议变为非交互式的（不过在安全性分析中，$\mathcal H$会被视为Random Oracle）

多项式

然后看一下和协议相关的一些多项式和记法

  • 首先是选择器多项式$q_L,q_R,q_O,q_M,q_C$和给定的整数$n$，这些值唯一定义了一个电路
  • 然后是$S_{ID_1}(X)=X,S_{ID_2}(X)=k_1X,S_{ID_3}(X)=k_2X$，这三个多项式会被分别用于对$\boldsymbol a,\boldsymbol b,\boldsymbol c$的置换，其中$k_1,k_2\in \mathbb F$需要满足使得$H,k_1\cdot H,k_2\cdot H$是$\mathbb F^*$上不同的的陪集（也即包含$3n$个不同的元素）
  • 然后定义一个新的集合$H'=H\cup (k_1\cdot H)\cup (k_2\cdot H)$，令置换$\sigma [3n] \rarr[3n]$，因此在集合$H'$上，我们有

$$ i\rarr \omega^i\\n+i\rarr k_1\cdot \omega ^i\\ 2n+i\rarr k_2\cdot \omega ^i $$

  • 定义$\sigma^*$，表示$[3n]$到$H'$的映射（该映射由$\sigma$得到），具体如下

$$ S_{\sigma_1}(X)=\sum_i^n\sigma^*(i)\cdot L_i(X)\\ S_{\sigma_2}(X)=\sum_i^n\sigma^*(n+i)\cdot L_i(X)\\ S_{\sigma_3}(X)=\sum_i^n\sigma^*(2n+i)\cdot L_i(X)\\ $$

SNARK证明关系

对于给定的$l<n$，以及上面那堆多项式，我们需要证明statemen $x=(w_i)_{i\in [l]}$和witness $w=(w_i)_{i=l+1}^{3n}$，满足

  1. 对于$\forall i\in [n]$，有

$$ q_{Mi}\cdot w_i\cdot w_{n+i}+q_{Li}\cdot w_i+q_{Ri}\cdot w_{n+i}+q_{Oi}\cdot w_{2n+i}+q_{Ci}=0 $$

实际上就是证明门约束

  1. 对于$\forall i\in [3n]$，有

$$ w_i=w_{\sigma(i)} $$

这里是拷贝约束

Protocol

正式介绍协议

首先是Prover和Verifier的预处理公共输入

$n$就是电路的规模，$(x\cdot [1]_1,...,x^{n+5}\cdot [1]_1)$是椭圆曲线上的点，因为最终PLONK是通过椭圆曲线配对的方式来高效验证结果，因此所有的多项式和计算过程都会转化为ECC上的点，因此这里需要一些点

$\sigma^*$，前面提到的置换

$(q_{L_i},q_{R_i},q_{O_i},q_{M_i},q_{C_i})^n_{i=1}$，这个就是前面提到的选择器向量，因为电路是公开的，因此这些约束值也是双方都知道的

$q_L(X),q_R(X),q_O(X),q_M(X),q_C(X)$，这个就是约束与拉氏基多项式乘积求和的结果，也就是利用拉氏插值法将这五个约束转化为对应的多项式

$S_{\sigma_1}(X),S_{\sigma_2}(X),S_{\sigma_3}(X)$，这三个多项式会用于前面提到的拷贝约束的检查（置换检查），分别对应$a(X),b(X),c(X)$三个多项式，前面提到了我们将三个向量视为一个大的向量，因此$i$就对应$a_i$，$n+i$就对应$b_i$，$2n+i$就对应$c_i$

然后是公共输入$(l,(w_i)_{i\in [l]})$和Prover的私有输入$(w_i)_{i\in[3n]}$

接下来是Prover的工作，需要分为五轮处理

Round 1

Prover在第一轮中，选择九个盲化标量$(b_1,...,b_9)$，盲化标量的目的是确保协议的零知识性

然后利用witness计算三个多项式$a(X),b(X),c(X)$，这里为了确保零知识性，在拉氏插值法的基础上，利用盲因子加上了一个$Z_H(X)$的倍数

这里需要解释一下，如果不加$Z_H(X)$的倍数，直接对witness利用拉氏插值法构造多项式（也即这三个多项式仅包含上图中红色框框的部分），显然是满足式(2)的验证等式，也即上图中红色框框的部分是可以被$Z_H(X)$整除的

但是为了确保协议的零知识性，再加上一个$Z_H(X)$的倍数后也必然会被$Z_H(X)$整除

然后将这三个多项式映射到椭圆曲线上的一个点，得到Prover的第一轮输出$([a]_1,[b]_1,[c]_1)$

Round 2

首先Prover利用Hash函数$\mathcal H$计算用于置换检查的挑战$\beta,\gamma$，这里的$transcript$表示截止至目前为止Prover的输出，也即第一轮中输出的三个点

然后Prover需要计算一个多项式$z(X)$，上图中的红色框框就是前面提到的置换检查中$\frac{f'}{g'}$的形式，分子和分母的三个括号分别对应$a,b,c$的三个多项式，也即置换检查中的三个不同的$f'$及其对应的$g'$

最后Prover将该多项式映射到曲线上的一个点，输出$[z]_1$

Round 3

首先利用$transcript$计算本轮的挑战$\alpha$（这里的$transcript$表示前两轮Prover的输出，一共是四个曲线上的点）

然后计算商多项式$t(X)$，如下

这里$t(X)$分为两个部分来看，红色部分就是电路中的门约束，蓝色部分就是置换检查中Verifier需要检查的东西

不难看出来这个$t(X)$是一堆多项式加减乘除，结果是得到一个阶数极高的多项式，如果直接处理$t$的话复杂度太高，我们将$t$分为低中高三个部分，其中$t_{io}'(X),t_{mid}'(X)$的阶小于$n$，$,t_{hi}'(X)$的阶小于$n+5$

然后选择盲因子$b_{10},b_{11}$，定义中间多项式

$$ t_{lo}(X)=t'_{lo}(X)+b_{10}\cdot X^n\\ t_{mid}=t'_{mid}(X)-b_{10}+b_{11}\cdot X^n\\ t_{hi}=t'_{hi}(X)-b_{11} $$

最后相乘相加就可以得到$t(X)$

这一轮中Prover将这三个子多项式映射到曲线上，输出三个点$([t_{lo}]_1,[t_{mid}]_1[t_{hi}]_1)$（注意这里映射的是$t_{lo}$而不是$t'_{lo}$）

Round 4

首先计算一个挑战$z$（这个鬼画符一样的玩意就是字母$z$），目的是在这个点$z$揭示前面所有的多项式

本轮Prover输出$\bar a,\bar b,\bar c,\bar s_{\sigma1},\bar s_{\sigma2},\bar z_\omega$

Round 5

最重要的一轮

这里需要关注一下这个$r(X)$，实际上就是用第四轮输出的那些个东西，代入到第三轮中的$t(X)$中，就得到了这个多项式

反正就这么回事，全部捏一起算出来就完事了

验证过程

Verifier也有一个预处理，首先将公共预处理输入中的多项式映射到曲线上的点

然后对于公共输入$(w_i)_{i\in[l]}$和Prover给出的证明串$\pi_{SNARK}$，Verifier计算下列这些东西

一步一步来，前面四个都好理解，直接看第五步，这一步是计算零值多项式

前面提到了我们需要在乘法子群$H$上计算目标多项式$Z_H(X)$，回忆一下该多项式的形式

$$ Z_H(X)=(X-\omega )\cdot (X-\omega^2)\cdot ...\cdot (X-\omega^{n})=X^n-1 $$

因此直接把点$z$带入，可以得到$Z_H(z)=z^n-1$（这个鬼画符一样的玩意是$z$的花体字）

然后第六第七步，计算拉氏多项式和公开输入的多项式在点$z$的值

第八步为了减少Verifier进行标量乘法的数量，将$r(X)$拆分乘常量部分和非常亮部分，这里的$r_0$是$r$中的常量部分，非常量部分$r'(X)=r-r_0$

第九步，计算批量多项式承诺的第一部分，记为$[D]_1$

第十步计算完整的批量多项式承诺，记为$[F]_1$

第11步，将那一堆东西映射到曲线上的一个点$[E]_1$

最后一步，通过双线性配对验证是否有这么一堆东西成立，结束

小结

到此为止，PLONK方案介绍完毕，先写到这里，后续再看一下协议的验证过程

（有点累了，看这个看的是真的头大，一堆符号和鬼画符）

后记

看了一些其他大佬的博客，然后在[6]这里看到了原始的论文在Prover第三轮中，将$t(X)$拆分成三个部分后是没有为这三个部分添加随机性的

没有随机选意味着模拟器无法模拟证明，也就意味着协议不满足零知识性

不过我看这篇论文的上号，eprint已经更新了最新版，就在8月16日修改的，已经加入了随机性$(b_{10},b_{11})$

Reference

$[1]$ Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru:PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptol. ePrint Arch. 2019: 953 (2019) （eprint link）

$[2]$ 拉格朗日插值法

$[3]$ 拉氏插值法计算器

$[4]$ Understanding PLONK

$[5]$ Plonk零知识证明方案

$[6]$ PLONK算法零知识性问题