⚠️ Draft Standards Track: Core

EIP-7797: 加速 hash_tree_root

通过定制 SHA-256，使 hash_tree_root 的性能翻倍

Authors	Etan Kissling (@etan-status)
Created	2024-10-23
Discussion Link	https://ethereum-magicians.org/t/eip-7797-double-speed-for-hash-tree-root/21447

概要
动机
规范
理由
向后兼容性
安全注意事项
版权

概要

本 EIP 解释了如何自定义 hash_tree_root 以使其性能翻倍。

动机

哈希运算是共识层实现的主要性能瓶颈。为了支持大量的验证者，优化哈希性能至关重要。

共识层哈希基于 hash_tree_root，这是一种将数据分成块，然后通过递归地组合两个相邻的块并将它们哈希成单个父块，直到只剩下一个根块的机制。

对于哈希，使用摘要大小为 256 位的安全哈希算法 2 (SHA-256)。该算法为可变长度的输入消息生成_恰好_ 256 位的输出。但是，由于 hash_tree_root 将所有输入块填充到恰好 256 位，因此有效输入消息长度始终_恰好_为 512 位。

本 EIP 定义了如何自定义 hash_tree_root 使用的 SHA-256 算法，以利用对精确输入长度的了解来使其性能翻倍，同时保留其安全属性。

规范

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

SHA-256 预处理

在 SHA-256 哈希计算开始之前，会对输入消息进行预处理。在输入消息后附加单个 1 位，后跟可变数量的 0 位，最后是一个大端 uint64，指示输入消息的位长度。选择 0 位的数量，以使消息大小是 512 位的最小倍数。在 hash_tree_root 的上下文中，输入消息大小为 512 位，预处理会产生以下填充消息：

         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
   0x00 |                                               |
   0x10 |                     Input                     |
   0x20 |                    message                    |
   0x30 |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
   0x40 |80|00 00 00 00 00 00 00 00 00 00 00 00 00 00 00|
   0x50 |00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00|
   0x60 |00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00|
   0x70 |00 00 00 00 00 00 00 00|00 00 00 00 00 00 02 00|
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

SHA-256 区块

SHA-256 在 512 位的消息块上运行。因此，在 hash_tree_root 的上下文中，输入消息大小为 512 位，会形成两个消息块，第一个包含整个输入消息，第二个包含由预处理步骤产生的完全静态的数据。

请注意，第二个 512 位消息块不提供任何熵，仅用于区分共享相同前缀且仅在尾随 0 位的数量上不同的输入消息。由于 hash_tree_root 使用固定消息大小，因此无需区分。此外，SHA-256 也被认为对于适合单个消息块的填充消息是安全的。

SHA-256-512

一种新的算法 SHA-256-512 被定义为一种修改后的 SHA-256 算法，它跳过输入消息预处理，并且仅限于精确的 512 位输入。输入消息 SHALL 按原样处理，作为单个 512 位 SHA-256 消息块。

对于每个正在使用的复合 SSZ 类型，实现 SHALL 支持一种新类型，该类型共享相同的功能，但使用 SHA-256-512 而不是常规 SHA-256 进行哈希。

共识类型

从引入此 EIP 的硬分叉开始，基于 SHA-256-512 的复合 SSZ 类型 SHOULD 优先于现有的基于 SHA-256 的类型。

某些涵盖历史对象的用例 MAY 需要转换为历史数据类型，并使用原始 SHA-256 类型重新哈希以恢复其历史根。这包括对历史数据进行签名的 compute_signing_root，以及诸如 BeaconState.latest_block_header 之类的单个字段，这些字段 MAY 引用来自先前分叉的数据。

某些其他对象，例如 DepositData 或 VoluntaryExit，MAY 继续依赖于现有的 SHA-256 逻辑。

理由

将底层哈希算法的吞吐量提高一倍，可以在同一硬件上扩展到更多的验证者，或者允许将释放的 CPU 时间用于其他任务。即使在跨计算（例如 BeaconState 的 validators 列表）缓存很少更改的中间哈希，并使用诸如 prysmaticlabs/hashtree 之类的库采用针对树结构进一步优化的硬件加速 SHA-256 实现时，共识层状态转换函数的状态根验证步骤仍然可以消耗约 25% 的 CPU 时间（Holesky 测试网络，约 170 万验证者），主要由频繁更改的每个验证者结构（例如 EpochParticipationFlags 列表）主导。

如果将来将哈希算法更改为对零知识更友好的算法，则需要进行类似于本 EIP 中描述的工作，以识别需要使用历史哈希来哈希历史对象的位置，并引入新的复合 SSZ 类型。从 SHA-256 切换到 SHA-256-512 会将此类工作提前，并且任何将来的哈希算法更改都只需扩展到这些已知位置。多次切换哈希算法所需的总工作量与切换一次相当。

现有的 SHA-256 硬件加速仍然可行，因为仅删除了消息预处理步骤。硬件加速通常仅实现 SHA-256 消息块函数，该函数不受本 EIP 的影响。

向后兼容性

验证共识层数据的智能合约和客户端应用程序需要更新才能与使用 SHA-256-512 哈希的数据保持兼容。可能需要新的逻辑来正确选择历史结构（例如 BeaconBlockHeader）的哈希算法。

SSZ 序列化、广义索引以及单个对象字段的语义保持不变。

安全注意事项

某些 512 位数据的 SHA-256-512 哈希可能与较短数据的常规 SHA-256 哈希冲突。例如：

任何常见的 440 位前缀：COMMON_PREFIX := 0x000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f30313233343536
SHA-256-512(COMMON_PREFIX ++ 0x80 ++ 0x00000000000001b8) == 463eb28e72f82e0a96c0a4cc53690c571281131f672aa229e0d45ae59b598b59
SHA-256(COMMON_PREFIX) == 463eb28e72f82e0a96c0a4cc53690c571281131f672aa229e0d45ae59b598b59

由于 SSZ 从未哈希过大小与 512 位不同的数据，因此基于 SHA-256 的 SSZ 哈希不会与基于 SHA-256-512 的哈希冲突。

SHA-256-512 SHOULD NOT 用于 SSZ Merkleization 以外的目的。

版权

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

Citation

Please cite this document as:

Etan Kissling (@etan-status), "EIP-7797: 加速 hash_tree_root [DRAFT]," Ethereum Improvement Proposals, no. 7797, October 2024. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7797.