The Verge - 以太坊的高效可验证查询技术：Verkle Trees

1. 简介

2023 年的最后一天，维塔利克在 Twitter 上分享了以太坊 2023 年的路线图，总结了以太坊一年来的进展。路线图 “The Verge ”部分描述了以太坊技术如何更简单、更高效地验证区块链状态。其中提到的一个核心概念就是 Verkle 树。那么，什么是 Verkle Trees，为什么以太坊需要它，Verkle Trees 又是如何解决问题的呢？本文的目的是在不深入研究密码学和数学的前提下为读者解答这些问题，帮助那些对以太坊有一定了解的读者快速掌握 Verkle Trees 的概念。

2. 可验证的查询

可验证查询技术在传统数据库领域被广泛研究，主要用于解决与外部数据库的信任问题。在很多场景中，数据所有者可能不会选择自己存储数据，而是将数据库需求委托给第三方提供数据库服务（如云数据库）。然而，由于第三方并不总是可信的，因此他们返回给用户的查询结果的可信度很难保证。目前针对传统数据库的可验证查询解决方案主要分为两类：基于ADS（认证数据结构）的解决方案和基于可验证计算的解决方案。

ADS 是一种在传统数据库中广泛使用的可验证查询技术，大多建立在哈希树（Merkle Trees）或类似的累积结构之上。随着密码学工具的发展，许多研究人员逐渐开始探索使用可验证计算技术来解决不可信查询的问题。一些基于零知识证明协议的可验证计算方案（如 SNARKs）可以间接支持外部数据库的可验证查询。这些方案支持多种查询类型，生成的验证信息较少，但计算开销较高。

目前，以太坊使用哈希树来实现可验证查询，而 Verkle 树技术也是基于哈希树技术。因此，我们先以哈希树为例，介绍一下哈希树，帮助读者理解可验证查询的作用。

3. 哈希树

3.1. 哈希树的定义和特点

哈希树是密码学中常用的树状结构，适用于解决数据完整性问题。下面是一个典型的哈希树结构：叶子节点代表原始数据或其哈希值，每个非叶子（内部）节点包含其子节点的哈希值组合。

哈希树有两个重要特征：

1. 抗篡改性： 梅克尔树通常使用抗碰撞散列函数构建，因此要找到产生相同散列值的两个不同信息在计算上是不可行的。从哈希树的结构可以看出，对叶节点内的交易数据进行任何修改，都会导致树根哈希值发生变化。
2. 高效验证大型数据集的完整性： 验证者只需存储哈希树的根散列值，即可验证任何数据的完整性。要做到这一点，无需传输完整的数据集，而是通过使用从叶到根的路径上的同级节点-梅克尔路径（Merkle Path）。这些同级节点可用于重建根散列，以便验证。

3.2.如何构造Merkles证明？

在常见的可验证查询场景中，有一个证明者和一个验证者。证明者需要生成一个证明并发送给验证者。与以太坊网络相对应，典型的应用场景是轻节点（只存储区块头的客户端）从全节点或归档节点（拥有所有数据的客户端）查询交易数据，并获取 Merkle 证明来本地验证查询结果是否正确。

1. Merkle 证明由以下三部分组成：
2. 完整数据集的 Merkle 树根哈希值。
3. 需要证明其完整性的数据块。
4. Merkle 路径，包括从叶节点到根节点路径上所有同级节点的值。

其中，哈希树的根哈希值需要提前通过可信的方式发送给验证者，验证者必须信任这个值。在以太坊中，区块数据的可信度由共识算法来保证，而哈希树的根哈希值包含在区块头中。

下面是一个具体的例子：当证明者需要向验证者证明 “4 ”是数据集中存在的一个数据块，而验证者持有完整数据集哈希树的可信根哈希值 “1d25 ”时，证明者只需提供所有标为蓝色的数据。假设数据集中有 n 个数据块，验证任何数据块的正确性最多需要进行 𝘭𝘰𝘨₂(𝘯) 次哈希计算。

