ZK 编年史：承诺方案（第 2 部分）

在之前的两篇文章中，我一直在暗示现代 ZK 系统如何依赖于（宽泛地说）将电路编码为多项式的方法。

虽然我们还不完全了解其工作原理，但使用这种策略将需要我们设计一种新类型的承诺方案。我们将不再对单个值进行承诺，而是对多项式本身进行承诺。

我估计这起初听起来可能很奇怪。但这实际上是我们很久以前在学习 sum-check 协议时暗示过的事情。

让我们动动脑筋，锻炼一下记忆肌肉！

我们当时谈到了对某些多项式拥有 Oracle 访问，但我们当时并不真正知道该如何实现。

今天就是揭开这个谜团的时候。有了这个，我们将做好所有准备，并完全准备好再次研究一些协议。

准备好了吗？我们开始吧！

动机

先想象一下这个“对多项式进行承诺”的过程将如何展开是个好主意。

其核心思想其实非常简单：我们不想检查电路中的所有门，而是想随机采样一些约束。

例如，连接到乘法门的导线应该遵循预期的 $a \cdot b = c$ 关系。或者，导线 $x$、$y$ 和 $z$ 应该具有相同的值。

然后，我们希望在能提供检查所需约束信息的位置对编码多项式进行求值，然后我们只需检查约束是否得到满足。

听起来很简单，对吧？

正如你现在可能已经预料到的那样，事情绝非那么简单。在这种情况下，问题在于这些编码多项式将至少与原始电路本身一样大……因此将这些多项式发送给验证者并不比发送对所有导线的承诺好多少！

就像我们在 Sigma 协议示例中所做的那样。记住，那并不是一个非常可扩展的策略。

为了使这行之有效，我们需要一种不同的方法。所以这里有一个想法：我们完全避免分享多项式怎么样？

Joey 不分享多项式！

从本质上讲，我们可以尝试设计一种让验证者请求求值的方法。这就是我们最初称之为对多项式的 Oracle 访问 的设置：你不需要自己计算求值，而是将工作量推给受信任的第三方。

然而，“信任”是一个我们必须谨慎使用的词。在证明者试图说服验证者的情况下，仅仅信任证明者提供正确的求值是灾难的根源。

因为这会打开作弊的闸门！

所以实际上，我们追求的是一种请求可验证的求值的方法：我要求在某个值 $a$ 处对某个多项式 $P(X)$ 进行求值，你计算它，但你不仅要回应 $P(a)$，还要附带一个小小的有效性证明或正确性证明。

这就是我们今天要研究的承诺方案的本质：多项式承诺方案，简称 PCS。我们将看到，正确性证明通常是针对相关多项式的初始承诺进行验证的——这也是这些东西被称为承诺方案的原因。

太棒了！这些前言足以让我们理解事情的发展方向。

让我们从简单的开始！

Merkle 树

我们要讨论的第一种多项式承诺方案是我们已经提到过的一种。这种策略虽然笨重，但很直接：只需一次性对每一个可能的函数值进行承诺！

没错！

我们已经见过这种方法的实际应用：我们要做的就是计算一个根，然后通过 Merkle 路径证明包含性。易如反掌！

局限性

然而，早在几篇文章前第一次讨论这个想法时，我们就立即发现了该方法的一个问题。我们注意到这是对多个值进行承诺的好方法，但我们如何知道这些值确实来自一个多项式呢？

事实上，Merkle 树是对 $n$ 个任意值进行承诺的好方法，但证明它们是多项式求值需要额外的一点努力。

解决方案是一种称为快速 Reed-Solomon 交互式 Oracle 证明（简称 FRI）的技术。

那到底是什么东西？？

是的，我知道这个名字听起来很吓人。它实际上相当复杂，所以我们将把细节留到以后，当我们看到一种称为 STARK 的证明系统时再说。

即使没有必要深入研究细节，我也可以提前告诉你：FRI 能做的最好的事情就是证明所承诺的多项式的度数低于某个上限 $d$。这就是我们所能知道的全部！

在某些语境下这已经足够了，但在大多数情况下并非如此。我们经常需要更强的保证，在我们的案例中，这意味着获得精确的度数界限。

为什么？还记得我们说过我们将电路编码为多项式吗？编码策略的成功取决于电路大小和多项式度数之间的精确关系。

获得这些保证绝对是可能的。但为此，我们将需要另一件密码学机器。

配对 (Pairings)

自从我们将群引入我们的工具箱以来，我们生成的每一个构造都存在于单一群中。这完全没问题，因为我们一直利用离散对数问题，所以一切都建立在某种坚实的安全性假设之上。

