Bitcoin 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.
What is transaction malleability?
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.
Is it the same as double spending?
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.
How does transaction malleability work?
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.
Transaction malleability will help prove the decentralized network's resilience against discrete network events
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.
How can it cause problems?
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:
Malicious individual attacks
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.
Well-meaning accidents
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 .
Mass denial of service attacks
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.
Does this mean that there's a bug in bitcoin?
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.