以太坊的轻节点只同步区块头，其中包含各种数据集（状态树、交易树、收据树）的哈希树根。当轻节点向完整节点查询树中某个叶节点的数据时，完整节点会返回原始数据以及相应的 Merkle 证明路径。这样，轻节点就可以相信查询结果的正确性。

3.3. 哈希树的变体

在哈希树的基础上，可以根据不同的目标，将其与其他数据结构进行组合和修改，以实现新的特征。为了满足各种可验证的查询场景，哈希树可以扩展为各种索引数据结构，如梅克尔-B 树（MBT）。为了高效执行插入、删除和查询等操作，以太坊团队提出了默克尔-帕特里夏树（Merkle Patricia Tree，MPT）。

3.3.1. Merkle-B 树

Merkle-B 树（MBT）主要用于处理可验证范围查询。设 𝑓 为 MBT 的扇出数（每个节点的子节点数）。基于 B+ 树结构，MBT 的每个内部节点除了存储 𝑓 - 1 个索引键和指向 𝑓 个子节点的指针外，还以摘要形式维护其所有子节点的哈希值。下面是 MBT 中叶节点和内部节点的结构示意图。

当需要证明从某个范围查询返回的数据符合指定范围时，计算验证对象（VO）的服务器必须首先执行两次自上而下的搜索操作，以找到左边界和右边界。它还必须返回该边界内的所有数据以及所有分支的哈希值，以便构建通向根哈希值的路径。

这种数据结构的缺点是，返回的 VO 只能证明查询结果在请求的查询范围内，但不能证明返回的结果是完整的。

3.3.2.Merkle Patricia Tree

如果使用纯粹的哈希树来提供可验证的查询，则每次插入或删除数据后重新生成哈希树根的过程都会非常耗时。此外，它还需要维护额外的数据搜索树以进行存储。Merkle Patricia Tree，（简称 MPT）结合了 Radix 树（紧凑前缀树）和哈希树的属性，可以在 O(log(N)) 时间内完成插入、删除和查询。要全面了解 MPT，读者可以参考相关的详细技术文章。本文仅介绍一些基本定义，并举例说明，以帮助读者快速理解 MPT。

以太坊的底层结构采用键值数据库进行存储，即数据以键值对的形式存储。MPT 也分解成键值对进行存储。我们将 MPT 节点的逻辑结构定义如下：

• 索引
• 路径
• 数据

在 Merkle Patricia Tree（MPT）的语境中，“索引 ”指的是键值对的键，而 “路径 ”与 “数据 ”相结合则构成了键值对的值。索引实际上存储了哈希树节点的哈希值，而路径则对应于前缀树中用于查找目标节点的路径字符串。以太坊使用十六进制字符串作为路径字符串，因此 MPT 的宽度为 16。数据是与路径相对应的目标数据。

下面是一个用压缩前缀优化过的 MPT 示例，其中存储了以下键值对数据：

{

cab8’: ‘dog’、

cabe’：’猫

39’：’鸡

395’：’鸭

56f0’：’马

}

要使用路径 “395 ”找到数据 “鸭子”，就必须从根散列开始，经过散列 A、散列 C 和散列 D，最终找到目标数据。下面是一个详细步骤指南：

1. 根散列： 这是 Merkle Patricia Tree (MPT) 的入口点，您可以用它找到第一个节点。
2. hashA：根据根切細值，您将检索由 hashA 标识的节点或内容。由于路径是 “395”，因此您要查找的是树中通向 “3 ”的部分。
3. hashC：访问完 hashA 的内容后，继续沿着路径查找。下一个片段 “9 ”会将你引向 hashC。
4. hashD： 最后，继续沿着路径前进，最后一个数据段 “5 ”将指向 hashD，其中包含值 “duck”。

在路径的每一步，MPT 都利用了 Radix 树和 Merkle 树的特性，前者可以根据密钥找到正确的路径，后者可以通过散列链接确保数据的完整性。树中的 “路径 ”通常用十六进制编码表示，与树的分支因子 16 相对应。路径中的每个节点都包含足够的哈希指针（指向子节点）和值，用于验证数据的完整性和在树中导航。

