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

After EIP-7797

Who is affected

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.

Original EIP · ← EIPs