Change merkle tree to fast merkle trees

[scravy]

BIP98 Fast Merkle Trees introduces the concept of fast merkle trees which essentially do not use double-sha256 but fast-sha256 for inner nodes of the tree. In the addendum it also gives an updated algorithm for building the merkle trees in bitcoin that would have prevented CVE-2012-2459.

Applying this in bitcoin is next to impossible as it makes blocks valid which would not be validated by old software (a hardfork). As we are starting new we should implement it.

The BIP itself states it best:

First, Satoshi's Merkle hash-tree has a serious vulnerability[1] related to duplicate tree entries that can cause bugs in protocols that use it. While it is possible to secure protocols and implementations against exploit of this flaw, it requires foresight and it is a bit more tricky to design secure protocols that work around this vulnerability. Designers of new protocols ought avoid using the Satoshi Merkle hash-tree construct where at all possible in order to responsibly decrease the likelihood of downstream bugs in naïve implementations.

Second, Satoshi's Merkle hash-tree performs an unnecessary number of cryptographic hash function compression rounds, resulting in construction and validation times that are approximately three (3) times more computation than is strictly necessary in a naïve implementation, or 2.32x more computation in an implementation specialized for this purpose only[2]. New implementations that do not require backwards compatibility ought to consider hash-tree implementations that do not carry this unnecessary performance hit.

An implementation which we could easily adapt is available: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

[Gnappuraz]

This seems extremely relevant. Good find!

[thothd]

There's quite an extensive thread about the topic here (mostly encoding / security considerations): https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014935.html

[scravy]

To prevent any confusion: The referenced BIP98 defines a soft fork from bitcoin. My proposal is to adopt fast merkle trees as the default (not doable in the bitcoin blockchain as that would constitute a hardfork).

Of course we need to understand the implications and should have a proper proposal/design document (maybe an ADR?). Are there any drawbacks? Are there implications for integration with infrastructure outside of the code we control (Wallets/Exchanges).

[Gnappuraz]

@scravy ADR sounds good to me.

[scravy]

@amiller Are you aware of this ticket? WDYT?