If we run the getrawmempool true
RPC, we can look at the data Bitcoin Core has for each of its mempool transactions. Here's an example:
"3a0af489e500322159db85ad95174ffa3dd9924dbd0b68b041364a8c8eac03cc": { "size": 226, "fee": 0.00001130, "modifiedfee": 0.00001130, "time": 1507465582,
"height": 488876,
"descendantcount": 24,
"descendantsize": 5412,
"descendantfees": 27120,
"ancestorcount": 2,
"ancestorsize": 451,
"ancestorfees": 2260,
"depends": [
"3da9c837b8560eadea2f8c48a050e9dd3f4d7637b5209bdf98c19175906529bb"
]
},
Notice the ancestorsize
and ancestorfees
fields. These represent the total byte size and fees for this transaction and all of its ancestors. It's then simple to divide the fee by the bytes and produce a sorted list to find which transaction pays the best feerate (fee per byte), including its ancestors.
Then the remaining transactions can have have their ancestor feerate recalculated by removing from consideration whichever transactions were added to the block proposal above, have those new feerates sorted, and find the new best feerate transaction including its ancestors. Repeat this step until the block proposal has less remaining space than any of the transactions in the mempool.
Calculating these ancestor sizes and fees is pretty fast: you don't need to calculate the values for every ancestor, you just grab the values from your immediate ancestors (which already have all of their ancestors factored in) and then add the current transaction's values to that.
Also, to keep things fast, Bitcoin Core only looks at transaction chains of depth 25 or less.
For more information, this is the patch that added CPFP to Bitcoin Core. It's relatively short and quite well commented.