The Challenges of Bitcoin Transaction Fee Estimation

The History of Bitcoin Transaction Fees

For the first several years of bitcoin’s existence, transaction fees were optional — they were considered a donation to miners.

Wallets paid the same fee on every transaction — defaulting to whatever fee the wallet developer thought was appropriate.

Bitcoin Core’s default fee changed several times over the years as the bitcoin exchange rate increased, from 0.01 BTC to 0.0005 BTC to 0.0001 BTC. There were also rules around “priority transactions” that enabled users to send transactions with no fee if the inputs were old and high value enough, though miners phased them out in early 2016.

I covered the history of Bitcoin transaction fees and how it led to the current state of our fee market in this CoinDesk article. BitGo implemented dynamic fees in July 2015 and now, two years later, we are still working on improving our fee estimate algorithms.

Bitcoin Core’s Fee Estimation

At BitGo, we use Bitcoin Core’s fee estimation algorithm to extract baseline data for our own fee estimation algorithm. Core’s logic can be found here.

At a high level the algorithm works by grouping transactions into fee rate buckets and then tracking how long it takes transactions in the various buckets to be mined. It operates under the assumption that transactions paying higher fee rates will be included in blocks before transactions with lower fee rates. For example, if you wanted to know what fee rate 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 fee rate transactions and verifying that a sufficiently high percentage of them were confirmed within 5 blocks. Then you would look at the next highest fee rate bucket, and so on, stopping at the last bucket to pass the test. The average fee rate of transactions in this bucket will give you an indication of the lowest fee rate you can pay while still having a sufficiently high chance of being confirmed within your desired 5 blocks.

More specifically, when a transaction enters the mempool, it makes note of the current block height. When a new block arrives, it counts the number of transactions in each bucket and the total amount of fee rate paid in each bucket. Then it calculates how many blocks (Y) it took each
transaction to be mined and tracks an array of counters in each bucket for how long it to took transactions to get confirmed and increments all the counters from Y up to the highest bucket. This is because for any number Z >= Y the transaction was successfully mined within Z blocks.

This methodology prevents the fee estimates from being skewed by several potential problems:

1. If some users are unnecessarily paying exorbitant fees, they will be ignored.
2. Miners may stuff their blocks with high fee rate transactions that cost them nothing to create, since they are paying themselves. These transaction will be ignored if the miner isn’t broadcast them as unconfirmed, which would decrease their strategy’s ROI because they’d be paying other miners the fees as well.
3. Miners confirming some extremely low fee rate transactions because higher fees are being paid out-of-band are also ignored.

It’s important to protect your fee algorithm from adversarial conditions or even from outlier data. For example:

A user / software error in 2016 resulted in someone creating a transaction with a whopping 300 BTC fee. This had ripple effects:

Improving Upon Core’s Estimates

If a fee estimate algorithm fails to correctly predict the future state of the fee market then transactions can get stuck. This can occur if you broadcast a transaction with a perfectly reasonable fee for the current market conditions, but before the next block is mined, many other higher fee transactions get broadcast by other users, which essentially push your transaction to the back of miners’ priority queue. You could prevent transactions from getting stuck by using Replace By Fee, thus updating your “bid” as time progresses, though that’s not a simple solution for BitGo since we’re a multisig wallet; users would either have to return to BitGo and re-sign new transactions or we’d have to sign a whole bunch of transactions up front. On that note, Bitcoin Core developers have been discussing doing just that with “precomputed fee bumping.”

Another method for correcting low-fee transactions is to use Child Pays For Parent, where you add much larger fees to new transactions that spend outputs of your stuck low-fee transactions. This incentivizes miners to prioritize confirming the entire set of your transactions. We’re excited to announce that BitGo has implemented CPFP functionality and is exploring ways to make it more user-friendly.

One of the biggest flaws in Core’s fee estimate algorithm is that it only uses historical data and thus can’t adjust quickly if the fee market becomes volatile. Improvements can be made that incorporate forward-looking data by examining unconfirmed transactions in the mempool. This is how BitGo implemented its “surge pricing” in 2015. By using mempool data you can bump up fees during times that the mempool grows in size and pull down fees during times that the mempool is nearly empty.

Services that create bitcoin transactions should also set minimum fee thresholds and maximum fee sanity checks, preferably dynamically. If you set a static maximum fee threshold and it becomes obsolete, you may find yourself in an emergency situation where you or your users have to upgrade software because it suddenly becomes impossible to create transactions. The fee market can be volatile, but over longer time periods it tends to spike and settle in a somewhat predictable range while remaining in an upward channel.

