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