<p>Just adding onto Murch's answer, which does a great job at explaining the uses of each index.</p>
<blockquote>
<p>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?).</p>
</blockquote>
<p>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 (<code>boost::multi_index::hashed_unique</code>), while entry time and feerate are specifically for sorting (<code>boost::multi_index::ordered_non_unique</code>). We won't sort by txid and, similarly, we won't try to uniquely identify a mempool entry based on its ancestor feerate.</p>
<p>You can find more information by looking at the <a href="https://github.com/bitcoin/bitcoin/blob/f697c068ebd0dfea552c1ff192dfd9d520f1ca9a/src/txmempool.h#L458-L488" rel="noreferrer">type declaration</a> of this data structure and the <a href="https://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/reference/index.html" rel="noreferrer">Boost multi index container reference</a>.</p>

CC BY-SA 4.0
2022-06-24T14:10:37.517Z
Welcome glozow!
Pieter Wuille
CC BY-SA 4.0
2022-06-24T14:33:13.613Z
Woop woop! Instant upvote :)
Michael Folkson
CC BY-SA 4.0
2022-06-24T14:00:46.950Z
2022-06-24T14:00:46.950Z
glozow
<p>The mempool is the short-term memory of a full node. We use its content e.g. to:</p>
<ul>
<li>exchange information with peers</li>
<li>build block templates</li>
<li>estimate feerates</li>
<li>track pending payments to our wallet</li>
</ul>
<p>The index allows us to look up the full transaction objects based on each of the keys of the index.</p>
<h2><code>txid</code>/<code>wtxid</code></h2>
<p>For example, the <code>txid</code> and <code>wtxid</code> 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 <code>txid</code>/<code>wtxid</code>s. We use this key to look up the object and serve their request. We also use the <code>txid</code> to reassemble blocks after getting a new block per &quot;compact block relay&quot;. Similarly, when a new transaction spends an unconfirmed input, we can look up the parent transaction per the <code>txid</code> referenced in the input of that new transaction. Generally, we use <code>txid</code> any time we reference individual transactions.</p>
<h2><code>time in mempool</code></h2>
<p>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.</p>
<h2><code>ancestor feerate</code></h2>
<p>An <em>ancestor set</em> 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 <code>Σ(fees)/Σ(vsize)</code> of its ancestor set.<br />
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.<br />
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.</p>
<h2><code>descendant feerate</code></h2>
<p>The <em>descendant feerate</em> is the counterpart to the <em>ancestor feerate</em>. It's the <code>Σ(fees)/Σ(size)</code> 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 <em>ancestor feerate</em> tells us what is most valuable to include, the <em>descendant feerate</em> tells us which transactions are signaling the lowest priority. We drop the transactions with the lowest <em>descendant feerate</em> 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.</p>

CC BY-SA 4.0
2022-11-23T16:23:01.820Z
Regarding ancestor feerate, "An ancestor set is composed from a transaction and all of its ancestors" -- just to be clear, only the transactions _unconfirmed_ ancestors.
Larry Ruane
CC BY-SA 4.0
2022-11-23T16:26:25.467Z
Regarding ancestor feerate, "After picking an ancestor set, each related transaction's ancestor set is updated ..." To clarify (but please check my understanding) "related" transactions are those that were _not_ chosen, but have ancestors that were. And the way we update such transactions' ancestor sets is to pretend that the chosen transactions are no longer in the mempool, as if they have already been mined.
Larry Ruane
CC BY-SA 4.0
2022-06-24T13:09:35.390Z
2022-06-25T21:54:27.770Z
2022-06-25T21:54:27.770Z
Murch
<p>In the bitcoin source code in <a href="https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.h#L371" rel="noreferrer">txmempool.h</a>, a comment says that unconfirmed transactions are indexed by five criteria:</p>
<pre><code> * 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)]
</code></pre>
<p>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 <code>descendant feerate</code> and <code>ancestor feerate</code>. 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 <code>fee rate</code> makes sense to me, but why is sorting based on parents and children of a transaction?</p>

<bitcoin-core><transaction-fees><bitcoin-core-development><mempool><source-code>
What is the purpose of indexing the mempool by these five criteria?
Amir reza Riahi
# What is the purpose of indexing the mempool by these five criteria?

(Asked by: username_0 on 2022-06-24)

In the bitcoin source code in [txmempool.h](https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.h#L371), 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?

**Tags:** bitcoin-core, transaction-fees, bitcoin-core-development, mempool, source-code


---

## 2 answers

### Answer by username_4 on 2022-06-24. Score: 15 | Accepted answer

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`/`wtxid`s. 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.

> **Comments:**
> **username_5**: Regarding ancestor feerate, "An ancestor set is composed from a transaction and all of its ancestors" -- just to be clear, only the transactions _unconfirmed_ ancestors.  
> **username_5**: Regarding ancestor feerate, "After picking an ancestor set, each related transaction's ancestor set is updated ..." To clarify (but please check my understanding) "related" transactions are those that were _not_ chosen, but have ancestors that were. And the way we update such transactions' ancestor sets is to pretend that the chosen transactions are no longer in the mempool, as if they have already been mined.  

---

### Answer by username_1 on 2022-06-24. Score: 10

Just adding onto username_4'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](https://github.com/bitcoin/bitcoin/blob/f697c068ebd0dfea552c1ff192dfd9d520f1ca9a/src/txmempool.h#L458-L488) of this data structure and the [Boost multi index container reference](https://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/reference/index.html).

> **Comments:**
> **username_2**: Welcome username_1!  
> **username_3**: Woop woop! Instant upvote :)  

---

