PLONK（1）：预备知识

拉格朗日插值法

这里不打算给出拉氏插值法的详细推导过程，感兴趣的可以看$[2]$这篇博客，讲的比较详细，这里只是讲一下基本原理以及需要使用到的部分

其实拉氏插值法在之前R1CS转QAP那篇文章中有介绍过，只是没有那么详细，这里详细介绍一下

拉氏插值法简单来说，就是通过一组观测值，来推导这组值对应的一个多项式，从数学角度来说，拉氏插值法可以给出一个二维平面上恰好都穿过这些已知观测值的多项式（或函数）

举个例子，比如说我们有四个点$(0,-2),(1,1),(2,0),(3,1)$，我们想知道一个恰好穿过这四个点的多项式，此时就可以用拉氏插值法，得到下列多项式（具体的公式和推导过程不是重点，这里就不给出了，感兴趣可以看网上的教程）

$$ f(x)=x^3-5x^2+7x-2 $$

该多项式对应的图像如下

注意到这里给出的四个点，得到的多项式的阶为3，实际上可以证明，对于已知的$d$个点，我们可以用拉氏插值法得到一个阶数不超过$d-1$的多项式（证略）

上述方法还可以用若干个独立的多项式表示，这些独立的多项式称为基多项式

还是上面那个例子，我们可以先令$x=0$处的值为$1$，然后令其余的$x$处的取值均为零（也即在$(0,1),(1,0),(2,0),(3,0)$上运用拉氏插值法），这样我们就得到了一个基多项式，记为$L_1(x)$

然后我们再令$x=1$处的值为$1$，其余的$x$处的取值均为零（也即在$(0,0),(1,1),(2,0),(3,0)$上运用拉氏插值法），得到第二个基多项式，记为$L_2(x)$，同理我们可以得到$L_3(x),L_4(x)$

回到最初的点集$(0,-2),(1,1),(2,0),(3,1)$，注意到$x=0$处的取值为$-2$，因此我们给$L_1(x)$前面附加一个系数$-2$，$L_2,L_3,L_4$同理，这样一来我们可以将上面的$f(x)$用四个基多项式表达如下

$$ f(x)=-2\cdot L_1(x)+1\cdot L_2(x)+0\cdot L_3(x)+1\cdot L_4(x) $$

这就是用拉格朗日插值法的基多项式表示法

除此之外，拉氏插值法的用途有很多，还可以用于将方程组以多项式的方式表示

举个例子，比如下面这个三元一次方程组

$$ \begin{aligned} &2x_1-x_2+3x_3=8\\ &x_1+4x_2-5x_3=5\\ &8x_1-x_2-x_3=-2 \end{aligned} $$

不难算出这个方程组的解为$x_1=1,x_2=6,x_3=4$，不过这里有三个等式，而且系数乱七八糟的，看起来不是很整洁，我们用拉氏插值法整理一下

这里引入六个多项式，首先是$V_1(x),V_2(x),V_3(x)$，这三个多项式分别用于表示$x_1,x_2,x_3$前面的系数，然后是$O(x)$，用于表示方程组等式右侧的常数项，然后记$Z(x)$为目标多项式，$H(x)$为商多项式，接下来一一解释这几个多项式怎么用

上面介绍了如何利用拉氏插值法，在已知的点集中构造恰好穿过这些点的多项式，这里我们用同样的方法构造$V_1(x),V_2(x),V_3(x)$和$O(x)$，也即我们分别在点$x=0,x=1,x=2$处对$x_1,x_2,x_3$的系数和常数项运用拉氏插值法，对应的点如下

$$ \begin{aligned} &V_1(x):(0,2),(1,1),(2,8)\\ &V_2(x):(0,-1),(1,4),(2,-1)\\ &V_3(x):(0,3),(1,-5),(2,-1)\\ &O(x):(0,8),(1,5),(2,-2)\\ \end{aligned} $$

分别对这四个点集运用拉氏插值法，就可以得到对应的四个多项式（这里没算，可以用$[3]$这个网站简单算一下，感兴趣的也可以写个脚本）

然后我们定义目标多项式为$Z(x)=(x-0)\cdot(x-1)\cdot ( x-2)$，商多项式$H(x)=0$，此时我们可以得到下列等式

