|Flaw In Bitcoin Algorithm|
|Written by Mike James|
|Wednesday, 06 November 2013|
Most security analysts don't regard the Bitcoin algorithm as particularly sophisticated, but until a new paper was published there was no explicit flaw. However, the problem that has been uncovered is more to do with game theory than cryptography.
The basic Bitcoin algorithm may not be sophisticated, but it is very clever and well constructed. The problem it solves is to allow the non-central administration of a currency. It does this by using a "proof of work" algorithm to ensure that just one server authenticates a block of transactions.
What happens is that when a transaction block is published Bitcoin miners, who run the authentication servers, pick up the block and try to solve the cryptographic problem it contains. The first one to do so gets a reward of some newly-minted Bitcoins, and perhaps even a transaction fee.
Because of the competitive nature of the task, the server that gets to authenticate the block is more-or-less chosen at random.This makes it very difficult to implement a dishonest transaction because it isn't possible to orchestrate the making of a transaction with the authenticating of a transaction so that the same agent involved in both. The idea is that as long as the majority of miners are honest then the Bitcoin block chain, i.e. the history of all Bitcoin transactions, remains true, irrevocable and trustworthy.
This, however, all depends on the majority of miners not only being honest, but not having a reason to be dishonest.
In other words, a miner makes more by competing rather than co-operating with other miners.
Now in a new paper, Ittay Eyal and Emin Gun Sirer of Cornell have noticed that there is a strategy whereby a group of miners can receive more Bitcoins if they work together.
Currently miners do organize themselves into pools but these are more like betting syndicates. The miners simply agree to work together and share the Bitcoins that they earn. This smooths out the statistical fluctuations in a miner's earnings.
However, if any pool notices that there is an advantage to be had from deviating from the standard behavior then the system falls apart - and this is what the researchers have found. The profitable deviation isn't obvious, but it is easy to implement. When a miner finds the solution to a block the idea is that this is announced at once. This is noticed by the other miners who then move on to the next block and regard the previously current block as solved. Now consider what happens if a mining pool decides not to announce that it has solved a block. That pool is the only group of miners that knows to move on to the next block. The other, honest, miners waste their time trying to solve a block that has already been solved.
Of course, at some point the honest miners solve the block, but the dishonest miners simply publish their longer extension to the block chain, which will be accepted with a reasonable probability. The honest miners get nothing and the dishonest miners get all of the newly-minted Bitcoins from their previously secret chain. This algorithm can be repeated and any miner offered a chance to join such a pool has nothing to lose and everything to gain. Dishonesty gets you more Bitcoins with no penalty.
The fact that the block chain is now built up in this new way has no real disadvantage. There is nothing particularly threatening to Bitcoin from the dishonest miners' behavior. The problem is that once the behavior is established the control of Bitcoin authentication will end up in the hands of a small number of mining pools. This is no longer a distributed currency, but a centrally administered one. Any such mining pool could choose to take a step further and manipulate the block chain for its own additional profit.
The paper explains that for the Bitcoin system to be safe it isn't good enough that just a majority of miners are honest.
This flaw is also present in all currencies derived from the Bitcoin algorithm, including Litecoin and Namecoin.
The only option is to modify the Bitcoin algorithm and this is what the researchers propose. The probability that the dishonest miner's new chain will be accepted depends on the way a forked chain, that is a chain with two proposed solutions, is handled. At the moment what happens is that the shortest branch is ignored (corresponding to gamma=1 in the chart above). Normally branching doesn't occur very often, but if a dishonest pool is at work it would become much more common.
The suggested change is to allow miners to select the branch to work on with a probability of 0.5, so reducing the chance the the dishonest branch is established. However, this simply increases the size of the dishonest pool needed to make a profit to 25% of the total number of miners. What this means is that, even after the fix, 75% of the miners have to honest for Bitcoin to be reasonably safe. As the paper points out, there is a pool that commands 25% of the mining resources at this time and in the past there have been pools of more than 33%.
The threat to Bitcoin isn't cryptographic, but the fact that a strategy exists that allows bigger profits by working as a group. This produces a pressure to centralize mining operations and this in turn is the destabilising event.
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin, or sign up for our weekly newsletter.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Wednesday, 06 November 2013 )|