<p>If we run the <code>getrawmempool true</code> RPC, we can look at the data Bitcoin Core has for each of its mempool transactions.  Here's an example:</p>

<p><code>"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"
    ]
  },
</code></p>

<p>Notice the <code>ancestorsize</code> and <code>ancestorfees</code> 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.</p>

<p>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.</p>

<p>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. </p>

<p>Also, to keep things fast, Bitcoin Core only looks at transaction chains of depth 25 or less.</p>

<p>For more information, <a href="https://github.com/bitcoin/bitcoin/pull/7600/files" rel="nofollow noreferrer">this is the patch</a> that added CPFP to Bitcoin Core.  It's relatively short and quite well commented.</p>

CC BY-SA 3.0
2017-10-08T16:03:07.753Z
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
CC BY-SA 3.0
2017-10-08T16:06:09.413Z
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
CC BY-SA 3.0
2017-10-08T16:32:54.837Z
@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
CC BY-SA 3.0
2017-10-08T17:15:45.393Z
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
CC BY-SA 3.0
2017-10-08T15:56:17.663Z
2017-10-08T15:56:17.663Z
David A. Harding
<p>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?</p>

<p>For example, when there is a dependency graph, looking like this</p>

<p><a href="https://i.sstatic.net/6ROAF.png" rel="noreferrer"><img src="https://i.sstatic.net/6ROAF.png" alt="simple dependency graph"></a></p>

<p>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?</p>

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

<p><a href="https://i.sstatic.net/qxu1J.png" rel="noreferrer"><img src="https://i.sstatic.net/qxu1J.png" alt="more complex graph"></a> </p>

CC BY-SA 3.0
2017-10-08T14:59:46.417Z
One can read [the code](https://github.com/bitcoin/bitcoin/blob/master/src/miner.cpp).  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
CC BY-SA 3.0
2017-10-08T15:08:25.650Z
I don't understand the code enough. There are not that many dependent transactions in mempool
Karel Bílek
<bitcoind><transaction-fees><mempool><child-pays-for-parent>
Does miner with CPFP look through all the possible combinations of descendants to find the one with the highest fee?
Karel Bílek
# Does miner with CPFP look through all the possible combinations of descendants to find the one with the highest fee?

(Asked by: username_0 on 2017-10-06)

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](https://i.sstatic.net/6ROAF.png)](https://i.sstatic.net/6ROAF.png)

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](https://i.sstatic.net/qxu1J.png)](https://i.sstatic.net/qxu1J.png)

**Tags:** bitcoind, transaction-fees, mempool, child-pays-for-parent

> **Comments:**
> **username_1**: One can read [the code](https://github.com/bitcoin/bitcoin/blob/master/src/miner.cpp).  But there is no way it literally considers all combinations.  A block with, say, 10000 transactions would have up to 2^10000 combinations.  
> **username_0**: I don't understand the code enough. There are not that many dependent transactions in mempool  

---

## 1 answers

### Answer by username_2 on 2017-10-08. Score: 4 | Accepted answer

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](https://github.com/bitcoin/bitcoin/pull/7600/files) that added CPFP to Bitcoin Core. It's relatively short and quite well commented.

> **Comments:**
> **username_0**: 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  
> **username_0**: 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?  
> **username_2**: @username_0 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.  
> **username_0**: 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  

---

