andrewdroll.com

A Bitcoin monopoly

A new week brings new posts in my series on Bitcoin! Ottawa had amazing weather over the weekend, and I enjoyed it thoroughly with good company.

Last time I left off at the end of an introductory, detailed but still mostly qualitative, description of Bitcoin's mining protocols. I mentioned that an organization controlling a majority of the world's mining power could perform several serious attacks on the Bitcoin network, including forcing a monopoly on Bitcoin production and block chain updates. I also mentioned problems presented by majority mining, and perhaps more fundamentally, by its inherent incentive scheme, in terms of Bitcoin's larger originating vision of a crypto-currency secured by a massively distributed open model.

In this entry I intend to discuss some potential attacks by majority miners in more detail. This will require some broad discussion of how block chains stay synchronized - I still am not ready to dive too far into the network synchronization implementation.

I'll note that I'd meant to publish this entry earlier, and in fact it will be a relatively short one - however, expect more!

Which chain should I use?

When a miner completes a block, he broadcasts it to the rest of the Bitcoin network. Each node receives the broadcast, checks that the transactions in the block are not contradictory and that the proof-of-work solution is correct (by verifying that the nonce in the broadcast produces a correct solution), and then adds it to the end of their own copy of the block chain - mirrored on every computer across the world.

However, let us engage on a scientist's favorite adventure - a thought experiment: What happens if two miners finish the proof-of-work solution, and broadcast the completed block simultaneously? The complexity of proof-of-work problems makes this an unlikely situation. However, it's certainly one that will come very close to happening occasionally, and its probability increases as the number of mining processors increases.

So what happens? We hinted at the answer in the last blog. Each block will arrive at some nodes before the other one does because of differing network latencies. The first one to arrive at any given node will win, and that miner will get credit for the block from that node. Let's not worry about which miner gets new Bitcoins from successful completion of the block - that's not the point of this thought experiment. Instead, simply notice that the Bitcoin network will now be split - some nodes will have the block from one miner, and others will have the block from a different miner.

So far there is not too much problem in terms of network integrity, since the blocks from each miner are identical. However, this illustrates the possibility of "forking," where different Bitcoin nodes are storing different versions of the block chain. In less innocuous situations, forking can cause some big problems.

Here's one way that a less-harmless fork happened to occur:

Bitcoin's core software gets regular updates by developers. In March 2013, its software was updated to version 0.8 from version 0.7. Version 0.8 used a new database structure for block chain storage. In particular, version 0.7 used a database structure called BerkeleyDB, which had a maximum block size restriction of 512kb. Version 0.8 increased this restriction to 1MB, doubling it (the size restriction on blocks is a topic that may merit additional discussion in a future blog, as well).

So what happened? Eventually (on March 11), the 0.8 software put too many transactions into a single block - and miners running that block were working on a block larger than 512kb. Indeed, eventually a proof-of-work solution was found, and a block that was nearly 1MB in size got broadcasted.

This was fine with version 0.8 Bitcoin clients. They accepted the solution and added it to their block chains. However, a lot of machines were still running the 0.7 version of Bitcoin's software, and 0.7 could not accept this new block. Eventually a 0.7 miner found a solution to the block he was working on, smaller than 512kb (and containing fewer transactions), and broadcasted it. The 0.7 clients accepted this block.

This was a real fork (called a "hard" fork, because it was induced by software incompatibility), and it was unexpected. Suddenly there were two block chains - one on 0.7 clients, containing all 0.7-compatible blocks, and one on 0.8 clients, containing the new 0.8-compatible blocks. There were more 0.8 clients in the world, so the 0.8 chain grew faster - but the 0.7 clients were incapable of accepting it, and once the block chain is written, it is very difficult to change (to the point of practical impossibility after a few blocks, by intent). The fork threw turmoil through the Bitcoin community and required coordinated action to resolve.

The solution was to stop all mining on version 0.8, to advise merchants to stop accepting transactions temporarily (to prevent double-spending Bitcoins and other fraud), and to set all miners back to working on the 0.7 chain. After that, the Bitcoin world waited until the 0.7 caught up in length to the 0.8 chain.

Why was this a solution?

The answer is that Bitcoin clients automatically update to the longest chain available. Nodes broadcast the current status of their block chain mirror - in particular, how many blocks it contains. If a client discovers a new, valid chain with more blocks in it (that is, a longer chain), it assumes that the longer one is correct, because longer chains are more computationally demanding to compute than shorter ones. This is one of Bitcoin's major distributed security features, in fact. Because a single miner would have to build a longer chain than the rest of the network combined in order to introduce fraudulent transactions, it should be very difficult for anyone to gain malicious control over the global block chain.

So once the 0.7 chain surpassed the 0.8 chain in length once again, all 0.8 nodes synched back to the 0.7 chain. And in this way, the hard fork issue was resolved. However, this resulted in double-spending events and losses to merchants and users as a result - once the hard fork occurred, every Bitcoin suddenly had two copies in two effectively-different currencies. Double spending could occur by attempting to buy from two merchants, one running version 0.7 and one running version 0.8.

