src/policy/fees.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 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 "uint256.h"
  10 #include "random.h"
  11 #include "sync.h"
  12
  13 #include <map>
  14 #include <string>
  15 #include <vector>
  16
  17 class CAutoFile;
  18 class CFeeRate;
  19 class CTxMemPoolEntry;
  20 class CTxMemPool;
  21 class TxConfirmStats;
  22
  23 /** \class CBlockPolicyEstimator
  24  * The BlockPolicyEstimator is used for estimating the feerate needed
  25  * for a transaction to be included in a block within a certain number of
  26  * blocks.
  27  *
  28  * At a high level the algorithm works by grouping transactions into buckets
  29  * based on having similar feerates and then tracking how long it
  30  * takes transactions in the various buckets to be mined.  It operates under
  31  * the assumption that in general transactions of higher feerate will be
  32  * included in blocks before transactions of lower feerate.   So for
  33  * example if you wanted to know what feerate you should put on a transaction to
  34  * be included in a block within the next 5 blocks, you would start by looking
  35  * at the bucket with the highest feerate transactions and verifying that a
  36  * sufficiently high percentage of them were confirmed within 5 blocks and
  37  * then you would look at the next highest feerate bucket, and so on, stopping at
  38  * the last bucket to pass the test.   The average feerate of transactions in this
  39  * bucket will give you an indication of the lowest feerate you can put on a
  40  * transaction and still have a sufficiently high chance of being confirmed
  41  * within your desired 5 blocks.
  42  *
  43  * Here is a brief description of the implementation:
  44  * When a transaction enters the mempool, we
  45  * track the height of the block chain at entry.  Whenever a block comes in,
  46  * we count the number of transactions in each bucket and the total amount of feerate
  47  * paid in each bucket. Then we calculate how many blocks Y it took each
  48  * transaction to be mined and we track an array of counters in each bucket
  49  * for how long it to took transactions to get confirmed from 1 to a max of 25
  50  * and we increment all the counters from Y up to 25. This is because for any
  51  * number Z>=Y the transaction was successfully mined within Z blocks.  We
  52  * want to save a history of this information, so at any time we have a
  53  * counter of the total number of transactions that happened in a given feerate
  54  * bucket and the total number that were confirmed in each number 1-25 blocks
  55  * or less for any bucket.   We save this history by keeping an exponentially
  56  * decaying moving average of each one of these stats.  Furthermore we also
  57  * keep track of the number unmined (in mempool) transactions in each bucket
  58  * and for how many blocks they have been outstanding and use that to increase
  59  * the number of transactions we've seen in that feerate bucket when calculating
  60  * an estimate for any number of confirmations below the number of blocks
  61  * they've been outstanding.
  62  */
  63
  64 enum FeeEstimateHorizon {
  65     SHORT_HALFLIFE = 0,
  66     MED_HALFLIFE = 1,
  67     LONG_HALFLIFE = 2
  68 };
  69
  70 struct EstimatorBucket
  71 {
  72     double start = -1;
  73     double end = -1;
  74     double withinTarget = 0;
  75     double totalConfirmed = 0;
  76     double inMempool = 0;
  77     double leftMempool = 0;
  78 };
  79
  80 struct EstimationResult
  81 {
  82     EstimatorBucket pass;
  83     EstimatorBucket fail;
  84     double decay;
  85 };
  86
  87 /**
  88  *  We want to be able to estimate feerates that are needed on tx's to be included in
  89  * a certain number of blocks.  Every time a block is added to the best chain, this class records
  90  * stats on the transactions included in that block
  91  */
  92 class CBlockPolicyEstimator
  93 {
  94 private:
  95     /** Track confirm delays up to 12 blocks medium decay */
  96     static constexpr unsigned int SHORT_BLOCK_CONFIRMS = 12;
  97     /** Track confirm delays up to 48 blocks medium decay */
  98     static constexpr unsigned int MED_BLOCK_CONFIRMS = 48;
  99     /** Track confirm delays up to 1008 blocks for longer decay */
 100     static constexpr unsigned int LONG_BLOCK_CONFIRMS = 1008;
 101
 102     /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
 103     static constexpr double SHORT_DECAY = .962;
 104     /** Decay of .998 is a half-life of 144 blocks or about 1 day */
 105     static constexpr double MED_DECAY = .9952;
 106     /** Decay of .9995 is a half-life of 1008 blocks or about 1 week */
 107     static constexpr double LONG_DECAY = .99931;
 108
 109     /** Require greater than 95% of X feerate transactions to be confirmed within Y blocks for X to be big enough */
 110     static constexpr double HALF_SUCCESS_PCT = .6;
 111     static constexpr double SUCCESS_PCT = .85;
 112     static constexpr double DOUBLE_SUCCESS_PCT = .95;
 113
 114     /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
 115     static constexpr double SUFFICIENT_FEETXS = 0.1;
 116     /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
 117     static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
 118
 119     /** Minimum and Maximum values for tracking feerates
 120      * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
 121      * might ever want to track.  Historically this has been 1000 since it was
 122      * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
 123      * invalidates old estimates files. So leave it at 1000 unless it becomes
 124      * necessary to lower it, and then lower it substantially.
 125      */
 126     static constexpr double MIN_BUCKET_FEERATE = 1000;
 127     static constexpr double MAX_BUCKET_FEERATE = 1e7;
 128
 129     /** Spacing of FeeRate buckets
 130      * We have to lump transactions into buckets based on feerate, but we want to be able
 131      * to give accurate estimates over a large range of potential feerates
 132      * Therefore it makes sense to exponentially space the buckets
 133      */
 134     static constexpr double FEE_SPACING = 1.05;
 135
 136 public:
 137     /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
 138     CBlockPolicyEstimator();
 139     ~CBlockPolicyEstimator();
 140
 141     /** Process all the transactions that have been included in a block */
 142     void processBlock(unsigned int nBlockHeight,
 143                       std::vector<const CTxMemPoolEntry*>& entries);
 144
 145     /** Process a transaction accepted to the mempool*/
 146     void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate);
 147
 148     /** Remove a transaction from the mempool tracking stats*/
 149     bool removeTx(uint256 hash, bool inBlock);
 150
 151     /** Return a feerate estimate */
 152     CFeeRate estimateFee(int confTarget) const;
 153
 154     /** Estimate feerate needed to get be included in a block within
 155      *  confTarget blocks. If no answer can be given at confTarget, return an
 156      *  estimate at the lowest target where one can be given.
 157      */
 158     CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool, bool conservative = true) const;
 159
 160     /** Return a specific fee estimate calculation with a given success threshold and time horizon.
 161      */
 162     CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult *result = nullptr) const;
 163
 164     /** Write estimation data to a file */
 165     bool Write(CAutoFile& fileout) const;
 166
 167     /** Read estimation data from a file */
 168     bool Read(CAutoFile& filein);
 169
 170     /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
 171     void FlushUnconfirmed(CTxMemPool& pool);
 172
 173 private:
 174     CFeeRate minTrackedFee;    //!< Passed to constructor to avoid dependency on main
 175     unsigned int nBestSeenHeight;
 176     unsigned int firstRecordedHeight;
 177     unsigned int historicalFirst;
 178     unsigned int historicalBest;
 179
 180     struct TxStatsInfo
 181     {
 182         unsigned int blockHeight;
 183         unsigned int bucketIndex;
 184         TxStatsInfo() : blockHeight(0), bucketIndex(0) {}
 185     };
 186
 187     // map of txids to information about that transaction
 188     std::map<uint256, TxStatsInfo> mapMemPoolTxs;
 189
 190     /** Classes to track historical data on transaction confirmations */
 191     TxConfirmStats* feeStats;
 192     TxConfirmStats* shortStats;
 193     TxConfirmStats* longStats;
 194
 195     unsigned int trackedTxs;
 196     unsigned int untrackedTxs;
 197
 198     std::vector<double> buckets;              // The upper-bound of the range for the bucket (inclusive)
 199     std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
 200
 201     mutable CCriticalSection cs_feeEstimator;
 202
 203     /** Process a transaction confirmed in a block*/
 204     bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry);
 205
 206     double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon) const;
 207     double estimateConservativeFee(unsigned int doubleTarget) const;
 208 };
 209
 210 class FeeFilterRounder
 211 {
 212 private:
 213     static constexpr double MAX_FILTER_FEERATE = 1e7;
 214     /** FEE_FILTER_SPACING is just used to provide some quantization of fee
 215      * filter results.  Historically it reused FEE_SPACING, but it is completely
 216      * unrelated, and was made a separate constant so the two concepts are not
 217      * tied together */
 218     static constexpr double FEE_FILTER_SPACING = 1.1;
 219
 220 public:
 221     /** Create new FeeFilterRounder */
 222     FeeFilterRounder(const CFeeRate& minIncrementalFee);
 223
 224     /** Quantize a minimum fee for privacy purpose before broadcast **/
 225     CAmount round(CAmount currentMinFee);
 226
 227 private:
 228     std::set<double> feeset;
 229     FastRandomContext insecure_rand;
 230 };
 231
 232 #endif /*BITCOIN_POLICYESTIMATOR_H */