Anatomy of a problem – Bitcoin loses 25% in value due to a long-missed bug

We’ve written several times about the controversial decentralised digital currency known as Bitcoin.

Bitcoin is an algorithmic currency, backed not by printed banknotes or government assurances, but by a database of cryptographic proofs-of-work.

That’s fancy talk for: find a block of data that produces a cryptographic hash with a specific bit pattern (this gets harder and harder as you lock more bits into the pattern); convince a majority of other participants you’ve come up wth a solution; and add the new proof-of-work into a blockchain.

The blockchain forms a cryptographic record of bitcoin creation and use.

Because each component in the blockchain depends on the hash of the previous one, you can’t go back and revise the bitcoin history:

We implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

A blockchain forms a sort of transaction log, and acts as a starting point for the next round of bitcoin mining.

The transaction log allows other players in the Bitcoin contest to verify your solution to the cryptographic puzzle (finding data that produces a hash with a specific number of leading zeros); once a majority of nodes in the Bitcoin scene accept that your solution came first, you’ve “mined” that coin, and it belongs to you.

Your new block is folded into the blockchain and everyone sets to work trying to solve the next cryptographic link in the chain, as depicted above.

“Winning” the next bitcoin in a chain means happening upon a bitstring, or nonce, that when combined with the data in the chain so far, produces a SHA-256 hash with a certain number of leading zeros. The probability of finding such a pattern by chance – and there is no better way known – is 1/2z, where z is the number of needed zero bits.

The Bitcoin protocol estimates the amount of CPU power currently in the Bitcoin mining network, and continually adjusts z so that, on average, one successful solution turns up every ten minutes. Each successful solution is currently worth 25 bitcoins; this halves every four years so as to limit the total number of bitcoins in circulation.

By 2140, each successful solution will be worth just 0.00000001 bitcoins; when this reward gets halved, it will effectively round down to zero, because bitcoins are denominated to eight decimal places, and no more bitcoins will be possible.

Ecosystem problems

Our previous articles describing problems with the Bitcoin ecosystem have all related to the services, known as exchanges, which trade real money into, and out of, bitcoins.

The biggest Bitcoin exchange, Mt. Gox, suffered a temporary meltdown in 2011 which saw the price of bitcoins plunge in minutes from $17 to about one cent.

The exchange operators decided to recover by pretending that the meltdown never happened, reversing the apparently-bogus trades and allowing the value of the “currency” to restore itself.

And in 2012, Bitcoin exchange Bitcoinica suffered not one but two digital breakins, leading to bitcoins (which are effectively just strings of data bytes) worth more than $300,000 being stolen.

Bitcoinica was then sued for nearly half-a-million dollars by disgruntled customers.

In 2012, Roman Shtylman, the operator of the Bitfloor exchange, ended up $250,000 out of pocket when he suffered a double-dose of bad luck.

Whils upgrading his servers, he decided to take the risk of making a temporary, unencrypted backup, which he kept online, just in case.

I’m sure you can guess what happened next.

→ Many of us will have committed this sort of security sin at some time, a problem for which there are three simple words: “Don’t do that.” Anything worth encrypting is worth encrypting always.

That’s just the moment that hackers – who probably didn’t believe their luck at first – got into his network, making off with a cool quarter-million’s worth of bitcoins he had in his possession.

Implementation problems

Yesterday, Bitcoin suffered another small setback, but of a different sort.

The side-effect was to force a brief but sudden devaluation of approximately 25% in the value of bitcoins, at least on the Mt. Gox exchange:

This reminds us that even algorithmic currencies backed by cryptography rather than fiat can suffer wild fluctuations in value.

This time, it wasn’t the surrounding ecosystem that turned out to have feet of clay, but the software behind Bitcoin itself.

It seems that version 0.7 of the Bitcoin mining software – the program that does the cryptographic guessing, and exchanges blockchains over its peer-to-peer network – had a fatal but unknown flaw.

This flaw was inherited from a database library module known as Oracle Berkeley DB that was used by Bitcoin coders until version 0.7; in version 0.8, they switched to a different database library, created by Google, known as LevelDB.

It turns out that a bug in Berkeley DB made it choke on blockchains bigger than a certain size; LevelDB, however, handled them just fine.

So a good, old-fashioned backwards incompatibility, albeit one that was caused by a flaw and thus terribly hard to predict, caught Bitcoiners on the hop.

Some of the ecosystem was willing to accept recently-minted bitcoins; some of it was not.

The stopgap solution, it seems, has been to persuade the community to commit to a temporary regression, and to:

• Run 0.8 software with artificial limits on the size of the blockchains it will tolerate, so it doesn’t make different decisions to the 0.7 version, or

• Downgrade to version 0.7 software.


This episode is an excellent reminder of one of computer science’s great ironies, namely that fixing bugs isn’t always the positive step you might hope.

In this case, switching to a more reliable database library made the 0.8 implementation more correct, yet annoyingly more fragile, simply because it wasn’t backwardly compatible with the 0.7 code.

It also reminds us how difficult it is to carry out a comprehensive code review on software that relies on third-party libraries, even if they are open source.

The moral of the story is: test, test and test again.