请注意，在真正的 MPT 中，路径和数据将以特定格式编码和存储，而额外类型的节点（如扩展节点和叶节点）有助于优化结构，以提高不同场景下的效率。

4.矢量承诺

承诺[1] 方案是确保数据隐私和完整性的加密原语。它们广泛应用于零知识证明和安全多方计算等场景。基本的承诺方案分为两个阶段：承诺阶段和揭示（或开放）阶段。

1. 承诺阶段： 在这一阶段，提交者使用加密算法将信息与承诺值绑定，并将承诺值发送给接收者。在这一阶段，承诺具有两个属性：隐藏和绑定。隐藏确保除承诺者外，其他人都不知道承诺信息的内容。绑定确保一旦做出承诺，包括承诺者在内的任何人都无法更改。
2. 揭示（公开）阶段： 在此阶段，提交者可以向接收者证明他们收到的承诺值是对原始信息的有效承诺。承诺具有正确性，这意味着如果提交者和接收者都正确地遵守协议，接收者就会确信他们在提交阶段收到的承诺值是对原始信息的有效承诺。

矢量承诺是 Catalano 等人 [2] 提出的一种特殊的承诺方案，它允许承诺者对一组有序的信息 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚△ ⟩ 作出承诺，并在任何指定位置揭示（打开）以证明信息 𝑖 𝑚 是第 ↔ 个承诺的信息。在矢量承诺中，绑定意味着任何人都不能在相同的位置来揭示不同的信息。

向量承诺方案通常由以下算法组成：

5. Verkle 树

5.1. Verkle树的定义和特征

定义：Verkle 树 = 矢量承诺 + Merkle 树。

请注意：以太坊联合创始人维塔利克-布特林（Vitalik Buterin）有一篇专门介绍 Verkle 树的博文。本章根据他的博客补充了一些背景和数学知识。下文中的部分数据和插图来自他的博客。

与哈希树相比，Verkle 树（VT）的特点是提供更小的证明。对于数十亿条目的数据规模，哈希树可能会生成约 1KB 大小的证明，而 Verkle 树的证明可能小于 150 字节。这种紧凑的证明大小有利于实现 “无状态客户端”。

Verkle 树的结构与 Merkle Patricia 树（MPT）有些相似。下面是一个结构示例。Verkle 树的节点可以是：(i) 空节点，(ii) 包含键及其相应值的叶节点，或 (iii) 带有固定数量子节点的内部节点。子节点的数量也称为树的 “宽度”。

VT（Verkle 树）和 MPT（Merkle Patricia 树）之间的区别主要在于树宽（或扇出，指树上一个节点的子节点数）如何影响它们的效率。就 MPT 而言，如果宽度越大，效率往往越低，因为宽度越大意味着同级节点越多，这可能导致 MPT 更新时间更长，证明大小更大。相反，对于 VT 来说，树的宽度越宽，证明就越小。唯一的限制是，如果宽度过大，生成证明所需的时间就会变长。

在以太坊的 VT 设计提案中，建议的树宽为 256，比目前 MPT 的 16 大得多。在 VT 中使用如此大的宽度是可行的，因为使用了先进的加密技术，如向量承诺，无论树的宽度如何，都能实现紧凑的证明。这种压缩技术使 Verkle 树能更有效地扩展证明大小。下文将更详细地解释上述特点。

5.2. Verkle Trees的承诺和证明

让我们来看看 MPT 是如何生成证明的： 证明需要包括从根节点到目标叶节点路径上所有边节点（或姐妹节点）的哈希值。以 “4ce ”为例，下图中红色标记的部分就是返回的证明中需要包含的节点。

在 Verkle 树中，你不需要提供同级节点；相反，你只需要提供路径和一些额外的数据作为证据。

那么，如何为 VT 生成承诺呢？用于计算的哈希函数不是传统的哈希函数，而是使用向量承诺。

