详情
ZKSwap 团队解析零常识证明 PLONK 电路

撰文:ZkSwap 菜鸟

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

近况

近些年,各种新的零常识证明算法层出不出,各有各的特征,各有各的优势。借用 V 神系列文章 里的一张图来容易呈现下目前的零常识证明算法近况。

从图中可以容易概要出以下几个方面:

1. 理论上安全性最高的是 STARKs 算法,不依靠数学难点假设,具备抗量子性;

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

3. PLONK 算法在安全性上和 Proof 大小上,坐落于上述两者之间;

4. 其他的这里不做过多讲解,如想知道零常识证明更多信息,可参考 链接;

对于 SNARKs 算法,绕不开的一个点就是中心化的 Trust Setup,也称之为 CRS。而无论是 PGHR13, Groth16, 还是 GM17 算法,它们的 CRS 都是一次性的,不可更新的。即:不一样的问题将对应着不一样的 CRS,这在某些场景下,会变得比较麻烦。这类存在的问题,变成了 PLONK,SONIC 这种算法的一个优势,它们算法虽然也需要中心化的可信设置,但它的 CRS 具备肯定的普适性。即:只须电路的大小低于 CRS 的上限阈值,一些证明问题就可以共用一个 CRS,这种 CRS 称之为 SRS,关于 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 = f。下面来看具体的原理:

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

1. 而经过仔细剖析 Z 的形式,不难发现,Z 其实就是两个函数所有值的乘积的比值 。理论上是等于 1。因此,大家需要设计如此的一个多项式 Z,需满足:

2. 乘法循环群刚好可以满足这个条件,假如设计一个阶为 n 的一个乘法循环群 H,依据群的性质可以了解 Z=Z)。因此,在设计 Z 时,会保证 Z = 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 = g。与(1)存在两处不同:

多个多项式;

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

2. 有了 小节的基础,这次大家先看一下有关的概念:

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

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

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

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

下面大家看一下具体的原理:

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

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

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

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

至此,本篇文章已经描述了,在 PLONK 算法里,电路的设计与复制约束的成立验证两大多数,下面,将会另起一片文章,去推荐门约束的成立和整个协议的具体步骤。

以上都是 ZkSwap 江菜鸟的个人理解,还期望各位读者多多指教,谢谢。

出处链接:zks.org

版权保护: 本文由 链一财经 原创,转载请保留链接: http://www.guide2breastenhancement.com/baike/899.html