mempool / miner: regularly flush <=0-fee entries and mine everything in the mempool

[glozow]

This was suggested in #26933 (comment).

The Problem
Package CPFP (only accessible through regtest-only RPC submitpackage) allows 0-fee (or otherwise below min relay feerate) transactions if they are bumped by a child. We need to know what to do with these transactions if they lose their sponsor, e.g. due to a replacement that removed the input spending this 0-fee transaction.

This is made slightly more complicated by the fact that our "selection scoring" (BlockAssembler) is different from our "eviction scoring." Roughly, we select based on ancestor feerate and evict based on descendant feerate. This may lead to evicting things we would actually want to mine and not evicting things that we will never mine.

This PR's approach is to remove the 1sat/vB -blockmintxfee and have BlockAssembler select anything in the mempool (still based on ancestor packages, but not stopping at 1sat/vB). It also adds logic to TrimToSize() to evict anything paying <=0 fees. The idea is, if we're getting to the bottom of our mempool, we scrape up all the sats we can. Anything that pays some fee is worth adding to the block template.

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: #26933 (comment)

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 #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 #25038 (comment)

[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. #26933 (comment)

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.

#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?

[ajtowns]

I think it would be good to rename this -- previously the tx was definitely being removed, but now the removal is conditional. candidate maybe?

[ajtowns]

I think this would have been slightly clearer to me as:

if (removed >= m_min_relay_feerate) {
    if (DynamicMemoryUsage() <= sizelimit) {
        break; // normal exit from loop
    }

    // only track fee rate for txs with descendant feerate above m_min_relay_feerate
    removed += incr; trackPackageRemoved(removed); mFRR = max(mFRR, removed);
}

[ajtowns]

If we're concerned about the 2500 tx thing, we could limit that here couldn't we? ie:

int low_fee_removed = 0;
while (!empty() && low_fee_removed < 100) {
    ...
    if (removed < m_min_relay_feerate && DynamicMemoryUsage() <= sizelimit) {
        ++low_fee_removed;
    }
    ...
}

[glozow]

If we're concerned about the 2500 tx thing, we could limit that here couldn't we?

I think the problem with limiting this way is we're just putting it off - we still need to finish flushing everything before we build a block template or ATMP another transaction, otherwise we might build a low-feerate block template or let a tx spend from something 0-fee. So we could stop here, then mark that the mempool needs_flush=true (or something) and flush fully before we do either of those 2 things?

[ajtowns]

What's the problem with building a low-feerate block template? The tx already propogated, so should be roughly fine for compact block relay; and if there are higher feerate txs, we'll select them anyway.

If we ATMP a child of the tx, and it CPFPs it enough to get above min_relay_feerate, then that's also fine, we just get the same behaviour with "accept A+B, drop A, accept C(pays for B)" as we do with "accept A+B, accept C, drop A".

[instagibbs]

Adding a 0-fee package to a block template can not raise profitability, only potentially lower it(?)

Pretty easy to imagine different ancestors being evicted at different times, causing compact block mismatches. We could retain blockmintxfee though, right? Then all you're left with is some mismatches across pools potentially causing weirdness with individual vs package evaluation(dedup or not), but this is likely short-lived anyways.

[glozow]

What's the problem with building a low-feerate block template?

So I think the argument for banning literal 0-fee packages is there is no gain from mining it, but it costs resources to include in the block. So it's probably not controversial to remove everything =0 fee, regardless of how many there are (?).

Beyond that (>0 but <minrelay), I don't have an argument other than the fact that a miner might expect -blockmintxfee to guarantee that the feerate of their block won't be lower than that.

[ajtowns]

If we want to support miners being able to guarantee the feerate of their block won't be lower than x, then we shouldn't be removing/deprecating -blockmintxfee ?

I think it makes sense to have "ancestor fee(rate) is at 0sat? we're done here" logic; miners can always modify the fee if the tx is desired anyway...

[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 mempool: disallow txns under min relay fee, even in packages #26933 (comment)). 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 #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.