Fees: add Fee rate Forecaster Manager

ismaelsadeeq commented at 9:42 pm on January 15, 2025: member

This PR implements the core component of #30392, introducing a new fee rate forecasting module. The primary addition is a ForecasterManager that coordinates multiple forecasting strategies to be able to provide better transaction fee rate predictions.

Key Changes

Refactoring of CBlockPolicyEstimator
- Renames fees to block_policy_estimator for clarity.
- Renamesfees_args to block_policy_estimator_args for clarity
- Renames policy_fee_tests to feerounder_tests also for clarity.
Addition of Fee Rate Forecasting Utility Structures
- Forecaster abstract class, serving as the base class for all fee rate forecasters.
- ForecastResult (the response from a Forecaster) with all metadata.
- ForecastType enum, identify and distinguish forecasters.
Introduce FeeRateForecasterManager class
- Adds the FeeRateForecasterManager class, responsible for managing all fee rate forecasters, including CBlockPolicyEstimator, which is now a forecaster.
- Updates the node context to hold a unique pointer to FeeRateForecasterManager instead of CBlockPolicyEstimator.
- Changes CBlockPolicyEstimator instance from unique_ptr to a shared_pointer, allowing it to be registered in the validation interface without requiring explicit unregistration during shutdown (current master behaviour). Registering for CBlockPolicyEstimator flushes also get a shared_pointer.
- Exposes a raw pointer of CBlockPolicyEstimator through FeeRateForecasterManager for compatibility with estimateSmartFee, friends, and node interfaces.
- Modifies CBlockPolicyEstimator to inherit from the Forecaster class and implement the pure abstract classes
Introduce MempoolForecaster class
- Adds the MempoolForecaster, which forecast the fee rate required for a transaction to confirm as soon as possible. It generates a block template and returns the 75th and 50th percentile fee rates as low-priority and high-priority fee rate forecasts.
- Implements caching for the last fee rate forecast, using a 30-second rate limit to avoid frequent block generation via the block assembler.

The FeeRateForecasterManager now includes a method ForecastFeeRateFromForecasters. This method polls forecasts from all registered forecasters and returns the lowest value. This behavior aligns with discussions and research outlined in this post. But the primary aim of the FeeRateForecasterManager is to be able to perform sanity checks and potentially apply heuristics to determine the most appropriate fee rate forecast from polled forecasters, for now it just return the lowest.

This PR also add unit tests for the classes.

DrahtBot commented at 9:42 pm on January 15, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31664.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31382 (kernel: Flush in ChainstateManager destructor by TheCharlatan)
#30079 (Fee Estimation: Ignore all transactions that are CPFP’d by ismaelsadeeq)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

In src/policy/fees/mempool_forecaster.cpp, error message reads
“Forecaster unable a fee rate due to insufficient data”
Replacement: “Forecaster unable to determine a fee rate due to insufficient data”
In src/policy/fees/forecaster_util.h, the comment for p95 says “// 5th percentile” but it should read “// 95th percentile”

DrahtBot added the label Needs rebase on Jan 22, 2025

ismaelsadeeq force-pushed on Jan 22, 2025

DrahtBot removed the label Needs rebase on Jan 22, 2025

glozow added the label TX fees and policy on Feb 12, 2025

in src/policy/fees/forecaster_man.cpp:50 in c6b94403bf outdated

