<p>This is intended to be a performance optimization when generating a block template for mining. The issue is around how many transactions we end up looking at while iterating over the mempool during block construction.</p>
<p>At a high level, the mempool sorts transactions by ancestor feerate, and in the mining algorithm we iterate over those transactions in descending ancestor feerate order to select transactions for a block. As we select transactions, we have to do some bookkeeping to update the new ancestor scores of descendants of those transactions (to reflect only the ancestors that are not yet selected), but because we can't modify the mempool when constructing blocks, we still <em>look</em> at each transaction in the same order it appears in the mempool.</p>
<p>So if the mempool were to sort a child transaction based on an ancestor feerate that is higher than its own feerate, you might expect that it has some higher feerate parent that would be selected first, and therefore the child's ancestor feerate would overstate its true mining score. This in turn would mean that we might look at many more transactions from the mempool than should be necessary when constructing a block, because those children would appear earlier in the mempool's sort, so we'd look at them only to decide that the true feerate is lower than indicated.  Instead, we try to
avoid this scenario by sorting transactions based on the minimum of the two feerates.</p>
<p>The implementation details are somewhat more involved than I described; see <a href="https://github.com/bitcoin/bitcoin/blob/d80348ccb65601d19b4b408d442e0999b5a6cf98/src/node/miner.cpp#L292C1-L429" rel="noreferrer">https://github.com/bitcoin/bitcoin/blob/d80348ccb65601d19b4b408d442e0999b5a6cf98/src/node/miner.cpp#L292C1-L429</a> for the full mining logic.</p>

CC BY-SA 4.0
2023-06-13T16:56:45.553Z
I'm not sure if I understand your answer, if this were only an optimization matter, then, the ordering of the transactions with the ancestor score ordering would be the same as the ordering with ancestor fee, but this is not the case.


Also, you say that if the ancestor fee rate is higher than the ancestor score, then there is an ancestor with higher ancestor fee rate, but then again this is not the case (a transaction diamond with appropriate weights and fees show the contrary).
algo2043
CC BY-SA 4.0
2023-06-14T11:18:52.033Z
@algo2043 Ignoring diamonds, I believe it is just an optimization: while the sort order is different, any case where the child has a lower feerate than the parent will have their parent included before, and thus during actual block building the child's ordering won't be what matters anymore (the local inside-block-building ordering of feerates-with-included-parents-removed will be used for the child), and the resulting block will be the same. With diamond structures present that is possibly not the case, but the mining logic is known to be suboptimal in that case anyway.
Pieter Wuille
CC BY-SA 4.0
2023-06-14T13:24:37.813Z
@PieterWuille Got it. Thanks!
algo2043
CC BY-SA 4.0
2023-06-13T03:17:00.193Z
2023-06-13T03:17:00.193Z
sdaftuar
<p>In Bitcoin Core’s implementation of the greedy knapsack algorithm to select transactions to go into a block for mining, the heuristic used to order transactions is based on an &quot;ancestor score&quot; which is the minimum between the ancestor fee rate of the transaction and the fee rate of the transaction itself (see <a href="https://github.com/bitcoin/bitcoin/blob/cf5bb048e80d4cde8828787b266b7f5f2e3b6d7b/src/txmempool.h#L224" rel="nofollow noreferrer">txmempool.h</a>, and <a href="https://bitcoinops.org/en/blog/waiting-for-confirmation/" rel="nofollow noreferrer">bitcoinops.org</a>).</p>
<p>Why is this a better heuristic than just using the ancestor fee rate?</p>

<bitcoin-core><mining-theory><bitcoin-core-development><miner-configuration><algorithms>
Why does Bitcoin Core’s algorithm uses ancestor score instead of just ancestor fee rate to select transactions?
algo2043
# Why does Bitcoin Core’s algorithm uses ancestor score instead of just ancestor fee rate to select transactions?

(Asked by: username_0 on 2023-06-12)

In Bitcoin Core’s implementation of the greedy knapsack algorithm to select transactions to go into a block for mining, the heuristic used to order transactions is based on an "ancestor score" which is the minimum between the ancestor fee rate of the transaction and the fee rate of the transaction itself (see [txmempool.h](https://github.com/bitcoin/bitcoin/blob/cf5bb048e80d4cde8828787b266b7f5f2e3b6d7b/src/txmempool.h#L224), and [bitcoinops.org](https://bitcoinops.org/en/blog/waiting-for-confirmation/)).

Why is this a better heuristic than just using the ancestor fee rate?

**Tags:** bitcoin-core, mining-theory, bitcoin-core-development, miner-configuration, algorithms


---

## 1 answers

### Answer by username_1 on 2023-06-13. Score: 6 | Accepted answer

This is intended to be a performance optimization when generating a block template for mining. The issue is around how many transactions we end up looking at while iterating over the mempool during block construction.

At a high level, the mempool sorts transactions by ancestor feerate, and in the mining algorithm we iterate over those transactions in descending ancestor feerate order to select transactions for a block. As we select transactions, we have to do some bookkeeping to update the new ancestor scores of descendants of those transactions (to reflect only the ancestors that are not yet selected), but because we can't modify the mempool when constructing blocks, we still *look* at each transaction in the same order it appears in the mempool.

So if the mempool were to sort a child transaction based on an ancestor feerate that is higher than its own feerate, you might expect that it has some higher feerate parent that would be selected first, and therefore the child's ancestor feerate would overstate its true mining score. This in turn would mean that we might look at many more transactions from the mempool than should be necessary when constructing a block, because those children would appear earlier in the mempool's sort, so we'd look at them only to decide that the true feerate is lower than indicated. Instead, we try to
avoid this scenario by sorting transactions based on the minimum of the two feerates.

The implementation details are somewhat more involved than I described; see <https://github.com/bitcoin/bitcoin/blob/d80348ccb65601d19b4b408d442e0999b5a6cf98/src/node/miner.cpp#L292C1-L429> for the full mining logic.

> **Comments:**
> **username_0**: I'm not sure if I understand your answer, if this were only an optimization matter, then, the ordering of the transactions with the ancestor score ordering would be the same as the ordering with ancestor fee, but this is not the case.   Also, you say that if the ancestor fee rate is higher than the ancestor score, then there is an ancestor with higher ancestor fee rate, but then again this is not the case (a transaction diamond with appropriate weights and fees show the contrary).  
> **username_2**: @username_0 Ignoring diamonds, I believe it is just an optimization: while the sort order is different, any case where the child has a lower feerate than the parent will have their parent included before, and thus during actual block building the child's ordering won't be what matters anymore (the local inside-block-building ordering of feerates-with-included-parents-removed will be used for the child), and the resulting block will be the same. With diamond structures present that is possibly not the case, but the mining logic is known to be suboptimal in that case anyway.  
> **username_0**: @username_2 Got it. Thanks!  

---

