EIP-7864: 使用统一二叉树的以太坊状态

将以太坊状态树切换到统一二叉树

摘要

引入一个新的二叉状态树，旨在取代十六进制 Patricia 树。账户和存储 trie 合并到一个具有 32 字节键的单个树中，该树还包含合约代码。账户数据被分解为独立的叶子节点，这些叶子节点以 256 个为一组进行分组，以便提供一些局部性。

注意：当前草案中使用的哈希函数尚未最终确定。当前的实现使用 BLAKE3 来减少 EL 客户端试验此 EIP 的摩擦，但最终决定仍待定。其他潜在的候选方案包括 Keccak 和 Poseidon2。

对于 Poseidon2，以太坊基金会正在进行一项密码学倡议，评估其安全性。如果选择 Poseidon2，则需要额外的规范来选择字段（BN254 标量字段、31 位字段元素等）并将 32 字节的值编码为字段元素。

随着此 EIP 逐渐被接受，可以切换哈希函数，对实现的影响最小。不要假设 BLAKE3 是最终决定。

动机

以太坊的长期目标是允许使用有效性证明来证明区块，以便链验证尽可能简单和快速。实现该目标最具挑战性的部分之一是证明树的状态，这是 EVM 执行所必需的。

当前 Merkle-Patricia Trie (MPT) 设计对有效性证明不友好，原因有很多，例如使用 RLP 进行节点编码、Keccak 作为哈希函数、作为“树的树”以及不将账户代码作为状态的一部分。

除了需要对区块有效性证明友好的状态树设计之外，当要证明的状态量很小时，拥有快速且小的常规 Merkle 证明也很重要。这不仅对应用层有用，而且对支持未来无状态世界的协议需求（例如：包含列表）也很有用。

关于 MPT 中的这些常规 Merkle 证明，由于它是一个十六进制树，因此它们的平均大小和最坏情况场景都非常大。给定一个 2^32 大小的树，证明单个分支的预期大小为 15 * 32 * log_16(2^32) = 3840。从最坏情况的区块角度来看，如果使用 30M gas 仅访问不同账户代码的单个字节，由于此代码未分块，我们将需要 30M/2400*(5*480+24k)=330MB。

二叉树在链下和链上证明之间取得了良好的平衡。由于树的阶数为 2，这减少了常规 Merkle 证明的大小（即，阶数为 2 时 # sibilings * log_arity(N) 比阶数为 16 时更好）。此外，我们建议从 Keccak 切换到对证明更友好的哈希函数，这将更适合现代证明系统。

规范

本文档中的关键词“MUST”、“MUST NOT”、“REQUIRED”、“SHALL”、“SHALL NOT”、“SHOULD”、“SHOULD NOT”、“RECOMMENDED”、“NOT RECOMMENDED”、“MAY”和“OPTIONAL”应按照 RFC 2119 和 RFC 8174 中的描述进行解释。

与十六进制结构的显着变化

• 账户和存储 trie 合并到一个 trie 中。
• 不再使用 RLP。
• 账户的代码被分块并包含在树中。
• 账户数据（例如，余额、nonce、第一个存储槽、第一个代码块）共同位于树中，以减少分支打开。

树结构

拟议的二叉树存储键值条目，其中键和值均为 32 字节。键的前 31 个字节定义条目词干，最后一个字节是该词干中的子索引。如果两个键具有相同的词干，则它们位于同一个“大分支”中——这会将 256 个键（即：具有相同前 31 个字节的键）的组共同定位。

（有关紫色/橙色部分的更多详细信息，请参阅“树嵌入”部分）

我们可以区分四种节点类型：

• InternalNode 具有 left_hash 和 right_hash 字段（黑色）。
• StemNode 具有 stem、left_hash 和 right_hash 字段（蓝色）。
• LeafNode 具有一个 value 字段，该字段是一个 32 字节的 blob 或 empty。（橙色）。
• EmptyNode 表示一个空节点/子树。

StemNode 的路径由键的前 248 位（31 字节）（从 MSB 到 LSB）定义。从该节点开始，存在一个由键的最后一个字节（8 位）索引的 256 个值的子树。新创建的 StemNode 子树（即：256 个值）的所有叶子都具有 value: empty。

