Bitcoin transaction malleability: looking at the bytes

"Malleability" of Bitcoin transactions has recently become a major issue. This article looks at how transactions are modified, at the byte level.

I have a new article The malleability attack graphed hour-by-hour. Check it out too.

An attacker has been modifying Bitcoin transactions, causing them to have a different hash. Recently an attacker has been taking transactions on the Bitcoin peer-to-peer network, modifying them slightly, and rapidly sending them to a miner. The modified transaction often gets mined first, pre-empting the original transaction. The attacker can only make "trivial" changes to a transaction, so exactly the same Bitcoin transfer happens as was intended - the same amount is moved between the same addresses, so this attack seems entirely pointless. However, each transaction is identified by a cryptographic hash, and even a trivial change to the transaction causes the transaction hash to change. Changing the hash of a transaction can have unexpected effects on the Bitcoin system.

A very quick explanation of transactions

A Bitcoin transaction moves bitcoins from one address to another. A transaction must be signed with the private key corresponding to the address, so only the owner of the bitcoins can move them. (This signing process is surprisingly complex.) The signature is then put in the middle of the transaction. Finally, the entire transaction (including the signature) is cryptographically hashed, and this hash is used to identify the transaction in the Bitcoin system. The important data is protected by the signature and can't be modified by an attacker. But there are few ways the signature itself can be changed, but still remain valid.

(This is oversimplified. For more details, see Bitcoins the hard way.)

Looking at a modified transaction

To find a transaction suffering from malleability, I looked at the unconfirmed transactions page. If a transaction gets modified, only one version will get mined successfully (and actually transfer bitcoins), and the other will remain unconfirmed (and have no effect). Among the many conditions enforced in mined blocks, the same bitcoins can't be spent twice, so both transactions will never be mined. This is why having two versions of a transaction doesn't result in two payments.

I picked a random unconfirmed transaction from Feb 11 to examine. (Unfortunately this transaction has been discarded since I wrote this article, breaking my links. But you can look up a different one if you want.) Blockchain.info helpfully includes a banner warning that something is wrong:

Warning! this transaction is a double spend of 112593804. You should be extremely careful when trusting any transactions to/from this sender.

Looking at the transactions, everything seems fine:

The confirmed transaction takes 0.01 BTC from 1JRQExbG6WAhPCWC5W5H7Rn1LannTx1Dix and transfers 0.0099 BTC to 1Hbum99G9Lp7PyQ2nYqDcN3jh5aw878bFt (the remainder is a mining fee of 0.001 BTC). This transaction has hash bba8c3d044828f099ae3bc5f3beaff2643e0202d6c121753b53536a49511c63f.

The unconfirmed transaction takes 0.01 BTC from 1JRQExbG6WAhPCWC5W5H7Rn1LannTx1Dix and transfers 0.0099 BTC to 1Hbum99G9Lp7PyQ2nYqDcN3jh5aw878bFt (the remainder is a mining fee of 0.001 BTC). This transaction has hash d36a0fcdf4b3ccfe114e882ef4159094d2012bc8b72dc6389862a7dc43dfa61c.

The scripts of both transactions appear identical:

Input Scripts
30450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d8701 046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44 OK
Output Scripts
OP_DUP OP_HASH160 b61c32ac39c63f919c4ce3a5df77590c5903d975 OP_EQUALVERIFY OP_CHECKSIG 
Both transactions look identical: the bitcoins are moving between the same accounts in both cases, the amounts are equal, and the scripts look identical. So why do they have different hashes? A clue is the unconfirmed transaction is 224 bytes and the confirmed transaction is 228 bytes.

Looking at the raw transactions also fails to show what is happening:

{
  "hash":"bba8c3d044828f099ae3bc5f3beaff2643e0202d6c121753b53536a49511c63f",
  "ver":1,
  "vin_sz":1,
  "vout_sz":1,
  "lock_time":0,
  "size":228,
  "in":[
    {
      "prev_out":{
        "hash":"3ceafb1d6864091a6c40f0f0fa7d4072d71a909820444ac307dcaa7a2d4b88d4",
        "n":1
      },
      "scriptSig":"30450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d8701 046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44"
    }
  ],
  "out":[
    {
      "value":"0.00990000",
      "scriptPubKey":"OP_DUP OP_HASH160 b61c32ac39c63f919c4ce3a5df77590c5903d975 OP_EQUALVERIFY OP_CHECKSIG"
    }
  ]
}

