ZKSwap 团队解读零知识证明 PLONK 电路

撰文：ZkSwap 小白

最近研究了下零知识证明算法-PLONK。肚子里的墨水又增加了，借此记录学习成果与心得体会。

现状

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

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

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

2. Proof 大小上最小的是 SNARKs 算法，如 Groth16;

3. PLONK 算法在安全性上和 Proof 大小上，位于上述两者之间；

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

对于 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 算法的具体细节，主要从下面四个小节去分享：

1. 电路的设计 — 描述 PLONK 算法的电路的描述思想；

2. 置换论证或者置换校验 — **约束，证明电路中门之间的一致性；

3. 多项式承诺 — 高效的证明多项式等式的成立；

4. PLONK 协议 — PLONK 协议分析；

电路

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

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

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

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

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

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

置换论证

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

可描述为：

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

2. 利用置换校验协议，去证明**约束关系成立；

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

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

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

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

上图中加入了一个正例 P，一个反例 A，方便大家理解置换校验的原理。有几点需要解释的是：

1. 而经过仔细分析 Z 的形式，不难发现，Z(n+1) 其实就是两个函数所有值的乘积的比值 (不知是否等同于 V 神文章里的坐标累加器？)。理论上是等于 1。因此，我们需要设计这样的一个多项式 Z，需满足：

2. 乘法循环群刚好可以满足这个条件，如果设计一个阶为 n 的一个乘法循环群 H，根据群的性质可以知道 Z(g)=Z(g^(n+1))。因此，在设计 Z 时，会保证 Z(g) = 1；上图中的自变量的取值也将从{1…n}变成{g…g^n}。所以在上图中验证的部分，a 其实已经换成了群 H 里的所有元素。

3. 根据论文中的协议，多项式 Z 是会发给可信第三方 I 验证方 V 会从 I 处获取到多项式 Z 在所有 a 处的取值，然后依次校验。

下面具体看一下论文中的定义：

从定义中可以看出：多项式 f, g 在 [n] 范围内具有相同的值的集合；下面看一下论文中具体的协议部分，结合上述解释的 3 点：

说明：图 4 中的 f,g 对应图 3 中的 f。即 f,g 是同一个多项式。其实只要是相同的值的集合，也可以不用于是同一个多项式。图 3 是一个特例而已。

（2）跨多项式的校验

其实就是证明对于某个多项式 f，g，存在两个点 x,y，满足 f(x) = g(y)。与（1）存在两处不同：

多个多项式；

1. 不强制 x,y 的关系，即也可以等，也可以不等；

2. 有了 (1) 小节的基础，这次我们先看一下相关的定义：

从定义可以看到，这次是两个多项式集合见的置换校验算法。从标注的部分可以看出：

1. 两个多项式集合仍然具有相同的值的结合；

2. 为了区分集合里的多项式，自变量的索引得区分开来；

因此，可以想象的到，如果存在两个多项式 f,g，想要证明 f(x) = g(y)，那么根据以上描述可以判断{f1,f2} = {f,g} = {g1,g2}。也保证了上述第 1 点的成立。

下面我们看一下具体的原理：

和 (1) 小节相比，证明方 P 增加了些工作量，验证方 V 工作量不变。结合上述描述，也能很容易的理解其数学原理。

说明：至此，其实我们已经慢慢的接触到 PLONK 算法的核心了，前面我们讲到，电路的满足性问题除了门的约束关系还有门之间的约束关系。

比如一个输入 x，它既是一个乘法门的左输入，又是另外一个乘法门的右输入，这就需要去证明 L(m)=R(n)，这就是跨多项式的置换校验。

下面再给出论文里的协议内容：

至此，本篇文章已经描述了，在 PLONK 算法里，电路的设计以及**约束的成立验证两大部分，接下来，将会另起一片文章，去分享门约束的成立和整个协议的具体步骤。

以上都是 ZkSwap 江小白的个人理解，还希望各位读者多多指教，谢谢。

来源链接：zks.org