Bitcoin Is BrokenSubmitted by Apple on Wed, 11/06/2013 - 10:23
Bitcoin is broken. And not just superficially so, but fundamentally, at the core protocol level. We're not talking about a simple buffer overflow here, or even a badly designed API that can be easily patched; instead, the problem is intrinsic to the entire way Bitcoin works. All other cryptocurrencies and schemes based on the same Bitcoin idea, including Litecoin, Namecoin, and any of the other few dozen Bitcoin-inspired currencies, are broken as well.
Specifically, in a paper we placed on arXiv, Ittay Eyal and I outline an attack by which a minority group of miners can obtain revenues in excess of their fair share, and grow in number until they reach a majority. When this point is reached, the Bitcoin value-proposition collapses: the currency comes under the control of a single entity; it is no longer decentralized; the controlling entity can determine who participates in mining and which transactions are committed, and can even roll back transactions at will. This snowball scenario does not require an ill-intentioned Bond-style villain to launch; it can take place as the collaborative result of people trying to earn a bit more money for their mining efforts.
Conventional wisdom has long asserted that Bitcoin is secure against groups of colluding miners as long as the majority of the miners are honest (by honest, we mean that they dutifully obey the protocol as proscribed by pseudonymous Nakamoto). Our work shows that this assertion is wrong. We show that, at the moment, any group of nodes employing our attack will succeed in earning an income above their fair share. We also show a new bound that invalidates the honest majority claim: under the best of circumstances, at least 2/3rds of the participating nodes have to be honest to protect against our attack. But achieving this 2/3 bound is going to be difficult in practice. We outline a practical fix to the protocol that is easy to deploy and will guard against the attack as long as 3/4ths of the miners are honest.