45+            if (selected_forecast.Empty()) {
46+                // If there's no selected forecast, choose curr_forecast as selected_forecast.
47+                selected_forecast = curr_forecast;
48+            } else {
49+                // Otherwise, choose the smaller as selected_forecast.
50+                selected_forecast = std::min(selected_forecast, curr_forecast);

frankomosh commented at 2:32 pm on April 8, 2025:

from my understanding here, the manager is to always choose a forecast having the lowest high_priority fee rate from

0bool operator<(const ForecastResult& other) const { return m_response.high_priority << other.m_response.high_priority; }

assuming we have mempool congestion spikes or other time-sensitive operations, wouldn’t we have a problem with underpayment if we always taking the minimum fee estimate here?

ismaelsadeeq commented at 3:06 pm on April 8, 2025:

Good question, @frankomosh.

You’re right to think the lowest fee rate might be an underestimate during instant spikes.

This approach was specifically chosen to address the concern raised by @harding here: https://delvingbitcoin.org/t/mempool-based-fee-estimation-on-bitcoin-core/703/6.

Although the concern is currently theoretical, @harding raised a valid point, and it seems reasonable to use mempool forecasts to adjust or correct block policy forecasts.

Empirical data also shows that this approach maintains around 60% accuracy, which performs better than the current status quo for economical fee rate forecasts: https://delvingbitcoin.org/t/mempool-based-fee-estimation-on-bitcoin-core/703/8?u=ismaelsadeeq.

My goal is to fix these issues with the following steps:

Select the lower value between the mempool forecast and the block policy forecast.
Return the certainty level of the mempool fee rate forecast based on statistics from previous block data in the next PR after this — see the POC here: #30157.
Use fee rate forecast from forecaster manager in the wallet

Potential Next Steps

Ensure the mempool is not being manipulated, and use the mempool forecast even during congestion for ASAP fee rate estimates. / Or expose the mempool state so users can fee bump when congestion persists and they absolutely need to do so.
Switch to a more economical fee rate forecaster for the long term, because the current one pays more than necessary, as by quite a large margin see research https://bitcoin.stackexchange.com/questions/124227/utility-of-longterm-fee-estimation/.

frankomosh commented at 7:41 am on April 9, 2025:

Thanks, @ismaelsadeeq, for sharing more context on this topic. I now see and understand why you took this approach. I think that the plan for improvement is also solid.

In 1. Select the lower value between the mempool forecast and the block policy forecast. I appreciate the approach of selecting the lower value forecasters to avoid fee overpayment.

Additionally, I would like to ask if we could improve accuracy by implementing a weighted selection strategy based on confirmation targets (this is just theoretical thinking since I haven’t done any tests on it).

From the little context I have tried to gather, I see that different forecasters seem to do well in different scenarios i.e CBlockPolicyEstimator likely offers a more reliable estimates during periods of stability and for longer confirmation targets, while the MempoolForecaster might offer better predictions during rapid changes and for immediate confirmation targets of like (1-2 blocks).

Would it, therefore, be worth considering a more targeted approach where we prefer MempoolForecaster for short-term targets and gradually shift to CBlockPolicyEstimator for longer-term targets of 3+ blocks?

I think this could maintain the fee savings of your current approach while improving accuracy in time-sensitive scenarios where underpayment could have repercussions for users. Even if not for this PR, it might be something to consider for a future enhancement.

(Note that I’m making assumptions here and have not looked into the overhead of actually doing this.)

ismaelsadeeq commented at 10:04 am on April 9, 2025:

Mempool forecaster only provide fee rate forecast for 1-2 blocks. see MEMPOOL_FORECAST_MAX_TARGET constant in https://github.com/bitcoin/bitcoin/pull/31664/commits/c7cdeafd7045c794b289e2438cc60baeee7e6f69

ismaelsadeeq commented at 3:06 pm on April 8, 2025: member

There is going to be a review club tomorrow on this PR https://bitcoincore.reviews/31664 notes and questions are up

in src/policy/fees/forecaster_util.h:48 in c6b94403bf outdated

123+ * Represents the input for a parameter of fee rate forecaster.
124+ */
125+struct ConfirmationTarget {
126+    unsigned int value;
127+    ConfirmationTargetType type;
128+};

glozow commented at 5:04 pm on April 9, 2025:

Are there any specific ideas for another ConfirmationTargetType? The only type defined here is a number of blocks (which could just be an integer) so I’m wondering why the complexity?

ismaelsadeeq commented at 7:07 pm on April 9, 2025:

Yes, as is now, it might seem like overkill (though it will be useful in the future). This is just forward-looking I believe that, realistically, businesses and users care more about time in minutes or hours, etc.

So, I envision a fee rate forecaster that accepts input based on time in hours rather than blocks. For example: ‘Give me a fee rate that will allow my transaction to confirm within the next 4 hours.’

this is a wishful thinking for now; no concrete idea or even reviewable design about it I don’t have a strong opinion on this we can easily refactor and enable it when needed.

Happy to remove it if we prefer to keep only structures that are used immediately.

glozow commented at 7:48 pm on April 9, 2025:

If there aren’t any concrete ideas, it seems better to add the extra complexity if/when there is a reason to. fwiw I don’t see why translating between hours and blocks would require another target type?

ismaelsadeeq commented at 2:21 pm on April 13, 2025:

Fixed in recent push.

glozow added the label Review club on Apr 9, 2025

in src/policy/fees/block_policy_estimator.cpp:746 in 9355da6de4 outdated

741+    }
742+    // Note: size can be any positive non-zero integer; the evaluated fee/size will result in the same fee rate,
743+    // and we only care that the fee rate remains consistent.
744+    int32_t size = 1000;
745+    response.low_priority = FeeFrac(feerate_economical.GetFee(size), size);
746+    response.high_priority = FeeFrac(feerate_conservative.GetFee(size), size);

