Improving fee estimation accuracy

sipa commented at 5:36 pm on June 28, 2023: member

The current fee estimation algorithm suffers from a number of issues that make it hard to use in the real world:

Because it’s solely based on historical data (looking at how long mempool transactions take to confirm), it cannot react quickly to changing conditions.
Because it’s aiming to match seen behavior rather than requirement, if some non-negligible fraction of users keeps paying a certain high feerate, it may try to match that, even if unnecessary for confirmation.

There exist alternative sources of information which could mitigate some of these issues, but they are not used for various reasons:

We could look at the feerate histogram of the current mempool, which can react much faster, though lacks information about the rate/feerate of transactions being added. It is not used, because in the presence of diverging network policy, it may give permanently and wildly wrong results. For example, a pre-taproot node won’t see taproot transactions entirely, and thus miss any feerate pressure they provide. In the other direction, If local policy is more lax than the network’s, our mempool may contain unconfirmable high-fee things that incorrectly are accounted for.
We could look at the rate and feerate of transactions entering the mempool currently, rather than only account for them when they confirm. This gives better predictive value, but suffers from the same problems as the previous point when policies differ.
We could look at the feerate of transactions in blocks, but this is trivially gameable by miners.

I wonder if it wouldn’t be possible to take the mempool-based approaches into account, but subjecting them to a sanity checks based on confirmation. More concretely:

We can look at what percentage of high-feerate mempool transactions confirm within a reasonable period of time. If that percentage is high, it’s unlikely we have a significantly diverging policy from the network’s aggregate policy. If it is too low, we may want to disable mempool-based fee estimation entirely.
We can keep a counter on transactions in the mempool that tracks how often we’d have expected it to be seen in a block, but didn’t. If that counter goes too high for a certain transaction, we could exclude it from feerate calculations. This can reduce issues with too lax local policy, but not the other way around.

Even with these safeguards, I don’t think it’s reasonable to use as a default feerate estimate (at least not for automatic feerate decisions without human intervention, like sendtoaddress and friends), but it could be a separately selectable estimation mode.

This issue is the result of a discussion with @Xekyo, @achow101, @adamjonas, and @mzumsande.

lontivero commented at 7:31 pm on June 28, 2023: contributor

Given the current fee rate estimation algorithm has no prediction power when the mempool conditions change, it is common to pay too little or too much, what is especially true while we increase the confirmation target.

In Wasabi we use the feerate histogram to “correct” the fee rate estimations provided by our node and to keep them between an acceptable range. There are many things that can be done but we just want to be sure our users participating in coinjoins don’t pay more than everybody else and also that they don’t pay too little and are among the top 200Mb txs, just to reduce the chances of been purged.

https://github.com/zkSNACKs/WalletWasabi/blob/6a7c8965cec291f41aab328a684ab8105653a8ac/WalletWasabi/Extensions/RPCClientExtensions.cs#L147

I think that something like this is not risky and it can improves the estimations by making them “safer”. Basically, the idea is to mimic what we humans do: look at the mempool and if the txs that pay more are paying 50s/b don’t pay 100s/b because it makes no sense, or at least it doesn’t in most of the cases.

ErikDeSmedt commented at 11:35 am on June 30, 2023: none

The highest paying transactions that are ‘stuck’ in the mempool are useful for fee estimation. For reasonably small transactions the fee is just below what you need to pay to get included.

This method isn’t affected by users who are over-paying and is robust against miners being paid out-of-band.

However, it does respond slowly to changes in mempool conditions

lontivero commented at 1:17 pm on June 30, 2023: contributor

Fee rates are a everyday discussion in many teams I guess. This is from today’s internal discussion about a problem in our UI regarding fees:

WaynePerth74 commented at 4:47 pm on July 8, 2023: none

free rate meed to be in union or better tet need to be unifited i would recomend dev team implament someting simulor to mempool.spoce

all so on asidenote i request dev team to reintraduce mining funchion to bitcoin core but have it mainly used for asic miners as cpu and gpu mining of bitcoin isnt safisent

glozow added the label Brainstorming on Jul 24, 2023

glozow added the label TX fees and policy on Jul 24, 2023

ismaelsadeeq commented at 9:26 am on October 2, 2023: member

Concept ACK

One approach to implementing a package-aware mempool-based fee estimator (Edit after #28762)

Process

Whenever we want to estimate fees for a confirmation target we:

Generate the fee rate histogram with the mempool transactions.
Aggregate the fee rates and their respective vsize values until reaching the desired confirmation target in terms of blocks: i) For a 1 block confirmation target, aggregate the highest fee rates until the sum of their vsize’s equals the maximum block weight. e.g For a 3-block confirmation target, do the step above thrice using the third aggregated fee rates.
Calculate the median fee rate of the confirmation target aggregated fee rates.
Take the median fee rate as the confirmation target fee rate.

