The troublesome history of the bitcoin exchange MtGox

Most, if not all, of the people interested in the bitcoin phenomenon have heard of MtGox, the Japanese bitcoin exchange. I'll look in to some of the issues they've run into over the handful of years they've existed.

From trading cards to real money

MtGox started in 2009 as an exchange for trading cards (MtGox = Magic: The Gathering, Online eXchange), by Jed McCaleb. Before this, Jed was mostly known for creating the P2P-file sharing software eDonkey2000. In July 2010, MtGox switched from being a trading card exchange, to a bitcoin exchange, letting users buy bitcoin for "real money".

In November 2010, the bitcoin price was USD $0.5, three months later, in February 2011, it was on par with the US dollar at $1/BTC. A month after that, in March 2011, Jed McCaleb sold Mt.Gox to Mark Karpelès, a French developer in Japan, who is also the one behind the VPS service AutoVPS.

The hack and the leak

In June 2011, just three months after Mark took over the site, MtGox was hacked, and over 60.000 usernames and hashed passwords were leaked. They reportedly accessed a MtGox "auditor" account, and issued huge sell orders for non-existing bitcoins, at any ask price, which resulted in a crash from $17.51 down to $0.01 per bitcoin on the MtGox exchange.

"Two months ago we migrated from MD5 hashing to freeBSD MD5 salted hashing. The unsalted user accounts in the wild are ones that haven't been accessed in over 2 months and are considered idle. Once we are back up we will have implemented SHA-512 multi-iteration salted hashing and all users will be required to update to a new strong password"

They decided to reverse all transactions, and suspended the site for a week while checking and fixing the security. Since password re-use is common, many users got their bitcoin stolen from other exchanges and online wallets due to the leak of hashed passwords from MtGox.

The hack caused delays of withdrawals and transfers, so people started questioning the solvency of MtGox. Are they trying to hide that they lost the bitcoin in the June 2011 hack? Mark decided to prove that they still were in control of the bitcoin by making a huge transfer between two internal wallets, to the size of 424,424.42424242 bitcoins:

The 2013 DDoS and service issues

The following months there are still complaints about slow withdrawals, and frequent issues, but otherwise it is business as usual. The U.S. dollar prices on MtGox are usually higher than on other exchanges, perhaps related to withdrawal issues.
In April 2013, MtGox were hit by a distributed denial-of-service attack, and suffered massive downtime:

Since yesterday, we are continuing to experience a DDoS attack like we have never seen. While we are being protected by companies like Prolexic, the sheer volume of this DDoS left us scrambling to fine-tune the system every few hours to make sure that things don’t go beyond a few 502 error pages and trading lag.

There are however reports that the attack was directed to a single open backend-server, not the CDN-powered/DDoS-protected frontend ones. It was a single open server, running both the webserver and the exchange, and found via a simple scan of MtGox's assigned IP block.

Believe it or not, there is pretty much nothing that can be done. Large companies are frequently victims of these kinds of attacks. Even though we are using one of the best companies to help us fight against these DDoS attacks, we are still being affected.  There are a few things that we can implement to help fight the attacks, such as disconnecting the trade engine backend from the Internet.

There are repeated rumors about problems on MtGox, in correlation with price drops on bitcoin. Users often experience lag or connection problems when trying to panic sell/transfer their bitcoins, and MtGox also chose to suspend the site at times:

However, since MtGox was the largest exchange, with 70% of all trades worldwide, it was not too strange to experience lag or issues during busy market times (quick changes in bitcoin value).
This graph shows the daily trading volume of bitcoin, and which exchanges were involved:

Enter Homeland Security

MtGox was by far the largest trading site, but something happened in May, 2013. The Department of Homeland Security issued a seizure warrant for MtGox's account at Dwolla, their payment provider, since they hadn't registered as a money transmitter with FinCEN in the US. They reportedly seized $2.9 million from MtGox's Dwolla accounts, and another $2.1 million from MtGox's Wells Fargo accounts, totaling in $5 million seized.

No more dollar ($) withdrawals

In June 2013, they temporarily suspended U.S. Dollar withdrawals, but later reinstated it. The last few months were troublesome for MtGox. Very few people have were able to successfully sell their bitcoin for money, and the few orders that went through took weeks or even months.