路径长度不是 248 位，而是包含如果存在具有相同前缀的其他词干所需的最小 InternalNodes 数量。就像在插入新 StemNode 时遍历 248 位路径一样，您可以结束于 EmptyNode 或 StemNode。在前一种情况下，您用新的 StemNode 替换它。在后一种情况下，您会根据两个词干作为前缀的公共位的数量创建尽可能多的 InternalNodes。看待此问题的另一种方法是路径中没有_扩展节点_，但我们使用最少数量的 InternalNodes 来放置具有公共前缀的 StemNode。

以下是一个描述树结构的实现：

class StemNode:
    def __init__(self, stem: bytes):
        assert len(stem) == 31, "stem must be 31 bytes"
        self.stem = stem
        self.values: list[Optional[bytes]] = [None] * 256

    def set_value(self, index: int, value: bytes):
        self.values[index] = value

class InternalNode:
    def __init__(self):
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, key: bytes, value: bytes):
        assert len(key) == 32, "key must be 32 bytes"
        assert len(value) == 32, "value must be 32 bytes"
        stem = key[:31]
        subindex = key[31]

        if self.root is None:
            self.root = StemNode(stem)
            self.root.set_value(subindex, value)
            return

        self.root = self._insert(self.root, stem, subindex, value, 0)

    def _insert(self, node, stem, subindex, value, depth):
        assert depth < 248, "depth must be less than 248"

        if node is None:
            node = StemNode(stem)
            node.set_value(subindex, value)
            return node

        stem_bits = self._bytes_to_bits(stem)
        if isinstance(node, StemNode):
            # If the stem already exists, update the value.
            # 如果词干已存在，则更新值。
            if node.stem == stem:
                node.set_value(subindex, value)
                return node
            existing_stem_bits = self._bytes_to_bits(node.stem)
            return self._split_leaf(
                node, stem_bits, existing_stem_bits, subindex, value, depth
            )

        # We're in an internal node, go left or right based on the bit.
        # 我们在一个内部节点中，根据该位向左或向右移动。
        bit = stem_bits[depth]
        if bit == 0:
            node.left = self._insert(node.left, stem, subindex, value, depth + 1)
        else:
            node.right = self._insert(node.right, stem, subindex, value, depth + 1)
        return node

    def _split_leaf(self, leaf, stem_bits, existing_stem_bits, subindex, value, depth):
        # If the stem bits are the same up to this depth, we need to create another
        # 如果词干位在此深度之前相同，我们需要创建另一个
        # internal node and recurse.
        # 内部节点并递归。
        if stem_bits[depth] == existing_stem_bits[depth]:
            new_internal = InternalNode()
            bit = stem_bits[depth]
            if bit == 0:
                new_internal.left = self._split_leaf(
                    leaf, stem_bits, existing_stem_bits, subindex, value, depth + 1
                )
            else:
                new_internal.right = self._split_leaf(
                    leaf, stem_bits, existing_stem_bits, subindex, value, depth + 1
                )
            return new_internal
        else:
            new_internal = InternalNode()
            bit = stem_bits[depth]
            stem = self._bits_to_bytes(stem_bits)
            if bit == 0:
                new_internal.left = StemNode(stem)
                new_internal.left.set_value(subindex, value)
                new_internal.right = leaf
            else:
                new_internal.right = StemNode(stem)
                new_internal.right.set_value(subindex, value)
                new_internal.left = leaf
            return new_internal

节点梅克尔化

将 hash(value) 定义为：

• hash([0x00] * 64) = [0x00] * 32
• hash(value) = H(value)，其中 H 是所选的加密哈希函数。

value 参数长度只能为 32 和 64。

按如下方式梅克尔化每种节点类型：

• internal_node_hash = hash(left_hash || right_hash)
• stem_node_hash = hash(stem || 0x00 || hash(left_hash || right_hash))
• leaf_node_hash = hash(value)
• empty_node_hash = [0x00] * 32

以下是使用 BLAKE3 作为参考实现来实现这些规则的示例：

def _hash(self, data):
    if data in (None, b"\x00" * 64):
        return b"\x00" * 32

    assert len(data) == 64 or len(data) == 32, "data must be 32 or 64 bytes"
    return blake3(data).digest()  # This will be replaced with the final hash function
                                  # 这将被最终哈希函数替换

