EIP-7916: SSZ 渐进列表

用于高效哈希短列表的 SSZ 类型

摘要

此 EIP 引入了一种新的 Merkle 树形结构，用于 Simple Serialize (SSZ)，当仅使用少量叶子节点时，可以减少哈希次数。新的树形结构随着叶子节点数量的增加而逐渐增长，并且不再具有有界容量。它还提供了向前兼容性：给定的块索引始终被分配相同的稳定 generalized index (gindex)，而与叶子节点数量无关。

定义了新的类型以使用渐进式 Merkle 树形结构：ProgressiveList[type] 和 ProgressiveBitlist。这些新类型表示具有稳定 merkleization 的任意长度的列表，从而减少了小型列表的哈希开销，并避免了任意容量限制。

动机

当前的 SSZ List[type, N] 类型需要预定义的容量 N，这导致了以下几个问题：

• 哈希效率低下：列表通常包含远少于其最大容量的元素（例如，Transaction），从而导致不必要的零填充和数十个额外的哈希计算。当嵌套 List[type, N] 时，这种情况会更加恶化，例如，在每个交易最多 X 个访问列表的设计中，每个访问列表最多有 Z 个存储槽。
• 任意限制：容量 N 通常是任意选择的（例如，MAX_BYTES_PER_TRANSACTION，MAX_TRANSACTIONS_PER_PAYLOAD），并设置为人为的大值，以预测未来并不总是正确的设计空间。
• 不稳定的证明：跨分叉修改 N（例如，MAX_ATTESTER_SLASHINGS_ELECTRA，MAX_ATTESTATIONS_ELECTRA）会更改 gindex，从而破坏下游验证器。

渐进式 Merkle 树形结构通过以下方式解决这些问题：

• 使用递归树结构，该结构随着实际叶子节点数量的增加而逐渐增长，且开销最小
• 放弃最大容量的概念，而是依赖于实际的限制，例如，SSZ 的 4 GB 变量偏移上限，网络负载限制，gas 限制，签名数量的限制。
• 为每个元素维护稳定的 gindex，确保证明器在叶子节点数量更改时保持有效。

规范

本文档中的关键词“必须”，“禁止”，“需要”，“应该”，“不应该”，“推荐”，“不推荐”，“可以”和“可选”应解释为 RFC 2119 和 RFC 8174 中所述。

渐进式 Merkle 树

SSZ Merkleization specification) 通过辅助函数进行扩展：

• merkleize_progressive(chunks, num_leaves=1): 给定排序后的 BYTES_PER_CHUNK 字节块：
  • merkleization 取决于输入块的数量，并以递归方式定义：
    • 如果 len(chunks) == 0：根是一个零值，Bytes32()。
    • 否则：使用 hash(a, b) 计算根
      • a: 使用 merkleize_progressive(chunks[num_leaves:], num_leaves * 4) 递归地 merkleize 超出 num_leaves 的块。
      • b: 使用 merkleize(chunks[:num_leaves], num_leaves) 将前 num_leaves 个块 merkleize 为二叉树。

这导致一个以 0 结尾的二叉子树序列，其叶子节点数量不断增加。最深的子树用零填充的块填充（实际上是为了提高内存效率）。

        root
         /\
        /  \
       /\   1: chunks[0 ..< 1]
      /  \
     /\   4: chunks[1 ..< 5]
    /  \
   /\  16: chunks[5 ..< 21]
  /  \
 0   64: chunks[21 ..< 85]

ProgressiveList[type] 和 ProgressiveBitlist

定义了两种新的 SSZ 组合类型)：

• 渐进列表：有序的可变长度同构集合
  • 符号 ProgressiveList[type]，例如 ProgressiveList[uint64]
• 渐进位列表：boolean 值的有序的可变长度集合
  • 符号 ProgressiveBitlist

新类型被认为是“可变大小的”。

为了方便起见，我们别名：

• ProgressiveByteList 到 ProgressiveList[byte]

默认值 定义为：

序列化

ProgressiveBitlist 的序列化、反序列化和 JSON 映射与 Bitlist[N] 相同。

ProgressiveList[type] 的序列化、反序列化和 JSON 映射与 List[type, N] 相同。

Merkle化

Merkleization 定义已扩展。

• 如果 value 是基本对象的渐进列表，则 mix_in_length(merkleize_progressive(pack(value)), len(value))。
• 如果 value 是渐进位列表，则 mix_in_length(merkleize_progressive(pack_bits(value)), len(value))。
• 如果 value 是复合对象的渐进列表，则 mix_in_length(merkleize_progressive([hash_tree_root(element) for element in value]), len(value))。

理由

为什么是递归结构？

• 效率：小型列表使用更少的哈希（例如，16 个元素的子树中的 3 个项目的列表比 1024 个元素的 List[type, N] 浪费更少的哈希）。
• 稳定性：固定的子树大小可确保稳定的 gindex，从而避免了动态深度调整或多次查询的需求。
• 可伸缩性：递归子树允许任意增长而没有硬编码的限制，仅受实际限制的约束（例如，网络负载限制，验证规则）。

为什么没有动态深度？

动态深度 Merkleization 会破坏 gindex：

• 需要两步查询（长度，然后是 gindex），从而增加了延迟和重组风险。
• 使带有语义查找的证明复杂化。

混合后继子树可确保可预测的 gindex 和证明大小。

为什么没有固定容量列表？

List[type, N]：

• 施加任意限制，从而阻碍了可伸缩性。
• 在重新定义时会破坏稳定性。
• 使用填充来浪费哈希（例如，对于 1 项列表，容量为 1024 个元素）。 （仅浪费 log(N) 个哈希）

ProgressiveList[type] 提供了一种可伸缩，高效的替代方案。

为什么初始叶子节点计数和缩放因子不是公开的参数？

• 简单性：固定值（初始叶子节点计数 1，缩放因子 4）提供了一个合理的默认值，该默认值平衡了效率和可用性，与 SSZ 的简单性目标相符。
• 未来可扩展性：如果特定用例需要不同的值，则将来的 EIP 可能会引入参数化。目前，固定值减少了采用障碍，并符合“足够好”的默认值原则。

向后兼容性

新的 SSZ 类型与现有类型共存而没有冲突，并共享其序列化逻辑。

测试用例

请参阅 EIP assets。

参考实现

请参阅 EIP assets，基于 protolambda/remerkleable。

安全考虑

• 资源限制：可变长度偏移量的 uint32 限制实际上引入了 ~4GB 的上限，当在另一个复杂类型中包括 ProgressiveList[type] 或 ProgressiveBitlist 时，但实际限制（例如，10MB libp2p 消息）适用。 实现应强制执行特定于上下文的边界。
• 可变证明大小：递归遍历可能会增加大索引的证明大小，但由于缩放因子，它在列表大小中是对数的。

版权

在 CC0 下放弃版权和相关权利。

Citation

Please cite this document as:

Zsolt Felföldi (@zsfelfoldi), Cayman (@wemeetagain), Etan Kissling (@etan-status), "EIP-7916: SSZ 渐进列表 [DRAFT]," Ethereum Improvement Proposals, no. 7916, March 2025. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7916.