src/policy/fees.h

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