Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2022 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : #ifndef BITCOIN_POLICY_FEES_H
       6             : #define BITCOIN_POLICY_FEES_H
       7             : 
       8             : #include <consensus/amount.h>
       9             : #include <policy/feerate.h>
      10             : #include <random.h>
      11             : #include <sync.h>
      12             : #include <threadsafety.h>
      13             : #include <uint256.h>
      14             : #include <util/fs.h>
      15             : 
      16             : #include <array>
      17             : #include <chrono>
      18             : #include <map>
      19             : #include <memory>
      20             : #include <set>
      21             : #include <string>
      22             : #include <vector>
      23             : 
      24             : 
      25             : // How often to flush fee estimates to fee_estimates.dat.
      26             : static constexpr std::chrono::hours FEE_FLUSH_INTERVAL{1};
      27             : 
      28             : /** fee_estimates.dat that are more than 60 hours (2.5 days) old will not be read,
      29             :  * as fee estimates are based on historical data and may be inaccurate if
      30             :  * network activity has changed.
      31             :  */
      32             : static constexpr std::chrono::hours MAX_FILE_AGE{60};
      33             : 
      34             : // Whether we allow importing a fee_estimates file older than MAX_FILE_AGE.
      35             : static constexpr bool DEFAULT_ACCEPT_STALE_FEE_ESTIMATES{false};
      36             : 
      37             : class AutoFile;
      38             : class CTxMemPoolEntry;
      39             : class TxConfirmStats;
      40             : 
      41             : /* Identifier for each of the 3 different TxConfirmStats which will track
      42             :  * history over different time horizons. */
      43             : enum class FeeEstimateHorizon {
      44             :     SHORT_HALFLIFE,
      45             :     MED_HALFLIFE,
      46             :     LONG_HALFLIFE,
      47             : };
      48             : 
      49             : static constexpr auto ALL_FEE_ESTIMATE_HORIZONS = std::array{
      50             :     FeeEstimateHorizon::SHORT_HALFLIFE,
      51             :     FeeEstimateHorizon::MED_HALFLIFE,
      52             :     FeeEstimateHorizon::LONG_HALFLIFE,
      53             : };
      54             : 
      55             : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);
      56             : 
      57             : /* Enumeration of reason for returned fee estimate */
      58             : enum class FeeReason {
      59             :     NONE,
      60             :     HALF_ESTIMATE,
      61             :     FULL_ESTIMATE,
      62             :     DOUBLE_ESTIMATE,
      63             :     CONSERVATIVE,
      64             :     MEMPOOL_MIN,
      65             :     PAYTXFEE,
      66             :     FALLBACK,
      67             :     REQUIRED,
      68             : };
      69             : 
      70             : /* Used to return detailed information about a feerate bucket */
      71        3192 : struct EstimatorBucket
      72             : {
      73        3192 :     double start = -1;
      74        3192 :     double end = -1;
      75        3192 :     double withinTarget = 0;
      76        3192 :     double totalConfirmed = 0;
      77        3192 :     double inMempool = 0;
      78        3192 :     double leftMempool = 0;
      79             : };
      80             : 
      81             : /* Used to return detailed information about a fee estimate calculation */
      82        1573 : struct EstimationResult
      83             : {
      84             :     EstimatorBucket pass;
      85             :     EstimatorBucket fail;
      86        1573 :     double decay = 0;
      87        1573 :     unsigned int scale = 0;
      88             : };
      89             : 
      90         651 : struct FeeCalculation
      91             : {
      92             :     EstimationResult est;
      93         651 :     FeeReason reason = FeeReason::NONE;
      94         651 :     int desiredTarget = 0;
      95         651 :     int returnedTarget = 0;
      96             : };
      97             : 
      98             : /** \class CBlockPolicyEstimator
      99             :  * The BlockPolicyEstimator is used for estimating the feerate needed
     100             :  * for a transaction to be included in a block within a certain number of
     101             :  * blocks.
     102             :  *
     103             :  * At a high level the algorithm works by grouping transactions into buckets
     104             :  * based on having similar feerates and then tracking how long it
     105             :  * takes transactions in the various buckets to be mined.  It operates under
     106             :  * the assumption that in general transactions of higher feerate will be
     107             :  * included in blocks before transactions of lower feerate.   So for
     108             :  * example if you wanted to know what feerate you should put on a transaction to
     109             :  * be included in a block within the next 5 blocks, you would start by looking
     110             :  * at the bucket with the highest feerate transactions and verifying that a
     111             :  * sufficiently high percentage of them were confirmed within 5 blocks and
     112             :  * then you would look at the next highest feerate bucket, and so on, stopping at
     113             :  * the last bucket to pass the test.   The average feerate of transactions in this
     114             :  * bucket will give you an indication of the lowest feerate you can put on a
     115             :  * transaction and still have a sufficiently high chance of being confirmed
     116             :  * within your desired 5 blocks.
     117             :  *
     118             :  * Here is a brief description of the implementation:
     119             :  * When a transaction enters the mempool, we track the height of the block chain
     120             :  * at entry.  All further calculations are conducted only on this set of "seen"
     121             :  * transactions. Whenever a block comes in, we count the number of transactions
     122             :  * in each bucket and the total amount of feerate paid in each bucket. Then we
     123             :  * calculate how many blocks Y it took each transaction to be mined.  We convert
     124             :  * from a number of blocks to a number of periods Y' each encompassing "scale"
     125             :  * blocks.  This is tracked in 3 different data sets each up to a maximum
     126             :  * number of periods. Within each data set we have an array of counters in each
     127             :  * feerate bucket and we increment all the counters from Y' up to max periods
     128             :  * representing that a tx was successfully confirmed in less than or equal to
     129             :  * that many periods. We want to save a history of this information, so at any
     130             :  * time we have a counter of the total number of transactions that happened in a
     131             :  * given feerate bucket and the total number that were confirmed in each of the
     132             :  * periods or less for any bucket.  We save this history by keeping an
     133             :  * exponentially decaying moving average of each one of these stats.  This is
     134             :  * done for a different decay in each of the 3 data sets to keep relevant data
     135             :  * from different time horizons.  Furthermore we also keep track of the number
     136             :  * unmined (in mempool or left mempool without being included in a block)
     137             :  * transactions in each bucket and for how many blocks they have been
     138             :  * outstanding and use both of these numbers to increase the number of transactions
     139             :  * we've seen in that feerate bucket when calculating an estimate for any number
     140             :  * of confirmations below the number of blocks they've been outstanding.
     141             :  *
     142             :  *  We want to be able to estimate feerates that are needed on tx's to be included in
     143             :  * a certain number of blocks.  Every time a block is added to the best chain, this class records
     144             :  * stats on the transactions included in that block
     145             :  */
     146             : class CBlockPolicyEstimator
     147             : {
     148             : private:
     149             :     /** Track confirm delays up to 12 blocks for short horizon */
     150             :     static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
     151             :     static constexpr unsigned int SHORT_SCALE = 1;
     152             :     /** Track confirm delays up to 48 blocks for medium horizon */
     153             :     static constexpr unsigned int MED_BLOCK_PERIODS = 24;
     154             :     static constexpr unsigned int MED_SCALE = 2;
     155             :     /** Track confirm delays up to 1008 blocks for long horizon */
     156             :     static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
     157             :     static constexpr unsigned int LONG_SCALE = 24;
     158             :     /** Historical estimates that are older than this aren't valid */
     159             :     static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
     160             : 
     161             :     /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
     162             :     static constexpr double SHORT_DECAY = .962;
     163             :     /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
     164             :     static constexpr double MED_DECAY = .9952;
     165             :     /** Decay of .99931 is a half-life of 1008 blocks or about 1 week */
     166             :     static constexpr double LONG_DECAY = .99931;
     167             : 
     168             :     /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
     169             :     static constexpr double HALF_SUCCESS_PCT = .6;
     170             :     /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
     171             :     static constexpr double SUCCESS_PCT = .85;
     172             :     /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
     173             :     static constexpr double DOUBLE_SUCCESS_PCT = .95;
     174             : 
     175             :     /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
     176             :     static constexpr double SUFFICIENT_FEETXS = 0.1;
     177             :     /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
     178             :     static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
     179             : 
     180             :     /** Minimum and Maximum values for tracking feerates
     181             :      * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
     182             :      * might ever want to track.  Historically this has been 1000 since it was
     183             :      * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
     184             :      * invalidates old estimates files. So leave it at 1000 unless it becomes
     185             :      * necessary to lower it, and then lower it substantially.
     186             :      */
     187             :     static constexpr double MIN_BUCKET_FEERATE = 1000;
     188             :     static constexpr double MAX_BUCKET_FEERATE = 1e7;
     189             : 
     190             :     /** Spacing of FeeRate buckets
     191             :      * We have to lump transactions into buckets based on feerate, but we want to be able
     192             :      * to give accurate estimates over a large range of potential feerates
     193             :      * Therefore it makes sense to exponentially space the buckets
     194             :      */
     195             :     static constexpr double FEE_SPACING = 1.05;
     196             : 
     197             :     const fs::path m_estimation_filepath;
     198             : public:
     199             :     /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
     200             :     CBlockPolicyEstimator(const fs::path& estimation_filepath, const bool read_stale_estimates);
     201             :     ~CBlockPolicyEstimator();
     202             : 
     203             :     /** Process all the transactions that have been included in a block */
     204             :     void processBlock(unsigned int nBlockHeight,
     205             :                       std::vector<const CTxMemPoolEntry*>& entries)
     206             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     207             : 
     208             :     /** Process a transaction accepted to the mempool*/
     209             :     void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
     210             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     211             : 
     212             :     /** Remove a transaction from the mempool tracking stats*/
     213             :     bool removeTx(uint256 hash, bool inBlock)
     214             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     215             : 
     216             :     /** DEPRECATED. Return a feerate estimate */
     217             :     CFeeRate estimateFee(int confTarget) const
     218             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     219             : 
     220             :     /** Estimate feerate needed to get be included in a block within confTarget
     221             :      *  blocks. If no answer can be given at confTarget, return an estimate at
     222             :      *  the closest target where one can be given.  'conservative' estimates are
     223             :      *  valid over longer time horizons also.
     224             :      */
     225             :     CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
     226             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     227             : 
     228             :     /** Return a specific fee estimate calculation with a given success
     229             :      * threshold and time horizon, and optionally return detailed data about
     230             :      * calculation
     231             :      */
     232             :     CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon,
     233             :                             EstimationResult* result = nullptr) const
     234             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     235             : 
     236             :     /** Write estimation data to a file */
     237             :     bool Write(AutoFile& fileout) const
     238             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     239             : 
     240             :     /** Read estimation data from a file */
     241             :     bool Read(AutoFile& filein)
     242             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     243             : 
     244             :     /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
     245             :     void FlushUnconfirmed()
     246             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     247             : 
     248             :     /** Calculation of highest target that estimates are tracked for */
     249             :     unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
     250             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     251             : 
     252             :     /** Drop still unconfirmed transactions and record current estimations, if the fee estimation file is present. */
     253             :     void Flush()
     254             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     255             : 
     256             :     /** Record current fee estimations. */
     257             :     void FlushFeeEstimates()
     258             :         EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
     259             : 
     260             :     /** Calculates the age of the file, since last modified */
     261             :     std::chrono::hours GetFeeEstimatorFileAge();
     262             : 
     263             : private:
     264             :     mutable Mutex m_cs_fee_estimator;
     265             : 
     266             :     unsigned int nBestSeenHeight GUARDED_BY(m_cs_fee_estimator){0};
     267             :     unsigned int firstRecordedHeight GUARDED_BY(m_cs_fee_estimator){0};
     268             :     unsigned int historicalFirst GUARDED_BY(m_cs_fee_estimator){0};
     269             :     unsigned int historicalBest GUARDED_BY(m_cs_fee_estimator){0};
     270             : 
     271             :     struct TxStatsInfo
     272             :     {
     273           0 :         unsigned int blockHeight{0};
     274           0 :         unsigned int bucketIndex{0};
     275           0 :         TxStatsInfo() {}
     276             :     };
     277             : 
     278             :     // map of txids to information about that transaction
     279             :     std::map<uint256, TxStatsInfo> mapMemPoolTxs GUARDED_BY(m_cs_fee_estimator);
     280             : 
     281             :     /** Classes to track historical data on transaction confirmations */
     282             :     std::unique_ptr<TxConfirmStats> feeStats PT_GUARDED_BY(m_cs_fee_estimator);
     283             :     std::unique_ptr<TxConfirmStats> shortStats PT_GUARDED_BY(m_cs_fee_estimator);
     284             :     std::unique_ptr<TxConfirmStats> longStats PT_GUARDED_BY(m_cs_fee_estimator);
     285             : 
     286             :     unsigned int trackedTxs GUARDED_BY(m_cs_fee_estimator){0};
     287             :     unsigned int untrackedTxs GUARDED_BY(m_cs_fee_estimator){0};
     288             : 
     289             :     std::vector<double> buckets GUARDED_BY(m_cs_fee_estimator); // The upper-bound of the range for the bucket (inclusive)
     290             :     std::map<double, unsigned int> bucketMap GUARDED_BY(m_cs_fee_estimator); // Map of bucket upper-bound to index into all vectors by bucket
     291             : 
     292             :     /** Process a transaction confirmed in a block*/
     293             :     bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     294             : 
     295             :     /** Helper for estimateSmartFee */
     296             :     double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     297             :     /** Helper for estimateSmartFee */
     298             :     double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     299             :     /** Number of blocks of data recorded while fee estimates have been running */
     300             :     unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     301             :     /** Number of blocks of recorded fee estimate data represented in saved data file */
     302             :     unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     303             :     /** Calculation of highest target that reasonable estimate can be provided for */
     304             :     unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     305             : 
     306             :     /** A non-thread-safe helper for the removeTx function */
     307             :     bool _removeTx(const uint256& hash, bool inBlock)
     308             :         EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
     309             : };
     310             : 
     311             : class FeeFilterRounder
     312             : {
     313             : private:
     314             :     static constexpr double MAX_FILTER_FEERATE = 1e7;
     315             :     /** FEE_FILTER_SPACING is just used to provide some quantization of fee
     316             :      * filter results.  Historically it reused FEE_SPACING, but it is completely
     317             :      * unrelated, and was made a separate constant so the two concepts are not
     318             :      * tied together */
     319             :     static constexpr double FEE_FILTER_SPACING = 1.1;
     320             : 
     321             : public:
     322             :     /** Create new FeeFilterRounder */
     323             :     explicit FeeFilterRounder(const CFeeRate& min_incremental_fee);
     324             : 
     325             :     /** Quantize a minimum fee for privacy purpose before broadcast. */
     326             :     CAmount round(CAmount currentMinFee) EXCLUSIVE_LOCKS_REQUIRED(!m_insecure_rand_mutex);
     327             : 
     328             : private:
     329             :     const std::set<double> m_fee_set;
     330             :     Mutex m_insecure_rand_mutex;
     331             :     FastRandomContext insecure_rand GUARDED_BY(m_insecure_rand_mutex);
     332             : };
     333             : 
     334             : #endif // BITCOIN_POLICY_FEES_H