7.KZG实践：多项式承诺方案及以太坊扩容中的用例.md

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

翻译：Junwei

介绍

由于其数学上的复杂性，零知识证明总是蒙着一层神秘的面纱，被亲切地称为“月亮数学”。在大多数人眼中 ，是一种神奇的魔法。

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

在这篇文章中，我们将介绍许多零知识证明系统中的关键要素：多项式承诺方案。然后我们将简要概述 KZG，它是实践中最广泛使用的多项式承诺方案之一。随后，我们将讨论如何在Scroll的zk-rollups以及以太坊的Proto-Danksharding中使用KZG。最后，我们将展示如何高效且优雅地集成zk-rollups和Proto-Danksharding—通过它们各自使用的多项式承诺方案来实现。

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

多项式是非常强大的工具，它们在许多不同领域都有相应的应用。多项式可用于高效地表示大型对象。

一个可以表示为多项式的标准对象是$n$维向量，向量内元素$v \in \mathbb{F}_p^n$. 我们可以构建一个多项式$\phi(x)$ 来表示$v$，只要确保对于$i = 1, 2, ..., n$，$\phi(x)$通过点 $(i, v_i)$

例如，我们取一个3维向量$v = [2, 0, 6]$，并将其表示为多项式$\phi(x) = 4x^2-14x+12$，通过插值$\phi(1) = 2,\phi(2) = 0$和$\phi(3) = 6$可以进行验证。用这样的方式，就用多项式$\phi(x)$“编码”了向量$v$.

一般来说，可以取$n$个任意点并找到唯一的$n-1$次多项式穿过所有这些点。这个过程被称为“多项式插值”法，并且现已有成熟的方法可以高效得实现它。（查看Wolfram Alpha提供的这个实用的在线工具，它可以在给定输入向量的情况下插值生成多项式！）

什么是多项式承诺方案？为什么它们有用？

多项式承诺方案是附加了一些有用的属性的承诺方案。在常规的承诺方案中，提交者通过输出一些承诺$c$，来对消息$m$进行承诺. 然后提交者可以随后揭露消息$m$，验证者可以验证确实该承诺$c$对应于消息$m$。一个承诺方案应具有“约束力”（一旦发布承诺$c$，提交者应当无法找到其他消息$m' \neq m$，也对应于承诺$c$）和“隐匿性”（发布承诺$c$不应当透露有关基础消息$m$的任何信息）。

现在，使用多项式承诺方案，提交者对多项式 $\phi$，而不是一些任意的消息 $m$进行承诺。 多项式承诺方案在满足上述常规的承诺方案的属性上，还实现了一个附加属性：提交者应该能够“打开”对承诺的多项式的特定取值，而不会透露整个多项式。例如，提交者应该能够证明 $\phi(a)=b$，但没有透露$\phi(x)$具体是什么。

这是一个非常棒的属性，对于零知识应用程序而言非常有用！我们可以用它来证明一些满足特定性质的多项式（在这种情况下，即多项式通过某个点$(a,b)$），而这些都没有透露多项式是什么！

这个属性有用的另一个原因是承诺$c$通常比它所代表的多项式小得多。我们将能构建一个承诺方案，其中任意次数的多项式都可以通过其承诺表示为单个群元素。这在链上发布数据时显得尤其必要，因为区块空间是一种宝贵的资产，任何形式的压缩都可以立即节省开销。

KZG 多项式承诺方案

好的，现在我们已经引入了多项式承诺方案，让我们看看如何真正构建一个。我们将关注的是Kate-Zaverucha-Goldberg (KZG) 多项式承诺方案。KZG 被广泛用于区块链领域的许多部分—它已经使用在Scroll 的证明系统中，并且很快将通过Proto-Danksharding (EIP-4844) 集成到以太坊的协议中。随后我们将详细介绍这每一个用例。

本节将简要概述KZG多项式承诺方案的数学结构。我们不试图面面俱到，但是将清楚地说明事情是如何运作的。对于更数学性的解释，我们将在本节末尾提供更进一步参考。

无论如何，让我们开始构建。KZG多项式承诺方案包括四个步骤。

第 1 步（设置）：