用向量承诺生成算法取代散列函数后，所谓的根散列就是根承诺了。如果任何节点的数据被篡改，最终都会影响根承诺。

如何生成证明？如下图所示，只需提供三个子证明，每个子证明都能证明路径上的节点存在于其父节点的某个位置。宽度越宽，层数越少，所需的子证明也就越少。

在实际应用中，使用多项式承诺（可以简单有效地实现向量承诺），允许对多项式进行承诺。最方便用户使用的两种多项式承诺方案是 “KZG 承诺 ”和 “防弹式多项式承诺”（前者的承诺大小为 48 字节，后者为 32 字节）。

如果采用 KZG 承诺和证明，每个中间节点的证明只需 96 字节，与基本梅克尔树（假设宽度为 256）相比，节省了近三倍的空间。

对哈希树和 Verkle 树进行操作的理论时间复杂度如下：

迄今为止介绍的 Verkle 证明方案是相当基本的；事实上，还有更高级的优化策略可供选择。

5.3.优化：合并证明

5.3.1.概念

与为路径上的每一层承诺生成一个证明相比，可以利用多项式承诺的特性，实现 “用一个固定大小的证明来证明路径上所有承诺之间的上下级关系，这个证明可以包括无限多的元素”。要具体理解如何实现这一点，有必要引入一些数学知识进行解释。本文将涉及一些数学公式，但原则上不涉及证明的加密部分。具体方法请参考通过随机评估实现多重证明的方案。

5.3.2.数学推导

首先，让我们介绍数学中有关多项式的一些基本概念：我们如何进行多项式还原，也称为多项式的度数还原？

假设我们知道一个多项式 𝑃(𝑥)及其在 𝑥₁处的值 𝑦₁，即 𝑃(𝑥₁)=𝑦₁。

现在，考虑一个新的多项式 𝑃(𝑥) - 𝑦₁ ，它在（𝑥 = 𝑥₁）处的值为零，因为 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0。

因此，多项式 𝑃(𝑥) - 𝑦₁ 在 𝑥 = 𝑥₁ 有一个根，这意味着 (𝑥 - 𝑥₁ ) 是 𝑃(𝑥) - 𝑦₁ 的因子。

换句话说，我们可以用下面的形式表示它： [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)] 。

𝑄(𝑥)是另一个多项式，其阶数比𝑃(𝑥) 少一级。这是因为 (𝑥 -𝑥₁ ) 是一个一级因子，它减小了多项式的总阶数。

如何使用 KZG 证明向量中的单值？

以 KZG10 承诺为例，对于多项式 𝑃(𝑥) ，假设其多项式承诺为 [ 𝑃(𝑠) ]₁ 。

如前所述，对于多项式 𝑃(𝑥) ，如果 𝑃(𝑧) = 𝑦 ，则 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧) 。

现在，证明者可以生成多项式 𝑃(𝑥) 满足 𝑃(𝑧) = 𝑦 的证明：计算 [ 𝑄(𝑠) ]₁ 并将其发送给验证者。

验证者需要验证 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) 。

如何使用 KZG 证明向量中的多个值？

我们可以构建如下证明来证明向量中的多个值：

使用这种方法，无论同一向量中有多少数据点需要验证，都只需要一个大小不变的证明。

现在，让我们从 KZG 承诺算法的角度来看看未经优化的 Verkle Tree 方案。

使用 “如何使用 KZG 证明向量中的单个值 ”一节中的构造方法，验证者可以为每个多项式 𝑓ᵢ(𝑥) 构造原多项式和商多项式的承诺，从而得到总共 𝟐﹡𝑚 KZG 承诺。验证者发送所有这些承诺作为验证证明。

然而，如前所述，这种方法需要生成多个证明，验证者也需要进行多次验证计算。我们需要找到一种方法来压缩多个承诺证明。

合并证明

证明者将证据 [ 𝑞( 𝑠 )]₁ 发送给验证者进行验证。

该方案生成的证据包括一个承诺、两个证明和一个值，数据大小保持不变。最终，在 Verkle 树的证明合并优化之后，发送给验证者的可验证数据对象包括以下内容：

