EIP-7797 Doubling hash tree root speed (Double speed for hash_tree_root)
No call decision · Consensus & staking · EIP status Stagnant · created 2024-10-23
A proposal to introduce SHA-256-512, which skips an unnecessary preprocessing step of SHA-256, doubling the speed of hash_tree_root hash computation on the consensus layer.
Why it is needed
Hashing is one of the biggest performance bottlenecks in consensus layer implementations. As the number of validators grows, the burden of repeatedly hashing each validator's state data via hash_tree_root also grows. hash_tree_root splits all data into 256-bit chunks and hashes them in pairs; the SHA-256 used here goes through a preprocessing step that appends padding to the end of the input to handle variable-length input in general. But because the input to hash_tree_root is always exactly 512 bits, this preprocessing ends up producing a second 512-bit block every time that carries no actual information. On the Holesky testnet, with roughly 1.7 million validators, state root verification alone consumes about 25% of CPU time, so removing this unnecessary block creates room to support more validators on the same hardware.
What changes
Today
- hash_tree_root pads every input to 512 bits and then applies SHA-256 preprocessing, hashing two 512-bit blocks: the input block and a padding block.
- On the Holesky testnet (roughly 1.7 million validators), state root verification accounts for about 25% of CPU time.
- Even with hardware-accelerated SHA-256 and caching, hashing frequently changing structures (such as EpochParticipationFlags) imposes a heavy burden.
After EIP-7797
- SHA-256-512 is defined to skip preprocessing, processing a single 512-bit input as one block only.
- A new SHA-256-512-based type is added for every composite SSZ type, cutting the amount of hashing in half.
- After the fork, it is recommended (SHOULD) that the new SHA-256-512-based types be used in preference to the existing SHA-256 types.
Who is affected
- Validators: The same hardware can support more validators, or the saved CPU time can be used for other work.
- Client teams: A SHA-256-512-based version must be newly implemented for every composite SSZ type, and the existing SHA-256 logic must be kept alongside it for historical data.
- Developers of apps and contracts that verify consensus layer data: Logic must be updated to verify data hashed with SHA-256-512.
In depth
The waste created by SHA-256 preprocessing
To handle variable-length input, SHA-256 preprocesses the message by appending a 1 bit, followed by a number of 0 bits, and finally a big-endian 64-bit length field. Because the input to hash_tree_root is always exactly 512 bits, this preprocessing produces a second 512-bit block, which is computed every time even though there is no need to distinguish input length since it is fixed. In other words, unlike the first block, which carries real information, the second block is a wasted computation that only hashes a fixed padding value.
Definition of SHA-256-512
SHA-256-512 is a variant of SHA-256 that skips input message preprocessing and only accepts an input of exactly 512 bits. It processes the input as a single 512-bit SHA-256 message block with no preprocessing. For every composite SSZ type, implementations must (SHALL) support a new type that hashes with SHA-256-512 while providing the same functionality as the existing type.
Coexistence of the existing type and the new type
Starting with the hard fork that introduces this EIP, SHA-256-512-based composite SSZ types SHOULD be preferred over the existing SHA-256-based types. However, for fields that point to data from previous forks, such as BeaconState.latest_block_header, or for functions like compute_signing_root that sign historical data, it MAY be necessary to convert back to the original SHA-256 type and rehash in order to restore the original historical root. Some objects, such as DepositData or VoluntaryExit, MAY continue to use the existing SHA-256 logic.
Hardware acceleration remains valid
Existing SHA-256 hardware acceleration typically implements only the message block function itself, and this block function is not changed at all by this EIP. Since the only part this change omits is the preprocessing step, existing hardware acceleration infrastructure can still be used as is.
Groundwork for future hash algorithm transitions
If the hash algorithm is changed in the future to a form more friendly to zero-knowledge proofs (ZK), the work of identifying where historical objects need to be recomputed using the old hashing method and introducing new composite SSZ types will be needed again. Since the transition from SHA-256 to SHA-256-512 performs this work in advance, only the already-identified points need to be extended when switching to a different hash algorithm later. The total amount of work across multiple transitions is similar to doing a single transition.
Security: collision possibility confined outside SSZ's scope
There are cases where hashing 512-bit data with SHA-256-512 yields the same value as hashing shorter data with a common prefix using ordinary SHA-256 (the source includes a concrete example). However, since SSZ has never hashed data of a length other than 512 bits, there is no case within SSZ where a SHA-256-based hash and a SHA-256-512-based hash collide with each other. Therefore, SHA-256-512 SHOULD NOT be used for purposes other than SSZ Merkleization.