Vitalik：以太坊状态爆炸问题，多项式承诺方案可解决

写在前面：为了应对以太坊的状态爆炸问题，以太坊联合创始人Vitalik提出了新的解决方案，其提议使用多项式承诺（polynomial commitments）方案来替代默克尔树（Merkle tree），以此大大减少无状态以太坊客户端的见证数据（witnesses）。

（图：以太坊联合创始人Vitalik Buterin）

（提示：文章有很多公式，译文仅供参考，以原文为准）

以下为译文：

关于这一研究，这里要感谢很多人提供的帮助，尤其是（1）AZTEC团队向我介绍了复制约束（ copy constraint）参数、排序参数以及有效的批范围证明方法； （2）Datery Khovratovich和Justin Drake在Kate 承诺部分提供的方案，（3）Eli ben Sasson关于FRI提供的反馈，以及（4）Justin Drake进行的审查工作。这篇文章只是第一次尝试，如果有进一步的重要思考，我确实希望该方案能够被类似但更好的计划所取代。

太烦不看版总结：

我们建议用称为“多项式承诺”（polynomial commitments）的神奇数学来替代默克尔树（Merkle tree）来累积区块链状态。好处包括：将无状态客户端的见证内容（witnesses）的大小减少到接近于零。这篇文章提出了利用多项式承诺进行状态累积所存在的挑战，并提出了具体的构建方法。

什么是多项式承诺（polynomial commitments）？

多项式承诺是多项式P（x）的一种‘哈希’，其具有可对哈希执行算术检查的属性。

例如，在三个多项式P（x），Q（x），R（x）上，给定三个多项式承诺 h_P = commit(P(x)) , h_Q = commit(Q(x)) , h_R = commit(R(x)) ，然后：

1. 如果 P(x) + Q(x) = R(x) ，你可以生成一个证明（proof），证明它和 h_P, h_Q, h_R 的关系（在某些构造中，你可以简单地检查 h_P + h_Q = h_R） ；
2. 如果 P(x) * Q(x) = R(x) ，你可以生成一个证明（proof），证明它和 h_P, h_Q, h_R 的关系；
3. 如果 P(z) = a ，你可以针对 h_P 生产一个证明（称为开放证明opening proof或简称opening）

你可以将多项式承诺用作vector承诺，类似于默克尔树（Merkle tree）。多项式承诺的一个主要优点是，由于其数学结构的原因，其生成复杂证明要容易得多（详细解释见下文）。

有哪些流行的多项式承诺方案？

当前有两个领跑者，它们分别是Kate承诺（在这篇 文章 中搜索 “Kate”）以及基于 FRI 的承诺。你可能还听说过防弹证明（Bulletproofs）和DARKs算法，这些是替代型多项式承诺方案。而要了解有关多项式承诺的更多信息，YouTube上有相关的内容（ part 1 ， part 2 ， part 3 ，以及 幻灯片 ）。

多项式承诺在以太坊中有哪些容易应用的场景？

我们可以用多项式承诺来替换目前区块数据的默克尔根（例如以太坊2.0的分片区块），并用开放证明替换默克尔分支（Merkle branches） 。这给我们带来了两个很大的优势。首先，数据可用性检查会变得容易，并且不会存在欺诈，因为你可以简单地以随机方式（例如一个N次多项式的2N个坐标中的40个）请求开放。非交互式的托管证明也可能变得更容易。

其次，说服多数据片段的轻客户端也变得更加容易，因为你可以制造一个同时涵盖多个索引的有效证明。对于任何集 {(x_1, y_1), ..., (x_k, y_k)} ，定义三个多项式：

1. 通过所有这些点的 插值多项式 I(x) ；
2. 在 x_1，...，x_k 等于0的 零多项式 Z（x）=（x-x_1）* ... *（x-x_k） ；
3. 商多项式 Q（x）=（P（x）-I（x））/Z（x） ；

商多项式 Q（x） 的存在，意味着 P(x) - I(x) 是 Z（x） 的倍数，因此 P（x）-I（x） 为零，其中 Z(x) 为零。这意味着对于所有 i ，我们都有 P(x_i) - y_i = 0 ，即 P(x_i) = y_i 。验证者（verifier）可以生成插值多项式和零多项式。证明（proof）由对商的承诺，加上随机点 z 上的开放证明组成，因此，我们可以对任意多个点拥有一个常数大小的见证内容（witness）。

这种技术可以为区块数据的多次访问提供一些好处。然而，其对于一种不同的用例而言，存在的优势就要大得多：证明区块交易账户witness。平均而言，每个区块会访问数百个账户和存储密钥，这导致潜在的无状态客户端的见证内容大小会有0.5 MB大小。而多项式承诺多见证（multi-witness），根据方案的不同，可以将区块witness的大小从数万字节减少到几百字节。

那我们可以使用多项式承诺来存储状态吗？

大体上，我们是可以的。相比将状态存储为默克尔树（Merkle tree），我们选择将状态存储为两个多项式 S_k(x) 和 S_v(x) ，其中 S_k（1），...，S_k（N） 表示键（key），而 S_v（1），.. 。，S_v（N） 表示这些键（key）上的值（如果值大于字段大小，则至少表示这些值的哈希值）。

为了证明键值对 （k_1，v_1），...，（k_k，v_k） 是状态的一部分，我们将提供索引 i_1, ..., i_k 并（使用上面提到的插值技术）显示与索引匹配的键和值，即 k_1 = S_k(i_1), ..., k_k = S_k(i_k) 和 v_1 = S_v(i_1), ..., v_k = S_v(i_k) 。

为了证明某些键（key）的非成员性，可以尝试构造一个奇特的证明，证明键（key）不在 S_k（1），…，S_k（N） 中。相反，我们只需对键（key）进行排序，以便证明非成员身份就足以证明两个相邻key的成员身份，一个小于目标key，一个则大于目标key。

而这和Justin Drake提出的使用SNARKs/STARKs来压缩witness以及相关的想法有着相似的好处， 另外一个好处是，由于证明是累加器密码学原生的，而不是构建在累加器密码学上的证明，因此这消除了一个数量级的开销，并移除了对零知识证明友好哈希函数的需求 。

但这里存在着两个大问题：

1. 为k个密钥生成witness需要的时间是 O（N） ，其中N是状态的大小。而预计N对应的状态数据会有大约 50 GB ，因此在单个区块中生成这样的证明是不实际的；
2. 2、用k个新值更新 S_k(x) 和 S_v(x) 花费的时间也需要 O（N） 。这在单个区块中是不切实际的，特别是考虑到诸如witness更新和重新排序之类的复杂性。

下面我们将介绍应对这两大问题的解决方案。

高效读取（Efficient reading）

我们提供了两种解决方案，一种针对Kate承诺而设计，另一种则是针对基于FRI的承诺。不幸的是，这些方案具有不同的优点和缺点，从而会导致不同的属性。

1、Kate承诺

首先，请注意，对于N次多项式f，有一种方案可生成N个对应于 O(N * log(N)) 时间中每个 q_i(x) = (f(x) - f(i)) / (X - i) 的开放证明。

还请注意，我们可以按以下方式合并witness。考虑这样一个事实， q_i(x) 只是一个离开 f（x）/（X-i） 的子常数（sub-constant）项，通常，已知 f/((X - x_1) * ... * (X - x_k)) 是 f /（X-x_1），...，f /（X-x_k） 使用部分分式分解（ partial fraction decomposition）的某种线性组合。只需知道x坐标就可以确定具体的线性组合：只需提出一个线性组合 c_1 * (x - x_2) * ... * (x - x_k) + c_2 * (x - x_1) * (x - x_3) * ... * (x - x_k) + ... + c_k * (x - x_1) * ... * (x - x_{k-1}) ，其中不存在非常数项，这是k个未知数中的k方程组。

