密码学101：承诺方案再探

这是关于密码学的一系列文章中的一部分。如果这是你遇到的第一篇文章，我强烈建议你从系列的开头开始。

好的！到目前为止，我们已经在_基于身份的密码学_的背景下看到了配对的应用。但我们也看到，配对本身是强大的，可以实现不依赖于 身份 的其他方法。在这篇文章中，我希望能针对这个想法进行扩展。

现在是时候重新审视几篇文章前提到的一个概念：承诺方案 。我们之前定义了它们：以不提前透露的方式承诺某个 值。

这算是一种密码学反作弊机制。

这次，我们将看一个还没有提到的承诺方案类型：多项式承诺 。具体来说，要呈现的方法是这篇论文中描述的：KZG（Kate-Zaverucha-Goldberg）承诺。

简短的免责声明

我相信，到目前为止，在这个系列中，给文章贴上 101 的标签将会比较困难——因为它们不再 那么 入门。尽管如此，这些展示的精神是为了让论文中相对晦涩的内容和符号变得更容易接触。从这个意义上说，确实是我去掉了一些复杂的元素——即便如此，这并不意味着这些主题会变得更容易。

尽管如此，如果你已经阅读到这一点，可能意味着你非常致力于理解复杂的密码学概念。所以，恭喜你为此付出的努力，感谢你的阅读，我希望你仍然觉得内容有用！

提交给多项式

到目前为止，我们对承诺方案的描述只涵盖了一个场景，那就是有一个我们不想提前透露的秘密值。而_打开_承诺的意思就是_揭示_这个值。

但如果我们能拥有一个完整的 承诺工厂 呢？

也就是说，如果我们能够承诺一个 函数 ？那么我们所能做的就是向验证者提供函数的 评估值 ，而他们可以使用我们的承诺来检查其 正确性 。

什么？

公平地说，尽管这听起来像是一个很有趣的想法，但不 Immediate clear 是否有任何合适的应用。

为了保持你们的积极性，我想说：对一个函数进行承诺是我们将在将来的文章中要关注的一些_零知识证明_的关键成分。

此外，回想一下，当我们谈论门限密码学时，我们提到过某些情况需要可验证的秘密共享。即，不仅需要某个多项式的评估值，而且还需要其正确性的证明。

多项式承诺方案可以对此提供帮助。

背景是（有点儿）设定好了。也许一个图解会帮助澄清我之前的意思：

大体来说，我们计划要做的事情

注意，在上面的图示中，函数 f 是 秘密的 ，并且从未真正披露。正如你现在可能猜到的那样，_一致性检查_将借助于_配对_进行。

话虽如此，让我们直接进入正题。

设置

我们的承诺方案将由至少_三个步骤_组成。论文本身描述了大约六个算法，但我们可以简化一些，以使解释更易懂。

首先，我们需要_两个_次序为_n_的群体：我们称它们为𝔾₁和𝔾₃。我们还需要一个𝔾₁的生成元，我们将其表示为G。这些群体的生成方式是存在一个对称配对（或[自配对](https://medium.com/@francomangone18/cryptography-101-pairings-e50520deea6c#:~:text=If%20you%20check,to%20be%20disjoint.）形式如下：

而这将是我们拼图中至关重要的一部分。

此外，由于我们将处理多项式，这次我们将更喜欢_乘法记号_来表示𝔾₁中的元素；也就是说，该组将有如下形式：

重要说明：由于G将是多项式的输入，我们通常以椭圆曲线群来展示实例，因此我们面临一个问题：椭圆曲线上的点是通过标量乘法（即[s]G）相乘，而不是进行指数运算。

为了缓解这个问题，我们可以利用同构关系转换为乘法群，使用类似的推理，如这里解释的.

所以实际上，Gˢ将仅意味着[s]G。

很好，很好。有了这些，我们可以真正开始设置系列的内容。

设置过程

现在，这个过程使用的是所谓的可信设置。为了使其工作，系统必须被初始化，在这个意义上，某些_公共参数_需要被计算。这些参数在验证过程中将很重要。

我们将对一个次数_最多为d_的多项式进行承诺。为此，这是我们所需的设置：一个_可信角色_随机采样一个整数α。他们用这个值计算以下一组公共参数：

在获得这些值后，α必须被丢弃。知道_α_意味着可能伪造虚假证明——这就是我们需要_信任_执行此操作的人的原因。稍后我们将看到如何产生虚假证明。

提交给多项式

一旦大家拥有了公共参数p，我们就可以创建实际的承诺了。

有趣的是，承诺将是一个单一的功能值：

我们将使用波浪符号（~）来表示对函数的承诺。

细看之下，我们可以看到，计算承诺_._时需要α。但是理论上，这在此时_已经被丢弃_了！那么，我们怎么可能计算这个呢？

记住在设置期间计算的_公共参数_吗？这就是它们派上用场的地方。因为我们的多项式的形式是：

我们可以生成以下产品，使用公共参数：

如果我们稍微整理一下表达式：

就是这样！在不知道_α_的情况下，我们仍然能够计算我们的承诺。这个值是由_证明者_计算的，并发送给验证者，后者将存储该值，并在将来需要验证多项式的其他_评估值_是否正确时使用。

让我们看看如何执行！

评估

在知道_承诺_的情况下，我们可以请求对秘密多项式的评估。回到我们最初的过程草图，这意味着验证者想要知道在某个特定的整数 b 上秘密多项式 f(x) 的值，因此他们实际上是询问值 f(b)：

证明者可以简单地计算这个，并将其发送给验证者，但验证者需要确保该计算是 正确的 和 一致的，并确保他们不是在接收一个随机、毫无意义的值。

因此，除了值 f(b)，证明者还需要生成一个 短证明，以便验证者可以 检验该证明与他们所持有的承诺 进行对比。

让我们深入看看这个证明是如何生成的。

证明

快速重申一下目标，我们想证明的是 f(b)= v 。稍微调整一下，也可以这样理解：

这意味着_b_是这个多项式的根：

通过这种简单的视角转换，最终能够生产出所需的证明。

感谢因式定理，我们知道 ĝ 可以被多项式 (x - b) 完美除尽（没有余数）。我们可以计算出 商多项式p(x)，即足够的多项式：

接下来发生的是计算对 p(x) 的 承诺 ；这正是我们用公共参数来做的。这个承诺将是我们所需要的短证明。因此，我们之前的图示可以这样更新：

在接收到多项式评估值 v 和对 p(x) 的承诺后，验证者可以检查这两个值是否有意义。事情在这里变得有趣。

到目前为止都明白吗？这一点让我读了几遍才能完全理解这个想法——如果需要，可以慢慢来。

还有剧透：接下来的部分可能比平常要复杂一点。哦，天哪。请做好准备。

是的，我知道。抱歉。很高兴你在这里！

验证

简单地说，验证者仅在以下验证真实的情况下接受评估：

这里显然有个问题：α被丢弃，所以是未知的。我们稍后将看到如何规避这个问题。但在此之前，让我们先确认这个表达式的合情合理性。

回顾一下承诺：给定一个多项式f，它只是这个值：

我们已经看到如何使用公共参数来计算这个。如果我们把它输入到验证表达式中，就得到：

仅检查指数我们可以看到：

当然，如果_p(x)_被正确计算并评估，我们就知道表达式（_α - b）。p(α)和(f(α) — v)_应该匹配。所以验证过程说得通！

在这里，我们可以清晰地看到，知道_α_会如何导致虚假证明的伪造。

你们看，我可以给你发一个任意数字A而不是_f(α)_作为初始承诺，而你根本没办法知道它并不合法。然后，因为我知道α，我可以选择一个任意的v，通过直接计算并将这个值P发送给你，来让你相信f(b) = v：

而最糟糕的是，你甚至不会有一点迹象表明这些证明是假的。所以，是的，确保_α_被丢弃是重要的！

总结：α仍然是未知的。我们该怎么办呢？

配对魔法

在这里，各位朋友，配对进来了。我将仅展示这个过程如何运作，然后我们将检查它是否合理。不需要过多的动机！

为了引入一些我们将使用的术语，我们称对 p(x) 的承诺——与值 b 相关的——为见证。并将其表示为 w(b)：

现在，想法是我们需要检查这个值是否与对_f_的承诺一致。为此，我们需要评估我们的配对，并检查：

哇哇哇。停一下，特瑞托。什么？

家庭的力量在这里可没帮上忙。

好的。让我们试图理清这个问题。

问题的关键在于，只有当_w(b)_被_正确计算_时，这两次评估才会产生相同的结果。而它只有在证明者_确实知道_秘密多项式的情况下才能被正确计算。

记住，群体中元素的指数表示实际上意味着椭圆曲线点乘法。

正式来说，我们可以看到，等式成立是因为，利用配对的双线性特性：

花一分钟时间。再读一遍。让它慢慢吸收。

如果你检查一下上面展开的所有参数，你会看到“较简单”的解释中第一次看到的元素被融入到了配对评估的混合中。

另外，注意我们使用了 G 和 Gᵃ （这是 G 的 α个 但没有上标 unicode α 字符）。这些值在_公共参数_中提供，实际上是前两个值：H₀ 和 H₁ 。所以，这是我们进行验证所需的所有公共参数！

太棒了，不是吗？

总结

我认为这篇文章绝对不容易追随。Medium估计的10分钟长度可能让人感觉像是在开玩笑。对此我表示歉意。我尽量保持简单！

为了获得不同且更具互动性的视角，我建议你查看Dan Boneh的这门课。虽然它没有涵盖配对验证，但几乎包括了所有其他内容。

因此，正如文章开头所提到的，这种构造本身在一开始似乎没有有趣的应用。尽管如此，我们将此作为其他构造的基础——特别是，构建强大的（零）知识证明家族：SNARKs。

然而，这并不是我们系列的下一个目标。相反，我们将在下一篇文章中讨论另一种形式的零知识证明：Bulletproofs（https://medium.com/@francomangone18/cryptography-101-zero-knowledge-proofs-part-1-53516825479c） 。这将自然为我们稍后接着讨论SNARKs铺平道路。下次再见！

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