感谢 Guillaume Ballet 和 Tanish Jasoria 的回馈，以及感谢 Stateless Implementors Call 参与者就此主题进行的先前讨论。

在本文中，我们深入探讨状态树原像生成主题，包括：

• 解释足够的背景来理解该主题适合协议演进的位置。
• 需要对 EIP-7612 和 EIP-7748 进行高层解释才能正确理解该问题。
• 为原像提出潜在的文件格式，并分析更复杂的格式是否值得。
• 提供一个新的原像工具，使用非存档 reth 来产生和验证原像文件，并产生本文中使用的数据，以便可以重现。

如果您知道为什么需要为未来的树转换产生原像，请跳过上下文部分。

情境

路线图的Verge部分提议用新树取代目前的 Merkle Patricia Trie (MPT)，新树在实现无状态性和进一步 SNARKifying L1 方面更加有效。

当今的主要树候选是 Verkle 树 ( EIP-6800 ) 和二叉树 ( EIP-7864 )。如果您想了解有关这种二分法的更多信息，请阅读EIP-7864 讨论主题。本文的主题与该决定无关，因此您可以假设任何未来的道路。

由于使用了新树，我们需要一个策略将现有资料从 MPT 移至新树。今天提出的策略是使用覆盖树（ EIP-7612 + EIP-7748 ）转换数据，我们稍后会进行探讨。

假设我们想将帐户的资料（nonce、balance、code hash）从 MPT 移至新树。 MPT 中的树键是keccack(address) ，但在新树中，它是new_key(address) ，其中new_key不一定是keccak 。 EL 用户端必须能够存取树中每个键的底层原像（即，在本例中为address ）。如果他们只有keccack(address)就不可能计算new_key(address) 。这同样适用于帐户状态尝试。

简而言之，网路中每个将经历从 MPT 到新目标树的状态转换的节点都应该能够解析帐户和储存树的每个 MPT 金钥原像。

EL 用户端不储存树密钥原像吗？

不幸的是，没有。根据 EL 用户端的当前架构和资料库设计，这些原像可能是根据现有资料计算出来的，但这仅适用于少数客户端。

树密钥原像和客户端资料库之间关系的一些范例：

• Geth 有一个 flatdb，可以比使用树更快存取状态。此资料库中的键是帐户的杂凑值或帐户杂凑和储存槽哈希的串联，即基于哈希的键。使用杂凑版本的金钥对于同步来说是有意义的，并且从来没有真正的动机来证明保存原像的额外储存是合理的。
• Erigon 和 Reth 也有一个 flatdb，但是该资料库中的键是未散列的树键，这对于解决这个问题非常方便。
• Nethermind 还没有 flatdb，所以它依赖高效地访问树来进行状态访问，但他们计划很快推出（密钥散列）flatdb。

这意味著，除非您是 Erigon 或 Reth 节点，否则您没有树键的实际原像。据ethernodes.org称，非 Erigon+Reth 节点占网路的 80% 以上，这意味著大多数网路都存在这个原像问题。即使对于 Erigon 或 Reth 节点，能够获取原像也并不意味著他们现在有有效的方法来解决它们。为了更好地理解这一点，让我们更深入地探讨原因。

原像在树转换中如何使用？

了解覆盖树和状态转换 EIP 如何协同工作可以更好地回答这个问题。您可以阅读 EIP，但这里有一个压缩摘要，可以继续进行原像讨论。

EIP-7612 概述

注意：此 EIP 引用了 Verkle，但该想法与目标树无关，因此它也适用于二元树。

EIP-7612 解释如何将新树引入协定：

• MPT 在分叉区块处变为唯读（即冻结）。
• 建立一棵新的空树（例如，Verkle 或 Binary）。
• 区块执行产生的状态更新仅写入新树。
• 副作用是，仅使用树读取状态意味著读取新树，如果未找到条目，则检查 MPT。

总之，它是一个两级（即覆盖）树，其中基础树（MPT）被冻结，而顶部树（Verkle 或 Binary）从头开始，接收写入。关于最后一条，EL 用户端有一个 flatdb 来存取状态，所以并不一定意味著您必须进行双树查找。

EIP-7748 概述

现在我们了解了 EIP-7612，接下来就是 EIP-7748 发挥作用的时候了：