哎呀，在单一群中能做的事情也就这么多。

特别是，我们稍后将要研究的承诺方案是基于我们已经知道是有问题的东西：指数相乘。指数相加很容易：

但是相乘呢？没戏。至少，如果我们只考虑标准的群运算的话！

幸运的是，我们可以使用一个工具来做到这一点：配对！它们正是为了这个原因而存在的：允许我们某种程度上将来自不同的群的元素相乘。

这就是配对发挥作用的地方：它们允许我们某种程度上将来自不同的群的元素相乘。

这听起来像是一个简单的任务，但实际上要做好它极其复杂。它们背后的数学既优雅又晦涩，所以我们不会深入研究使配对成为可能的内部机制。我们只关心它们是否存在，以及某些值得信赖的密码学家是否已经实现了一个我们可以使用的优秀库。

然而，如果你真的、非常想知道配对是如何工作的，我不会阻止你。这是一个精彩的话题。你可以在这里阅读更多相关内容。尽管你可能需要从这里开始以掌握一些重要的基础概念。

定义和属性

那么让我们来看看定义。配对是一个函数或映射，它接受两个来自不同群的输入，并产生一个属于另一个群的输出：

不过，并非所有此类映射都是配对。为了被视为配对，它必须满足一个特殊的属性，称为双线性。使用我们信任的指数符号，这可以总结为：

从本质上讲，双线性赋予了我们移动指数的位置的能力。而这种简单的重新排列允许我们做一些非常酷的事情。

为了使这一点更完整，我还应该提到，我们需要这些映射是非退化的（对于生成元 $g$ 和 $h$，$e(g, h) \neq 1$），并且是可有效计算的。

这就是配对。同样，我们将在可以找到此类函数的假设下继续前进。

嘿，我没意见！

好的！但为什么配对如此特殊？

判定性 Diffie-Hellman

事实上，它们的存在使它们因为错误的原因而变得特殊：它们碰巧破解了一个问题，而这个问题以前被认为是困难的。

在密码学中，这通常不是一件好事。

为了充分理解配对的力量，我们需要谈谈那个假设，它与我们熟知的离散对数问题有关。

设置如下：想象我们有一个大群，我给你三个群元素：$g^a$、$g^b$ 和 $h$。问题很简单：你能确定 $h$ 是否等于 $g^{ab}$ 吗？

思考一下。我们不是在问 $h$ 是否等于 $g^{a+b}$，因为那是微不足道的。不，我们问的是 $a$ 和 $b$ 的乘积。如果我们预先知道 $a$ 和 $b$，当然可以进行计算。但反过来则需要我们解决离散对数问题，正如我们所知，这是很难破解的。

这就是我们所说的判定性 Diffie-Hellman 问题，简称 DDH。假设这个问题是困难的，是一些流行加密系统安全性的关键，比如 Diffie-Hellman 密钥交换和 ElGamal 加密。

然而，情况是这样的：配对破解了 DDH。有办法创建我们称之为自配对的东西，它使用来自同一个群的输入，并简单地检查这一点：

然后你就得到了答案。

那么，如果配对破解了 DDH……配对是否危险？

一点也不！或者至少，如果它们容易找到的话，它们会是危险的。

另外，作为一个旁注：请注意，即使我们能够破解 DDH，离散对数问题 (DLP) 仍是未受影响的。理解它们是不同的问题很重要。任何方法的安全性都取决于它所依赖的困难问题！

如果没有明确的方向，构造配对就像大海捞针。因此，依赖 DDH 难度的协议可能是安全的，因为寻找可以用来破解它们的配对被认为在实践中是不可能的。

相反，如果我们知道该往哪看，我们就可以生成配对。它们是由椭圆曲线群构造的，而且并非任何椭圆曲线都可以：有一类子曲线被称为配对友好曲线，它们具有非常特殊特性，使得构造配对成为现实。只有在这些情况下，DDH 才是容易的。

这里有一个大胆的看法：破解 DDH 真的是一件坏事吗？答案取决于语境：如果我们用它来破解协议，那么，是的。但如果我们能用它来构建东西呢？那么它就是一种恩赐而不是诅咒！

好吧！我们已经拥有了继续前进所需的一切。但在跳入好东西之前，有一件重要的事情我们需要处理。

设置 (Setups)

我们即将研究的多项式承诺方案的成功和效率在很大程度上取决于预处理步骤的存在。

我们可以将设置分为两类：可信的和透明的。两者都会产生一组公共参数，稍后用于制作打开证明，但这两类之间的主要区别在于，可信设置需要在过程中生成一个秘密值。

