Alert Source Discuss
🚧 Stagnant Standards Track: Core

EIP-2584: 带覆盖树的 Trie 格式转换

Authors Guillaume Ballet (@gballet)
Created 2020-04-03
Discussion Link https://ethresear.ch/t/overlay-method-for-hex-bin-tree-conversion/7104

Table of Contents

简述

本 EIP 提出了一种将状态 trie 格式从十六进制转换为二进制的方法：新值直接存储在“覆盖”十六进制 trie 的二进制 trie 中。同时，十六进制 trie 在后台转换为二进制 trie。当该过程完成时，两层合并。

摘要

本 EIP 描述了一个四阶段的过程来完成转换。

  • 在第一阶段，所有新的状态写入都将写入一个覆盖二进制 trie，同时将十六进制 trie 转换为二进制。区块格式被更改为具有两个存储根：十六进制 trie 的根（以下称为“基础”trie）和覆盖二进制 trie 的根。
  • 在给予矿工足够的时间来执行转换之后，第二阶段开始。覆盖树被逐步合并回到新转换的二进制基础 trie 中。从覆盖中删除固定数量的条目并将其插入到基础 trie 中。
  • 当覆盖 trie 为空时，第三个也是最后一个阶段开始。保存其根的字段将从区块头中删除。

动机

长期以来，人们一直有兴趣将状态 trie 从十六进制格式切换到二进制格式，原因在于证明和存储大小。转换过程提出了一个追赶问题，这是由完整状态的庞大规模引起的：它无法在合理的时间内（即与区块时间相同的数量级）进行转换。

规范

本规范遵循 黄皮书 引入的符号。在阅读之前，建议先熟悉黄皮书。

二进制 tries

本 EIP 假设二进制 trie 的定义与 MPT 类似，除了：

  • I₀ 中的字节序列被视为一系列_位_，因此对于所有 i≤256，I₀[i] 是键 I₀ 中的第 i 位
  • 扩展或叶子的第一项用位替换 nibbles；
  • 分支是一个 2 项结构，其中两项都对应于密钥在其遍历中的此点上每个可能的位值；
  • c(𝕴,i) ≡ RLP((u(0), u(1)) 在一个分支上，其中 u(j) = n({I : I ∈ 𝕴 ⋀ I₀[i] = j}, i+1)

令 ß 为一个函数，给定一个十六进制 trie，计算该 trie 在上述二进制 trie 格式中的等效表示。

阶段 1

令 h₁ 为先前商定的区块高度，阶段 1 从该高度开始，h₂ 为阶段 2 开始的区块。对于每个高度 h₁ ≤ h < h₂ 的区块：

  1. 在后台启动转换过程，将十六进制 trie 转换为其二进制等效项。此过程的最终目标是计算_转换后的二进制 trie 的根哈希_，表示为 Hᵣ²。十六进制 trie 的根此后称为 Hᵣ¹⁶。形式上，此过程写为 Hᵣ² ≡ ß(Hᵣ¹⁶)。
  2. 区块头包含一个新的 Hₒ 字段，它是_覆盖二进制 trie 的根_；
  3. Hᵣ ≡ P(H)ᵣ¹⁶，即只要从十六进制到二进制的转换未完成，十六进制 trie 根就与其父区块的根相同。

执行环境中的以下内容已更改：

  • 在执行_状态读取_时，ϒ 首先在覆盖 trie 中搜索地址。如果找不到密钥，则 ϒ 会像在区块高度 h’ < h₁ 时一样搜索基本 trie；
  • 在执行_状态写入_时，ϒ 将值插入或更新到覆盖树中。基本树保持不变；
  • 如果删除了一个帐户，ϒ 会在帐户地址处插入空哈希 H(∅)，以标记其删除；从此类地址的读取行为与缺少帐户相同，无论基本 trie 中存在什么。

阶段 1 在区块高度 h₂ 结束，该高度与 h₁ 相距足够远，以便为矿工提供足够的时间来执行转换。

阶段 2

此阶段与前一阶段的不同之处在于以下几点：

  • 在区块高度 h₂，在执行 ϒ 之前，Hᵣ ≡ Hᵣ²，即转换函数执行之前的值设置为转换后的_二进制基础 trie_ 的根；
  • Hₒ 仍然存在于区块树中，但是覆盖 trie 内容只能被_读取或删除_；
  • 在区块高度 h ≥ h₂，在执行 ϒ 之前，从二进制覆盖 trie 中删除 N 个帐户并将其插入到二进制基础 trie 中；
  • 在执行_状态写入_时，ϒ 会将值插入或更新到_基本_ trie 中。如果搜索关键字存在于覆盖 trie 中，则将其删除。

帐户删除是根据以下规则执行的：

  • 选择覆盖树中剩余的第一个 N 个帐户（按字典顺序）；对于这些帐户中的每一个：
  • 如果该值是空哈希，则从二进制基本 trie 中删除相同地址的帐户；
  • 否则，使用其覆盖 trie 值在基本 trie 中按对应地址插入/更新帐户。

当覆盖 trie 为空时，阶段 2 结束，阶段 3 开始。

阶段 3

阶段 3 与阶段 2 相同，但以下更改除外：

  • Hₒ 从区块头中删除

理由

到目前为止讨论的方法包括“停止世界”方法，其中链被停止了转换所需的大量时间，以及“写入时复制”方法，其中分支在被访问时被转换。 此处建议的方法的优点是，链在转换过程中继续正常运行，并且树在可预测的时间内完全转换为二进制格式。

向后兼容性

这需要一个分叉，并且会破坏向后兼容性，因为哈希和区块格式必然会有所不同。这将导致未实现覆盖树的客户端以及不接受新二进制根的客户端发生分叉。由于这是一个硬分叉，因此不提出任何缓解措施。

测试用例

  • 为了测试阶段 1，足以检查十六进制 trie 中的每个密钥是否也在二进制 trie 中可用。一个更宽松但更快的测试随机选择十六进制 trie 中 1% 的密钥，并检查它们是否存在于二进制 trie 中；
  • 待定用于阶段 2 和 3

实现

转换过程（阶段 1）的原型版本可在 此 PR 中用于 geth。

安全考虑

我可以预见到三种攻击媒介：

  • 一种有针对性的攻击，会导致覆盖 trie 变得不合理地大。由于 gas 成本可能会在转换过程中增加，因此延长阶段 2 会在较长一段时间内使 Ethereum 的成本更高。这可以通过在阶段 1 中增加 SSTORE 的成本来解决。
  • 相反，如果 h₂ 过早到来，那么大多数矿工可能无法及时为 Hᵣ² 生成正确的值。
  • 如果代表超过 51% 网络的一群矿工报告了无效值，他们可能会窃取资金而无需任何人发表意见。

社区反馈

  • 初步测试表明，快速机器可以在大约 30 分钟内执行转换。
  • 本 EIP 的初始版本希望矿工对二进制基本根的值进行投票。由于此过程的复杂性，并且由于“最长链”规则已经保证了此功能，因此已将其删除。

版权

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Guillaume Ballet (@gballet), "EIP-2584: 带覆盖树的 Trie 格式转换 [DRAFT]," Ethereum Improvement Proposals, no. 2584, April 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2584.