链眼社区:专注于区块链安全,区块链数据分析, 区块链信息整合,区块链技术服务和区块链技术咨询。

ZKP—PlonK算法介绍
shijiang
2022-06-10 10:27:37

PlonK 是Permutations over L agrange -bases for O eumenical N oninteractive arguments of Knowledge 的首字母缩写。PlonK 是通用零知识证明算法的实现。通用意味着可信设置只需要启动一次。对于熟悉 Groth16 的人来说,您一定已经知道 Groth16 中的每个电路都需要单独的 Trusted Setup。

您可以在此处访问 PlonK 的论文:

https://eprint.iacr.org/2019/953.pdf

这篇关于 Plonk 的论文用 8 章解释了清晰的技术逻辑。我对阅读顺序的建议:第 1 章(概述)。第5章(电路设计),第2/3/4章(背景理论),第6/7/8章(约束系统和协议)。我强烈建议你看看这篇论文。

本文讲述了Plonk算法的原理和协议Proof/Verify阶段的证明过程。

一.初始参数 SRS

对于那些了解 Groth16 的人来说,应该对 CRS - Common Reference String 有点熟悉。以类似的方式,SRS 只有通用数据,即结构化引用字符串。

二. 多项式承诺

批量多项式承诺基于一个非常简单的理论,而这恰好是 PlonK 最重要的基础。多项式承诺是证明多个多项式。该论文解释了单类型多项式commiement和多类型多项式(批处理)算法。

1. 单多项式承诺

在第 11 页,本文详细介绍了单多项式承诺的原理。分为三个步骤:

第 1 步:生成 SRS。假设多项式的最高阶为 d。取一个随机值x,生成SRS,对应多项式中每一项的两条椭圆曲线上的点。

第 2 步:为多项式生成承诺。使用 SRS,乘以多项式的系数,最终我们得到多项式的承诺。

第 3 步:验证者将 gamma 发送给验证者。验证者构造 h 多项式,并得出与多项式相关的 SRS 的关联点值。然后验证者验证多项式的值是否等于承诺值:

{cmi} — 多项式的承诺,{zi} — 多项式值(具有相同值的多个多项式),{si} — 多项式结果。Vpc 是验证者。Ppc 是认证者。Vpc 选择一个随机数并将其发送给 Ppc。Ppc计算h(X),得到椭圆曲线上的点W并发送给Vpc。Vpc计算F,通过配对验证配对函数是否具有相等的价值和承诺。在了解了配对函数的计算之后,可信度和完整性证明就变得相当简单了。如果您有兴趣,请随时查看论文。

仔细观察 Vpc 的 F 计算——它只是计算最后一个承诺和多项式。公共信息是多项式承诺和在某一点“展开”的多项式。验证者通过计算h(X)来了解多项式的知识。也就是说,使用可信 SRS,验证者不会泄露任何关于多项式的具体信息,验证者可以巩固某个多项式的值是可信的。

2. 多项式承诺

基于单多项式承诺,让我们继续进行多项式承诺。多项式意味着给定多个多项式,我们需要证明它们的值与承诺相匹配。在 PlonK 算法中,我们使用两种类型的多项式承诺。与单一多项式承诺不同,这需要 Vpc 提供两条随机消息。

原理很简单:(cm-si) + z(cm-si)/(xz) = x/(sz)(cm-si)。

3.多项式置换

PlonK 算法依赖于多项式置换的证明。这里的多项式置换意味着交换特定多项式的输入,输出不会改变。

4.Li(X)

Li(X) 指多项式中第 i 项的拉格朗日函数值。在有限子群 H 中,生成元为 g,幂为 n。如果a=g^i,则Li(a)=1;否则,Li(a) = 0。

使用 Li(X),我们可以将相等多项式的检查设置为范围检查。

Li(a)(Z(a) — Z(a)) = 0。这对 H 中的所有元素都成立,当且仅当 Li(a)=Z(g^i)。如果a属于g^i,Li(a)=1,那么Z(g^i)一定等于Z*(g^i)。如果a不属于g^i,Li(a) =0,则证明等式为真。