这个值相当令人讨厌。如果它在设置后没有被丢弃或销毁，后果将是毁灭性的：任何知道这个值的人都可以为虚假陈述伪造有效的证明。

出于这个原因，这个秘密值通常被称为“有毒废料”。

这就是为什么这类设置是可信的：我们相信运行预处理的人会丢弃这个值。相反，透明设置不需要这些潜在有害的秘密，因此它们在安全性方面算是一种黄金标准。

然而，一些多项式承诺方案仍然选择使用可信设置。显而易见的问题是为什么？为什么要心甘情愿地选择一种有如此大缺陷的策略？

实际上有两个原因。

首先，因为天下没有免费的午餐！透明设置通常伴随着性能成本。而在我们寻求构建高效证明系统的过程中，每一点开销都很重要。

其次，可信设置并不一定意味着盲目信任单一一方。这就是为什么这些设置通常以仪式的形式运行，许多独立的参与者可以贡献一点点随机性，最终参数由所有贡献组合而成。因此，任何人都无法完全知晓有毒废料。

这就是你目前需要知道的全部。处理完这些，我们终于可以专注于承诺方案本身了。

让我们疯狂起来吧！我们能想出什么样的疯狂构造？

KZG

事实证明，配对为我们提供了以几乎神奇的方式检查多项式打开所需的正确功能。

它们产生的最重要的方法之一归功于 Kate、Zaverucha 和 Goldberg，并且与 GKR 的命名方式类似，它被普及为 KZG 多项式承诺方案。

该过程共有三个步骤：预处理、承诺和打开。我认为最好按照这个顺序来处理它们，即使某些做法的原因不会立即显现出来。

相信这个过程！

可信设置

首先是预处理步骤。该步骤的输出被称为结构化参考字符串（或 SRS）：一组大小为 $d$ 的群元素。巧合的是，这个数字 $d$ 将是我们使用该 SRS 可以承诺的多项式的最大度数。

这是一个通用可信设置：我们运行一次过程，就可以用它来承诺任何度数最多为 $d$ 的多项式。正如我们稍后将看到的，其他一些方法使用每个电路独立的可信设置。从这个意义上说，通用设置更方便！

推导 SRS 实际上非常简单。首先，我们需要一个素数阶为 $p$ 的群 $\mathbb{G}$，以及一个生成元 $g$。然后，我们需要从域 $\mathbb{F}_p$ 中采样一个随机非零值。如果我们称该随机值为 $\tau$，那么 SRS 由以下 $g$ 的幂组成：

自然地，我们谈论过的有毒废料就是 $\tau$。我们稍后会看到如何伪造虚假证明——但与此同时，请注意我们无法从 SRS 中恢复 $\tau$，因为那需要我们解决离散对数问题！

一旦我们有了 SRS，对任何度数最多为 $d$ 的多项式 $Q(X)$ 进行承诺就非常简单了，因为我们只需要计算：

等一下。我们刚才不是说 $\tau$ 绝对必须被丢弃吗？那么，如果 $\tau$ 是未知的，谁能计算出 $c$ 呢？

的确，直接计算是不可能的。但我们可以使用一个巧妙的变通方法，这与 SRS 的精确形式有关。我们需要做的就是取出 $Q(X)$ 的系数 $q_i$，然后在这里计算这个乘积：

它看起来可能很吓人，但我们要做的只是取出 SRS 中的每个值，并将它们提升到相应的系数（意味着它们共享相同的索引），然后将所有内容相乘。很容易证明这等于 $c$：

这本身就很令人满意，不是吗？另外，请注意 $c$ 是 $\mathbb{G}$ 的一个元素。

整洁！我们有了我们的承诺，可以与验证者共享。现在我们可以专注于行动了。

打开一个求值

此时，验证者将要求计算了承诺的证明者在某个选定的值 $z$ 处打开多项式。当然，他们会计算 $v = Q(z)$，但仅发送该值是不够的：他们需要附带一个有效性证明供验证者检查。

自然地，我们需要弄清楚如何构建证明 $\pi$。这就是事情变得有点棘手的地方。

在我们开始使用配对之前，我们首先需要构建所谓的见证多项式。这是一个巧妙的小技巧，但由于它是 KZG 成功的关键部分，因此需要特别注意。

我们所做的本质上是将断言 $v = Q(z)$ 转换为实际上可以检查的东西。为此，我们将多项 $H(X)$ 定义为：

从表面上看，这似乎无关紧要。然而，我们知道关于这个多项式的一些事情，我们可以利用这些事情：它在 $X = z$ 处有一个根。

只要证明者是诚实的，并且 $v = Q(z)$ 确实成立！

