零知识证明 - PLONK电路原理

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

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

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

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约束通过累加算法实现。

本文参与2022世界杯预选赛赛程直播社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-10-06 13:28
  • 阅读 ( 1893 )
  • 学分 ( 24 )
  • 分类:零知识证明

0 条评论

请先 登录 后评论
Star Li
Star Li

81 篇文章, 6304 学分