$$ V_1(x)\cdot x_1+V_2(x)\cdot x_2+V_3(x)\cdot x_3-O(x)=Z(x)\cdot H(x) $$

注意这里需要区分原方程组的解（$x_1,x_2,x_3$）和多项式的变量（$x$），当$x$取不同的值时，我们就可以得到原方程组中不同的方程（或者称为约束条件）

比如取$x=1$时，有$V_1(1)=1,V_2(1)=4,V_3(1)=-5,O(1)=5$，也即$x_1+4x_2-5x_3-5=0$,从而我们恢复出了原方程组中的第二个方程

这样一来，我们利用了拉氏插值法将多个方程（或者说多个小的约束）转化为了一个大的方程（一个大的约束）

但是这又有什么用呢？如果说这个方程组很大，有十万个变量和独立方程，即便是我知道这个大的方程组的解，逐个方程去验算也依然很费时费力

但是如果我们用拉氏插值法将这十万个方程整合成一个，然后在已知解的情况下，只需要验证从$x=0$到$x=999,999$是否均有等式成立即可，原来的验证需要的开销就减少很多了

坐标对累加器

在介绍置换检查之前，介绍一个叫坐标累加器的东西，便于理解置换检查

这一小节的内容参考了V神的文章$[4]$，原文里面讲的比较详细，感兴趣的可以看一下

PLONK里面用到了置换检查，我们都知道一个数组的置换只会调整各个元素之间的排列顺序，而其本身的值是不会改变的，PLONK用到了一个叫拷贝约束的概念来增强这种置换，确保置换后的值没有发生改变（也即置换没有导致值的覆盖）

举个例子，比如说我们有一些点$(0,-2),(1,1),(2,0),(3,1)$，然后我们分别对这些点的$x$和$y$坐标利用拉氏插值法，得到两个多项式$X(x)=x,Y(x)=x^3-5x^2+7x-2$

接下来我们记坐标对累加器为$p(x)$，其本质是一个多项式，我们的目的是让$p$代表（但不包括）上述的所有点

首先我们先令$p(0)=1$，然后让$p(1)$代表第一个点，$p(2)$代表前两个点，依此类推

因为这里有两个多项式$X,Y$，我们可以随机选择两个常数$v_1,v_2$来构造$p(x)$，如下

$$ p(0)=1\\p(x+1)=p(x)\cdot (v_1+X(x)+v_2\cdot Y(x)) $$

比如，我们令$v_1=3,v_2=2$，结合上面的点和多项式，我们可以得到下列表格

最终我们可以算出$p(4)=-240$

观察之前的四个点，注意到$Y(1)=Y(3)=1$，如果我们仅对$Y(1)$和$Y(3)$作用一个置换，其值应当是不变的

我们将这个置换同样作用于点和坐标，并再次利用拉氏插值法，得到置换后的多项式，记为$X'$和$Y'$，同时利用坐标对累加器生成对应的累加值，如下

置换过后，由于$Y(1)=Y(3)$，必然有$p(4)=p'(4)$

利用坐标对累加器，我们不仅可以对置换进行检查，还有一个优点在于，将原本需要检查多项式在多个点的取值转化为了检查累加器最终结果是否相等，大大减少了验证的工作量

PLONK的置换检查的原理和坐标点累加器差不多，只不过引入了其他的一些东西

多项式承诺

PLONK主要用到的是$[KZG10]$和$[MBKM19]$多项式承诺，这里可以看之前介绍Kate多项式承诺的那篇文章，这里不再介绍

多项式引理

在介绍下一个内容之前，先介绍几个引理和推论，以便后续理解

第一个是熟知的Schwartz-Zippel引理，之前在R1CS那篇文章中也介绍过

• Lemma 1（Schwartz-Zippel）：记$P(X_1,...,X_n)$为一个$\Z_p$上的非零多变量多项式，$P$的度为$d$，则从$\Z_p$中随机选择$n$个值$(\alpha_1,...,\alpha_n)\in _R\Z_p$，有下列不等式成立

$$ Pr[P(\alpha_1,...,\alpha_n)=0]\leq \frac{d}{p} $$