If a single miner gains more than 50% of worldwide mining power, they gain the ability to induce forks at will and manipulate the market in a number of ways. The next sections will begin investigating these.

Double-spending

We will now put ourselves in the shoes of a miner with more than 50% of global mining power, and engage in some new thought experiments to figure out what powers we might have.

One of the first things we can do is to double-spend our own Bitcoins. How can we do this?

Well, let's say we want to buy a lot of new mining hardware to extend our power farther. We can pay for our hardware with Bitcoins, broadcasting our transactions to the network, letting every miner in the world know about our purchase. We then wait. We let the transaction become completed, confirmed six times over the course of roughly two hours by the rest of the world's miners, so that our purchase is irreversible and the merchant feels comfortable sending us our new hardware.

In the background, though, our own mining hardware is quietly working away as well. And it isn't working on the same blocks as the rest of the world. On our hardware, we've excluded our purchase transaction. We simply haven't put it into our internal block chain. We've forced a fork, but we aren't revealing it to the world yet - we're working on our own chain on our servers, recording all of the world's transactions except for our hardware purchase, and we aren't broadcasting our new blocks when we find them or accepting completed blocks from the outside network. Nonetheless, our chain is growing faster than the other one - the one being computed by the rest of the Bitcoin network - because we have more than 50% of the computing power.

So, we wait until our hardware has been shipped - until our purchase is really, truly safe. Then we drop the veil and broadcast our private block chain to the world.

Since our chain is longer, every Bitcoin client recognizes it as more secure, and synchronizes to it automatically. The old main block chain that the rest of the world had been working on is erased, not recognized by any client because of its assumed inferior security. And those Bitcoins we spent? Well, we didn't include that transaction in our block chain. So now, it's as if it never happened. The merchant we bought hardware from - or perhaps another company, who accepted their Bitcoins, obtained from us, after the fact - is out of luck. Those Bitcoins are now back in our wallet, and out of theirs. And we're free to spend them again.

This example also illustrates how we can reverse our own transactions.

This is the first power granted to us by our >50% mining share. There are more of them, though. What's the next trick up our sleeve?

Preventing transactions

Being a monopoly, purchasing new hardware to maintain our competitive >50% mining edge (as in our last example), we want to make sure to leverage every tool that we can to deny our competitors the opportunity to catch up. What can we do to screw up their plans?

Well, maybe they're trying to make a purchase of hardware too - one that will allow them to cut our majority back to a healthier, sub-50% size. We're trying to exploit the system here - we can't be having that! Fortunately, we can stop them in their tracks, at least as long as they're also buying their hardware with Bitcoins.

How do we do that? Well, when they want to make their hardware purchase via Bitcoin, they must broadcast the transaction to the entire Bitcoin network, and we're the masters there. We can choose simply to filter out all transactions, or particular transactions - from our competitor, and not incorporate them into the blocks we're working on.

Since we have >50% of the mining share, it is likely we'll solve the block first and simply be able to prevent their transaction from ever being completed. We can be more devious than that though - just as in the previous example, we can work on our own private block chain, without their purchase, until we can be sure that ours will be longer than the external chain, then synchronize the wider network to deny the transaction. As long as we can get ahead (in terms of length of our internal chain) fast enough - say, within an hour or two, or 6-12 blocks - we will be able to prevent our competitor's transaction from being confirmed by the vendor. Thus we can deny them the opportunity to ever buy their hardware successfully using Bitcoin currency.

This strategy isn't limited to competitors. We can deny any transaction by anyone on the Bitcoin network for as long as we like, assuming we maintain our >50% mining share.

Our powers still don't stop here, though.

Masters of the (Bitcoin) universe

This is our final evolution as majority miners in the Bitcoin world, and it's a big one. Indeed, with a majority, we can claim 100% share of all Bitcoins produced. Restated, this means that having more than 50% of the mining power means that you can ensure that you effectively do 100% of successful mining, and reap 100% of the rewards, if you so desire. Thus >50% mining power may translate to a mining monopoly for a malicious organization, at least until the wider Bitcoin community were to respond by modifying the protocol to deny the attack. In any case, the aftermath of such a situation would seem likely to shatter confidence in the currency, cause great harm to users and merchants, and result in a wide dramatic reduction in the valuation of Bitcoins.

How would we achieve a monopoly holding only slightly more than 50% of the mining power? The answer relies on the same old tricks.

Again, we start by mining our own private block chain - filtering out successful block solutions from outside and not broadcasting our solutions to the broader network. We don't need to filter any transactions, although we may, if we wish to cause other harm. Instead we simply work on our own chain, where we are solving every block. We do this faster than the outside network builds their chain since we have more computing power than the rest of the network combined.

