5

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 here, and here).

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

1 Answer 1

6

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.

3
  • 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
    Jun 13, 2023 at 16:56
  • 2
    @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. Jun 14, 2023 at 11:18
  • 1
    @PieterWuille Got it. Thanks!
    – algo2043
    Jun 14, 2023 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.