零知识证明 - PLONK电路原理

Groth16算法确实比较美，优点是证明小，非常适合链上验证的场景。但是，Groth16算法需要可信的初始设置(Trusted Setup)，而且每个电路都需要初始设置。特别在业务电路升级的时候，还需要重新初始设置。PLONK算法，只需要一次初始设置（Universal Trusted Setup）。初始设置的参数可以升级，而且在电路大小不超过范围的情况下，不需要重新设置。

理解PLONK算法，可以先从PLONK的电路开始。熟悉Groth16算法的小伙伴都知道，Groth16算法基于QAP问题。所有的计算电路可以通过R1CS，转换成QAP问题。PLONK的电路描述采用不同的方式。Vitalik的这篇Blog对PLONK电路的解释非常清楚，感兴趣的小伙伴可以直接看原文：

https://vitalik.ca/general/2019/09/22/plonk.html

PLONK电路

PLONK的电路由加法门/乘法门以及一些常量组成。以P(x) = x^3 + x + 5 = 35为例：

对电路中的常量以及加法门/乘法门进行编号和标注，乘法门和加法门都由三组连线组成：a/b/c，分别代表一种门的两个输入（左右输入）和一个输出。

以编号为1的乘法门举例，这个乘法门约束a1*b1=c1。

门约束

PLONK算法采用两种约束关系描述整个电路：1/ 加法门/乘法门约束 2/ Copy约束。因为加法门和乘法门，只描述单个门的依赖关系，所以要加上Copy约束才能描述确定的完整电路。所谓的Copy约束，其实就是门和门之间的“共享”连接。从加法门和乘法门约束说起。

因为“门”的描述需要包括三种情况：1/乘法门 2/加法门 3/常量，PLONK系统定义了通用的表示公式：

其中L代表左输入，R代表右输入，O代表输出，M代表乘法，C代表常量。在这种的通过公式下，乘法门/加法门以及常量采用不同的系数。

加法门，采用如下的系数：

乘法门，采用如下的系数：

常量，采用如下的系数：

简单的说，在通用公式下，所有电路中的门和变量都可以表达。而这一系列的表达式，可以用多项式进行“压缩”，表示为：

也就是说，电路中的所有加法门/乘法门以及常量的关系可以通过一个多项式进行表示。

Copy约束

显然，上述的门和常量的约束，只是约束独立的，相互不依赖的约束关系。在这些约束关系的基础上，加上“Copy约束“， 门和门之间的连接关系，整个电路就确定了。在介绍Copy约束之前，先介绍一下“坐标点累加” (coordinate pair accumulator)。

假设X(x)和Y(x)，定义了一系列的X/Y的坐标点。x从0开始。p(x)为从0到x（不包括）的坐标点累加，定义如下：

p(0) = 1

p(x+1) = p(x) (v1+X(x)+v2 Y(x))

以Y(x) = x^3 - 5 * x^2 + 7x -2 为例，并且v1=3, v2=2 ：

简单的说，p(x)把一系列的坐标点累加。因为乘法的交换律，这种累加算法，并不区分坐标点的顺序。如果只改变X(x)的点的顺序，在累加结果相同的情况下，可以推导出Y(x)的关系。举个例子：

一个累加器计算：(0，a(0))，(1，a(1))，(2，a(2))，(3，a(3))，(4，a(4))

另外一个累加器计算：(0，a(0))，(3，a(1))，(2，a(2))，(1，a(3))，(4，a(4))

这两个累加器计算结果相同，在v1，v2随机选择的情况下，可以推导出a(1) = a(3)。a(1)=a(3)就是Copy约束，第1个门的左输入和第3个门的左输入相同。

电路中总共有三组连线：a/b/c。为了表示，不同连线之间的Copy约束，三组连线采用统一的编号。假设总的门的个数为n，a的连线编号从0～n-1，b的连线编号从n～2n-1，c的连线编号从2n～3n-1。也就是说，Xa(x) = x, Xb(x) = n+x, Xc(x) = 2n+x。在举个例子，比如n=5，为了证明a(2) = b(4)， Xa(x)=01234, X'a(x) =01934, Xb(x)=56789, X'b(x) = 56782。

如果在X(x)交换了顺序后，pa(n) pb(n) pc(n) = p'a(n) 'pb(n) p'c(n) ，就可以证明交换了连线编号有“连线”关系，相应的Copy约束成立。

特别注意的是，X'a(x), X'b(x), X'c(x)只改变的是X的编号，并不改变Y的结果。

电路验证

真实的电路计算在有限域，电路中的门的编号并不是整数，而是omega（omega是有限域中的根）。

在上述的电路描述方法下，整个电路需要验证如下的关系：

1/ 各个门的关系是否正确

2/ 门和门之间的连线正确

先确定累加的计算在X编号变化前后的计算正确。

再确认累加结果的初始和最后一致。

以上介绍了PLONK电路描述和约束的基本原理，具体的PLONK算法后面的文章会具体介绍。PLONK算法为什么能做到Universal，具体的协议过程和计算如何，敬请期待～

总结：

PLONK算法的电路采用新的描述模型。整个电路由门电路约束和Copy约束（连线约束）组成。门电路约束和Copy约束都转换为多项式表达。Copy约束通过累加算法实现。