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

glozow commented at 7:11 pm on February 1, 2023: member

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.

glozow added the label Mining on Feb 1, 2023

glozow added the label Mempool on Feb 1, 2023

DrahtBot commented at 7:11 pm on February 1, 2023: contributor

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 force-pushed on Feb 2, 2023

glozow commented at 9:47 am on February 2, 2023: member

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 commented at 9:57 am on February 2, 2023: member

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 commented at 8:24 pm on February 2, 2023: member

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 commented at 7:53 am on February 6, 2023: member

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

Inviting to open a dual-funded channel below-minrelayfeerate
Submit it as a package with high-feerate child (solo-Bob)
Replace the high-feerate child with another solo-Bob tx which has nothing to do with the initial dual funding transaction
Now the dual funding transaction is sitting alone below-minrelayfeerate and is trimmed from the mempool in the end
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 commented at 3:23 pm on February 7, 2023: member

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?

in src/txmempool.cpp:1063 in 98121c61fb outdated

1042@@ -1043,17 +1043,23 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
1043 
1044     unsigned nTxnRemoved = 0;
1045     CFeeRate maxFeeRateRemoved(0);
1046-    while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1047+    while (!mapTx.empty()) {
1048         indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1049 
1050+        CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());

ajtowns commented at 10:11 am on February 8, 2023:

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

in src/txmempool.cpp:1072 in 98121c61fb outdated

