RPC: `getblockstats` might not return the *effective* percentile fee rate #31140

One of the responses from the getblockstats RPC is feerate_percentiles, which returns the following:

"feerate_percentiles": [    (json array, optional) Feerates at the 10th, 25th, 50th, 75th, and 90th percentile weight unit (in satoshis per virtual byte)
  n,                         (numeric) The 10th percentile feerate
  n,                         (numeric) The 25th percentile feerate
  n,                         (numeric) The 50th percentile feerate
  n,                         (numeric) The 75th percentile feerate
  n                          (numeric) The 90th percentile feerate
]

Currently, the implementation simply appends the fee rates of all transactions in a block along with their corresponding weights to a vector, and then returns the percentile fee rates. https://github.com/bitcoin/bitcoin/blob/ffe4261cb0669b1e1a926638e0498ae5b63f3599/src/rpc/blockchain.cpp#L2027-L2030

However, the fee rate of a transaction at a given percentile may not reflect its effective fee rate, as it could be fee-bumped by some descendant transactions.

To address this, transactions within a block that are not independent should first be linearized using an ancestor-based linearization algorithm, for example using MiniMiner. This approach would be similar to what's done in #30079.

Note: MiniMiner will change alot due to #30289, which introduces a new form of linearization. While I assume linearization will still be supported in MiniMiner for mempool transactions, I'm unsure about support for linearizing non-mempool transactions.

A more efficient approach would be to persist previous block package data. With this approach, I don't see any reason to support linearizing non-mempool transactions in MiniMiner for now. While this would increase resource usage, I believe the trade-off is justified when compared to the complexity of linearizing clusters on the fly.

Having this package data available from disk would be very helpful for both this issue and #30079.

I hope this doesn't sound too dismissive, but who uses this and what are they using it for? Can we delete these fields or the whole RPC? To visualize stats, I think using getblock to obtain the fees and sizes for each transaction is much more flexible and appropriate (though tbf I don't think this was the case when #10757 was originally opened).

Separately, linearizing and chunking transactions (whether it's a block or something else) is pretty complicated and perhaps worth exposing it or offering a tool (if there is demand).

A more efficient approach would be to persist previous block package data. With this approach, I don't see any reason to support linearizing non-mempool transactions in MiniMiner for now. While this would increase resource usage, I believe the trade-off is justified when compared to the complexity of linearizing clusters on the fly.

Having this package data available from disk would be very helpful for both this issue and #30079.

For #30079, I don't think we need to linearize the received block after #30289, as we will be tracking chunks. After receiving a new block, we will obtain the chunk fee rate of those block transactions from the mempool when the entire chunk transactions is in the block cc @sipa

Separately, linearizing and chunking transactions (whether it's a block or something else) is pretty complicated and perhaps worth exposing it or offering a tool (if there is demand).

This has also been proposed by @ajtowns here. The complexity of linearization arises because a block could be constructed as a single cluster, which cannot be optimally linearized due to the current cluster size limit. While this limit can be updated in the tool, the current linearization algorithm will likely be unable to optimally linearize it. but that's okay, I guess.

However, the fee rate of a transaction at a given percentile may not reflect its effective fee rate, as it could be fee-bumped by some descendant transactions.

The block's txs are put into feerate_array in order, but CalculatePercentilesByWeight sorts them by feerate, so if you have a block with txs at fee rates [5, 4, 3, 100, 2, 2, 1, 1, 1] it will be treated as [100, 5, 4, 3, 2, 2, 1, 1, 1], so even if the "100" is a child paying for the "5" and "4" txs, it will come first when calculating percentiles. Because of this sorting, "effective" feerate isn't really meaningful.

Because of this sorting, "effective" feerate isn't really meaningful.

When a child transaction (fee rate 100) is paying for parent transactions (fee rates 4 and 5), they should be considered as a single chunk with a combined fee rate (e.g., ~40). So instead of sorting as [100, 5, 4, 3, 2, 2, 1, 1, 1], a more accurate representation would be [40, 3, 2, 2, 1, 1]. This will provide a more accurate view (different percentile fee rate when they are sorted individually) that represents what fee rate users compete for at a certain block space percentile.