Even though the scripts are mostly in hex in this raw display, they have been parsed slightly, which hides what is going on. We need to get the full scripts here and here.

The unconfirmed transaction has script:

4830450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d870141046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44
The confirmed transaction has script:
4d480030450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87014d4100046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44
There are a couple differences (highlighted in red). But what do they mean?

This script is the scriptSig, the signature of the transaction using the sender's private key. This signature proves the sender owns the bitcoins. However, the scriptSig isn't just a simple signature, but is actually a program written in Bitcoin's Script language. This program pushes the signature data onto the execution stack. The program from the unconfirmed script is interpreted as follows:

PUSHDATA 4848
signature
(DER)
sequence30
length45
integer02
length20
X539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1
integer02
length21
Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
SIGHASH_ALL01
PUSHDATA 4141
public key type04
X6c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc4
Y 02b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44

The program from the confirmed script is interpreted as follows:

OP_PUSHDATA2 00484d 48 00
signature
(DER)
sequence30
length45
integer02
length20
X539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1
integer02
length21
Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
SIGHASH_ALL01
OP_PUSHDATA2 00414d 41 00
public key type04
X6c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc4
Y 02b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44

Note the highlighted differences. The original transaction has a byte 0x48, which says to push (hex) 48 bytes of data. The modified transaction has a OP_PUSHDATA2 (0x4d), which says the next two bytes (48 00) are the number of bytes to push. In other words, both transactions do exactly the same thing (push the signature), but the original indicates this with 48, while the modified transaction indicates this with 4d 48 00. (Pushing the public key has a similar modification.) Since both scripts do exactly the same thing, both transactions are equally valid. However, since the data has changed, the transactions have two different hashes.

Why does malleability matter?

Transaction Malleability has been discussed for years and treated as a minor inconvenience. Both transactions have exactly the same effect, moving bitcoins between the same addresses. Only one transaction will be confirmed by miners, and the other will be discarded, so nobody gets paid twice even though there are two transactions.

There are, however, three problems that have turned up recently due to malleability.

First, the major Mt.Gox exchange stated they would stop processing bitcoin withdrawals until the Bitcoin network approves and standardizes on a new non-malleable hash. Apparently they were using the hash to track transactions, and would re-send bitcoins if the transaction didn't appear to go through. This is obviously a problem if the transaction did go through, but with a different hash.

Second, some wallet software would use both transactions to compute the balance, which caused it to show the wrong value.

Finally, due to the way Bitcoin handles change, malleability could cause a second transaction to fail. This requires a bit more explanation.

Failures due to change and malleability

The Bitcoin protocol doesn't really move bitcoins from address to address. Instead, it takes bitcoins from a set of inputs, and sends them to a set of outputs. Each output is an address (actually a script, but let's ignore that for now). Each input is an output from a previous transaction, and each input must be entirely spent.

As a result, if you have 3 bitcoins, and you want to spend one of them, the other two bitcoins get returned to you as change, sent to an address you control. If you then want to spend some of the change, your second transaction references the previous transaction that generates the change, referencing it by the hash of the first transaction. This is where malleability becomes a problem - if the first transaction's hash changed, the second transaction is not valid and the transaction will fail. Note that the change will still go to your proper address, so you can spend it as long as you use the correct (modified) transaction hash, so you don't lose any bitcoins. You just have the inconvenience of having a transaction rejected, and you'll need to redo it with the right hash.

The change problem only happens because some wallet software takes a shortcut, letting you (attempt to) spend the change before the transaction has been confirmed. The reasoning is that since it's your change from your transaction, you should be able to trust yourself. But that breaks down with malleability.

Malleability has been known for a long time

Transaction malleability has been known since 2011. The exact OP_PUSHDATA2 malleability used above was described four months ago here. There are many other types of malleability, which are explained here. The script code can be modified in several ways while leaving its operation unchanged. The signature itself can be encoded slightly differently. And interestingly, due to the mathematics of elliptic curves the numeric value of the signature can be negated, yielding a second valid signature.

