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