• 在定义的区块时间戳记（ CONVERSION_START_TIMESTAMP ）处，转换过程开始。请注意，EIP-7612 活化和CONVERSION_START_TIMESTAMP之间必须有足够的时间，这样我们才能保证 MPT 被冻结（即，链已完成，因此任何重组都无法改变这一事实）
• 在下一个区块中，在执行交易之前：
  • 确定性地从 MPT 中取得CONVERSION_STRIDE树条目。
    • 树条目的概念在 EIP（即命名转换单元）中定义更精确——我们在这里稍微简化了一下。
    • CONVERSION_STRIDE 值仍有待确定，因为它是The Block执行状态转换开销和完整转换持续时间之间的权衡。正确的值取决于哪个是目标树，因为 Verkle 比 Binary 具有更昂贵的重新散列。
  • 如果它不是一个过时的值，我们会将其复制到顶部树中 - 由于 EIP-7612 已被激活，区块执行可能已经为这个 MPT 键写入了一个新值，该值不能被覆盖。
• 继续执行上述操作，直到我们完成所有 MPT 键的遍历。

状态转换步骤发生在交易执行之前的设计决策是有益的，因为 EL 用户端可以在下一个区块到达之前执行状态转换步骤。

与原像档案相关的这个过程的主要事实是我们对 MPT 条目进行迭代的顺序。目前建议的顺序是在 MPT 中进行完整的深度优先遍历 (DFW)：在帐户 trie 中执行 DFW，当到达叶子节点时，在帐户储存 trie 中执行 DFW，然后继续遍历帐户尝试。我们先迁移帐户储存槽，然后迁移帐户的资料。

让我们看一个例子来更好地理解它。假设CONVERSION_STRIDE为 5，且我们处于状态转换的第一个区块。以下是我们在步行过程中可能会看到的 MPT 条目：

1. 帐户 trie 金钥0x000000abc...等于keccak(address_A) 。我们注意到address_A有一个带有两个储存槽的储存 trie，因此我们将 DFW 放入其中。
   1. 步骤＃1：帐户address_A储存树的金钥为0x0000131...等于keccack(storage_slot_A) ，这表示我们将address_A的storage_slot_A值迁移到新树。
   2. 步骤＃2：帐户address_A储存树的金钥为0x0003012...等于keccack(storage_slot_B) ，这表示我们将address_A的storage_slot_B值迁移到新树。
   3. 步骤#3：由于我们迁移了所有储存槽，我们现在迁移address_A帐户的nonce，balance和code。
2. 帐户 trie 金钥0x000000ffa...等于keccak(address_B) 。 address_B是 EOA
   1. 步骤＃4：没有储存槽，因此在储存 trie 中没有完成 DFW。我们迁移address_B帐户的nonce、balance、以及code。
3. 帐户 trie 金钥0x000005630...等于keccak(address_C) 。我们注意到address_C有一个包含 1000 个储存槽的储存 trie，因此我们对其进行 DFW。
   1. 步骤＃5：帐户address_C储存树的金钥为0x0000021...等于keccack(storage_slot_A) ，这表示我们将address_C的storage_slot_A值迁移到新树。

请注意以下几点：

• 帐户 trie 和潜在 trie 中的行走顺序是基于哈希的，而不是地址或普通的储存槽值。这是 trie 中 DFW 的结果，因为键是位址或储存槽的杂凑值。
• storage_slot_A与address_A和address_C是不同的数字（例如分别为 10 和 24）。它们的意思是 DFW 在储存尝试中行走时发现的第一个储存槽。如上文所述，储存槽行走顺序是基于哈希的，而不是「自然」排序，因此storage_slot_A可以大于storage_slot_B 。
• 上述观点也是我们需要原像的原因——第一个键的值为0x000000abb ，您需要知道它对应于地址address_A以便您可以重新散列以确定新树中哪个键。
• 最后迁移的条目只是account_C的第一个储存槽，但我们仍然有 99 个剩余的槽。由于我们已经达到 CONVERSION_STRIDE 限制，我们将在下一个区块中继续迁移这些内容！

您还可以在此处找到有关此 EIP 的讨论，其中有一些视觉效果可以帮助补充此解释。

回顾

以上内容可望澄清以下事实：

• 原像档案必须包含冻结的 MPT 帐户树中所有现有的address_X 。
• 原像档案必须包含所有冻结的 MPT 储存尝试中所有现有的storage_slot_X 。
• 由于 MPT 是冻结的，行走是确定性的，我们需要原像的顺序是完全预先决定的。

原像文件

现在我们深入研究这个原像文件的不同维度：

• 分配
• 可验证性
• 产生和编码
• 用法

本文主要关注生成和编码，但为了完整性我们也涉及其他维度。在我们到达生成部分之前，请假设该档案是神奇地生成和编码的。

分配

假设原像档案以某种方式生成，那么该档案如何到达网路中的所有节点？在无状态实施者呼吁 (SIC) 、L1 事件研讨会和非正式讨论中多次探讨这个主题。

在与许多（但总体样本较小）核心开发人员交谈后，目前的共识是，期望客户端透过多个潜在的 CDN 下载此文件可能是可以的。原像。

其他讨论的选项包括：

• 具有协议内分发机制。
• 将所需的原像分发到每个区块上。

