The Bitcoin Eternal Choice for the Dark Side Attack (ECDSA)

Warning: This post is a mere speculation. There are many unknowns that may change the ending of this story, but nevertheless, an attack like this, that tries to divide the Bitcoin community, undermining the moral of each user, sounds quite probable to me. But I love Bitcoin, I’m optimistic and I wish Bitcoin a great future.

The 51% attack is probably to costly and to risky to be performed for profit. Currently it requires the attacker to invest (buy) around 5M USD in ASIC mining boxes. This have been widely discussed (e.g. here).. There are nevertheless fewer posts analyzing on the impact of an 51% attack performed to destroy Bitcoin (e.g. here). The most simple idea is to use 51% of the hashing power to paralyze Bitcoin: just creating empty blocks. But it turns out that this attack can be defeated by comparing branches not only using the PoW, but using the age of the coins transacted.

I will describe an attack that could destroy Bitcoin, starting with less resources, such as 15% of the hashing power, with high probability of success, so then the attacker has a chance to increase the resources gradually as the attack proves to be working. I’ve call it the Eternal Choice for the Dark Side Attack (ECDSA), so that it doesn’t clash with some other attack name in the literature. It may work, and may be carried anonymously. The idea is that, with 15% of the hashing power, the attacker has approximately a 1:1000 chance of creating a branch of 8 blocks in a row himself faster than the main branch. So every 7 days, on average, the attacker gets a chance to revert transactions that most people think they are sufficiently confirmed. So far, nothing new.

Now imagine that the attacker never broadcasts the blocks he mines, keeping them private. The attacker includes in his blocks some percentage of the transaction he sees in the network, such as 10%, to thwart a coin-age distinguisher algorithms. Every time he mines 7 blocks in a row faster than the honest chain, he anonymously publishes the block headers (as proof) in some public board such as bitcointalk, but he does not publish the transactions referred by the Merkle root. He also hacks some computer X somewhere and runs a special version of bitcoind that only accepts double-spends (not new transactions, nor previous transactions). Then he advertises a “service” to allow people to double-spend the past transactions, which would only require people to send the double-spend transactions to X, including a fee of 10% of the transaction output value (the 10% fee is just a diversion to let people think it’s some kind of dark business). Since the attacker has 15% of the hashing power, he can succeed creating a new block with the double-spends collected with probability 1/6.6.

What people would do? If they are honest, they will not use the double-spend service. If they are not, they may be tempted to do so. Suppose 10% of the people try double-spending. After the first successful attack , some victims will complain as having been cheated. Rumors will  spread regarding the current insecurity of the network. The price will fluctuate, but will stabilize. Seven days later, the same announce is made, publishing the 6 block header branch. This time the market will react before the attack is even made. Bitcoin price will certainly decrease, even if afterwards the attack is unsuccessful.  In forums, people are advised not to accept 6 confirmations, but 10. Now the attacker increases his resources to 20% of the network hashing power. Seven days later, the announce is made again, showing 10 block headers. This time 20% of the people opt for cheating. More fraud victims appear. Now more fear spreads.  Bitcoin price drops substantially. Miners fail to prevent the attack by including the original transactions in blocks mined after the attacker branch because some of the transactions were actually included in the attackers branch, but which ones is unknown until the attack is performed. Core developers try to implement a patch for the satoshi client to distinguish between the attacker branches and the “honest” branches, by inspecting the maturity of the coins transferred. But since the attacker branch also contains some percentage of valid transactions, the distinction is risky and the patch also introduces the possibility of wrongly switching to a parallel branch with less PoW. The attacker manages to fool the patch. Some honest miners leave Bitcoin mining business temporarily with dubts. The attacker now sees an increase of its hashing share to 30% of network hashing power. He begins to accept double-spends before actually performing the attack, so cheaters can gamble at SatoshiDice and have their bets reversed when they loose, with 1/3 of cheating probability. SatoshiDice closes temporarily. Cheaters find other online sites to abuse. The Core dev team tries to implement a checkpoint system to manually distinguish between branches every week, but there is no consensus on who should take the decision of which is the right branch. There is a warm debate in the forums. Time to decide for the Core dev team is running out. The same eternal choice of cheating or not comes over and over, as attacker announcements are made too often, like Darth Sidious seducing Anakin to go the dark side.  The attacker increases his power to 40%. . The offer is more tempting, so more people try to cheat.  Bitcointalk heros tell people to accept only transactions with 20 confirmations. The usefulness of Bitcoin is in danger. Bitcoin price decreases. The attacker is advertising the reversal of transaction every hour, with a 50% success probability.  Honest people stop transacting using Bitcoin preventively. The price drops, and drops again. Cheaters start to automate cheating using bots, and withdraw funds as fast as they can.  The price collapses.

