ZKP 底层协议 | 理解 PLONK

---

引言

「深入 ZKP 底层系列」

• 背景
  当下，ZKP（Zero-Knowledge Proof） 已经在加密货币、数据隐私保护、安全认证等多个领域发挥着至关重要的作用。Plancker Langlands 小组现也已启动 zkp 研究，专注于通过硬件加速 MSM 与 NTT 等运算，提高 ZKP 中 proof 的生成速度。ZKP 的底层协议是零知识证明技术的核心和灵魂，在本系列中，我们将一起带你深入展开探索。
• 文章概述
  PLONK 协议对于 ZKP 发展意义深远，通过提供一个高效、通用且易于实现的框架，大大推动了 ZKP 技术在各种应用中的实用性和可扩展性，著名的 ZK 公链 - Mina Network 在其底层就使用了 PLONK 协议。本文主要讲了 PLONK 协议的工作原理以及一些升级优化。
  
• 本文作者：David，zkSecurity^[1] 联创，Real-World Cryptography book^[2] 作者，crypto architect of Mina Netowrk
  
• 原文链接：https://www.cryptologie.net/article/527/understanding-plonk/

---

正文

PLONK^[3] 是通用证明系统的最先进技术。虽然该论文于 2019 年发布，但有了一些更新，并且该方案仍在不断发展（Aztec 宣布 UltraPLONK^[4] 版本即将推出）。PLONK 是我们在 Mina^[5] 使用的方案，能将区块链的大小从千兆字节压缩到十几千字节的固定大小。

通用证明系统
在零知识证明（ZK, Zero-Knowledge Proof）的领域中通常指的是一种能够支持各种不同陈述（statements）或断言的证明系统。
这样的系统可以被用来证明各种各样的属性或条件，而不仅仅限于特定的领域或应用

虽然这个方案或计划的基本理念相对容易理解，但是由于其中包含了大量的优化技术和细节，这些复杂的内容使得整个方案变得难以彻底弄懂。在这篇文章中，我希望对该方案的某些方面进行阐释。当然，这是在我假设你知道 PlONK 这个算法如何运行的情况下。

PLONK 的工作原理（简单版本）

PLONK 这个概念的最终目的是为了证明 —— 在某个特定范围 内，有一个多项式 的值是零。换句话说，PLONK 的目标是表示存在这样一个数学公式（多项式），当我们把这个特定范围 内的数值代入这个公式时，计算得到的结果总是 0。这个范围 是在一个更大的数集  里面挑选出来的一部分。（我会先不考虑排列论证，那是另一回事）。为了证明前面提到的，我们把问题转化成另一个问题，这个过程可以逐步这样理解：

• 证明先前的声明，即在某个特定范围 内，有一个多项式 ，其实就等同于证明这个多项式 能被 整除。 是一个有着 中所有元素作为根的多项式（也被称为消失多项式或零化多项式）。

• 这又等同于证明以下的等式（假设这个商多项式为 ，对于某个商多项式 来说）：

零化/消失多项式（vanishing polynomial）
这种多项式在其定义的某些特定值上的计算结果为零。
在数学和密码学的特定领域，如零知识证明中，这个概念被频繁使用。

这相当于在一个随机选择的点 上证明一个等式是成立的（这是基于 Schwartz-Zippel^[6] 定理）。

Schwartz-Zippel 定理
这个定理帮助我们判断两个多项式是否相同。它告诉我们，通过在多项式中随机代入数值进行检验，我们可以以很高的概率确定这两个多项式是否一样。
这个定理在算法设计和错误检测等领域非常有用，特别是在那些涉及多项式的应用中。

为了证明这个结论，证明者（Prover）使用了一种多项式承诺方案（具体来说是 KZG 方案），来对多项式 和 进行承诺。然后，证明者将这些承诺发送给验证者（Verifier）。这时，验证者需要检查在某个随机点 上这个承诺是否成立。

这个过程是通过（验证者）向证明者发送一个随机点 ，并在这一点上「开启」这些承诺来完成的 —— 证明者发送 和 的值，以及一个证明，向（验证者）表明这些是正确的计算结果。

简单来说，就是为了验证一个复杂的数学问题，证明者（Prover）用一种特殊的方法（KZG 方案）来保证他们所做的工作是可信的。
然后，他们把这个保证承诺发送给验证者（Verifier）。验证者随机挑选一个点，要求证明者在这一点上展示证明者的工作是正确的。
证明者提供在这一点上多项式的计算结果和证明，来表明自己的计算是正确的。

说到底，这就是 PLONK 协议的基本思想，但实际上，如果你仔细阅读相关的论文，会发现实际上协议的运作细节和这里描述的有所不同，真正的 PLONK 协议比这个简化的解释更复杂。

更多简化

在 PLONK 协议的更新版本中，它把上面的陈述做了进一步的简化：

• 正如前面部分所述，我们想证明的是一个数学上的等式或关系：

• 这相当于证明 是多项式 的根（也就是将 代入这个多项式后，多项式的值为零）。

• 由于验证者已经知道其中一个多项式（），他们可以提前计算它。所以就变成证明： 是 的根。

