撰文:ZkSwap 小白

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

现状

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

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

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

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)。下面来看具体的原理:

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

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

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

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

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 点:

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

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

(2)跨多项式的校验

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

多个多项式;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

来源链接:zks.org