理解零知识算法PLONK（一）—电路

江小白 安比技术社区 2021-01-26 12:32
收录于合集

本文作者江小白，来自安比技术社区的小伙伴，本系列文章将对零知识证明算法-PLONK展开介绍。

最近研究了下零知识证明算法-PLONK。肚子里的墨水又增加了，记一下学习成果与新的体会，和大家共同学习 。

现状

近些年，各种新的零知识证明算法层出不出，各有各的特点，各有各的优势。借用V神系列文章里的一张图来简单呈现下当前的零知识证明算法现状。

Image

Fig.1 Zkp Algs 

从图中可以简单总结出以下几点：

  • 理论上安全性最高的是STARKs算法，不依赖数学难题假设，具有抗量子性；

  • Proof大小上最小的是SNARKs算法，如Groth16; PLONK算法在安全性上和Proof大小上，位于上述两者之间；

  • 其他的这里不做过多阐述，如想了解零知识证明更多信息，可参考链接。

对于SNARKs算法，绕不开的一个点就是中心化的Trust Setup，也称之为CRS(the Common Reference String)。而无论是PGHR13, Groth16,还是GM17算法，它们的CRS都是一次性的，不可更新的。即，不同的问题将对应着不同的CRS，这在某些场景下，会变得比较麻烦。这些存在的问题，变成了PLONK，SONIC这类算法的一个优势，它们算法虽然也需要中心化的可信设置，但是它的CRS具有一定的普适性。即，只要电路的大小不超过CRS的上限阈值，一些证明问题就可以共用一个CRS，这种CRS称之为SRS(universal Structured Reference String)，关于SRS的定义，详细的可参考SONIC协议里的第3小节。PLONK算法继用了SONIC算法的SRS的思想，但是在证明的效率上，做了很大的提升。接下来，让我们详细的介绍下PLONK算法的具体细节，主要从下面四个小节去分享：

  • 电路的设计 -- 描述PLONK算法的电路的描述思想；

  • 置换论证或者置换校验 -- 复制约束，证明电路中门之间的一致性；

  • 多项式承诺 -- 高效的证明多项式等式的成立；

  • PLONK协议 -- PLONK协议剖析。

电路

PLONK算法电路的描述和SONIC算法一直，具体的过程可以参考李星大牛的分享，已经写的比较详细且易懂。在这个小篇幅里，我想主要分享下我自己的两点想法：

  • 无论是什么样的电路描述方式，电路的满足性问题都要归结于2点，门的约束关系和门之间的约束关系成立；

  • 在SNARKs系列的算法里，电路的描述单元都是以电路中有效的线为基本单元，具体的原理可以参考我之前分享的文章，而在PLONK，SONIC以及HALO算法里，电路的描述单元都是以门为基本单元。

这两种电路的不同描述方式带来了一定的思考。那就是，之前在研究SNARKs算法时，我们都已经相信一个事实，“多项式等式成立，就代表着每个门的约束成立”，然后推断，整个电路逻辑都是成立；在这个过程中，并没有额外的去证明门之间的一致性成立；但是在PLONK算法里，除了要证明多项式等式成立外，还要额外的用置换论证的数学方法去证明门之间的约束关系，即复制约束。为何会有这样的区别？希望有心的读者能一起在评论区探讨这个问题？我个人理解是因为电路的描述方式的不同：

  • PLONK算法里，电路描述的单元是门，它为每个门定义了自己的L,R,O，因此需要证明门之间的一致性；

  • SNARKs算法里，电路描述的单元是线，门与门之间的值用的是同一个witness，因此不用额外证明一致性。

置换论证

前面我们说过，在PLONK算法里，需要去证明门之间的约束关系成立。在做具体的原理解释之前，我们先简单的过一下PLONK协议的过程，如下图所示：

Image

Fig2. Protocol 

可描述为：

  • 根据电路生成三个多项式，分别代表这电路的左输入，右输入，输出；

  • 利用置换校验协议，去证明复制约束关系成立；

  • 步骤3和4，校验门的约束关系成立。

其中第1点已经在电路小节里阐述过了，接下来，将详细的讲解多项式置换校验的原理。先从简单的场景去讲解：

（1）单个多项式的置换校验 

其实就是证明对于某个多项式f，存在不同的两个点x,y，满足f(x) = f(y)。下面来看具体的原理：