Implement smart fee estimation (estimatesmartfee rpc endpoint)

[matheusd]

Bitcoin core has an estimatesmartfee rpc endpoint that allows users to use a fee other than the minimum relay fee in order to prioritize different parameters when publishing a transaction:

• Minimize Mining Delay by using a higher fee which is likely to make the transaction be picked up earlier by miners (but no higher than historically required for a given target confirmation window)
• Minimize fee rate by picking a longer target confirmation window

This estimation is "smart" in the sense that it tracks transaction mining times in the actual network and performs a probabilistic guess given as input a target confirmation window. This endpoint is important in the context of the lightning network (to estimate fees that maintain the LN invariants) and in an environment of increased network usage, where fee rates play an important role in deciding when a transaction is mined.

This issue is to propose adding a similar rpc endpoint to decred full nodes.

Preliminaries

There are two main regimes against which fee estimation needs to be evaluated according to how full blocks being mined are (and consequently how important fee rates are): low contention and high contention:

In a low contention regime, the mempool sits mostly empty, transactions are usually mined very soon after being published and transaction fees are mostly sent using the minimum relay fee.

In a high contention regime, the mempool is usually filled with unmined transactions, there is active dispute for space in a block (by transactions using higher fees) and blocks are usually full.

The exact point of where these two regimes intersect is arbitrary, but it should be clear in the examples and simulations which of these is being discussed.

Note: a very high contention scenario (> 90% of blocks being full and transactions remaining in the mempool indefinitely) is one in which stakeholders should be discussing alternative solutions (increase block size, provide other second layer alternatives, etc). Also, the current fill rate of blocks in decred is low, so while we try to account for this regime, I personally expect that the implementation will need more tweaks as it approaches this.

The suggested approach to implement this estimation is based on bitcoin core's algorithm. References [1] and [2] provide a high level description of how it works there. Actual code is linked in references [3] and [4].

Outline of the Algorithm

The algorithm is currently based in fee estimation as used in v0.14 of bitcoin core (which is also the basis for the v0.15+ method). A more comprehensive overview is available here.

This particular version was chosen because it's simpler to implement and should be sufficient for low contention regimes. It probably overestimates fees in higher contention regimes and longer target confirmation windows, but as pointed out earlier should be sufficient for current fill rate of decred's network.

The basic algorithm is as follows (as executed by a single full node):

Stats building stage:

• For each transaction observed entering mempool, record the block at which it was first seen
• For each mined transaction which was previously observed to enter the mempool, record how long (in blocks) it took to be mined and its fee rate
• Group mined transactions into fee rate buckets and confirmation ranges, creating a table of how many transactions were mined at each confirmation range and fee rate bucket and their total committed fee
• Whenever a new block is mined, decay older transactions to account for a dynamic fee environment

Estimation stage:

• Input a target confirmation range (how many blocks to wait for the tx to be mined)
• Starting at the highest fee bucket, look for buckets where the chance of confirmation within the desired confirmation window is > 95%
• Average all such buckets to get the estimated fee rate

Implementation and Simulation

A proof of concept implementation has been written in the dcrfeesim repo. It's currently completely separate from dcrd code in order to simplify testing and to ensure the general algorithm is correct before actually bringing it in.

This tool simulates various test cases including low and high contention, minimum and no minimum fees, changing the internal estimation parameters, etc. It makes some assumptions about the distribution of simulated transaction sizes, new transactions per block, etc, which may not be super accurate but which (eyeballing the current charts in dcrdata) seem reasonable to me and are easy to generate. Improvements on either determining the actual current distribution of these parameters and in generating them more accurately are welcome!

The individual test scenarios are described and the resulting data is stored in the results/ folder. For each test, the network is simulated for roughly 3 months, then an estimate is made as if an user wanted to post transactions at varying target confirmations.

Steps for Inclusion in dcrd

The estimation results seem roughly correct at the desired regimes. They have been reviewed by @davecgh, but given the importance of fee estimates for end users, this needs to be more thoroughly discussed with the community at large.