如果我们知道关于根%20are%20defined.-,Roots,-Let%E2%80%99s%20recap%20our)的一件事，那就是我们可以将多项式重写为：

那里的 $W(X)$ 是 $H(X)$ 和 $(X - z)$ 的商多项式。换句话说，$(X - z)$ 完美地整除了 $H(X)$，没有余数：

再次强调，只有在求值 $v = Q(z)$ 正确的情况下，这才是真的。

完美！这实际上就是我们需要的一切，因为证明 $\pi$ 是从这个见证多项式计算出来的，它简单地为：

我们再次使用 SRS 来计算它。

是的，我知道这有点令人困惑——但我们还没有进入更疯狂的部分。因为现在，验证者必须使用原始承诺 $c$ 来检查该证明。这就是需要配对的部分。

我们将需要群 $\mathbb{G}$ 和 $\mathbb{G}_t$ 之间的自配对，通过它，验证者将检查这里的这个等式：

啊啊啊

我知道，这非常烧脑！我建议喘口气，充分理解这一点。事实上，我邀请你尝试检查该表达式的正确性——这是一个掌握双线性如何工作的有趣小练习。从核心上看，这所做的是检查承诺和证明是一致的，使用见证多项式关系和双线性将一切联系在一起。

证明它是绑定的要稍微复杂一些，但核心思想是，为错误的 $v$ 生成一个有效证明 $\pi$ 相当于解决我们之前讨论过的 DDH 问题的一个变体，即使对于配对友好群，该问题仍然是困难的！

这就是全盛时期的 KZG！

破解该方案

在结束这种方法的章节之前，我想向你展示一下，如果知道秘密 $\tau$，破解它是多么容易，这样我们就能充分衡量丢弃它的重要性。

假设有一秒钟 $\tau$ 是已知的。验证者要求打开 $Q(z)$，尽管正确的求值是 $v = Q(z)$，但我们想说服他们结果实际上是某个其他值 $y$。我们需要做什么来实现这一点？

我们需要做的是伪造一个证明 $\pi'$，使其通过验证。仅此而已！所以让我们从那里倒推。

正在执行的检查依赖于见证多项式的预期结构：之所以可以除以 $Q(X) - v$，是因为我们知道在 $X = z$ 处有一个根。这给了我们一组系数，我们可以使用 SRS 计算 $\pi$，因为这是在不知道 $\tau$ 的情况下获得 $\pi$ 的唯一方法。

如果我们尝试为虚假值 $y$ 计算见证多项式，我们会遇到一个问题，因为 $y$ 不是我们原始 $H(X)$ 的根，因此在除以 $(X - z)$ 时会有一个余项。所以，这个表达式在这里不会是一个多项式：

但是……如果我们知道 $\tau$，那么谁在乎呢？你可以直接直接地计算 $W'(\tau)$！而虚假证明就只是：

只是这一次，我们能够直接计算它。

就是这样。产生那个伪造证明并不费多少功夫。因此需要摆脱秘密值。它确实是有毒废料。

呼！内容真多！

我们可以进一步分析这一点，但我认为这里讲得已经够多了。

写完这些后我的大脑已经糊涂了，我可以想象你们在阅读时也有同感！

KZG 的精妙之处在于承诺和证明都是单个群元素。这非常精简，非常适合保持即将推出的协议成本低廉。这是一个很好的卖点——但只有在我们有能力保持秘密值 $\tau$ 不被泄露的情况下才有效。

总结

至此，我们有了第一个功能齐全的多项式承诺方案！

这意味着我们至少有一种方法来处理我们在之前的交流中谈到的那些 Oracle 查询。这不仅完成了我们对很久以前的 sum-check 协议的描述，而且还开启了一个全新的可能性世界。

当然，KZG 并不是唯一的可能解决方案（我们已经提到了 FRI，但我们还将探索其他选项），研究人员继续提出新的、改进的 PCS，可以使可验证计算更加高效。

尽管我必须说，KZG 已经是一个非常优雅的解决方案了，尤其是在通信方面非常精简：对多项式的承诺和正确性证明都是单个群元素。当我们开始将其插入完整的证明系统时，这将变得非常重要！

至关重要的是，我们引入了一个非常有用的重要数学工具：配对！

KZG 最受质疑的方面也许是它的可信设置。我对此一直很坚持，因为我们知道存在更安全设置的可能性。

尽管存在权衡，但这绝对是我们绝对需要探索的方向。

为了实现这一目标，我希望我们接下来探索整个家族的知识论证，其中包括一组非常重要的想法，这些想法绝对是我们追求零知识过程中必不可少的。

所以我们在下一篇再见！

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