The attackers laughs, and then an order to dispose 1M USD in custom ASIC chips arrives, not before  100 additional employees are hired and given hammers in order to smash each chip 7 times, in some secret office at a secret headquarters of a secret department of some secretive state.

Solution

(this section has been edited twice!)

At the time I wrote the post I had no clue of how to solve the problem.  My only relief was the hope that there are more honest people in the world than dishonest ones. But after 4 hours of bad sleep I realized that the key is taking pro-active measures. There is little that can be done well under the pressure of an attack. So my idea is to add the Satoshi client a “Safe Mode”. In Safe Mode, transactions are only considered confirmed if they have 144 blocks of confirmation (1 day). Also in Safe Mode, the clients do not accept any chain reorganization of length greater than 144 blocks (this is the key restriction).  One day has been proven to be enough for the core dev team to resolve chain forking situations, and still it is short enough to let people transact almost as normal. Only services that require fast confirmation will have to pause their operations, or accept payments of low value with the implicit risk. Safe Mode could be announced by using the network alert system, either by making clients automatically switch to this mode or by requiring the user confirmation. Safe Mode alerts would have a finalization date, as other alerts. Also Safe Mode would be immediately terminated by the “Alert key compromised” alert.

This solution is very simple to implement (maybe 5 lines of code), and yet provides an incredible increased level of protection against attacks that attempt Bitcoin destruction. I has to be there so it never needs to be used. The bad news is that is not a solution at all (see my second edit) if some other protective measures are not taken.

(second edit)

This solution alone does not work, as Gregory Maxwell explains nicely in this text:

For example, some of the most common proposals in this space is simply to refuse to make reorganizations over some size X. But this means an attacker who can produce X+1 blocks can do a simultaneous announce to half the network of one fork while giving the other half one more block. Everyone locks in and the network is forever split.  If you assume that an attacker couldn’t make an X block reorg, then the “protection” was pointless in the first place.

The additional protective measure would be that any chain reorg of n blocks is delayed n seconds.  During that wait period, if another better chain reorg is received, is processed in the same way. After one period expires, the chain reorg is applied, and a new best chain is created. If a block that extends a waiting chain is received, then the waiting lapse is restarted from zero for that chain. If a node receives a 144 length branch in a very short period of time, it will wait 144 seconds to actually apply the reorganization, so if the network is not split, that gives plenty of time to exchange all other chains in existence and choose the best.  If a node receives two 143 block competing branches in a short period of time, then any attempt to extend both chains at the same time will result in both staying in a waiting state for 144 seconds more. A chain of 144 blocks won’t accept any additional extension (the max is 144) so the attacker cannot keep playing this game forever.

 

So after talking with Gavin, my last thought is this:

If someone wants to do something illegal, is not afraid to be caught,  and waste 50M USD, in order to destroy Bitcoin, he would partially succeed. He will not destroy it completely, but he would erode so much the confidence on the system that the bitcoin price will fall to almost zero. And I unsure if a democratic government can sustain committing a crime indefinitely without people protesting.

Advertisements