这个主题非常有争议，因为这些选项在复杂性、协议热路径所需频宽和压缩机方面有不同的权衡。尽管与许多核心开发人员进行了交谈，但他们的代表性仍然不足以得出结论说 ACD 会得出相同的结论。

本文主要讨论原像的生成和编码格式，无论这个文件如何分发，我们都必须这样做。

可验证性

如上所述，完整节点将从可能不受信任的一方或被骇客入侵的供应链的地方接收此文件。如果档案损坏或无效，则完整节点将在转换过程的某个时刻被阻止。

透过执行所描述的树遍历、读取预期的原像、计算 keccak 杂凑值并验证它是否符合客户端的期望，可以轻松验证该档案。验证此文件后，无论何时开始转换，都可以安全地使用它，并保证客户端不会因解析原像而被阻塞——此保证对于转换期间网路的稳定性至关重要。此验证时间必须考虑到 EIP-7612 启动和 EIP-7748 CONVERSION_START_TIMESTAMP时间戳之间的时间延迟*。

当然，验证此文件的其他方法更快，但需要更多假设。例如，由于产生档案的任何人都会获得相同的输出，因此客户端团队可以自行产生并对档案的杂凑值/校验和进行硬编码。当档案被下载/汇入时，验证可以将档案的杂凑值与硬编码的杂凑值进行比较。

产生和编码

现在我们知道文件必须包含哪些资讯以及以什么顺序存取这些讯息，我们可以考虑如何在文件中对这些数据进行编码。理想情况下，我们希望编码能够满足以下属性：

• 针对预期的读取模式进行最佳化：状态转换是主链运行时在背景进行的任务，因此读取所需资讯应该是高效率的。
• 优化大小：如前所述，文件必须以某种方式分发。频宽是一种宝贵的资源；用得少一点比较好。
• 复杂度低：此文件只会使用一次，因此简单的编码格式就好。透过创建新的复杂格式来重新发明轮子是没有意义的，除非它们能够提供特殊的好处，但同时需要更长的时间来确定和测试。

有一个非常简单且明显的候选编码，可以按照我们之前探索的范例进行如下描述： [address_A][storage_slot_A][storage_slot_B][address_B][address_C][storage_slot_A]... 。我们按照预期的行走顺序将原始原像直接连结在一起。

这种编码有以下好处：

• 由于不需要前缀字节，因此编码格式没有任何开销。尽管原像条目具有不同的大小（位址为20 位元组，储存槽为32 位元组），但EL 用户端可以知道接下来要读取多少位元组，这取决于它们是否应该解析树遍历中的位址或储存槽。
• EL 用户端始终对档案进行前向线性读取，因此不存在随机存取。即将到来的使用部分将对此进行扩展。

在深入研究这种编码的效率之前，让我们尝试为主主网产生此档案并了解其大小。为此， 我们创建了一个工具，使用同步的 reth 完整节点（即不一定存档）来产生、验证和执行稍后将介绍的其他分析。不久前，我们创建了一个geth 工具，但它需要从 genesis 同步节点并启用--cache.preimages标志。

我们可以透过执行preimages generate --datadir <...> --eip7748来建立原像档案。以下是有关中阶机器中产生的档案的一些事实：

• 生成时间：~1 小时
• 未压缩的档案大小：42GiB
• 压缩档案大小（zstd）：36GiB

请注意，网路中运行 Reth（或潜在的 Erigon）节点的任何人都可以产生该文件，并且输出始终相同，因为给定一个冻结的 MPT，原像就是固定的。

深入研究编码效率

尽管编码格式的编码开销为零，但压缩和未压缩大小之间的差异表明了压缩机。让我们来探究为什么会出现这种情况。

我们可以将文件中的每个原像条目放在两个储存桶中：

• 解决原像
  • 重复资料删除
    • 由于帐户树包含每个帐户的唯一讯息，因此文件中每个[address_X]条目都是唯一的，因此不存在重复资料删除的机会。
  • 压缩：
    • 位址是哈希值，因此没有机会压缩它们。
• 储存槽原像
  • 重复资料删除
    • 它们在文件中重复，因为多个合约可以（并且确实）在储存槽使用上重叠。例如，多个合约使用储存槽 0、1 和 2。
    • 最大的重复储存槽组是顶级槽，因为它们共享0x00000...前缀（例如，上一个项目中提到的那些）。
    • 当合约具有数组或哈希图时，由于哈希将变数映射到储存槽的性质，储存槽在储存槽空间中变得更加分散。
  • 压缩
    • 储存槽的压缩机会各不相同。例如，带有0x00000..前缀的储存槽（即顶部合约变数）非常可压缩，因为它们具有许多零位元组。其他储存槽主要都是哈希的结果；它们并不是那么可压缩（但可「重复资料删除」）。