SZ引理简单来说就是对一个非零多项式随机赋值，其等于零的概率不超过$\frac{d}{p}$，这个引理在很多密码组件中都有用，因为密码工具都是在一个很大的域或群中计算，此时通常会有$d\ll p$，也即$\frac{d}{p}=negl(\lambda)$，因此SZ引理的意思是，在域上随机选择这些值，使得该非零多项式的值为零的概率可忽略不计

SZ引理还可以用于检查两个多项式是否相等，比如两个多项式$P_1(X_1,...,X_n),P_2(X_1,...,X_n)$，我们可以从$\Z_p$中随机选择$n$个值$(\alpha_1,...,\alpha_n)\in _R\Z_p$分别赋值给这两个多项式，然后做差，计算$P_1-P_2$，若$P_1-P_2=0$，则表示$P_1$恒等于$P_2$，若不为零，则根据SZ引理，这两个多项式不相等的概率小于等于$\frac{\max(d_1,d_2)}{p}$（$d_1,d_2$分别表示两个多项式的度）

然后是第二个引理，一个关于置换相关的引理

• Lemma 2：对于两个数组$(a_1,...,a_n),(b_1,...,b_n)$而言，若对于随机选择$\gamma \in \mathbb F$，下列等式以不可忽略的概率成立

$$ \prod _i(a_i+\gamma )=\prod_i(b_i+\gamma ) \tag1 $$

则$(b_1,...,b_n)$是$(a_1,...,a_n)$的一个置换

这个引理很好理解，每个元素都加上了$\gamma$，而且乘法具有交换律，如果$(b_1,...,b_n)$是$(a_1,...,a_n)$的一个置换，必然有等式成立

不过这个引理也可以用SZ引理证明

• Proof：记两个多项式

$$ P_a(X)=\prod_i(X+a_i)\\P_b(X)=\prod_i(X+b_i) $$

不难看出这两个多项式的根分别为$(-a_1,...,-a_n)$和$(-b_1,...,-b_n)$

根据SZ引理，若$P_a\neq P_b$，则式(1)成立的概率小于等于$\frac{n}{|\mathbb F|}$，若选择的域$\mathbb F$足够大，则此概率可忽略不计，此时意味着$P_a$的根也是$P_b$的根（反之亦然）

进一步的，将这个引理推广一下，得到下面这个推论

• Corollary：对于给定的置换$\sigma$和数组$[n]$，给定$A_1,...,A_n,B_1,...,B_n\in \mathbb F$，对于随机选择的$\beta \in \mathbb F$，下列等式以不可忽略的概率成立

$$ \prod _{i\in [n]}(A_i+\beta \cdot i)=\prod _{i\in [n]}(B_i+\beta \cdot \sigma (i)) $$

则$(\frac{B_1}{\sigma(1)},...,\frac{B_n}{\sigma(n)})$为$(A_1,...,\frac{A_n}{n})$的一个置换

同样用SZ引理证明

• Proof：记两个多项式

$$ P_A(Y)=\prod_{i\in [n]}(i\cdot Y+A_i) \\ P_B(Y)=\prod_{i\in [n]}(\sigma(i)\cdot Y+B_i) $$

不难看出这两个多项式的根分别为$(-A_1,...,-\frac{A_n}{n})$和$(-\frac{B_1}{\sigma(1)},...,-\frac{B_n}{\sigma (n)})$，利用Lemma 2，我们可以证明上述推论正确

这个推论只不过是在Lemma 2的基础上加了一个置换$\sigma$而已，本质的证明方式还是和SZ引理相关

最后我们将Lemma 2和Corollary结合起来，得到下面这个

• Claim：若对于随机选择的$\beta ,\gamma \in _R\mathbb F$，下列等式以不可忽略的概率成立

$$ \prod_{i\in [n]}(a_i+\beta \cdot i+\gamma )=\prod_{i\in [n]}(b_i+\beta \cdot \sigma(i)+\gamma ) \tag 2 $$

则对于$\forall i\in [n]$，有$b_i=a_{\sigma(i)}$

这里的Claim就是前面坐标点累加器的一个比较形式的描述，这里的$\beta,\gamma$相当于前面坐标点累加器中的$v_1,v_2$，$a_i,b_i$相当于前面的$X,Y$

