Why is the mempool indexed by descendant_score?

[RHavar]

i.e.

bitcoin/src/txmempool.h

Lines 466 to 471 in 920c090

	// sorted by fee rate
	boost::multi_index::ordered_non_unique<
	boost::multi_index::tag<descendant_score>,
	boost::multi_index::identity<CTxMemPoolEntry>,
	CompareTxMemPoolEntryByDescendantScore
	>,

I'm probably missing some other usages, but I can only find it in CTxMemPool::TrimToSize

bitcoin/src/txmempool.cpp

Line 1024 in 920c090

indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();

which I don't really understand. Wouldn't using ancestor_score make a lot more sense?

[maflcko]

I guess it returns the max, so that either its own feerate or the feerate with its descandants are considered to allow for fee bumping by spending one (e.g. the change) output and "attaching" a high fee?

[RHavar]

Yes, I believe it uses the MAX(transactionFeeRate, transactionAndAllDescendantsFeeRate) as the descendant_score. But I'm still struggling to understand why this is useful. I didn't quite get your comment about allowing for fee bumping

[fanquake]

cc @sdaftuar

[sdaftuar]

which I don't really understand. Wouldn't using ancestor_score make a lot more sense?

I think there are two observations to note here. First, the ancestor score of a transaction T is the feerate of T along with any unconfirmed transactions that T depends on.

Second, if we evict T from the mempool, then to maintain consistency we must also evict all descendants of T as well, so that no transaction in the mempool is missing its unconfirmed parents.

Taken together, using the ancestor score wouldn't make any sense -- just because a transaction has a low feerate with ancestor does not mean it's unlikely to be included in the next block. For example, if transaction A is small and has the minimum fee rate of the mempool, but transaction B is a large descendant with a huge feerate, then the ancestor score for A will be small, but it might be selected in the next block, because the ancestor score for B is still very high, causing it to get pulled in when B is selected. Moreover, if you evicted A for being low feerate, then you must also evict B (which is obviously undesirable -- it might have been the most profitable thing to be included in the next block).

One way to think about this is that while the top transactions according to the ancestor score are likely to be good candidates for inclusion in the next block, you have basically no information about whether things at the bottom of the ancestor index are likely to be included or not (since their descendants are relevant to that determination, and the ancestor score tells us nothing about a transaction's descendants).

On the other hand, the transaction with the worst descendant score is very unlikely to be a good candidate for inclusion in the next block, as neither the transaction nor its descendants sorts very high -- and again you have basically no information about whether transactions at the top of the descendant index are likely to be included or not (since their ancestors must be included in any block as well, and the descendant score does not include any ancestor information).

I guess an important point here is that if a low feerate transaction A has two immediate descendants B and C, where B has a high feerate and C has the lowest feerate of the group, then the descendant score of C will be lower than that of A. This is important because the descendant feerate of A might also be low while C is in the mempool even though A+B may be a good candidate for inclusion in the next block, but C would be evicted first (bumping up A's descendant score) before A would be considered for eviction.

You are correct to observe that the descendant score is only used in TrimToSize. Our mempool limiting algorithm (#6722) works by evicting the least-likely-to-be-mined transactions from the mempool whenever we bump up against our limit, and the descendant score is what we use to measure that.

[RHavar]

Thanks @sdaftuar that makes perfect sense, I'll close the issue.

I do wonder though if TrimToSize called rarely enough (and at time-non-critical points) that it makes sense to just do a single-pass of the mempool when deciding what to trim in exchange for being able to speed up all the other mempool operations.