After a long enough time, our internal chain will necessarily end up longer than the outside chain. Here, "a long enough time" is not very long - we should expect it to be no more than a few hours. And so after a few hours, we broadcast our internal, longer, chain to the world. Suddenly all the Bitcoins earned by outside miners during that time disappear, because their solutions have been removed from the chain. We are now the miner who has solved every block for the last several hours, and all of the resulting coins are in our wallet.

Now, of course, once we have broadcasted our chain, external miners will start working on the next block to continue developing it. Perhaps an external miner will solve it first, and earn Bitcoins for their solution. We are free to repeat the pattern described above, though, to erase those Bitcoin gains a few hours later and claim them for ourselves. In this way we can achieve a complete monopoly over mining, and over Bitcoin production, with only slightly more than a 50% proportion of computational power.

What are the limits?

Despite a majority miner's considerable potential to attack the Bitcoin network or to introduce fraudulent transactions, there are some things that would remain impossible or impractical.

One of these is performing transactions for other users. We have yet to examine the Bitcoin transaction protocol in these blogs, but every Bitcoin transaction is digitally signed using a private key unknown to anyone but the sender. Digital signing is a cryptographic mechanism that makes it possible for anyone to verify that the transaction comes from the sender, while making it effectively impossible to impersonate a sender unless you possess their private key. We will discuss the details of digital signatures in an upcoming blog on transaction protocols, but for now, we will simply note that even a majority miner would be unable to spend another user's Bitcoins - the wider network would immediately reject any block (or any new block chain) containing a transaction without a valid digital signature.

So: Majority miners cannot force transactions with other users' Bitcoins.

Another limit is in terms of modifying the larger history of transactions. In theory, based on our discussion so far, a majority miner could go back to any point in the block chain, remove some transactions (or add some transactions with their own Bitcoins), and recalculate the rest of the chain up to the present point in time, catching up with the wider network's version eventually by virtue of superior computational power. They could even re-write all of Bitcoin's transaction history, worldwide! Fortunately, there are mechanisms in place to prevent this, called checkpoints. The Bitcoin checkpoint system is an additional security measure to ensure that historical blocks are impossible to re-write past a reasonable point. Every several thousand blocks, on Bitcoin client version updates, a checkpoint is introduced to the base Bitcoin client code in the form of a record of the cryptographic hash of the latest block, along with the block's height (that is, its place in the chain).

If anyone wishes to re-write the Bitcoin block chain history past the last checkpoint, they must compute a block, at the same height as the checkpoint, with an identical SHA-256 hash and matching their alternate transaction history. This is an effectively impossible computational problem with current technology. If the checkpoint hash does not match that hard-coded into the Bitcoin software, the alternate block chain will not be accepted. Thus checkpoints effectively hard-lock the block chain history prior to the last few hundred or few thousand blocks.

Thus majority miners' control over the block chain's history is controlled by checkpoints in the Bitcoin client code.

Finally, it is certainly worth noting that due to Bitcoin's transparent nature, all of these types of attacks would be available for easy detection by the wider community. A response could involve modifying the Bitcoin protocol to induce a hard fork away from the malicious entity. Nevertheless, >50% attacks would cause havoc in the Bitcoin world. The recent emergence of >50% miners should certainly be a fact worthy of concern for anyone interested in investing in the currency, or in accepting it as payment. Moreover, it should be a concern for Bitcoin developers, both in terms of maintaining Bitcoin's distributed vision, and in terms of the practical venture of keeping investor confidence in Bitcoin as a currency.

Why a majority?

The abuses possible for majority miners which we have discussed here all rely on forking the block chain intentionally, and writing a longer internal chain in order to eventually subvert that being computed by the broader Bitcoin network. Of course, any miner could decide to filter completed blocks from the outside, filter certain transactions, or reverse their own transactions on an internal fork.

The key factor for majority miners is that they can compute blocks on their internal fork faster than the outer network can on theirs. Thus a majority miner can replace the global block chain at will. A miner without >50% of the power share could attempt the same forking strategy, but in the long run, their fork would not build as fast as the wider network's - unless perhaps another attacker were attempting the same feat at the same time.

Remark also that this strategy relies on the fact that proof-of-work difficulty only updates in the Bitcoin protocol approximately once every two weeks. Thus, if a miner chooses to start an internal fork, both they and the external network will continue computing at the same difficulty until the next update, giving the superior hardware of the majority miner an edge at block completion.

Next time

As I mentioned earlier, this is a shorter and less-technical blog than my last entry. Here we have discussed the broader view of what sorts of attacks are possible by majority miners, and how they could be carried out. There are additional attacks that could be made, and I may return to them in a future blog. One question which I will certainly discuss soon is: What can a miner with less than 50%, but still with a significant proportion of mining power do to affect the network negatively if they so desire? Can you get more than your fair share of mining profits even with less than 50% of the power?

There are several other points I will address in my next few entries as well. Most of all, I am excited to jump into more details of the transaction and network synchronization protocols.

That's it for today!