5. ID和排列

在我们进入多项式置换之前,我们需要定义多项式输入的 ID。因为在一个确定的领域,输入是g^i,输入可以用i间接表示。SID 是一个订单索引。Sigma(i) 是置换函数。

6. 置换协议

置换可能发生以下情况:

多项式值对应的置换。

该协议还可以有两种不同的情况:1/对相同多项式的输入进行置换 2/对多个多项式的输入进行置换。这两种情况由需要置换的多项式数量来区分。

单多项式的置换协议:

f' 和 g' 是新函数,它累积函数 f 和 g 的输入和输出值。它使用 beta 和 gamma 随机因子来防止 f 函数的信息泄漏。这里我们需要了解Z函数:Z函数是f'/g'(b)的乘法函数,Z(g)=1 (a)。通过简单的推导我们可以得到 Z(g^n) = 1,只要对输入信息进行置换。

根据上述Z函数的定义,我们可以知道Z(g^n) = 1。也就是说,f/g函数按照约定置换。

多个多项式的置换一致:

点标记可以扩展到多个多项式。换句话说,多个多项式的输入信息被连续索引。

基于单个多项式的一致性,我们将多项式相乘,然后计算函数Z。总之,我们可以通过验证两个多项式来确定多项式置换。置换协议也是后面会出现的“复制约束”的基础。

二. Fiat-Shamir 启发式算法

Fiat-Shamir 启发式算法有两种不同的类型:交互式和非交互式。有兴趣的可以看看wiki:

https://en.wikipedia.org/wiki/Fiat –Shamir_heuristic

1. 互动类型

为了证明 Peggy 知道一个特定的值 x。并且 y=g^x,Peggy 和 Victor 都选择一个随机数:v 和 c。Peggy 提供 g^v 和 r=v-cx,以便 Victor 可以验证。

2. 非交互类型

在交互类型算法中,Victor 必须提供一个随机数。在非交互类型中,这个随机数被公共哈希值代替。

PlonK 使用交互类型算法。

3.电路原理与约束系统

Vitalik 在他的博客上发布了一篇关于 PlonK 的文章,其中涵盖了电路原理。

https://vitalik.ca/general/2019/09/22/plonk.html

所谓约束系统,就是电路的约束规则。电路中的每个门都代表一个约束。该论文给出了一个具有 2 个输入和无限输出的电路。假设一个电路包含 n 个门和 m 个线 m,其中 n<=m<=2n。约束系统有两部分: 1/ 每个门的输入信息 2/ 门约束的系数向量。

V由左输入a、右输入b和输出c向量组成。请注意,a/b/c 只是索引。qL, qR, qO, qM, qC 是门的选择算子向量。L代表左。R是对的。O是输出,M是乘法,C是常数。

整个电路满足上式。也就是说,每个约束代表一加一乘。基于此定义,本文给出了表示特定电路的三种方式:1/ 算术电路(加法和乘法) 2/ 仅布尔值 3/ 仅公共输入值。公共输入只能解释为将输入固定为公共值。

总之,简而言之,PlonK 约束系统:

fL/fR/fO 是左/右/输出功能。这个约束系统有2个约束逻辑:

1/ 复制约束——门和门共享的线是正确的

2/ 每个门约束都是有效的

在这里,我对逻辑进行了一些澄清。对于一个有 2 个输入、无限输出的电路,如果它有 n 个门,那么最多存在 2n 个输入,我们将其写为 m。每个门都有左、右输入和输出。我们用 ai、bi 和 ci 标记它们,其中 0<=i<=n。i 是门的索引,而 ai 是X中输入或输出的索引。X ai 是那个输入或输出的值。通过排列,我们交换 i。简而言之,当我们计算某个输入或输出值的函数时,函数值会在两个不同的点上是相同的。这限制了一个门的输入/输出与另一个门的输入/输出连接。PLONK 在电路中的表示形式较少——每个门在 PLONK 中只有一个加法/乘法。R1CS 支持累加和乘法。

