fees

README

fees

Package fees provides decred-specific methods for tracking and estimating fee rates for new transactions to be mined into the network. Fee rate estimation has two main goals:

• Ensuring transactions are mined within a target confirmation range (expressed in blocks);
• Attempting to minimize fees while maintaining be above restriction.

This package was started in order to resolve issue decred/dcrd#1412 and related. See that issue for discussion of the selected approach.

This package was developed for dcrd, a full-node implementation of Decred which is under active development. Although it was primarily written for dcrd, this package has intentionally been designed so it can be used as a standalone package for any projects needing the functionality provided.

Installation and Updating

$ go get -u github.com/decred/dcrd/fees

License

Package dcrutil is licensed under the copyfree ISC License.

Documentation

Overview

Package fees provides decred-specific methods for tracking and estimating fee rates for new transactions to be mined into the network. Fee rate estimation has two main goals:

• Ensuring transactions are mined within a target _confirmation range_ (expressed in blocks);
• Attempting to minimize fees while maintaining be above restriction.

Although it was primarily written for dcrd, this package has intentionally been designed so it can be used as a standalone package for any projects needing the functionality provided.

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 current 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 in reference [1].

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

Simulation

Development of the estimator was originally performed and simulated using the code in [5]. Simulation of the current code can be performed by using the dcrfeesim tool available in [6].

Acknowledgements

Thanks to @davecgh for providing the initial review of the results and the original developers of the 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

[5] Source for the original dcrfeesim and estimator work: https://github.com/matheusd/dcrfeesim_dev

[6] Source for the current dcrfeesim, using this module: https://github.com/matheusd/dcrfeesim

Index

• Constants
• Variables
• func DisableLog()
• func UseLogger(logger slog.Logger)
• type ErrTargetConfTooLarge
  • func (e ErrTargetConfTooLarge) Error() string
• type Estimator
  • func NewEstimator(cfg *EstimatorConfig) (*Estimator, error)
  • func (stats *Estimator) AddMemPoolTransaction(txHash *chainhash.Hash, fee, size int64, txType stake.TxType)
  • func (stats *Estimator) Close()
  • func (stats *Estimator) DumpBuckets() string
  • func (stats *Estimator) Enable(bestHeight int64)
  • func (stats *Estimator) EstimateFee(targetConfs int32) (dcrutil.Amount, error)
  • func (stats *Estimator) IsEnabled() bool
  • func (stats *Estimator) ProcessBlock(block *dcrutil.Block) error
  • func (stats *Estimator) RemoveMemPoolTransaction(txHash *chainhash.Hash)
• type EstimatorConfig

Constants

const (
	// DefaultMaxBucketFeeMultiplier is the default multiplier used to find the
	// largest fee bucket, starting at the minimum fee.
	DefaultMaxBucketFeeMultiplier int = 100

	// DefaultMaxConfirmations is the default number of confirmation ranges to
	// track in the estimator.
	DefaultMaxConfirmations uint32 = 32

	// DefaultFeeRateStep is the default multiplier between two consecutive fee
	// rate buckets.
	DefaultFeeRateStep float64 = 1.1
)

Variables

var (
	// ErrNoSuccessPctBucketFound is the error returned when no bucket has been
	// found with the minimum required percentage success.
	ErrNoSuccessPctBucketFound = errors.New("no bucket with the minimum " +
		"required success percentage found")

	// ErrNotEnoughTxsForEstimate is the error returned when not enough
	// transactions have been seen by the fee generator to give an estimate.
	ErrNotEnoughTxsForEstimate = errors.New("not enough transactions seen for " +
		"estimation")
)

Functions

func DisableLog

func DisableLog()

DisableLog disables all library log output. Logging output is disabled by default until either UseLogger or SetLogWriter are called.

func UseLogger

func UseLogger(logger slog.Logger)

UseLogger uses a specified Logger to output fee estimator logging info. This should be used in preference to SetLogWriter if the caller is also using slog.

Types

type ErrTargetConfTooLarge

type ErrTargetConfTooLarge struct {
	MaxConfirms int32
	ReqConfirms int32
}

ErrTargetConfTooLarge is the type of error returned when an user of the estimator requested a confirmation range higher than tracked by the estimator.

