There's a lot of really fascinating technology in Bitcoin. Even more fascinating to me is the history of different flaws in Bitcoin, and how they've been addressed. In this post I want to explain one of the most subtle and nefarious Bitcoin flaws of all time: transaction malleability.
Overview Of The Attack
Bitcoin payments are encoded as transactions that eventually become part of the blockchain. Each Bitcoin transaction contains metadata such as: the input addresses (where the money is coming from), the output addresses (where the money is going), the amount of Bitcoin actually being sent, and cryptographic signatures proving the authenticity of the transaction. This data is bundled into a DER-encoded ASN.1 representation before being broadcast to the network. Each transaction has a "transaction id" or txid, which is a hash of the transaction. An example txid is adae0270457bad95152c5ae7771b50fae06afa01edeefca4201689e7c99e0b19. This hexadecimal string is calculated using a variant of SHA-256 on the DER-encoded transaction data.
These txids are immaterial to how the Bitcoin blockchain works: their primary use is as a convenience for humans when referring to transactions. For instance, suppose you want to buy something online, and send a Bitcoin payment to an ecommerce site. If there's a problem with the merchant's ecommerce software, it's possible that they could "lose" the transaction, meaning they might think you haven't actually paid them. You could then show them the txid of your payment, and then the merchant could then manually reconcile the error after confirming the transaction. For this to work the txids need to be immutable, and that was the original intention in Bitcoin.
Bitcoin is a peer-to-peer network, operating using a gossip protocol which is conceptually similar to BitTorrent. To send a payment, a node creates a transaction and then broadcasts it to the node's peers on the network. The peers then broadcast the transaction to their peers, and so on. Usually it takes less than a minute from the time a transaction is created until it fully propagates to the rest of the network. Well connected nodes in Europe and North America have typical propagation times on the order of 10 to 15 seconds.
Here's how the transaction malleability attack works. Alice creates a Bitcoin payment transaction, and sends it to her peers. The original Bitcoin implementation was underspecified with respect to how txids were actually calculated (more on this in a moment). Therefore, it's possible for Alice's peers to slightly modify the transaction. Suppose Bob is a peer of Alice, and wants to initiate a transaction malleability attack against Alice. The inputs, outputs, and payment amount are all cryptographically signed, so Bob can't steal money or make any semantic changes to the transaction. However, Bob can make some changes that don't change the transaction semantics, but do change the computed txid. At this point Bob will broadcast the transaction with a new txid to the rest of the network. At this point it's a race to see which transaction will actually be accepted by the network: the original transaction created by Alice and relayed by her good peers, or the modified version created by Bob. The attack is called "transaction malleability" because Bob was able to modify the transaction, even though the transaction was supposed to be immutable.
Transaction Malleability Significance
Most Bitcoin clients have an option to show you a txid after you send a transaction. Bitcoin transactions take some time to actually be confirmed as part of the blockchain. Therefore it's natural to periodically check the blockchain to see if the transaction has actually gone through, by checking if the expected txid has been added to a new block. If a transaction malleability attack occurs, and the txid changes, then the transaction will eventually be added to the blockchain, but under an unexpected txid. This can confuse client software that was looking for a particular txid.
For instance, suppose Alice sends 1 BTC with expected txid $A$, but Bob modifies the transaction so the new txid is $B$. The modified transaction $B$ then gets added to the blockchain, which implicitly invalidates $A$. Alice's client software keeps checking for txid $A$, but never sees it. Alice's wallet software will debit 1 BTC from her account once the modified transaction is confirmed, since the modified transaction still sent 1 BTC from her account. But if Alice isn't paying close attention, she might eventually give up and think the transaction failed for some reason, and she could retry the transaction. If she does retry the transaction, she'll send another 1 BTC to the same address. In essence, Bob has tricked Alice into double paying.
It is thought that this attack was used against some Bitcoin exchanges, including Mt Gox. Here's how it would work. You deposit 1 BTC into an account on an exchange. Later, you try to withdraw your 1 BTC off the exchange, back to your private wallet. If you control nodes that peer with the exchange, you might be able to change the txid for your withdrawal using transaction malleability. The 1 BTC you withdrew will go into your private wallet under a new txid. If the exchange is naive, you might be able to trick the exchange into thinking that it never sent you your withdrawal. Then you'd ask to withdraw your 1 BTC again, and if you tricked the exchange it could comply. By doing this repeatedly, you could potentially withdraw a large amount of Bitcoin before the exchange caught on. This is possibly what happened to Mt Gox (but see below for a more detailed analysis).
How Transaction Malleability Actually Works
Before continuing, I want to re-emphasize that Bob can't change where Alice's money comes from, where it goes, or how much is sent. These parameters are all cryptographically signed by Alice, using her private key. Bob can really just change the actual txid shown to humans. How does this work exactly?
The first flaw is that the original Bitcoin implementation used OpenSSL to verify the DER-encoded ASN.1 transaction data. However, OpenSSL did not do strict validation of the ASN.1 data by default. For instance, OpenSSL would ignore extra padding in the data. Just like adding trailing whitespace to a C file won't change the semantic meaning of the C code, Bob could add extra padding data to the transaction. This padding changes the transaction hash, just as adding trailing whitespace to a source code file would change the file hash.
The flaw related to DER-encoded ASN.1 data was fixed by the BIP66 soft fork. This became active on block 363,724 which was added to the blockchain on July 4, 2015. BIP66 is simple: it mandates a strict set of rules to how the ASN.1 data is encoded, and requires Bitcoin nodes to reject transactions that don't conform to the specification.
The second transaction malleability flaw was found later, and is much more subtle. The cryptographic signature scheme used by Bitcoin is ECDSA, which is a modified version of DSA using elliptic curves. An ECDSA signature consists of pair of numbers $(r, s)$. The elliptic curve itself has integer order $n$. There is a surprising consequence of this, due to how the elliptic curve math works: if $(r, s)$ is a valid signature, then so is the complementary signature $(r, -s \mod n)$. Given a signature $(r, s)$ it's possible to calculate the complementary signature without knowing the ECDSA private keys. The complementary signature has a different hash, so using the complementary signature will result in a new txid. In other words, an attacker can change a txid by broadcasting a variation of the transaction that uses the complementary ECDSA signature.
The fix for the ECDSA signing flaw is to enforce a canonical signature
representation. The Bitcoin core developers decided to use the following scheme:
both signature values are calculated, but only the signature with the smaller
"S-value" is considered valid. That is, the correct representation is the form
with the smaller unsigned integer representation. The ECDSA signing flaw was
originally supposed to be fixed
by BIP62,
which was later withdrawn. However, Bitcoin Core added a mechanism to enforce
low S-values with PR #6769,
which was merged in Bitcoin Core in October 2015. Validation is done when the
transaction script contains the opcode SCRIPT_VERIFY_LOW_S, which all recent
Bitcoin implementations use.
The Future
I'd be remiss to end this post without mentioning the hottest topic in Bitcoin right now, BIP141 a.k.a. Segregated Witness or "Segwit". Transaction malleability is already more or less fixed in Bitcoin, but Segwit will improve the situation further with the introduction of a new type of txid, the wtxid (i.e. "witness" txid).
Here's how Segwit fixes the problem. When we think of a transaction, we really just care about the inputs, outputs, and payment amounts. ECDSA signatures are essential to the Bitcoin security model, but don't actually affect these transaction details. Segwit transactions continue to include a legacy txid as described here, but also include a new wtxid field. The wtxid is calculated according to a strict set of rules over the transaction metadata, without including the ECDSA signature data when computing the transaction hash. This prevents all known transaction malleability attacks. Old clients can ignore the wtxid field and continue to use the legacy txid.
Fixing transaction malleability is just one aspect of Segwit. BIP141 has a number of other improvements as well: it makes a number of significant changes to the Bitcoin scripting language, and will enable the use of cryptographically secure off-chain transaction using the Lightning Network. BIP141 should make future protocol extensions to Bitcoin much easier to deploy. As of the time of this writing, the most likely scenario is that Segwit will get "locked in" later this month, and then activate sometime in August. For more details about the Segwit timeline, read Jimmy Song's post UASF/Segwit2x Scenarios and Timelines.
Postscript: The Mt Gox Hack
Since the Mt Gox incident is so famous, I want to point out that it's not known definitively if transaction malleability is actually what caused Mt Gox to become insolvent. Mark Karpeles, the founder of Mt Gox, claimed that coins were stolen using this flaw, but it's hard to independently verify this claim. An attacker exploiting transaction malleability could generate new receive addresses for each transaction. They could also randomize the withdrawal amounts. This would make it very difficult (potentially impossible) to audit the blockchain to verify that this attack was used against Mt Gox. To verify the claim, you'd need the actual Mt Gox database records to perform a full analysis. It's possible that only a small percentage of stolen coins from Mt Gox were taken using this attack, or even none at all.
Regardless of what happened with Mt Gox, since this transaction malleability is quite subtle, it's likely that other exchanges or sites were tricked into resending payments using transaction malleability.