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