Branch data 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 : :
6 : : #include <policy/fees.h>
7 : :
8 : : #include <common/system.h>
9 : : #include <consensus/amount.h>
10 : : #include <kernel/mempool_entry.h>
11 : : #include <logging.h>
12 : : #include <policy/feerate.h>
13 : : #include <primitives/transaction.h>
14 : : #include <random.h>
15 : : #include <serialize.h>
16 : : #include <streams.h>
17 : : #include <sync.h>
18 : : #include <tinyformat.h>
19 : : #include <uint256.h>
20 : : #include <util/fs.h>
21 : : #include <util/serfloat.h>
22 : : #include <util/time.h>
23 : :
24 : : #include <algorithm>
25 : : #include <cassert>
26 : : #include <chrono>
27 : : #include <cmath>
28 : : #include <cstddef>
29 : : #include <cstdint>
30 : : #include <exception>
31 : : #include <stdexcept>
32 : : #include <utility>
33 : :
34 : : // The current format written, and the version required to read. Must be
35 : : // increased to at least 289900+1 on the next breaking change.
36 : : constexpr int CURRENT_FEES_FILE_VERSION{149900};
37 : :
38 : : static constexpr double INF_FEERATE = 1e99;
39 : :
40 : 49 : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
41 : : {
42 [ + + + - ]: 49 : switch (horizon) {
43 : 21 : case FeeEstimateHorizon::SHORT_HALFLIFE: return "short";
44 : 9 : case FeeEstimateHorizon::MED_HALFLIFE: return "medium";
45 : 19 : case FeeEstimateHorizon::LONG_HALFLIFE: return "long";
46 : : } // no default case, so the compiler can warn about missing cases
47 : 0 : assert(false);
48 : : }
49 : :
50 : : namespace {
51 : :
52 : : struct EncodedDoubleFormatter
53 : : {
54 : 316211 : template<typename Stream> void Ser(Stream &s, double v)
55 : : {
56 : 316211 : s << EncodeDouble(v);
57 : : }
58 : :
59 : 942090 : template<typename Stream> void Unser(Stream& s, double& v)
60 : : {
61 : : uint64_t encoded;
62 : 941977 : s >> encoded;
63 : 941977 : v = DecodeDouble(encoded);
64 : 941977 : }
65 : : };
66 : :
67 : : } // namespace
68 : :
69 : : /**
70 : : * We will instantiate an instance of this class to track transactions that were
71 : : * included in a block. We will lump transactions into a bucket according to their
72 : : * approximate feerate and then track how long it took for those txs to be included in a block
73 : : *
74 : : * The tracking of unconfirmed (mempool) transactions is completely independent of the
75 : : * historical tracking of transactions that have been confirmed in a block.
76 : : */
77 : : class TxConfirmStats
78 : : {
79 : : private:
80 : : //Define the buckets we will group transactions into
81 : : const std::vector<double>& buckets; // The upper-bound of the range for the bucket (inclusive)
82 : : const std::map<double, unsigned int>& bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
83 : :
84 : : // For each bucket X:
85 : : // Count the total # of txs in each bucket
86 : : // Track the historical moving average of this total over blocks
87 : : std::vector<double> txCtAvg;
88 : :
89 : : // Count the total # of txs confirmed within Y blocks in each bucket
90 : : // Track the historical moving average of these totals over blocks
91 : : std::vector<std::vector<double>> confAvg; // confAvg[Y][X]
92 : :
93 : : // Track moving avg of txs which have been evicted from the mempool
94 : : // after failing to be confirmed within Y blocks
95 : : std::vector<std::vector<double>> failAvg; // failAvg[Y][X]
96 : :
97 : : // Sum the total feerate of all tx's in each bucket
98 : : // Track the historical moving average of this total over blocks
99 : : std::vector<double> m_feerate_avg;
100 : :
101 : : // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
102 : : // Combine the total value with the tx counts to calculate the avg feerate per bucket
103 : :
104 : : double decay;
105 : :
106 : : // Resolution (# of blocks) with which confirmations are tracked
107 : : unsigned int scale;
108 : :
109 : : // Mempool counts of outstanding transactions
110 : : // For each bucket X, track the number of transactions in the mempool
111 : : // that are unconfirmed for each possible confirmation value Y
112 : : std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
113 : : // transactions still unconfirmed after GetMaxConfirms for each bucket
114 : : std::vector<int> oldUnconfTxs;
115 : :
116 : : void resizeInMemoryCounters(size_t newbuckets);
117 : :
118 : : public:
119 : : /**
120 : : * Create new TxConfirmStats. This is called by BlockPolicyEstimator's
121 : : * constructor with default values.
122 : : * @param defaultBuckets contains the upper limits for the bucket boundaries
123 : : * @param maxPeriods max number of periods to track
124 : : * @param decay how much to decay the historical moving average per block
125 : : */
126 : : TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,
127 : : unsigned int maxPeriods, double decay, unsigned int scale);
128 : :
129 : : /** Roll the circular buffer for unconfirmed txs*/
130 : : void ClearCurrent(unsigned int nBlockHeight);
131 : :
132 : : /**
133 : : * Record a new transaction data point in the current block stats
134 : : * @param blocksToConfirm the number of blocks it took this transaction to confirm
135 : : * @param val the feerate of the transaction
136 : : * @warning blocksToConfirm is 1-based and has to be >= 1
137 : : */
138 : : void Record(int blocksToConfirm, double val);
139 : :
140 : : /** Record a new transaction entering the mempool*/
141 : : unsigned int NewTx(unsigned int nBlockHeight, double val);
142 : :
143 : : /** Remove a transaction from mempool tracking stats*/
144 : : void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
145 : : unsigned int bucketIndex, bool inBlock);
146 : :
147 : : /** Update our estimates by decaying our historical moving average and updating
148 : : with the data gathered from the current block */
149 : : void UpdateMovingAverages();
150 : :
151 : : /**
152 : : * Calculate a feerate estimate. Find the lowest value bucket (or range of buckets
153 : : * to make sure we have enough data points) whose transactions still have sufficient likelihood
154 : : * of being confirmed within the target number of confirmations
155 : : * @param confTarget target number of confirmations
156 : : * @param sufficientTxVal required average number of transactions per block in a bucket range
157 : : * @param minSuccess the success probability we require
158 : : * @param nBlockHeight the current block height
159 : : */
160 : : double EstimateMedianVal(int confTarget, double sufficientTxVal,
161 : : double minSuccess, unsigned int nBlockHeight,
162 : : EstimationResult *result = nullptr) const;
163 : :
164 : : /** Return the max number of confirms we're tracking */
165 [ + + + + : 46914 : unsigned int GetMaxConfirms() const { return scale * confAvg.size(); }
+ + + + +
+ + + + +
+ + + + +
+ ]
166 : :
167 : : /** Write state of estimation data to a file*/
168 : : void Write(AutoFile& fileout) const;
169 : :
170 : : /**
171 : : * Read saved state of estimation data from a file and replace all internal data structures and
172 : : * variables with this state.
173 : : */
174 : : void Read(AutoFile& filein, size_t numBuckets);
175 : : };
176 : :
177 : :
178 : 3330 : TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
179 : : const std::map<double, unsigned int>& defaultBucketMap,
180 : 3330 : unsigned int maxPeriods, double _decay, unsigned int _scale)
181 [ - + ]: 3330 : : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_scale)
182 : : {
183 [ - + ]: 3330 : assert(_scale != 0 && "_scale must be non-zero");
184 [ + - ]: 3330 : confAvg.resize(maxPeriods);
185 [ + - ]: 3330 : failAvg.resize(maxPeriods);
186 [ + + ]: 89910 : for (unsigned int i = 0; i < maxPeriods; i++) {
187 [ + - ]: 86580 : confAvg[i].resize(buckets.size());
188 [ + - ]: 86580 : failAvg[i].resize(buckets.size());
189 : : }
190 : :
191 [ + - ]: 3330 : txCtAvg.resize(buckets.size());
192 [ + - ]: 3330 : m_feerate_avg.resize(buckets.size());
193 : :
194 [ + - ]: 3330 : resizeInMemoryCounters(buckets.size());
195 : 3330 : }
196 : :
197 : 3594 : void TxConfirmStats::resizeInMemoryCounters(size_t newbuckets) {
198 : : // newbuckets must be passed in because the buckets referred to during Read have not been updated yet.
199 : 3594 : unconfTxs.resize(GetMaxConfirms());
200 [ + + ]: 1227200 : for (unsigned int i = 0; i < unconfTxs.size(); i++) {
201 : 1223606 : unconfTxs[i].resize(newbuckets);
202 : : }
203 : 3594 : oldUnconfTxs.resize(newbuckets);
204 : 3594 : }
205 : :
206 : : // Roll the unconfirmed txs circular buffer
207 : 2580 : void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
208 : : {
209 [ + + ]: 492780 : for (unsigned int j = 0; j < buckets.size(); j++) {
210 : 490200 : oldUnconfTxs[j] += unconfTxs[nBlockHeight % unconfTxs.size()][j];
211 : 490200 : unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
212 : : }
213 : 2580 : }
214 : :
215 : :
216 : 192 : void TxConfirmStats::Record(int blocksToConfirm, double feerate)
217 : : {
218 : : // blocksToConfirm is 1-based
219 [ + - ]: 192 : if (blocksToConfirm < 1)
220 : : return;
221 : 192 : int periodsToConfirm = (blocksToConfirm + scale - 1) / scale;
222 : 192 : unsigned int bucketindex = bucketMap.lower_bound(feerate)->second;
223 [ + + ]: 587 : for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
224 : 395 : confAvg[i - 1][bucketindex]++;
225 : : }
226 : 192 : txCtAvg[bucketindex]++;
227 : 192 : m_feerate_avg[bucketindex] += feerate;
228 : : }
229 : :
230 : 2580 : void TxConfirmStats::UpdateMovingAverages()
231 : : {
232 [ + - ]: 2580 : assert(confAvg.size() == failAvg.size());
233 [ + + ]: 492780 : for (unsigned int j = 0; j < buckets.size(); j++) {
234 [ + + ]: 13235400 : for (unsigned int i = 0; i < confAvg.size(); i++) {
235 : 12745200 : confAvg[i][j] *= decay;
236 : 12745200 : failAvg[i][j] *= decay;
237 : : }
238 : 490200 : m_feerate_avg[j] *= decay;
239 : 490200 : txCtAvg[j] *= decay;
240 : : }
241 : 2580 : }
242 : :
243 : : // returns -1 on error conditions
244 : 530 : double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
245 : : double successBreakPoint, unsigned int nBlockHeight,
246 : : EstimationResult *result) const
247 : : {
248 : : // Counters for a bucket (or range of buckets)
249 : 530 : double nConf = 0; // Number of tx's confirmed within the confTarget
250 : 530 : double totalNum = 0; // Total number of tx's that were ever confirmed
251 : 530 : int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
252 : 530 : double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
253 : 530 : const int periodTarget = (confTarget + scale - 1) / scale;
254 : 530 : const int maxbucketindex = buckets.size() - 1;
255 : :
256 : : // We'll combine buckets until we have enough samples.
257 : : // The near and far variables will define the range we've combined
258 : : // The best variables are the last range we saw which still had a high
259 : : // enough confirmation rate to count as success.
260 : : // The cur variables are the current range we're counting.
261 : 530 : unsigned int curNearBucket = maxbucketindex;
262 : 530 : unsigned int bestNearBucket = maxbucketindex;
263 : 530 : unsigned int curFarBucket = maxbucketindex;
264 : 530 : unsigned int bestFarBucket = maxbucketindex;
265 : :
266 : : // We'll always group buckets into sets that meet sufficientTxVal --
267 : : // this ensures that we're using consistent groups between different
268 : : // confirmation targets.
269 : 530 : double partialNum = 0;
270 : :
271 : 530 : bool foundAnswer = false;
272 : 530 : unsigned int bins = unconfTxs.size();
273 : 530 : bool newBucketRange = true;
274 : 530 : bool passing = true;
275 : 530 : EstimatorBucket passBucket;
276 : 530 : EstimatorBucket failBucket;
277 : :
278 : : // Start counting from highest feerate transactions
279 [ + + ]: 101230 : for (int bucket = maxbucketindex; bucket >= 0; --bucket) {
280 [ + + ]: 100700 : if (newBucketRange) {
281 : 530 : curNearBucket = bucket;
282 : 530 : newBucketRange = false;
283 : : }
284 : 100700 : curFarBucket = bucket;
285 : 100700 : nConf += confAvg[periodTarget - 1][bucket];
286 : 100700 : partialNum += txCtAvg[bucket];
287 : 100700 : totalNum += txCtAvg[bucket];
288 : 100700 : failNum += failAvg[periodTarget - 1][bucket];
289 [ + + ]: 15599760 : for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
290 : 15499060 : extraNum += unconfTxs[(nBlockHeight - confct) % bins][bucket];
291 [ + - ]: 100700 : extraNum += oldUnconfTxs[bucket];
292 : : // If we have enough transaction data points in this range of buckets,
293 : : // we can test for success
294 : : // (Only count the confirmed data points, so that each confirmation count
295 : : // will be looking at the same amount of data and same bucket breaks)
296 : :
297 [ + - ]: 100700 : if (partialNum < sufficientTxVal / (1 - decay)) {
298 : : // the buckets we've added in this round aren't sufficient
299 : : // so keep adding
300 : 100700 : continue;
301 : : } else {
302 : 0 : partialNum = 0; // reset for the next range we'll add
303 : :
304 : 0 : double curPct = nConf / (totalNum + failNum + extraNum);
305 : :
306 : : // Check to see if we are no longer getting confirmed at the success rate
307 [ # # ]: 0 : if (curPct < successBreakPoint) {
308 [ # # ]: 0 : if (passing == true) {
309 : : // First time we hit a failure record the failed bucket
310 [ # # ]: 0 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
311 [ # # ]: 0 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
312 [ # # ]: 0 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
313 : 0 : failBucket.end = buckets[failMaxBucket];
314 : 0 : failBucket.withinTarget = nConf;
315 : 0 : failBucket.totalConfirmed = totalNum;
316 : 0 : failBucket.inMempool = extraNum;
317 : 0 : failBucket.leftMempool = failNum;
318 : 0 : passing = false;
319 : : }
320 : 0 : continue;
321 : 0 : }
322 : : // Otherwise update the cumulative stats, and the bucket variables
323 : : // and reset the counters
324 : : else {
325 : 0 : failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
326 : 0 : foundAnswer = true;
327 : 0 : passing = true;
328 : 0 : passBucket.withinTarget = nConf;
329 : 0 : nConf = 0;
330 : 0 : passBucket.totalConfirmed = totalNum;
331 : 0 : totalNum = 0;
332 : 0 : passBucket.inMempool = extraNum;
333 : 0 : passBucket.leftMempool = failNum;
334 : 0 : failNum = 0;
335 : 0 : extraNum = 0;
336 : 0 : bestNearBucket = curNearBucket;
337 : 0 : bestFarBucket = curFarBucket;
338 : 0 : newBucketRange = true;
339 : : }
340 : : }
341 : : }
342 : :
343 : 530 : double median = -1;
344 : 530 : double txSum = 0;
345 : :
346 : : // Calculate the "average" feerate of the best bucket range that met success conditions
347 : : // Find the bucket with the median transaction and then report the average feerate from that bucket
348 : : // This is a compromise between finding the median which we can't since we don't save all tx's
349 : : // and reporting the average which is less accurate
350 [ + - ]: 530 : unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
351 [ + - ]: 530 : unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
352 [ + + ]: 1060 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
353 : 530 : txSum += txCtAvg[j];
354 : : }
355 [ - + ]: 530 : if (foundAnswer && txSum != 0) {
356 : 0 : txSum = txSum / 2;
357 [ # # ]: 0 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
358 [ # # ]: 0 : if (txCtAvg[j] < txSum)
359 : 0 : txSum -= txCtAvg[j];
360 : : else { // we're in the right bucket
361 : 0 : median = m_feerate_avg[j] / txCtAvg[j];
362 : 0 : break;
363 : : }
364 : : }
365 : :
366 [ # # ]: 0 : passBucket.start = minBucket ? buckets[minBucket-1] : 0;
367 : 0 : passBucket.end = buckets[maxBucket];
368 : : }
369 : :
370 : : // If we were passing until we reached last few buckets with insufficient data, then report those as failed
371 [ + - ]: 530 : if (passing && !newBucketRange) {
372 [ - + ]: 530 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
373 [ + - ]: 530 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
374 [ - + ]: 530 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
375 : 530 : failBucket.end = buckets[failMaxBucket];
376 : 530 : failBucket.withinTarget = nConf;
377 : 530 : failBucket.totalConfirmed = totalNum;
378 : 530 : failBucket.inMempool = extraNum;
379 : 530 : failBucket.leftMempool = failNum;
380 : : }
381 : :
382 : 530 : float passed_within_target_perc = 0.0;
383 : 530 : float failed_within_target_perc = 0.0;
384 [ - + ]: 530 : if ((passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool)) {
385 : 0 : passed_within_target_perc = 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool);
386 : : }
387 [ + + ]: 530 : if ((failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool)) {
388 : 342 : failed_within_target_perc = 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool);
389 : : }
390 : :
391 [ - + ]: 530 : LogDebug(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
392 : : confTarget, 100.0 * successBreakPoint, decay,
393 : : median, passBucket.start, passBucket.end,
394 : : passed_within_target_perc,
395 : : passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool,
396 : : failBucket.start, failBucket.end,
397 : : failed_within_target_perc,
398 : : failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool);
399 : :
400 : :
401 [ + + ]: 530 : if (result) {
402 : 351 : result->pass = passBucket;
403 : 351 : result->fail = failBucket;
404 : 351 : result->decay = decay;
405 : 351 : result->scale = scale;
406 : : }
407 : 530 : return median;
408 : : }
409 : :
410 : 351 : void TxConfirmStats::Write(AutoFile& fileout) const
411 : : {
412 : 351 : fileout << Using<EncodedDoubleFormatter>(decay);
413 : 351 : fileout << scale;
414 : 351 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
415 : 351 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
416 : 351 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
417 : 150 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
418 : 148 : }
419 : :
420 : 488 : void TxConfirmStats::Read(AutoFile& filein, size_t numBuckets)
421 : : {
422 : : // Read data file and do some very basic sanity checking
423 : : // buckets and bucketMap are not updated yet, so don't access them
424 : : // If there is a read failure, we'll just discard this entire object anyway
425 : 488 : size_t maxConfirms, maxPeriods;
426 : :
427 : : // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
428 : 488 : filein >> Using<EncodedDoubleFormatter>(decay);
429 [ + + + + ]: 467 : if (decay <= 0 || decay >= 1) {
430 [ + - ]: 10 : throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
431 : : }
432 : 457 : filein >> scale;
433 [ + + ]: 457 : if (scale == 0) {
434 [ + - ]: 5 : throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
435 : : }
436 : :
437 : 452 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
438 [ + + ]: 434 : if (m_feerate_avg.size() != numBuckets) {
439 [ + - ]: 12 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
440 : : }
441 : 422 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
442 [ + + ]: 416 : if (txCtAvg.size() != numBuckets) {
443 [ + - ]: 4 : throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
444 : : }
445 : 412 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
446 [ + + ]: 333 : maxPeriods = confAvg.size();
447 : 333 : maxConfirms = scale * maxPeriods;
448 : :
449 [ + + ]: 333 : if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
450 [ + - ]: 13 : throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
451 : : }
452 [ + + ]: 1796 : for (unsigned int i = 0; i < maxPeriods; i++) {
453 [ + + ]: 1481 : if (confAvg[i].size() != numBuckets) {
454 [ + - ]: 5 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
455 : : }
456 : : }
457 : :
458 : 315 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
459 [ + + ]: 282 : if (maxPeriods != failAvg.size()) {
460 [ + - ]: 8 : throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
461 : : }
462 [ + + ]: 1227 : for (unsigned int i = 0; i < maxPeriods; i++) {
463 [ + + ]: 963 : if (failAvg[i].size() != numBuckets) {
464 [ + - ]: 10 : throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
465 : : }
466 : : }
467 : :
468 : : // Resize the current block variables which aren't stored in the data file
469 : : // to match the number of confirms and buckets
470 : 264 : resizeInMemoryCounters(numBuckets);
471 : :
472 [ - + ]: 264 : LogDebug(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
473 : : numBuckets, maxConfirms);
474 : 264 : }
475 : :
476 : 906 : unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
477 : : {
478 : 906 : unsigned int bucketindex = bucketMap.lower_bound(val)->second;
479 : 906 : unsigned int blockIndex = nBlockHeight % unconfTxs.size();
480 : 906 : unconfTxs[blockIndex][bucketindex]++;
481 : 906 : return bucketindex;
482 : : }
483 : :
484 : 675 : void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex, bool inBlock)
485 : : {
486 : : //nBestSeenHeight is not updated yet for the new block
487 : 675 : int blocksAgo = nBestSeenHeight - entryHeight;
488 [ + + ]: 675 : if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
489 : : blocksAgo = 0;
490 [ - + ]: 417 : if (blocksAgo < 0) {
491 [ # # ]: 0 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error, blocks ago is negative for mempool tx\n");
492 : 0 : return; //This can't happen because we call this with our best seen height, no entries can have higher
493 : : }
494 : :
495 [ + + ]: 675 : if (blocksAgo >= (int)unconfTxs.size()) {
496 [ + + ]: 370 : if (oldUnconfTxs[bucketindex] > 0) {
497 : 40 : oldUnconfTxs[bucketindex]--;
498 : : } else {
499 [ - + ]: 330 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
500 : : bucketindex);
501 : : }
502 : : }
503 : : else {
504 [ + - ]: 305 : unsigned int blockIndex = entryHeight % unconfTxs.size();
505 [ + - ]: 305 : if (unconfTxs[blockIndex][bucketindex] > 0) {
506 : 305 : unconfTxs[blockIndex][bucketindex]--;
507 : : } else {
508 [ # # ]: 0 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
509 : : blockIndex, bucketindex);
510 : : }
511 : : }
512 [ + + + + ]: 675 : if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
513 [ - + ]: 183 : assert(scale != 0);
514 : 183 : unsigned int periodsAgo = blocksAgo / scale;
515 [ + + + + ]: 4699 : for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
516 : 4516 : failAvg[i][bucketindex]++;
517 : : }
518 : : }
519 : : }
520 : :
521 : 391 : bool CBlockPolicyEstimator::removeTx(uint256 hash)
522 : : {
523 : 391 : LOCK(m_cs_fee_estimator);
524 [ + - + - ]: 391 : return _removeTx(hash, /*inBlock=*/false);
525 : 391 : }
526 : :
527 : 12966 : bool CBlockPolicyEstimator::_removeTx(const uint256& hash, bool inBlock)
528 : : {
529 : 12966 : AssertLockHeld(m_cs_fee_estimator);
530 : 12966 : std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
531 [ + + ]: 12966 : if (pos != mapMemPoolTxs.end()) {
532 : 225 : feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
533 : 225 : shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
534 : 225 : longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
535 : 225 : mapMemPoolTxs.erase(hash);
536 : 225 : return true;
537 : : } else {
538 : : return false;
539 : : }
540 : : }
541 : :
542 : 837 : CBlockPolicyEstimator::CBlockPolicyEstimator(const fs::path& estimation_filepath, const bool read_stale_estimates)
543 : 837 : : m_estimation_filepath{estimation_filepath}
544 : : {
545 : 837 : static_assert(MIN_BUCKET_FEERATE > 0, "Min feerate must be nonzero");
546 : 837 : size_t bucketIndex = 0;
547 : :
548 [ + + ]: 159030 : for (double bucketBoundary = MIN_BUCKET_FEERATE; bucketBoundary <= MAX_BUCKET_FEERATE; bucketBoundary *= FEE_SPACING, bucketIndex++) {
549 [ + - ]: 158193 : buckets.push_back(bucketBoundary);
550 [ + - ]: 158193 : bucketMap[bucketBoundary] = bucketIndex;
551 : : }
552 [ + - ]: 837 : buckets.push_back(INF_FEERATE);
553 [ + - ]: 837 : bucketMap[INF_FEERATE] = bucketIndex;
554 [ - + ]: 837 : assert(bucketMap.size() == buckets.size());
555 : :
556 [ + - + - ]: 837 : feeStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
557 [ + - + - ]: 837 : shortStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
558 [ + - + - ]: 837 : longStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
559 : :
560 [ + - + - ]: 837 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "rb")};
561 : :
562 [ + - ]: 837 : if (est_file.IsNull()) {
563 [ + - + - ]: 1674 : LogPrintf("%s is not found. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
564 : 837 : return;
565 : : }
566 : :
567 [ # # ]: 0 : std::chrono::hours file_age = GetFeeEstimatorFileAge();
568 [ # # # # ]: 0 : if (file_age > MAX_FILE_AGE && !read_stale_estimates) {
569 [ # # # # ]: 0 : LogPrintf("Fee estimation file %s too old (age=%lld > %lld hours) and will not be used to avoid serving stale estimates.\n", fs::PathToString(m_estimation_filepath), Ticks<std::chrono::hours>(file_age), Ticks<std::chrono::hours>(MAX_FILE_AGE));
570 : 0 : return;
571 : : }
572 : :
573 [ # # # # ]: 0 : if (!Read(est_file)) {
574 [ # # # # ]: 0 : LogPrintf("Failed to read fee estimates from %s. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
575 : : }
576 : 837 : }
577 : :
578 : 837 : CBlockPolicyEstimator::~CBlockPolicyEstimator() = default;
579 : :
580 : 0 : void CBlockPolicyEstimator::TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /*unused*/)
581 : : {
582 : 0 : processTransaction(tx);
583 : 0 : }
584 : :
585 : 0 : void CBlockPolicyEstimator::TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason /*unused*/, uint64_t /*unused*/)
586 : : {
587 : 0 : removeTx(tx->GetHash());
588 : 0 : }
589 : :
590 : 0 : void CBlockPolicyEstimator::MempoolTransactionsRemovedForBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block, unsigned int nBlockHeight)
591 : : {
592 : 0 : processBlock(txs_removed_for_block, nBlockHeight);
593 : 0 : }
594 : :
595 : 803 : void CBlockPolicyEstimator::processTransaction(const NewMempoolTransactionInfo& tx)
596 : : {
597 : 803 : LOCK(m_cs_fee_estimator);
598 : 803 : const unsigned int txHeight = tx.info.txHeight;
599 : 803 : const auto& hash = tx.info.m_tx->GetHash();
600 [ + + ]: 803 : if (mapMemPoolTxs.count(hash)) {
601 [ + - - + : 78 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error mempool tx %s already being tracked\n",
- - - - ]
602 : : hash.ToString());
603 : 78 : return;
604 : : }
605 : :
606 [ + + ]: 725 : if (txHeight != nBestSeenHeight) {
607 : : // Ignore side chains and re-orgs; assuming they are random they don't
608 : : // affect the estimate. We'll potentially double count transactions in 1-block reorgs.
609 : : // Ignore txs if BlockPolicyEstimator is not in sync with ActiveChain().Tip().
610 : : // It will be synced next time a block is processed.
611 : : return;
612 : : }
613 : : // This transaction should only count for fee estimation if:
614 : : // - it's not being re-added during a reorg which bypasses typical mempool fee limits
615 : : // - the node is not behind
616 : : // - the transaction is not dependent on any other transactions in the mempool
617 : : // - it's not part of a package.
618 [ + - + + : 341 : const bool validForFeeEstimation = !tx.m_mempool_limit_bypassed && !tx.m_submitted_in_package && tx.m_chainstate_is_current && tx.m_has_no_mempool_parents;
+ - + + ]
619 : :
620 : : // Only want to be updating estimates when our blockchain is synced,
621 : : // otherwise we'll miscalculate how many blocks its taking to get included.
622 : 341 : if (!validForFeeEstimation) {
623 : 39 : untrackedTxs++;
624 : 39 : return;
625 : : }
626 : 302 : trackedTxs++;
627 : :
628 : : // Feerates are stored and reported as BTC-per-kb:
629 [ + - ]: 302 : const CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
630 : :
631 [ + - ]: 302 : mapMemPoolTxs[hash].blockHeight = txHeight;
632 [ + - ]: 302 : unsigned int bucketIndex = feeStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
633 [ + - ]: 302 : mapMemPoolTxs[hash].bucketIndex = bucketIndex;
634 [ + - ]: 302 : unsigned int bucketIndex2 = shortStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
635 [ - + ]: 302 : assert(bucketIndex == bucketIndex2);
636 [ + - ]: 302 : unsigned int bucketIndex3 = longStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
637 [ - + ]: 302 : assert(bucketIndex == bucketIndex3);
638 : 803 : }
639 : :
640 : 12451 : bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const RemovedMempoolTransactionInfo& tx)
641 : : {
642 : 12451 : AssertLockHeld(m_cs_fee_estimator);
643 [ + + ]: 12451 : if (!_removeTx(tx.info.m_tx->GetHash(), true)) {
644 : : // This transaction wasn't being tracked for fee estimation
645 : : return false;
646 : : }
647 : :
648 : : // How many blocks did it take for miners to include this transaction?
649 : : // blocksToConfirm is 1-based, so a transaction included in the earliest
650 : : // possible block has confirmation count of 1
651 : 71 : int blocksToConfirm = nBlockHeight - tx.info.txHeight;
652 [ + + ]: 71 : if (blocksToConfirm <= 0) {
653 : : // This can't happen because we don't process transactions from a block with a height
654 : : // lower than our greatest seen height
655 [ - + ]: 7 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error Transaction had negative blocksToConfirm\n");
656 : 7 : return false;
657 : : }
658 : :
659 : : // Feerates are stored and reported as BTC-per-kb:
660 : 64 : CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
661 : :
662 : 64 : feeStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
663 : 64 : shortStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
664 : 64 : longStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
665 : 64 : return true;
666 : : }
667 : :
668 : 1036 : void CBlockPolicyEstimator::processBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block,
669 : : unsigned int nBlockHeight)
670 : : {
671 : 1036 : LOCK(m_cs_fee_estimator);
672 [ + + ]: 1036 : if (nBlockHeight <= nBestSeenHeight) {
673 : : // Ignore side chains and re-orgs; assuming they are random
674 : : // they don't affect the estimate.
675 : : // And if an attacker can re-org the chain at will, then
676 : : // you've got much bigger problems than "attacker can influence
677 : : // transaction fees."
678 [ + - ]: 176 : return;
679 : : }
680 : :
681 : : // Must update nBestSeenHeight in sync with ClearCurrent so that
682 : : // calls to removeTx (via processBlockTx) correctly calculate age
683 : : // of unconfirmed txs to remove from tracking.
684 : 860 : nBestSeenHeight = nBlockHeight;
685 : :
686 : : // Update unconfirmed circular buffer
687 [ + - ]: 860 : feeStats->ClearCurrent(nBlockHeight);
688 [ + - ]: 860 : shortStats->ClearCurrent(nBlockHeight);
689 [ + - ]: 860 : longStats->ClearCurrent(nBlockHeight);
690 : :
691 : : // Decay all exponential averages
692 [ + - ]: 860 : feeStats->UpdateMovingAverages();
693 [ + - ]: 860 : shortStats->UpdateMovingAverages();
694 [ + - ]: 860 : longStats->UpdateMovingAverages();
695 : :
696 : 860 : unsigned int countedTxs = 0;
697 : : // Update averages with data points from current block
698 [ + + ]: 13311 : for (const auto& tx : txs_removed_for_block) {
699 [ + - + + ]: 12451 : if (processBlockTx(nBlockHeight, tx))
700 : 64 : countedTxs++;
701 : : }
702 : :
703 [ + + + + ]: 860 : if (firstRecordedHeight == 0 && countedTxs > 0) {
704 : 39 : firstRecordedHeight = nBestSeenHeight;
705 [ + - - + : 39 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy first recorded height %u\n", firstRecordedHeight);
- - ]
706 : : }
707 : :
708 : :
709 [ + - - + : 860 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy estimates updated by %u of %u block txs, since last block %u of %u tracked, mempool map size %u, max target %u from %s\n",
- - - - -
- - - -
- ]
710 : : countedTxs, txs_removed_for_block.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size(),
711 : : MaxUsableEstimate(), HistoricalBlockSpan() > BlockSpan() ? "historical" : "current");
712 : :
713 : 860 : trackedTxs = 0;
714 [ + - ]: 860 : untrackedTxs = 0;
715 : 1036 : }
716 : :
717 : 20740 : CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) const
718 : : {
719 : : // It's not possible to get reasonable estimates for confTarget of 1
720 [ + + ]: 20740 : if (confTarget <= 1)
721 : 13478 : return CFeeRate(0);
722 : :
723 : 7262 : return estimateRawFee(confTarget, DOUBLE_SUCCESS_PCT, FeeEstimateHorizon::MED_HALFLIFE);
724 : : }
725 : :
726 : 28002 : CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult* result) const
727 : : {
728 : 28002 : TxConfirmStats* stats = nullptr;
729 : 28002 : double sufficientTxs = SUFFICIENT_FEETXS;
730 [ + + + - ]: 28002 : switch (horizon) {
731 : 7837 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
732 : 7837 : stats = shortStats.get();
733 : 7837 : sufficientTxs = SUFFICIENT_TXS_SHORT;
734 : 7837 : break;
735 : : }
736 : 19559 : case FeeEstimateHorizon::MED_HALFLIFE: {
737 : 19559 : stats = feeStats.get();
738 : 19559 : break;
739 : : }
740 : 606 : case FeeEstimateHorizon::LONG_HALFLIFE: {
741 : 606 : stats = longStats.get();
742 : 606 : break;
743 : : }
744 : : } // no default case, so the compiler can warn about missing cases
745 [ - + ]: 28002 : assert(stats);
746 : :
747 : 28002 : LOCK(m_cs_fee_estimator);
748 : : // Return failure if trying to analyze a target we're not tracking
749 [ + + + + ]: 28002 : if (confTarget <= 0 || (unsigned int)confTarget > stats->GetMaxConfirms())
750 : 27782 : return CFeeRate(0);
751 [ + + ]: 220 : if (successThreshold > 1)
752 : 21 : return CFeeRate(0);
753 : :
754 [ + - ]: 199 : double median = stats->EstimateMedianVal(confTarget, sufficientTxs, successThreshold, nBestSeenHeight, result);
755 : :
756 [ + - ]: 199 : if (median < 0)
757 : 199 : return CFeeRate(0);
758 : :
759 : 0 : return CFeeRate(llround(median));
760 : 28002 : }
761 : :
762 : 20740 : unsigned int CBlockPolicyEstimator::HighestTargetTracked(FeeEstimateHorizon horizon) const
763 : : {
764 : 20740 : LOCK(m_cs_fee_estimator);
765 [ + + + - ]: 20740 : switch (horizon) {
766 : 7759 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
767 : 7759 : return shortStats->GetMaxConfirms();
768 : : }
769 : 12270 : case FeeEstimateHorizon::MED_HALFLIFE: {
770 : 12270 : return feeStats->GetMaxConfirms();
771 : : }
772 : 711 : case FeeEstimateHorizon::LONG_HALFLIFE: {
773 : 711 : return longStats->GetMaxConfirms();
774 : : }
775 : : } // no default case, so the compiler can warn about missing cases
776 : 0 : assert(false);
777 : 20740 : }
778 : :
779 : 416 : unsigned int CBlockPolicyEstimator::BlockSpan() const
780 : : {
781 [ + + ]: 416 : if (firstRecordedHeight == 0) return 0;
782 [ - + ]: 76 : assert(nBestSeenHeight >= firstRecordedHeight);
783 : :
784 : 76 : return nBestSeenHeight - firstRecordedHeight;
785 : : }
786 : :
787 : 416 : unsigned int CBlockPolicyEstimator::HistoricalBlockSpan() const
788 : : {
789 [ + + ]: 416 : if (historicalFirst == 0) return 0;
790 [ - + ]: 38 : assert(historicalBest >= historicalFirst);
791 : :
792 [ + + ]: 38 : if (nBestSeenHeight - historicalBest > OLDEST_ESTIMATE_HISTORY) return 0;
793 : :
794 : 3 : return historicalBest - historicalFirst;
795 : : }
796 : :
797 : 167 : unsigned int CBlockPolicyEstimator::MaxUsableEstimate() const
798 : : {
799 : : // Block spans are divided by 2 to make sure there are enough potential failing data points for the estimate
800 [ + - + + ]: 334 : return std::min(longStats->GetMaxConfirms(), std::max(BlockSpan(), HistoricalBlockSpan()) / 2);
801 : : }
802 : :
803 : : /** Return a fee estimate at the required successThreshold from the shortest
804 : : * time horizon which tracks confirmations up to the desired target. If
805 : : * checkShorterHorizon is requested, also allow short time horizon estimates
806 : : * for a lower target to reduce the given answer */
807 : 192 : double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const
808 : : {
809 : 192 : double estimate = -1;
810 [ + - + + ]: 192 : if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
811 : : // Find estimate from shortest time horizon possible
812 [ + + ]: 191 : if (confTarget <= shortStats->GetMaxConfirms()) { // short horizon
813 : 158 : estimate = shortStats->EstimateMedianVal(confTarget, SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, result);
814 : : }
815 [ + + ]: 33 : else if (confTarget <= feeStats->GetMaxConfirms()) { // medium horizon
816 : 16 : estimate = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
817 : : }
818 : : else { // long horizon
819 : 17 : estimate = longStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
820 : : }
821 [ + + ]: 191 : if (checkShorterHorizon) {
822 : 146 : EstimationResult tempResult;
823 : : // If a lower confTarget from a more recent horizon returns a lower answer use it.
824 [ + + ]: 146 : if (confTarget > feeStats->GetMaxConfirms()) {
825 : 12 : double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, &tempResult);
826 [ - + - - : 12 : if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
- - ]
827 : 0 : estimate = medMax;
828 [ # # ]: 0 : if (result) *result = tempResult;
829 : : }
830 : : }
831 [ + + ]: 146 : if (confTarget > shortStats->GetMaxConfirms()) {
832 : 22 : double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(), SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, &tempResult);
833 [ - + - - : 22 : if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
- - ]
834 : 0 : estimate = shortMax;
835 [ # # ]: 0 : if (result) *result = tempResult;
836 : : }
837 : : }
838 : : }
839 : : }
840 : 192 : return estimate;
841 : : }
842 : :
843 : : /** Ensure that for a conservative estimate, the DOUBLE_SUCCESS_PCT is also met
844 : : * at 2 * target for any longer time horizons.
845 : : */
846 : 64 : double CBlockPolicyEstimator::estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const
847 : : {
848 : 64 : double estimate = -1;
849 : 64 : EstimationResult tempResult;
850 [ + + ]: 64 : if (doubleTarget <= shortStats->GetMaxConfirms()) {
851 : 50 : estimate = feeStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, result);
852 : : }
853 [ + + ]: 64 : if (doubleTarget <= feeStats->GetMaxConfirms()) {
854 : 56 : double longEstimate = longStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, &tempResult);
855 [ - + ]: 56 : if (longEstimate > estimate) {
856 : 0 : estimate = longEstimate;
857 [ # # ]: 0 : if (result) *result = tempResult;
858 : : }
859 : : }
860 : 64 : return estimate;
861 : : }
862 : :
863 : : /** estimateSmartFee returns the max of the feerates calculated with a 60%
864 : : * threshold required at target / 2, an 85% threshold required at target and a
865 : : * 95% threshold required at 2 * target. Each calculation is performed at the
866 : : * shortest time horizon which tracks the required target. Conservative
867 : : * estimates, however, required the 95% threshold at 2 * target be met for any
868 : : * longer time horizons also.
869 : : */
870 : 20740 : CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
871 : : {
872 : 20740 : LOCK(m_cs_fee_estimator);
873 : :
874 [ + + ]: 20740 : if (feeCalc) {
875 : 19509 : feeCalc->desiredTarget = confTarget;
876 : 19509 : feeCalc->returnedTarget = confTarget;
877 : : }
878 : :
879 : 20740 : double median = -1;
880 : 20740 : EstimationResult tempResult;
881 : :
882 : : // Return failure if trying to analyze a target we're not tracking
883 [ + + + + ]: 20740 : if (confTarget <= 0 || (unsigned int)confTarget > longStats->GetMaxConfirms()) {
884 : 20573 : return CFeeRate(0); // error condition
885 : : }
886 : :
887 : : // It's not possible to get reasonable estimates for confTarget of 1
888 [ + + ]: 167 : if (confTarget == 1) confTarget = 2;
889 : :
890 [ + - ]: 167 : unsigned int maxUsableEstimate = MaxUsableEstimate();
891 [ + + ]: 167 : if ((unsigned int)confTarget > maxUsableEstimate) {
892 : 104 : confTarget = maxUsableEstimate;
893 : : }
894 [ + + ]: 167 : if (feeCalc) feeCalc->returnedTarget = confTarget;
895 : :
896 [ + + ]: 167 : if (confTarget <= 1) return CFeeRate(0); // error condition
897 : :
898 : 64 : assert(confTarget > 0); //estimateCombinedFee and estimateConservativeFee take unsigned ints
899 : : /** true is passed to estimateCombined fee for target/2 and target so
900 : : * that we check the max confirms for shorter time horizons as well.
901 : : * This is necessary to preserve monotonically increasing estimates.
902 : : * For non-conservative estimates we do the same thing for 2*target, but
903 : : * for conservative estimates we want to skip these shorter horizons
904 : : * checks for 2*target because we are taking the max over all time
905 : : * horizons so we already have monotonically increasing estimates and
906 : : * the purpose of conservative estimates is not to let short term
907 : : * fluctuations lower our estimates by too much.
908 : : *
909 : : * Note: In certain rare edge cases, monotonically increasing estimates may
910 : : * not be guaranteed. Specifically, given two targets N and M, where M > N,
911 : : * if a sub-estimate for target N fails to return a valid fee rate, while
912 : : * target M has valid fee rate for that sub-estimate, target M may result
913 : : * in a higher fee rate estimate than target N.
914 : : *
915 : : * See: https://github.com/bitcoin/bitcoin/issues/11800#issuecomment-349697807
916 : : */
917 [ + - ]: 64 : double halfEst = estimateCombinedFee(confTarget/2, HALF_SUCCESS_PCT, true, &tempResult);
918 [ + + ]: 64 : if (feeCalc) {
919 : 57 : feeCalc->est = tempResult;
920 : 57 : feeCalc->reason = FeeReason::HALF_ESTIMATE;
921 : : }
922 : 64 : median = halfEst;
923 [ + - ]: 64 : double actualEst = estimateCombinedFee(confTarget, SUCCESS_PCT, true, &tempResult);
924 [ - + ]: 64 : if (actualEst > median) {
925 : 0 : median = actualEst;
926 [ # # ]: 0 : if (feeCalc) {
927 : 0 : feeCalc->est = tempResult;
928 : 0 : feeCalc->reason = FeeReason::FULL_ESTIMATE;
929 : : }
930 : : }
931 [ + - ]: 64 : double doubleEst = estimateCombinedFee(2 * confTarget, DOUBLE_SUCCESS_PCT, !conservative, &tempResult);
932 [ - + ]: 64 : if (doubleEst > median) {
933 : 0 : median = doubleEst;
934 [ # # ]: 0 : if (feeCalc) {
935 : 0 : feeCalc->est = tempResult;
936 : 0 : feeCalc->reason = FeeReason::DOUBLE_ESTIMATE;
937 : : }
938 : : }
939 : :
940 [ + - ]: 64 : if (conservative || median == -1) {
941 [ + - ]: 64 : double consEst = estimateConservativeFee(2 * confTarget, &tempResult);
942 [ - + ]: 64 : if (consEst > median) {
943 : 0 : median = consEst;
944 [ # # ]: 0 : if (feeCalc) {
945 : 0 : feeCalc->est = tempResult;
946 : 0 : feeCalc->reason = FeeReason::CONSERVATIVE;
947 : : }
948 : : }
949 : : }
950 : :
951 [ + - ]: 64 : if (median < 0) return CFeeRate(0); // error condition
952 : :
953 : 0 : return CFeeRate(llround(median));
954 : 20740 : }
955 : :
956 : 0 : void CBlockPolicyEstimator::Flush() {
957 : 0 : FlushUnconfirmed();
958 : 0 : FlushFeeEstimates();
959 : 0 : }
960 : :
961 : 0 : void CBlockPolicyEstimator::FlushFeeEstimates()
962 : : {
963 [ # # ]: 0 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "wb")};
964 [ # # # # : 0 : if (est_file.IsNull() || !Write(est_file)) {
# # ]
965 [ # # # # ]: 0 : LogPrintf("Failed to write fee estimates to %s. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
966 : : } else {
967 [ # # # # ]: 0 : LogPrintf("Flushed fee estimates to %s.\n", fs::PathToString(m_estimation_filepath.filename()));
968 : : }
969 : 0 : }
970 : :
971 : 889 : bool CBlockPolicyEstimator::Write(AutoFile& fileout) const
972 : : {
973 : 889 : try {
974 [ + - ]: 889 : LOCK(m_cs_fee_estimator);
975 [ + + ]: 889 : fileout << CURRENT_FEES_FILE_VERSION;
976 [ + - ]: 249 : fileout << int{0}; // Unused dummy field. Written files may contain any value in [0, 289900]
977 [ + - ]: 249 : fileout << nBestSeenHeight;
978 [ + - + - : 249 : if (BlockSpan() > HistoricalBlockSpan()/2) {
+ + ]
979 [ + - + - ]: 7 : fileout << firstRecordedHeight << nBestSeenHeight;
980 : : }
981 : : else {
982 [ + - + - ]: 242 : fileout << historicalFirst << historicalBest;
983 : : }
984 [ + - ]: 249 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(buckets);
985 [ + + ]: 249 : feeStats->Write(fileout);
986 [ + + ]: 53 : shortStats->Write(fileout);
987 [ + + ]: 49 : longStats->Write(fileout);
988 : 843 : }
989 [ - + ]: 843 : catch (const std::exception&) {
990 [ + - ]: 843 : LogWarning("Unable to write policy estimator data (non-fatal)");
991 : 843 : return false;
992 : 843 : }
993 : 46 : return true;
994 : : }
995 : :
996 : 1047 : bool CBlockPolicyEstimator::Read(AutoFile& filein)
997 : : {
998 : 1047 : try {
999 [ + - ]: 1047 : LOCK(m_cs_fee_estimator);
1000 : 1047 : int nVersionRequired, dummy;
1001 [ + + + + ]: 1047 : filein >> nVersionRequired >> dummy;
1002 [ + + ]: 438 : if (nVersionRequired > CURRENT_FEES_FILE_VERSION) {
1003 [ + - + - ]: 160 : throw std::runtime_error{strprintf("File version (%d) too high to be read.", nVersionRequired)};
1004 : : }
1005 : :
1006 : : // Read fee estimates file into temporary variables so existing data
1007 : : // structures aren't corrupted if there is an exception.
1008 : 358 : unsigned int nFileBestSeenHeight;
1009 [ + + ]: 358 : filein >> nFileBestSeenHeight;
1010 : :
1011 [ + + ]: 356 : if (nVersionRequired < CURRENT_FEES_FILE_VERSION) {
1012 [ + - ]: 49 : LogWarning("Incompatible old fee estimation data (non-fatal). Version: %d", nVersionRequired);
1013 : : } else { // nVersionRequired == CURRENT_FEES_FILE_VERSION
1014 : 307 : unsigned int nFileHistoricalFirst, nFileHistoricalBest;
1015 [ + + + + ]: 307 : filein >> nFileHistoricalFirst >> nFileHistoricalBest;
1016 [ + + + + ]: 304 : if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
1017 [ + - ]: 6 : throw std::runtime_error("Corrupt estimates file. Historical block range for estimates is invalid");
1018 : : }
1019 : 298 : std::vector<double> fileBuckets;
1020 [ + + ]: 298 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(fileBuckets);
1021 [ + + ]: 279 : size_t numBuckets = fileBuckets.size();
1022 [ + + ]: 279 : if (numBuckets <= 1 || numBuckets > 1000) {
1023 [ + - ]: 6 : throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
1024 : : }
1025 : :
1026 [ + - + - : 273 : std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
+ - ]
1027 [ + - + - : 273 : std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
+ - ]
1028 [ + - + - : 273 : std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
+ + ]
1029 [ + + ]: 273 : fileFeeStats->Read(filein, numBuckets);
1030 [ + + ]: 145 : fileShortStats->Read(filein, numBuckets);
1031 [ + + ]: 70 : fileLongStats->Read(filein, numBuckets);
1032 : :
1033 : : // Fee estimates file parsed correctly
1034 : : // Copy buckets from file and refresh our bucketmap
1035 [ + - ]: 49 : buckets = fileBuckets;
1036 : 49 : bucketMap.clear();
1037 [ + + ]: 204 : for (unsigned int i = 0; i < buckets.size(); i++) {
1038 [ + - ]: 155 : bucketMap[buckets[i]] = i;
1039 : : }
1040 : :
1041 : : // Destroy old TxConfirmStats and point to new ones that already reference buckets and bucketMap
1042 : 49 : feeStats = std::move(fileFeeStats);
1043 : 49 : shortStats = std::move(fileShortStats);
1044 : 49 : longStats = std::move(fileLongStats);
1045 : :
1046 : 49 : nBestSeenHeight = nFileBestSeenHeight;
1047 : 49 : historicalFirst = nFileHistoricalFirst;
1048 : 49 : historicalBest = nFileHistoricalBest;
1049 : 970 : }
1050 : 949 : }
1051 [ - + ]: 949 : catch (const std::exception& e) {
1052 [ + - ]: 949 : LogWarning("Unable to read policy estimator data (non-fatal): %s", e.what());
1053 : 949 : return false;
1054 : 949 : }
1055 : 98 : return true;
1056 : : }
1057 : :
1058 : 18663 : void CBlockPolicyEstimator::FlushUnconfirmed()
1059 : : {
1060 : 18663 : const auto startclear{SteadyClock::now()};
1061 : 18663 : LOCK(m_cs_fee_estimator);
1062 : 18663 : size_t num_entries = mapMemPoolTxs.size();
1063 : : // Remove every entry in mapMemPoolTxs
1064 [ + + ]: 18787 : while (!mapMemPoolTxs.empty()) {
1065 [ + - ]: 124 : auto mi = mapMemPoolTxs.begin();
1066 [ + - ]: 124 : _removeTx(mi->first, false); // this calls erase() on mapMemPoolTxs
1067 : : }
1068 : 18663 : const auto endclear{SteadyClock::now()};
1069 [ + - - + : 18663 : LogDebug(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %.3fs\n", num_entries, Ticks<SecondsDouble>(endclear - startclear));
- - + - ]
1070 : 18663 : }
1071 : :
1072 : 0 : std::chrono::hours CBlockPolicyEstimator::GetFeeEstimatorFileAge()
1073 : : {
1074 : 0 : auto file_time{fs::last_write_time(m_estimation_filepath)};
1075 : 0 : auto now{fs::file_time_type::clock::now()};
1076 : 0 : return std::chrono::duration_cast<std::chrono::hours>(now - file_time);
1077 : : }
1078 : :
1079 : 1102 : static std::set<double> MakeFeeSet(const CFeeRate& min_incremental_fee,
1080 : : double max_filter_fee_rate,
1081 : : double fee_filter_spacing)
1082 : : {
1083 [ + + ]: 1102 : std::set<double> fee_set;
1084 : :
1085 [ + + ]: 1102 : const CAmount min_fee_limit{std::max(CAmount(1), min_incremental_fee.GetFeePerK() / 2)};
1086 [ + - ]: 1102 : fee_set.insert(0);
1087 : 1102 : for (double bucket_boundary = min_fee_limit;
1088 [ + + ]: 111520 : bucket_boundary <= max_filter_fee_rate;
1089 : 110418 : bucket_boundary *= fee_filter_spacing) {
1090 : :
1091 [ + - ]: 110418 : fee_set.insert(bucket_boundary);
1092 : : }
1093 : :
1094 : 1102 : return fee_set;
1095 : 0 : }
1096 : :
1097 : 1102 : FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee, FastRandomContext& rng)
1098 : 1102 : : m_fee_set{MakeFeeSet(minIncrementalFee, MAX_FILTER_FEERATE, FEE_FILTER_SPACING)},
1099 : 1102 : insecure_rand{rng}
1100 : : {
1101 : 1102 : }
1102 : :
1103 : 245672 : CAmount FeeFilterRounder::round(CAmount currentMinFee)
1104 : : {
1105 : 245672 : AssertLockNotHeld(m_insecure_rand_mutex);
1106 : 245672 : std::set<double>::iterator it = m_fee_set.lower_bound(currentMinFee);
1107 [ + + + + ]: 245672 : if (it == m_fee_set.end() ||
1108 [ + + ]: 221547 : (it != m_fee_set.begin() &&
1109 [ + + + - ]: 429582 : WITH_LOCK(m_insecure_rand_mutex, return insecure_rand.rand32()) % 3 != 0)) {
1110 : 169259 : --it;
1111 : : }
1112 : 245672 : return static_cast<CAmount>(*it);
1113 : : }
|