• 第1步是一次性的可信初始化设置。完成此步骤后，可以重复其他步骤以提交和揭示各种不同的多项式。
• 令$g$是一些配对友好的椭圆曲线群$\mathbb{G}$的生成元
• 令$l$是我们要承诺的多项式的最大次数
• 选择一些随机字段元素$\tau \in \mathbb{F}_p$
• 计算$(g, g^{\tau}, g^{\tau^2}, ..., g^{\tau^l})$，并公开发布
  • 注意$\tau$不应该被透露 - 它是设置的秘密参数，应该在可信初始化设置后丢弃，这样任何人都无法知道它的值。[1]

第 2 步（多项式承诺）：

• 给定一个多项式$\phi(x) = \sum_{i=0}^{l} \phi_i x^i$
• 计算和输出承诺$c = g^{\phi(\tau)}$
  • 虽然提交者无法直接计算$g^{\phi(\tau)}$，因为他不知道$\tau$，他可以使用设置的输出来计算它$(g, g^{\tau}, g^{\tau^2}, ..., g^{\tau^l})$：
    • $\prod_{i=0}^{l} (g^{\tau^i})^{\phi_i} = g^{\sum_{i=0}^{l}\phi_i \tau^i}= g ^{\phi(\tau)}$

第 3 步（证明求值）：

• 给出求值$\phi(a) = b$
• 计算和输出证明$\pi = g^{q(\tau)}$
  • 其中$q(x) := \frac{\phi(x) - b}{x - a}$
    • 这称为“商多项式(quotient polynomial)”。 请注意，当且仅当$\phi(a)=b$存在这样的多项式$q(x)$. 因此，该商多项式的存在可作为求值的证明。

第 4 步（验证估值证明）：

• 给定承诺$c = g^{\phi(\tau)}$, 求值$\phi(a)=b$，和一个证明$\pi = g^{q(\tau)}$
• 验证$e(\frac{c}{g^b}, g) = e(\pi, \frac{g^{\tau}}{g^a})$，此处 $e$是一个non-trival双线性映射
  • 代数转化（详见下面的链接注释）表明这相当于检查步骤3中的属性在随机数 $\tau $上是否成立：
    • $q(\tau) = \frac{\phi(\tau) - b}{\tau - a}$
  • 双线性映射使我们能够在不知道初始化时的秘密参数$\tau$的情况下检查该属性
• 一旦验证完成，我们可以（以极高的概率）得出结论：商多项式是正确的，因此求值是正确的。

这是KZG背后数学的非常简单的介绍，省略了一些细节。想要更深入了解（例如在一个更进阶的扩展中，可以使用一个证明来证明多个求值），请查看以下优秀资源：

• Dankrad Feist 关于 KZG 的笔记
• Alin Tomescu 关于 KZG 的笔记

用例

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将提交一组多项式，它们都代表计算。然后，验证者可以要求对一些随机点展开计算，以检查正确性约束是否成立，从而验证多项式表示的计算是否有效。[4]

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

1. Inner Product Argument (IPA) 方案很有吸引力，因为它不需要可信初始化设置，并且还可以高效得实现递归组合。但是，它需要一个特定的循环椭圆曲线（称为“ Pasta 曲线”），才能实现其良好的递归特性。以太坊目前不支持对这些 Pasta 曲线进行有效操作。这意味着在以太坊执行层进行的证明验证效率极低。如果在没有递归特性的情况下使用（例如，使用非Pasta 曲线），IPA的证明验证时间会随着电路的大小线性增长，这在zk-rollups所需的巨大电路下并不可行。
2. Fast Reed-Solomon IOP of Proximity(FRI) 方案也不需要可信初始化设置。它不依赖椭圆曲线密码学，因此可以快速生成证明（不需要昂贵的椭圆曲线操作去生成证明）并且是抗量子的。但是，与 KZG 相比，它的证明规模和验证时间都很大。

以太坊的 Proto-Danksharding

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

现在，我们应该如何创建对数据块的承诺？我们可以通过简单地对数据块进行哈希来生成承诺。但这有所限制，因为我们不能在不揭示整个数据块的情况下证明其的任何属性。[5]

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

多项式承诺对数据块采用的一项非常有用的功能是数据可用性采样(DAS)。凭借DAS，验证者可以验证数据块的正确性和可用性，而无需下载整个数据块。我们不会深入研究DAS的具体工作原理，但它是由我们上述的多项式承诺方案的特殊属性实现的。虽然 DAS 的实际实现并没有包含在最初的Proto-Danksharding(EIP 4844) 提案中，但它将在不久之后，以太坊实现“完整的” Danksharding 的过程中实现。

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