给定这样的线性组合，我们得到的东西仅是离开 f/((x - x_1) * ... * (x - x_k)) 的一个子常数项（因为所有原始误差都是子常数的，所以线性错误的组合必然是sub-constant），因此它必然是商 f(x) // ((x - x_1) * ... * (x - x_k)) ，其等于期望值 (f(x) - I(x_1 ... x_k, y_1 ... y_k)) / ((x - x_1) * ... * (x - x_k)) 。

一个可能的挑战是，对于大的状态，一个实际可计算的单一可信设置（例如，100多个独立参与者，因此只要其中任何一个是诚实的，方案就是安全的）是不够大的：例如，PLONK设置只能容纳约3.2 GB。相反，我们可以有一个由多个Kate承诺组成的状态。

我们对很多承诺作如下单一witness。为证明 ，首先让 （这是fi和1的线性组合，因此验证者verifier可以实时计算此承诺）。witness是 ；如果Q是一个多项式，则F实际上在那些位置为零，因此fi在其位置具有期望值。

2、基于FRI的承诺

我们将状态存储在一个二维多项式 F（x，y） 的求值中（每个变量的阶数为 sqrt（N） ），并致力于对 4*sqrt(N) by 4*sqrt(N) square 求值 F 。

我们将所有我们关心的值存储在位置 (x, x**sqrt(N)) ，因此它们都具有唯一的 x 坐标。（请注意，在很多情况下，这些位置会超出我们承诺求值的 4*sqrt(N) by 4*sqrt(N) square ，而这无关紧要。）

为了证明在一组点 x_1, ..., x_k 上的求值，我们构造了一个k次多项式路径 （x） ，其在 x_i 处的求值为 x_i ** sqrt（N） 。

然后，我们创建一个多项式 h(t) = F(t, path(t)) ，其中包含对 (x_i, y_i) 的所有期望求值，并且具有 k*（1+sqrt（N）） 次。

我们在求值域中选择随机的30列 c_1 ... c_k ，对于每列查询30个随机行。我们承诺于 h （使用FRI证明它实际上是一个多项式），为 z_i = h(c_i) 提供一个多开口（multi-opening），并对列商 (R_i - z_i) / (X - path(c_i)) 进行FRI随机线性组合，以验证 h（c_i） 的声明值是正确的，因此 h(t) 实际上等于 F(t, path(t)) 。

使用二维多项式的原因是，这确保了我们不必对所有 F 进行任何计算；相反，我们只需要对我们选择的随机30行 F 进行计算（即 30*sqrt（N） ），加上阶为 p * (sqrt(N) + 1) 的 h ，创建FRI进行的计算大约为 p * sqrt(N) 。可以将此技术扩展到二维以上的多项式，以将 sqrt 因子降低到更低的指数。

高效写入（Efficient writing）

我们通过一系列的承诺，来解决与更新包含整个状态的单个承诺相关的挑战，较大的承诺，其更新频率也就较低：

1. 区块本身，具有“读取见证” (R_k(x) , R_v(x)) 和“写入见证” （W_k（x） ， W_v（x） ），表示要写入状态的值。注意，我们可以设置 W_k = R_k ，并在运行时计算 W_v 。
2. 第一个缓存 C1 =（C1_k（x），C1_v（x）） 存储最近一天的更新内容；
3. 第二个缓存C2等于前一天的最后一个C1；
4. 满状态 S = （S_k（x），S_v（x）） 包含时间超过1-2天的值；

我们将使用的方法如下。为了从状态中读取一些键k，我们将依次读取 C1 , C2 , S 。如果键位于某 C1_k（x） 处，则对应的值 C1_v（x） 存储该值，如果键位于 C2_k（x） ，则 C2_v（x） 存储该值，依此类推，如果键位于 S_k（x） ，则 S_v（x） 存储该值。如果这些检查都没有返回键，则该值为0。

复制约束（copy constraint）参数的简介

