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 /** Track confirm delays up to 25 blocks, can't estimate beyond that */
  65 static const unsigned int MAX_BLOCK_CONFIRMS = 25;
  66
  67 /** Decay of .998 is a half-life of 346 blocks or about 2.4 days */
  68 static const double DEFAULT_DECAY = .998;
  69
  70 /** Require greater than 95% of X feerate transactions to be confirmed within Y blocks for X to be big enough */
  71 static const double MIN_SUCCESS_PCT = .95;
  72
  73 /** Require an avg of 1 tx in the combined feerate bucket per block to have stat significance */
  74 static const double SUFFICIENT_FEETXS = 1;
  75
  76 // Minimum and Maximum values for tracking feerates
  77 // The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
  78 // might ever want to track.  Historically this has been 1000 since it was
  79 // inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
  80 // invalidates old estimates files. So leave it at 1000 unless it becomes
  81 // necessary to lower it, and then lower it substantially.
  82 static constexpr double MIN_BUCKET_FEERATE = 1000;
  83 static const double MAX_BUCKET_FEERATE = 1e7;
  84 static const double INF_FEERATE = MAX_MONEY;
  85
  86 // We have to lump transactions into buckets based on feerate, but we want to be able
  87 // to give accurate estimates over a large range of potential feerates
  88 // Therefore it makes sense to exponentially space the buckets
  89 /** Spacing of FeeRate buckets */
  90 static const double FEE_SPACING = 1.1;
  91
  92 /**
  93  *  We want to be able to estimate feerates that are needed on tx's to be included in
  94  * a certain number of blocks.  Every time a block is added to the best chain, this class records
  95  * stats on the transactions included in that block
  96  */
  97 class CBlockPolicyEstimator
  98 {
  99 public:
 100     /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */
 101     CBlockPolicyEstimator();
 102     ~CBlockPolicyEstimator();
 103
 104     /** Process all the transactions that have been included in a block */
 105     void processBlock(unsigned int nBlockHeight,
 106                       std::vector<const CTxMemPoolEntry*>& entries);
 107
 108     /** Process a transaction accepted to the mempool*/
 109     void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate);
 110
 111     /** Remove a transaction from the mempool tracking stats*/
 112     bool removeTx(uint256 hash);
 113
 114     /** Return a feerate estimate */
 115     CFeeRate estimateFee(int confTarget) const;
 116
 117     /** Estimate feerate needed to get be included in a block within
 118      *  confTarget blocks. If no answer can be given at confTarget, return an
 119      *  estimate at the lowest target where one can be given.
 120      */
 121     CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool) const;
 122
 123     /** Write estimation data to a file */
 124     bool Write(CAutoFile& fileout) const;
 125
 126     /** Read estimation data from a file */
 127     bool Read(CAutoFile& filein);
 128
 129 private:
 130     CFeeRate minTrackedFee;    //!< Passed to constructor to avoid dependency on main
 131     unsigned int nBestSeenHeight;
 132     struct TxStatsInfo
 133     {
 134         unsigned int blockHeight;
 135         unsigned int bucketIndex;
 136         TxStatsInfo() : blockHeight(0), bucketIndex(0) {}
 137     };
 138
 139     // map of txids to information about that transaction
 140     std::map<uint256, TxStatsInfo> mapMemPoolTxs;
 141
 142     /** Classes to track historical data on transaction confirmations */
 143     TxConfirmStats* feeStats;
 144
 145     unsigned int trackedTxs;
 146     unsigned int untrackedTxs;
 147
 148     mutable CCriticalSection cs_feeEstimator;
 149
 150     /** Process a transaction confirmed in a block*/
 151     bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry);
 152
 153 };
 154
 155 class FeeFilterRounder
 156 {
 157 public:
 158     /** Create new FeeFilterRounder */
 159     FeeFilterRounder(const CFeeRate& minIncrementalFee);
 160
 161     /** Quantize a minimum fee for privacy purpose before broadcast **/
 162     CAmount round(CAmount currentMinFee);
 163
 164 private:
 165     std::set<double> feeset;
 166     FastRandomContext insecure_rand;
 167 };
 168 #endif /*BITCOIN_POLICYESTIMATOR_H */