Scroll 的 zk-rollups 和 Ethereum 的 Proto-Danksharding 如何交互

我们现在讨论了 KZG的两个看似独立的用例：Scroll用它来提交在 L2 上执行的计算，而以太坊用它来提交数据块。现在我们将看到 KZG的这两个用例如何实际中很好地交互！

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

• $T$- 在L2上执行的交易列表
• $s_i$- time-step $i $时的新状态根
• $\pi$- 新状态根$s_i$有效的证明

我们不仅要验证新的状态根$s_i$是有效的（即存在一些交易列表，当正确执行时，会导致先前的状态根$s_{i-1}$变更为新的状态$s_i$），还需要验证交易列表$T$确实是导致状态根从$s_{i-1}$至$s_i $的交易列表。为了实现这一点，我们需要以某种方式关联$T$和$\pi$.

$T$将作为数据块发布，因此验证者合约将有权访问其KZG 承诺。证明$\pi$本身将包含对各种表示计算的多项式的 KZG 承诺。$\pi$中的一个多项式承诺是表示已处理交易列表的多项式。因此，我们对于相同的数据有两个单独的KZG承诺—我们称它们为$C_T$（来自数据块）和$C_{\pi}$（来自证明），我们假设它们代表相同的基础多项式$\phi_T$（这个多项式用来表示交易列表）。我们可以通过“等价证明”有效地检查两个承诺是否表示相同的多项式：

1. 计算$z = \text{hash}(C_T | C_{\pi})$
2. 根据两项承诺$C_T$和$C_{\pi}$，发布计算证明$\phi(z) = a$

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

这种等价证明实际上适用于多项式承诺方案的任何组合[8] —一个是FRI承诺而另一个是KZG承诺也没有关系，只要两者都可以在一个点上打开。

小结

让我们回顾一下。

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

然后，我们对最主流的多项式承诺方案之一即KZG，进行了数学描述。它有四个步骤：（1）一次性可信初始化设置；(2) 构建承诺$c = g^{\phi(\tau)}$；(3) 构建证明$\pi = g^{q(\tau)}$，此处$q(x)$是商多项式；(4) 使用双线性映射进行验证，检查两者之间的关系$\phi(x)$和$q(x)$是正确的。

多项式承诺方案的点计算(point-evaluation)特性可以实现非常酷的应用。

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

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

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

脚注

1. 虽然这听起来是一项复杂的任务，但已经建立了在弱信任假设（1/N的信任假设）使用多方计算（MPC）进行此类可信初始化设置的方法。有关可信设置如何工作的更多信息，请查看Vitalik 的这篇文章。
2. 这种将计算转换为数学对象并将其有效性表示为数学关系的过程称为“算术化”。有多种方法可以进行这种转换，但 Scroll使用Plonkish arithmetization。
3. 这个想法被正式称为Schwartz Zippel 引理，它被广泛用于高效验证多项式的属性。
4. 请注意，验证者在随机点查验多项式的这种交互式挑战，可以通过Fiat-Shamir 变换转换为非交互式协议。
5. 我们也可以使用简洁的证明（例如，证明数据被正确哈希，然后证明该数据的某些属性）来证明数据块的某些属性，但每次执行有关数据需要访问/验证数据块的信息，代价太大。
6. 从长远来看，KZG可能需要换成抗量子的多项式承诺方案。Proto-Danksharding 的实现方式使得承诺方案可以在未来被替换掉。
7. 这也来自Schwartz Zippel 引理。请注意，证明者在提交数据之前必须无法知道计算点$z$的值，这一点很重要—这将使证明者能够轻松构建满足在$z$点上进行相等性检查的虚假多项式。通过设置$z$为两个承诺的哈希值，证明者无法知道$z$直到两个多项式都被提交。
8. 然而，当两个多项式承诺方案在不同的群上运行时，就会出现复杂情况。例如，Scroll 目前使用BN254曲线，而以太坊计划使用BLS12-381曲线进行 Proto-Danksharding。在这种情况下，我们无法像上述的等价证明一样，直接比较群元素。但是，有一种解决方法，可以阅读Dankrad Feist 的笔记。