复制约束参数，是我们将使用的witness更新证明的关键组成部分；有关复制约束参数如何工作的详细信息，请参见 此处 。简而言之，该想法是选择一个随机 r ，并生成一个“累加”多项式 ACC（x） ，其中 ACC（0）= 1 且 ACC（x + 1）= ACC（x）*（r + P（x）） 。你可以通过开放读取 ACC(y) / ACC(x) ，来读取 x .... y-1 范围内的点累加器。你可以使用这些累加器值，将这些求值与其他求值集（作为多集）进行比较，而无需考虑排列。

你还可以通过设置 ACC(x+1) = ACC(x) * (r + P_1(x) + r2 * P_2(x)) 来证明某些随机 r 和 r2 的求值元组（即多集 {(P_1(0), P_2(0)), (P_1(1), P_2(1)), ...} ）的等价性。多项式承诺可有效用于证明有关ACC的主张。

为了证明子集，我们可以做相同的事情，除了我们还要提供一个指标多项式 ind（x） ，证明该 ind(x) 在整个范围内等于0或1，并设置 ACC（x + 1）= ACC（x ）*（ind（x）*（r + P（x））+（1-ind（x））） （即，如果指标为1，则在每一步乘以 r + P（x） ，否则不使用累加器值）。

小结：

1. 我们可以证明a和b之间的P（x）求值，是a和b（或某些不同的c和d）之间Q（x）求值的置换；
2. 我们可以证明a和b之间的P（x）求值，是a和b（或一些不同的c和d）之间Q（x）求值置换的子集；
3. 我们可以证明P（x）和Q（x）的求值，是R（x）和S（x）置换，其中P-> Q和R-> S是相同的置换；

在下面的内容中，除非明确说明，否则我们将偷懒地表述为“P是Q的置换”，意思是“P在0和k之间的求值，是Q在0和k之间对适当k求值的置换”。请注意，下面的内容中，我们还会涉及到每个witness的“大小”，以确定我们接受的任何 C_k 中的坐标，而超出范围的 C_k（x） 值当然不计算在内。

映射合并参数（Map merging argument）

为了更新缓存，我们使用了“映射合并参数”。给定两个映射 A=（A_k（x），A_v（x）） 和 B=（B_k（x），B_v（x）） ，生成合并映射 C=（C_k（x），C_v（x）） 以便：

1. C_k 中的键被分类；
2. 对于0 <= i < size(B)，(B_k(i), B_v(i)) 在C中；
3. 对于0 <= i < size(A)，仅当 A_k(i)不在B的求值集之内时，(A_k(i), A_v(i))在C中；

我们用一系列复制约束参数来实现这一点。首先，我们生成两个辅助多项式 U（x） ， I（x） ，它们分别表示 A_k 和 B_k 的“并集”和“交集”。将 A_k，B_k，C_k，U，I 视为集合，我们首先需要展示：

1、 A_k ⊆ U ；

2、 B_k ⊆ U ；

3、 I ⊆ A_k ；

4、 I ⊆ B_k ；

5、 A_k + B_k = U + I ；

我们预先假设在 A_k 和 B_k 中没有重复，这意味着 A_k（i）！= A_j（j） 对于范围内的 i！= j 与 B_k 相同（因为在之前使用此算法时已对此进行了验证）。由于 I 是 A_k 和 B_k 的子集，所以我们已经知道 I 也没有重复的值。通过使用另一个复制约束参数来证明 U 和 C_k 之间的等价关系，证明了 U 中没有重复项，并证明 C_k 是已排序且无重复的。我们用一个简单的复制约束参数证明 A_k + B_k = U + I 声明。

