Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2021 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 <consensus/amount.h>
# 9 : : #include <policy/feerate.h>
# 10 : : #include <uint256.h>
# 11 : : #include <random.h>
# 12 : : #include <sync.h>
# 13 : :
# 14 : : #include <array>
# 15 : : #include <map>
# 16 : : #include <memory>
# 17 : : #include <string>
# 18 : : #include <vector>
# 19 : :
# 20 : : class CAutoFile;
# 21 : : class CFeeRate;
# 22 : : class CTxMemPoolEntry;
# 23 : : class CTxMemPool;
# 24 : : class TxConfirmStats;
# 25 : :
# 26 : : /* Identifier for each of the 3 different TxConfirmStats which will track
# 27 : : * history over different time horizons. */
# 28 : : enum class FeeEstimateHorizon {
# 29 : : SHORT_HALFLIFE,
# 30 : : MED_HALFLIFE,
# 31 : : LONG_HALFLIFE,
# 32 : : };
# 33 : :
# 34 : : static constexpr auto ALL_FEE_ESTIMATE_HORIZONS = std::array{
# 35 : : FeeEstimateHorizon::SHORT_HALFLIFE,
# 36 : : FeeEstimateHorizon::MED_HALFLIFE,
# 37 : : FeeEstimateHorizon::LONG_HALFLIFE,
# 38 : : };
# 39 : :
# 40 : : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);
# 41 : :
# 42 : : /* Enumeration of reason for returned fee estimate */
# 43 : : enum class FeeReason {
# 44 : : NONE,
# 45 : : HALF_ESTIMATE,
# 46 : : FULL_ESTIMATE,
# 47 : : DOUBLE_ESTIMATE,
# 48 : : CONSERVATIVE,
# 49 : : MEMPOOL_MIN,
# 50 : : PAYTXFEE,
# 51 : : FALLBACK,
# 52 : : REQUIRED,
# 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 .9952 is a half-life of 144 blocks or about 1 day */
# 149 : : static constexpr double MED_DECAY = .9952;
# 150 : : /** Decay of .99931 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 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 191 : :
# 192 : : /** Process a transaction accepted to the mempool*/
# 193 : : void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
# 194 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 195 : :
# 196 : : /** Remove a transaction from the mempool tracking stats*/
# 197 : : bool removeTx(uint256 hash, bool inBlock)
# 198 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 199 : :
# 200 : : /** DEPRECATED. Return a feerate estimate */
# 201 : : CFeeRate estimateFee(int confTarget) const
# 202 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 203 : :
# 204 : : /** Estimate feerate needed to get be included in a block within confTarget
# 205 : : * blocks. If no answer can be given at confTarget, return an estimate at
# 206 : : * the closest target where one can be given. 'conservative' estimates are
# 207 : : * valid over longer time horizons also.
# 208 : : */
# 209 : : CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
# 210 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 211 : :
# 212 : : /** Return a specific fee estimate calculation with a given success
# 213 : : * threshold and time horizon, and optionally return detailed data about
# 214 : : * calculation
# 215 : : */
# 216 : : CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon,
# 217 : : EstimationResult* result = nullptr) const
# 218 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 219 : :
# 220 : : /** Write estimation data to a file */
# 221 : : bool Write(CAutoFile& fileout) const
# 222 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 223 : :
# 224 : : /** Read estimation data from a file */
# 225 : : bool Read(CAutoFile& filein)
# 226 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 227 : :
# 228 : : /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */
# 229 : : void FlushUnconfirmed()
# 230 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 231 : :
# 232 : : /** Calculation of highest target that estimates are tracked for */
# 233 : : unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
# 234 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 235 : :
# 236 : : /** Drop still unconfirmed transactions and record current estimations, if the fee estimation file is present. */
# 237 : : void Flush()
# 238 : : EXCLUSIVE_LOCKS_REQUIRED(!m_cs_fee_estimator);
# 239 : :
# 240 : : private:
# 241 : : mutable Mutex m_cs_fee_estimator;
# 242 : :
# 243 : : unsigned int nBestSeenHeight GUARDED_BY(m_cs_fee_estimator);
# 244 : : unsigned int firstRecordedHeight GUARDED_BY(m_cs_fee_estimator);
# 245 : : unsigned int historicalFirst GUARDED_BY(m_cs_fee_estimator);
# 246 : : unsigned int historicalBest GUARDED_BY(m_cs_fee_estimator);
# 247 : :
# 248 : : struct TxStatsInfo
# 249 : : {
# 250 : : unsigned int blockHeight;
# 251 : : unsigned int bucketIndex;
# 252 : 66166 : TxStatsInfo() : blockHeight(0), bucketIndex(0) {}
# 253 : : };
# 254 : :
# 255 : : // map of txids to information about that transaction
# 256 : : std::map<uint256, TxStatsInfo> mapMemPoolTxs GUARDED_BY(m_cs_fee_estimator);
# 257 : :
# 258 : : /** Classes to track historical data on transaction confirmations */
# 259 : : std::unique_ptr<TxConfirmStats> feeStats PT_GUARDED_BY(m_cs_fee_estimator);
# 260 : : std::unique_ptr<TxConfirmStats> shortStats PT_GUARDED_BY(m_cs_fee_estimator);
# 261 : : std::unique_ptr<TxConfirmStats> longStats PT_GUARDED_BY(m_cs_fee_estimator);
# 262 : :
# 263 : : unsigned int trackedTxs GUARDED_BY(m_cs_fee_estimator);
# 264 : : unsigned int untrackedTxs GUARDED_BY(m_cs_fee_estimator);
# 265 : :
# 266 : : std::vector<double> buckets GUARDED_BY(m_cs_fee_estimator); // The upper-bound of the range for the bucket (inclusive)
# 267 : : std::map<double, unsigned int> bucketMap GUARDED_BY(m_cs_fee_estimator); // Map of bucket upper-bound to index into all vectors by bucket
# 268 : :
# 269 : : /** Process a transaction confirmed in a block*/
# 270 : : bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 271 : :
# 272 : : /** Helper for estimateSmartFee */
# 273 : : double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 274 : : /** Helper for estimateSmartFee */
# 275 : : double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 276 : : /** Number of blocks of data recorded while fee estimates have been running */
# 277 : : unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 278 : : /** Number of blocks of recorded fee estimate data represented in saved data file */
# 279 : : unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 280 : : /** Calculation of highest target that reasonable estimate can be provided for */
# 281 : : unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 282 : :
# 283 : : /** A non-thread-safe helper for the removeTx function */
# 284 : : bool _removeTx(const uint256& hash, bool inBlock)
# 285 : : EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator);
# 286 : : };
# 287 : :
# 288 : : class FeeFilterRounder
# 289 : : {
# 290 : : private:
# 291 : : static constexpr double MAX_FILTER_FEERATE = 1e7;
# 292 : : /** FEE_FILTER_SPACING is just used to provide some quantization of fee
# 293 : : * filter results. Historically it reused FEE_SPACING, but it is completely
# 294 : : * unrelated, and was made a separate constant so the two concepts are not
# 295 : : * tied together */
# 296 : : static constexpr double FEE_FILTER_SPACING = 1.1;
# 297 : :
# 298 : : public:
# 299 : : /** Create new FeeFilterRounder */
# 300 : : explicit FeeFilterRounder(const CFeeRate& minIncrementalFee);
# 301 : :
# 302 : : /** Quantize a minimum fee for privacy purpose before broadcast. Not thread-safe due to use of FastRandomContext */
# 303 : : CAmount round(CAmount currentMinFee);
# 304 : :
# 305 : : private:
# 306 : : std::set<double> feeset;
# 307 : : FastRandomContext insecure_rand;
# 308 : : };
# 309 : :
# 310 : : #endif // BITCOIN_POLICY_FEES_H
|
