详解 KZG 如何应用于 zk-rollup 以及以太坊 DA 方案

原文作者：Scroll 研究员 Andy Arditi

编译： DeFi 之道

感谢 Yi Sun 和 Kobi Gurkan 的反馈和评论。

简介

由于数学复杂性，零知识证明在其周围形成了一种神秘的气质，它们被亲切地称为“月球数学”，因为它们被大多数人视为超凡脱俗的魔法。

我们 Scroll 想要揭开零知识证明内部运作的神秘面纱，这并没有让它们变得不那么神奇，但我们认为帮助社区了解这些技术是很重要的。

在这篇文章中，我们介绍了很多零知识证明系统的关键要素：多项式承诺（polynomial commitment）方案。然后我们简要解释一下 KZG，它是实践中使用最广泛的多项式承诺方案之一。接着，我们会继续讨论如何在 Scroll 的 zk-rollups 以及以太坊的 Proto-Danksharding 中使用 KZG。最后，我们展示了 zk-rollups 以及 Proto-Danksharding 如何能够高效、优雅地相互集成——这种集成是通过它们各自使用多项式承诺方案来实现的。

为什么我们要讨论多项式？

多项式是非常强大的工具，它们在很多不同领域都有有用的应用。 多项式可用于以一种有效的方式表示大型对象。

我们可以表示为多项式的一个标准对象是域元素

的 n 维向量。我们可以制作一个多项式 ϕ(x) ，通过确保 ϕ(x) 通过点 (i,vi)（i=1,2,…,n）来表示 v。

例如，我们可以取 3 维向量 v =[2,0,6]，并将其表示为多项式 ϕ(x)=4x^2−14x+12. 你可以插入值来验证 ϕ(1)=2, ϕ(2) = 0 ，以及 ϕ(3)=6。这样，多项式 ϕ(x) “编码”了向量 v。

总的来说，取 n 个任意点，并找到一个唯一的 n-1 次多项式（它通过所有这些点）是可能的。 这个过程被称为“多项式插值”，并且有人已建立了有效完成这个任务的方法。 （查看 Wolfram Alpha 提供的这个漂亮的在线工具‌，它可以在给定输入向量的情况下插值多项式！）

什么是多项式承诺（polynomial commitment）方案？为什么它们是有用的？

多项式承诺方案是具有一些不错的附加属性的承诺方案。在一般的承诺方案中，committer 通过输出一些 commitment c 来承诺一则消息 m。committer 随后可以显示消息 m，验证者可以验证 commitment c 确实对应于 m。承诺方案应该是“绑定的”（一旦发布 c，committer 应该无法找到其他一些消息，即发布 c 不应泄露有关底层消息 m 的任何信息）。

现在，使用多项式承诺方案，committer 提交一个多项式 ϕ，而不是一些任意消息 m。多项式承诺方案满足上述正常承诺方案的属性，并且还实现了一个附加属性：committer 应该能够“开放”对承诺多项式的某些评估，而不会透露整个事情。例如，committer 应该能够证明 ϕ(a)=b 而无需确切透露 ϕ(x) 是什么。

这是一个非常棒的属性，它对于零知识应用是非常有用的！我们可用它来证明我们有一些满足某些性质的多项式（在这种情况下，它通过某个点 (a,b)），而无需揭示多项式是什么！

这个属性有用的另一个原因是，commitment c 通常比它所代表的多项式要小得多。我们将看到一个承诺方案，其中任意大次数的多项式可以通过其 commitment 表示为单个组元素。当考虑在链上发布数据时，这尤为可取，因为区块空间是一种宝贵的资产，任何形式的压缩都可立即转化为成本上的节约。

KZG 多项式承诺方案

好的，现在我们已经简单了解了多项式承诺方案，让我们看看如何实际构建一个。 我们将关注的是一个称为 Kate-Zaverucha-Goldberg‌ (简称 KZG) 多项式承诺方案。 KZG 被广泛用于区块链领域的许多任务（它已经被 Scroll 的证明系统使用，并且很快将通过 Proto-Danksharding‌ (EIP-4844) 集成到以太坊的协议中）。 稍后我们将详细介绍这些用例中的每一个。

