Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2022 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 <threadsafety.h>
13 : #include <uint256.h>
14 : #include <util/fs.h>
15 : #include <validationinterface.h>
16 :
17 : #include <array>
18 : #include <chrono>
19 : #include <map>
20 : #include <memory>
21 : #include <set>
22 : #include <string>
23 : #include <vector>
24 :
25 :
26 : // How often to flush fee estimates to fee_estimates.dat.
27 : static constexpr std::chrono::hours FEE_FLUSH_INTERVAL{1};
28 :
29 : /** fee_estimates.dat that are more than 60 hours (2.5 days) old will not be read,
30 : * as fee estimates are based on historical data and may be inaccurate if
31 : * network activity has changed.
32 : */
33 : static constexpr std::chrono::hours MAX_FILE_AGE{60};
34 :
35 : // Whether we allow importing a fee_estimates file older than MAX_FILE_AGE.
36 : static constexpr bool DEFAULT_ACCEPT_STALE_FEE_ESTIMATES{false};
37 :
38 : class AutoFile;
39 : class TxConfirmStats;
40 : struct RemovedMempoolTransactionInfo;
41 : struct NewMempoolTransactionInfo;
42 :
43 : /* Identifier for each of the 3 different TxConfirmStats which will track
44 : * history over different time horizons. */
45 : enum class FeeEstimateHorizon {
46 : SHORT_HALFLIFE,
47 : MED_HALFLIFE,
48 : LONG_HALFLIFE,
49 : };
50 :
51 : static constexpr auto ALL_FEE_ESTIMATE_HORIZONS = std::array{
52 : FeeEstimateHorizon::SHORT_HALFLIFE,
53 : FeeEstimateHorizon::MED_HALFLIFE,
54 : FeeEstimateHorizon::LONG_HALFLIFE,
55 : };
56 :
57 : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon);
58 :
59 : /* Enumeration of reason for returned fee estimate */
60 : enum class FeeReason {
61 : NONE,
62 : HALF_ESTIMATE,
63 : FULL_ESTIMATE,
64 : DOUBLE_ESTIMATE,
65 : CONSERVATIVE,
66 : MEMPOOL_MIN,
67 : PAYTXFEE,
68 : FALLBACK,
69 : REQUIRED,
70 : };
71 :
72 : /* Used to return detailed information about a feerate bucket */
73 : struct EstimatorBucket
74 : {
75 : double start = -1;
76 : double end = -1;
77 : double withinTarget = 0;
78 : double totalConfirmed = 0;
79 : double inMempool = 0;
80 : double leftMempool = 0;
81 : };
82 :
83 : /* Used to return detailed information about a fee estimate calculation */
84 : struct EstimationResult
85 : {
86 : EstimatorBucket pass;
87 : EstimatorBucket fail;
88 : double decay = 0;
89 : unsigned int scale = 0;
90 : };
91 :
92 : struct FeeCalculation
93 : {
94 : EstimationResult est;
95 : FeeReason reason = FeeReason::NONE;
96 : int desiredTarget = 0;
97 : int returnedTarget = 0;
98 : unsigned int best_height{0};
99 : };
100 :
101 : /** \class CBlockPolicyEstimator
102 : * The BlockPolicyEstimator is used for estimating the feerate needed
103 : * for a transaction to be included in a block within a certain number of
104 : * blocks.
105 : *
106 : * At a high level the algorithm works by grouping transactions into buckets
107 : * based on having similar feerates and then tracking how long it
108 : * takes transactions in the various buckets to be mined. It operates under
109 : * the assumption that in general transactions of higher feerate will be
110 : * included in blocks before transactions of lower feerate. So for
111 : * example if you wanted to know what feerate you should put on a transaction to
112 : * be included in a block within the next 5 blocks, you would start by looking
113 : * at the bucket with the highest feerate transactions and verifying that a
114 : * sufficiently high percentage of them were confirmed within 5 blocks and
115 : * then you would look at the next highest feerate bucket, and so on, stopping at
116 : * the last bucket to pass the test. The average feerate of transactions in this
117 : * bucket will give you an indication of the lowest feerate you can put on a
118 : * transaction and still have a sufficiently high chance of being confirmed
119 : * within your desired 5 blocks.
120 : *
121 : * Here is a brief description of the implementation:
122 : * When a transaction enters the mempool, we track the height of the block chain
123 : * at entry. All further calculations are conducted only on this set of "seen"
124 : * transactions. Whenever a block comes in, we count the number of transactions
125 : * in each bucket and the total amount of feerate paid in each bucket. Then we
126 : * calculate how many blocks Y it took each transaction to be mined. We convert
127 : * from a number of blocks to a number of periods Y' each encompassing "scale"
128 : * blocks. This is tracked in 3 different data sets each up to a maximum
129 : * number of periods. Within each data set we have an array of counters in each
130 : * feerate bucket and we increment all the counters from Y' up to max periods
131 : * representing that a tx was successfully confirmed in less than or equal to
132 : * that many periods. We want to save a history of this information, so at any
133 : * time we have a counter of the total number of transactions that happened in a
134 : * given feerate bucket and the total number that were confirmed in each of the
135 : * periods or less for any bucket. We save this history by keeping an
136 : * exponentially decaying moving average of each one of these stats. This is
137 : * done for a different decay in each of the 3 data sets to keep relevant data
138 : * from different time horizons. Furthermore we also keep track of the number
139 : * unmined (in mempool or left mempool without being included in a block)
140 : * transactions in each bucket and for how many blocks they have been
141 : * outstanding and use both of these numbers to increase the number of transactions
142 : * we've seen in that feerate bucket when calculating an estimate for any number
143 : * of confirmations below the number of blocks they've been outstanding.
144 : *
145 : * We want to be able to estimate feerates that are needed on tx's to be included in
146 : * a certain number of blocks. Every time a block is added to the best chain, this class records
147 : * stats on the transactions included in that block
148 : */
149 : class CBlockPolicyEstimator : public CValidationInterface
150 : {
151 : private:
152 : /** Track confirm delays up to 12 blocks for short horizon */
153 : static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
154 : static constexpr unsigned int SHORT_SCALE = 1;
155 : /** Track confirm delays up to 48 blocks for medium horizon */
156 : static constexpr unsigned int MED_BLOCK_PERIODS = 24;
157 : static constexpr unsigned int MED_SCALE = 2;
158 : /** Track confirm delays up to 1008 blocks for long horizon */
159 : static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
160 : static constexpr unsigned int LONG_SCALE = 24;
161 : /** Historical estimates that are older than this aren't valid */
162 : static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
163 :
164 : /** Decay of .962 is a half-life of 18 blocks or about 3 hours */
165 : static constexpr double SHORT_DECAY = .962;
166 : /** Decay of .9952 is a half-life of 144 blocks or about 1 day */
167 : static constexpr double MED_DECAY = .9952;
168 : /** Decay of .99931 is a half-life of 1008 blocks or about 1 week */
169 : static constexpr double LONG_DECAY = .99931;
170 :
171 : /** Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks*/
172 : static constexpr double HALF_SUCCESS_PCT = .6;
173 : /** Require greater than 85% of X feerate transactions to be confirmed within Y blocks*/
174 : static constexpr double SUCCESS_PCT = .85;
175 : /** Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks*/
176 : static constexpr double DOUBLE_SUCCESS_PCT = .95;
177 :
178 : /** Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance */
179 : static constexpr double SUFFICIENT_FEETXS = 0.1;
180 : /** Require an avg of 0.5 tx when using short decay since there are fewer blocks considered*/
181 : static constexpr double SUFFICIENT_TXS_SHORT = 0.5;
182 :
183 : /** Minimum and Maximum values for tracking feerates
184 : * The MIN_BUCKET_FEERATE should just be set to the lowest reasonable feerate we
185 : * might ever want to track. Historically this has been 1000 since it was
186 : * inheriting DEFAULT_MIN_RELAY_TX_FEE and changing it is disruptive as it
187 : * invalidates old estimates files. So leave it at 1000 unless it becomes
188 : * necessary to lower it, and then lower it substantially.
189 : */
190 : static constexpr double MIN_BUCKET_FEERATE = 1000;
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, const 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 24560 : 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 1 : 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
|