为了证明 C_k 已排序且没有重复，我们证明 C_k（x + 1）> C_k（x） 的范围为 0 ... size（C_k） 。我们通过生成多项式 D_1（x），...，D_16（x） ，并证明 C（x + 1）-C（x）= 1 + D_1（x）+ 2 ** 16 * D_2（x）+ 2 ** 32 * D_3（x）+... 来做到这一点。本质上， D_1（z），...，D_16（z） 将差异存储在基 2**16 中。然后，我们生成一个多项式 E（x） ，其满足所有 D_1，...，D_16 的复制约束以及 f（x）= x ，并且满足 E(x+1) - E(x) = {0, 1} 限制（对E的2次约束）。我们还检查了 E（0）= 0 以及 E（size（C_k）* 16 + 65536）= 65535 。

关于E的约束表明，E中的所有值都夹在0和65535（包括0和65535）之间。对 D_i 的复制约束，证明 D_i（x） 中的所有值都在0到65535（含）之间，这证明了它是一个正确的16进制表示，从而证明了 C_k（x+1）-C_k（x） 实际上是一个正数。

现在，我们需要证明value（值）。我们添加另一个多项式 U_v（x） ，并验证：

1. 在 0...size(B) 的 (U, U_v) 等于在 0...size(B) 的 (B_k, B_v) ；
2. 在 size(B) ... size(A)+size(B) 的 (U, U_v) ，是 （A_k，A_v） 在 0...size(A) 的一个子集；

目标是在 U 中，我们先放置来自 B 的所有值，然后再放置来自 A 的值，并使用相同的置换参数来确保键（key）和值（value）被正确复制。然后我们验证 （C_k，C_v） 是 （U，U v） 的一个置换。

使用映射合并参数

我们按照下面的方式使用映射合并参数，假设每天有 BLOCKS_PER_DAY 个区块。

1. 如果 block.number % BLOCKS_PER_DAY != 0 ，我们验证 (C1_k, C1_v) = merge((W_k, W_v), (C1_old_k, C1_old_v)) （将区块合并到C1）；
2. 如果 block.number % BLOCKS_PER_DAY == 0 ，我们验证 (C1_k, C1_v) = (W_k, W_v) 以及 (C2_k, C2_v) = (C1_old_k, C1_old_v) （也就是说，我们“清除” C1并将其内容移入C2）；

请注意，C2具有一整天的时间，在此期间它保持不变。我们为任何人产生 （S_k，S_v）= merge（（S_old_k，S_old_v），（C2_k，C2_v）） 的证明提供奖励；提供此证明后，我们将承诺 （S_k，S_v） 更新为新值，并将 （C2_k，C2_v） 重置为空。如果 S 在当天没有更新，则我们将 C1-> C2 传输延迟到更新为止；请注意，该协议确实取决于 S 的更新速度是否足够快。如果这不可能发生，那么我们可以通过添加更多层缓存的层次结构来解决这个问题。

从糟糕的FRI中恢复

对于FRI的情况，注意，有可能会出现有人生成的FRI在某些位置无效，但这不足以阻止验证。这不会立即造成安全风险，但可能会阻止下一个更新者生成witness。

我们通过以下几种方法来解决这个问题。首先，注意到某些FRI生成错误的人，可提供自己的FRI。如果通过相同的检查，它将被添加到可构建下一次更新的有效FRI列表中。然后，我们可以使用交互式计算游戏来检测和惩罚不良FRI的创建者。其次，他们可提供自己的FRI以及STARK来证明其有效，从而立即罚没了无效FRI的创建者。通过FRI生成STARK是非常昂贵的，尤其是在较大规模时，但这样做是值得的，因为这可以赚取很大一部分无效提议者的保证金奖励。

因此，我们有了一种机制来使用多项式承诺，以此作为一个有效读取和写入witness来存储状态。这使我们能够大幅度减少见证内容（witness）大小，同时也可以带来一些好处，比如让我们有能力对数据可用性进行检查，以及实现关于状态的托管证明 。

今后的工作

1. 提出FRI证明，要求少于900次查询（更正式地讲，安全参数小于平方）；
2. 从理论上讲，如果你预先计算并存储拉格朗日基（Lagrange basis），理论上可以快速更新 Kate承诺。这是否可以扩展到（i）快速更新所有witness，以及（2）为键值映射而不是一个vector工作？