glozow commented at 6:11 pm on April 9, 2025:

this might just be a personal opinion, but “low priority” and “high priority” usually mean different block targets to me. people who are accustomed to the mempool.space wording might say the same. but really, here and in the MempoolForecaster, it’s a measure of how conservative/confident we are in our estimate no?

ismaelsadeeq commented at 6:54 pm on April 9, 2025:

Good point Yes, it will be better to maintain the conservative and economical name? Happy to update.

ismaelsadeeq commented at 2:22 pm on April 13, 2025:

This is fixed now.

ismaelsadeeq commented at 9:35 am on April 10, 2025: member

I will update the PR to address recent comments, I also want to remove some redundancy and restructure the commits.

in src/policy/fees/mempool_forecaster.cpp:31 in 5bd2220422 outdated

30@@ -31,6 +31,13 @@ ForecastResult MemPoolForecaster::EstimateFee(ConfirmationTarget& target)
31                                             target.value, MEMPOOL_FORECAST_MAX_TARGET, MEMPOOL_FORECAST_MAX_TARGET));
32     }
33 
34+    const auto cached_estimate = cache.get();

polespinasa commented at 2:35 pm on April 10, 2025:

Already commented during the review club but leaving a comment to make it easy to track.

The cache should not be returned when there is a chain reorganization. This can be done by simply checking if there was a reorganization during the last CACHE_LIFE window or by clearing the cache after a reorganization.

Personally, clearing the cache seems to me to be the best option, since the method can also be used for testing, as we may want to call the forecaster several times and do not want the cache to influence it.

ismaelsadeeq commented at 3:45 pm on April 25, 2025:

Even better, I modified CachedMempoolForecast to store the last known tip. Now, the mempool forecaster will only return the cached fee rate if the last known tip matches the current tip.

This also prevents a case where a cache exists but a new block has just been mined and the mempool has been cleared—in such cases, a new block template should be generated instead of using the cache.

Thanks for your review @polespinasa

ismaelsadeeq force-pushed on Apr 13, 2025

ismaelsadeeq commented at 2:28 pm on April 13, 2025: member

Forced pushed c6b94403bf9d5bf4fe9d5e5360b3d2c30a430d69..9455f2f0927014f2cc2495d432be635b58cc8fe2

I’ve made the following changes:

Rebased on master.
Reorganized the commits (refactor comes first).
Squashed the structure-related commits into one.
Addressed comments by @glozow.
Removed some redundancy and things that seemed like YAGNI.
Comparison of forecast results is now based on fee rate, and we now return "economical" by default—following comments by @polespinasa and @monlovesmango in the recent review club meeting.

DrahtBot added the label Needs rebase on Apr 14, 2025

fees: refactor: rename policy_fee_tests.cpp to feerounder_tests.cpp