The next steps for inclusion of the estimatesmartfees rpc endpoint in dcrd are the following:

• [x] Public comments on the proposal
• [ ] Improve code in various ways (naming, memory usage, individual lower lower level algos, public API, etc)
• [x] Deal with edge cases
  • [x] Tx expired
  • [x] Ticket sdiff'ed out of the mempool
  • [x] Block invalidated
  • [x] Tx not finalized
  • [x] Reorgs
• [x] Integrate into the full node
  • [x] Hook into mempool
  • [x] Save/Restore on node shutdown/startup (dealing with stale data)
  • [x] Hook to rpc endpoint
• [ ] Integrate to wallet
  • [ ] in normal mode
  • [ ] In SPV mode?

Acknowledgements

Thanks to @davecgh for providing the initial review of the results and the original developers of bitcoin core code (the brunt of which seems to have been made by @morcos).

References

[1] Introduction to Bitcoin Core Estimation: https://bitcointechtalk.com/an-introduction-to-bitcoin-core-fee-estimation-27920880ad0

[2] Proposed Changes to Fee Estimation in version 0.15: https://gist.github.com/morcos/d3637f015bc4e607e1fd10d8351e9f41

[3] Source for fee estimation in v0.14: https://github.com/bitcoin/bitcoin/blob/v0.14.2/src/policy/fees.cpp

[4] Source for fee estimation in version 0.16.2: https://github.com/bitcoin/bitcoin/blob/v0.16.2/src/policy/fees.cpp

[davecgh]

Great work! I don't have too much to add that we didn't already cover via DMs prior to submission for public feedback.

I will say this is important for the LN work and it has the expected characteristics for smart fees:

• It doesn't allow PoW miners to trivially game it by mining high fee transactions to themselves in an effort to jack up the fees since they must have been seen the mempool which means the PoW miners would have to broadcast their high fee transactions and risk losing them to another miner
• It does not use a naive approach of only considering the mempool which would produce extremely poor results
• When there is contention:
  • The 1 confirmation bucket fee goes up to compensate
  • Each successive longer confirmation reduces the expected fee
  • If you're willing to wait long enough, you can still pay the min fee
• When there is little to no contention
  • The 1 confirmation bucket fee is at or near the min fee

[matheusd]

For reference, here are the counts for the relevant parameters from mainnet for the past 6 months (starting at height 267745 and going back 51840 blocks):

Block Size Histogram
{400:    0, 512:    0, 1024:    0, 2048:   37, 4096: 4994, 8192: 27021, 16384: 15181, 32768: 3606, 65535:  691, 131072:  195, 262144:   50, 524288:   65, }
{400: 0.00, 512: 0.00, 1024: 0.00, 2048: 0.07, 4096: 9.63, 8192: 52.12, 16384: 29.28, 32768: 6.96, 65535: 1.33, 131072: 0.38, 262144: 0.10, 524288: 0.13, }

Txs per Block Histogram
{8:  478, 16: 25779, 32: 23603, 64: 1883, 128:   79, 256:   15, 512:    2, 1024:    1, 2048:    0, 4096:    0, 8192:    0, 16384:    0, 32768:    0, }
{8: 0.92, 16: 49.73, 32: 45.53, 64: 3.63, 128: 0.15, 256: 0.03, 512: 0.00, 1024: 0.00, 2048: 0.00, 4096: 0.00, 8192: 0.00, 16384: 0.00, 32768: 0.00, }

Tx size Block Histogram
{128:    0, 256: 113988, 512: 534934, 1024: 200004, 2048: 21171, 4096: 7687, 8192: 4707, 16384: 2089, 32768:  902, 65535:  340, 131072:  211, 262144:    0, 524288:    0, }
{128: 0.00, 256:  12.86, 512:  60.37, 1024:  22.57, 2048:  2.39, 4096: 0.87, 8192: 0.53, 16384: 0.24, 32768: 0.10, 65535: 0.04, 131072: 0.02, 262144: 0.00, 524288: 0.00, }