In what should be one of the greatest and weirdest pivots of all time, Jed McCaleb transformed Mt. Gox (short for Magic: The Gathering Online Exchange) from a card-trading platform into what became the world’s one-time leading Bitcoin exchange.
Not wanting the legal hassle of operating a crypto-currency exchange, McCaleb sold Mt. Gox to a few Tokyo-based French entrepreneurs he had never met before in 2011. They presided over Mt. Gox as it went on to dominate Bitcoin trading for more than a year by volume. However, over the past six months, the platform has seen a fall from grace as users have had trouble withdrawing their funds. New troubles emerged in the last couple days again, as Mt. Gox said it was halting withdrawals. The company said it was having problems finalizing transactions because of a perceived flaw in the Bitcoin protocol around “transaction malleability.” Other exchanges also halted withdrawals as the Bitcoin Foundation said it was working on a solution to the problem.
In any case, McCaleb has been free of Mt. Gox’s troubles for years.
Now he’s back at work on a new project. And here it is at the mysterious address of secretbitcoinproject.com.
It has just this short message:
When I sold Mt. Gox a few years ago, Bitcoin was trading at less than a dollar. Today Bitcoin exists in a new environment. Mt. Gox is struggling to keep up. Now, I am building something that will be better for Bitcoin and better for you.
I’m looking for alpha testers.
-Jed
We also hear from a source that he’s raised some funding solely through some instant messages and Skype. (McCaleb is a bit reclusive.)
なぜマウントゴックスが破たんしたのか、まだ理由が明らかになっていません。ビットコインについては、マネーロンダリングに利用されたり、投機の対象になったり、開発された当初に比べると毀誉褒貶著しいわけで、ロシアや中国では禁止され、マウントゴックスもすでに2013年春頃には米国政府が問題にしています。同年4月のビットコイン暴落時には一時的に取引停止している。今回の被害額は数百億円、同システムの利用者は世界中で100万人、という話もあるんだが、東京渋谷に拠点を置いている、ということで日本にも無関係ではありません。ちなみにマウントゴックスの社名は「Magic: The Gathering Online Exchange」の頭文字を並べたものです。
マケーレブ氏は、米国カリフォルニア大学バークレー校を中途退学した後、2009年にカード取引ゲーム「Magic: The Gathering （マジック:ザ・ギャザリング）」のオンライン取引所を立ち上げ、2010年7月からマウントゴックスとしてビットコインの取引所の運営を始めました。しかし、2011年3月にマルク・カルプレス氏の「ティバン」という資本金500万円の企業に売却しています。マケーレブ氏がマウントゴックスを売却した理由は、ビットコインに減滅したから、と言われている。彼は2011年頃から同システムの欠陥を指摘していました。
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 $ 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?
Secret Bitcoin Project – Come see.
http://alphatesters.secretbitcoinproject.com/
Mt. Gox’s Original Creator Is At Work On A Secret Bitcoin Project
by Kim-Mai Cutler
http://techcrunch.com/2014/02/12/jed-mccaleb/
In what should be one of the greatest and weirdest pivots of all time, Jed McCaleb transformed Mt. Gox (short for Magic: The Gathering Online Exchange) from a card-trading platform into what became the world’s one-time leading Bitcoin exchange.
Not wanting the legal hassle of operating a crypto-currency exchange, McCaleb sold Mt. Gox to a few Tokyo-based French entrepreneurs he had never met before in 2011. They presided over Mt. Gox as it went on to dominate Bitcoin trading for more than a year by volume. However, over the past six months, the platform has seen a fall from grace as users have had trouble withdrawing their funds. New troubles emerged in the last couple days again, as Mt. Gox said it was halting withdrawals. The company said it was having problems finalizing transactions because of a perceived flaw in the Bitcoin protocol around “transaction malleability.” Other exchanges also halted withdrawals as the Bitcoin Foundation said it was working on a solution to the problem.
In any case, McCaleb has been free of Mt. Gox’s troubles for years.
Now he’s back at work on a new project. And here it is at the mysterious address of secretbitcoinproject.com.
It has just this short message:
We also hear from a source that he’s raised some funding solely through some instant messages and Skype. (McCaleb is a bit reclusive.)
今日のリンク
ビットコイン騒動の重要人物とは
アゴラ編集部
http://agora-web.jp/archives/1583987.html
NHKや日経あたりが「売り込んで」きたビットコイン（Bitcoin）周辺が世界中で大騒ぎです。半年前まで世界最大のビットコイン取引所だった「マウントゴックス（Mt.Gox）」が破たん。交換はもちろん預け入れていたビットコインの引き出し、担当者との連絡さえできない状況に陥っている。グローバル化した自由主義経済のデジタル技術を駆使した究極の「通貨」という触れ込みなんだが、国家が発行する通貨を否定する交換手段、というわりに既存通貨との交換取引所が必要、という「矛盾」が顕わに浮かび上がっています。
このビットコイン、いったい何なのか、どこで手に入れることができるかもわからない、という人がほとんどでしょう。昨日夜のNHKニュースでは、ビットコインで支払い可能な六本木の飲食店のオーナーを紹介していたんだが、クレジットカードの代わりにビットコインを受け付けていたらしい。ビットコインについてはアゴラでも大石哲之氏の論考に詳しいので読んでみてください。
なぜマウントゴックスが破たんしたのか、まだ理由が明らかになっていません。ビットコインについては、マネーロンダリングに利用されたり、投機の対象になったり、開発された当初に比べると毀誉褒貶著しいわけで、ロシアや中国では禁止され、マウントゴックスもすでに2013年春頃には米国政府が問題にしています。同年4月のビットコイン暴落時には一時的に取引停止している。今回の被害額は数百億円、同システムの利用者は世界中で100万人、という話もあるんだが、東京渋谷に拠点を置いている、ということで日本にも無関係ではありません。ちなみにマウントゴックスの社名は「Magic: The Gathering Online Exchange」の頭文字を並べたものです。
ビットコインの「創始者」は、当時37歳の匿名日本人数学者、と言われています。とりあえず名前は「Satoshi Nakamoto」というらしい。2008年にビットコインのシステムを作り、当初は声明を出したりネット上に足跡が残されていたり、現実の世界にいたようなんだが、2011年頃から消息不明になっている。この人物を特定するために、これまでいろんなウワサが流され、個人ではなく集団なのではないか、英語の特徴からオーストラリアや南アフリカなど、英国連邦出身者なのではないか、ネット上の投稿時間から北米もしくは中南米在住なのではないか、など様々に取り沙汰されています。
発行の上限があらかじめ決められているビットコインは、最初に作ったり初期に投資して大量のビットコインを所持している者が、システムが認知され、広がり使用者が増えるにつれて莫大なリターンを得ることができます。この匿名の日本人数学者もしくは団体は、現在、ビットコインの創業者利益として10億ドル相当の利益を得ている、と言われている。一説によれば、この創始者はマウントゴックスを立ち上げたジェド・マケーレブ（Jed McCaleb）氏その人なのではないか、という話もあります。
マケーレブ氏は、米国カリフォルニア大学バークレー校を中途退学した後、2009年にカード取引ゲーム「Magic: The Gathering （マジック:ザ・ギャザリング）」のオンライン取引所を立ち上げ、2010年7月からマウントゴックスとしてビットコインの取引所の運営を始めました。しかし、2011年3月にマルク・カルプレス氏の「ティバン」という資本金500万円の企業に売却しています。マケーレブ氏がマウントゴックスを売却した理由は、ビットコインに減滅したから、と言われている。彼は2011年頃から同システムの欠陥を指摘していました。
マケーレブ氏は現在「ripple」という、また別の仮想通貨システムを構築し、ビットコインのライバルになっています。ビットコインと同じく発行上限が決められ、違いは価値をドルなどで保障することのようです。また、迅速な取り引きが可能なのもメリットらしい。rippleにとってライバルのビットコインの信用失墜は喜ぶべきことでしょう。ひょっとすると、今回の騒動の裏にはマケーレブ氏がいるのかもしれません。
THE TROUBLESOME HISTORY OF THE BITCOIN EXCHANGE MTGOX
https://anders.io/the-troublesome-history-of-the-bitcoin-exchange-mtgox/
by Jason Benjamin
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.
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:
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.
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 $ 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.
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?