上面最后两步是一种优化（称为 Maller 的优化^[7]），这个优化减少了证明者需要发送的信息量。具体来说，它不需要证明者发送，因为验证者可以利用对 的承诺来生成对 的承诺（以验证开启证明）。

开启证明（proof of opening） 指一种特定类型的证明，它用于验证在特定点上的多项式承诺是否正确。具体来说，它涉及以下几个步骤：

• 多项式承诺：证明者（Prover）首先对一个多项式进行「承诺」。承诺相当于对这个多项式的内容做一个加密的保证，同时不暴露具体的多项式。
• 选择点：验证者（Verifier）选择一个点（通常是随机的），要求证明者在这个点上「开启」他们的承诺。
• 提供证据：证明者然后提供证据，证明他们的多项式在这个特定点的值是正确的。这个证据需要足够强，能够让验证者相信证明者的确持有这个特定多项式，而且它在选定的点上的值是正确的。

这些额外的简化使得协议从一个证明者（Prover）需要发送开启（openings），以便验证者（Verifier）自行检查等式的协议，变成了一个证明者只需发送开启（opening）的协议。

在 时，为了开启 ，验证者首先需要重建一个对 的承诺。这很简单，方法是：

这这个方法将会用到：

• 在协议过程中接收到的对 的承诺
• 在协议过程中接收到的对 的承诺
• 验证者自己在 时对 的计算结果
  

没那么快， 太大了

如果你已经读过了 PLONK，你想必已经注意到证明者实际上不需要直接向 发送一个承诺，因为 实在是太大了，而多项式承诺方案在初始的可信阶段其实有一个固定的上限。（顺便说一句， 之所以太大了，是因为排列论证（permutation argument）的三个见证多项式让它变成了原来的三倍大。）因此，为了避免这种限制，这个多项式 被分成三个更小的多项式 ，例如：

这意味着在我们先前的协议中，我们无法直接证明 是 的根。

反过来，我们得证明 是等式 的根。

这不太妙，因为证明者现在不能再对 做出承诺了。原因是 和 超过了我们多项式承诺的上限，所以不能被承诺。但是请注意，因为验证者已经知道这些值，所以他们可以提前在 处计算这些值，并且改为要求证明：

简单来说，证明者不能对某个值 提供一个有效的承诺，因为涉及的数学运算超出了这个过程的处理能力。不过，因为验证者已经知道了一些必要的信息，他们可以自己先做一些计算，然后要求证明者提供不同类型的证明。

这是一个不错的需求，因为验证者可以产生 所需的验证开启证明的承诺：

此时，协议看起来看更像是这样：

哇哦，那 呢？

PLONK 协议中的主要证明实际上就涉及两个关键部分：

1. 排列论证，用于连接我们电路中的导线。我在这篇文章中没有涉及这个证明。
2. 主要的多项式 ，这就是我们的电路。

多项式 需要这样构造：

• 它不会向验证者泄露任何非公开信息；
• 它不允许证明者改变电路的固定部分。

因此，证明者和验证者需要共跳一场「多项式舞蹈」，共同构造这个多项式。最终的产物大概是这样的：

其中 ，， 是证明者自己构建、承诺并发送给验证者的私有多项式；而 ，，，， 是公开的多项式（选择器多项式：通常用于选择或激活特定的功能或属性），验证者和证明者都可以构建这些多项式（如果需要的话，还可以对它们进行承诺）。

所以最终的协议更像是这样的：

和上个部分一样，验证者需要在能够请求开启之前，给 重构一个承诺，但这个目前不可能，因为我们正在处理多个承诺的相乘（见下）：

但因为证明者在 上发送了 ，， 的计算结果（并附上证明），所以验证者可以用这些信息，把多项式 简化为：

最后，验证者能够以以下的形式生成对多项式 的承诺：

PLONK 还有很多其他内容。我跳过了关于电路的部分、排列论证，我也没有提及最后重要的配对方程（pairing equation）。这些内容将是另一篇文章的主题:)

---

参考资料[1]

zkSecurity: https://www.zksecurity.xyz/

[2]

Real-World Cryptography book: https://www.manning.com/books/real-world-cryptography?a_aid=Realworldcrypto&a_bid=ad500e09

[3]

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

[4]

UltraPLONK: https://aztec.network/

[5]

Mina: https://minaprotocol.com/

[6]

Schwartz-Zippel: https://www.cryptologie.net/article/507/the-missing-explanation-of-zk-snarks-part-1/

[7]

Maller 的优化: https://www.cryptologie.net/article/526/maller-optimization-to-reduce-proof-size/

---

编译&排版：Purple

技术校对：Harold

*如果对相关内容感兴趣，欢迎评论区留言与我们交流

/ About  Plancker

PlanckerDAO 是一个专注建设以太坊生态的社区，我们为开发者、产品经理和研究员提供多方面支持，致力于与以太坊共建人类的数字化美好未来。

Website：https://plancker.org/

Notion：planckerdao.notion.site

Forum：http://forum.plancker.org/

Telegram：https://t.me/PlanckerDAO

Twitter：https://twitter.com/PlanckerDao