约束系统

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 lin

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

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

$[4]$ Understanding PLONK

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

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