The programming error that cost Mt Gox 2609 bitcoins

In October 2011, Mt Gox lost over 2609 bitcoins by accidentally creating transactions that can never be redeemed. (At the time, 2609 bitcoins were worth about $8000, but they would be worth almost $1.5 million dollars now.) The problem was discussed on the Bitcoin forum, but I think it's worth taking a closer look at it in light of Mt Gox's recent massive bitcoin loss and bankruptcy. This problem reveals how easy it is to lose bitcoins through software errors. It also reveals that Mt Gox has made careless and expensive programming errors before.

The problem

When you send bitcoins to an address, what happens inside the Bitcoin transaction is more complicated than you would expect. The transaction contains a tiny computer program in the Bitcoin Script language, and this program is executed to determine if the bitcoins can be spent. Normally the program requires a public key and signature in order to spend the bitcoins. The program checks that the public key matches the address you sent the bitcoins to, and the signature is valid, proving the spender of the bitcoins has the private key. If everything matches, the bitcoins can be spent.

You might wonder why Bitcoin uses such a complex system to validate transactions. The idea is that by providing a programming language, Bitcoin allows many different types of transactions, such as escrow transactions or more complex contracts.

Going into a bit more detail, a typical scriptPubKey program looks like:

OP_DUP
OP_HASH160
f2e63314c350094550c703fcdcd4850ad37d8310
OP_EQUALVERIFY
OP_CHECKSIG

This program is part of a transaction that sent bitcoins to the address 1P9LHy6K2c9cwbfSfdaaoYVAprqUYtcFnB (which in hex is the f2e633... value above). In order for that address to redeem the bitcoins, they must provide the public key for the address 1P9L... and provide the signature for the spending transaction (which proves they have the private key). Walking through the execution of the program, it first duplicates the provided public key, computes the 160-bit hash of it, and verifies that it is equal to the provided public key address. Then it checks the signature for validity. If all goes well, the bitcoins can be spent. If there is a problem, the transaction is rejected.

In Mt Gox's bad transactions, they made a small but costly error. The script is:

OP_DUP
OP_HASH160
0
OP_EQUALVERIFY
OP_CHECKSIG

Note that in place of the destination address hash, this transaction has the byte 0, representing OP_0, which pushes an empty array of bytes. Since it's impossible for the 160-bit hash to match an empty array, it's impossible for this script to complete successfully, and the bitcoins can never be spent. (For more information on how these scripts work, see my article Bitcoins the hard way).

Why does Bitcoin permit broken transactions?

You might wonder why Bitcoin permits transactions that can never be spent. Unfortunately, it would be very difficult to determine if a script can be satisfied or not. Bitcoin is designed to give people a lot of flexibility with the Script language, even though it's easy to shoot yourself in the foot. In addition, a complex algorithm to reject transactions would be very dangerous - if clients and miners disagree on the validity of a transaction, a blockchain fork will result, causing chaos.

(The computer scientists are probably yelling "halting problem" at this point. However, that doesn't apply because the Bitcoin Script language doesn't have loops so it's guaranteed to halt. A non-terminating script would be a disaster since miners and clients would lock up, so the language prohibits looping.)

In addition, it's common to lose bitcoins by using an address when you don't have the private key, and there's no way software could detect that. Strangely, people often do this on purpose. Many transactions deliberately send tiny amounts of bitcoins to bad addresses to hide text and images in the blockchain. Other people have deliberately lost over a million dollars in bitcoins in a Counterparty proof-of-burn.

Gold coins from the Fishpool Hoard. Unlike lost bitcoins, lost gold coins can sometimes be recovered.

Another interesting script bug

While analyzing coinbase transactions, I came across another interesting bug that lost bitcoins. Some transactions have the meaningless and unredeemable script:

OP_IFDUP
OP_IF
OP_2SWAP
OP_VERIFY
OP_2OVER
OP_DEPTH

That script turns out to be the ASCII text script. Instead of putting the redemption script into the transaction, the P2Pool miners accidentally put in the literal word "script". The associated bitcoins are lost forever due to this error.

Conclusion

Losing bitcoins due to programming errors is very easy. Mt Gox has lost thousands of bitcoins in the past this way, as have others. I don't know what happened to Mt Gox recently (although I know it wasn't OP_PUSHDATA2 malleability), but based on history it is worth keeping programming errors in mind.

If you want some scary reading describing other major Bitcoin losses, take a look at List of Major Bitcoin Heists, Thefts, Hacks, Scams, and Losses.