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

Filed Under: Denial of Service, Featured

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.

Conclusions

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.

, , , , , , ,

You might like

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

  1. Dr. Honked · 497 days ago

    MTGOX is an abbreviation of Magic The Gathering Online Exchange. It's not the name of a mountain!

    • Paul Ducklin · 497 days ago

      Er...I didn't say it was a mountain, just used the company's own orthographic style in writing the company name.

      Having said that...

      The company's own website writes its name "Mt. Gox," the company is registered in Japan, a notoriously mountainous country, and the corporate About Us page is dominated by a largish picture of a largish volcanic mountain.

      So it jolly well *is* a mountain now, no matter than it might have been an MTG site before :-)

  2. Daniel · 497 days ago

    Perhaps the article should mention Bitcoins are back to USD $47 one day. This article is dishonest journalism.

  3. Billiam · 496 days ago

    Umm.where has it decreased 25%? Because two weeks ago they were going for 30 usd per btc. Now they are nearly 50 usd.

  4. Mr Poontangle · 496 days ago

    FYI this caused a successful double-spend, which is supposed to never happen: https://bitcointalk.org/index.php?topic=152348.0

  5. donut · 496 days ago

    Misleading and sensationalist title. Change it to "Anatomy of a problem - Bitcoin dips 25% in value due to a long-missed bug", and it will become instantly better.

    • Paul Ducklin · 496 days ago

      I get your point (though my dictionary has "dip" meaning "to fall or set", like the sun does, as well as "to drop and rise again").

      Of course, the price dropped 3n and recovered by only about 2n, so you can argue that "dip" understates the situation as much as you can argue that "loses" overstates it.

      I'm going to leave it as "loses", if you don't mind...

      • Klober · 496 days ago

        I agree with donut and I do mind. Have you bothered to look at the value of Bitcoins today? The value is nearly identical to the value before the "loss". Your own words in the article were "brief but sudden devaluation" which sounds like a dip going by your dictionary definition of "to drop and rise again". "Loses" - as used in your title - indicates that Bitcoins lost the value and stayed at the lower value which is far from true.

        I read the Sophos Naked Security articles because they are usually well-written and informative. While this article is informative it bothers me that more opinion was introduced than necessary. It's quite obvious from the article that you don't have a very high opinion of Bitcoins. Having that opinion is fine but skewing your article towards that negative opinion is not.

        • Paul Ducklin · 496 days ago

          I suggest that it's not obvious from the article that I "don't have a very high opinion of bitcoins."

          (If you are interested in my opinion, you will find it elsewhere on this site, where I have written in strong favour of an international, distributed, anonymous digital currency - Bitcoin isn't quite anonymous, but it's close.)

          If I had wanted to mislead you, I wouldn't have used the words "small setback" (for what was actually a potentially catastrophic bug, you will have to admit) or "brief devaluation", I wouldn't have shown the Mt. Gox price graph beyond the drop, and I wouldn't have mentioned that the fix was in part due to "persuading the community" into pulling together.

          There you have it. I'm not going to change the headline. One of my colleagues might care to, but I'm not going to change it because you don't like the word "lost" being applied in the context of something that's later found again :-)

          [This thread will now close. Thanks.]

  6. Where are all the wild fluctuations everybody keeps talking about? There was one fairly large crash in 2011, and a couple minor blips since then, but Bitcoin recently seems MUCH tamer than most stocks and commodities. Looking at the 60-day chart, almost every day shows a slight increase with trading in a fairly narrow range, and that includes the non-event this article is about. There was a tiny decrease that day, with a corresponding increase the next.

    This is my all-time most boring investment. It just keeps going up and up. Of course, you won't see any articles about that, because they would be too BORING!

  7. Mike Rogers · 136 days ago

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

    Actually, as you alluded in a later article, it is more a case that ESPECIALLY algorithmic currencies backed by cryptography - and nothing else - can suffer wild fluctuations in value.

    I regard BitCoin as the digital equivalent of a penny stock certificate - it may make you rich, it may make you poor, but its value depends entirely on blind faith.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

About the author

Paul Ducklin is a passionate security proselytiser. (That's like an evangelist, but more so!) He lives and breathes computer security, and would be happy for you to do so, too. Paul won the inaugural AusCERT Director's Award for Individual Excellence in Computer Security in 2009. Follow him on Twitter: @duckblog