Can a malicious majority miner rewrite history?

Question

Is it the case that a malicious miner with the majority of hash power (say, 99%) can perform a double-spending attack by rewriting history?

If so, I can't understand how. If not, under what circumstances is double-spending possible at all?

Consider the following simple assumptions:

1. A malicious miner M controls 99% of hash power
2. M does not control much "relay power" (e.g. it only operates a single node in the network)
3. The current legit blockchain (before the attack) is forkless, and consists of block B0,B1,...,B10, and 100% of the nodes in the network agree on that.
4. The attacker wants to void blocks B6-B10
5. The attacker mined alternative blocks B6' (on top of B5), B7', ..., B11'.

How can the attacker carry out the attack?

If he publishes B6' first, wouldn't all nodes reject it for being built on top of a block other than the last, thus preventing the attack?

If he publishes B11' first, wouldn't all nodes reject it for being built on top of an unknown block (not seeing B10' yet), thus preventing the attack?

Answer 1

Let's assume for a minute that your theory is true, and that actual nodes on the network would not accept this new, valid, and longer block chain.

That on itself would be a bug. Maybe it isn't obvious for a 5-block reorganization, but if it was a 2-block deep one (which actually occurs in practice), your argument would be equally true. If there was no means to accept a 2-block deep reorganization, nodes would be stuck in their shorter chain. This is actually exploitable too: someone may intentionally try to get you in such a state, as you will not see new payments on the chain that might conflict with a payment the attacker is trying to send you.

This is true for any depth of reorganization. If we don't accept 12-block deep reorganization, the network would remain in a very sore state if there would ever be a few-hour partitioning of the network. Being able to accept the longest valid chain under every condition is absolutely required for making Bitcoin converge.

So: we need a mechanism to reorganize pretty much any depth. How it is accomplished changed in Bitcoin Core 0.10 with the introduction of headers-first synchronization.

Before 0.10, the attacker would broadcast B11' first, which the victim doesn't know about. It will do a getblocks message to request the hashes of blocks between B5 (using a block locator) and B11'. When it receives these hashes, it will download them one by one using getdata, see they have a missing parent, place them in the orphan pool (the set of blocks without known parent), and when they're all received, notice that they connect, and switch to it.

Since 0.10, the attacker would inv B11'. The victim will use a getheaders message to request the block headers between B5 and B11' and getdata for the block B11' itself. When the headers arrive, they are validated on the fly (in order of increasing height, so they always connect). By the time B11' arrives, we already know about its parents, and know that (assuming the parents are valid) this will in fact be the new best chain. We will then start fetching the actual blocks B6' through B10' to fill in the gaps, and when they have all arrived, switch over to that chain.