Btw, not bitcoin either

Fast-forward to February 2014. After several months of withdrawal problems, and an increasing backlog of failed bitcoin transfers, they decided to disable bitcoin transfers also.

With delays and issues in exchanging bitcoin for fiat money (regular currencies), and the halt of bitcoin transfers to other exchanges, or users own wallets, they have effectively cut of people's access to their money. It may be a harsh thing to do, but the reason for this is simple enough:

MtGox currently has no control over or knowledge of what bitcoins they have, and how much belongs to whom!

The client is the culprit

There are several different bitcoin applications to use, however, the most common one, the reference client, is the one the bitcoin core developers are creating and updating. Other versions usually use the changes in this one as a reference to changes that need to be implemented, or at least should.

MtGox doesn't use the standard client, but instead they are using either an older version, or, more likely, a custom version of the software. This is where the problem arise.

First, lets look at how the bitcoin network and a transaction works.

The bitcoin block chain and transactions

All bitcoin transactions, from the single first one, to the ones being made right now, are stored in the bitcoin block chain. This is a big public ledger of every single transaction ever made over the years. This is the reason a new bitcoin client needs to download several gigabytes of data before it's up-to-date and knows the current state of itself and the whole network. There are clients that only rely on smaller bits of the data, assuming that the previous ones are correct, but the block chain data is a feature of bitcoin which is necessary to prove that a certain address/person actually has access to certain funds. All of this is managed via a peer-to-peer network, where clients relay transactions to each other.

When a bitcoin transaction is made (assuming it's actually a funds transfer), it contains information of where the funds come from (the inputs), where they are going (the outputs), and the amounts transferred. Since every single previous transaction is known, the bitcoin software can follow-the-trail and know the inputs actually has access to the funds.

Each transaction on the network also contains a transaction id. The transaction id is a hash of the contents of the transaction, so that every transaction will have (should have) a unique transaction id.

Since bitcoin clients generally talk to each other via a P2P-network, this means that transactions are sent through different clients and added to the big public ledger. When a client sees a new transaction, it can check the public ledger to see if the sender should have access to those coins, or check if they have been spent already. However, since it's a P2P-network, perhaps they were spent already, but the local client hasn't seen that transaction yet?

This is where "confirmations" come in. A new transaction will have zero confirmations, meaning that there is nothing actually proving that the sender had access to the fees. The local client can check the public ledger, and verify that it should have access, but, it does not know if it has "missed a packet" that says that they were already spent.

When a new bitcoin block is mined, it "confirms" a bunch of transactions. The miners get transaction fees, and newly mined bitcoin as a reward to their confirmations of the transactions. With zero confirmations, you can't actually be sure that the transaction is valid. When it has received a single confirmation, it should be trusted, but for transactions with larger value, most exchanges and bitcoin services usually wait for more confirmations (~6) before allowing the coins to be exchanged for goods or services.

The "transaction malleability" flaw

Within the bitcoin transaction, there is also a digital signature (ECDSA), to make sure you have access to the wallet doing the transaction, and OpenSSL is very "kind" to allow and accept signatures with an invalid encoding. The digital signature consists of two large integers, and in general, any leading zeros should be dropped. However, even if they aren't, OpenSSL happily validates the signature anyways.

However, the signature is part of the hash that creates the transaction id. This means that leading zeros can be prepended to those integers, making the signature still valid, but gives it another transaction id (hash)!
Since the signature isn't "altered", just prepended with zeros, "anyone" could alter the transaction, and give it a new transaction id (since the hash of the transaction changes, even though the signature isn't altered). The actual sender, recipient and amounts can't be changed, since that would invalidate the digital signature.
The problem is that someone in the bitcoin network could maliciously alter the transaction by keeping the signature valid, but giving it a new transaction id (hash). The transactions would only differ by the hash, not which bitcoin is being spent. The miners could confirm either of the transactions, which validates that the sender had access to the coins. The second transaction would never be validated, since the coins will already have been spent by the first transaction.
Here's a (very simplified) mockup:

Both transactions are valid, and they contain the same data, but they have different hashes (transaction ids). Only one of them will be validated by the bitcoin network.

With version 0.8 of the bitcoin reference client, it would no longer relay transactions with leading zeros to the rest of the network, preventing troublesome transactions from propagating. The bitcoin network also does not allow newly mined coins to be spent, before they have 101 confirmations.

In September 2013, MtGox used freshly mined coins for transactions (which was denied by the network). Users started seeing failed transactions when transferring bitcoin from the exchange. MtGox didn't know what was causing the issues, so they tried raising the transaction fees, to no avail. MtGox fixed this by changing their software to use the oldest coins first.

But, the problems continued. More and more transactions were failing for users. And, MtGox has a nice page showing the currently failing transactions! They just recently started redacting information in them...

Now, the reason was that their software was sending transactions with padded signatures, which were denied by other bitcoin software, to prevent the so-called transaction malleability flaw.

Since the transactions were visible, and people wanted their own transactions to succeed, they would try to "help out" the exchange, by retransmitting the transaction, but with a fixed digital signature. They didn't need access to the wallets, they just removed the zero-padding, which allowed the transaction to go through, but with a different transaction id.

But, MtGox's software didn't like this at all. They sent a transaction, which failed, but someone fixed it, but on MtGox's end, they didn't know about the new transaction. The public ledger has the information that MtGox tried to send money from wallet A, to user B, and it is confirmed. MtGox should be able to see that "hey, these three BTC that I tried to send, but haven't been confirmed in transaction id 123... HAVE been confirmed, but in transaction id 456 instead!". They are either trusting transaction ids only, or ignoring the public ledger of the coins.

And... this causes chaos.

MtGox thinks that several (SEVERAL) transactions have failed, when in reality, they have succeeded. Transaction 1 is sent, trying to send 2 bitcoins, but fails due to the padded digital signature. Someone fixes the signature, so the transaction succeeds. Those 2 bitcoins are now spent, and arrived to their destination (often outside of MtGox's control). But, MtGox still believes they have them, and are trying to use them in future transactions, causing the transaction to fail, because the money has already been spent.

And this continued for months, before MtGox shut down all bitcoin transfers a few days ago. They have no idea which of their coins they still have, which are spent, which are sent where.

They have a whole lot of cleaning up to do. Matching transactions in the public ledger with their software (and finance books).

It's fully possible that there has been no malicious theft done, but it's also possible that someone has abused this ability to steal money from MtGox. How? User A tries to withdraw 10 bitcoin from MtGox. MtGox sends an invalid transaction (with padded zeroes). The transaction fails, but User A fixes the transaction. MtGox believes the transaction failed, when in actually succeeded. User A gets the withdrawal, but MtGox thinks it failed. User A can now re-try that withdrawal, getting another transaction, fixes that. Rinse and repeat. It's fully possible to completely drain their wallets.

And, other withdrawals will fail, because it tries to spend money that has already been spent. Increasing the backlog of transactions, customer complaints and problems.

MtGox decided to blame their issues on the bitcoin protocol itself, claiming this was a newly discovered issue, when it has in fact been known for a while. It's a horrible problem to have though, and it shouldn't have been possible from the beginning.

The problem we have identified is not limited to MtGox, and affects all transactions where Bitcoins are being sent to a third party. We believe that the changes required for addressing this issue will be positive over the long term for the whole community. As a result we took the necessary action of suspending bitcoin withdrawals until this technical issue has been resolved.

Bitstamp in the same boat

Bitstamp, another bitcoin exchange, currently the largest one, has also shut down their withdrawals, due to the same issue. And, I'm sure there are other implementations out there suffering from the same issues. There are also some reports of repeated floods of "duplicate" transactions on the network, just to cause havoc, or see who's vulnerable.

This is where we are today. MtGox have millions of dollars in seized assets, and an unknown amount of bitcoin lost or stolen due to their problematic bitcoin client. Will they survive at all? Will they make another internal transfer to prove they actually hold their users bitcoins? Or, should the tongue-in-cheek remark often heard that they should go back to trading cards instead perhaps be taken as a pretty good career advice?

Awesome Magic: The Gathering image by: Isma - http://www.imonfort.com/