How does Bitcoin Core estimate the transaction fee?

Question

I want to know how Bitcoin-Core estimates the transaction fee and what factors it takes into account to estimatesmartfee. What is the formula that it uses? Can you also refer me Bitcoin Core files where I can find it's code.

Answer 1

Your client [1] will make use of transactions it relays to build an estimation : by caching it (and the block height) when it first sees it. It will later be able to tell how much time (# of blocks) it took for it to be confirmed.

To build a reliable estimation, it will fill "buckets" (basically, a pack of transactions sharing a common characteristic) according to the feerate paid by each transaction it relays.

When comes the time to estimate the feerate for a transaction to be included in block before a specified number of blocks, your client will check the percentage of transactions confirmed in each bucket (so, with transactions paying that much on average) during this period of time. It will return the feerate of the first bucket with a success (confirmed transaction) rate higher to the threshold [2].
This probability threshold is set by the second argument to estimatesmartfee (CONSERVATIVE | ECONOMICAL).

To quote the documentation by Alex Morcos (who coded most of the fee estimator) :

/** \class CBlockPolicyEstimator
The BlockPolicyEstimator is used for estimating the feerate needed
for a transaction to be included in a block within a certain number of
blocks.

At a high level the algorithm works by grouping transactions into buckets
based on having similar feerates and then tracking how long it
takes transactions in the various buckets to be mined. It operates under
the assumption that in general transactions of higher feerate will be
included in blocks before transactions of lower feerate. So for
example if you wanted to know what feerate you should put on a transaction to
be included in a block within the next 5 blocks, you would start by looking
at the bucket with the highest feerate transactions and verifying that a
sufficiently high percentage of them were confirmed within 5 blocks and
then you would look at the next highest feerate bucket, and so on, stopping at
the last bucket to pass the test.

The average feerate of transactions in this
bucket will give you an indication of the lowest feerate you can put on a
transaction and still have a sufficiently high chance of being confirmed
within your desired 5 blocks.

[1]: Talking about each node, it goes without saying that all nodes on the network don't share the same estimation (as there is no consensus on the mempools).

[2]: this is simplified, the CONSERVATIVE and ECONOMICAL parameters have technically an influence across buckets (target / 2, target, target * 2) but it's conceptually the same logic.

---

Going further, this is the best (without using easily malleable data) we can do with the information we have at broadcast time but it's clearly not enough from a UX perspective as you'll never be able to predict the feerate.

For example if multiple megabytes of transactions are broadcast at the same time you broadcast yours, fee estimation won't help you.
This is why replace by fee.