Denial of Service using orphan blocks?

[patvarilly]

Reading through the bitcoin client sources, I can't find any limit on the number of orphan blocks kept in memory by a client, and I wanted to confirm if this is true.  The reason this seems odd is that someone could bring down any Bitcoin client of their choosing by connecting to them and pushing a constant stream of fake, large, difficulty-1 orphan blocks.  These never get discarded because it's in principle possible that such blocks live at the tip of a higher-aggregate-difficulty chain than the main chain (with a catastrophic collapse in difficulty at some unseen point between a putative fork and the orphan block).  At some point, the client's memory is exhausted.  With the rates at which people can hash these days with a GPU (say, 50 MHash/s to be conservative), it only takes about one minute to hash a difficulty-1 block.  Worse yet, you could precompute a few hundred of these and reuse them to bring down different clients, since orphaned blocks don't get relayed.

Is this a problem that has been discussed before?  If so, I would like to know what its eventual resolution was.

Thanks.

[kjj]

Nodes do not accept blocks with difficulty below what they are expecting.

[ByteCoin]

Nodes do not accept blocks with difficulty below what they are expecting.

But do they accept blocks which are built off blocks mined in the very distant past when the difficulty was minimal?

I think they do.

As patvarilly says (and you overlook) the client can't gratuitously ignore new blocks which branch off very old blocks because that would hinder block chain reorganisation and the adoption of the "longest" chain if the network were split for a long time and then reconnected.

I haven't seen the problem addressed before. If such checks existed I would expect to see them in ProcessBlock() in main.cpp and there's nothing appropriate there. As far as I can tell, patvarilly's post is completely correct.

ByteCoin

[JoelKatz]

This could be solved by adding a few barriers into the client. Any time the world block chain is known stable, one could take a block number and hash pair and hard code it into the client a few days later. Once the client had passed a barrier, confirming the hash, it would not accept orphaned blocks for before the barrier or with difficulties below the barrier difficulty.

However, this brings up a larger point. The BitCoin client should be audited for these kinds of risks. As of right now, there are probably many ways a malicious attacker could temporarily disable or compromise the BitCoin network. (At worst, all they could do is slow down mining and transaction committing. Your money is safe. But that's still kind of bad.)

[genjix]

There are already checkpoints in Bitcoin.

Also orphan blocks aren't verified unless there's a block chain re-organisation. At which point the block chain is invalidated from where it forks and the entire thing is recalculated from there.

[JoelKatz]

There are already checkpoints in Bitcoin.

Oh?! Awesome.

Also orphan blocks aren't verified unless there's a block chain re-organisation. At which point the block chain is invalidated from where it forks and the entire thing is recalculated from there.

His attack is not forcing the client to verify them but tricking the client into storing them in case there's a massive reorganization that we know will never happen.

A simple limit on orphan blocks will solve this. Since they're not propagated and the attack is on memory, it seems pretty little to worry about. You could handle millions of such blocks with no problem.

[patvarilly]

A simple limit on orphan blocks will solve this. Since they're not propagated and the attack is on memory, it seems pretty little to worry about. You could handle millions of such blocks with no problem.

Not really: MAX_BLOCK_SIZE is 1,000,000, so I could make megabyte-sized blocks and send them your way.  Every thousand of these I send you chew up 1GB of memory on your end, enough to make anyone sad (and perhaps even crash the client due to a process limit).  To go further, if I send you a million such blocks, that'll eat up 1 TB of swap space, which would bring down almost any normal user's machine, and maybe even some miners (admittedly, sending you 1TB takes a while, but if you're a server machine and no one's watching, then who cares?).

Of course, you could just restart the client and be in the clear, but it seems pretty easy to defend against this kind of attack.  As you said, limit the number of orphan blocks you're willing to keep in memory.  Even better, when choosing which orphans to forget about, preferentially forget those that are linked to a previous orphan that you know about.  That way, you'll slowly build back to a genuine fork point, if that's what's going on.  But to do this properly, as soon as an orphan chain is linked into the main chain, you'd need to push a request for all the blocks following the tip of that orphan chain, since you may have received them before and chosen to forget about them.

[Gavin Andresen]

I'd like to see somebody work on a "shun ill-behaved peers" patch.

So if one of your peers sends you lots of garbage (blocks/transactions/addresses/whatever) you just disconnect from it and refuse to accept connections from it for a while.

The trick is thinking really hard about what is really 'garbage' and what might be honest, it-happens-every-so-often weird behavior due to block chain splits or other network events.

The goal would be to prevent a wide range of denial-of-service attacks.

[makomk]

I'd like to see somebody work on a "shun ill-behaved peers" patch.

So if one of your peers sends you lots of garbage (blocks/transactions/addresses/whatever) you just disconnect from it and refuse to accept connections from it for a while.

Now imagine what happens if some nodes have the patch and some don't, and it's possible to convince the ones that don't to forward the garbage they receive. It wouldn't have to be enough garbage to pose a denial-of-service threat in itself, just enough to trigger other nodes to shun the unpatched part of the network.

[JoelKatz]

Now imagine what happens if some nodes have the patch and some don't, and it's possible to convince the ones that don't to forward the garbage they receive. It wouldn't have to be enough garbage to pose a denial-of-service threat in itself, just enough to trigger other nodes to shun the unpatched part of the network.

Most of the garbage we're talking about wouldn't be forwarded (such as orphaned blocks). But you pose a very good point if the attack comes in the form of something that does cause node-to-node traffic.

It might be necessary to implement some of these changes with a trigger to implement them only after a certain block number is received. We then leave enough room for at least most of the network to update.

Another possible idea is to make a node submit some proof of work to connect to you. You can normally demand none or a very small one. But if you sense an attack, start demanding proof of work and start disconnecting nodes that place an unusual load on you. That would increase the computational resources an attacker would need, and it wouldn't affect existing non-malicious node-to-node connections.