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