The past couple days have been a roller coaster of events for the bitcoin world. First, MtGox suspended bitcoin withdrawals for a bitcoin “design issue that has been largely ignored”. Attackers took note of this and begin running malicious nodes to increase the frequency of the attack. To handle the network attacks, other big exchanges like Bitstamp temporarily suspended bitcoin withdrawals as well, while some businesses remain unaffected and continue operations as normal.
So, what have we learned?
While writing correct software in any field is important, this is especially true for the realm of finance. Even if the behavior of a program does not deviate from the behavior a programmer intended, such a design may not take into consideration all necessary requirements, leaving it wide open for attacks. This is what happened to MtGox and many existing bitcoin wallet implementations.
There have been two separate, but related, issues with many existing bitcoin wallets brought to the spotlight due to the MtGox press release. Both have been known for years. First of all, wallets must never use transaction hashes (erroneously referred to as a ‘txid’) as the sole means of verifying that a transaction was mined and all inputs creating the transaction must be marked as spent. Second, wallets must be extremely careful as to which inputs they choose when creating transactions, or it’s possible to create transactions which stay forever unconfirmed.
The first attack works as follows: multiple transactions may be functionally equivalent but with slightly different raw representations. Each different representation results in a different transaction hash. An attacker may take a transaction, mutate it ever so slightly to change the hash, and relay it to the network. If this mutated transaction is confirmed in a block and the creating wallet does not recognize the transaction, the transaction will still appear to be unconfirmed and an incorrect balance will be reported.
The second attack involves spending unconfirmed change and, as such, understanding it requires a more in-depth knowledge about how wallets and transactions work. Every transaction is a set of inputs and outputs. New transactions reference inputs by the previous transaction’s hash and output index. Inputs must be either be unspent or spent (it is impossible to partially spend an input). To work around this, wallets traditionally create a new address and send back any leftover coins not needed for the recipient(s) or miner fee. This is called a change address.
If a wallet quickly creates multiple transactions, it is possible that the change from a previous transaction is used as an input for a later transaction. If an attacker mutates the original transaction (let’s call it A) into a different but functionally equivalent transaction A’, and A’ is confirmed into a block, assuming no blockchain reorgs, the later transaction (let’s call it B) will never be added to the blockchain. Doing so would require A to also be mined, however A is now a double spend because A’ already spends the same inputs.
User 2 receives an unconfirmed transaction which can never be included in the blockchain
Most wallet implementations have been aware of the issues of spending unconfirmed transaction outputs and prevent users from doing so. However, these same checks were ignored for change. This was the case even for the reference wallets bitcoind and bitcoin-qt. It was (incorrectly) assumed that previous wallet transactions, if valid, will eventually be confirmed and change is always safe to spend. This assumption is incorrect due to the possibility of attackers mutating transactions, thereby invalidating entire chains of transactions created using unconfirmed outputs.
The core team (the bitcoind developers) are currently merging in stricter checks to lessen the likelihood of an attacker mutating one of your own transactions. Eventually, it’s likely that these checks will become part of the block acceptance rules, eliminating the ability of an attacker mutating your transaction so a wallet does not recognize it. However, the problem can not be solved completely and just as incorrect assumptions got us into this mess, not fully understanding the issue at hand will only cause more issues later if wallet developers do not properly account for all the intricacies of bitcoin.
Even if bitcoind changes the rules to eliminate the possibility of attackers mutating transactions for which they don’t own the private keys, the general issue of transaction malleability remains. An attacker spending their own coins will always be able to create mutated versions of their own transactions, through means such as ignoring inputs or modifying scripts to use to one of the many valid sighash flags. These cases can not be prevented by stricter block rules. Even though only one transaction will ever be included in the blockchain at any time, wallets must be aware of this issue and, if they choose to spend unconfirmed inputs, to recognize this mutation and create new transactions which properly reference the confirmed transaction.
These attacks can also affect services accepting bitcoin as payment. Consider the following scenario: an attacker creates two functionally equivalent transactions A and A’, and sends payment to a service with transaction B (spending change from A). The equivalent transaction B’ is intentionally never created. If A’ is mined (and assuming no reorgs), the outputs of transaction B will never be spendable as it creates a double spend. If the service has immediately credited the user based on transaction B, they lose money.
There simply is no way around the fact that transaction hashes may not safely be used as unique IDs. In fact, there are already instances of transactions with duplicate hashes recorded in the blockchain. Wallets attempting to take this shortcut, even after the transaction rules are strengthened, risk the possibility of creating transactions that remain forever unconfirmed.