It’s also worth noting that the fee market has cyclical variance day by day and week by week. Kaiko published a great analysis of peak/off-peak cycles with regard to block space demand.

At time of writing, low fee transactions (paying under 50 satoshis per byte) can usually get confirmed over the weekend, though we have noted that as of March 2017 sometimes there is no weekend slack. As far as we’re aware, no fee estimation algorithms take these cycles into account.

Also, there are a lot of “magic numbers” in Core’s estimate algorithm. They have been chosen to be as conservative and useful for the average user as possible. But just as many people use Bitcoin for many different things, so do different users have different needs in terms of confirmation times. Eventually we’d like to see more configuration options exposed within Bitcoin Core so that enterprise users can have more control over how their fee estimates are calculated. As this article was being written, Bitcoin Core contributor Alex Morcos released code to overhaul the fee estimate algorithm and additionally expose more tunable options via new RPC calls!

There is one common use case that receives little to no discussion: finding the minimum viable fee for the lowest priority sends. This becomes important for enterprise wallets that receive high volumes of low value outputs. Eventually they have to consolidate these outputs so that they can spend the value in regular transactions. To my knowledge there isn’t a single public fee estimate API that supports a block target of greater than 25 blocks. For the purposes of UTXO consolidation, your block target should be incredibly high because you’re looking to find the most savings rather than achieve a fast confirmation. That’s why I’m pleased to announce that BitGo now supports fee estimates up to block targets of 1,000! You can view our 1,000 block target estimate here.

The Fee Estimate Ecosystem

It’s important to remember that all the providers of transaction creation software are competing against each other in terms of fee estimate algorithms. At BitGo our goal is to underbid median fee rates and overperform transaction confirmation times. Here’s a snapshot of a Monday (the busiest day of the week) in March where we compared our transactions against the rest of the network:

The median non-BitGo txn paid a fee rate of 190 satoshis per byte
The median BitGo txn paid 159 satoshis per byte (a 16% savings)
The median BitGo txn paid lower fees than 62% of all non-BitGo txns

The median non-BitGo transaction was confirmed in 574 seconds
The median BitGo transaction was confirmed in 608 seconds (6% slower)

90% of non-BitGo txns were confirmed within 6,748 seconds
90% of BitGo txns were confirmed within 5,456 seconds (19% faster)

Because transaction fee rates have continued to rise dramatically in 2017, I spent some time in April working overhauling our fee estimate system once again.

Running our internal metrics again, this time against a Monday in May:

The median non-BitGo txn paid a fee rate of 193 satoshis per byte
The median BitGo txn paid 174 satoshis per byte (a 9% savings)
The median BitGo txn paid lower fees than 62% of all non-BitGo txns

The median non-BitGo transaction was confirmed in 590 seconds
The median BitGo transaction was confirmed in 522 seconds (12% faster)

90% of non-BitGo txns were confirmed within 6,944 seconds
90% of BitGo txns were confirmed within 3,632 seconds (48% faster)

Thus it looks like our new estimates are saving a bit less money but resulting in much better time-to-confirm performance. It’s also worth noting that due to the recent 70% exchange rate increase, the 16% satoshi/byte savings we saw in March is actually about the same as the 9% savings in May in USD terms. A 9% savings doesn’t sound like much, but for our high transaction volume customers this can result in saving thousands of dollars per month.

Back in 2015 when we were running this analysis, our numbers were much more performant — we’d routinely undercut the rest of the network by 40% on fees and still achieve similar confirmation times. However, the rest of the wallets in the ecosystem have since developed and improved upon their own fee estimate algorithms, making the fee market more competitive. You can see that the percentage of transactions using dynamically calculated fees has risen from about 15% to nearly 90%. The fee market is much more competitive than it used to be.

If we accept the premise that competition is healthy for free markets, then it behooves all bitcoin transaction creators to make their fee estimates accessible via public APIs. It’s also probably desirable for the ecosystem to have a greater diversity of fee estimate algorithms and better tools to perform backtesting on them. I suspect that the fee estimate algorithms themselves will often remain closed source, but if the estimates are public then we can more easily watch for abnormal activity. Perhaps someone will even build a “Bitcoin Average” aggregator for fee estimates! I suspect that it would be quite similar to what Antoine is currently offering as a visualization on p2sh.info.

It’s a safe assumption that space on Bitcoin’s blockchain will continue to be a scarce resource, and thus demand will rise for flexible and competitive fee estimate algorithms. Much like with the challenges of unspent outputs selection, there is no “one size fits all” solution. It’s the responsibility of transaction creation software developers to build tools that enable their users to easily pay an appropriate fee that matches their confirmation priority.