Line data    Source code

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