def merkelize(self):
    def _merkelize(node):
        if node is None:
            return b"\x00" * 32
        if isinstance(node, InternalNode):
            left_hash = _merkelize(node.left)
            right_hash = _merkelize(node.right)
            return self._hash(left_hash + right_hash)

        level = [self._hash(x) for x in node.values]
        while len(level) > 1:
            new_level = []
            for i in range(0, len(level), 2):
                new_level.append(self._hash(level[i] + level[i + 1]))
            level = new_level

        return self._hash(node.stem + b"\0" + level[0])

    return _merkelize(self.root)

树嵌入

我们将把所有信息嵌入提议的单棵树中的唯一 key: value 空间中，而不是像 MPT 那样的两层结构。本节指定哪些树键存储状态的信息（帐户标头数据、代码、存储）。数据以这样一种方式共同定位，即通常一起访问的数据位于同一 StemNode 中，这减少了分支打开。

以下是我们将继续在本节的其余部分中描述的大致情况：

帐户词干（绿色 account 节点）包含帐户基本数据、前 64 个存储槽和前 128 个代码块。这种数据的共位允许在通常一起访问的单个词干分支数据中拥有数据。其余的存储槽和代码块分布在树的其余部分中 256 个值的组中——这样做也是为了方便，因为彼此靠近的槽/代码块将共享相同的词干分支。

要求 STEM_SUBTREE_WIDTH > CODE_OFFSET > HEADER_STORAGE_OFFSET 且 HEADER_STORAGE_OFFSET 大于叶键。此外，MAIN_STORAGE_OFFSET 必须是 STEM_SUBTREE_WIDTH 的幂。

请注意，地址始终作为 Address32 传递。要将现有地址转换为 Address32，请在前面加上 12 个零字节：

def old_style_address_to_address32(address: Address) -> Address32:
    return b'\\x00' * 12 + address

标头值

这些是在树中存储帐户标头字段的位置。

def tree_hash(inp: bytes) -> bytes32:
    return bytes32(blake3.blake3(inp).digest())

def get_tree_key(address: Address32, tree_index: int, sub_index: int):
    # Assumes STEM_SUBTREE_WIDTH = 256
    # 假设 STEM_SUBTREE_WIDTH = 256
    return tree_hash(address + tree_index.to_bytes(32, "little"))[:31] + bytes(
        [sub_index]
    )

def get_tree_key_for_basic_data(address: Address32):
    return get_tree_key(address, 0, BASIC_DATA_LEAF_KEY)

def get_tree_key_for_code_hash(address: Address32):
    return get_tree_key(address, 0, CODE_HASH_LEAF_KEY)

帐户的 version、balance、nonce 和 code_size 字段以大端编码方式打包在 BASIC_DATA_LEAF_KEY 处找到的值中：

字节 1..4 保留供将来使用。

当前的布局和编码允许将 code_size 扩展到 4 个字节，而无需更改帐户版本。将这些字段一起打包在基本数据叶中的目标是降低 gas 成本，因为与如果未打包这些字段通常需要的 3 或 4 个分支打开相比，我们只需要一个分支打开。这也简化了见证人生成。

设置任何帐户标头字段时，version 字段也会设置为零。codehash 和 code_size 字段在合约或 EOA 创建时设置。

代码

def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
    return get_tree_key(
        address,
        (CODE_OFFSET + chunk_id) // STEM_SUBTREE_WIDTH,
        (CODE_OFFSET + chunk_id)  % STEM_SUBTREE_WIDTH
    )

块 i 存储一个 32 字节的值，其中字节 1…31 是代码的字节 i*31...(i+1)*31 - 1（即，它的第 i 个 31 字节切片），字节 0 是作为 PUSHDATA 的一部分的前导字节的数量（例如，如果代码的某部分是 ...PUSH4 99 98 | 97 96 PUSH1 128 MSTORE...，其中 | 是新块开始的位置，那么后一个块的编码将以 2 97 96 PUSH1 128 MSTORE 开头，以反映前 2 个字节是 PUSHDATA）。

