src/policy/fees.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2015 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
  12 #include <map>
  13 #include <string>
  14 #include <vector>
  15
  16 class CAutoFile;
  17 class CFeeRate;
  18 class CTxMemPoolEntry;
  19 class CTxMemPool;
  20
  21 /** \class CBlockPolicyEstimator
  22  * The BlockPolicyEstimator is used for estimating the feerate needed
  23  * for a transaction to be included in a block within a certain number of
  24  * blocks.
  25  *
  26  * At a high level the algorithm works by grouping transactions into buckets
  27  * based on having similar feerates and then tracking how long it
  28  * takes transactions in the various buckets to be mined.  It operates under
  29  * the assumption that in general transactions of higher feerate will be
  30  * included in blocks before transactions of lower feerate.   So for
  31  * example if you wanted to know what feerate you should put on a transaction to
  32  * be included in a block within the next 5 blocks, you would start by looking
  33  * at the bucket with the highest feerate transactions and verifying that a
  34  * sufficiently high percentage of them were confirmed within 5 blocks and
  35  * then you would look at the next highest feerate bucket, and so on, stopping at
  36  * the last bucket to pass the test.   The average feerate of transactions in this
  37  * bucket will give you an indication of the lowest feerate you can put on a
  38  * transaction and still have a sufficiently high chance of being confirmed
  39  * within your desired 5 blocks.
  40  *
  41  * Here is a brief description of the implementation:
  42  * When a transaction enters the mempool, we
  43  * track the height of the block chain at entry.  Whenever a block comes in,
  44  * we count the number of transactions in each bucket and the total amount of feerate
  45  * paid in each bucket. Then we calculate how many blocks Y it took each
  46  * transaction to be mined and we track an array of counters in each bucket
  47  * for how long it to took transactions to get confirmed from 1 to a max of 25
  48  * and we increment all the counters from Y up to 25. This is because for any
  49  * number Z>=Y the transaction was successfully mined within Z blocks.  We
  50  * want to save a history of this information, so at any time we have a
  51  * counter of the total number of transactions that happened in a given feerate
  52  * bucket and the total number that were confirmed in each number 1-25 blocks
  53  * or less for any bucket.   We save this history by keeping an exponentially
  54  * decaying moving average of each one of these stats.  Furthermore we also
  55  * keep track of the number unmined (in mempool) transactions in each bucket
  56  * and for how many blocks they have been outstanding and use that to increase
  57  * the number of transactions we've seen in that feerate bucket when calculating
  58  * an estimate for any number of confirmations below the number of blocks
  59  * they've been outstanding.
  60  */
  61
  62 /**
  63  * We will instantiate an instance of this class to track transactions that were
  64  * included in a block. We will lump transactions into a bucket according to their
  65  * approximate feerate and then track how long it took for those txs to be included in a block
  66  *
  67  * The tracking of unconfirmed (mempool) transactions is completely independent of the
  68  * historical tracking of transactions that have been confirmed in a block.
  69  */
  70 class TxConfirmStats
  71 {
  72 private:
  73     //Define the buckets we will group transactions into
  74     std::vector<double> buckets;              // The upper-bound of the range for the bucket (inclusive)
  75     std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
  76
  77     // For each bucket X:
  78     // Count the total # of txs in each bucket
  79     // Track the historical moving average of this total over blocks
  80     std::vector<double> txCtAvg;
  81     // and calculate the total for the current block to update the moving average
  82     std::vector<int> curBlockTxCt;
  83
  84     // Count the total # of txs confirmed within Y blocks in each bucket
  85     // Track the historical moving average of theses totals over blocks
  86     std::vector<std::vector<double> > confAvg; // confAvg[Y][X]
  87     // and calculate the totals for the current block to update the moving averages
  88     std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X]
  89
  90     // Sum the total feerate of all tx's in each bucket
  91     // Track the historical moving average of this total over blocks
  92     std::vector<double> avg;
  93     // and calculate the total for the current block to update the moving average
  94     std::vector<double> curBlockVal;
  95
  96     // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
  97     // Combine the total value with the tx counts to calculate the avg feerate per bucket
  98
  99     double decay;
 100
 101     // Mempool counts of outstanding transactions
 102     // For each bucket X, track the number of transactions in the mempool
 103     // that are unconfirmed for each possible confirmation value Y
 104     std::vector<std::vector<int> > unconfTxs;  //unconfTxs[Y][X]
 105     // transactions still unconfirmed after MAX_CONFIRMS for each bucket
 106     std::vector<int> oldUnconfTxs;
 107
 108 public:
 109     /**
 110      * Initialize the data structures.  This is called by BlockPolicyEstimator's
 111      * constructor with default values.
 112      * @param defaultBuckets contains the upper limits for the bucket boundaries
 113      * @param maxConfirms max number of confirms to track
 114      * @param decay how much to decay the historical moving average per block
 115      */
 116     void Initialize(std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay);
 117
 118     /** Clear the state of the curBlock variables to start counting for the new block */
 119     void ClearCurrent(unsigned int nBlockHeight);
 120
 121     /**
 122      * Record a new transaction data point in the current block stats
 123      * @param blocksToConfirm the number of blocks it took this transaction to confirm
 124      * @param val the feerate of the transaction
 125      * @warning blocksToConfirm is 1-based and has to be >= 1
 126      */
 127     void Record(int blocksToConfirm, double val);
 128
 129     /** Record a new transaction entering the mempool*/
 130     unsigned int NewTx(unsigned int nBlockHeight, double val);
 131
 132     /** Remove a transaction from mempool tracking stats*/
 133     void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
 134                   unsigned int bucketIndex);
 135
 136     /** Update our estimates by decaying our historical moving average and updating
 137         with the data gathered from the current block */
 138     void UpdateMovingAverages();
 139
 140     /**
 141      * Calculate a feerate estimate.  Find the lowest value bucket (or range of buckets
 142      * to make sure we have enough data points) whose transactions still have sufficient likelihood
 143      * of being confirmed within the target number of confirmations
 144      * @param confTarget target number of confirmations
 145      * @param sufficientTxVal required average number of transactions per block in a bucket range
 146      * @param minSuccess the success probability we require
 147      * @param requireGreater return the lowest feerate such that all higher values pass minSuccess OR
 148      *        return the highest feerate such that all lower values fail minSuccess
 149      * @param nBlockHeight the current block height
 150      */
 151     double EstimateMedianVal(int confTarget, double sufficientTxVal,
 152                              double minSuccess, bool requireGreater, unsigned int nBlockHeight);
 153
 154     /** Return the max number of confirms we're tracking */
 155     unsigned int GetMaxConfirms() { return confAvg.size(); }
 156
 157     /** Write state of estimation data to a file*/
 158     void Write(CAutoFile& fileout);
 159
 160     /**
 161      * Read saved state of estimation data from a file and replace all internal data structures and
 162      * variables with this state.
 163      */
 164     void Read(CAutoFile& filein);
 165 };
 166
 167
 168
 169 /** Track confirm delays up to 25 blocks, can't estimate beyond that */
 170 static const unsigned int MAX_BLOCK_CONFIRMS = 25;
 171
 172 /** Decay of .998 is a half-life of 346 blocks or about 2.4 days */
 173 static const double DEFAULT_DECAY = .998;
 174
 175 /** Require greater than 95% of X feerate transactions to be confirmed within Y blocks for X to be big enough */
 176 static const double MIN_SUCCESS_PCT = .95;
 177
 178 /** Require an avg of 1 tx in the combined feerate bucket per block to have stat significance */
 179 static const double SUFFICIENT_FEETXS = 1;
 180
 181 // Minimum and Maximum values for tracking feerates
 182 static const double MIN_FEERATE = 10;
 183 static const double MAX_FEERATE = 1e7;
 184 static const double INF_FEERATE = MAX_MONEY;
 185 static const double INF_PRIORITY = 1e9 * MAX_MONEY;
 186
 187 // We have to lump transactions into buckets based on feerate, but we want to be able
 188 // to give accurate estimates over a large range of potential feerates
 189 // Therefore it makes sense to exponentially space the buckets
 190 /** Spacing of FeeRate buckets */
 191 static const double FEE_SPACING = 1.1;
 192
 193 /**
 194  *  We want to be able to estimate feerates that are needed on tx's to be included in
 195  * a certain number of blocks.  Every time a block is added to the best chain, this class records
 196  * stats on the transactions included in that block
 197  */
 198 class CBlockPolicyEstimator
 199 {
 200 public:
 201     /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
 202     CBlockPolicyEstimator(const CFeeRate& minRelayFee);
 203
 204     /** Process all the transactions that have been included in a block */
 205     void processBlock(unsigned int nBlockHeight,
 206                       std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate);
 207
 208     /** Process a transaction confirmed in a block*/
 209     void processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry);
 210
 211     /** Process a transaction accepted to the mempool*/
 212     void processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate);
 213
 214     /** Remove a transaction from the mempool tracking stats*/
 215     void removeTx(uint256 hash);
 216
 217     /** Return a feerate estimate */
 218     CFeeRate estimateFee(int confTarget);
 219
 220     /** Estimate feerate needed to get be included in a block within
 221      *  confTarget blocks. If no answer can be given at confTarget, return an
 222      *  estimate at the lowest target where one can be given.
 223      */
 224     CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool);
 225
 226     /** Return a priority estimate.
 227      *  DEPRECATED
 228      *  Returns -1
 229      */
 230     double estimatePriority(int confTarget);
 231
 232     /** Estimate priority needed to get be included in a block within
 233      *  confTarget blocks.
 234      *  DEPRECATED
 235      *  Returns -1 unless mempool is currently limited then returns INF_PRIORITY
 236      *  answerFoundAtTarget is set to confTarget
 237      */
 238     double estimateSmartPriority(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool);
 239
 240     /** Write estimation data to a file */
 241     void Write(CAutoFile& fileout);
 242
 243     /** Read estimation data from a file */
 244     void Read(CAutoFile& filein, int nFileVersion);
 245
 246 private:
 247     CFeeRate minTrackedFee;    //!< Passed to constructor to avoid dependency on main
 248     unsigned int nBestSeenHeight;
 249     struct TxStatsInfo
 250     {
 251         unsigned int blockHeight;
 252         unsigned int bucketIndex;
 253         TxStatsInfo() : blockHeight(0), bucketIndex(0) {}
 254     };
 255
 256     // map of txids to information about that transaction
 257     std::map<uint256, TxStatsInfo> mapMemPoolTxs;
 258
 259     /** Classes to track historical data on transaction confirmations */
 260     TxConfirmStats feeStats;
 261 };
 262
 263 class FeeFilterRounder
 264 {
 265 public:
 266     /** Create new FeeFilterRounder */
 267     FeeFilterRounder(const CFeeRate& minIncrementalFee);
 268
 269     /** Quantize a minimum fee for privacy purpose before broadcast **/
 270     CAmount round(CAmount currentMinFee);
 271
 272 private:
 273     std::set<double> feeset;
 274     FastRandomContext insecure_rand;
 275 };
 276 #endif /*BITCOIN_POLICYESTIMATOR_H */