func (ErrTargetConfTooLarge) Error

func (e ErrTargetConfTooLarge) Error() string

type Estimator

type Estimator struct {
	// contains filtered or unexported fields
}

Estimator tracks historical data for published and mined transactions in order to estimate fees to be used in new transactions for confirmation within a target block window.

func NewEstimator

func NewEstimator(cfg *EstimatorConfig) (*Estimator, error)

NewEstimator returns an empty estimator given a config. This estimator then needs to be fed data for published and mined transactions before it can be used to estimate fees for new transactions.

func (*Estimator) AddMemPoolTransaction

func (stats *Estimator) AddMemPoolTransaction(txHash *chainhash.Hash, fee, size int64, txType stake.TxType)

AddMemPoolTransaction to the estimator in order to account for it in the estimations. It assumes that this transaction is entering the mempool at the currently recorded best chain hash, using the total fee amount (in atoms) and with the provided size (in bytes).

This is safe to be called from multiple goroutines.

func (*Estimator) Close

func (stats *Estimator) Close()

Close closes the database (if it is currently opened).

func (*Estimator) DumpBuckets

func (stats *Estimator) DumpBuckets() string

DumpBuckets returns the internal estimator state as a string.

func (*Estimator) Enable

func (stats *Estimator) Enable(bestHeight int64)

Enable establishes the current best height of the blockchain after initializing the chain. All new mempool transactions will be added at this block height.

func (*Estimator) EstimateFee

func (stats *Estimator) EstimateFee(targetConfs int32) (dcrutil.Amount, error)

EstimateFee is the public version of estimateMedianFee. It calculates the suggested fee for a transaction to be confirmed in at most `targetConf` blocks after publishing with a high degree of certainty.

This function is safe to be called from multiple goroutines but might block until concurrent modifications to the internal database state are complete.

func (*Estimator) IsEnabled

func (stats *Estimator) IsEnabled() bool

IsEnabled returns whether the fee estimator is ready to accept new mined and mempool transactions.

func (*Estimator) ProcessBlock

func (stats *Estimator) ProcessBlock(block *dcrutil.Block) error

ProcessBlock processes all mined transactions in the provided block.

This function is safe to be called from multiple goroutines.

func (*Estimator) RemoveMemPoolTransaction

func (stats *Estimator) RemoveMemPoolTransaction(txHash *chainhash.Hash)

RemoveMemPoolTransaction from statistics tracking.

This is safe to be called from multiple goroutines.

type EstimatorConfig

type EstimatorConfig struct {
	// MaxConfirms is the maximum number of confirmation ranges to check.
	MaxConfirms uint32

	// MinBucketFee is the value of the fee rate of the lowest bucket for which
	// estimation is tracked.
	MinBucketFee dcrutil.Amount

	// MaxBucketFee is the value of the fee for the highest bucket for which
	// estimation is tracked.
	//
	// It MUST be higher than MinBucketFee.
	MaxBucketFee dcrutil.Amount

	// ExtraBucketFee is an additional bucket fee rate to include in the
	// database for tracking transactions. Specifying this can be useful when
	// the default relay fee of the network is undergoing change (due to a new
	// release of the software for example), so that the older fee can be
	// tracked exactly.
	//
	// It MUST have a value between MinBucketFee and MaxBucketFee, otherwise
	// it's ignored.
	ExtraBucketFee dcrutil.Amount

	// FeeRateStep is the multiplier to generate the fee rate buckets (each
	// bucket is higher than the previous one by this factor).
	//
	// It MUST have a value > 1.0.
	FeeRateStep float64

	// DatabaseFile is the location of the estimator database file. If empty,
	// updates to the estimator state are not backed by the filesystem.
	DatabaseFile string

	// ChainParams must point to the parameters of the current network.
	ChainParams *chaincfg.Params

	// ReplaceBucketsOnLoad indicates whether to replace the buckets in the
	// current estimator by those stored in the feesdb file instead of
	// validating that they are both using the same set of fees.
	ReplaceBucketsOnLoad bool
}

EstimatorConfig stores the configuration parameters for a given fee estimator. It is used to initialize an empty fee estimator.