- Also remame the test suite name to match the new name.

4187ad19c3

fees: refactor: rename fees to block_policy_estimator

- Also move it to policy/fees and update the includes

87f9d4af9d

fees: rename fees_args to block_policy_estimator_args

- Also move them to policy/fees/ and update includes
- Note: the block_policy_estimator_args.h include in block_policy_estimator_args.cpp was done manually.

7f7da59d65

fees: return current block height in `estimateSmartFee` 47f012dd9f

fees: add forecaster structures

i  - Forecaster abstract class is the base class of fee rate forecasters.
     Derived classes must provide concrete implementation
     of the virtual methods.

ii - ForecastResult struct represent the response returned by
     a fee rate forecaster.

iii - ForecastType will be used to identify forecasters.
      Each time a new forecaster is added, a corresponding
      enum value should be added to ForecastType.

Co-authored-by: willcl-ark <will@256k1.dev>

cbf568f564

fees: add ForecasterMan class

- Its a module for managing and utilising multiple
  fee rate forecasters to provide fee rate forecast.

- The ForecasterManager class allows for the registration of
  multiple fee rate forecasters.

Co-authored-by: willcl-ark <will@256k1.dev>

1ac79fc5a9

fees: make block_policy_estimator a forecaster b996a12cf4

fees: add block policy estimator to forecaster manager

- This changes `CBlockPolicyEstimator` to a shared pointer
  this gives us three advantages.
   - Registering to validation interface using shared pointer
   - Scheduling block policy estimator flushes using shared pointer
   - Registering block policy estimator to forecaster_man

f320b7c501

fees: add `forecastTypeToString` method

- This method converts a ForecastType enum to its
  string representation.

6bb23b1cae

fees: add `CalculatePercentiles` function

- The CalculatePercentiles function, given
  a vector of feerates in the order they were added
  to the block, will return the 25th, 50th, 75th,
  and 95th percentile feerates.

- Also add a unit test for this function.

95e678d578

fees: add `MemPoolForecaster` class

- The mempool forecaster uses the unconfirmed transactions in the mempool
  to generate a fee rate that a package should have for it to confirm as soon as possible.

Co-authored-by: willcl-ark <will@256k1.dev>

73e72cc129

test: add mempool forecaster unit test d8c2f8c2f0

ismaelsadeeq force-pushed on Apr 15, 2025

DrahtBot removed the label Needs rebase on Apr 15, 2025

ismaelsadeeq force-pushed on Apr 25, 2025

in src/policy/fees/mempool_forecaster.cpp:33 in ed220500c8 outdated

27@@ -28,6 +28,13 @@ ForecastResult MemPoolForecaster::ForecastFeeRate(int target, bool conservative)
28         return result;
29     }
30 
31+    const auto cached_estimate = cache.get_cached_forecast();
32+    const auto last_tip = cache.get_last_known_tip();
33+    if (cached_estimate && activeTip->nHeight == last_tip) {

polespinasa commented at 9:23 am on April 26, 2025:

I like the new approach!

What do you think about saving the hash and not the heigh? In case of a reorg we could be at the same height and think that nothing happened.

0if (chache_estimate && activeTip->phashBlock == last_tip)
1...

ismaelsadeeq commented at 1:06 pm on April 27, 2025:

Done.

fees: cache `MemPoolPolicyEstimator` forecasts

- Provide new forecast only when the time delta from previous
  forecast is older than 30 seconds.

- This caching helps avoid the high cost of frequently generating block templates.

Co-authored-by: willcl-ark <will@256k1.dev>

7bf7b212a5

fees: add `ForecastFeeRateFromForecasters` method

- Polls all registered forecasters and selects the lowest fee rate.

75e6bb5ada

ismaelsadeeq force-pushed on Apr 27, 2025

bitcoin deleted a comment on Apr 27, 2025

Fees: add Fee rate Forecaster Manager #31664

Key Changes

Code Coverage & Benchmarks

Reviews

Conflicts

LLM Linter (✨ experimental)