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