零知识证明—PlonK算法介绍

PlonK是 P ermutations over L agrange-bases for O ecumenical N oninteractive arguments of K nowledge 的缩写。PlonK是通用零知识证明算法的一个实现。通用意味着可信设置只需要初始化一次。对熟悉Groth16的人来说，你应该知道每个电路在Groth16中都需要一个单独的可信设置。

你可以在这里访问PlonK的论文：

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

关于PlonK的这篇论文在8个章节中清晰地解释了技术逻辑。我的阅读顺序推荐：第一章（概述），第五章（电路设计），第二/三/四章（背景理论），第六/七/八章（约束系统和协议）。我强烈建议你看看这篇论文。

本文讨论了Plonk算法的原理以及协议证明/验证阶段的过程。

初始参数 SRS

对于那些了解Groth16的人来说，应该对CRS — 通用参考字符串有所了解。SRS仅有通用数据，即结构化参考字符串。

多项式承诺

批处理多项式承诺基于一个非常简单的理论，这恰好是PlonK最重要的基础。多项式承诺是为了证明多个多项式。论文解释了单一类型多项式承诺和多类型多项式（批处理）算法。

单一多项式承诺

在第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的情况下，认证者不会泄露关于多项式的任何具体信息，并且验证者可以确信某个多项式的值是值得信赖的。

多项式承诺

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

原理非常直接：（cm-si）+ z*(cm-si)/(x-z) = x/(s-z)*(cm-si)。

多项式置换

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

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，该方程成立。

ID与置换

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

置换协议

置换可能发生在以下情况：

多项式值对应的置换。

该协议还可能存在两种不同情况：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启发式算法有两种不同的类型：交互式和非交互式。如果感兴趣，可以查看维基：

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

交互式类型：

证明Peggy知道某一特定值x，且y=g^x，Peggy和Victor都选择一个随机数：v和c。Peggy提供g^v和r=v-cx，以便Victor进行验证。

非交互式类型：

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

PlonK使用交互式算法。

电路原理与约束系统

Vitalik在他的博客上发表了关于PlonK的文章，涉及电路的原理。

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

所谓的约束系统只是电路的约束规则。电路中的每个门表示一个约束。论文给出了一个具有2个输入和无限输出的电路。假设一个电路包含n个门和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见证、一个多项式的系数向量和置换函数，证明每个门的约束存在：

公共信息

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

证明过程：

证明过程有5轮。

第一轮：

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

第二轮：

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

第三轮：

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

注意t(X)是核心，将3个多项式融入方程中：

1/ 第一个方程对门电路设置约束

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

第四轮：

第一轮到第三轮是计算多项式承诺。从第四轮开始，我们计算某些点的椭圆点。

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

定义并计算r函数及其值。注意r函数与t函数相关，我们将在验证过程中讨论这种关系。

第五轮：

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

验证过程：

验证过程有一些简单的数据检查。主要步骤列在下面：

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

如何约束？

对于关注这一点的人来说，你可能会好奇这些计算如何保证满足电路约束？即使多项式承诺与挑战匹配，它只能保证以下函数的多项式形式：

1. 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个多项式是相等的。

性能比较

论文在第一章中也给出了性能比较。

性能

假设有n个乘法门，且加法门的数量与乘法门数量相等（a=n）。线路数量（m）是总门数量的两倍（m=4n）。G2的计算是G1的三倍。 然后：

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

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

3/ PlonK证明的大小约为 2.5倍 的Groth16。

验证性能

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

结论：

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

• 原文链接： trapdoortech.medium.com/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～