, ,

  1. #1 by gwern on June 26, 2013 - 2:52 pm

    This seems to depend very heavily on miners having extreme elasticity in response to attacks. Why would they? Wouldn’t the real scenario go like this: “week 1: after burning a ton of money to produce the altchain, the attacker advertises and gets some takers, who make a decent chunk of money in unpaid-for services; week 2: the attacker fails because everyone shrugged and increased confirmations by n; week 3: the attacker fails and having run out of money, goes bankrupt; week 4: the price of Bitcoin goes permanently up after having weathered a real attak, more miners join due to the increased value of the reward, and Bitcoin is permanently more secure’?

    • #2 by SDLerner on June 26, 2013 - 5:33 pm

      That could be a happy ending. The chaotic point is at week 2, if fear wins, then the attacker wins. If not, then the community wins. There is also the uncertainty of the amount of resources available to the attacker, so people will not be certain on how many confirmations to accept, and what the extent of the attack is. As Darth Vader could have said: fear leads to runs to the coin, and runs strengthens the dark side of the network hashing power.

      • #3 by gwern on June 26, 2013 - 6:39 pm

        > There is also the uncertainty of the amount of resources available to the attacker, so people will not be certain on how many confirmations to accept, and what the extent of the attack is.

        And why would there be any uncertainty? The longer the fork, the more damaging it is and the more powerful – and also likely to reach the minimum block count to do a double-spend at all – an attacker is and the more likely their attack to succeed. They don’t have any incentive to say ‘well, we only mined 6 blocks but we *could* have mined 8 if we wanted to’.

  2. #4 by SDLerner on June 26, 2013 - 7:14 pm

    In response to #3 by Gwern: The idea is that if the attacker creates a 100-block fork, then it will be easy to spot and ignore with an on-the-fly checkpoint. My attacker uses a guerrilla style approach, trying to tempt people into accepting his fork with double-spends, and making it difficult to distinguish it from the honest branch (and by forcing the core devs to create checkpoints, or miners to manually inspect the block-chain, at a very fast rate). This brings me to another subject: maybe the best way an attacker can destroy a peer to peer network is by using another peer to peer network: the minds of the humans in charge.

  3. #5 by Gavin Andresen on June 27, 2013 - 2:24 pm

    That is a long chain of “what ifs” :

    what if
    … a rich, motivated, willing to lose millions of dollars attacker wants to destroy bitcoin
    … and they get a significant fraction of hashing power
    … and hire the technical expertise
    … and they’re willing to solicit fraud (break the law in most countries I know about)
    … and they manage to find people who just happened to have a transaction in the right block at the right time who are also willing to commit fraud (break the law)
    … and they manage to double-spend at a high enough level to shake confidence in the whole Bitcoin system

    That all seems extremely unlikely to me. Even if it does happen, the victims of the double spend should have a good case to take to court; there are non-technical remedies to most double-spend situations (if you’re in a situation where you’re delivering high-value goods to somebody unknown in exchange for bitcoin… well maybe you should require 144 confirmations before delivery, but most honest merchants are not in that situation).


    Gavin Andresen

    • #6 by reply on August 12, 2013 - 3:19 pm

      what if the NSA is
      … a rich, motivated, willing to lose millions of dollars attacker wants to destroy bitcoin
      … and they get a significant fraction of hashing power
      … and hire the technical expertise
      … and they’re willing to solicit fraud (break the law in most countries I know about)
      … and they manage to find people who just happened to have a transaction in the right block at the right time who are also willing to commit fraud (break the law)
      … and they manage to double-spend at a high enough level to shake confidence in the whole Bitcoin system

      yes, completly out of the blue…

      • #7 by Craig S Wright on December 10, 2014 - 6:01 am

        “… a rich, motivated, willing to lose millions of dollars attacker wants to destroy bitcoin”

        Then they will lose all they have. A rich motivated supporter could choose to start mining and intervening at a point where this would make a difference.

        http://www.top500.org/site/50547

  4. #8 by Albitos on September 3, 2013 - 4:27 pm

    > And I unsure if a democratic government can sustain committing a crime indefinitely without people protesting.

    Look at what USA is doing these days…

  5. #9 by Anonymous on September 12, 2013 - 10:32 am

    The only ones with that much resources and intent to destroy bitcoin would be governments, and governments have a much easier method to destroy bitcoin – legislation.

  6. #10 by Jeff R. Allen on November 26, 2013 - 1:40 pm

    > And I unsure if a democratic government can sustain committing a
    > crime indefinitely without people protesting

    This must be a joke, right? Have you not read The Guardian this year? 🙂

    -jeff

  7. #11 by Craig S Wright on December 9, 2014 - 7:17 am

    Your math is off.

    The following is wrong.
    “the attacker has approximately a 1:1000 chance of creating a branch of 8 blocks in a row himself faster than the main branch”.

    Random does not make linear.
    Independent vs conditional.

    The solution is fine, but the calculation is not.

    There are also those with the ability to hash who chose when to mine. That is, if such an attack came about could impose other constraints. Not only attackers have compute power at hand.

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

%d bloggers like this: