Vitalik：多项式承诺如何让 zk-SNARK 的实现更加高效？

原文标题：An approximate introduction to how zk-SNARKs are possible

原文作者：Vitalik Buterin

原文来源：vitalik.ca

编者注：说到过去十年来诞生的最强密码学技术，肯定免不了提及零知识证明 (zero knowledge proof)。在区块链领域中，它们有两大应用场景：可扩展性和隐私。zk-SNARK 作为其中一种 zkp 技术，在近几年来也得到了较大的突破，以太坊上出现了诸如 zkSync、Scroll、Hermez 等此类使用 zk-SNARK 证明的通用扩容解决方案。

然而，实现 zk-SNARK 并不简单，因为对某个声明生成了 zk-SNARK 证明之后，验证者需要以某种方式检查计算中的数百万个步骤。多项式承诺就是在这里发挥其作用，即可以将计算编码为多项式，然后使用一种特殊类型的多项式“哈希”(多项式承诺)，以允许验证者在极短的时间内验证多项式等式，即便这些计算背后的多项式规模无比大。

在本文中，Vitalik 介绍了 zk-SNARK 技术的工作原理和难点，然后解释了多项式以及多项式承诺如何让 zk-SNARK 的实现更加高效。

特别感谢 Dankrad Feist、Karl Floersch 以及 Hsiao-wei Wan 的反馈和校对。

过去十年来诞生的最强密码学技术大概要数通用简洁零知识证明，通常称为 zk-SNARK（zero knowledge succinct arguments of knowledge）。zk-SNARK 允许你生成一个证明 (这个证明是针对一些运算得出的特定输出，可用于对该运算的验证)，通过这种方式，即使底层计算十分耗时，该证明也可以被快速验证。“ZK”（零知识）为证明新增了一个额外特性：证明可以隐藏计算的某些输入。

例如，您可以对以下声明生成一个证明：“我知道一个秘密值，如果你将数字添加到挑选的单词 cow 的末尾，然后对其进行 1 亿次 SHA256 哈希运算，那么输出的哈希值以 0x57d00485aa 开头”。验证者验证该证明的耗时可远小于自行进行 1 亿次哈希运算的耗时，而且证明也不会泄漏秘密值。

在区块链领域中，该技术有两大应用场景：

1. 可扩展性：如果一个区块的验证十分耗时，某个人可以验证区块并生成一个证明，而其他人只需快速地验证证明即可

2. 隐私：你可以证明你有权转移某些资产（你收到了该资产，而且你还没有转走），而不透露该资产的来源。这不会对外泄漏交易双方的信息，确保了交易的安全性。

然而，zk-SNARK 是相当复杂的；实际上，就在 2014-17 年，它们还常被称为“月亮数学”。好消息是，从那时起，协议愈发简化，我们对它们的理解也愈发深入。本篇博客将试图以一种数学水平普通的人能理解的方式来解释 ZK-SNARKs 的工作原理。

注意，我们将聚焦于可扩展性；一旦有了可扩展性，这些协议的隐私性就相对容易实现，因此我们将在最后回归这个主题。

为什么 ZK-SNARK “会”很难

以开头例子为例：我们有一个数字（我们可以将末尾跟着秘密输入的 “cow” 整体编码为一个整数），我们计算该数字的 SHA256 哈希，然后重复做 9999999 次，最后我们检查输出的开头。这里面的计算量特别大。

一个“简洁（succinct）”证明指的是证明大小和验证耗时的增长远慢于需验证计算量的增长。如果我们想要一个“简洁”证明，我们就不能要求验证者在每轮哈希中做一些运算（因为那样的话，验证耗时将与计算量成正比）。相反，验证者必须以某种方式检查整个运算过程，而不必窥视运算过程中的每个部分。

有一种自然的技术就是随机抽样：让验证者只在 500 个不同的地方检查运算的正确性，如果所有的 500 个检查都通过了，那么认为运算过程的其余部分也大概率没问题？

该流程甚至可以通过使用 Fiat-Shamir 启发式（Fiat-Shamir heuristic）转化为非交互式证明：证明者计算运算过程的默克尔根，基于默克尔根伪随机地选取 500 个索引，并提供对应的 500 个默克尔分支。核心思想是证明者并不知道将要揭示哪些分支，直到他们已经对数据生成了“承诺”。如果恶意证明者在了解到需要检查哪些索引后试图篡改数据，那么这会改变默克尔根的值，而这将导致一组新随机索引被选出，这将需要再次去篡改数据…让恶意证明者陷入无休止的循环中，无法达成目的。

但不幸的是，简单地随机抽查运算过程存在一个致命的缺陷：运算过程本身并不健壮。如果恶意证明者在计算过程中的某个位置翻转一个比特，可以导致一个完全不同的结果，而随机抽样验证者几乎永远不会发现。

只需一次故意的插入错误，就会导致计算得出完全错误的结果，而这几乎不会被随机检查所捕获。

如果要提出一个 zk-SNARK 协议，那么很多人会走到上面这步，然后陷入困境，最终放弃。不单独查看每个计算片段的情况下，验证者究竟如何才能够校验每个计算片段？事实证明，有一个绝妙的解决方案。

多项式

多项式是一类特殊的代数表达式，具有以下形式：

• x+5

• x4

• x3

• +3x2

• +3x+1

• 628x271

• +318x270

• +530x269

• +…+69x+381

也就是说，它们是有限个形式为 cxk 的项之和。

多项式有许多有趣的特性。但这里，我们将聚焦于多项式的一个特性：多项式是一个可以包含无限信息量（多项式显然可视为一个整数列表）的单一数学对象上。面的第四个示例包含 tau 的 816 位的信息，而且我们能够很容易地想象出一个包含更多信息量的多项式。

此外，多项式间的单个等式就能够表示无限个数间的方程。例如，考虑等式 A(x)+B(x)=C(x)。如果该等式是正确的，那么下面也是正确的：

• A(0)+B(0)=C(0)

• A(1)+B(1)=C(1)

• A(2)+B(2)=C(2)

• A(3)+B(3)=C(3)

可以类推到每个可能的下标。甚至，你可以构造特地表示一组数字的多项式，这样你就可以一次性地检查众多等式。例如，假设您想检查：

• 12 + 1 = 13

• 10 + 8 = 18

• 15 + 8 = 23

• 15 + 13 = 28

您可以使用一个名为拉格朗日插值的方法来构造多项式：A(x) 在某些特定下标集合（例如 (0，1，2，3) 上的输出为 (12，10，15，15)），B(x) 在相同下标上的输出为 (1，8，8，13)，如此类推。准确地说，以下是相应的多项式：

用这些多项式校验等式 A(x)+B(x)=C(x) 相当于同时校验上述四个等式。

将多项式与自身进行比较

甚至，你可以用一个简单的多项式等式来校验相同多项式的大量相邻取值的关系。这稍微更进一步。假设您想校验，对于给定的多项式 F，在整数范围 {0,1…98} 内满足 F(x+2)=F(x)+F(x+1)（因此，如果您还校验F(0)=F(1)=1，那么 F(100) 将是第 100 个斐波拉契数）。

作为多项式，F(x+2)