64 Byte Transactions
Abstract: A 64 byte Bitcoin transaction has the potential to be confused with an intermediate hashing step in Bitcoin’s Merkle tree, because this is also 64 bytes. We explore how this vulnerability can potentially be used to trick Simple Payment Verification (SPV) clients into thinking they have received a payment, when they have not and other issues caused by this weakness. Although pulling off some of these attacks is very complicated and this vulnerability is not severe, it has a relatively simple fix, banning all witness stripped 64 byte transactions, in a softfork.
Overview
This article is part of a series on the four security vulnerabilities that BIP 54, the Consensus Cleanup softfork would fix. We have already covered two of the security vulnerabilities:
In this piece we are focusing on the issues of the “64 byte transactions.” The trick involved here is that the data in the inner branches in the Merkle trees that make up Bitcoin blocks are 64 bytes. The hash of a Bitcoin transaction, the TXID, is 32 bytes. The inner branches of the second lowest row of the Merkle tree hashes two Bitcoin TXIDs concatenated together. This makes 64 bytes. The security vulnerability is that this 64 bytes of data could be confused with a 64 byte Bitcoin transaction. For instance, an attacker could create a 64 byte Bitcoin transaction, or something that looks like a 64 byte Bitcoin transaction, to confuse or trick a would be victim into accepting an incoming payment. We will explore some of these attacks below.
An illustration of the Merkle tree inside a Bitcoin block
Sergio Lerner’s diagram indicating the position of the fake transaction
Source: https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/
In general, in our view, the risk associated with this vulnerability is moderate to low, due to the complexities involved, in contrast to the Timewarp attack, which we consider more serious. However, it is still an interesting vulnerability to examine and it may be worth fixing.
Hiding A Transaction ID Inside Another Transaction
Perhaps the most severe form of an attack that exploits the vulnerability, that currently known about, involves tricking someone who uses simple payment verification (SPV) to confirm an invalid incoming transaction. We have provided an example illustration below, summarising the attack. The attack works as follows:
The attacker creates a real valid Bitcoin transaction, which is exactly 64 bytes in size. This 64 byte size excludes any segregated witness.
The attacker creates a fake invalid Bitcoin transaction, sending say 1,000 BTC to the victim. For example 1,000.002 BTC from a fake input that doesn’t exist in the UTXO set.
The attacker has a change address for the fake Bitcoin input transaction and using brute force, the attacker grinds though different change addresses until the 32 byte TXID for the fake transaction collides exactly with the last 32 bytes of the real 64 byte transaction.
Once there is a match, the attacker sends the SPV proof to the victim’s wallet, which includes a valid path from the real block header to the fake transaction. The victim is tricked into thinking the bottom row of the Merkle tree is the second to bottom row, with another transaction underneath. The victim now believes they have been paid 1,000 BTC and the Proof of Work from the miners has essentially been stolen by the attacker, to help trick the victim. Of course a full node cannot be fooled like this, for multiple reasons, but an SPV node can be tricked.
Diagram illustrating the two transactions used in the attack
Note: This attack was explained by Peter Todd on 07 June 2018 and Sergio Lerner on 09 June 2018.
The attack described above seems computationally unfeasible, as it seems to require a full 32 byte SHA 256 collision. This is known to be computationally unfeasible and it’s certainly more difficult than just mining a fake block to trick an SPV client, which only takes around 2^84 attempts today, far lower than 2^256 for a full collision. However, the trick here is that the 64 byte transaction can be manipulated, such that you do not need to match 32 bytes by pure brute force.
Components of the last 32 bytes of the 64 byte transaction
Item | Description | Size | Size required to collide |
Input TXID | This is the transaction hash of a previous Bitcoin transaction. It is therefore random and cannot feasibly be manipulated. Brute force is required | 5 bytes in the second half | 5 bytes |
Input index | One could make a setup transaction, with thousands of inputs. Then the input index can be manipulated to collide with the fake transaction, to some extent. However, this may be expensive and challenging to conduct. In reality perhaps a partial brute force collision is required here. | 4 bytes | 0 |
Input size | This is difficult to manipulate, given the other constraints on the transaction. Brute force is therefore required. | 1 byte | 1 byte |
Output count | The transaction requires exactly one output, otherwise it’s hard to see how the transaction could be 64 bytes. This field therefore cannot be manipulated. Brute force is therefore required. | 1 byte | 1 byte |
Output value | One can spend as much Bitcoin as one likes, as long as the attacker has the Bitcoin and is prepared to lose it. If 1 BTC is spent in the input on this transaction, that leaves 100 million for possibilities for the output value (I.e. 100 million satoshis in a Bitcoin). Therefore this field is manipulatable, to some extent. However, one may need to burn more than 21 million Bitcoin to fully manipulate this field. | 8 bytes | 0 |
Output size | This is difficult to manipulate, given the other constraints on the transaction. Brute force is therefore required. | 1 byte | 1 byte |
Output script pubkey | Since the funds in this transaction are non recoverable, this can easily be freely manipulated. | 8 bytes | 0 |
Locktime | The locktime can be manipulated, for instance a block height of up to 500 million can be chosen. Therefore there is plenty of entropy here. | 4 bytes | 0 |
Total | 8 bytes |
Therefore, based on the above table, the attacker only needs to find a collision for 8 bytes, in the best case scenario for the attacker, assuming they can pull off all the other manipulations. 8 bytes or 2^64 does not require much computational resources and an ordinary laptop could pull that off reasonably quickly. In reality, it is likely to be slightly higher than 2^64, as all the above fields are not fully manipulatable.
This attack does not seem that bad. The setup is extremely complicated, perhaps with a setup transaction with thousands of inputs and perhaps burning thousands of dollars, just to give you entropy in deciding the value of the output. Besides, SPV wallets are not that popular anymore anyway. People who expect to receive large value payments tend to know they need a full node to verify incoming payments. However, this attack is still feasible to pull off, especially if the tools are built to conduct it and therefore it’s worth being aware of and to try to mitigate the risks here.
Merkle Root Hash Collision
Another somewhat related Bitcoin vulnerability was discovered and fixed in 2012. The vulnerability here was that two different Bitcoin blocks, a valid one and an invalid one, could each have the same Merkle root hash. There were several ways of achieving this, one of which again included confusing a 64 byte intermediate hashing step with a 64 byte transaction.
The issue here was that Bitcoin nodes store the block hash of invalid blocks, so that they know not to waste resources attempting to validate it again. However, if there are two blocks with the same block hash, one valid and one invalid, a Bitcoin node could be tricked into not following the most work valid chain and instead follow a less work hostile chain. This issue was fixed in 2012, by making nodes do some more checks before caching the hash of an invalid block.
A related issue popped up again in 2019, when Bitcoin developer Suhas Daftuar noted that a similar bug was inadvertently introduced in Bitcoin Core 0.13.0 (released in November 2016), before being fixed again in February 2017. There are also other vulnerabilities associated with this problem and potentially other undiscovered exploits.
Proposed Solution
Fixing this problem does not require a softfork, at least for the SPV trick. The methodology SPV wallets use could just be upgraded, for example to check that each transaction is on the same row in the Merkle tree as the Coinbase transaction. However, the issue is that SPV wallets do not do this and knowledge about this problem is not widespread. Therefore, people are vulnerable. New protocols, such as BitVM may also be vulnerable and the developers here may not have considered this problem.
The proposed softfork solution in BIP 54 is that transactions with a witness stripped size of 64 bytes would be completely banned. This seems like a reasonably simple and easy fix. There does seem to be much reason to make 64 byte transactions anyway. For instance, our example above achieved the 64 byte size by making the funds unrecoverable. In his 2019 email, Suhas Daftuar mentioned that he scanned the blockchain and there were no 64 byte transactions. This should make any softfork smoother and easier to gain consensus for, as banning something that never happens anyway, is considered a less risky and less confrontational path. However, this would leave Bitcoin with a rather quirky new rule, where 63 byte transactions and 65 byte transactions are ok, but 64 byte transactions would be banned.
BitMEX Blog