1. 固定大小的证据
2. 待验证的叶子数据（键值对）
3. 从叶子到根节点路径上所有节点的承诺值（假设树的宽度为 256，有 2³² 个节点，平均深度为 4，仅需要 3 个承诺值）

请注意，𝑥ᵢ 和 𝑦ᵢ 不需要明确提供，它们都可以计算出来。

5.3.3 性能

关于 Verkle 树的证明合并方案，生成证明的具体大小如下（行的单位是亿）：

上述数据假设使用树的宽度为 256，采用 KZG 承诺方案（承诺大小为 48 字节），并最大限度地提高树的利用率。实际上，对于完全随机的信息分布，树的深度将增加约 60%，每个元素的大小将增加 30 字节。如果使用防弹证明方案，则承诺大小为 32 字节。

5.4.证明者和验证者计算负载

1. 证明生成： 证明者生成证明的成本与树的宽度有关，但每个原子操作所需的计算成本相对较低，因此宽度在 256 到 1024 之间的 Verkle 树在算法方面表现良好。
2. 证明验证： Vitalik 表示，验证算法非常快，即使有几千个值需要验证，通常也能在 100ms 内完成。
3. 更新 Verkle 树时： 由于值或结构的变化，更新树需要重新计算路径上的所有中间承诺值。不过，Vitalik提到，由于多项式承诺算法的一些特性，可以设计一种方法，预先计算替代承诺值并存储它们，从而减少更新时的计算时间成本，这实质上是用空间换时间。

6.结论

以下是 vitalik 博客的原话，我们在最后添加了一段作为补充。

Verkle 树是 Merkle 证明的强大升级版，它允许更小的证明规模。证明者不需要提供每一层的所有 “姊妹节点”，而只需提供一个证明，证明从每个叶节点到根节点的路径上所有承诺之间的所有父子关系。与理想的哈希树相比，这使得证明规模减少了 ~6-8 倍，与以太坊目前使用的六叉Patricia trees相比，则减少了 20-30 倍（！！）。

它们的实现需要更复杂的加密技术，但却为扩展性带来了巨大的潜力。中期来看，SNARKs 可以进一步改善情况：我们可以将已经高效的 Verkle 证明验证器 SNARK 化，将见证大小减少至接近零，或者在 SNARKs 显著改进时（例如，通过 GKR、非常适合 SNARK 的哈希函数或 ASICs），重新切换回 SNARKed Merkle 证明。而在更遥远的未来，量子计算的崛起将迫使我们转向以哈希为基础的 STARKed Merkle 证明，因为它会使 Verkle 树所依赖的线性同态变换不再安全。但目前而言，它们给我们带来了与这些更先进技术相同的扩展收益，而我们已经具备了实现它们所需的所有工具。

目前，许多以太坊客户端已经提供了 Verkle 树及其相关测试网络的实现。社区仍在讨论 Verkle 树何时将在主网络上启用。很可能会在 2024 年或 2025 年通过硬分叉升级实现。有关以太坊上 Verkle 树的详细信息，请参阅 https://verkle.info/ 。

7. 参考文献

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Minimum disclosure proofs of knowledge[J]. Journal of computer and system sciences, 1988, 37(2)： 156-189.

[2]. CATALANO D, FIORE D. 矢量承诺及其应用[C]//Public-KeyCryptography-PKC 2013： 第 16 届国际公钥密码学实践与理论会议，日本奈良，2013 年 2 月 26 日至 3 月 1 日。论文集 16. Springer, 2013： 55-72.

声明：

1. 本文转载自[ZAN]，著作权归属原作者[AntChain Open Labs and ZAN]，如对转载有异议，请联系Gate Learn团队，团队会根据相关流程尽速处理。
2. 免责声明：本文所表达的观点和意见仅代表作者个人观点，不构成任何投资建议。
3. 文章其他语言版本由Gate Learn团队翻译， 在未提及Gate.io的情况下不得复制、传播或抄袭经翻译文章。