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