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 : 52 : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
41 : : {
42 [ + + + - ]: 52 : switch (horizon) {
43 : 21 : case FeeEstimateHorizon::SHORT_HALFLIFE: return "short";
44 : 12 : 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 : 439656 : template<typename Stream> void Ser(Stream &s, double v)
55 : : {
56 : 439656 : s << EncodeDouble(v);
57 : : }
58 : :
59 : 250992 : template<typename Stream> void Unser(Stream& s, double& v)
60 : : {
61 : : uint64_t encoded;
62 : 250909 : s >> encoded;
63 : 250909 : v = DecodeDouble(encoded);
64 : 250909 : }
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 [ + + + + : 105871 : 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 : 2925 : TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
179 : : const std::map<double, unsigned int>& defaultBucketMap,
180 : 2925 : unsigned int maxPeriods, double _decay, unsigned int _scale)
181 [ - + ]: 2925 : : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_scale)
182 : : {
183 [ - + ]: 2925 : assert(_scale != 0 && "_scale must be non-zero");
184 [ + - ]: 2925 : confAvg.resize(maxPeriods);
185 [ + - ]: 2925 : failAvg.resize(maxPeriods);
186 [ + + ]: 78975 : for (unsigned int i = 0; i < maxPeriods; i++) {
187 [ + - ]: 76050 : confAvg[i].resize(buckets.size());
188 [ + - ]: 76050 : failAvg[i].resize(buckets.size());
189 : : }
190 : :
191 [ + - ]: 2925 : txCtAvg.resize(buckets.size());
192 [ + - ]: 2925 : m_feerate_avg.resize(buckets.size());
193 : :
194 [ + - ]: 2925 : resizeInMemoryCounters(buckets.size());
195 : 2925 : }
196 : :
197 : 3083 : 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 : 3083 : unconfTxs.resize(GetMaxConfirms());
200 [ + + ]: 1068305 : for (unsigned int i = 0; i < unconfTxs.size(); i++) {
201 : 1065222 : unconfTxs[i].resize(newbuckets);
202 : : }
203 : 3083 : oldUnconfTxs.resize(newbuckets);
204 : 3083 : }
205 : :
206 : : // Roll the unconfirmed txs circular buffer
207 : 1842 : void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
208 : : {
209 [ + + ]: 351822 : for (unsigned int j = 0; j < buckets.size(); j++) {
210 : 349980 : oldUnconfTxs[j] += unconfTxs[nBlockHeight % unconfTxs.size()][j];
211 : 349980 : unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
212 : : }
213 : 1842 : }
214 : :
215 : :
216 : 3558 : void TxConfirmStats::Record(int blocksToConfirm, double feerate)
217 : : {
218 : : // blocksToConfirm is 1-based
219 [ + - ]: 3558 : if (blocksToConfirm < 1)
220 : : return;
221 : 3558 : int periodsToConfirm = (blocksToConfirm + scale - 1) / scale;
222 : 3558 : unsigned int bucketindex = bucketMap.lower_bound(feerate)->second;
223 [ + + ]: 23095 : for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
224 : 19537 : confAvg[i - 1][bucketindex]++;
225 : : }
226 : 3558 : txCtAvg[bucketindex]++;
227 : 3558 : m_feerate_avg[bucketindex] += feerate;
228 : : }
229 : :
230 : 1842 : void TxConfirmStats::UpdateMovingAverages()
231 : : {
232 [ + - ]: 1842 : assert(confAvg.size() == failAvg.size());
233 [ + + ]: 351822 : for (unsigned int j = 0; j < buckets.size(); j++) {
234 [ + + ]: 9449460 : for (unsigned int i = 0; i < confAvg.size(); i++) {
235 : 9099480 : confAvg[i][j] *= decay;
236 : 9099480 : failAvg[i][j] *= decay;
237 : : }
238 : 349980 : m_feerate_avg[j] *= decay;
239 : 349980 : txCtAvg[j] *= decay;
240 : : }
241 : 1842 : }
242 : :
243 : : // returns -1 on error conditions
244 : 11537 : 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 : 11537 : double nConf = 0; // Number of tx's confirmed within the confTarget
250 : 11537 : double totalNum = 0; // Total number of tx's that were ever confirmed
251 : 11537 : int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
252 : 11537 : double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
253 : 11537 : const int periodTarget = (confTarget + scale - 1) / scale;
254 : 11537 : 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 : 11537 : unsigned int curNearBucket = maxbucketindex;
262 : 11537 : unsigned int bestNearBucket = maxbucketindex;
263 : 11537 : unsigned int curFarBucket = maxbucketindex;
264 : 11537 : 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 : 11537 : double partialNum = 0;
270 : :
271 : 11537 : bool foundAnswer = false;
272 : 11537 : unsigned int bins = unconfTxs.size();
273 : 11537 : bool newBucketRange = true;
274 : 11537 : bool passing = true;
275 : 11537 : EstimatorBucket passBucket;
276 : 11537 : EstimatorBucket failBucket;
277 : :
278 : : // Start counting from highest feerate transactions
279 [ + + ]: 2203567 : for (int bucket = maxbucketindex; bucket >= 0; --bucket) {
280 [ + + ]: 2192030 : if (newBucketRange) {
281 : 11807 : curNearBucket = bucket;
282 : 11807 : newBucketRange = false;
283 : : }
284 : 2192030 : curFarBucket = bucket;
285 : 2192030 : nConf += confAvg[periodTarget - 1][bucket];
286 : 2192030 : partialNum += txCtAvg[bucket];
287 : 2192030 : totalNum += txCtAvg[bucket];
288 : 2192030 : failNum += failAvg[periodTarget - 1][bucket];
289 [ + + ]: 456773490 : for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
290 : 454581460 : extraNum += unconfTxs[(nBlockHeight - confct) % bins][bucket];
291 [ + + ]: 2192030 : 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 [ + + ]: 2192030 : if (partialNum < sufficientTxVal / (1 - decay)) {
298 : : // the buckets we've added in this round aren't sufficient
299 : : // so keep adding
300 : 2191134 : continue;
301 : : } else {
302 : 896 : partialNum = 0; // reset for the next range we'll add
303 : :
304 : 896 : double curPct = nConf / (totalNum + failNum + extraNum);
305 : :
306 : : // Check to see if we are no longer getting confirmed at the success rate
307 [ + + ]: 896 : if (curPct < successBreakPoint) {
308 [ + - ]: 528 : if (passing == true) {
309 : : // First time we hit a failure record the failed bucket
310 [ + + ]: 528 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
311 [ + - ]: 528 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
312 [ + + ]: 528 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
313 : 528 : failBucket.end = buckets[failMaxBucket];
314 : 528 : failBucket.withinTarget = nConf;
315 : 528 : failBucket.totalConfirmed = totalNum;
316 : 528 : failBucket.inMempool = extraNum;
317 : 528 : failBucket.leftMempool = failNum;
318 : 528 : passing = false;
319 : : }
320 : 528 : continue;
321 : 528 : }
322 : : // Otherwise update the cumulative stats, and the bucket variables
323 : : // and reset the counters
324 : : else {
325 : 368 : failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
326 : 368 : foundAnswer = true;
327 : 368 : passing = true;
328 : 368 : passBucket.withinTarget = nConf;
329 : 368 : nConf = 0;
330 : 368 : passBucket.totalConfirmed = totalNum;
331 : 368 : totalNum = 0;
332 : 368 : passBucket.inMempool = extraNum;
333 : 368 : passBucket.leftMempool = failNum;
334 : 368 : failNum = 0;
335 : 368 : extraNum = 0;
336 : 368 : bestNearBucket = curNearBucket;
337 : 368 : bestFarBucket = curFarBucket;
338 : 368 : newBucketRange = true;
339 : : }
340 : : }
341 : : }
342 : :
343 : 11537 : double median = -1;
344 : 11537 : 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 [ + + ]: 11537 : unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
351 [ + - ]: 11537 : unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
352 [ + + ]: 42188 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
353 : 30651 : txSum += txCtAvg[j];
354 : : }
355 [ + + ]: 11537 : if (foundAnswer && txSum != 0) {
356 : 368 : txSum = txSum / 2;
357 [ + - ]: 19482 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
358 [ + + ]: 19482 : if (txCtAvg[j] < txSum)
359 : 19114 : txSum -= txCtAvg[j];
360 : : else { // we're in the right bucket
361 : 368 : median = m_feerate_avg[j] / txCtAvg[j];
362 : 368 : break;
363 : : }
364 : : }
365 : :
366 [ + + ]: 368 : passBucket.start = minBucket ? buckets[minBucket-1] : 0;
367 : 368 : 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 [ + + ]: 11537 : if (passing && !newBucketRange) {
372 [ - + ]: 10911 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
373 [ + - ]: 10911 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
374 [ - + ]: 10911 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
375 : 10911 : failBucket.end = buckets[failMaxBucket];
376 : 10911 : failBucket.withinTarget = nConf;
377 : 10911 : failBucket.totalConfirmed = totalNum;
378 : 10911 : failBucket.inMempool = extraNum;
379 : 10911 : failBucket.leftMempool = failNum;
380 : : }
381 : :
382 : 11537 : float passed_within_target_perc = 0.0;
383 : 11537 : float failed_within_target_perc = 0.0;
384 [ + + ]: 11537 : if ((passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool)) {
385 : 368 : passed_within_target_perc = 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool);
386 : : }
387 [ + + ]: 11537 : if ((failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool)) {
388 : 10223 : failed_within_target_perc = 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool);
389 : : }
390 : :
391 [ - + ]: 11537 : 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 [ + + ]: 11537 : if (result) {
402 : 10597 : result->pass = passBucket;
403 : 10597 : result->fail = failBucket;
404 : 10597 : result->decay = decay;
405 : 10597 : result->scale = scale;
406 : : }
407 : 11537 : return median;
408 : : }
409 : :
410 : 266 : void TxConfirmStats::Write(AutoFile& fileout) const
411 : : {
412 : 266 : fileout << Using<EncodedDoubleFormatter>(decay);
413 : 266 : fileout << scale;
414 : 266 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
415 : 266 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
416 : 266 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
417 : 121 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
418 : 112 : }
419 : :
420 : 277 : 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 : 277 : size_t maxConfirms, maxPeriods;
426 : :
427 : : // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
428 : 277 : filein >> Using<EncodedDoubleFormatter>(decay);
429 [ + + + + ]: 257 : if (decay <= 0 || decay >= 1) {
430 [ + - ]: 7 : throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
431 : : }
432 : 250 : filein >> scale;
433 [ + + ]: 248 : if (scale == 0) {
434 [ + - ]: 3 : throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
435 : : }
436 : :
437 : 245 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
438 [ + + ]: 236 : if (m_feerate_avg.size() != numBuckets) {
439 [ + - ]: 6 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
440 : : }
441 : 230 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
442 [ + + ]: 229 : if (txCtAvg.size() != numBuckets) {
443 [ + - ]: 2 : throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
444 : : }
445 : 227 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
446 [ + + ]: 198 : maxPeriods = confAvg.size();
447 : 198 : maxConfirms = scale * maxPeriods;
448 : :
449 [ + + ]: 198 : if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
450 [ + - ]: 7 : throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
451 : : }
452 [ + + ]: 1127 : for (unsigned int i = 0; i < maxPeriods; i++) {
453 [ + + ]: 940 : if (confAvg[i].size() != numBuckets) {
454 [ + - ]: 4 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
455 : : }
456 : : }
457 : :
458 : 187 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
459 [ + + ]: 168 : if (maxPeriods != failAvg.size()) {
460 [ + - ]: 7 : throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
461 : : }
462 [ + + ]: 668 : for (unsigned int i = 0; i < maxPeriods; i++) {
463 [ + + ]: 510 : if (failAvg[i].size() != numBuckets) {
464 [ + - ]: 3 : 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 : 158 : resizeInMemoryCounters(numBuckets);
471 : :
472 [ - + ]: 158 : LogDebug(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
473 : : numBuckets, maxConfirms);
474 : 158 : }
475 : :
476 : 17841 : unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
477 : : {
478 : 17841 : unsigned int bucketindex = bucketMap.lower_bound(val)->second;
479 : 17841 : unsigned int blockIndex = nBlockHeight % unconfTxs.size();
480 : 17841 : unconfTxs[blockIndex][bucketindex]++;
481 : 17841 : return bucketindex;
482 : : }
483 : :
484 : 16506 : 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 : 16506 : int blocksAgo = nBestSeenHeight - entryHeight;
488 [ + + ]: 16506 : if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
489 : : blocksAgo = 0;
490 [ + + ]: 15906 : if (blocksAgo < 0) {
491 [ - + ]: 2187 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error, blocks ago is negative for mempool tx\n");
492 : 2187 : return; //This can't happen because we call this with our best seen height, no entries can have higher
493 : : }
494 : :
495 [ + + ]: 14319 : if (blocksAgo >= (int)unconfTxs.size()) {
496 [ + + ]: 3984 : if (oldUnconfTxs[bucketindex] > 0) {
497 : 226 : oldUnconfTxs[bucketindex]--;
498 : : } else {
499 [ - + ]: 3758 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
500 : : bucketindex);
501 : : }
502 : : }
503 : : else {
504 [ + - ]: 10335 : unsigned int blockIndex = entryHeight % unconfTxs.size();
505 [ + - ]: 10335 : if (unconfTxs[blockIndex][bucketindex] > 0) {
506 : 10335 : 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 [ + + + + ]: 14319 : if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
513 [ - + ]: 989 : assert(scale != 0);
514 : 989 : unsigned int periodsAgo = blocksAgo / scale;
515 [ + + + + ]: 23055 : for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
516 : 22066 : failAvg[i][bucketindex]++;
517 : : }
518 : : }
519 : : }
520 : :
521 : 6079 : bool CBlockPolicyEstimator::removeTx(uint256 hash)
522 : : {
523 : 6079 : LOCK(m_cs_fee_estimator);
524 [ + - + - ]: 6079 : return _removeTx(hash, /*inBlock=*/false);
525 : 6079 : }
526 : :
527 : 15243 : bool CBlockPolicyEstimator::_removeTx(const uint256& hash, bool inBlock)
528 : : {
529 : 15243 : AssertLockHeld(m_cs_fee_estimator);
530 : 15243 : std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
531 [ + + ]: 15243 : if (pos != mapMemPoolTxs.end()) {
532 : 5502 : feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
533 : 5502 : shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
534 : 5502 : longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
535 : 5502 : mapMemPoolTxs.erase(hash);
536 : 5502 : return true;
537 : : } else {
538 : : return false;
539 : : }
540 : : }
541 : :
542 : 826 : CBlockPolicyEstimator::CBlockPolicyEstimator(const fs::path& estimation_filepath, const bool read_stale_estimates)
543 : 826 : : m_estimation_filepath{estimation_filepath}
544 : : {
545 : 826 : static_assert(MIN_BUCKET_FEERATE > 0, "Min feerate must be nonzero");
546 : 826 : size_t bucketIndex = 0;
547 : :
548 [ + + ]: 156940 : for (double bucketBoundary = MIN_BUCKET_FEERATE; bucketBoundary <= MAX_BUCKET_FEERATE; bucketBoundary *= FEE_SPACING, bucketIndex++) {
549 [ + - ]: 156114 : buckets.push_back(bucketBoundary);
550 [ + - ]: 156114 : bucketMap[bucketBoundary] = bucketIndex;
551 : : }
552 [ + - ]: 826 : buckets.push_back(INF_FEERATE);
553 [ + - ]: 826 : bucketMap[INF_FEERATE] = bucketIndex;
554 [ - + ]: 826 : assert(bucketMap.size() == buckets.size());
555 : :
556 [ + - + - ]: 826 : feeStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
557 [ + - + - ]: 826 : shortStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
558 [ + - + - ]: 826 : longStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
559 : :
560 [ + - + - ]: 826 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "rb")};
561 : :
562 [ + - ]: 826 : if (est_file.IsNull()) {
563 [ + - + - ]: 1652 : LogPrintf("%s is not found. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
564 : 826 : 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 : 826 : }
577 : :
578 : 826 : 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 : 17288 : void CBlockPolicyEstimator::processTransaction(const NewMempoolTransactionInfo& tx)
596 : : {
597 : 17288 : LOCK(m_cs_fee_estimator);
598 : 17288 : const unsigned int txHeight = tx.info.txHeight;
599 : 17288 : const auto& hash = tx.info.m_tx->GetHash();
600 [ + + ]: 17288 : if (mapMemPoolTxs.count(hash)) {
601 [ + - - + : 4117 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error mempool tx %s already being tracked\n",
- - - - ]
602 : : hash.ToString());
603 : 4117 : return;
604 : : }
605 : :
606 [ + + ]: 13171 : 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 [ + - + + : 6422 : 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 : 6422 : if (!validForFeeEstimation) {
623 : 475 : untrackedTxs++;
624 : 475 : return;
625 : : }
626 : 5947 : trackedTxs++;
627 : :
628 : : // Feerates are stored and reported as BTC-per-kb:
629 [ + - ]: 5947 : const CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
630 : :
631 [ + - ]: 5947 : mapMemPoolTxs[hash].blockHeight = txHeight;
632 [ + - ]: 5947 : unsigned int bucketIndex = feeStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
633 [ + - ]: 5947 : mapMemPoolTxs[hash].bucketIndex = bucketIndex;
634 [ + - ]: 5947 : unsigned int bucketIndex2 = shortStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
635 [ - + ]: 5947 : assert(bucketIndex == bucketIndex2);
636 [ + - ]: 5947 : unsigned int bucketIndex3 = longStats->NewTx(txHeight, static_cast<double>(feeRate.GetFeePerK()));
637 [ - + ]: 5947 : assert(bucketIndex == bucketIndex3);
638 : 17288 : }
639 : :
640 : 6874 : bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const RemovedMempoolTransactionInfo& tx)
641 : : {
642 : 6874 : AssertLockHeld(m_cs_fee_estimator);
643 [ + + ]: 6874 : 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 : 1348 : int blocksToConfirm = nBlockHeight - tx.info.txHeight;
652 [ + + ]: 1348 : 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 [ - + ]: 162 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy error Transaction had negative blocksToConfirm\n");
656 : 162 : return false;
657 : : }
658 : :
659 : : // Feerates are stored and reported as BTC-per-kb:
660 : 1186 : CFeeRate feeRate(tx.info.m_fee, tx.info.m_virtual_transaction_size);
661 : :
662 : 1186 : feeStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
663 : 1186 : shortStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
664 : 1186 : longStats->Record(blocksToConfirm, static_cast<double>(feeRate.GetFeePerK()));
665 : 1186 : return true;
666 : : }
667 : :
668 : 5720 : void CBlockPolicyEstimator::processBlock(const std::vector<RemovedMempoolTransactionInfo>& txs_removed_for_block,
669 : : unsigned int nBlockHeight)
670 : : {
671 : 5720 : LOCK(m_cs_fee_estimator);
672 [ + + ]: 5720 : 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 [ + - ]: 5106 : 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 : 614 : nBestSeenHeight = nBlockHeight;
685 : :
686 : : // Update unconfirmed circular buffer
687 [ + - ]: 614 : feeStats->ClearCurrent(nBlockHeight);
688 [ + - ]: 614 : shortStats->ClearCurrent(nBlockHeight);
689 [ + - ]: 614 : longStats->ClearCurrent(nBlockHeight);
690 : :
691 : : // Decay all exponential averages
692 [ + - ]: 614 : feeStats->UpdateMovingAverages();
693 [ + - ]: 614 : shortStats->UpdateMovingAverages();
694 [ + - ]: 614 : longStats->UpdateMovingAverages();
695 : :
696 : 614 : unsigned int countedTxs = 0;
697 : : // Update averages with data points from current block
698 [ + + ]: 7488 : for (const auto& tx : txs_removed_for_block) {
699 [ + - + + ]: 6874 : if (processBlockTx(nBlockHeight, tx))
700 : 1186 : countedTxs++;
701 : : }
702 : :
703 [ + + + + ]: 614 : if (firstRecordedHeight == 0 && countedTxs > 0) {
704 : 160 : firstRecordedHeight = nBestSeenHeight;
705 [ + - - + : 160 : LogDebug(BCLog::ESTIMATEFEE, "Blockpolicy first recorded height %u\n", firstRecordedHeight);
- - ]
706 : : }
707 : :
708 : :
709 [ + - - + : 614 : 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 : 614 : trackedTxs = 0;
714 [ + - ]: 614 : untrackedTxs = 0;
715 : 5720 : }
716 : :
717 : 48972 : CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) const
718 : : {
719 : : // It's not possible to get reasonable estimates for confTarget of 1
720 [ + + ]: 48972 : if (confTarget <= 1)
721 : 35715 : return CFeeRate(0);
722 : :
723 : 13257 : return estimateRawFee(confTarget, DOUBLE_SUCCESS_PCT, FeeEstimateHorizon::MED_HALFLIFE);
724 : : }
725 : :
726 : 62229 : CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult* result) const
727 : : {
728 : 62229 : TxConfirmStats* stats = nullptr;
729 : 62229 : double sufficientTxs = SUFFICIENT_FEETXS;
730 [ + + + - ]: 62229 : switch (horizon) {
731 : 13297 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
732 : 13297 : stats = shortStats.get();
733 : 13297 : sufficientTxs = SUFFICIENT_TXS_SHORT;
734 : 13297 : break;
735 : : }
736 : 43334 : case FeeEstimateHorizon::MED_HALFLIFE: {
737 : 43334 : stats = feeStats.get();
738 : 43334 : break;
739 : : }
740 : 5598 : case FeeEstimateHorizon::LONG_HALFLIFE: {
741 : 5598 : stats = longStats.get();
742 : 5598 : break;
743 : : }
744 : : } // no default case, so the compiler can warn about missing cases
745 [ - + ]: 62229 : assert(stats);
746 : :
747 : 62229 : LOCK(m_cs_fee_estimator);
748 : : // Return failure if trying to analyze a target we're not tracking
749 [ + + + + ]: 62229 : if (confTarget <= 0 || (unsigned int)confTarget > stats->GetMaxConfirms())
750 : 60767 : return CFeeRate(0);
751 [ + + ]: 1462 : if (successThreshold > 1)
752 : 38 : return CFeeRate(0);
753 : :
754 [ + - ]: 1424 : double median = stats->EstimateMedianVal(confTarget, sufficientTxs, successThreshold, nBestSeenHeight, result);
755 : :
756 [ + + ]: 1424 : if (median < 0)
757 : 1190 : return CFeeRate(0);
758 : :
759 : 234 : return CFeeRate(llround(median));
760 : 62229 : }
761 : :
762 : 48972 : unsigned int CBlockPolicyEstimator::HighestTargetTracked(FeeEstimateHorizon horizon) const
763 : : {
764 : 48972 : LOCK(m_cs_fee_estimator);
765 [ + + + - ]: 48972 : switch (horizon) {
766 : 12862 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
767 : 12862 : return shortStats->GetMaxConfirms();
768 : : }
769 : 17026 : case FeeEstimateHorizon::MED_HALFLIFE: {
770 : 17026 : return feeStats->GetMaxConfirms();
771 : : }
772 : 19084 : case FeeEstimateHorizon::LONG_HALFLIFE: {
773 : 19084 : return longStats->GetMaxConfirms();
774 : : }
775 : : } // no default case, so the compiler can warn about missing cases
776 : 0 : assert(false);
777 : 48972 : }
778 : :
779 : 2062 : unsigned int CBlockPolicyEstimator::BlockSpan() const
780 : : {
781 [ + + ]: 2062 : if (firstRecordedHeight == 0) return 0;
782 [ - + ]: 1684 : assert(nBestSeenHeight >= firstRecordedHeight);
783 : :
784 : 1684 : return nBestSeenHeight - firstRecordedHeight;
785 : : }
786 : :
787 : 2062 : unsigned int CBlockPolicyEstimator::HistoricalBlockSpan() const
788 : : {
789 [ + + ]: 2062 : if (historicalFirst == 0) return 0;
790 [ - + ]: 22 : assert(historicalBest >= historicalFirst);
791 : :
792 [ + + ]: 22 : if (nBestSeenHeight - historicalBest > OLDEST_ESTIMATE_HISTORY) return 0;
793 : :
794 : 4 : return historicalBest - historicalFirst;
795 : : }
796 : :
797 : 1877 : 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 [ + - + + ]: 3754 : 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 : 4911 : double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const
808 : : {
809 : 4911 : double estimate = -1;
810 [ + - + + ]: 4911 : if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
811 : : // Find estimate from shortest time horizon possible
812 [ + + ]: 4825 : if (confTarget <= shortStats->GetMaxConfirms()) { // short horizon
813 : 1317 : estimate = shortStats->EstimateMedianVal(confTarget, SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, result);
814 : : }
815 [ + + ]: 3508 : else if (confTarget <= feeStats->GetMaxConfirms()) { // medium horizon
816 : 1707 : estimate = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
817 : : }
818 : : else { // long horizon
819 : 1801 : estimate = longStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
820 : : }
821 [ + + ]: 4825 : if (checkShorterHorizon) {
822 : 4054 : EstimationResult tempResult;
823 : : // If a lower confTarget from a more recent horizon returns a lower answer use it.
824 [ + + ]: 4054 : if (confTarget > feeStats->GetMaxConfirms()) {
825 : 1453 : double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, &tempResult);
826 [ - + - - : 1453 : if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
- - ]
827 : 0 : estimate = medMax;
828 [ # # ]: 0 : if (result) *result = tempResult;
829 : : }
830 : : }
831 [ + + ]: 4054 : if (confTarget > shortStats->GetMaxConfirms()) {
832 : 2971 : double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(), SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, &tempResult);
833 [ + + - + : 2971 : if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
- - ]
834 : 110 : estimate = shortMax;
835 [ + - ]: 110 : if (result) *result = tempResult;
836 : : }
837 : : }
838 : : }
839 : : }
840 : 4911 : 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 : 1590 : double CBlockPolicyEstimator::estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const
847 : : {
848 : 1590 : double estimate = -1;
849 : 1590 : EstimationResult tempResult;
850 [ + + ]: 1590 : if (doubleTarget <= shortStats->GetMaxConfirms()) {
851 : 335 : estimate = feeStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, result);
852 : : }
853 [ + + ]: 1590 : if (doubleTarget <= feeStats->GetMaxConfirms()) {
854 : 529 : double longEstimate = longStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, &tempResult);
855 [ - + ]: 529 : if (longEstimate > estimate) {
856 : 0 : estimate = longEstimate;
857 [ # # ]: 0 : if (result) *result = tempResult;
858 : : }
859 : : }
860 : 1590 : 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 : 48972 : CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
871 : : {
872 : 48972 : LOCK(m_cs_fee_estimator);
873 : :
874 [ + + ]: 48972 : if (feeCalc) {
875 : 35040 : feeCalc->desiredTarget = confTarget;
876 : 35040 : feeCalc->returnedTarget = confTarget;
877 : : }
878 : :
879 : 48972 : double median = -1;
880 : 48972 : EstimationResult tempResult;
881 : :
882 : : // Return failure if trying to analyze a target we're not tracking
883 [ + + + + ]: 48972 : if (confTarget <= 0 || (unsigned int)confTarget > longStats->GetMaxConfirms()) {
884 : 47095 : return CFeeRate(0); // error condition
885 : : }
886 : :
887 : : // It's not possible to get reasonable estimates for confTarget of 1
888 [ + + ]: 1877 : if (confTarget == 1) confTarget = 2;
889 : :
890 [ + - ]: 1877 : unsigned int maxUsableEstimate = MaxUsableEstimate();
891 [ + + ]: 1877 : if ((unsigned int)confTarget > maxUsableEstimate) {
892 : 240 : confTarget = maxUsableEstimate;
893 : : }
894 [ + + ]: 1877 : if (feeCalc) feeCalc->returnedTarget = confTarget;
895 : :
896 [ + + ]: 1877 : if (confTarget <= 1) return CFeeRate(0); // error condition
897 : :
898 : 1637 : 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 [ + - ]: 1637 : double halfEst = estimateCombinedFee(confTarget/2, HALF_SUCCESS_PCT, true, &tempResult);
910 [ + + ]: 1637 : if (feeCalc) {
911 : 894 : feeCalc->est = tempResult;
912 : 894 : feeCalc->reason = FeeReason::HALF_ESTIMATE;
913 : : }
914 : 1637 : median = halfEst;
915 [ + - ]: 1637 : double actualEst = estimateCombinedFee(confTarget, SUCCESS_PCT, true, &tempResult);
916 [ + + ]: 1637 : if (actualEst > median) {
917 : 10 : median = actualEst;
918 [ + - ]: 10 : if (feeCalc) {
919 : 10 : feeCalc->est = tempResult;
920 : 10 : feeCalc->reason = FeeReason::FULL_ESTIMATE;
921 : : }
922 : : }
923 [ + - ]: 1637 : double doubleEst = estimateCombinedFee(2 * confTarget, DOUBLE_SUCCESS_PCT, !conservative, &tempResult);
924 [ + + ]: 1637 : if (doubleEst > median) {
925 : 10 : median = doubleEst;
926 [ + - ]: 10 : if (feeCalc) {
927 : 10 : feeCalc->est = tempResult;
928 : 10 : feeCalc->reason = FeeReason::DOUBLE_ESTIMATE;
929 : : }
930 : : }
931 : :
932 [ + + ]: 1637 : if (conservative || median == -1) {
933 [ + - ]: 1590 : double consEst = estimateConservativeFee(2 * confTarget, &tempResult);
934 [ - + ]: 1590 : if (consEst > median) {
935 : 0 : median = consEst;
936 [ # # ]: 0 : if (feeCalc) {
937 : 0 : feeCalc->est = tempResult;
938 : 0 : feeCalc->reason = FeeReason::CONSERVATIVE;
939 : : }
940 : : }
941 : : }
942 : :
943 [ + + ]: 1637 : if (median < 0) return CFeeRate(0); // error condition
944 : :
945 : 73 : return CFeeRate(llround(median));
946 : 48972 : }
947 : :
948 : 0 : void CBlockPolicyEstimator::Flush() {
949 : 0 : FlushUnconfirmed();
950 : 0 : FlushFeeEstimates();
951 : 0 : }
952 : :
953 : 0 : void CBlockPolicyEstimator::FlushFeeEstimates()
954 : : {
955 [ # # ]: 0 : AutoFile est_file{fsbridge::fopen(m_estimation_filepath, "wb")};
956 [ # # # # : 0 : if (est_file.IsNull() || !Write(est_file)) {
# # ]
957 [ # # # # ]: 0 : LogPrintf("Failed to write fee estimates to %s. Continue anyway.\n", fs::PathToString(m_estimation_filepath));
958 : : } else {
959 [ # # # # ]: 0 : LogPrintf("Flushed fee estimates to %s.\n", fs::PathToString(m_estimation_filepath.filename()));
960 : : }
961 : 0 : }
962 : :
963 : 856 : bool CBlockPolicyEstimator::Write(AutoFile& fileout) const
964 : : {
965 : 856 : try {
966 [ + - ]: 856 : LOCK(m_cs_fee_estimator);
967 [ + + ]: 856 : fileout << CURRENT_FEES_FILE_VERSION;
968 [ + - ]: 185 : fileout << int{0}; // Unused dummy field. Written files may contain any value in [0, 289900]
969 [ + - ]: 185 : fileout << nBestSeenHeight;
970 [ + - + - : 185 : if (BlockSpan() > HistoricalBlockSpan()/2) {
+ + ]
971 [ + - + - ]: 23 : fileout << firstRecordedHeight << nBestSeenHeight;
972 : : }
973 : : else {
974 [ + - + - ]: 162 : fileout << historicalFirst << historicalBest;
975 : : }
976 [ + - ]: 185 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(buckets);
977 [ + + ]: 185 : feeStats->Write(fileout);
978 [ + + ]: 43 : shortStats->Write(fileout);
979 [ + + ]: 38 : longStats->Write(fileout);
980 : 825 : }
981 [ - + ]: 825 : catch (const std::exception&) {
982 [ + - ]: 825 : LogWarning("Unable to write policy estimator data (non-fatal)");
983 : 825 : return false;
984 : 825 : }
985 : 31 : return true;
986 : : }
987 : :
988 : 1151 : bool CBlockPolicyEstimator::Read(AutoFile& filein)
989 : : {
990 : 1151 : try {
991 [ + - ]: 1151 : LOCK(m_cs_fee_estimator);
992 : 1151 : int nVersionRequired, dummy;
993 [ + + + + ]: 1151 : filein >> nVersionRequired >> dummy;
994 [ + + ]: 544 : if (nVersionRequired > CURRENT_FEES_FILE_VERSION) {
995 [ + - + - ]: 672 : throw std::runtime_error{strprintf("File version (%d) too high to be read.", nVersionRequired)};
996 : : }
997 : :
998 : : // Read fee estimates file into temporary variables so existing data
999 : : // structures aren't corrupted if there is an exception.
1000 : 208 : unsigned int nFileBestSeenHeight;
1001 [ + + ]: 208 : filein >> nFileBestSeenHeight;
1002 : :
1003 [ + + ]: 203 : if (nVersionRequired < CURRENT_FEES_FILE_VERSION) {
1004 [ + - ]: 23 : LogWarning("Incompatible old fee estimation data (non-fatal). Version: %d", nVersionRequired);
1005 : : } else { // nVersionRequired == CURRENT_FEES_FILE_VERSION
1006 : 180 : unsigned int nFileHistoricalFirst, nFileHistoricalBest;
1007 [ + - + - ]: 180 : filein >> nFileHistoricalFirst >> nFileHistoricalBest;
1008 [ + + + + ]: 180 : if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
1009 [ + - ]: 4 : throw std::runtime_error("Corrupt estimates file. Historical block range for estimates is invalid");
1010 : : }
1011 : 176 : std::vector<double> fileBuckets;
1012 [ + + ]: 176 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(fileBuckets);
1013 [ + + ]: 151 : size_t numBuckets = fileBuckets.size();
1014 [ + + ]: 151 : if (numBuckets <= 1 || numBuckets > 1000) {
1015 [ + - ]: 2 : throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
1016 : : }
1017 : :
1018 [ + - + - : 149 : std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
+ - ]
1019 [ + - + - : 149 : std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
+ - ]
1020 [ + - + - : 149 : std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
+ + ]
1021 [ + + ]: 149 : fileFeeStats->Read(filein, numBuckets);
1022 [ + + ]: 88 : fileShortStats->Read(filein, numBuckets);
1023 [ + + ]: 40 : fileLongStats->Read(filein, numBuckets);
1024 : :
1025 : : // Fee estimates file parsed correctly
1026 : : // Copy buckets from file and refresh our bucketmap
1027 [ + - ]: 30 : buckets = fileBuckets;
1028 : 30 : bucketMap.clear();
1029 [ + + ]: 112 : for (unsigned int i = 0; i < buckets.size(); i++) {
1030 [ + - ]: 82 : bucketMap[buckets[i]] = i;
1031 : : }
1032 : :
1033 : : // Destroy old TxConfirmStats and point to new ones that already reference buckets and bucketMap
1034 : 30 : feeStats = std::move(fileFeeStats);
1035 : 30 : shortStats = std::move(fileShortStats);
1036 : 30 : longStats = std::move(fileLongStats);
1037 : :
1038 : 30 : nBestSeenHeight = nFileBestSeenHeight;
1039 : 30 : historicalFirst = nFileHistoricalFirst;
1040 : 30 : historicalBest = nFileHistoricalBest;
1041 : 533 : }
1042 : 1098 : }
1043 [ - + ]: 1098 : catch (const std::exception& e) {
1044 [ + - ]: 1098 : LogWarning("Unable to read policy estimator data (non-fatal): %s", e.what());
1045 : 1098 : return false;
1046 : 1098 : }
1047 : 53 : return true;
1048 : : }
1049 : :
1050 : 25067 : void CBlockPolicyEstimator::FlushUnconfirmed()
1051 : : {
1052 : 25067 : const auto startclear{SteadyClock::now()};
1053 : 25067 : LOCK(m_cs_fee_estimator);
1054 : 25067 : size_t num_entries = mapMemPoolTxs.size();
1055 : : // Remove every entry in mapMemPoolTxs
1056 [ + + ]: 27357 : while (!mapMemPoolTxs.empty()) {
1057 [ + - ]: 2290 : auto mi = mapMemPoolTxs.begin();
1058 [ + - ]: 2290 : _removeTx(mi->first, false); // this calls erase() on mapMemPoolTxs
1059 : : }
1060 : 25067 : const auto endclear{SteadyClock::now()};
1061 [ + - - + : 25067 : LogDebug(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %.3fs\n", num_entries, Ticks<SecondsDouble>(endclear - startclear));
- - + - ]
1062 : 25067 : }
1063 : :
1064 : 0 : std::chrono::hours CBlockPolicyEstimator::GetFeeEstimatorFileAge()
1065 : : {
1066 : 0 : auto file_time{fs::last_write_time(m_estimation_filepath)};
1067 : 0 : auto now{fs::file_time_type::clock::now()};
1068 : 0 : return std::chrono::duration_cast<std::chrono::hours>(now - file_time);
1069 : : }
1070 : :
1071 : 1148 : static std::set<double> MakeFeeSet(const CFeeRate& min_incremental_fee,
1072 : : double max_filter_fee_rate,
1073 : : double fee_filter_spacing)
1074 : : {
1075 [ + + ]: 1148 : std::set<double> fee_set;
1076 : :
1077 [ + + ]: 1148 : const CAmount min_fee_limit{std::max(CAmount(1), min_incremental_fee.GetFeePerK() / 2)};
1078 [ + - ]: 1148 : fee_set.insert(0);
1079 : 1148 : for (double bucket_boundary = min_fee_limit;
1080 [ + + ]: 118040 : bucket_boundary <= max_filter_fee_rate;
1081 : 116892 : bucket_boundary *= fee_filter_spacing) {
1082 : :
1083 [ + - ]: 116892 : fee_set.insert(bucket_boundary);
1084 : : }
1085 : :
1086 : 1148 : return fee_set;
1087 : 0 : }
1088 : :
1089 : 1148 : FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee, FastRandomContext& rng)
1090 : 1148 : : m_fee_set{MakeFeeSet(minIncrementalFee, MAX_FILTER_FEERATE, FEE_FILTER_SPACING)},
1091 : 1148 : insecure_rand{rng}
1092 : : {
1093 : 1148 : }
1094 : :
1095 : 84697 : CAmount FeeFilterRounder::round(CAmount currentMinFee)
1096 : : {
1097 : 84697 : AssertLockNotHeld(m_insecure_rand_mutex);
1098 : 84697 : std::set<double>::iterator it = m_fee_set.lower_bound(currentMinFee);
1099 [ + + + + ]: 84697 : if (it == m_fee_set.end() ||
1100 [ + + ]: 65733 : (it != m_fee_set.begin() &&
1101 [ + + + - ]: 112256 : WITH_LOCK(m_insecure_rand_mutex, return insecure_rand.rand32()) % 3 != 0)) {
1102 : 56815 : --it;
1103 : : }
1104 : 84697 : return static_cast<CAmount>(*it);
1105 : : }
|
