diff options
Diffstat (limited to 'src/policy/fees.h')
| -rw-r--r-- | src/policy/fees.h | 334 |
1 files changed, 174 insertions, 160 deletions
diff --git a/src/policy/fees.h b/src/policy/fees.h index dd01c90c45..7125a74f03 100644 --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -6,8 +6,10 @@ #define BITCOIN_POLICYESTIMATOR_H #include "amount.h" +#include "feerate.h" #include "uint256.h" #include "random.h" +#include "sync.h" #include <map> #include <string> @@ -17,6 +19,7 @@ class CAutoFile; class CFeeRate; class CTxMemPoolEntry; class CTxMemPool; +class TxConfirmStats; /** \class CBlockPolicyEstimator * The BlockPolicyEstimator is used for estimating the feerate needed @@ -39,160 +42,81 @@ class CTxMemPool; * within your desired 5 blocks. * * Here is a brief description of the implementation: - * When a transaction enters the mempool, we - * track the height of the block chain at entry. Whenever a block comes in, - * we count the number of transactions in each bucket and the total amount of feerate - * paid in each bucket. Then we calculate how many blocks Y it took each - * transaction to be mined and we track an array of counters in each bucket - * for how long it to took transactions to get confirmed from 1 to a max of 25 - * and we increment all the counters from Y up to 25. This is because for any - * number Z>=Y the transaction was successfully mined within Z blocks. We - * want to save a history of this information, so at any time we have a - * counter of the total number of transactions that happened in a given feerate - * bucket and the total number that were confirmed in each number 1-25 blocks - * or less for any bucket. We save this history by keeping an exponentially - * decaying moving average of each one of these stats. Furthermore we also - * keep track of the number unmined (in mempool) transactions in each bucket - * and for how many blocks they have been outstanding and use that to increase - * the number of transactions we've seen in that feerate bucket when calculating - * an estimate for any number of confirmations below the number of blocks - * they've been outstanding. + * When a transaction enters the mempool, we track the height of the block chain + * at entry. All further calculations are conducted only on this set of "seen" + * transactions. Whenever a block comes in, we count the number of transactions + * in each bucket and the total amount of feerate paid in each bucket. Then we + * calculate how many blocks Y it took each transaction to be mined. We convert + * from a number of blocks to a number of periods Y' each encompassing "scale" + * blocks. This is is tracked in 3 different data sets each up to a maximum + * number of periods. Within each data set we have an array of counters in each + * feerate bucket and we increment all the counters from Y' up to max periods + * representing that a tx was successfully confirmed in less than or equal to + * that many periods. We want to save a history of this information, so at any + * time we have a counter of the total number of transactions that happened in a + * given feerate bucket and the total number that were confirmed in each of the + * periods or less for any bucket. We save this history by keeping an + * exponentially decaying moving average of each one of these stats. This is + * done for a different decay in each of the 3 data sets to keep relevant data + * from different time horizons. Furthermore we also keep track of the number + * unmined (in mempool or left mempool without being included in a block) + * transactions in each bucket and for how many blocks they have been + * outstanding and use both of these numbers to increase the number of transactions + * we've seen in that feerate bucket when calculating an estimate for any number + * of confirmations below the number of blocks they've been outstanding. */ -/** - * We will instantiate an instance of this class to track transactions that were - * included in a block. We will lump transactions into a bucket according to their - * approximate feerate and then track how long it took for those txs to be included in a block - * - * The tracking of unconfirmed (mempool) transactions is completely independent of the - * historical tracking of transactions that have been confirmed in a block. - */ -class TxConfirmStats -{ -private: - //Define the buckets we will group transactions into - std::vector<double> buckets; // The upper-bound of the range for the bucket (inclusive) - std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket - - // For each bucket X: - // Count the total # of txs in each bucket - // Track the historical moving average of this total over blocks - std::vector<double> txCtAvg; - // and calculate the total for the current block to update the moving average - std::vector<int> curBlockTxCt; - - // Count the total # of txs confirmed within Y blocks in each bucket - // Track the historical moving average of theses totals over blocks - std::vector<std::vector<double> > confAvg; // confAvg[Y][X] - // and calculate the totals for the current block to update the moving averages - std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X] - - // Sum the total feerate of all tx's in each bucket - // Track the historical moving average of this total over blocks - std::vector<double> avg; - // and calculate the total for the current block to update the moving average - std::vector<double> curBlockVal; - - // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X - // Combine the total value with the tx counts to calculate the avg feerate per bucket - - double decay; - - // Mempool counts of outstanding transactions - // For each bucket X, track the number of transactions in the mempool - // that are unconfirmed for each possible confirmation value Y - std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X] - // transactions still unconfirmed after MAX_CONFIRMS for each bucket - std::vector<int> oldUnconfTxs; - -public: - /** - * Initialize the data structures. This is called by BlockPolicyEstimator's - * constructor with default values. - * @param defaultBuckets contains the upper limits for the bucket boundaries - * @param maxConfirms max number of confirms to track - * @param decay how much to decay the historical moving average per block - */ - void Initialize(std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay); - - /** Clear the state of the curBlock variables to start counting for the new block */ - void ClearCurrent(unsigned int nBlockHeight); - - /** - * Record a new transaction data point in the current block stats - * @param blocksToConfirm the number of blocks it took this transaction to confirm - * @param val the feerate of the transaction - * @warning blocksToConfirm is 1-based and has to be >= 1 - */ - void Record(int blocksToConfirm, double val); - - /** Record a new transaction entering the mempool*/ - unsigned int NewTx(unsigned int nBlockHeight, double val); - - /** Remove a transaction from mempool tracking stats*/ - void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, - unsigned int bucketIndex); - - /** Update our estimates by decaying our historical moving average and updating - with the data gathered from the current block */ - void UpdateMovingAverages(); - - /** - * Calculate a feerate estimate. Find the lowest value bucket (or range of buckets - * to make sure we have enough data points) whose transactions still have sufficient likelihood - * of being confirmed within the target number of confirmations - * @param confTarget target number of confirmations - * @param sufficientTxVal required average number of transactions per block in a bucket range - * @param minSuccess the success probability we require - * @param requireGreater return the lowest feerate such that all higher values pass minSuccess OR - * return the highest feerate such that all lower values fail minSuccess - * @param nBlockHeight the current block height - */ - double EstimateMedianVal(int confTarget, double sufficientTxVal, - double minSuccess, bool requireGreater, unsigned int nBlockHeight); - - /** Return the max number of confirms we're tracking */ - unsigned int GetMaxConfirms() { return confAvg.size(); } - - /** Write state of estimation data to a file*/ - void Write(CAutoFile& fileout); - - /** - * Read saved state of estimation data from a file and replace all internal data structures and - * variables with this state. - */ - void Read(CAutoFile& filein); +/* Identifier for each of the 3 different TxConfirmStats which will track + * history over different time horizons. */ +enum FeeEstimateHorizon { + SHORT_HALFLIFE = 0, + MED_HALFLIFE = 1, + LONG_HALFLIFE = 2 }; +/* Enumeration of reason for returned fee estimate */ +enum class FeeReason { + NONE, + HALF_ESTIMATE, + FULL_ESTIMATE, + DOUBLE_ESTIMATE, + CONSERVATIVE, + MEMPOOL_MIN, + PAYTXFEE, + FALLBACK, + REQUIRED, + MAXTXFEE, +}; +std::string StringForFeeReason(FeeReason reason); -/** Track confirm delays up to 25 blocks, can't estimate beyond that */ -static const unsigned int MAX_BLOCK_CONFIRMS = 25; - -/** Decay of .998 is a half-life of 346 blocks or about 2.4 days */ -static const double DEFAULT_DECAY = .998; - -/** Require greater than 95% of X feerate transactions to be confirmed within Y blocks for X to be big enough */ -static const double MIN_SUCCESS_PCT = .95; - -/** Require an avg of 1 tx in the combined feerate bucket per block to have stat significance */ -static const double SUFFICIENT_FEETXS = 1; +/* Used to return detailed information about a feerate bucket */ +struct EstimatorBucket +{ + double start = -1; + double end = -1; + double withinTarget = 0; + double totalConfirmed = 0; + double inMempool = 0; + double leftMempool = 0; +}; -// Minimum and Maximum values for tracking feerates -// The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we -// might ever want to track. Historically this has been 1000 since it was -// inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it -// invalidates old estimates files. So leave it at 1000 unless it becomes -// necessary to lower it, and then lower it substantially. -static constexpr double MIN_BUCKET_FEERATE = 1000; -static const double MAX_BUCKET_FEERATE = 1e7; -static const double INF_FEERATE = MAX_MONEY; +/* Used to return detailed information about a fee estimate calculation */ +struct EstimationResult +{ + EstimatorBucket pass; + EstimatorBucket fail; + double decay = 0; + unsigned int scale = 0; +}; -// We have to lump transactions into buckets based on feerate, but we want to be able -// to give accurate estimates over a large range of potential feerates -// Therefore it makes sense to exponentially space the buckets -/** Spacing of FeeRate buckets */ -static const double FEE_SPACING = 1.1; +struct FeeCalculation +{ + EstimationResult est; + FeeReason reason = FeeReason::NONE; + int desiredTarget = 0; + int returnedTarget = 0; +}; /** * We want to be able to estimate feerates that are needed on tx's to be included in @@ -201,41 +125,101 @@ static const double FEE_SPACING = 1.1; */ class CBlockPolicyEstimator { +private: + /** Track confirm delays up to 12 blocks for short horizon */ + static constexpr unsigned int SHORT_BLOCK_PERIODS = 12; + static constexpr unsigned int SHORT_SCALE = 1; + /** Track confirm delays up to 48 blocks for medium horizon */ + static constexpr unsigned int MED_BLOCK_PERIODS = 24; + static constexpr unsigned int MED_SCALE = 2; + /** Track confirm delays up to 1008 blocks for long horizon */ + static constexpr unsigned int LONG_BLOCK_PERIODS = 42; + static constexpr unsigned int LONG_SCALE = 24; + /** Historical estimates that are older than this aren't valid */ + static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008; + + /** Decay of .962 is a half-life of 18 blocks or about 3 hours */ + static constexpr double SHORT_DECAY = .962; + /** Decay of .998 is a half-life of 144 blocks or about 1 day */ + static constexpr double MED_DECAY = .9952; + /** Decay of .9995 is a half-life of 1008 blocks or about 1 week */ + static constexpr double LONG_DECAY = .99931; + + /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/ + static constexpr double HALF_SUCCESS_PCT = .6; + /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/ + static constexpr double SUCCESS_PCT = .85; + /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/ + static constexpr double DOUBLE_SUCCESS_PCT = .95; + + /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */ + static constexpr double SUFFICIENT_FEETXS = 0.1; + /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/ + static constexpr double SUFFICIENT_TXS_SHORT = 0.5; + + /** Minimum and Maximum values for tracking feerates + * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we + * might ever want to track. Historically this has been 1000 since it was + * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it + * invalidates old estimates files. So leave it at 1000 unless it becomes + * necessary to lower it, and then lower it substantially. + */ + static constexpr double MIN_BUCKET_FEERATE = 1000; + static constexpr double MAX_BUCKET_FEERATE = 1e7; + + /** Spacing of FeeRate buckets + * We have to lump transactions into buckets based on feerate, but we want to be able + * to give accurate estimates over a large range of potential feerates + * Therefore it makes sense to exponentially space the buckets + */ + static constexpr double FEE_SPACING = 1.05; + public: /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */ CBlockPolicyEstimator(); + ~CBlockPolicyEstimator(); /** Process all the transactions that have been included in a block */ void processBlock(unsigned int nBlockHeight, std::vector<const CTxMemPoolEntry*>& entries); - /** Process a transaction confirmed in a block*/ - bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry); - /** Process a transaction accepted to the mempool*/ void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate); /** Remove a transaction from the mempool tracking stats*/ - bool removeTx(uint256 hash); + bool removeTx(uint256 hash, bool inBlock); + + /** DEPRECATED. Return a feerate estimate */ + CFeeRate estimateFee(int confTarget) const; - /** Return a feerate estimate */ - CFeeRate estimateFee(int confTarget); + /** Estimate feerate needed to get be included in a block within confTarget + * blocks. If no answer can be given at confTarget, return an estimate at + * the closest target where one can be given. 'conservative' estimates are + * valid over longer time horizons also. + */ + CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, const CTxMemPool& pool, bool conservative = true) const; - /** Estimate feerate needed to get be included in a block within - * confTarget blocks. If no answer can be given at confTarget, return an - * estimate at the lowest target where one can be given. + /** Return a specific fee estimate calculation with a given success + * threshold and time horizon, and optionally return detailed data about + * calculation */ - CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool); + CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult *result = nullptr) const; /** Write estimation data to a file */ - void Write(CAutoFile& fileout); + bool Write(CAutoFile& fileout) const; /** Read estimation data from a file */ - void Read(CAutoFile& filein, int nFileVersion); + bool Read(CAutoFile& filein); + + /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */ + void FlushUnconfirmed(CTxMemPool& pool); private: - CFeeRate minTrackedFee; //!< Passed to constructor to avoid dependency on main unsigned int nBestSeenHeight; + unsigned int firstRecordedHeight; + unsigned int historicalFirst; + unsigned int historicalBest; + struct TxStatsInfo { unsigned int blockHeight; @@ -247,14 +231,43 @@ private: std::map<uint256, TxStatsInfo> mapMemPoolTxs; /** Classes to track historical data on transaction confirmations */ - TxConfirmStats feeStats; + TxConfirmStats* feeStats; + TxConfirmStats* shortStats; + TxConfirmStats* longStats; unsigned int trackedTxs; unsigned int untrackedTxs; + + std::vector<double> buckets; // The upper-bound of the range for the bucket (inclusive) + std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket + + mutable CCriticalSection cs_feeEstimator; + + /** Process a transaction confirmed in a block*/ + bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry); + + /** Helper for estimateSmartFee */ + double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const; + /** Helper for estimateSmartFee */ + double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const; + /** Number of blocks of data recorded while fee estimates have been running */ + unsigned int BlockSpan() const; + /** Number of blocks of recorded fee estimate data represented in saved data file */ + unsigned int HistoricalBlockSpan() const; + /** Calculation of highest target that reasonable estimate can be provided for */ + unsigned int MaxUsableEstimate() const; }; class FeeFilterRounder { +private: + static constexpr double MAX_FILTER_FEERATE = 1e7; + /** FEE_FILTER_SPACING is just used to provide some quantization of fee + * filter results. Historically it reused FEE_SPACING, but it is completely + * unrelated, and was made a separate constant so the two concepts are not + * tied together */ + static constexpr double FEE_FILTER_SPACING = 1.1; + public: /** Create new FeeFilterRounder */ FeeFilterRounder(const CFeeRate& minIncrementalFee); @@ -266,4 +279,5 @@ private: std::set<double> feeset; FastRandomContext insecure_rand; }; + #endif /*BITCOIN_POLICYESTIMATOR_H */ |