mempool / miner: regularly flush below-minrelayfeerate entries, mine everything in the mempool

[glozow]

Opening as an alternative to #26933, as suggested in https://github.com/bitcoin/bitcoin/pull/26933#issuecomment-1412320818. Though they don't need to be mutually exclusive, e.g. we could both require individual transactions to meet minrelayfeerate and also evict below-minrelayfeerate entries in TrimToSize().

This PR adds logic to TrimToSize() to evict anything that is below min relay feerate and removes BlockAssembler::blockMinFeeRate and -blockmintxfee.

A major advantage of this approach is that 0-fee, non-v3 transactions can be bumped in package CPFP.

A few observations which may or may not be problematic:

• This increases the potential work after a reorg, since we add an extra step of removing the below-minrelayfeerate entries.
• This increases the number of transactions that may be evicted in a replacement (from the worst case scenario we discussed before, it's up to 2500 entries).
• This means you can remove a transaction from your own mempool by calling prioritisetransaction with a negative value.

[DrahtBot]

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

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

[glozow]

cc @naumenkogs Re: https://github.com/bitcoin/bitcoin/pull/26933#issuecomment-1413246009

Just re-posting the scenario with 2400 extra transactions to evict in an RBF (originally in #26933 description):

• The mempool contains 100 "child" transactions, each spending from 24 unconfirmed parent transactions and 1 confirmed UTXO. - The parents are all 0sat/vB and CPFP'd. If the children are evicted, and the parents no longer bumped, they will be below min relay feerate.
• A replacement transaction spends only confirmed UTXOs. This means it has 100 directly conflicting transactions (the 100 children). There are no descendants, so there are 100 original transactions in total. But accepting the replacement transaction actually invalidates not 100, but 100 * 25 = 2500 mempool transactions.
• We can remove these transactions in TrimToSize(), but 2500 is considerably more than our previous limit of 100.

A counterargument is that we don't currently have any guarantees that we never TrimToSize() more than 2500 entries at a time. We also don't have a good idea of how computationally expensive this really is. For example, it's possible that accepting a large, high-feerate transaction when the mempool is almost full causes just as many evictions. In general, when traffic is high, mempool churn is probably high as well.

[glozow]

I guess another similar question is whether we care about the potential reorg handling slowdown. One scenario is a reorg adding below-minrelayfeerate transactions back to mempool, which we then spend time flushing through TrimToSize() (I suppose this is bounded by MAX_DISCONNECTED_TX_POOL_SIZE and the fact that it's extremely expensive to mine a bunch of free txns so that other people's reorg processing slows down). During this time, we can't build the next block template. Previously, we basically held off on flushing until the next tx was submitted, and blockmintxfee prevented low-feerate things getting into the template. I'm not sure how long this takes, will have to benchmark.

[ariard]

Adding a trim-under-min-relay directly in ActivateBestChainStep() to evict 0-fee parent dangling in the mempool on an observable oracle like block propagation could break some assumptions for chain of transactions, especially if they're coming from multiple spenders. If you assume a collaborative transaction like the dual-funding specified by BOLTs, where the collaborative transaction can be RBF'ed, an old low-federate transaction could be broadcast with a high-federate package, and if this CPFP replaced, stale the opening of the dual-funded channel. I think an improvement could be at least to make the oracle hard to predict from a spying node (and if so we should probably add a filter to prevent 0-fee evicted probing with GETDATA).

Transaction processing not being computationally cheap has already been raised in the context of https://github.com/bitcoin/bitcoin/pull/21224 As of today, I think we would like to ensure second-layers can broadcast significant quantity of pre-signed transactions in a short period of time (e.g a LSP doing splicing with all its spokes to rebalance channels because network mempools are empty), without interferences with our current DoS limits like MAX_PEER_TX_ANNOUNCEMENTS. Or if second-layers nodes should deploy multiple "transaction-relay" entry points (e.g connect to multiple full-nodes) to do some kind of initial broadcast load-balancing, that something to be thought of, I believe (and if we should modify our transaction-broadcast backend there). I think we would like to be careful to not introduce exploitable synchronicity issues, e.g in the case of massive redeployment of channel types for Lightning (e.g upgrade from anchor outputs to Taproot outputs on the commitment transaction format), see comment https://github.com/bitcoin/bitcoin/pull/25038#issuecomment-1405944407

[naumenkogs]

@ariard Can you tell if my description is correct? When Alice and Bob are not friends, Bob can waste Alice's resources by:

1. Inviting to open a dual-funded channel below-minrelayfeerate
2. Submit it as a package with high-feerate child (solo-Bob)
3. Replace the high-feerate child with another solo-Bob tx which has nothing to do with the initial dual funding transaction
4. Now the dual funding transaction is sitting alone below-minrelayfeerate and is trimmed from the mempool in the end
5. Alice has to double-spend it or keep trying to get it mined

And before this PR, the transaction would sit in the mempool with below-minrelayfeerate waiting for empty blocks? So that's a problem? (Apart from that, I'm confused by you saying collaborative transaction can be RBF'ed — why does this matter?)

[instagibbs]

an old low-federate transaction could be broadcast with a high-federate package, and if this CPFP replaced, stale the opening of the dual-funded channel.

I'm also not really understanding the comment. The flushing logic only effects things that can't even be relayed on today's network, assuming no one is touching minrelayfeerate defaults?

I did some basic benchmarking here on eviction, showing that on my machine at least it takes ~0.3s to evict a "worst case" scenario. Do note that it also takes roughly the same amount of time to even build up the mempool, and that's without any script checks. So in some sense it at least isn't obviously the wrong thing to do from a CPU exhaustion perspective. https://github.com/bitcoin/bitcoin/pull/26933#issuecomment-1413841878

One sanity benchmark I didn't run is the speed of the benchmark if only the child transaction of each package is evicted. I suspect it would be quick, but probably should double check.

This PR seems to be simpler from a mental model perspective, at the cost of some additional CPU cycles. It would also allow non-V3 transactions to have more reasonable specs.

https://github.com/bitcoin/bitcoin/pull/26933 Seems to be more complex from a mental model perspective, but may be more protective of CPU cycles in certain scenarios with non-privileged mempool usage.

One scenario is a reorg adding below-minrelayfeerate transactions back to mempool

I'd consider this roughly equivalent to a mempool user paying to put things in the mempool, then evicting them in terms of attack cost. Am I thinking about this wrong?

[sdaftuar]

So, in trying to come up with a proof that evicting a descendant package that is below the minrelayfeerate from the mempool is safe to do because we'd never evict transactions we'd want to mine, I discovered a counterexample, please see below:

descendant feerate example.pdf

[ajtowns]

So, in trying to come up with a proof that evicting a descendant package that is below the minrelayfeerate from the mempool is safe to do because we'd never evict transactions we'd want to mine, I discovered a counterexample, please see below:

descendant feerate example.pdf

You can already have the same with a full mempool? Multiply the fees by 10, and set the mempool min fee to 9sat/vb, have the rest of the mempool only spend confirmed txs and have a fee rate of 8.4-9 sat/vb, but have there be enough of them that the mempool is overfull and needs to be trimmed. In that case, we'll drop A (at 8.3sat/vb descendant feerate) first, even though D+A has the highest ancestor score and should be the first thing we'd mine.

I don't think you can mine by ancestor score and trim by descendant score without getting these inconsistent edge cases...

[instagibbs]

IIUC Mempool trimming when full causes this in very simple situations, such as a 0-fee parent with two fee-paying children. If DF(parent) is dragged down too much by a child, the whole package is evicted even if the other child was paying enough.

In other words, I think it opens the door to a more specific form of it when mempools are empty, not a new class of issues.

1. Is this a problem from a node anti-DoS perspective?

2. Is this a problem from a wallet perspective?

Would a wallet's rebroadcast of say a parent-child package still similarly as robust if things weren't trimmed?

[sdaftuar]

I am still wrapping my head around how best to think about this, but a few things come to mind:

1. Yes perhaps we should improve the way mempool limiting works in general, so that we either (a) automatically resubmit descendant subpackages that would be eligible for mempool acceptance due to sufficient feerate whenever they get trimmed out of the mempool due to eviction of a parent, or better (b) avoid evicting those subpackages in the first place.

2. The example I posted shows that it is possible for there to be transactions in the mempool that cannot be mined at a feerate >= minrelayfeerate, but cannot be detected as such by looking only at descendant scores (this is demonstrated if you only considered transactions B, C and E in the example I posted above). Looking at ancestor scores is also insufficient for making this determination (as mentioned in https://github.com/bitcoin/bitcoin/pull/26933#issuecomment-1416713975). This would seem to imply that we would need to do something substantially more complicated in order to prevent a situation where, after package validation is deployed, that a miner might mine a block containing a package at a feerate below the minrelayfeerate.

Thinking about (2), perhaps we should split our concerns about low-feerate transactions/packages in the mempool into what I think are the two components: (a) anti-DoS and (b) maximizing miner income.

For (a) anti-DoS, I don't believe there is a DoS concern if we both mine everything in the mempool and only encounter this situation due to these RBF scenarios where no free relay is going on. So really the concern is just (b), how do we ensure that a miner is never worse off for including some transactions that are in the mempool.

We could just try to cut out the most obvious problems -- transactions that are literally 0-fee to the miner. If we restrict the allowed topologies for package validation, we may be able to do better than that, but I don't know if that's a direction we want to go down. @ajtowns' idea in https://github.com/bitcoin/bitcoin/pull/26933 may work as well, but I'm wondering how we can generalize our thinking of what we're trying to specifically achieve?

[maflcko]

Needs rebase if still relevant?

[glozow]

Closing in favor of #27677 which would solve the more general issue of selection score != eviction score.

Noting that #25038 adds trimming of things below min relay feerate, but we only expect those transactions as a result of reorgs or replacement of v3 children. v3 doesn't have the the issue of selection score != eviction score due to topological restrictions.

[glozow]

Planning to resurrect this after #28948.