本节将简要概述 KZG 多项式承诺方案的数学结构，它并不是全面的，但应该能清楚地说明事情是如何运作的。对于数学爱好者，我们将在本节末尾提供一些进一步的参考资料。

无论如何，让我们从解释开始。 KZG 多项式承诺方案由四个步骤组成：

步骤1（设置）：

1、第一步是一次性可信设置。 完成此步骤后，可以重复其他步骤以提交和揭示各种不同的多项式。

2、设 g 为一些配对友好的椭圆曲线群

的生成器。

3、设 l 为我们要承诺的多项式的最大次数。

4、选择一些随机 field 元素

5、计算

，然后将其公开发布 （注意 τ 不应该被揭示，它是设置的一个秘密参数，应该在设置仪式后丢弃它，这样没有人可以弄清楚它的值）

步骤2 （Commit to 多项式）：

1、给定一个多项式

2、计算并输出 commitment

尽管 committer 不能直接计算

，因为他并不知道 τ，他可以使用设置

的输出计算它。

步骤3 （证明一个评估）：

1、给定一个评估 ϕ(a)=b

2、计算并输出证明

其中

，这被称为“商多项式”。 请注意，当且仅当 φ(a)=b 时，这样的 q(x) 才存在。 因此，该商多项式的存在可作为评估的证明。

步骤4 （验证一个评估证明）：

1、给定一个 commitment

，一个评估 ϕ(a)=b,以及一个证明

2、验证

，其中 e 是一个 non-trivial 双线性映射。

（1） 一些代数（见下面的链接注释）表明这相当于检查步骤 3 中的属性在 τ

时是否成立。

（2）双线性映射使我们能够在不知道秘密设置参数 τ 的情况下检查此属性。

（3）一旦验证完成，我们可以得出商多项式是正确的结论（概率极高），因此评估是正确的。

这是 KZG 背后数学的一个非常简化的讲解，其中省略了一些细节。 要了解更多深度的东西（并查看一个很酷的扩展，你可以使用一个证明来证明多个评估），请查看以下的优秀资源：

1、Dankrad Feist 的 KZG 笔记‌；

2、Alin Tomescu 的 KZG 笔记‌；

KZG 多项式 commitment 方案的用例

1、Scroll 的 zk-rollups

在 zk-rollups 的情况下，我们想证明发生在 L2 上的一些计算是有效的。简单来讲，发生在 L2 上的计算可通过称为“ witness 生成”的过程表示为二维矩阵。然后可以用多项式列表来表示矩阵 - 每列都可以编码为其自己的一维向量。然后，计算的有效性可以表示为这些多项式之间必须保持的一组数学关系。[2] 例如，如果前三列分别由多项式 a(x)、b(x) 以及 c(x) 表示，我们可能需要关系 a(x)⋅b(x)−c(x)=0 保持。多项式（代表计算）是否满足这些“正确性约束”可通过在一些随机点评估多项式来确定。如果“正确性约束”在这些随机点上得到了具体的满足，则一名验证者可以非常高的概率断言计算是正确的。 [3]

人们可以很自然地看到像 KZG 这样的多项式承诺方案，是如何直接插入到这个范式中的：rollup 将 commit to 一组多项式，它们一起代表计算。 然后，验证者可要求对一些随机点进行评估，以检查正确性约束是否成立，从而验证多项式表示的计算是否有效。 [4]

Scroll 专门将 KZG 用于其多项式承诺方案。 还有一些其他的承诺方案也可以发挥类似的作用，但与 KZG 相比，它们目前都有缺点：