总之，位址无法被重复资料删除或压缩，但储存槽确实有机会被重复资料删除/压缩。然而，很难知道其影响会有多大以及是否值得。

若要进行更深入的分析，您可以执行preimage storage-slot-freq分析工具。我们先看一下输出：

 Database block number: 21662206 Top 1000 storage slot 29 -byte prefix repetitions: 0000000000000000000000000000000000000000000000000000000000 : 57150357 ( 4.65 %) ~1580MiB (cumm 1580MiB)f3f7a9fe364faab93b216da50a3214154f22a0a2b415b23a84c8169e8b: 13671109 ( 1.11 %) ~378MiB (cumm 1958MiB)8a35acfbc15ff81a39ae7d344fd709f28e8600b4aa8c65c6b64bfe7fe3: 9429136 ( 0.77 %) ~260MiB (cumm 2219MiB)f652222313e28459528d920b65115c16c04f3efc82aaedc97be59f3f37: 8580073 ( 0.70 %) ~237MiB (cumm 2456MiB)405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3: 7750842 ( 0.63 %) ~214MiB (cumm 2671MiB)a66cc928b5edb82af9bd49922954155ab7b0942694bea4ce44661d9a87: 3545488 ( 0.29 %) ~98MiB (cumm 2769MiB)c2575a0e9e593c00f959f8c92f12db2869c3395a3b0502d05e2516446f: 2663837 ( 0.22 %) ~73MiB (cumm 2842MiB)...

（完整输出较长，可在此处找到）

此程式计算具有相同 29 位元组前缀的储存槽数量，例如前缀00000....00 ：

• 储存槽位数量约5700万个，占总量的4.65%。
• 它映射到原像档案大小的~1580MiB。
• cumm值是到目前行为止的大小总和。例如，前 3 个储存槽原像前缀占原像档案的 2219MiB。

您可能想知道第二行、第三行和接下来行中的值是什么：

• f3f7...是keccak(0x000000..08)
• 8a35...是keccak(0x000000..04)

这些前缀的出现是因为许多合约分别在储存槽 8 和 4 中定义了阵列。这意味著原像档案中的值是这些插槽号码的杂凑值。由于数组中的项是从该基值连续的，因此这些“顶级数组”是原像文件中的顶部前缀。

选择 29 个位元组作为前缀没有什么特别之处；这个想法是捕获分组顶级变数和数组。对于杂凑图，条目分布在整个储存槽空间中，因此重复资料删除的机会较少。随著合约变数中出现更多的“嵌套”，这种可能性会更低。这就是为什么顶部前缀是顶级数组，所以它是有意义的。

如果您查看完整的输出链接，前 1000 个前缀占 ~4GiB，接近我们透过 zstd 获得的 ~6GiB 压缩。当然，尾巴很长，所以最佳尺寸可能更好。

尝试将重复资料删除作为档案格式的一部分会增加档案格式规范的复杂性。可以透过分离要保存在 RAM 中的前 N ​​个原像来保留准线性读取。尽管如此，如果与简单格式 + zstd 相比，为了减小尺寸而增加额外的复杂性，那么这可能不值得。请记住，这是一次性下载。它可以在时段持续时间的非关键部分下载，甚至可以透过单独的网路连结下载（但这需要手动操作）。

请注意，尽管 zstd 是一种使用广泛的压缩工具，但它为 EL 用户端添加了新的依赖项。此外，可能需要额外的时间空间来解压缩档案（但可能有办法避免这种情况）。无论如何，本文的主要目标是提供有关储存槽尺寸尾部如何表现的真实测量，并引发有关该主题的更多讨论。

用法

值得一提的是有关 EL 用户端如何使用此文件的一些事实：

• 由于档案是线性读取的，因此保留一个游标来指示在下一个区块的开始处继续读取的位置很有用。
• 保留最后 X 个区块的游标位置清单有助于处理重组。如果发生重组，则很容易再次在档案中寻找相应的位置。
• 当客户端在插槽中大部分处于空闲状态时，客户端也可以在记忆体中预先载入下一个 X 区块原像，从而避免在The Block热路径执行中产生额外的 IO。
• 如果将整个档案保存在磁碟上太麻烦，您可以删除链终止点之后的旧值。我们怀疑这是否值得增加额外的复杂性，但这是一个取决于 EL 客户团队的实作细节。

结论

本文在树状转换协议演化的背景下探讨了原像文件的上下文、问题和解决方案空间。这里提出的想法都不是最终的，也不指望在 ACD 中达成明显的共识。

主要目标是提供足够深入的解释，以提高社区中尽可能多的人的水平，不断进步，并希望成为一种资源，以加快未来 ACD 关于这个主题的讨论。