最后这个Claim在PLONK中很重要，构成了PLONK中拷贝约束的核心

置换检查

PLONK的核心之一就是置换检查（Permutation Check），最早来自于Bayer和Groth的论文$[BG12]$，PLONK用的是$[MBKM19]$的改进版本，用单变量多项式和乘法子群进一步优化以得到更高的效率

置换检查，简单来说就是检查一个集合是另一个集合的置换，$[BG12]$这篇paper里面介绍的是秘密洗牌（就是证明一副牌洗过了），whatever，反正置换检查和秘密洗牌讲的是同一个东西

置换检查是为了实现PLONK中的拷贝约束，确保门的输入输出关系成立

这里需要用到两个整数参数$n\leq d$，$n$表示诚实Prover的多项式的度，$d$用于限制恶意Prover的一个参数（这个参数$d$还会用于分析协议的合理性，不过这里不重要，随便说一下）

此外还需要用到一个乘法子群$H\subset \mathbb F$，生成元记为$\mathtt g$，该子群的阶为$n$，也即有$\mathtt g^n=1$

对于$i\in [n]$，记一个关于$H$的拉格朗日基多项式，多项式$L_i(X)$表示$H$上的第$i$个基多项式（$L_i(\mathtt g^i)=1$，且对于$\forall a\in H,a\neq \mathtt g^i,L_i(a)=0$）

对于$f,g$为域$\mathbb F$上度小于$d$的多项式，记一个置换$\sigma :[n]\rarr [n]$，引入一个记法：$g=\sigma(f)$表示对于$\forall i\in [n]$，有$g(\mathtt g^i)=f(\mathtt g^{\sigma(i)})$

记两个度小于$n$的多项式$S_{ID},S_\sigma$，分别定义为$\forall a\in [n]:S_{ID}(\mathtt g^i)=i,S_\sigma(\mathtt g^i)=\sigma(i)$

所有的符号介绍完了，接下来看置换检查的核心部分，Prover需要向Verifier证明多项式置换$g=\sigma(f)$，具体协议如下

Input：$f,g$

1. Verifier随机选择$\beta ,\gamma \in \mathbb F$并发送给给Prover
2. Prover计算

$$ f'=f+\beta\cdot S_{ID}+\gamma\\g'=g+\beta \cdot S_\sigma +\gamma $$

也即

$$ f'(\mathtt g^i)=f(\mathtt g^i)+\beta \cdot i+\gamma \\ g'(\mathtt g^i)=g(\mathtt g^i)+\beta \cdot \sigma(i)+\gamma $$

1. Prover计算一个度小于$n$的多项式$Z$，满足$Z(\mathtt g)=1$，而对于$i\in\{2,3,...,n\}$，有

$$ Z(\mathtt g^i)=\prod_{1\leq j\leq i}\frac{f'(\mathtt g^j)}{g'(\mathtt g^j)} $$

Prover将计算好的$Z$发送给可信第三方$I$

1. Verifier检查对于$\forall a\in H$，有

   • $L_1(a)\cdot (Z(a)-1)=0$
   • $Z(a)\cdot f'(a)=g'(a)\cdot Z(a\cdot \mathtt g)$

若所有检查都通过， 则Verifier输出接受

看不懂没关系，结合之前多项式引理末尾提到的Claim就很好理解了

这里Prover需要证明的是两个多项式满足一个置换$g=\sigma(f)$，这里利用$f,g$构造了$f',g'$，目的就是凑成Claim中的那种形式，$f'$中的$f(\mathtt g^i)$实际上就是式(2)中的$a_i$，$S_{ID}$就是$i$，同理$g'$中的$g(\mathtt g^i)$就是式(2)中的$b_i$，$S\sigma$就是$\sigma(i)$，这样就很好理解了

前面提到了，SZ引理的方式是做差，根据SZ引理，若$f'\neq g'$，则大概率$f'-g'\neq 0$

而PLONK的方式是将两个多项式做比，也即上述第三步中的$\frac{f'(\mathtt g^j)}{g'(\mathtt g^j)}$，若两个多项式相同，根据SZ引理，两个多项式的比值应当是1，换言之，对于给定度小于$d$的两个多项式$f,g$，若有$g\neq \sigma(f)$，则Verifier输出接受的概率为$negl(\lambda)$