为了精确起见，以下是代码分块的实现：

PUSH_OFFSET = 95
PUSH1 = PUSH_OFFSET + 1
PUSH32 = PUSH_OFFSET + 32

def chunkify_code(code: bytes) -> Sequence[bytes32]:
    # Pad to multiple of 31 bytes
    # 填充到 31 字节的倍数
    if len(code) % 31 != 0:
        code += b'\\x00' * (31 - (len(code) % 31))
    # Figure out how much pushdata there is after+including each byte
    # 找出在每个字节之后+包括多少推送数据
    bytes_to_exec_data = [0] * (len(code) + 32)
    pos = 0
    while pos < len(code):
        if PUSH1 <= code[pos] <= PUSH32:
            pushdata_bytes = code[pos] - PUSH_OFFSET
        else:
            pushdata_bytes = 0
        pos += 1
        for x in range(pushdata_bytes):
            bytes_to_exec_data[pos + x] = pushdata_bytes - x
        pos += pushdata_bytes
    # Output chunks
    # 输出块
    return [
        bytes([min(bytes_to_exec_data[pos], 31)]) + code[pos: pos+31]
        for pos in range(0, len(code), 31)
    ]

存储

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // STEM_SUBTREE_WIDTH,
        pos % STEM_SUBTREE_WIDTH
    )

请注意，相同大小的 STEM_SUBTREE_WIDTH 范围内的存储槽（即形式为 x*STEM_SUBTREE_WIDTH ... (x+1)*STEM_SUBTREE_WIDTH-1) 的范围）全部（除了 HEADER_STORAGE_OFFSET 特殊情况）是单个词干的一部分。

分叉

在 EIP-7612 中描述。

访问事件

在 EIP-4762 中描述。

理由

此 EIP 定义了一个新的二叉树，该树最初为空。只有新的状态更改存储在树中。MPT 继续存在，但被冻结。这为未来将 MPT 数据迁移到此二叉树的硬分叉奠定了基础（EIP-7748）。

单棵树设计

该提案使用具有 32 字节键和值的单层树结构，原因有以下几个：

• 简单：使用键/值存储的抽象概念可以更轻松地编写处理树的代码（例如，数据库读取/写入、缓存、同步、证明创建和验证）并在将来将其升级到其他树。此外，见证人 gas 规则可以变得更简单、更清晰。
• 统一性：状态在整个树中均匀分布；即使单个合约有数百万个存储槽，合约的存储槽也不会集中在一个地方。这对于状态同步算法很有用。此外，它有助于降低不平衡树填充攻击的有效性。
• 可扩展性：帐户标头和代码与存储位于同一结构中，可以更轻松地扩展这两个功能，甚至在需要时添加新结构。

SNARK 友好性和后量子安全性

拟议的设计应考虑链下实现（即 EL 客户端）和链上实现（用于在 ZK 电路中生成证明）的通常复杂性、性能和效率。

树设计结构力求简单，没有复杂的 branching 规则。例如，与 MPT 相比，我们避免在分支中间注入扩展节点。此外，RLP 编码已被删除，因为它增加了不必要的复杂性。虽然复杂性可以在链下实现中更轻松地管理，但帮助电路实现尽可能简单以避免证明开销是有价值的。

设计中最重要的因素是用于梅克尔化的密码哈希函数。此哈希函数应具有高效的链外和链内实现。哈希函数选择仍待定，目前正在考虑以下几个候选方案：

1. BLAKE3：
   • 良好的链外性能（即，用于原始 EL 客户端执行）
   • 用于证明的合理的链内性能
   • 完善的安全属性
   • 目前在参考实现中使用，以方便进行实验
2. Keccak：
   • 已在以太坊中使用，降低了实现复杂性
   • 经过充分研究的安全属性
   • 与替代方案相比，电路证明效率较低
3. Poseidon2：
   • 用于 ZK 证明的出色的链内性能
   • 可能更好的证明吞吐量
   • 安全性分析仍在通过 EF 密码学计划进行
   • 需要额外的规范来选择字段和编码

最终的哈希函数选择将平衡这些考虑因素，特别关注安全性、证明效率和实现复杂性。

