PLONK算法的电路采用新的描述模型。整个电路由门电路约束和Copy约束(连线约束)组成。门电路约束和Copy约束都转换为多项式表达。Copy约束通过累加算法实现。
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的电路由加法门/乘法门以及一些常量组成。以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约束之前,先介绍一下“坐标点累加” (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约束通过累加算法实现。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!