What the 'Bitcoin Bug' Means: A Guide to Transaction Malleability

This week, a term emerged that many bitcoiners won't have heard before: transaction malleability. Mt Gox cited it as a key reason for suspending withdrawals, and it was also mentioned as the basis for an exploit used in a massive attack against the bitcoin network this week. So, what is it, how does it work, and should we be worried? Here's what we know.

It's an attack that lets someone change the unique ID of a bitcoin transaction before it is confirmed on the bitcoin network. The change makes it possible for someone to pretend that a transaction didn't happen, if all the right conditions are in place.

No. Double spending involves spending coins once, then creating a different transaction with those same coins before the first transaction is confirmed. The trick is then to get the fraudulent transaction confirmed on the bitcoin network first, so that the first transaction didn't happen. That effectively means that you get to spend them twice.

To understand that, you have to know how a bitcoin transaction works.

When you send bitcoins to someone, you don't withdraw them from an account and send them whizzing along the wires. Bitcoins are never sent this way. Instead, a transaction is created on the bitcoin block chain.

The block chain acts like a giant general ledger for the whole of the bitcoin network. It keeps records of which bitcoin addresses sent funds to other bitcoin addresses, and when. This gives it a complete record of how many bitcoins can be attributed to which addresses on the network at any one time.

When a bitcoin transaction is made, it includes information such as the addresses that the bitcoins came from (the inputs), where they're going (the outputs), the amounts transferred, and which addresses sent those funds to the sender's address.

[post-quote]

Each transaction must be uniquely identified, so that it can be referenced in the block chain. That transaction ID (TX ID) is produced by taking the information in the transaction, and running it through a hash function.

Hashing is a mathematical procedure that takes different pieces of data and combines them to produce a shorter piece of information, known as a hash. One of the things that's included in a transaction hash is the user's digital signature, which proves that the transaction came from them. It's a way for them to digitally 'sign' the transaction.

One of the key qualities of a hashing function is that it is impossible to tell what the original information was simply by looking at the hash. It is also impossible to predict what the hash will be, based on the pieces of information that you start with. If any small detail changes in any of those pieces of data, it will change the hash in a completely unpredictable way.

This makes transaction IDs practically impossible to spoof. Each transaction should only have one possible hash. You can prove that a transaction is valid by simply running all of the pieces of information that made up that transaction through the hashing function, to check that you get the same hash.

At least, that's the idea. But here's where malleability comes in. The user's digital signatures used as part of the hash to 'sign' the transaction are meant to be in a certain format. That format wasn't always properly checked. This meant that a badly-formatted one could be introduced, and still accepted. Altering the signature in this way makes it possible to create different hashes for the same transaction.

That's not good. But, as it turns out, it's not world-endingly bad either. Here's why.

One problem here centers around exchanges, which bitcoin users often used to buy and sell bitcoins. They send their fiat currency or their bitcoins to an exchange, where it sits in an account, so that it can be converted. At some point, they may wish to withdraw bitcoins from the account.

There are several potential scenarios. Here are a couple:

Let's say that Alice runs an exchange, and Eve has bitcoins sitting in that exchange. Eve decides to withdraw her coins, and asks Alice to send the bitcoins to her address. When Alice sends them, this automatically creates a transaction, which is transmitted for mining so that it can be included in the bitcoin block chain.

But Eve pretends that Alice never sent them. She uses the transaction malleability flaw to reproduce Alice's original transaction, tweaking the signature slightly to produce a different hash. She then retransmits that transaction, with the different ID.

There is a chance that Eve's transaction will be confirmed on the block chain first. If that happens, the network will assume that transaction is valid, and won't record Alice's. Eve can then complain to Alice that she didn't receive the coins. When Alice checks for her transaction ID in the block chain, she won't find it, and she might try to send more bitcoins, meaning that she'll be out of pocket.