由于量子计算领域的最新进展，专家估计它们可能会在 2030 年代变为现实。美国国家标准与技术研究院建议在 2030 年之前停止使用 ECC。其他替代方案（例如 Verkle Trees）向协议引入了新的密码学堆栈，该堆栈依赖于不具有后量子安全性的椭圆曲线。这使得当前的树提案具有吸引力，因为它仅依赖于哈希函数，而在这种新范例中，哈希函数仍然是安全的。

此外，证明系统取得了令人印象深刻的进展，这表明我们可能很快就能达到足够快的速度来创建预状态和后状态证明所需的性能。最后一点至关重要，因为 Verkle Trees 的主要优势是具有小而快速生成的证明。

最后，与 Verkle Trees 相比，当前的 state tree 提案可能将是协议中使用的最终状态树，而最终 Verkle Trees 需要由后量子安全替代方案替代。

Arity-2

选择二叉树的主要原因是它们可以减小见证人大小。一般来说，在具有 N 个元素且每个元素具有 k 个子元素的树中，分支的平均大小约为 32 * (k-1) * log(N) / log(k)，再加上几个百分点的开销。32 是哈希的长度；k-1 是指 Merkle 证明需要在每个级别提供所有 k-1 个姊妹节点，而 log(N) / log(k) 是树中级别数的近似值（例如，每个节点具有 5 个子节点的树，总共有 625 个节点，将具有深度 4，因为 625 = 5**4，因此 log(625) / log(5) = 4）。

对于任何 N，表达式在 k = 2 处最小化。以下是一个表格，其中列出了假设 N = 2**24 的不同 k 值的分支长度：

由于分布不均，实际分支长度可能会略大于此值，但 k=2 的模式仍然是迄今为止最好的。

树深度

树设计尝试尽可能简单，同时考虑链外和电路实现，同时满足我们对证明哈希的吞吐量约束。

拟议的设计避免了在 Sparse Merkle Tree (SMT) 中发生的完整 248 位深度。这种方法有助于减少证明系统中哈希负载，目前这是商品硬件上的吞吐量瓶颈。哈希函数的选择将影响这种考虑——像 Poseidon2 这样的算术友好型哈希函数将具有与像 BLAKE3 或 Keccak 这样的密码哈希函数不同的性能特征。可以使用一些优化技术，但它们会增加规范的复杂性。

此外，我们可以进一步尝试在路径中间引入扩展节点，就像在 MPT 中所做的那样，但这也会增加复杂性，考虑到树应该相当平衡，这可能不值得。

状态过期

状态过期策略（例如 EIP-7736）仍然可以应用，这需要更改设计。一种潜在的解决方案是按照上述 EIP 中的描述，将 epoch 字段添加到 StemNode。另一种替代方案是将 247 位用于词干，并具有两个子树 StemValuesNode（对应于当前的 256 个值）和 StemMetaNode（也是一个 256 子树，可用于存储任意词干元数据）。

向后兼容性

主要的中断性更改是：

• (1) 代码块访问的 gas 成本可能会对应用程序的经济可行性产生影响
• (2) 树结构更改使得 EVM 内的历史状态证明不再有效

(1) 可以通过在实现此 EIP 时增加 gas 限制来缓解，从而允许应用程序具有相同的经济可行性。

测试用例

待办事项：

• 添加树操作的全面测试向量
• 最终确定哈希函数的选择，并为所选函数提供测试向量
• 添加树操作中 edge 情况下的测试用例

参考实现

Python 参考实现 (github.com/jsign/binary-tree-spec)。

安全注意事项

需要讨论。

版权

通过 CC0 放弃版权和相关权利。

Citation

Please cite this document as:

Vitalik Buterin (@vbuterin), Guillaume Ballet (@gballet), Dankrad Feist (@dankrad), Ignacio Hagopian (@jsign), Kevaundray Wedderburn (@kevaundray), Tanishq Jasoria (@tanishqjasoria), Gajinder Singh (@g11tech), Danno Ferrin (@shemnon), Piper Merriam (@pipermerriam), Gottfried Herold (@GottfriedHerold), "EIP-7864: 使用统一二叉树的以太坊状态 [DRAFT]," Ethereum Improvement Proposals, no. 7864, January 2025. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7864.