Hi,

I'm writing to report a consensus vulnerability affecting Bitcoin Core versions

0.13.0, 0.13.1, and 0.13.2.  These software versions reached end-of-life on

2018-08-01.

The issue surrounds a fundamental design flaw in Bitcoin's Merkle tree

construction.  Last year, the vulnerability (CVE-2017-12842) around 64-byte

transactions being used to trick light clients into thinking that a transaction

was committed in a block was discussed on this mailing list

(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016091.html).

There is a related attack resulting from the ambiguity around 64-byte

transactions which could be used to cause a vulnerable full-node implementation

to fall out of consensus.

The attack on light clients discussed previously was centered on the idea of

claiming the Merkle tree has one more level in it than it actually has, to

prove that a candidate transaction is in the chain by having its hash match one

side of a 64-byte transaction. The vulnerability I am describing here involves

going the other direction: find a row of interior nodes in the Merkle tree

that successfully deserialize as transactions, in order to make a block appear

to be invalid. (This is of a similar character to the attack described by

Sergio Demian Lerner on

https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/,

in the section titled "An (expensive) attack to partition Bitcoin".)

It has long been recognized that malleating a block's transactions in a way

that produces the same Merkle root could be used to cause a node to fall out of

consensus, because of the logic in Bitcoin Core to cache the invalidity of

blocks (ie to avoid re-validation of known-invalid ones, which would otherwise

make the software vulnerable to DoS). Malleation by "going up" the Merkle tree,

and claiming that some interior row is in fact the set of (64-byte)

transactions in a block, could be used to cause the Bitcoin Core 0.13 branch to

incorrectly mark as invalid a block that in fact has a valid set of

transactions. Moreover, this requires very little work to accomplish -- less

than 22 bits of work in all.

I have attached a writeup that I put together for my own memory and notes which

goes into more detail (along with a summary of other Merkle tree issues,

including the duplicate transactions issue from CVE-2012-2459 and the SPV

issue); please see sections 3.1 and 4.1 for a discussion.  The bug in 0.13 was

introduced as an unintended side-effect of a change I authored

(https://github.com/bitcoin/bitcoin/pull/7225).  Once I learned of this

category of Merkle malleation issues, I realized that the change inadvertently

introduced a vulnerability to this issue that did not previously exist (in any

prior version of the software, as far as I can tell).  A bug fix that

effectively reverted the change (https://github.com/bitcoin/bitcoin/pull/9765)

was made just before the 0.14 version of Bitcoin Core was released, and no

later versions of the software are affected.

Also, I have scanned the blockchain looking for instances where the first two

hashes in any row of the Merkle tree would deserialize validly as a 64-byte

transaction, and I have found zero such instances.  So in particular there are

no blocks on Bitcoin's main chain (as of this writing) that could be used to

attack an 0.13 node.

I thought it best to withhold disclosure of this vulnerability before a

mitigation was in place for the related SPV-issue (which I assumed would become

obvious with this disclosure); once that became public last summer and a

mitigation deployed (by making 64-byte transactions nonstandard), that concern

was eliminated.

Thanks to Johnson Lau and Greg Maxwell for originally alerting me to this issue.