What is the purpose of indexing the mempool by these five criteria?

Question

In the bitcoin source code in txmempool.h, a comment says that unconfirmed transactions are indexed by five criteria:

 * mapTx is a boost::multi_index that sorts the mempool on 5 criteria:
 * - transaction hash (txid)
 * - witness-transaction hash (wtxid)
 * - descendant feerate [we use max(feerate of tx, feerate of tx with all descendants)]
 * - time in mempool
 * - ancestor feerate [we use min(feerate of tx, feerate of tx with all unconfirmed ancestors)]

I can understand why would we need to index transactions by the time they are in the mempool. But I can't understand the need for sorting them based on txid and wtxid (while they are hash output, so they are like random numbers, why bother to index them?). And I also don't understand the meaning of descendant feerate and ancestor feerate. The simple concept I can deduce is that miners are willing to put transactions with higher fee rates in their block, so sorting based simply on fee rate makes sense to me, but why is sorting based on parents and children of a transaction?

Answer 1

The mempool is the short-term memory of a full node. We use its content e.g. to:

• exchange information with peers
• build block templates
• estimate feerates
• track pending payments to our wallet

The index allows us to look up the full transaction objects based on each of the keys of the index.

txid/wtxid

For example, the txid and wtxid appear in the context of transaction relay as shorthand identifiers for the full transaction objects. We tell a peer that we have a list of new txs using just the txids and they respond by asking for a subset of those by listing the respective txid/wtxids. We use this key to look up the object and serve their request. We also use the txid to reassemble blocks after getting a new block per "compact block relay". Similarly, when a new transaction spends an unconfirmed input, we can look up the parent transaction per the txid referenced in the input of that new transaction. Generally, we use txid any time we reference individual transactions.

time in mempool

When we build new transactions, we need to estimate the feerate that'll get us a confirmation in the intended time frame. We base our estimate on tracking how long transactions were in our mempool before they got included in a block. While unconfirmed transactions remain valid indefinitely (or until an input gets spent in another transaction), we want to allow users to easily supersede unsuccessful attempts at transacting. Full nodes drop transactions after they have stuck around their mempool for 14 days. Additionally, it is policy to only keep the first of a set of conflicting transactions unless the first transaction signaled replaceability and the subsequent transactions fulfill the requirements to replace the predecessor. Either way, we want to look up transactions per the time they've been in the mempool sometimes, and if we wouldn't have an index for that, we'd have to sort the whole mempool each time to do so.

ancestor feerate

An ancestor set is composed from a transaction and all of its ancestors. Ancestors are transactions that an observed transaction topologically depends upon: a transaction cannot be included in a block until all of its parents have been included. If tx_C spends an output of tx_B and tx_B spends an output of tx_A, tx_A and tx_B are ancestors of tx_C, and the ancestor set of tx_C is {tx_A, tx_B, tx_C}. The ancestor feerate of a transaction refers to Σ(fees)/Σ(vsize) of its ancestor set.
When we build block templates, we sort all transactions by their ancestor feerates and pick the ancestor set with the highest ancestor feerate to the block template. After picking an ancestor set, each related transaction's ancestor set is updated, and we pick the new highest. Repeat until the block is full or there is nothing left to pick.
This approach ensures that the transactions appear in the topological order in the block, correctly prioritizes child-pays-for-parent situations, and greedily maximizes the collected transaction fees in the block template. If we only looked at the feerate of the transaction, we might miss that a transaction is dependent on a heavy low-fee transaction, or that a transaction has been bumped by a high feerate child.

descendant feerate

The descendant feerate is the counterpart to the ancestor feerate. It's the Σ(fees)/Σ(size) of the given transaction and all its descendants. E.g. tx_A has two child transactions tx_B and tx_C. If tx_B has a lower feerate than tx_A, but tx_C has a higher feerate than tx_A, then tx_C has the highest descendant feerate, tx_B has the lowest descendant feerate, and tx_A has one between the two. The mempool size is limited. Sometimes, when there is a lot of blockspace demand, more transactions are submitted to the network than can fit in your node's mempool. At that point, the mempool will drop the transactions that are least likely to be included in a block. While the ancestor feerate tells us what is most valuable to include, the descendant feerate tells us which transactions are signaling the lowest priority. We drop the transactions with the lowest descendant feerate first. If we only looked at the transaction's feerate itself, we might miss that a low feerate transaction is the parent in a CPFP situation. In the case of the above example, we would first drop tx_B because it has the lowest feerate, and then drop tx_A (whose descendant feerate is higher than its own feerate at that point, but lower than tx_C's). Evicting tx_A also evicts tx_C because it cannot be included in a block with its parent creating the output it spends.

Answer 2

Just adding onto Murch's answer, which does a great job at explaining the uses of each index.

But I can't understand the need for sorting them based on txid and wtxid (while they are hash output, so they are like random numbers, why bother to index them?).

Note that indexing by something doesn't necessarily mean ability to sort by it. Boost multi index containers allow each index to have different properties (ordered vs hashed, unique vs non-unique, etc.), which makes this data structure very suitable for the mempool use case. The txid/wtxid indices allow us to quickly look something up by txid/wtxid (boost::multi_index::hashed_unique), while entry time and feerate are specifically for sorting (boost::multi_index::ordered_non_unique). We won't sort by txid and, similarly, we won't try to uniquely identify a mempool entry based on its ancestor feerate.

You can find more information by looking at the type declaration of this data structure and the Boost multi index container reference.