April 24, 2014

avatar

Understanding Bitcoin’s transaction malleability problem

In recent days, several Bitcoin exchanges have suspended certain kinds of payments due to “transaction malleability” issues. There has been a lot of talk about why this happened, and some finger-pointing. In this post, I will try to unpack what “transaction malleability” is and why it has proven to be a problem for some companies.

To understand the issue, we need to talk about two core concepts of Bitcoin: transactions and the public ledger.

A transaction is like a (paper) check. A simple transaction might say that Account A hereby pays X number of Bitcoins to Account B. This must be (digitally) signed by the owner of Account A. If the transaction is properly signed by Account A’s owner, and if Account A actually owns the coins that it says it is spending, then the transaction is well-formed. The transaction also has a “transaction ID” which serves to identify the transaction, like a check number.

(Bitcoin actually supports more complex transactions, for example with multiple payers and multiple recipients, but that doesn’t matter for us here, so let’s stick to the simple, check-like transactions.)

The other core concept is the public ledger. This is a single, public, consensus data structure that records every transaction that has ever happened in the Bitcoin system. In order for a transaction to be real, it must be put into the public ledger—if it’s not in the public ledger then it didn’t happen.

The public ledger is maintained by Bitcoin miners. For our purposes today all that matters is that miners are the people who add things to the public ledger. If you have a well-formed transaction and you want it to appear in the public ledger, you send that transaction to the miners. Typically your transaction will appear in the public ledger within about ten minutes. Once your transaction is confirmed as being in the public ledger, you know that the funds have officially been transferred, and you can move on.

(Of course, all of these things—transactions, signatures, and the public ledger—are fully digital and are defined using cryptography and distributed algorithms, which is what makes Bitcoin different from ordinary checks and bank accounts.)

Once Account A has digitally signed our example transaction, cryptography ensures that any attempt to alter the important details of the transaction, such as the payer, recipient, or amount, will be detectable. Any alterations to these important aspects of the transactions will necessarily invalidate the digital signature so that the modified transaction is no longer well-formed and will therefore be rejected. This is an important safeguard that prevents tampering with already-signed transactions.

It has been known since roughly 2011 that signed transactions are slightly “malleable” in the sense that it is possible to modify a signed transaction in certain minor ways, without invalidating the signature. The critical details about payment—who is paying how much, and to whom—can’t be changed, but certain peripheral information can be modified in a way that causes the transaction ID to change.

[Technical detail for crypto nerds: This happens because the transaction ID is computed by hashing a set of fields that is a superset of the fields covered by the signature.]

Now consider what happens to our example payment if, when Account A sends the signed transaction to the miners, the transaction is modified in transit so that the transaction ID changes. The modified transaction will show up in the public ledger, so A’s coins will be transferred to B as authorized.

So what’s the problem?

Perhaps A is watching the public ledger, watching for the expected transaction ID to show up. The payment will go through, but A will never see the transaction ID it is waiting for. The payment happened, but A thinks it didn’t happen.

This could be a problem, depending on how A reacts. Perhaps A will decide that the payment must have failed, leading A to re-do the payment—then B gets paid twice, and Bitcoin transactions are not reversible. Or perhaps A doesn’t double-pay but the mismatch causes A’s accounting system to get confused—so that the books balance but the payments in the public ledger don’t match up with the payments A thinks it has made.

For a long time this issue was mostly theoretical, but there has been a recent surge of transaction modification, causing trouble for MtGox and some other Bitcoin businesses.

Who is at fault?

On the one hand, you can argue that malleability has been a known issue since 2011 and companies should have known to be watching for the non-malleable payment details of a transaction to show up, rather than waiting for the transaction ID to show up. If you’re not doing this, your system is buggy and it’s your own fault. Or so this argument goes.

On the other hand, watching for a transaction ID is an easy mistake to make, and it is kind of odd to call something a transaction ID when it can be changed. This is certainly a rough edge in the Bitcoin design, which could have been avoided and will likely be fixed in the future. This was an avoidable error by the Bitcoin designers. Or so this argument goes.

Both arguments have some merit. The bottom line is that these problem could have been prevented either by the Bitcoin designers or by the authors of the affected software. This is an important reminder that relying on new, complex technologies carries risks, and it pays to be extra careful to engineer the details of your technology correctly.

Comments

  1. Joe Pallas says:

    Yes, “it is kind of odd to call something a transaction ID when it can be changed”, but further: it is dangerously misleading to call something a transaction ID when it does not identify a transaction.

  2. Tony Lauck says:

    It is dangerously irresponsible to run financial software involving millions of dollars of customer’s money without doing due diligence and being aware of the implications of “edge” cases that have been known for 2+ years on public web sites.

    The present behavior of at least one of the Bitcoin exchanges demonstrates either incompetence and/or ignorance or deliberate FUD created by people who are trying to spread the blame to CYA.

    • Wes Felter says:

      I suspect the exchanges have been in a situation where fixing the edge cases would cost more than their revenue and once their revenue exploded they ended up spending all their time on scaling instead of security.

  3. Sean says:

    Good article, just one correction, the blockchain is maintained by bitcoin-d wallet holders, not just miners. You don’t need to be a miner to participate in maintaining the blockchain

  4. Sean says:

    Here’s a succint account of what’s being done by the bitcoin dev team
    https://bitcoinfoundation.org/blog/?p=422

  5. Michael says:

    Good information.

    If I follow correctly, the transaction ID is changed but the exchange doesn’t know so it looks for the original transaction ID. Next, the mallformed transaction is accepted and becomes part of the blockchain. Can this be prevented? Otherwise, the exchange holds the original copy whereas the blockchain holds the mallformed copy. How to reconcile? I fear by changing the code in the exchange alone may not be sufficient.

  6. Mr. Crankypants says:

    Very well written. I don’t exactly understand how “when Account A sends the signed transaction to the miners, the transaction is modified in transit so that the transaction ID changes”, but I probably don’t need to know exact details of a live exploit. I’m not sure if I understand the mistake, Mt.Gox only looked at the transaction ID and didn’t bother to actually check the signature on the vitals inside the transaction, is that all that there is? A savings of a few CPU cycles? As a programmer who’s recently left the industry, all I can say is… HAHAHAHAHAHAHAHAHAHAHAHAHA!!!!!!!