The Challenges of Bitcoin Transaction Fee Estimation

The Challenges of Bitcoin Transaction Fee Estimation

For the very 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 suitable.

Bitcoin Core’s default fee switched several times over the years as the bitcoin exchange rate enlargened, 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, tho’ 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 two thousand fifteen 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 dreamed to know what fee rate you should put on a transaction to be included in a block within the next five blocks, you would begin by looking at the bucket with the highest fee rate transactions and verifying that a reasonably high percentage of them were confirmed within five 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 adequately high chance of being confirmed within your desired five blocks.

More specifically, when a transaction comes in the mempool, it makes note of the current block height. When a fresh 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 overlooked.
  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 overlooked 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 enormously low fee rate transactions because higher fees are being paid out-of-band are also disregarded.

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

A user / software error in two thousand sixteen resulted in someone creating a transaction with a whopping three hundred 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 flawlessly 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 shove your transaction to the back of miners’ priority queue. You could prevent transactions from getting stuck by using Substitute By Fee, thus updating your “bid” as time progresses, tho’ that’s not a elementary solution for BitGo since we’re a multisig wallet; users would either have to comeback to BitGo and re-sign fresh transactions or we’d have to sign a entire 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 fresh 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 largest 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 almost 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 all of a sudden becomes unlikely to create transactions. The fee market can be volatile, but over longer time periods it tends to spike and lodge 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 excellent analysis of peak/off-peak cycles with regard to block space request.

At time of writing, low fee transactions (paying under fifty satoshis per byte) can usually get confirmed over the weekend, however we have noted that as of March two thousand seventeen 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 fresh 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 significant 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 skill there isn’t a single public fee estimate API that supports a block target of greater than twenty five blocks. For the purposes of UTXO consolidation, your block target should be exceptionally high because you’re looking to find the most savings rather than achieve a swift 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 significant to recall that all the providers of transaction creation software are challenging against each other in terms of fee estimate algorithms. At BitGo our purpose 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 Five,456 seconds (19% swifter)

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% swifter)

90% of non-BitGo txns were confirmed within 6,944 seconds

90% of BitGo txns were confirmed within Three,632 seconds (48% quicker)

Thus it looks like our fresh estimates are saving a bit less money but resulting in much better time-to-confirm spectacle. It’s also worth noting that due to the latest 70% exchange rate increase, the 16% satoshi/byte savings we witnessed 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 two thousand fifteen 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 almost 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 most likely desirable for the ecosystem to have a greater diversity of fee estimate algorithms and better implements 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 lightly see for abnormal activity. Perhaps someone will even build a “Bitcoin Average” aggregator for fee estimates! I suspect that it would be fairly similar to what Antoine is presently suggesting as a visualization on p2sh.info.

It’s a safe assumption that space on Bitcoin’s blockchain will proceed to be a scarce resource, and thus request will rise for supple 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 instruments that enable their users to lightly pay an adequate fee that matches their confirmation priority.

The Challenges of Bitcoin Transaction Fee Estimation

The Challenges of Bitcoin Transaction Fee Estimation

For the very 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 suitable.

Bitcoin Core’s default fee switched several times over the years as the bitcoin exchange rate enhanced, 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, however 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 two thousand fifteen 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 wished to know what fee rate you should put on a transaction to be included in a block within the next five blocks, you would begin by looking at the bucket with the highest fee rate transactions and verifying that a adequately high percentage of them were confirmed within five 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 reasonably high chance of being confirmed within your desired five blocks.

More specifically, when a transaction comes in the mempool, it makes note of the current block height. When a fresh 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 overlooked.
  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 disregarded 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 utterly low fee rate transactions because higher fees are being paid out-of-band are also overlooked.

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

A user / software error in two thousand sixteen resulted in someone creating a transaction with a whopping three hundred 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 ideally 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 thrust your transaction to the back of miners’ priority queue. You could prevent transactions from getting stuck by using Substitute By Fee, thus updating your “bid” as time progresses, however that’s not a plain solution for BitGo since we’re a multisig wallet; users would either have to come back to BitGo and re-sign fresh transactions or we’d have to sign a entire 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 fresh 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 largest 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 almost 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 abruptly becomes unlikely to create transactions. The fee market can be volatile, but over longer time periods it tends to spike and lodge 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 superb analysis of peak/off-peak cycles with regard to block space request.

At time of writing, low fee transactions (paying under fifty satoshis per byte) can usually get confirmed over the weekend, however we have noted that as of March two thousand seventeen 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 fresh 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 significant 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 skill there isn’t a single public fee estimate API that supports a block target of greater than twenty five blocks. For the purposes of UTXO consolidation, your block target should be amazingly high because you’re looking to find the most savings rather than achieve a swift 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 significant to reminisce that all the providers of transaction creation software are contesting against each other in terms of fee estimate algorithms. At BitGo our objective 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 Five,456 seconds (19% quicker)

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% swifter)

90% of non-BitGo txns were confirmed within 6,944 seconds

90% of BitGo txns were confirmed within Three,632 seconds (48% swifter)

Thus it looks like our fresh estimates are saving a bit less money but resulting in much better time-to-confirm spectacle. It’s also worth noting that due to the latest 70% exchange rate increase, the 16% satoshi/byte savings we eyed 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 two thousand fifteen 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 almost 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 very likely desirable for the ecosystem to have a greater diversity of fee estimate algorithms and better contraptions 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 lightly witness for abnormal activity. Perhaps someone will even build a “Bitcoin Average” aggregator for fee estimates! I suspect that it would be fairly similar to what Antoine is presently suggesting as a visualization on p2sh.info.

It’s a safe assumption that space on Bitcoin’s blockchain will proceed to be a scarce resource, and thus request will rise for pliable 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 instruments that enable their users to lightly pay an suitable fee that matches their confirmation priority.

Related video:

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *