Mining of bitcoins
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 prescribed 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.
We need the Bitcoin community's help in deploying this fix so that the Bitcoin ecosystem can be made more robust, at least against attackers whose mining power is below the 25% threshold. Even with our fix deployed, however, there is a problem: there are mining pools at the moment that command more than 25% of the mining power, and, in the past, there have been mining pools that commanded more than 33% of the mining power. We need the Bitcoin community's awareness and concerted effort to ensure that no mining pool reaches these thresholds. The mere possibility that the system can get into a vulnerable state will be an impediment to greater adoption of Bitcoin.
Those of you who want a precise and full explanation of the attack can cut straight to the research paper, though it may be a bit terse and dry. In the rest of this blog entry, we will outline the attack for the non-hard-core practitioner, such that by the end of the blog entry, anyone should understand the intuition behind our attack, be equipped to earn higher revenues through mining, and possess the tools required to usurp the currency. To get to this point, we need a little bit of background on how Bitcoin works. If you're familiar with Bitcoin mining, you can skip to the next section that describes how the attack works. If you are a non-techie Bitcoin user, you can skip straight to the Implications section.
The Blockchain
The key idea behind Bitcoin's success is a decentralized protocol for maintaining a global ledger, called a blockchain. The blockchain records transactions between Bitcoin addresses, tracking the movement of every Bitcoin as it changes hands. This tracking ensures that no one can double-spend a coin, as the ledger makes it all too apparent whether a user sent out more Bitcoins from his account than he earned. The particular way in which Bitcoin tracking is performed makes sure that the record is also immutable; once a Bitcoin transaction is committed and buried in the blockchain, it is difficult for an attacker to reverse the transaction, so that a merchant can ship goods in good conscience, assured that the transaction will later not be reversed.
This protocol works through a process called mining. In essence, the ledger is organized into a single, ordered sequence of blocks, each of which records a set of transactions. Each block contains a crypto-puzzle, a computationally difficult challenge akin to a CAPTCHA. Miners organize themselves into a loosely-organized, distributed network, and they all concurrently try to add a new block to the ledger. To do this, they need to discover the solution to a crypto-puzzle, formed by the contents of the ledger until the point where the new block is being added. Solving a crypto-puzzle is hard work; a computer has to plug in many different values and see if they solve the crypto-puzzle posed by the new block. The puzzles are such that a home computer working alone will take many years to solve a crypto-puzzle. Some people use GPUs to speed up this process, while others have invested in custom ASICs designed to solve Bitcoin crypto-puzzles.
Of course, this process is not free, as the process of solving these crypto-puzzles consumes power and requires cooling. For the currency to be viable, the miners need to be compensated for their efforts. Bitcoin miners are compensated through two mechanisms: they collect the transaction fees from the transactions recorded in the new block they contributed to the block chain, and they also collect a lump sum fee. This lump sum fee creates new Bitcoins, according to a time-varying formula. Hence, "mining" is similar to digging for gold - every now and then, a miner is rewarded with a nugget. The difficulty of crypto-puzzles are automatically adjusted such that a new block is added to the ledger approximately every 10 minutes, which ensures a predictable coin generation rate for the system, which stems inflation and makes the currency supply more predictable than it would be otherwise.
The nice thing about having crypto-puzzles that are so difficult is that it is not practical for an attacker to modify the ledger. Someone who wants to, say, buy something from a Bitcoin merchant, get the goods shipped, and then later change that block to erase the transfer of money to the merchant, faces a very difficult task: they need to find alternative solutions to cryptopuzzles for that block and every subsequent block. What makes this difficult is that the main bulk of the miners will be working hard on adding new blocks at the tail end of the ledger, so an attacker, with limited resources, cannot hope to find alternative solutions for all the past blocks and catch up to the rest of the miners.
