Bitcoin Core  0.18.99
P2P Digital Currency
fees.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2018 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 
6 #include <policy/fees.h>
7 
8 #include <clientversion.h>
10 #include <streams.h>
11 #include <txmempool.h>
12 #include <util/system.h>
13 
14 static constexpr double INF_FEERATE = 1e99;
15 
17  static const std::map<FeeEstimateHorizon, std::string> horizon_strings = {
21  };
22  auto horizon_string = horizon_strings.find(horizon);
23 
24  if (horizon_string == horizon_strings.end()) return "unknown";
25 
26  return horizon_string->second;
27 }
28 
38 {
39 private:
40  //Define the buckets we will group transactions into
41  const std::vector<double>& buckets; // The upper-bound of the range for the bucket (inclusive)
42  const std::map<double, unsigned int>& bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
43 
44  // For each bucket X:
45  // Count the total # of txs in each bucket
46  // Track the historical moving average of this total over blocks
47  std::vector<double> txCtAvg;
48 
49  // Count the total # of txs confirmed within Y blocks in each bucket
50  // Track the historical moving average of these totals over blocks
51  std::vector<std::vector<double>> confAvg; // confAvg[Y][X]
52 
53  // Track moving avg of txs which have been evicted from the mempool
54  // after failing to be confirmed within Y blocks
55  std::vector<std::vector<double>> failAvg; // failAvg[Y][X]
56 
57  // Sum the total feerate of all tx's in each bucket
58  // Track the historical moving average of this total over blocks
59  std::vector<double> avg;
60 
61  // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
62  // Combine the total value with the tx counts to calculate the avg feerate per bucket
63 
64  double decay;
65 
66  // Resolution (# of blocks) with which confirmations are tracked
67  unsigned int scale;
68 
69  // Mempool counts of outstanding transactions
70  // For each bucket X, track the number of transactions in the mempool
71  // that are unconfirmed for each possible confirmation value Y
72  std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
73  // transactions still unconfirmed after GetMaxConfirms for each bucket
74  std::vector<int> oldUnconfTxs;
75 
76  void resizeInMemoryCounters(size_t newbuckets);
77 
78 public:
86  TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,
87  unsigned int maxPeriods, double decay, unsigned int scale);
88 
90  void ClearCurrent(unsigned int nBlockHeight);
91 
98  void Record(int blocksToConfirm, double val);
99 
101  unsigned int NewTx(unsigned int nBlockHeight, double val);
102 
104  void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
105  unsigned int bucketIndex, bool inBlock);
106 
109  void UpdateMovingAverages();
110 
122  double EstimateMedianVal(int confTarget, double sufficientTxVal,
123  double minSuccess, bool requireGreater, unsigned int nBlockHeight,
124  EstimationResult *result = nullptr) const;
125 
127  unsigned int GetMaxConfirms() const { return scale * confAvg.size(); }
128 
130  void Write(CAutoFile& fileout) const;
131 
136  void Read(CAutoFile& filein, int nFileVersion, size_t numBuckets);
137 };
138 
139 
140 TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
141  const std::map<double, unsigned int>& defaultBucketMap,
142  unsigned int maxPeriods, double _decay, unsigned int _scale)
143  : buckets(defaultBuckets), bucketMap(defaultBucketMap)
144 {
145  decay = _decay;
146  assert(_scale != 0 && "_scale must be non-zero");
147  scale = _scale;
148  confAvg.resize(maxPeriods);
149  for (unsigned int i = 0; i < maxPeriods; i++) {
150  confAvg[i].resize(buckets.size());
151  }
152  failAvg.resize(maxPeriods);
153  for (unsigned int i = 0; i < maxPeriods; i++) {
154  failAvg[i].resize(buckets.size());
155  }
156 
157  txCtAvg.resize(buckets.size());
158  avg.resize(buckets.size());
159 
161 }
162 
163 void TxConfirmStats::resizeInMemoryCounters(size_t newbuckets) {
164  // newbuckets must be passed in because the buckets referred to during Read have not been updated yet.
165  unconfTxs.resize(GetMaxConfirms());
166  for (unsigned int i = 0; i < unconfTxs.size(); i++) {
167  unconfTxs[i].resize(newbuckets);
168  }
169  oldUnconfTxs.resize(newbuckets);
170 }
171 
172 // Roll the unconfirmed txs circular buffer
173 void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
174 {
175  for (unsigned int j = 0; j < buckets.size(); j++) {
176  oldUnconfTxs[j] += unconfTxs[nBlockHeight%unconfTxs.size()][j];
177  unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
178  }
179 }
180 
181 
182 void TxConfirmStats::Record(int blocksToConfirm, double val)
183 {
184  // blocksToConfirm is 1-based
185  if (blocksToConfirm < 1)
186  return;
187  int periodsToConfirm = (blocksToConfirm + scale - 1)/scale;
188  unsigned int bucketindex = bucketMap.lower_bound(val)->second;
189  for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
190  confAvg[i - 1][bucketindex]++;
191  }
192  txCtAvg[bucketindex]++;
193  avg[bucketindex] += val;
194 }
195 
197 {
198  for (unsigned int j = 0; j < buckets.size(); j++) {
199  for (unsigned int i = 0; i < confAvg.size(); i++)
200  confAvg[i][j] = confAvg[i][j] * decay;
201  for (unsigned int i = 0; i < failAvg.size(); i++)
202  failAvg[i][j] = failAvg[i][j] * decay;
203  avg[j] = avg[j] * decay;
204  txCtAvg[j] = txCtAvg[j] * decay;
205  }
206 }
207 
208 // returns -1 on error conditions
209 double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
210  double successBreakPoint, bool requireGreater,
211  unsigned int nBlockHeight, EstimationResult *result) const
212 {
213  // Counters for a bucket (or range of buckets)
214  double nConf = 0; // Number of tx's confirmed within the confTarget
215  double totalNum = 0; // Total number of tx's that were ever confirmed
216  int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
217  double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
218  int periodTarget = (confTarget + scale - 1)/scale;
219 
220  int maxbucketindex = buckets.size() - 1;
221 
222  // requireGreater means we are looking for the lowest feerate such that all higher
223  // values pass, so we start at maxbucketindex (highest feerate) and look at successively
224  // smaller buckets until we reach failure. Otherwise, we are looking for the highest
225  // feerate such that all lower values fail, and we go in the opposite direction.
226  unsigned int startbucket = requireGreater ? maxbucketindex : 0;
227  int step = requireGreater ? -1 : 1;
228 
229  // We'll combine buckets until we have enough samples.
230  // The near and far variables will define the range we've combined
231  // The best variables are the last range we saw which still had a high
232  // enough confirmation rate to count as success.
233  // The cur variables are the current range we're counting.
234  unsigned int curNearBucket = startbucket;
235  unsigned int bestNearBucket = startbucket;
236  unsigned int curFarBucket = startbucket;
237  unsigned int bestFarBucket = startbucket;
238 
239  bool foundAnswer = false;
240  unsigned int bins = unconfTxs.size();
241  bool newBucketRange = true;
242  bool passing = true;
243  EstimatorBucket passBucket;
244  EstimatorBucket failBucket;
245 
246  // Start counting from highest(default) or lowest feerate transactions
247  for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) {
248  if (newBucketRange) {
249  curNearBucket = bucket;
250  newBucketRange = false;
251  }
252  curFarBucket = bucket;
253  nConf += confAvg[periodTarget - 1][bucket];
254  totalNum += txCtAvg[bucket];
255  failNum += failAvg[periodTarget - 1][bucket];
256  for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
257  extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket];
258  extraNum += oldUnconfTxs[bucket];
259  // If we have enough transaction data points in this range of buckets,
260  // we can test for success
261  // (Only count the confirmed data points, so that each confirmation count
262  // will be looking at the same amount of data and same bucket breaks)
263  if (totalNum >= sufficientTxVal / (1 - decay)) {
264  double curPct = nConf / (totalNum + failNum + extraNum);
265 
266  // Check to see if we are no longer getting confirmed at the success rate
267  if ((requireGreater && curPct < successBreakPoint) || (!requireGreater && curPct > successBreakPoint)) {
268  if (passing == true) {
269  // First time we hit a failure record the failed bucket
270  unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
271  unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
272  failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
273  failBucket.end = buckets[failMaxBucket];
274  failBucket.withinTarget = nConf;
275  failBucket.totalConfirmed = totalNum;
276  failBucket.inMempool = extraNum;
277  failBucket.leftMempool = failNum;
278  passing = false;
279  }
280  continue;
281  }
282  // Otherwise update the cumulative stats, and the bucket variables
283  // and reset the counters
284  else {
285  failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
286  foundAnswer = true;
287  passing = true;
288  passBucket.withinTarget = nConf;
289  nConf = 0;
290  passBucket.totalConfirmed = totalNum;
291  totalNum = 0;
292  passBucket.inMempool = extraNum;
293  passBucket.leftMempool = failNum;
294  failNum = 0;
295  extraNum = 0;
296  bestNearBucket = curNearBucket;
297  bestFarBucket = curFarBucket;
298  newBucketRange = true;
299  }
300  }
301  }
302 
303  double median = -1;
304  double txSum = 0;
305 
306  // Calculate the "average" feerate of the best bucket range that met success conditions
307  // Find the bucket with the median transaction and then report the average feerate from that bucket
308  // This is a compromise between finding the median which we can't since we don't save all tx's
309  // and reporting the average which is less accurate
310  unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
311  unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
312  for (unsigned int j = minBucket; j <= maxBucket; j++) {
313  txSum += txCtAvg[j];
314  }
315  if (foundAnswer && txSum != 0) {
316  txSum = txSum / 2;
317  for (unsigned int j = minBucket; j <= maxBucket; j++) {
318  if (txCtAvg[j] < txSum)
319  txSum -= txCtAvg[j];
320  else { // we're in the right bucket
321  median = avg[j] / txCtAvg[j];
322  break;
323  }
324  }
325 
326  passBucket.start = minBucket ? buckets[minBucket-1] : 0;
327  passBucket.end = buckets[maxBucket];
328  }
329 
330  // If we were passing until we reached last few buckets with insufficient data, then report those as failed
331  if (passing && !newBucketRange) {
332  unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
333  unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
334  failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
335  failBucket.end = buckets[failMaxBucket];
336  failBucket.withinTarget = nConf;
337  failBucket.totalConfirmed = totalNum;
338  failBucket.inMempool = extraNum;
339  failBucket.leftMempool = failNum;
340  }
341 
342  LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.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",
343  confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay,
344  median, passBucket.start, passBucket.end,
345  100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool),
346  passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool,
347  failBucket.start, failBucket.end,
348  100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool),
349  failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool);
350 
351 
352  if (result) {
353  result->pass = passBucket;
354  result->fail = failBucket;
355  result->decay = decay;
356  result->scale = scale;
357  }
358  return median;
359 }
360 
361 void TxConfirmStats::Write(CAutoFile& fileout) const
362 {
363  fileout << decay;
364  fileout << scale;
365  fileout << avg;
366  fileout << txCtAvg;
367  fileout << confAvg;
368  fileout << failAvg;
369 }
370 
371 void TxConfirmStats::Read(CAutoFile& filein, int nFileVersion, size_t numBuckets)
372 {
373  // Read data file and do some very basic sanity checking
374  // buckets and bucketMap are not updated yet, so don't access them
375  // If there is a read failure, we'll just discard this entire object anyway
376  size_t maxConfirms, maxPeriods;
377 
378  // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
379  filein >> decay;
380  if (decay <= 0 || decay >= 1) {
381  throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
382  }
383  filein >> scale;
384  if (scale == 0) {
385  throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
386  }
387 
388  filein >> avg;
389  if (avg.size() != numBuckets) {
390  throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
391  }
392  filein >> txCtAvg;
393  if (txCtAvg.size() != numBuckets) {
394  throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
395  }
396  filein >> confAvg;
397  maxPeriods = confAvg.size();
398  maxConfirms = scale * maxPeriods;
399 
400  if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
401  throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
402  }
403  for (unsigned int i = 0; i < maxPeriods; i++) {
404  if (confAvg[i].size() != numBuckets) {
405  throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
406  }
407  }
408 
409  filein >> failAvg;
410  if (maxPeriods != failAvg.size()) {
411  throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
412  }
413  for (unsigned int i = 0; i < maxPeriods; i++) {
414  if (failAvg[i].size() != numBuckets) {
415  throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
416  }
417  }
418 
419  // Resize the current block variables which aren't stored in the data file
420  // to match the number of confirms and buckets
421  resizeInMemoryCounters(numBuckets);
422 
423  LogPrint(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
424  numBuckets, maxConfirms);
425 }
426 
427 unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
428 {
429  unsigned int bucketindex = bucketMap.lower_bound(val)->second;
430  unsigned int blockIndex = nBlockHeight % unconfTxs.size();
431  unconfTxs[blockIndex][bucketindex]++;
432  return bucketindex;
433 }
434 
435 void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex, bool inBlock)
436 {
437  //nBestSeenHeight is not updated yet for the new block
438  int blocksAgo = nBestSeenHeight - entryHeight;
439  if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
440  blocksAgo = 0;
441  if (blocksAgo < 0) {
442  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, blocks ago is negative for mempool tx\n");
443  return; //This can't happen because we call this with our best seen height, no entries can have higher
444  }
445 
446  if (blocksAgo >= (int)unconfTxs.size()) {
447  if (oldUnconfTxs[bucketindex] > 0) {
448  oldUnconfTxs[bucketindex]--;
449  } else {
450  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
451  bucketindex);
452  }
453  }
454  else {
455  unsigned int blockIndex = entryHeight % unconfTxs.size();
456  if (unconfTxs[blockIndex][bucketindex] > 0) {
457  unconfTxs[blockIndex][bucketindex]--;
458  } else {
459  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
460  blockIndex, bucketindex);
461  }
462  }
463  if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
464  assert(scale != 0);
465  unsigned int periodsAgo = blocksAgo / scale;
466  for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
467  failAvg[i][bucketindex]++;
468  }
469  }
470 }
471 
472 // This function is called from CTxMemPool::removeUnchecked to ensure
473 // txs removed from the mempool for any reason are no longer
474 // tracked. Txs that were part of a block have already been removed in
475 // processBlockTx to ensure they are never double tracked, but it is
476 // of no harm to try to remove them again.
477 bool CBlockPolicyEstimator::removeTx(uint256 hash, bool inBlock)
478 {
479  LOCK(m_cs_fee_estimator);
480  std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
481  if (pos != mapMemPoolTxs.end()) {
482  feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
483  shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
484  longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
485  mapMemPoolTxs.erase(hash);
486  return true;
487  } else {
488  return false;
489  }
490 }
491 
493  : nBestSeenHeight(0), firstRecordedHeight(0), historicalFirst(0), historicalBest(0), trackedTxs(0), untrackedTxs(0)
494 {
495  static_assert(MIN_BUCKET_FEERATE > 0, "Min feerate must be nonzero");
496  size_t bucketIndex = 0;
497  for (double bucketBoundary = MIN_BUCKET_FEERATE; bucketBoundary <= MAX_BUCKET_FEERATE; bucketBoundary *= FEE_SPACING, bucketIndex++) {
498  buckets.push_back(bucketBoundary);
499  bucketMap[bucketBoundary] = bucketIndex;
500  }
501  buckets.push_back(INF_FEERATE);
502  bucketMap[INF_FEERATE] = bucketIndex;
503  assert(bucketMap.size() == buckets.size());
504 
505  feeStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
506  shortStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
507  longStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
508 }
509 
511 {
512 }
513 
514 void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
515 {
517  unsigned int txHeight = entry.GetHeight();
518  uint256 hash = entry.GetTx().GetHash();
519  if (mapMemPoolTxs.count(hash)) {
520  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error mempool tx %s already being tracked\n",
521  hash.ToString().c_str());
522  return;
523  }
524 
525  if (txHeight != nBestSeenHeight) {
526  // Ignore side chains and re-orgs; assuming they are random they don't
527  // affect the estimate. We'll potentially double count transactions in 1-block reorgs.
528  // Ignore txs if BlockPolicyEstimator is not in sync with ::ChainActive().Tip().
529  // It will be synced next time a block is processed.
530  return;
531  }
532 
533  // Only want to be updating estimates when our blockchain is synced,
534  // otherwise we'll miscalculate how many blocks its taking to get included.
535  if (!validFeeEstimate) {
536  untrackedTxs++;
537  return;
538  }
539  trackedTxs++;
540 
541  // Feerates are stored and reported as BTC-per-kb:
542  CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
543 
544  mapMemPoolTxs[hash].blockHeight = txHeight;
545  unsigned int bucketIndex = feeStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
546  mapMemPoolTxs[hash].bucketIndex = bucketIndex;
547  unsigned int bucketIndex2 = shortStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
548  assert(bucketIndex == bucketIndex2);
549  unsigned int bucketIndex3 = longStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
550  assert(bucketIndex == bucketIndex3);
551 }
552 
553 bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry)
554 {
555  if (!removeTx(entry->GetTx().GetHash(), true)) {
556  // This transaction wasn't being tracked for fee estimation
557  return false;
558  }
559 
560  // How many blocks did it take for miners to include this transaction?
561  // blocksToConfirm is 1-based, so a transaction included in the earliest
562  // possible block has confirmation count of 1
563  int blocksToConfirm = nBlockHeight - entry->GetHeight();
564  if (blocksToConfirm <= 0) {
565  // This can't happen because we don't process transactions from a block with a height
566  // lower than our greatest seen height
567  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error Transaction had negative blocksToConfirm\n");
568  return false;
569  }
570 
571  // Feerates are stored and reported as BTC-per-kb:
572  CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
573 
574  feeStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
575  shortStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
576  longStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
577  return true;
578 }
579 
580 void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
581  std::vector<const CTxMemPoolEntry*>& entries)
582 {
584  if (nBlockHeight <= nBestSeenHeight) {
585  // Ignore side chains and re-orgs; assuming they are random
586  // they don't affect the estimate.
587  // And if an attacker can re-org the chain at will, then
588  // you've got much bigger problems than "attacker can influence
589  // transaction fees."
590  return;
591  }
592 
593  // Must update nBestSeenHeight in sync with ClearCurrent so that
594  // calls to removeTx (via processBlockTx) correctly calculate age
595  // of unconfirmed txs to remove from tracking.
596  nBestSeenHeight = nBlockHeight;
597 
598  // Update unconfirmed circular buffer
599  feeStats->ClearCurrent(nBlockHeight);
600  shortStats->ClearCurrent(nBlockHeight);
601  longStats->ClearCurrent(nBlockHeight);
602 
603  // Decay all exponential averages
604  feeStats->UpdateMovingAverages();
605  shortStats->UpdateMovingAverages();
606  longStats->UpdateMovingAverages();
607 
608  unsigned int countedTxs = 0;
609  // Update averages with data points from current block
610  for (const auto& entry : entries) {
611  if (processBlockTx(nBlockHeight, entry))
612  countedTxs++;
613  }
614 
615  if (firstRecordedHeight == 0 && countedTxs > 0) {
616  firstRecordedHeight = nBestSeenHeight;
617  LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy first recorded height %u\n", firstRecordedHeight);
618  }
619 
620 
621  LogPrint(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",
622  countedTxs, entries.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size(),
623  MaxUsableEstimate(), HistoricalBlockSpan() > BlockSpan() ? "historical" : "current");
624 
625  trackedTxs = 0;
626  untrackedTxs = 0;
627 }
628 
630 {
631  // It's not possible to get reasonable estimates for confTarget of 1
632  if (confTarget <= 1)
633  return CFeeRate(0);
634 
636 }
637 
638 CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult* result) const
639 {
640  TxConfirmStats* stats;
641  double sufficientTxs = SUFFICIENT_FEETXS;
642  switch (horizon) {
644  stats = shortStats.get();
645  sufficientTxs = SUFFICIENT_TXS_SHORT;
646  break;
647  }
649  stats = feeStats.get();
650  break;
651  }
653  stats = longStats.get();
654  break;
655  }
656  default: {
657  throw std::out_of_range("CBlockPolicyEstimator::estimateRawFee unknown FeeEstimateHorizon");
658  }
659  }
660 
662  // Return failure if trying to analyze a target we're not tracking
663  if (confTarget <= 0 || (unsigned int)confTarget > stats->GetMaxConfirms())
664  return CFeeRate(0);
665  if (successThreshold > 1)
666  return CFeeRate(0);
667 
668  double median = stats->EstimateMedianVal(confTarget, sufficientTxs, successThreshold, true, nBestSeenHeight, result);
669 
670  if (median < 0)
671  return CFeeRate(0);
672 
673  return CFeeRate(llround(median));
674 }
675 
677 {
679  switch (horizon) {
681  return shortStats->GetMaxConfirms();
682  }
684  return feeStats->GetMaxConfirms();
685  }
687  return longStats->GetMaxConfirms();
688  }
689  default: {
690  throw std::out_of_range("CBlockPolicyEstimator::HighestTargetTracked unknown FeeEstimateHorizon");
691  }
692  }
693 }
694 
696 {
697  if (firstRecordedHeight == 0) return 0;
698  assert(nBestSeenHeight >= firstRecordedHeight);
699 
700  return nBestSeenHeight - firstRecordedHeight;
701 }
702 
704 {
705  if (historicalFirst == 0) return 0;
706  assert(historicalBest >= historicalFirst);
707 
708  if (nBestSeenHeight - historicalBest > OLDEST_ESTIMATE_HISTORY) return 0;
709 
710  return historicalBest - historicalFirst;
711 }
712 
714 {
715  // Block spans are divided by 2 to make sure there are enough potential failing data points for the estimate
716  return std::min(longStats->GetMaxConfirms(), std::max(BlockSpan(), HistoricalBlockSpan()) / 2);
717 }
718 
723 double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const
724 {
725  double estimate = -1;
726  if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
727  // Find estimate from shortest time horizon possible
728  if (confTarget <= shortStats->GetMaxConfirms()) { // short horizon
729  estimate = shortStats->EstimateMedianVal(confTarget, SUFFICIENT_TXS_SHORT, successThreshold, true, nBestSeenHeight, result);
730  }
731  else if (confTarget <= feeStats->GetMaxConfirms()) { // medium horizon
732  estimate = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, true, nBestSeenHeight, result);
733  }
734  else { // long horizon
735  estimate = longStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, true, nBestSeenHeight, result);
736  }
737  if (checkShorterHorizon) {
738  EstimationResult tempResult;
739  // If a lower confTarget from a more recent horizon returns a lower answer use it.
740  if (confTarget > feeStats->GetMaxConfirms()) {
741  double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, true, nBestSeenHeight, &tempResult);
742  if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
743  estimate = medMax;
744  if (result) *result = tempResult;
745  }
746  }
747  if (confTarget > shortStats->GetMaxConfirms()) {
748  double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(), SUFFICIENT_TXS_SHORT, successThreshold, true, nBestSeenHeight, &tempResult);
749  if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
750  estimate = shortMax;
751  if (result) *result = tempResult;
752  }
753  }
754  }
755  }
756  return estimate;
757 }
758 
762 double CBlockPolicyEstimator::estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const
763 {
764  double estimate = -1;
765  EstimationResult tempResult;
766  if (doubleTarget <= shortStats->GetMaxConfirms()) {
767  estimate = feeStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, true, nBestSeenHeight, result);
768  }
769  if (doubleTarget <= feeStats->GetMaxConfirms()) {
770  double longEstimate = longStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, true, nBestSeenHeight, &tempResult);
771  if (longEstimate > estimate) {
772  estimate = longEstimate;
773  if (result) *result = tempResult;
774  }
775  }
776  return estimate;
777 }
778 
786 CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
787 {
789 
790  if (feeCalc) {
791  feeCalc->desiredTarget = confTarget;
792  feeCalc->returnedTarget = confTarget;
793  }
794 
795  double median = -1;
796  EstimationResult tempResult;
797 
798  // Return failure if trying to analyze a target we're not tracking
799  if (confTarget <= 0 || (unsigned int)confTarget > longStats->GetMaxConfirms()) {
800  return CFeeRate(0); // error condition
801  }
802 
803  // It's not possible to get reasonable estimates for confTarget of 1
804  if (confTarget == 1) confTarget = 2;
805 
806  unsigned int maxUsableEstimate = MaxUsableEstimate();
807  if ((unsigned int)confTarget > maxUsableEstimate) {
808  confTarget = maxUsableEstimate;
809  }
810  if (feeCalc) feeCalc->returnedTarget = confTarget;
811 
812  if (confTarget <= 1) return CFeeRate(0); // error condition
813 
814  assert(confTarget > 0); //estimateCombinedFee and estimateConservativeFee take unsigned ints
825  double halfEst = estimateCombinedFee(confTarget/2, HALF_SUCCESS_PCT, true, &tempResult);
826  if (feeCalc) {
827  feeCalc->est = tempResult;
828  feeCalc->reason = FeeReason::HALF_ESTIMATE;
829  }
830  median = halfEst;
831  double actualEst = estimateCombinedFee(confTarget, SUCCESS_PCT, true, &tempResult);
832  if (actualEst > median) {
833  median = actualEst;
834  if (feeCalc) {
835  feeCalc->est = tempResult;
836  feeCalc->reason = FeeReason::FULL_ESTIMATE;
837  }
838  }
839  double doubleEst = estimateCombinedFee(2 * confTarget, DOUBLE_SUCCESS_PCT, !conservative, &tempResult);
840  if (doubleEst > median) {
841  median = doubleEst;
842  if (feeCalc) {
843  feeCalc->est = tempResult;
845  }
846  }
847 
848  if (conservative || median == -1) {
849  double consEst = estimateConservativeFee(2 * confTarget, &tempResult);
850  if (consEst > median) {
851  median = consEst;
852  if (feeCalc) {
853  feeCalc->est = tempResult;
854  feeCalc->reason = FeeReason::CONSERVATIVE;
855  }
856  }
857  }
858 
859  if (median < 0) return CFeeRate(0); // error condition
860 
861  return CFeeRate(llround(median));
862 }
863 
864 
866 {
867  try {
869  fileout << 149900; // version required to read: 0.14.99 or later
870  fileout << CLIENT_VERSION; // version that wrote the file
871  fileout << nBestSeenHeight;
872  if (BlockSpan() > HistoricalBlockSpan()/2) {
873  fileout << firstRecordedHeight << nBestSeenHeight;
874  }
875  else {
876  fileout << historicalFirst << historicalBest;
877  }
878  fileout << buckets;
879  feeStats->Write(fileout);
880  shortStats->Write(fileout);
881  longStats->Write(fileout);
882  }
883  catch (const std::exception&) {
884  LogPrintf("CBlockPolicyEstimator::Write(): unable to write policy estimator data (non-fatal)\n");
885  return false;
886  }
887  return true;
888 }
889 
891 {
892  try {
894  int nVersionRequired, nVersionThatWrote;
895  filein >> nVersionRequired >> nVersionThatWrote;
896  if (nVersionRequired > CLIENT_VERSION)
897  return error("CBlockPolicyEstimator::Read(): up-version (%d) fee estimate file", nVersionRequired);
898 
899  // Read fee estimates file into temporary variables so existing data
900  // structures aren't corrupted if there is an exception.
901  unsigned int nFileBestSeenHeight;
902  filein >> nFileBestSeenHeight;
903 
904  if (nVersionRequired < 149900) {
905  LogPrintf("%s: incompatible old fee estimation data (non-fatal). Version: %d\n", __func__, nVersionRequired);
906  } else { // New format introduced in 149900
907  unsigned int nFileHistoricalFirst, nFileHistoricalBest;
908  filein >> nFileHistoricalFirst >> nFileHistoricalBest;
909  if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
910  throw std::runtime_error("Corrupt estimates file. Historical block range for estimates is invalid");
911  }
912  std::vector<double> fileBuckets;
913  filein >> fileBuckets;
914  size_t numBuckets = fileBuckets.size();
915  if (numBuckets <= 1 || numBuckets > 1000)
916  throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
917 
918  std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
919  std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
920  std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
921  fileFeeStats->Read(filein, nVersionThatWrote, numBuckets);
922  fileShortStats->Read(filein, nVersionThatWrote, numBuckets);
923  fileLongStats->Read(filein, nVersionThatWrote, numBuckets);
924 
925  // Fee estimates file parsed correctly
926  // Copy buckets from file and refresh our bucketmap
927  buckets = fileBuckets;
928  bucketMap.clear();
929  for (unsigned int i = 0; i < buckets.size(); i++) {
930  bucketMap[buckets[i]] = i;
931  }
932 
933  // Destroy old TxConfirmStats and point to new ones that already reference buckets and bucketMap
934  feeStats = std::move(fileFeeStats);
935  shortStats = std::move(fileShortStats);
936  longStats = std::move(fileLongStats);
937 
938  nBestSeenHeight = nFileBestSeenHeight;
939  historicalFirst = nFileHistoricalFirst;
940  historicalBest = nFileHistoricalBest;
941  }
942  }
943  catch (const std::exception& e) {
944  LogPrintf("CBlockPolicyEstimator::Read(): unable to read policy estimator data (non-fatal): %s\n",e.what());
945  return false;
946  }
947  return true;
948 }
949 
951  int64_t startclear = GetTimeMicros();
953  size_t num_entries = mapMemPoolTxs.size();
954  // Remove every entry in mapMemPoolTxs
955  while (!mapMemPoolTxs.empty()) {
956  auto mi = mapMemPoolTxs.begin();
957  removeTx(mi->first, false); // this calls erase() on mapMemPoolTxs
958  }
959  int64_t endclear = GetTimeMicros();
960  LogPrint(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %gs\n", num_entries, (endclear - startclear)*0.000001);
961 }
962 
964 {
965  CAmount minFeeLimit = std::max(CAmount(1), minIncrementalFee.GetFeePerK() / 2);
966  feeset.insert(0);
967  for (double bucketBoundary = minFeeLimit; bucketBoundary <= MAX_FILTER_FEERATE; bucketBoundary *= FEE_FILTER_SPACING) {
968  feeset.insert(bucketBoundary);
969  }
970 }
971 
973 {
974  std::set<double>::iterator it = feeset.lower_bound(currentMinFee);
975  if ((it != feeset.begin() && insecure_rand.rand32() % 3 != 0) || it == feeset.end()) {
976  it--;
977  }
978  return static_cast<CAmount>(*it);
979 }
static constexpr double MED_DECAY
Decay of .998 is a half-life of 144 blocks or about 1 day.
Definition: fees.h:150
EstimatorBucket pass
Definition: fees.h:70
std::vector< std::vector< double > > failAvg
Definition: fees.cpp:55
EstimationResult est
Definition: fees.h:78
bool processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry *entry) EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Process a transaction confirmed in a block.
Definition: fees.cpp:553
int returnedTarget
Definition: fees.h:81
static constexpr double MAX_BUCKET_FEERATE
Definition: fees.h:174
static constexpr double HALF_SUCCESS_PCT
Require greater than 60% of X feerate transactions to be confirmed within Y/2 blocks.
Definition: fees.h:155
size_t GetTxSize() const
Definition: txmempool.cpp:50
static constexpr unsigned int MED_BLOCK_PERIODS
Track confirm delays up to 48 blocks for medium horizon.
Definition: fees.h:139
double start
Definition: fees.h:59
bool removeTx(uint256 hash, bool inBlock)
Remove a transaction from the mempool tracking stats.
Definition: fees.cpp:477
CBlockPolicyEstimator()
Create new BlockPolicyEstimator and initialize stats tracking classes with default values...
Definition: fees.cpp:492
TxConfirmStats(const std::vector< double > &defaultBuckets, const std::map< double, unsigned int > &defaultBucketMap, unsigned int maxPeriods, double decay, unsigned int scale)
Create new TxConfirmStats.
Definition: fees.cpp:140
double estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Helper for estimateSmartFee.
Definition: fees.cpp:762
bool Write(CAutoFile &fileout) const
Write estimation data to a file.
Definition: fees.cpp:865
void FlushUnconfirmed()
Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool...
Definition: fees.cpp:950
std::vector< double > avg
Definition: fees.cpp:59
unsigned int HistoricalBlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Number of blocks of recorded fee estimate data represented in saved data file.
Definition: fees.cpp:703
FeeReason reason
Definition: fees.h:79
We will instantiate an instance of this class to track transactions that were included in a block...
Definition: fees.cpp:37
std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
Definition: fees.cpp:16
static constexpr double DOUBLE_SUCCESS_PCT
Require greater than 95% of X feerate transactions to be confirmed within 2 * Y blocks.
Definition: fees.h:159
static constexpr double FEE_SPACING
Spacing of FeeRate buckets We have to lump transactions into buckets based on feerate, but we want to be able to give accurate estimates over a large range of potential feerates Therefore it makes sense to exponentially space the buckets.
Definition: fees.h:181
CCriticalSection m_cs_fee_estimator
Definition: fees.h:227
unsigned int MaxUsableEstimate() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Calculation of highest target that reasonable estimate can be provided for.
Definition: fees.cpp:713
double decay
Definition: fees.cpp:64
void Record(int blocksToConfirm, double val)
Record a new transaction data point in the current block stats.
Definition: fees.cpp:182
static constexpr double MIN_BUCKET_FEERATE
Minimum and Maximum values for tracking feerates The MIN_BUCKET_FEERATE should just be set to the low...
Definition: fees.h:173
double withinTarget
Definition: fees.h:61
void resizeInMemoryCounters(size_t newbuckets)
Definition: fees.cpp:163
void ClearCurrent(unsigned int nBlockHeight)
Roll the circular buffer for unconfirmed txs.
Definition: fees.cpp:173
int desiredTarget
Definition: fees.h:80
static constexpr double SUFFICIENT_TXS_SHORT
Require an avg of 0.5 tx when using short decay since there are fewer blocks considered.
Definition: fees.h:164
CTxMemPoolEntry stores data about the corresponding transaction, as well as data about all in-mempool...
Definition: txmempool.h:66
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
static constexpr double SUCCESS_PCT
Require greater than 85% of X feerate transactions to be confirmed within Y blocks.
Definition: fees.h:157
void Read(CAutoFile &filein, int nFileVersion, size_t numBuckets)
Read saved state of estimation data from a file and replace all internal data structures and variable...
Definition: fees.cpp:371
const std::map< double, unsigned int > & bucketMap
Definition: fees.cpp:42
static constexpr unsigned int SHORT_SCALE
Definition: fees.h:137
static constexpr double LONG_DECAY
Decay of .9995 is a half-life of 1008 blocks or about 1 week.
Definition: fees.h:152
std::vector< std::vector< double > > confAvg
Definition: fees.cpp:51
unsigned int NewTx(unsigned int nBlockHeight, double val)
Record a new transaction entering the mempool.
Definition: fees.cpp:427
unsigned int GetHeight() const
Definition: txmempool.h:105
double end
Definition: fees.h:60
EstimatorBucket fail
Definition: fees.h:71
CFeeRate estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult *result=nullptr) const
Return a specific fee estimate calculation with a given success threshold and time horizon...
Definition: fees.cpp:638
#define LOCK(cs)
Definition: sync.h:182
void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketIndex, bool inBlock)
Remove a transaction from mempool tracking stats.
Definition: fees.cpp:435
const uint256 & GetHash() const
Definition: transaction.h:322
const CAmount & GetFee() const
Definition: txmempool.h:101
CFeeRate estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
Estimate feerate needed to get be included in a block within confTarget blocks.
Definition: fees.cpp:786
unsigned int scale
Definition: fees.cpp:67
const std::vector< double > & buckets
Definition: fees.cpp:41
unsigned int BlockSpan() const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Number of blocks of data recorded while fee estimates have been running.
Definition: fees.cpp:695
double inMempool
Definition: fees.h:63
double estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const EXCLUSIVE_LOCKS_REQUIRED(m_cs_fee_estimator)
Helper for estimateSmartFee.
Definition: fees.cpp:723
std::string ToString() const
Definition: uint256.cpp:62
FeeFilterRounder(const CFeeRate &minIncrementalFee)
Create new FeeFilterRounder.
Definition: fees.cpp:963
CFeeRate estimateFee(int confTarget) const
DEPRECATED.
Definition: fees.cpp:629
static constexpr unsigned int LONG_SCALE
Definition: fees.h:143
int64_t GetTimeMicros()
Returns the system time (not mockable)
Definition: time.cpp:62
FeeEstimateHorizon
Definition: fees.h:27
std::vector< std::vector< int > > unconfTxs
Definition: fees.cpp:72
unsigned int HighestTargetTracked(FeeEstimateHorizon horizon) const
Calculation of highest target that estimates are tracked for.
Definition: fees.cpp:676
256-bit opaque blob.
Definition: uint256.h:121
static constexpr unsigned int MED_SCALE
Definition: fees.h:140
static const unsigned int OLDEST_ESTIMATE_HISTORY
Historical estimates that are older than this aren&#39;t valid.
Definition: fees.h:145
std::vector< int > oldUnconfTxs
Definition: fees.cpp:74
void processBlock(unsigned int nBlockHeight, std::vector< const CTxMemPoolEntry *> &entries)
Process all the transactions that have been included in a block.
Definition: fees.cpp:580
const CTransaction & GetTx() const
Definition: txmempool.h:99
bool Read(CAutoFile &filein)
Read estimation data from a file.
Definition: fees.cpp:890
double leftMempool
Definition: fees.h:64
unsigned int GetMaxConfirms() const
Return the max number of confirms we&#39;re tracking.
Definition: fees.cpp:127
static constexpr unsigned int LONG_BLOCK_PERIODS
Track confirm delays up to 1008 blocks for long horizon.
Definition: fees.h:142
Fee rate in satoshis per kilobyte: CAmount / kB.
Definition: feerate.h:19
static constexpr unsigned int SHORT_BLOCK_PERIODS
Track confirm delays up to 12 blocks for short horizon.
Definition: fees.h:136
double totalConfirmed
Definition: fees.h:62
static constexpr double SUFFICIENT_FEETXS
Require an avg of 0.1 tx in the combined feerate bucket per block to have stat significance.
Definition: fees.h:162
CAmount round(CAmount currentMinFee)
Quantize a minimum fee for privacy purpose before broadcast.
Definition: fees.cpp:972
static constexpr double SHORT_DECAY
Decay of .962 is a half-life of 18 blocks or about 3 hours.
Definition: fees.h:148
double EstimateMedianVal(int confTarget, double sufficientTxVal, double minSuccess, bool requireGreater, unsigned int nBlockHeight, EstimationResult *result=nullptr) const
Calculate a feerate estimate.
Definition: fees.cpp:209
void Write(CAutoFile &fileout) const
Write state of estimation data to a file.
Definition: fees.cpp:361
std::vector< double > txCtAvg
Definition: fees.cpp:47
void UpdateMovingAverages()
Update our estimates by decaying our historical moving average and updating with the data gathered fr...
Definition: fees.cpp:196
unsigned int scale
Definition: fees.h:73
bool error(const char *fmt, const Args &... args)
Definition: system.h:61
CAmount GetFeePerK() const
Return the fee in satoshis for a size of 1000 bytes.
Definition: feerate.h:41
Non-refcounted RAII wrapper for FILE*.
Definition: streams.h:603
void processTransaction(const CTxMemPoolEntry &entry, bool validFeeEstimate)
Process a transaction accepted to the mempool.
Definition: fees.cpp:514
double decay
Definition: fees.h:72