1058         // equal to txn which were removed with no block in between.
1059-        CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1060-        removed += m_incremental_relay_feerate;
1061-        trackPackageRemoved(removed);
1062-        maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1063+        if (removed >= m_min_relay_feerate) {

ajtowns commented at 10:17 am on February 8, 2023:

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

0if (removed >= m_min_relay_feerate) {
1    if (DynamicMemoryUsage() <= sizelimit) {
2        break; // normal exit from loop
3    }
4
5    // only track fee rate for txs with descendant feerate above m_min_relay_feerate
6    removed += incr; trackPackageRemoved(removed); mFRR = max(mFRR, removed);
7}

ajtowns commented at 10:27 am on February 8, 2023:

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

0int low_fee_removed = 0;
1while (!empty() && low_fee_removed < 100) {
2    ...
3    if (removed < m_min_relay_feerate && DynamicMemoryUsage() <= sizelimit) {
4        ++low_fee_removed;
5    }
6    ...
7}

glozow commented at 11:07 am on February 8, 2023:

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 commented at 11:32 am on February 8, 2023:

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 commented at 3:42 pm on February 8, 2023:

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 commented at 12:38 pm on February 13, 2023:

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 commented at 5:38 pm on February 20, 2023:

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 commented at 8:05 pm on February 9, 2023: member

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 commented at 1:11 am on February 10, 2023: contributor

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 commented at 3:54 pm on February 10, 2023: member

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.

Is this a problem from a node anti-DoS perspective?
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 commented at 4:25 pm on February 10, 2023: member

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

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

DrahtBot added the label Needs rebase on Feb 20, 2023

glozow force-pushed on Mar 23, 2023

glozow renamed this:
~~mempool / miner: regularly flush below-minrelayfeerate entries, mine everything in the mempool~~
mempool / miner: regularly flush <=0-fee entries and mine everything in the mempool
on Mar 23, 2023

DrahtBot removed the label Needs rebase on Mar 23, 2023

[miner] set default -blockmintxfee to 0

If we enforce -minrelaytxfee at the same feerate as -blockmintxfee
(currently their defaults are the same) for all transactions coming into
the mempool, the BlockAssembler can trust that adding packages will
result in a block template meeting this feerate.

This strategy may also be better. For example, one transaction
is bumped by two children, where the 3-transaction package is above
blockMinFeeRate, but each child's ancestor set is below blockMinFeeRate.

We do not enforce feerate rules during reorgs, so it is possible for
low-feerate transactions to exist in the mempool this way. However,
these transactions are only selected if there are no better packages
available in the mempool.

Having separate values for -minrelaytxfee and -blockmintxfee made sense
in the past when Coin Age Priority existed, but that was removed in
v0.15.

89ec73cdfc

[mempool] evict everything paying 0 fees in TrimToSize()

At this point it's not expected that there are any such transactions,
except from reorgs.

def42c2089

[mempool] TrimToSize() after a reorg 62f4ab77cd

[test] 0-fee transactions from reorg are not kept in mempool 3232070bfb

[test] 0-fee package CPFP consequences 744851d68e

in src/init.cpp:594 in 2629aea842 outdated

590@@ -591,7 +591,7 @@ void SetupServerArgs(ArgsManager& argsman)
591 
592 
593     argsman.AddArg("-blockmaxweight=<n>", strprintf("Set maximum BIP141 block weight (default: %d)", DEFAULT_BLOCK_MAX_WEIGHT), ArgsManager::ALLOW_ANY, OptionsCategory::BLOCK_CREATION);
594-    argsman.AddArg("-blockmintxfee=<amt>", strprintf("Set lowest fee rate (in %s/kvB) for transactions to be included in block creation. (default: %s)", CURRENCY_UNIT, FormatMoney(DEFAULT_BLOCK_MIN_TX_FEE)), ArgsManager::ALLOW_ANY, OptionsCategory::BLOCK_CREATION);
595+    argsman.AddArg("-blockmintxfee=<amt>", strprintf("(DEPRECATED) Set lowest fee rate (in %s/kvB) for transactions to be included in block creation. (default: %s)", CURRENCY_UNIT, FormatMoney(DEFAULT_BLOCK_MIN_TX_FEE)), ArgsManager::ALLOW_ANY, OptionsCategory::BLOCK_CREATION);

ajtowns commented at 11:23 pm on March 23, 2023:

Should say “UNSUPPORTED”, not “DEPRECATED” ?

Weak NACK on removing this option – in inq#23 we’ve got a use case for accepting txs into the mempool that we don’t intend to mine (until they are CPFP’ed).

ajtowns commented at 1:18 am on April 5, 2023:

(Would support changing the default to 0sat/vb though)

ajtowns commented at 9:58 pm on April 11, 2023:

From the ephemeral anchors review club:

<glozow> ok hm. i kinda need to get rid of blockmintxfee for pakcage relay tho

Can you elaborate on that? You can just drop the blockminfee commit from this PR, and it seems fine, no?

The only result of setting -blockminfee is that if its value is higher than -minrelaytxfee you’ll potentially never empty your own memory even if you’re the only miner and no new transactions are being created/relayed. That’s undesirable as default behaviour, but seems okay if you deliberately choose it. (And the mempool will empty eventually anyway, as a result of expiry)

glozow commented at 1:53 pm on April 12, 2023:

From the ephemeral anchors review club:

<glozow> ok hm. i kinda need to get rid of blockmintxfee for pakcage relay tho

Can you elaborate on that?

My thinking there was that we needed to address this DoS issue in order to proceed with package relay, and this PR seemed like the most likely approach (hence the “kinda”). Now, maybe #26933 seems more likely?

You can just drop the blockminfee commit from this PR, and it seems fine, no? The only result of setting -blockminfee is that if its value is higher than -minrelaytxfee you’ll potentially never empty your own memory even if you’re the only miner and no new transactions are being created/relayed.

I don’t think the problem is only when blockmintxfee > minrelaytxfee. With this PR, if both are 1sat/vB, you can have (all transactions same size):

parent (paying 1 satoshi in fees) + fee-bumping child accepted to mempool as a package
attach 2 more children to the parent, each 1.5sat/vB
replace the child with something not bumping the parent. The parent is not removed because its descendant score > 1sat/vB
parent is also never selected in BlockAssembler because the 2 children’s ancestor scores are < 1sat/vB.

This works even if we have a significantly lower blockmintxfee (e.g. 0.6sat/vB) while minrelaytxfee = 1sat/vB. We can still get to an equivalent state, just with more children. N children with feerate (N+1)/N keeps the descendant score above 1sat/vB while the ancestor scores are lower than blockmintxfee.

(Would support changing the default to 0sat/vb though)

Yeah, I think this would work.

ajtowns commented at 3:44 pm on April 12, 2023:

Yeah, fair point – the claim should be “setting -blockminfee higher than zero may result in txs remaining in your mempool that will never be mined”; but as long as that’s not the default behaviour, that doesn’t seem particularly problematic? (TBH, I’d rather be able to pass blockminfee/blockmaxweight as getblocktemplate parameters)

Sounds like this should be closed though?

glozow commented at 5:35 pm on April 12, 2023:

Resolving - restored support for -blockmintxfee (now it’s actually just “deprecated”), default is 0, and added this warning when it is set.

glozow force-pushed on Apr 12, 2023

glozow referenced this in commit bdfe27c9d2 on Apr 26, 2023

DrahtBot added the label CI failed on Apr 30, 2023

maflcko commented at 9:37 am on August 8, 2023: member

Needs rebase if still relevant?

glozow commented at 9:12 am on August 9, 2023: member

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 closed this on Aug 9, 2023

glozow commented at 2:18 pm on December 12, 2023: member

Planning to resurrect this after #28948.

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

Reviews

Conflicts