Lighthouse tree-states ELI5 第一部分

Lighthouse v5.2.0 版本发布包括对其处理 BeaconState 数据结构方式的完整重构，该数据结构是以太坊共识层的核心。BeaconState 包括验证器数据，如激活时间、余额等。与执行层的状态 50GB+ 不同，信标状态足够小，可以完全放入内存中。由于信标链的巨大成功，状态已从创世时的 5 MB 增长到今天的 150 MB。在内存中进行布局，并使用缓存以实现快速访问，在主网上状态最终会更大，达到 500MB+，而在 Holesky 测试网上则达到 1GB。

问题是，我们不仅仅需要 1 个状态，我们需要不同时间点的几个状态 —— 在头部、在已证明的检查点、在最终确定时等等。当发生重组时，我们需要回溯并获取通常仅落后于头部 1 个 slot 的 pre-state。当我们从网络收到一个具有旧父级的区块时，我们必须再次加载并重新计算旧状态。这里存在一个权衡：我们希望尽可能快地处理一切（在内存中有更多的状态），但同时限制 Lighthouse 的内存使用（在内存中拥有更少的状态）。根本问题是，我们必须为每个状态支付 500 MB 的 RAM，但我们能做得更好吗？

你看，信标状态的变异恰好非常稀疏。我们可以利用这个事实，以一种消除数据重复的方式表示状态，这样每个额外的状态所花费的 RAM 远小于 500 MB。这样我们就可以鱼和熊掌兼得：大量的状态、更快的处理速度和有限的内存使用量。

为了可视化如何以差异方式存储突变，考虑一个保存所有数据的基本状态（绿色状态）。然后，后代状态包括指向其基本状态的指针以及它们的突变集合（黄色状态）。

这种方法是有效的，Lighthouse 将会把它用于其新的数据库方案中（待定）。然而，有一种更优雅的方法，使用来自函数式编程的 持久性 数据结构，利用一种称为 结构共享 的属性。

与其将 BeaconState 表示为一块扁平的内存，不如将数据布局为二叉 Merkle 树。树中的任何中间节点都可以指向另一个状态的数据，从而实现大规模的去重。

这非常适合区块链范例，在区块链范例中，我们有一棵从最新最终确定区块派生的区块树，并允许分叉选择在它们之中选择最佳的 tip。它也可以很好地加速状态哈希。在处理完每个信标区块后，我们必须对 BeaconState 进行哈希，作为二叉 Merkle 树。通过树状态，我们已经通过设计构建了这个二叉 Merkle 树！为了不必一遍又一遍地对相同的数据进行哈希，我们将哈希值附加到每个中间节点。并且由于其结构共享的性质，这些缓存的值可以被所有后代状态重用。

现在，我们可以将几乎所有这些状态保存在内存中，这意味着 Lighthouse 可以几乎立即跳回到任何未完成的状态。如果最终确定失败，我们仍然需要使用启发式方法来丢弃状态，但在 99% 的时间内，当最终确定是常规的时候，我们可以将每个状态都保存在内存中顺利运行。你可能会看到这使得重组能够更快地处理。我们不必进行大量的复制或缓存未命中，而是可以直接从内存中获取先前的状态并将新区块应用到其中。常规区块的生成和处理速度也更快，因为我们可以跳过保留先前状态所需的昂贵的复制步骤。复制从 O(n) 变为 O(1)！

让我们深入了解一下树状态是如何构建的。

Milhouse

这个库实现了持久的二叉 Merkle 树，并提供了一些技巧来批量处理和加速突变。请注意，它只实现了数组（Vector 和 List），因为 Containers 更小，无法从结构共享中受益。

这个名字是为了纪念 Milhouse Van Houten，我们必须认为他对树木略知一二，因为他的名字 – Houten 在荷兰语中是 “木制的”。荷兰语也是无可比拟的 Protolambda 的母语，他的 remerkleable 库是一个伟大的灵感来源。

树状态和持久性数据结构的主要缺点是，从大型数组中读取数据的成本更高。让我们比较一下对某个索引的随机访问。在常规数组上，你可以直接跳转到项目的位置。

但是，在二叉 Merkle 树上，你必须遍历多个指针（它们在内存中可能不是连续的）才能访问特定项目。

由于同样的原因，迭代的成本也更高。因此，Milhouse 库中的大部分复杂性都是为了优化使用大型树的成本。

这里 \(n\) 是存储在数组中的项目数。尽管迭代具有相同的大 O 时间复杂度（我们总共迭代约 2n 个节点），但由于指针追逐，常数因子要大得多。

如果你喜欢算法优化，那么接下来的部分适合你。让我们看几个策略示例，以最大限度地减少昂贵操作的树遍历。

批量应用更新