Sanity check

Whenever a new block is connected, we create a new block template which will give us the list of transactions we expect to be included in the new block. This can be used for comparison (as a sanity check) vs miner-generated blocks, to give us more confidence that our mempool somewhat-closely resembles miner mempools and can be somewhat relied upon for fee estimation:
- Tracking the number of times we expect a transaction to be mined and it’s not.
- Track the number of times a high fee rate transaction is not confirmed. A transaction will be eligible to be high fee only if it’s greater than e.g. the median fee rate of transactions in the newly connected block?
To determine whether node policy diverges from the network’s aggregate policy we will:
1. Check that transactions we expect to be confirmed and are not (e.g. for up to three blocks) are below an as-yet undetermined threshold (10%?).
2. Check our mempool has seen another as-yet undetermined threshold % of the transactions in the last n (3?) blocks.
If both conditions are met, high fee-rate transactions in our mempool are getting confirmed, our mempool has likely not diverged from the global network aggregate policy.
Before generating any fee rate histogram we will:
1. exclude high fee rate transactions that failed to be included in block (e.g., three times) with all their descendants.

Implementation

Modify the mini_miner block-building algorithm to generate a fee rate histogram after building a block template (fee rate histogram is an array of fee rates along with their corresponding sizes, arranged in descending order, the higher fee rate listed first with their corresponding vsize)

Naive approach of generating fee rate histogram

Manually generate mempool transactions manual_entries and their descendants descendant_caches from CTxMempool, this has the downside of locking and mempool_cs while we go through the whole mempool transactions and their descendant.
Use manual_entries and descendant_caches to get fee rate histogram with mini miner.

Improved approach of generating fee rate histogram

Implement a mempool-based fee estimator that will subscribe to the validation interface (similar to the one done in CBlockPolicyEstimator #28368)
Create a parallel (lightweight) “mempool” of unconfirmed transactions with their fee rates, and descendants.
Use the lightweight mempool to get fee rate histogram from mini miner.
Modify mini miner to build a block template with a target visize and return the transactions of the block template it built.
We can use either the Naive or Improved appraoch to get the mempool transactions manual_entries and their descendants descendant_caches and generate a DEFAULT_BLOCK_MAX_WEIGHT block template.

Questions

Whenever we estimate fees with the naive approach we generate a fee rate histogram with the whole mempool, we are locking mempool cs and creating manual_entries and descendant_caches, is that efficient?
Every time a new block is connected we generate a block template to perform a sanity check with the naive approach this locks mempool cs to create manual_entries and descendant_caches, is that efficient?

We are building a normal block template with the default limit for this, the sanity checks execute in the background.

If this locking issue is a concern, to solve it I think the mempool-based fee estimator will have to implement the improved approach, which has the downside of creating another lightweight mempool, for a resource-constrained node, we can provide the option of turning it off?

The lightweight mempool DS might just be the cache of the mini miner constructor

0const std::vector<MiniMinerMempoolEntry>& manual_entries,
1const std::map<Txid, std::set<Txid>>& descendant_caches

MiniMinerMempoolEntry DS https://github.com/bitcoin/bitcoin/blob/f2cc718e6920b8c45be107e2eb5ac84c4b839e50/src/node/mini_miner.h#L25

This work is the result of some discussions with @willcl-ark @glozow

I would like to have feedback on the approaches before creating a PR.

LaurentMT commented at 4:28 pm on December 14, 2023: none

A minimalist implementation of the second idea (“look at the rate and feerate of transactions entering the mempool currently”): https://code.samourai.io/oxt/one_dollar_fee_estimator

From our observations, the estimator behaves rather well under current network conditions but as noted in the original post, no fee estimator should be used automatically without safeguards put in place.

npslaney commented at 2:52 pm on April 25, 2024: none

Bitcoin’s fee estimator is outdated for sure. For lightning channels, where some functionality depends on accurate fee estimation, fee spikes like what we had last week can make small channels that are typically usable unusable, and that effect lasts longer due to bitcoind’s fee estimation lagging what it actually takes to get into the next block.

Lightning peers have to agree on fees to an extent to function. We would love to pipe in our own fee estimation, but we are stuck in a lowest common denominator problem with bitcoind’s fee estimation the way it is currently. Making this better in bitcoind would go a long way to help (I understand not everyone will upgrade at once, but the incentive to upgrade will be great.)

Right now mempool.space’s fee estimation is very simple and open source, and is becoming the de facto standard for people sending one-off bitcoin transactions who have the ability / know to set a custom fee rate.