这个不难证明，通过反证法就可以，根据上一节的Claim，若我们假设有$g\neq \sigma(f)$，我们可以得到

$$ \prod_{i\in [n]}f'(\mathtt g^i)=a\\ \prod_{i\in [n]}g'(\mathtt g^i)=b $$

假设对于选择的$\beta,\gamma \in \mathbb F$，有$a\neq b$成立，同时有对于$\forall i\in [n],g'(\mathtt g^i)\neq 0$，则第四步中Verifier的第一个检查确保了$Z(\mathtt g)=1$，而第二个检查确保了对于$\forall i\in [n]$，都有

$$ Z(\mathtt g^{i+1})=\prod _{1\leq j\leq i}\frac{f'(\mathtt g^j)}{g'(\mathtt g^j)} $$

而根据假设$g\neq \sigma(f)$，可以得到$Z(\mathtt g^{n+1})=\frac{a}{b}$，但是我们最开始提到了在乘法子群$H$上讨论，因此必然有$\mathtt g^{n+1}=\mathtt g$

故我们可以得到

$$ 1=Z(\mathtt g)=Z(\mathtt g^{n+1})=\frac{a}{b}\neq 1 $$

矛盾，故必然有$g=\sigma(f)$

可能还是有些难以理解，我们可以简单改一下，把$\frac{f'(\mathtt g^i)}{g'(\mathtt g^i)}$视为一个整体（注意这里将不带连乘的符号的部分视为一个整体），记为$U_i$，然后将$Z(\mathtt g^i)$记为$Z_i$

此时上述协议第三步中的式子就可以改写为下列的递归式

$$ \begin{aligned}&Z_1=1\\ &Z_{i+1}=Z_iU_i\ \ \ \ (i=2,3,...,n)\end{aligned} $$

因为我们需要证明的是$g=\sigma(f)$，因此必然有$\prod_{i\in [n]} U_i=1$，根据这里的记法，当$i=n$时，我们有$Z_{n+1}=Z_n\cdot U_n=\prod_{i\in [n]} U_i=1$，也即上面的$Z(\mathtt g)=Z(\mathtt g^{n+1})=1$

因此只要Verifier验证通过，必然有$g=\sigma(f)$

跨多项式置换检查

这里对应的是原文的5.1节，其实和上一节提到的置换检查差不多，在PLONK协议中也用于拷贝约束，不过是不同门之间的约束

比如一个门的左输入很可能会是另一个门的右输入，或者一个门的输出很可能又是其他门的左/右输入

PLONK协议里面会把左/右输入和输出全部编码为多项式的形式，如果存在上述情况，则意味着一个值会涉及到多个多项式，因此就需要用到跨多项式置换检查

举个例子，比如说第一个门的输出$c_1$，很有可能是第三个门的输入$a_3$，为了确保$c_1=a_3$，PLONK通过拷贝约束的方式来限制，跨多项式置换检查的目的就是检查此类拷贝约束

和Groth的算法一样，最后所有的$a_i,b_i,c_i$都会编码成多项式$a(X),b(X),c(X)$，而要检查$c_1=a_3$就意味着检查两个不同的多项式

这里似乎说的有点复杂了，跨多项式检查简单来说就是检查两个不同的多项式$f\neq g$，存在两个值$x,y$，使得$f(x)=g(y)$，这里允许$x\neq y$，因为实际电路中不一定是同一个门的约束

跨多项式置换检查的方法和前面的置换检查方法类似，也是通过构造拉氏基多项式，然后相加相乘得到最终结果，这里不再赘述，具体可以看原文的第5.1节

小结

这篇paper主要介绍一下PLONK需要的预备知识，重点是多项式承诺和置换检查

KZG多项式承诺可以参考之前的文章，写的比较详细，PLONK用到了里面的批量揭示（batch opening），还是比较有用的

其次就是两种置换检查，置换检查会在PLONK中的拷贝约束（copy constraint）里面用到，也是PLONK的核心之一，理解了置换检查感觉理解了PLONK一半了

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零知识证明方案