Is this Merkle hash root problem existent in Bitcoin?

Question

In the Wikipedia article about Merkle trees, I was just reading this, unable to understand where the problem lies:

Second preimage attack

The Merkle hash root does not indicate the tree depth, enabling a second-preimage attack in which an attacker creates a document other than the original that has the same Merkle hash root. For the example above, an attacker can create a new document containing two data blocks, where the first is hash 0-0 + hash 0-1, and the second is hash 1-0 + hash 1-1.

One simple fix is defined in Certificate Transparency: when computing leaf node hashes, a 0x00 byte is prepended to the hash data, while 0x01 is prepended when computing internal node hashes. Limiting the hash tree size is a prerequisite of some formal security proofs, and helps in making some proofs tighter. Some implementations limit the tree depth using hash tree depth prefixes before hashes, so any extracted hash chain is defined to be valid only if the prefix decreases at each step and is still positive when the leaf is reached.

My first questions are: Is this really a problem in Bitcoin? If yes, how is it being solved in Bitcoin core?

My second questions are: Could this problem be solved by storing the tree depth of each block directly in the block chain? Or speaking of Bitcoin, would that negatively affect the block validation procedure itself somehow?

Answer 1

Yes, these kinds of attack do effect Bitcoin and are known and described. Bitcoin does not have any consensus level mitigations for them because doing so requires consensus changes which are difficult to do. It is known that Bitcoin's merkle tree design has multiple vulnerabilities.

The particular attack described on wikipedia is that an internal level can be presented as a valid document. In Bitcoin, this is theoretically possible, although it would take significant work to produce a block where the transactions produce hashes which can then be deserialized as valid transactions. If such a block were produced, it could result in a network partition due to behavior around the caching of invalid blocks. Obviously the solution to this is to be sure that cached invalid blocks are treating carefully to avoid rejecting blocks for things that are third party malleable.

In fact, this particular issue lead to a vulnerability in Bitcoin Core 0.13 that has since been fixed. A description of the vulnerability is available on the bitcoin-dev mailing list.

There is another related attack going the other direction - including a transaction in a block which could be interpreted as an internal node in a merkle tree. This attack could be used to target SPV wallets and trick those wallets into thinking a transaction was included in a block when it was not. This attack in described by Sergio Demian Lerner in this blog post.

The only true solution to this second attack requires some kind of consensus change to introduce the tree depth. But consensus changes are hard, and there are other things that can be done. SPV wallets can protect themselves by checking that no internal nodes can be serialized as valid transactions. Such an internal node is incredibly unlikely to appear randomly so this shouldn't have any real effect on the user. In Bitcoin Core, to help with protecting against this attack, 64 byte transactions won't be relayed. As 64 byte transactions are smaller than any standard transaction could be, this is safe.