三. PlonK 协议

论文的最后一章,第 8 章给出了整个 PlonK 协议的结论。PlonK 协议基于多项式承诺和 Fiat-Shamir 启发式算法。给定 3n 见证,以及多项式的系数向量和置换函数,证明每个门都存在约束:

1. 公共信息

PlonK 协议公共信息,包括门系数、置换函数和公共输入。

2. 证明过程

证明过程有5轮。

第1轮:

计算 a(X)、b(X)、c(X) 的多项式形式,以及对应 SRS 的椭圆点。a/b/c对应协议中的fL/fR/fO。

第 2 轮:

使用 Fiat-Shamir 启发式算法生成随机数,并计算 z(X) 多项式和对应 SRS 的椭圆点。

第三轮:

用Fiat-Shamir启发式算法生成随机数,计算t(X)多项式和对应SRS的椭圆点。

请注意,t(X) 是核心,并将 3 个多项式合并为方程:

1/ 第一个方程对门电路施加约束

2/ 第二个和第三个方程满足“复制约束”并且门之间的链接满足方程

第四轮:

第 1 到第 3 轮正在计算多项式承诺。从第 4 轮开始,我们正在计算某些点的椭圆点。

使用 Fiat-Shamir 启发式算法生成随机数。计算a/b/c/t/z及其对应的置换函数值。

定义和计算 r 函数及其值。注意r函数和t函数是有关系的,我们在验证过程中会讲到这个关系。

第五轮:

使用 Fiat-Shamir 启发式算法生成随机数。计算多项式承诺的证明。证明多项式有两种类型:1/ a/b/c/t/r 和置换函数 2/ z 函数。

3. 验证过程

验证过程有一些简单的数据检查。主要步骤如下:

我们从第 12 步开始。整个验证过程只需要验证一个多项式承诺。核心计算是F-E。F是多项式承诺的值。E 是多项式挑战的值。多项式承诺保证挑战值等于承诺值。F计算过程中的D由r和z函数组成。

4. 如何约束

对于那些关注的人,您可能会好奇所有这些计算如何保证满足电路约束?即使多项式承诺与挑战相匹配,它也只能保证以下函数的多项式形式:

a/b/c 2. r 3. z 4. t 5. 置换函数 仔细看看 D 的计算(包括证明中的 r 函数)。我们可以发现 D 不是由验证者提供的。也就是在证明过程中没有提供r函数承诺值。验证者自己计算 D 承诺值,因此限制了 D 的多项式表达式。

在定义了 D 的多项式表达式之后,我们也间接定义了 r 函数表达式。

由第 8 步的计算,给出了 t 函数挑战值的计算公式。因为现在我们有了 r 函数表达式,我们也可以得到 t 函数表达式。然后我们仔细看看证明过程中的t函数表达式。由于 t 函数可以除以 ZH 函数,因此根处的值将为 0。这也证明了电路的3个多项式相等。

四. 性能比较

本文还在第一章中给出了性能比较。

1. 表现

假设有n个乘法门,加法门的个数等于乘法门(a=n)。线数 (m) 是总门数 (m=4n) 的两倍。G2 的计算是 G1 的 3 倍。然后:

1/ PlonK SRS 大小是Groth16 的1/4。

2/ PlonK证明的计算量约为Groth16的1.8倍。

3/ PlonK proof size 大约是 Groth16 的2.5 倍。

2. 验证性能

PlonK 验证花费的时间与 Groth16 几乎相同。

3. 结论

PlonK 算法实现了通用零知识证明。可信设置 (SRS) 需要一次。PlonK 电路由门组成,只支持乘法和加法。该电路需要证明门的输入/输出的有效性,以及线的关系。PlonK 的基础是多项式承诺。PlonK 使用智能方法通过多项式承诺来证明电路。

文章翻译自: https://starli.medium.com/zkp-plonk-algorithm-introduction-834556a32a