为什么以太坊需要 KZG10 承诺？

（译者注：本文介绍的技术在密码学界一般称为“KZG10承诺”，以三位作者姓氏首字母命名。但引入以太坊生态后，被简化为“Kate Commitment” ”，连核心开发者都这么叫，这是对其他两位作者的不尊重，不应该继续。在本次翻译中，原作者凡使用“Kate commitment”的地方，都将翻译为“KZG10 Commitment”。）

免责声明：本文仅收集并链接了许多已发表的成果，相应的荣誉（包括本文链接的图片）应归相应的作者/开发者所有。

PS：特别感谢以太坊研发discord频道（特别是@vbuterin和@piper）帮助我理解了KZG10承诺的某些方面。 另外，感谢 @vbuterin 帮助审阅本文。

PPS：这篇文章是为了 lodestar 团队的利益而写的； lodestar是一个很棒的基于typescript的ETH PoS客户端，可以让以太坊服务无处不在，也开启了作者对以太坊生态和创新的认识。

希望本文也能对世界各地的其他开发人员/技术人员有所帮助。 本文遵循CC0自由创作公约以太坊最新，作者已放弃一切权利。

动机

作为读者熟悉的有益指南，总结 KZG10 承诺在以太坊背景下的建议用法，为深入理解提供指导。

基本原则

注1：哈希值是对哈希原像的承诺，用于验证哈希数据的完整性。 （译者注：这其实不是很严谨。因为散列函数往往很难满足“承诺方案”所要求的性质。）

例如，假设 h1 = H(t1, t2, t3..)，然后将 h1 交给验证者（例如，将其放在区块头中），然后给出一个假区块 (t1,t2' ,t3... )，对方快速计算出伪造区块的哈希值，发现两者不匹配后，就可以合理拒绝你的伪造区块。

同样，Merkle 树的根节点是对由特定索引（路径）组织的所有叶节点的承诺。 或者简单地说，索引 => 值映射的承诺（从索引值到数值）。

而这里的“证明”是一个叶子的默克尔分支（merkle branch）和这个分支（在每一层）的兄弟哈希（sibling hashes）。 有了这些数据以太坊最新，就可以逐级向上哈希，通过最终的哈希值是否与根节点一致来判断叶子是否与这棵Merkle树一致（存在于这棵Merkle树上）。

你可以在这里看到介绍:)。

注2：数据映射与多项式的对应关系

indexes => values这样的数据映射可以表示为一个多项式f(x)，f(index)=value（从拉格朗日插值法可以知道满足这个条件的多项式一定存在）。 “ f(index)=value ”通常称为评估形式，而“ f(x)=a0+ a1.x + a2.x^2...” 是其系数形式。 直观上，我们实际上是根据地图中的所有（索引，值）点来拟合一个多项式。

为了简化计算，保证多项式与数据映射的一一匹配，我们不使用索引值作为f(x)的x，而是使用w^index，即f( w^index)=value，其中w为d次单位根（即w^d=1，w为复数），d为多项式的次数（以及索引值个数的上限我们可以包括）。 因此，我们可以使用快速傅里叶变换来实现高效的多项式计算，比如乘法和除法，其计算复杂度在求值形式上为O(d)，可以复杂到O(d*log(d))转换回以度为单位的系数形式。 所以保持 d 的值较小仍然是有益的。

注 2.1：以太坊的状态是从地址到账户状态的映射（地址 => (version, balance, nonce, codeHash, storageRoot)）。

背景知识

以太坊目前使用 Merkle 树（更具体地说是“Patricia Merkle 树”）作为 EVM 数据（EVM 状态、区块交易和交易收据，也许还有最近的合约代码）的承诺。 此类承诺可以：

前缀树结构在这里提供了这种逐块更新的特性。

给定一棵有 N 个叶子的 d-forked 前缀树，对叶子节点的任何更改都需要更新 O(log-d(N)) 个节点（即连接叶子到根节点的路径上的节点数）来计算反映新状态的新根值； 这需要额外的 (d-1)*O(log-d(N)) 兄弟散列/时间和空间承诺（假设服务轻节点）见证数据（见证）。 一个block可以看成是一次batch update需要改变m个随机叶子，而在mvalues的映射中，所有的values都必须表示为椭圆曲线上的元素，即[value]，从而计算出承诺（后面详述）。 这限制了值的大小（以便成为模 Fp 的值）。 在 BLS 曲线上，它大概在 31 到 32 字节之间。 为简单起见，值的大小限制为 31 个字节，任何更大的值都被分块并由其索引值正确表示（或截断）。

注3.1：[t]可以看作是t的哈希值，因为从[t]中取出t是一个离散对数问题（discrete log problem），安全曲线很难做到。

注3.2：s是一个秘密值，永远不应该向任何人/所有人透露，而是椭圆曲线点[s]、[s^2]…[s^d]和它们在另一个椭圆曲线[s]上的值' （其生成点是[1]'，只需要知道[s]'）应该生成并公开给大家知道。 这就是启动设置所做的。

这些系统参数定义了整个系统的安全性，因为 s 暴露将允许攻击者构建任意内容的证据。 因此，在一个有N个参与者参与的启动设置仪式中，他们需要通过协议结合本地的s，这样只要有一个参与者是诚实的，在参与后销毁自己提供的s，系统就安全了。 即信任模型是1/N模型，N越高，风险越低。

