This PR is another attempt to fix #27995 using a better approach.

For background and motivation, see #27995 and the discussion in the Delving Bitcoin post Mempool Based Fee Estimation on Bitcoin Core
This PR is currently limited to using the mempool only to lower what is recommended by the Block Policy Estimator.
Accurate and safe fee estimation using the mempool is challenging. There are open questions about how to prevent mempool games that are theoretically possible for miners (a variant of the Finney attack)

This is one of the reasons I opted to use the mempool only to lower the Block Policy Estimator, which itself is not gameable, and therefore this mechanism is not susceptible to this attack.

The underlying assumption here is that, with the current tools and work done to make RBF and CPFP feasible and guarantee (TRUC transaction relay, ephemeral anchors, cluster size 2 package rbf), it is safer to underestimate rather than overestimate.
We now assume it is relatively easy to fee-bump later if a transaction does not confirm, whereas once a fee is overestimated there is no way to recover from that.

Another open question when using the mempool for fee estimation is how to account for incoming transaction inflow.
Bitcoin Augur does this by using past inflow plus a constant expected inflow to predict future inflow. I find this unconvincing for fee estimation and potentially prone to more overestimation, as past conditions are not always representative of the future. See my review of the Augur fee rate estimator and open questions.

This PR uses a much simpler approach based on current user behavior, similar to the widely used method employed by mempool.space: looking at the top block of the mempool and selecting a percentile feerate depending on whether the user is economical or conservative.

Empirical data from both myself and Clara Shikhelman shows that the 75th percentile feerate for economical users and the 50th percentile feerate for conservative users provide positive confirmation guarantees, hence this is what is used in this PR.

Parallel research by René Pickhardt and his student suggests that using the average fee per byte of the block template performs well.

All of these are constants that can be adjusted, there is parallel work exploring these constants and running benchmarks across fee estimators to find a sweet spot.

See also work in LND, the LND Budget Sweeper, which applies this idea successfully. Their approach is to estimate fees initially with bitcoind, then increment gradually as the confirmation deadline approaches, using a fixed fee budget.

Historical data indicates that by doing only the approach in this PR, we are able to reduce overestimation quite significantly (~29%).

This is particularly useful in scenarios where the Block Policy Estimator recommends a high feerate while the mempool is empty.

As seen in the image above, there is only one remaining unfixed case: when there is a sudden inflow of transactions and the feerate rises, the Block Policy Estimator takes time to reflect this. In that case, users will continue to see a low feerate estimate until it slowly updates. From the historical data linked above, this occurs about ~26% of the time).

Overall, we observe a 73% success rate with 0% overestimation, and 26% underestimation with this approach.

This PR also includes refactors that enable this work. Rather than splitting the PR and implementing changes incrementally, I opted for an end-to-end implementation:

1. Refactors

• Separation of feerate format from the fee estimate mode enumerator (separation of concerns, as they are semantically distinct)
• Move logging after fee estimation estimateSmartFee from the wallet to the Block Policy Estimator internal method (also separation of concerns and avoiding leaking fee estimator internals). This change also comes with updating createTransactionInternal to log only the fee and its source (fee estimator, fallback fee, etc.), which is more appropriate.
• Separate the fee estimate mode enum from the fee source enumerator (separation of concerns, as they are semantically distinct). This introduces a minor breaking change: the wallet RPCs now return fee source instead of fee reason, which is more accurate. Let me know if we prefer to keep the field name unchanged while returning the fee source.
• Move the StringForReason enum from common to the Block Policy Estimator (also separation of concerns)
• Various test file updates and renames for improved accuracy
• Update Block Policy Estimator unit tests to be independent of the mempool and the validation interface

2. Introduce Mempool-Based Fee Estimator and Fee Estimator Manager

• Introduce a new abstract fee estimator base class that all fee estimators must implement

• Introduce FeeRateEstimateResult as the response type, containing metadata and avoiding the use of out-parameters. This is easily extensible and makes future changes less invasive, as method signatures do not need to change.

• Add FeeEstimatorType enum to identify different fee estimators

• Make CBlockPolicyEstimator derive from the new fee estimator base class

• Add FeeRateEstimatorManager, responsible for managing all fee estimators

• Update the node context to store a unique_ptr to FeeRateEstimatorManager instead of CBlockPolicyEstimator

• Update CBlockPolicyEstimator to no longer subscribe directly to the validation interface; instead, FeeRateEstimatorManager subscribes and forwards relevant notifications

• Add a percentile calculation function that takes the chunk feerates of a block template and returns feerate percentiles; this can also be reused by the getblockstats RPC

• Add a mempool fee estimator that generates a block template when called, calculates a percentile feerate, and returns the 75th percentile for economical mode or the 50th percentile for conservative mode

• Add caching to the mempool estimator so that new estimates are generated only every 7 seconds, assuming enough transactions have propagated to make a meaningful difference.
  This heuristic will likely be replaced by requesting block templates via the general-purpose block template cache proposed here: RFC: Bitcoin Core Node BlockTemplateManager #33389

• Update MempoolTransactionRemovedForBlock to return the actual block transactions as well

• Track the weight of block transactions and evicted transactions after each block connection
  This data is tracked for the last 6 mined blocks. A mempool feerate estimate is returned only when the average ratio of mempool transaction weight evicted due to BLOCK reasons to block transaction weight is greater than 75%. This heuristic provides rough confidence that the node’s mempool matches that of the majority of the hashrate. The 75% threshold is arbitrary and can be adjusted.

There is a caveat when transactions in the local mempool are consistently not mined by the network, as described in #27995 (e.g., due to filtering).
Accounting for these transactions during fee estimation is not necessary, as they should be evicted from the mempool itself (see #33510). Handling this again within fee estimation would be redundant.

• Persist statistics for the 6 most recent blocks to disk during periodic flushes and shutdown, so this data is available after restarts
• Expose this data to users when running estimatesmartfee with verbosity > 2

bitcoin-cli estimatesmartfee 1 "conservative" 2

{
  "feerate": 0.00002133,
  "errors": [],
  "blocks": 2,
  "mempool_health_statistics": [
    {
      "block_height": 927953,
      "block_weight": 3991729,
      "mempool_txs_weight": 3942409,
      "ratio": 0.987644451815241
    },
    ...
  ]
}