1、Inner Product Argument (IPA) 方案很有吸引力，因为它不需要可信设置，并且还能以有效的方式递归组合。 但是，它需要一个特定的椭圆曲线循环（称为“Pasta 曲线”）才能实现其良好的递归特性。 以太坊目前不支持对这些 Pasta 曲线进行有效操作，这意味着在以太坊执行层进行的证明验证效率极低。 如果在没有递归特性的情况下使用（例如，使用非 Pasta 曲线），IPA 的证明验证时间会随着电路的大小线性增长，这使得它对于 zk-rollups 所需的巨大电路而言是不可行的。

2、Fast Reed-Solomon IOP of Proximity (FRI) 方案也不需要可信设置，它不依赖椭圆曲线密码学，因此具有快速的证明生成（生成证明不需要昂贵的椭圆曲线操作），并且它是抗量子计算的。但是，与 KZG 相比，FRI 方案的证明大小和验证时间都很大。

2、以太坊的 Proto-Danksharding

Proto-Danksharding (EIP-4844) 是一项提案，其旨在降低 rollup 在以太坊 L1 上发布数据的成本，它将通过引入一种称为“blob-carrying transaction”的新交易类型来做到这一点。这种新的交易类型将携带一个更大的数据 blob（大约 128 kB）。但是，数据 blob 将无法从以太坊的执行层访问（即智能合约不能直接读取数据 blob）。相反，只有对数据 blob 的 commitment 才能从执行层访问。

现在，我们应该如何创建对数据 blob 的 commitment ？我们可通过简单地哈希数据 blob 来生成一个 commitment。但这存在一点限制，因为我们无法在不揭示整个事物的情况下证明数据 blob 的任何属性。 [5]

我们也可以将数据 blob 视为一个多项式（请记住，将诸如数据向量之类的数学对象表示为多项式很容易），然后使用一个多项式承诺方案来提交数据。这使我们不仅能够实现对数据的 commitment，而且能够有效地检查数据 blob 的某些属性，而无需读取整个数据。

多项式承诺方案为数据 blob 启用的一项非常有用的功能，是数据可用性采样 (DAS)‌。使用 DAS，验证者可以验证数据 blob 的正确性和可用性，而无需下载整个数据 blob。我们不会深入解释 DAS 的具体工作原理，但它是由我们上面讨论的多项式承诺方案的特殊属性实现的。虽然 DAS 的实际实施并未包含在最初的 Proto-Danksharding (EIP 4844) 提案中，但它将在不久之后实施，即以太坊实现“完整” 的 Danksharding 时。

以太坊计划专门使用 KZG 作为其多项式承诺方案。研究人员探索了其他多项式承诺方案，并得出结论认为，KZG 在中短期内为以太坊的 Danksharding 路线图带来了最优雅、最高效的实现。[6]

3、Scroll 的 zk-rollups 和以太坊的 Proto-Danksharding 如何实现交互？

我们现在讨论了 KZG 方案的两个看似独立的用途：Scroll 使用它来提交在 L2 上执行的计算，而以太坊使用它来提交数据 blob。现在我们将看看 KZG 的这两种用途，如何以一种很酷的方式交互在一起！

在 L2 上处理一批交易并计算出新的状态根后，Scroll 将基本上将三件事发布到以太坊 L1：

• T，在 L2 上执行的交易列表；

• Si，在 time-step i 的新状态根；

• π，新状态根 Si 为有效的一个证明；

我们不仅要验证新的状态根 Si 是有效的（即存在一些交易列表，当正确执行时，会导致先前的状态根 Si-1更改为新的状态根 Si），而且交易列表 T 实际上是导致状态根从 Si-1 变为 Si 的交易列表，为了实现这一点，我们需要以某种方式强制 T 和 π 之间的连接。

T 将作为数据 blob 发布，因此验证者合约将有权访问它的 KZG commitment。证明 π 本身将包含对表示计算的各种多项式的 KZG commitment。 一个在 π 内提交的多项式是表示已处理交易列表的多项式。因此，我们对相同的数据有两个单独的 KZG commitment，我们称它们为 CT （来自数据 blob）以及 Cπ（来自证明），假设它们代表相同的基础多项式 φT （这个多项式是事务列表 T 的一个表示）。我们可通过“等价证明”有效地检查两个 commitment 是否表示相同的多项式：

