5

When there is a transaction with more descendants, does CPFP policy look through all possible combination of descendants to consider "together", to find which one has the best fee?

For example, when there is a dependency graph, looking like this

simple dependency graph

there are 6 possibilities to consider for A - {A}, {A, B}, {A, B, C}, {A,C}, {A,C,D}, {A,B,C,D}. Does CPFP miner look through all of them?

In this graph, there will be 25 such combinations, if I count correctly. Would bitcoin core look through all of them?

more complex graph

Improve this question
2
  • One can read the code. But there is no way it literally considers all combinations. A block with, say, 10000 transactions would have up to 2^10000 combinations.
    – Nate Eldredge
    Oct 8, 2017 at 14:59
  • I don't understand the code enough. There are not that many dependent transactions in mempool
    – Karel Bílek
    Oct 8, 2017 at 15:08

1 Answer 1

Reset to default
4
+250

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.

Improve this answer
4
  • Thanks for the answer; I will accept when I am at home and have time to read through thoroughly, but it looks good. I haven't understood the code in either the original Luke-Jr code or in the new one, since they seem too technical to me
    – Karel Bílek
    Oct 8, 2017 at 16:03
  • Shouldn't it be "including fees of its descendants" instead of ancestors? Child pays for parent, so you should be interested in the descendants, no?
    – Karel Bílek
    Oct 8, 2017 at 16:06
  • 2
    @KarelBílek it's ancestors. Per consensus rules, child transactions can only be added to a block if their parents are in the same block or an earlier block, so CPFP means a child pays a high fee in order to get its low-fee ancestors confirmed. A high-fee ancestor does nothing towards having its low-fee descendants confirmed.
    – David A. Harding
    Oct 8, 2017 at 16:32
  • 1
    Oh OK, I had it reversed. I thought that for each transaction, you check its descendants, if they pay for it. But it's the other way, for each transaction, you check its ancestors, if it pays for them. Cool
    – Karel Bílek
    Oct 8, 2017 at 17:15

Your Answer

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

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