注3-3：[]为线性运算，即[x]+[y]=[x+y]，a[x]=[ax]。

上面提到，我们将数据映射（索引值=>值）表示为f(w^index)=值，这是一个多项式的求值形式。 也可以说，我们用这（w^index,value）个点拟合了一条曲线（多项式）。

所以，一个多项式f(x)的KZG10承诺c(f)是一个椭圆曲线点f([s])，可以将其插入到f(x)的展开中[s],[s^2] ……计算。

注3-4：无法计算f(s)，因为s是一个秘密值。 但是 C(f)=[f(s)]=f([s]) 是可计算的。

注3-5：f(x)的承诺C(f)=[f(s)]也是一个线性算子，即C(f+g)=C(f)+C(g)。

汇总/聚合器可以使用此属性来更新承诺。 在评估表中，更新一个评估点会导致 f(x) 完全改变，但由于这个性质，承诺 c(f) 仍然很容易更新。

注3.6：如果启动设置计算的[s]，[s^2]...[s^d]只计算到指数d，这组值不能用来生成阶数更​​大的任何多项式承诺比d。 反之亦然。

由于在安全曲线上没有办法将两个点相乘得到第三个点，[s^(d+k)] 是一个（永远不会！）无法找到的值，因此任何承诺 c(f) 都可以仅表示次数小于或等于 d 的多项式。

注 3.7：使用 KZG10 承诺的证明基本上是证明 f(x) - 一些余数的结果可以以某种方式分解，但必须有一种方法将这些因子相乘并将它们与原始承诺相乘比较 C(f )=f([s])。

为此，我们需要一个“配对方程”，它是将曲线上的两个点相乘并与另一个曲线点进行比较的乘法，因为我们不能直接将这两个曲线点直接相乘得到结果曲线点。

注3.8：以上两个性质可以进一步证明某承诺c(f)表示的多项式f(x)的k阶小于d。

总之，KZG10 promises 可以具有良好的特性：

在 PoS 链的常见初始设置中，共享数据块表示为低阶多项式（并使用相同的拟合多项式进行纠删码缩放至两倍大），并且 KZG 承诺可用于检查任意随机分布。 在不获取同级数据点的情况下阻止和验证并确保数据可用性。 这开启了随机抽样的可能性。

现在，对于最多可包含 2^28 个帐户密钥的状态，您需要阶数至少为 2^28 的多项式来构建平坦承诺（帐户密钥的实际总空间将大得多）。 更新和插入时有一些不便之处。 对任一账户的任何更改都将触发对承诺的重新计算（更麻烦的是，见证数据/证据）。

更新 KZG10 承诺

Sqrt(N) 复杂性的更新 KZG10 承诺的构造

因此，要实现理想承诺方案的第四点，我们需要一个特殊的结构：Verkle trie。

Verkle 树

以太坊需要表示的状态大约是2^28，约等于16^7，约等于2.5亿个键值对。 如果我们只使用固定承诺（那么我们至少需要 2^28 的阶数）。 虽然我们的证据始终是一个 48 字节的椭圆曲线元素，但是任何插入或更新都需要 O(N) 操作来更新所有预先计算的见证数据（即所有点的 q_i(s)，因为 f(x) 本身有改变了）； 甚至，如果没有预先计算好的witness data，每一个witness data都需要用O(N)重新计算。

因此，我们需要用一种叫做Verkle树的结构来代替平面结构，它是一种类似于Merkle树的树结构。

也就是像Merkle树一样，构造一个commitment树，这样我们就可以保证d的阶数比较小（但是也需要高到256或者1024左右）。

复杂性

下面是对 Verkle 多值证明的分析

证明的大小（包括用于计算 E 的分支承诺）加上验证的复杂性 ~O( log_d(N) )

Verkle树构造

提议的 ETH 状态 Verkle 树

单树结构，存储账户头和代码块，以及存储项目块，节点的承诺是一个d=256阶的多项式

代码默克尔化

代码自动成为verkle树的一部分（作为统一状态树的一部分）

PoS 协议中的数据采样和分片

ETH PoS 的目标之一是能够提交约 1.5MB/s 的数据量（将这个吞吐量理解为状态变化的吞吐量，从而 L2 rollup 可以利用的交易吞吐量，最终是L1 EVM）。 为此，需要在给定的 12 秒内发布并验证许多并行区块提案； 也就是说，必须有多个分片（大约 64 个），并且每个分片必须在每个槽中发布自己的分片。 数据块。 如果超过 2/3 的票数得到支持，信标链区块将包含碎片化的数据块，分叉选择规则也会根据信标链区块中所有数据块的数据可用性及其各自的数据可用性来决定是否可以。祖先。 成为主链块。

注 3：此时的分片不是链，任何隐含的顺序都必须由 L2 协议解释。

KZG promises 也可用于构建数据有效性和可用性方案，客户端无需访问分片提议者发布的完整数据即可验证可用性。

这个纠删码的32768个样本被分成2048个块，每个块包含16个样本，即512字节的数据； 由区块提议者水平发布，即第i个区块和相应的证据发送到第i个垂直子网，加上承诺在全球公开完整的数据

在指定的(shard, slot)，每个验证者在k~20个垂直子网中下载并检查这些块，并与相应数据块的承诺进行验证，建立数据可用性保证

基准

正如我们在 POC verkle go 代码库中看到的那样，在构建状态树规模的 verkle 之后，插入和更新非常快：

插入/更新基准

证明生成验证基准