"What happens if we replace something that was bumping an otherwise-too-low-feerate transaction? Should we try to calculate those and include them in the 100-tx limit?"
Concretely, I think this is the worst case scenario (corrected, thanks sdaftuar):
- The mempool contains 100 transactions Y1...Y100, each spending from 24 unconfirmed parent transactions and 1 confirmed UTXO. Let's say for each i in 1...100, Yi has unconfirmed parents {Ai...Xi} and spends a confirmed UTXO, zi. Altogether, we have 100 sets of 25 unconfirmed transactions: {A1...X1, Y1} ... {A100...X100, Y100}.
- All of {A1...X1} ... {A100...X100} are 1sat/vB, while Y1...Y100 are 100sat/vB, and the mempool minimum feerate is 2sat/vB. That is, if Y1...Y100 are evicted, {A1...X1} ... {A100...X100} will go below minimum feerate.
- The replacement transaction, Z, spends only confirmed UTXOs: z1...z100. This means Z has 100 directly conflicting transactions: A1...A100. There are no descendants, so there are 100 original transactions in total.
- Since the eviction of Y1...Y100 means that {B1...X1} ... {B100...X100} will no longer meet the mempool minimum feerate or min relay feerate, accepting the replacement transaction Z actually invalidates not 100, but 100 * 25 = 2500 mempool transactions (!).
- In the worst case scenario, we make these transactions as large as possible memory-wise. This means very large witnesses: assuming the maximum ancestor package weight is 404KWu, Z invalidates 100 * 404KWu = 40.4MWu ~= 40MB (actual memory is higher as it includes entry metadata) of the mempool.
Fun fact: unless the mempool is at its size limit, TrimToSize() doesn't actually evict things below the minimum feerate - see https://github.com/bitcoin/bitcoin/blob/9e59d21fbe5746b220f35b0a5a735198c3e6dcdb/src/txmempool.cpp#L1066-L1067
See logs from discussion https://gnusha.org/bitcoin-core-dev/2022-12-16.log
(1) Is this a more "effective" way to DoS the mempool and, if so, how much worse is it?
Suppose no transactions are below min mempool feerate or min relay feerate. Again, memory usage includes both transaction size and entry metadata/overhead. With default package limits and transactions maximizing bytes per vsize (404,000 weight units with mostly witness data), the worst case is 100 independent, 100KvB transactions. That's 100 * 400KWu = 40MWu ~= 40MB, which can be ~40MB + the memory for metadata/overhead.
(2) Is this new to packages?
Yes and no: package CPFP would allow transactions below min relay feerate and mempool minimum feerate. Without package CPFP, it is possible for transactions to be below mempool minimum feerate (i.e. because the mempool minimum feerate has risen after the transaction was accepted).
Concretely, it's already possible today to replace the sponsor of a e.g. 1sat/vB transaction that was submitted prior to your mempool min feerate rising. That tx will likely be evicted after the replacement, but was not counted by GetEntriesForConflicts for the 100 tx limit.
(3) Difference between these "fee-dependent" replaced transactions being below min relay feerate vs mempool minimum feerate?
Below mempool minimum feerate but above min relay feerate = paid some fees which at some point was acceptable. Below min relay feerate with no fee bumper = free relay, DoS.
(4) Can we try to remove these transactions?
We can try to remove transactions (by descendant feerate) below min relay fee in TrimToSize() regardless of whether we're at the limit or not. Need to make sure we can halt if this takes a long time (or if we're certain that the cap is something like 2400 transactions perhaps we bench and accept it). Lazily remove? We need to ensure that we don't try to accept another transaction before removing these dependencies, otherwise we may validate a transaction that depends on one of these freeloader mempool entries. It may make the most sense to just remove them all together.
Caveat: it is not always possible to detect these transactions. Namely, a transaction may have multiple children s.t. its descendant package is above minimum mempool feerate but each child's ancestor feerate is not. Note that, if each child's ancestor feerate is below min relay feerate, the block assembler will not consider them (BlockAssembler::blockMinFeeRate is set by default to min relay feerate).