If you are using custom software of your own to handle your bitcoins, it may generate malformed hashes by mistake. These hashes may then be 'fixed' by another, better-behaved wallet, which properly formats them. But that might change the TX ID. If your wallet is not designed to notice transactions with the same characteristics but a different ID, then it may end up with 'stuck' transactions that hang in limbo. Worse still, it might think that it still has those coins to spend.

Either way, it's a bookkeeping nightmare, if your software can't cope. Bitcoin core developer Gregory Maxwell muses about that possibility here.

Someone could also cause wider problems for the bitcoin network by deliberately launching transaction malleability attacks on multiple exchanges at once, perhaps using software deliberately designed to create mutant transactions. This concerted attack is what appears to have happened this week, with multiple exchanges being hit.

The back end accounting systems for these exchanges may be able to cope with moderate numbers of mutant transactions, but if they are repeatedly bombarded with them, then it could cause them logistical problems for a while.

It could cause short-term problems for the market, too. Any uncertainty or doubt about market stability will naturally have an effect on market prices, especially with such an illiquid, volatile asset class.

There have been several issues with technologies that the bitcoin network uses, that create malleability problems. One of them was originally in the reference client - this is the software produced by a core team of developers that most people draw on when building their own services. That issue was a failure to double-check signature data before passing it to another piece of software that the bitcoin reference client relied on.

According to an announcement from the Bitcoin Foundation this week, this latest malleability attack is relaying mutated versions of transactions which is "exposing bugs in both the reference implementation and some exchange’s software," meaning that there are software flaws in different places in the bitcoin ecosystem that should be addressed.

The core developers have also told CoinDesk about two 'edge cases' in the reference client (those are flaws that would very rarely be invoked). These both focus on the wallet part of the software.

It turns out that there are quite a few other malleability issues, including some listed just this month by one of the core bitcoin developers in a Bitcoin Improvement Proposal (BIP) - a document that requests some changes to bitcoin.

The core developers are being muted about exactly what the most troublesome issues are, because they don't want to give any more information to potential attackers.

The community knew about the most often-discussed issue, which allowed for malformed signatures to be submitted, as long ago as 2011 (see this discussion). The problem here was that a key piece of software used by the bitcoin client didn't handle badly-formed signatures correctly. That wasn't the bitcoin core developers' fault, but what they failed to do was to get the bitcoin client to double-check that the signature was properly formed before they handed it over. That was remedied in the 0.8 version of the reference client.

Not all exchanges use the reference client to handle their bitcoin transactions, however. They may use custom versions, which do things slightly differently. So bitcoin developers, and wallet and exchange developers are all tinkering with their code to ensure that things run smoothly. For exchanges, that will involve making sure that exchanges handle mutant transactions gracefully, doing the right things when they see one.

The other fixes are more about processes. Things that make malleability more of a problem are a reliance on unconfirmed transactions, in which goods and services are transferred or provided before a transaction is confirmed in the block chain. So requiring transaction confirmation is always a good idea.

Similarly, having some manual verification of bitcoin withdrawals from exchanges can help to keep things in order at the back end.

It's an irritation, but little more. There are bugs in most software products, but not all bugs are created equal. Some are critical, show-stopping errors, and some aren't. These aren't, and bitcoin is not broken. The core basics of bitcoin - the decentralized way in which lots of computers work together to make decisions about transactions - still work.

In our exchange example above, you'd hope that Alice would have detailed enough bookkeeping records that she would still be able to reconcile the bitcoins that she had sent. If she sent Eve, say, 1 bitcoin at 12:10pm GMT on February 5th, that's a pretty unique transaction. She could simply say "our records show that this transaction went out, at this time, with these parameters. The transaction ID must have changed, so I'm not resending those bitcoins."

An exchange could also implement tools to automatically track inputs on transactions, which would help it spot mutations.

If anything, transaction malleability will help prove the decentralized network's resilience against discrete network events. Decentralization is one of the things that makes it the 'honey badger of money', after all.

Malleable coin image via Shutterstock