Conclusion

Hopefully this has helped to make malleability more understandable. If you want to know more details of the Bitcoin protocol, including signing and hashing, see my previous article Bitcoins the hard way.

7 comments:

  1. Nice write-up. I only vaguely understood what was going on before reading this, but it makes sense now. Thanks!

    ReplyDelete
  2. > OP_PUSHDATA 0041 4d 41 00

    I think you missed a '2' in the operator's name there.

    ReplyDelete
  3. In case anyone's wondering what my comment was about, the issue I was pointing out in the post has now been fixed.

    ReplyDelete
  4. so what happened here ??

    # Theft Withdrawal Transactions and historical withdrawals by Attacker 1
    address,txid_cleaned

    1C2qqRaDHGbTHeEa29p3QruyUKusYDMCb9,0f1a8a0258e6a8b0860f7ba04a81c31077e029b7a5ac82b6631c5397b7b7a0d6
    1C2qqRaDHGbTHeEa29p3QruyUKusYDMCb9,582b8663a91adc90d931ff1536802fa6d2422176230b5664b636826be63bf049
    1C2qqRaDHGbTHeEa29p3QruyUKusYDMCb9,12fd1f14c55bfc3bd07d644355f047d8237855ec3e5a6434254cb021e8a0fcf3
    1C2qqRaDHGbTHeEa29p3QruyUKusYDMCb9,82cdc3b2dedfbfaad5a5c8d89a775af2df535ebe9e3d8602633f9976ad0abdf5


    -----BEGIN PGP SIGNATURE-----

    iQIcBAEBCgAGBQJS/RWkAAoJECRwq0imSkC03nsQAJWepo3NnOzKWbA8Gx3sz/RU
    QQHKuFl2LIAu/L0EXOj/Q1HJHVUSsfyKk7V01ePuUNFjWZXOYrkhV10EK0lls5QL
    l6NbLX3Pd4y88kh5kZ/j5lcucx3vCyuNWp854MGNYrxOghA3qTfdte9kXST/cybd
    e8Zo21I5O75BwUaLUv31W07uRy+4MW+ASwy8utA5Pwed/sc22ts2e2x8lAHN6eFB
    85BHij8DuklHtk8TCcjLRaPUrV2mvQK3bDm/P72ei8te6tMn58zrxBYZLDuymG2R
    LpSiK+H+Bc4C++rvKPeGbg1tbetC1l3POeIBBMRZl/ZPLPl+V5yVqnZ7ucoyFZap
    djVLXYaxZrLVH87o8sY3z+z9o6aDZ5+FfNOY0fKJlgL8pokemL5o+BiAbTlOBBPy
    LSEt7XBWszZ4kEJGkwEMnG7PPimoxhXNXcOgeniHAAlTtV7T/2fIYkXLjESx3osi
    4g6mOfkdgmeiL2ioYrclD4HiB2s+ycYKNUWAwmU52oJHEuErm1MHtxqYH5GNJKXR
    hs/wtVPhnclto1g1/uMg4uUeGjyQOwsD9842oOBG8UPvIKW93UN5rh4p9gykd9Ss
    XLsVgKw4vDX2gEKBW1k+NI8NrfgV5lJrPS71zqpiI2NMWVwr8uG817IbKh4/ZD1p
    f9Ofh2e2b0sGGVUFEbFd
    =QBPm
    -----END PGP SIGNATURE-----

    ReplyDelete
  5. Note that the malleability is also with PUSHDATA and PUSHDATA4, not specifically PUSHDATA2. Also, a major application that malleability breaks is anything that relies on a precomputed nlocktime'd refund transaction, spending a transaction back to the sender before the original transaction is announced.

    ReplyDelete
  6. great article, i have really enjoyed reading this. learning about mining is very interesting and mineco are a really good mining company!

    ReplyDelete
  7. Really nice post!
    Now I'm trying to conduct such a malleable TX on my own example, just to try how it works.
    Can you tell what exactly and how I can change in my tx 350946f9c61598ff4d8c77cb99625f6ac106765dcbf2d2d855a122363b3f3c24?
    Did you use createrawtransaction/signrawtransaction?

    ReplyDelete