p2p: Proof-of-concept: Improve DoS-resistance to low-work headers chains #17332

A low-work headers chain might be valid according to consensus rules, yet uninteresting for reaching consensus, because of the little work on the chain. Currently, a low-work headers chain that is received by bitcoind is nevertheless stored in memory (permanently), because the headers download logic stores valid headers as it goes, and we only look at the total work on the chain at a later point.

By definition, a low-work headers chain can be cheap to produce, so the cost to an adversary for performing a memory DoS (on the entire network of reachable nodes) is not very high (checkpoints currently make this cost non-trivial, but the cost is not increasing as the chain advances).

Ideally, the cost to making a node store a headers chain should be related to the total work on the best chain, as we're only ever interested in the most work chain for consensus purposes. (If an adversary is able to perform a memory DoS by producing a headers chain with work comparable to the work on the best chain, there's not much we could do about it, as a node must be aware of all headers chains that potentially have the most work in order to remain in consensus. So requiring that a headers chain have work comparable to the most-work chain before we store it is essentially the best we can do.)

This patch introduces a headers download scheme that attempts to verify that a peer's headers chain has sufficient work (namely, within a week of our current tip and at least as much work as nMinimumChainWork) before committing to permanent storage.

If a peer gives us a headers message whose last header has less work than our anti-DoS threshold, then we store those headers in memory that is allocated to just that peer, until we've seen a chain tip building on those headers that has sufficient work. At that point, the headers will be processed and stored globally.

Because of the time-warp problem, where a chain producing blocks at a rate of 6 blocks/second can theoretically be valid even while being low-work, we have to consider the possibility of being fed a very long, low-work chain. If we stored all of a peer's headers even in temporary memory, this could be enough to be a memory DoS by itself. To address this, this patch uses a heuristic to cache just the last header in each message if the time on the chain is progressing slower than expected. If the chain ends up having sufficient work, then we can redownload the chain, verifying that we get the same headers back by using these cached headers as intermediate markers that must match the redownloaded chain.

Using this scheme, we can bound the memory used for headers download by a single peer to roughly the amount of memory we'd expect an "honest" chain to use (1 block header per 10 minutes starting at the genesis block). To prevent an adversary from using many inbound peers to flood a node's memory due to simultaneous headers sync, this patch also includes logic to restrict using the per-peer headers sync memory by more than one peer at a time, along with timeout logic to prevent a single peer from starving headers sync from other peers.

Please see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017354.html for additional background on memory attacks possible using low-work headers chains. Currently, checkpoints are our only defense against memory attacks on our algorithm for storing headers, and the cost of attack (as described in that mailing list post) is not very high. Notably, the cost of an attack does not increase as the consensus chain accumulates work, because attacking our algorithm now relies on just being able to ramp down difficulty on a chain that forks from the last checkpointed block header.

My goal with this patch is to demonstrate that it should be possible to drastically increase the cost of this type of attack with changes only at our p2p application layer.

The algorithm is described a bit in the OP and further in comments in net_processing.cpp. This patchset is complex and difficult to reason about, I think for two reasons:

(a) We reuse the "headers" message in many contexts (it can be a response to a getheaders, which can be sent either for an initial chain sync or in response to a block announcement; or it can be a newly announced block). The different contexts that might be in play when processing a headers message makes reasoning about our state machine fairly difficult.

(b) Because our p2p protocol does not support downloading headers in reverse, which is a functionality needed by the algorithm I tried to use here, I had to approximate that by doing something fairly complicated (storing 1 block hash from each headers message, so that when I got to the point where I'd want to download headers in reverse, I instead download them forwards a second time and ensure I'm getting the same chain on the second try). This in turn means that the algorithm uses much more peer memory than desirable in the face of an attacker chain, which in turn requires additional complexity around limiting the number of simultaneously syncing peers, and preventing a sync peer from starving other peers whose chains need to sync.

In the absence of an attacker giving a node a "fake" chain, this code would only have one effect: it changes initial headers sync to not fully process headers until we've downloaded the chain up to our nMinimumChainWork, at which point all the headers are processed in one go. After that, headers processing should be essentially unchanged from how it operates today.

That said, this patch is very complex, and I am not sure it's worth the review effort that would be required to merge this change in. It may be interesting as a proof-of-concept however, so that we have a defense on standby in the event of a memory attack on the network using low-work headers, and so that we have a good answer to any mistaken notions that checkpoints are somehow required to maintain Bitcoin's security model (they are not).

One alternate idea for increasing the cost of attack, which would be vastly simpler to deploy, is to raise the minimum difficulty of blocks (eg after the last checkpoint height). If we make an arbitrary chain cost at least, say, $1/block to create (assuming current mining hardware capabilities), then mining 100M blocks to create 8GB of memory usage would be quite expensive! I think this is a reasonable approach, but has two downsides:

(a) The cost of an attack still does not go up as the chain work goes up (so in particular, if the cost of an attack were to come down as hardware gets more efficient in the future, we could become vulnerable again).

(b) Changing the consensus rules we enforce comes with a higher bar for justification. Even though in this case I think someone could make a coherent argument for why this is not a meaningful consensus change (and, debatably, shouldn't even require community consensus!), this may not be well-understood without significant discussion and education. I think it's probably not worth the social effort of changing the consensus rules, just to solve what is fundamentally a problem at the p2p layer. But perhaps I'm overly pessimistic here.

If this high level approach (of having peers prove that their headers chains have sufficient work in order to permanently store them) seems like something we might want to include, but if this patch is indeed not worth the effort to try to merge, then another option would be to consider a p2p protocol upgrade that would make this logic easier to implement, such as a set of new headers sync messages that support the underlying functionality, while giving other improvements as well, such as compression or parallel-download features described by Jim Posen (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015851.html). The advantage to that should be much simpler logic; the downside is that we run into issues with syncing headers chains from unupgraded peers who do not support the new message types.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #17383 (Refactor: Move consts to their correct translation units by jnewbery)
• #17376 (Add Parallel P2P Client in Rust by TheBlueMatt)
• #16762 (Rust-based Backup over-REST block downloader by TheBlueMatt)
• #16748 ([WIP] Add support for addrv2 (BIP155) by dongcarl)
• #16442 (Serve BIP 157 compact filters by jimpo)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

this would be so much cleaner and simpler if the p2p protocol had explicit measures for reverse fetching... ( https://en.bitcoin.it/w/index.php?title=User:Gmaxwell/Reverse_header-fetching_sync&action=history )

Cool, I had heard of the mitigation a long time ago but hadn't seen it written anywhere(hadn't seen bitcointalk thread either).

Too bad that this requires so much additional code and modifications to inner critical logic. Also, it doesn't compile on any of the ci builds.