Accelerate Merkle tree hashing

[mratsim]

Merkle tree hashing is a significant bottleneck in blockchains.

In most (all?) blockchains and in particular Ethereum, efficient storage/retrieval/update as well as integrity guarantees of data is implemented through a Merkle-Tree or other hash trees (Merkle Patricia Trie for Ethereum).

Those require computing hashes from the leaves to the root of the tree. In particular the latest way to accelerate syncing a whole blockchain, 800GB+ of data for Ethereum execution layer (accounts/transactions) involve only downloading the leaves and reconstructing the Merkle tree locally. (https://github.com/ethereum/devp2p/blob/40ab248/caps/snap.md)

Besides, the consensus layer is also extremely hashing intensive with everything being serialized in a "merkleizable" wire format, SimpleSerialize (SSZ): https://github.com/ethereum/consensus-specs/blob/9a2fcc0/ssz/simple-serialize.md#merkleization.

Note that the Execution Layer uses hexary Merkle tree (16 leaves per node) while the Consensus Layer is binary (2 leaves per node).

Writeups:

• https://hackmd.io/@potuz/rJX9iD30u (inaccessible)
• https://hackmd.io/hOZnkh50RKehsOyf0b3CdQ (inaccessible)
• https://hackmd.io/80mJ75A5QeeRcrNmqcuU-g
• https://github.com/prysmaticlabs/hashtree
• https://github.com/prysmaticlabs/gohashtree
• https://github.com/potuz/mammon/tree/bf2bd93/ssz
• https://github.com/prysmaticlabs/prysm/tree/94768a3/crypto/hash/custom_hasher
• Change SHA256 Library prysmaticlabs/prysm#9389
• https://github.com/ChainSafe/as-sha256/pull/59/files
• digest64 ChainSafe/as-sha256#51
• Investigate faster hash implementations status-im/nimbus-eth2#2740
• Padding hardcoding: https://github.com/potuz/mammon/blob/bf2bd93/ssz/sha256_avx2.asm#L730-L738
• Make vectorized SHA256 default prysmaticlabs/prysm#10286
  • Integration of Vectorized Sha256 In Prysm prysmaticlabs/prysm#10166
• optimize hash_tree_root using hashtree status-im/nim-ssz-serialization#35

Note: Bitcoin has similar needs

• Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 bitcoin/bitcoin#13191
• https://github.com/sipa/bitcoin/tree/201709_dsha256_64 / sipa/bitcoin@4437d6e
• https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki
• https://github.com/maaku/bitcoin/tree/fast-merkle-tree / maaku/bitcoin@63fa744

Benchmarks:

Mammon being optimized for tree hashing

	Nimbus	Prysm	Lighthouse (single thread)	Mammon
NUC i5-8259U @ 2.30GHz	1112ms (AVX2)	1125ms (AVX2)	860ms (AVX2)	563 (AVX2) 596(AVX) 1042 (SSE)
Ryzen 5 @3.60 GHz	251ms (SHA)	292ms (SHA)	760ms (SHA)	161ms (SHA) 760ms (AVX2) 813ms (AVX) 1361 ms (SSE)
XPS 13 i5-7200U @ 2.50GHz	953 ms (AVX2)	1085ms (AVX2)	998ms (AVX2)	654 ms (AVX2) 681ms(AVX) 964ms (SSE)

Beyond blockchains, while there are many usecases for Merkle trees

Hash trees are also used in the IPFS, Btrfs and ZFS file systems[4] (to counter data degradation[5]); Dat protocol; Apache Wave protocol;[6] Git and Mercurial distributed revision control systems; the Tahoe-LAFS backup system; Zeronet; the Bitcoin and Ethereum peer-to-peer networks;[7] the Certificate Transparency framework; the Nix package manager and descendants like GNU Guix;[8] and a number of NoSQL systems such as Apache Cassandra, Riak, and Dynamo