The following is the description of the algorithm used for the selection of the transactions to include in the block candidate as implemented in BU. This selection process is where the Child Pay For Parents (CPFP) bumping fee technique is executed.
Briefly CPFP is way for increase the likelihood of inclusion for transaction with a low feerate by spending at least one of its outputs with a new transaction with, usually, higher than needed feerate.
The bookkeeping of feerate / size/ sigops for ancestors and descendants of those chained transaction is where the main bottleneck is when it comes to selecting transactions to be included in a block candidate. This bookkeeping process will also impact the performance of the mempool admittance/evictions transactions process. Changes merged into BU code base have taken care of the selection step only. Feature enhancements will be carried out to also to improve the performance of mempool admission and post block processing.
We are going to start with describing the status quo, namely how the algorithm as implemented in Core/ABC. The selection algorithm goes like this:
- at mempool admission, calculate
feerate-with-ancestors1 andsize-with-ancestorsfor every transaction 2. - transactions in the mempool are selected from the mempool once sorted by
ancestor-scorewhich isfeerate-with-ancestors / size-with-ancestors. - the higher the
ancestors-scorethe higher the inclusion probability for the transaction will be. - add transaction's package3 to the block.
- as soon as a transaction is selected a new
feerate-with-ancestorsandsize-with-ancestorsis calculated for each of the in-mempool descendants that haven't yet been selected.
This last step is where the main part of the time is spent during transactions selection process.
What BU is actually doing is the exact same as Core does but the last point. BU does not recompute feerate-with-ancestor each descendants which has not been still selected.
This is the thing that bring us the improvement in performance.
The code that is used to traverse the mempool to define package of transactions is identical to the one used in Core/ABC, hence transactions packages are defined and handled in the same way as core during the definition step.
Again the very big difference is that the bookkeeping step (point 5 above) is executed significantly less times than what is used in Core during the selections process.
The simplification in computation complexity comes with some compromise that have to be taken in terms of fee maximization. For example there is a theoretical downside to this approach which could happen when a block is almost full.
We could for instance end up including a lower fee transaction as part of an ancestor group when in fact it would be better, in terms of fees, to include some other single transaction. This would result in slightly less fees (perhaps a few hundred satoshis) rewarded to the miner.
However, this situation is not likely to be seen for two reasons. 1), long unconfirmed chains are typically having transactions with all the same fees and 2), the typical child pays for parent scenario has only two transactions with the child having the higher fee. And neither of these two types of packages could cause any loss of fees with this mining algorithm, when the block is nearly full.
Assuming that the following transactions are 1 byte in size, the fee that pays are reported in the parenthesis and that an arrow (->) implies a parent/child relation and that a comma (,) implies that the following transaction is not linked to any previous listed transactions.
t1(5000)->t2(0), t3(2000)
The feerate-with-ancestor for these transactions are (ordered):
t1 5000
t2 2500
t3 2000
Let's assume for a moment that there's space for just 2 additional transactions in the block. According to what we said above BU will include t1 and t2 for a total of 5000 satoshis in fees where as Core would have included t1 and t3 for a total amount of 7000 satoshis in fees. This is happening because BU is not going to update t2 feerate-with-ancestor or size-with-ancestor after the inclusion of t1, on the other hand core would have done it and so that the new score for t2 would have been 0, whereas for t3 2000, hence t2 would be included.
There is another case where the performance improvements could be limited and has to be accounted for. Namely this happen when a child transaction has lower feerate than its parent which causes child transaction to show up later as we parse though the ancestor index. In this scenario we then have to recalculate the ancestor sigops and package size which can be time consuming given we have to parse through the ancestor tree each time.
However we get around that by shortcutting the process by parsing through only the portion of the tree that is currently not in the block. This shortcutting happens in _CalculateMempoolAncestors() where we pass in the inBlock vector of already added transactions. Even so, if we didn't do this shortcutting the current algorithm is still much better than the older method which needed to update calculations for the entire descendant tree after each package was added to the block.
[1] feerate-with-ancestor == the fee rate of a given transactions considering all ancestors as if they were a single transaction. ↩
[2] size-with-ancestor == the size of a given transactions added with the size of all ancestors as if they were a single transaction. ↩
[3] transaction plus its unconfirmed ancestors. ↩