在修改我们的持久二叉 Merkle 树时，我们需要为每个叶子创建和重新绑定 log(n) 个中间节点。在执行信标区块期间，许多单独的节点被修改。我们不必每次都重新绑定所有这些 log(n) 个节点，而是创建一个临时的待处理更新层。在某种程度上，我们将差异叠加在我们的树上。然后，在完成执行后，我们一次性应用这些更新，从而最大限度地减少树遍历和重新绑定的总数。

对于我们叠加的待处理更新，我们使用从列表索引到值的映射。当一个值被更新时，它会被插入到这个映射中。通过在映射中查找待处理的更新并将其替换为最新的更新，支持对同一索引的多次更新。当调用者需要更新时，通过递归地向下遍历树并构建一个新树（将更新嫁接到现有树的未修改部分上），可以批量 应用 更新。为了有效地做到这一点，如果待处理的更新存储在一个 有序的 映射中，那么这是最容易的。这允许我们确定某个范围（子树）是否存在待处理的更新，并在没有待处理更新的情况下重用整个子树。默认映射是 VecMap（本质上是一个Vec<Option<T>>），尽管 Milhouse 也支持 BTreeMap。试验更多映射类型可能是进一步优化的途径。

在上图中，索引 2 和 3 被更新（绿色），因此该算法创建一个新的内部节点作为 2 和 3 的父节点（黄色）。然后，它创建新的父节点，向上遍历树（黄色），同时嫁接未修改的子树（灰色）。

要深入了解，请查看 with_updates_leaves 的源代码：

https://github.com/sigp/milhouse/blob/e838fd875d1bb7cec942741ca8c7c6d1a1bd3d9c/src/tree.rs#L157-L236

Rebasing

Milhouse 代码库中的另一个有趣的算法是 rebasing 的算法。当从磁盘加载状态时，Lighthouse 必须为正在加载的数据创建全新的树。Rebasing 是指根据已保存在内存中的现有树（例如，最终状态）来消除这些树的重复数据的过程。List 和 Vector 的 rebase 算法将两棵树作为输入，并创建一个与第二棵树等效的新树，但重用第一棵树中相同的子树，从而减少总体内存使用量。

该实现使用递归树遍历，最终比较叶子上的值，并根据该比较传播要采取的“操作”。例如，如果两棵树包含所有相同的叶子，那么该算法将从叶子开始并向上移动树来传播“相等替换”操作。我们使用以下观察结果：如果一个节点的左右子节点完全相等，那么该节点本身也完全相等，并且可以在 rebased 树中重用。

算法的完整细节位于 rebase_on 函数中：

https://github.com/sigp/milhouse/blob/e838fd875d1bb7cec942741ca8c7c6d1a1bd3d9c/src/tree.rs#L264-L405

测试

Milhouse 通过一套属性测试进行了完整的测试。我们生成测试用例，这些测试用例使用随机数据以随机顺序应用 Milhouse 支持的操作。我们将 Milhouse 计算的结果与每个测试的预期结果进行比较。Milhouse 类型的预期行为很容易根据 Rust 标准 Vec 类型的操作来指定。

除了属性测试之外，我们还使用模糊器来压力测试 Milhouse 的功能，并确保它没有崩溃且没有 bug。Milhouse 中的模糊测试工具使用 AFL+ 根据测试覆盖率来探索代码路径。

我们欢迎改进 Milhouse 代码，特别是在那些改进消除了错误范围并提高了可靠性的情况下。

Single-pass epoch processing

我们的树状态工作与我们以可证明正确的方式优化以太坊状态转换函数的研究密切相关。使用树状态进行迭代的更高成本促使我们将 epoch processing 优化为单次迭代（pass）。你可以在这个主题中阅读有关该项目和正在进行的形式化验证工作的更多信息：

https://ethresear.ch/t/formally-verified-optimised-epoch-processing/17359

如何运行树状态

自 2022 年以来，Lighthouse 提供了一种实验模式，其中包含两个主要功能。这些是：

内存树状态

本文的特点是在保持更多状态在内存中的同时减少 RAM。自 v5.2.0 起，它默认对所有 Lighthouse 用户启用。要运行它，只需将 Lighthouse 更新到大于或等于 v5.2.0 的版本即可。无需进一步操作。

具有分层状态差异的新存储布局

运行具有约 200GB 空间的共识存档节点，而今天为 2TB+。此功能尚未在 Lighthouse 稳定版中提供。要使用它，你必须从 https://github.com/sigp/lighthouse/releases 下载 Lighthouse 的实验版本。

在撰写本文时，可以在此处找到包含此功能的最新实验版本。

此功能已接近完成，即将推出™️，目标是 2024 年第三季度。

警告：实验性 - 使用风险自负

• 原文链接： blog.sigmaprime.io/tree-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～