Prioritize transactions selection for block template inclusion by total fee for dependent transactions (CPFP)

[matheusd]

When you have a set of interdependent transactions in the mempool (eg: c spends utxos from b, which spends from a, all of them in the mempool), ideally the block template generation should take into account the total fee rate for the full set of transactions instead of just for each transaction individually.

This is also known as the Child Pays For Parent (CPFP) mechanism.

The main advantages of performing this are:

• Miners increase their profitability when the mempool has more transactions than fit into the next block. Instead of considering only individual transactions (which might leave high fee, dependent transactions on the mempool), miners select the most profitable chain of transactions for inclusion.

• Users can unstuck low fee transactions from the mempool by spending one of the utxos of that transaction with a new one using higher than average fee rate.

When implementing this, it's important to watch out for a possible exploit when building the block template: long transaction chains that don't entirely fit in the remaining size of the block. This could force a miner to include lower fee transactions, while stopping it short from including the final (high fee) transaction, while non-dependent (medium fee) transactions sit in the mempool.

The easiest way to implement this would be to include new fields in the txPrioItem struct to track total fee rate and size for the highest paying tx dependency chain for a given transaction, and then directly adjust the priority queue and block template generation function to account for this when selecting transactions for inclusion.

Another more complex alternative would be to change the mempool to directly track and maintain the dependency list, such that the NewBlockTemplate() wouldn't have to perform this calculation every time a new template is requested.

[sefbkn]

This is an interesting policy. To add on, rather than interdependent transactions a <- b <- c being calculated as a whole, each permutation should be ranked separately as

• a
• a <- b
• a <- b <- c

The tail of one chain may be ranked lower than the head of another. In the scenario where c is a low-rank transaction - low fee, low priority - it may be preferable to include a slice of the chain in the block while leaving the tail in the mempool. This would allow a miner to prefer high fee transactions in place of c while still considering a <- b.

[sefbkn]

Picking this one up.

[davecgh]

Resolved by #1829.