1、计算

2、在 commitment CT 以及 Cπ 下发布 φ(z)=a 的评估证明

这里的想法是选择一个随机（ish）点，并检查两个多项式之间的相等性。 如果多项式在随机选择的点处相等（并且总点的数量足够大），则两个多项式相同的概率非常高。 [7]

这种等价性证明实际上适用于多项式承诺方案的任何组合[8]——如果一个是 FRI commitment，而另一个是 KZG commitment，这实际并不重要，只要两者都可以在某个点打开即可。

总结

让我们回顾一下。

我们从简单解释多项式开始，多项式是可以轻松表示大型数学对象的有用对象。 当我们引入多项式承诺方案时，它们变得更加有用。 多项式承诺方案类似于普通的密码学承诺方案，其具有可以在不揭示整个多项式的情况下证明点评估的附加属性。

然后，我们对最流行的多项式承诺方案之一 KZG 进行了数学描述，该方案有四个步骤：（1）一次性可信设置；（2）一个 commitment

；（3）一个证明

，其中 q(x) 是一个商多项式；（4）使用一个双线性映射进行验证，检查 ϕ(x) 和 q(x) 之间的关系是否正确。

多项式承诺方案的点评估（point-evaluation）特性可以实现非常酷的应用。

我们在 zk-rollups 的情况下看到了一个这样的应用：计算表示为一个多项式，并且可通过检查多项式是否满足某些约束来验证其有效性。 由于多项式承诺方案允许点评估证明，zk-rollups 可以简单地使用简洁的 commitment 来表示计算，而不是冗长的多项式本身。

另一个应用是 Proto-Danksharding：数据 blob 表示为多项式，它们的 commitment 通过 KZG 计算。 KZG 的数学特性支持数据可用性采样（DAS），这对于以太坊数据层的扩容是至关重要的。

最后，我们检查了 Scroll 的 zk-rollup 证明中的 commitment 如何与以太坊上的数据 blob commitment 进行交互。

脚注

1、虽然这听起来是一项艰巨的任务，但研究人员已通过使用多方计算 (MPC) 建立了以弱信任假设（1-of-N信任假设）进行此类可信设置仪式的方法。有关可信设置如何工作的更多信息，请查看 Vitalik 撰写的这篇文章‌。

2、这种将计算转换为数学对象并将其有效性表达为数学关系的过程称为“算术化”（arithmetization）。有多种方法可以进行这种转换，而 Scroll 使用的是 Plonkish 算术化‌。

3、这个想法被正式称为 Schwartz Zippel 引理‌，它被广泛用于有效地验证多项式的属性。

4、请注意，验证者在随机点查询多项式的这种交互式挑战可通过 Fiat-Shamir 变换‌转换为非交互式协议。

5、我们也可以使用简洁的证明来证明数据 blob 的某些属性（例如，证明哈希到正确哈希的数据的知识，然后证明该数据的某些属性），但是这对于每次需要访问/验证关于数据 blob 的信息执行来说太昂贵了。

6、从长远来看，KZG 可能需要更换成抗量子的多项式承诺方案。 Proto-Danksharding 的实施方式‌使得承诺方案可以在未来被替换掉。

7、这再次源自 Schwartz Zippel 引理。请注意，在提交数据之前，证明者必须不能知道评估点 z 的值 ，这一点很重要- 这将使证明者能够轻松构建一个伪多项式，该多项式满足 z 处的等式检查。通过将 z 设置为两个承诺的哈希值，证明者在两个多项式提交之前无法知道 z。

8、然而，当两个多项式承诺方案在不同的组上运行时，就会出现一个复杂的问题。例如，Scroll 目前使用的是 BN254 曲线‌，而以太坊计划将 BLS12-381 曲线‌用于 Proto Danksharding。在这种情况下，我们无法直接比较组元素，就像上面概述的等价证明一样。但我们也有一种解决方法，你可以在 Dankrad Feist 的笔记中阅读到。