1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2015 The Bitcoin developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or https://www.opensource.org/licenses/mit-license.php .
6 #include "policy/fees.h"
9 #include "primitives/transaction.h"
11 #include "txmempool.h"
14 void TxConfirmStats::Initialize(std::vector<double>& defaultBuckets,
15 unsigned int maxConfirms, double _decay, std::string _dataTypeString)
18 dataTypeString = _dataTypeString;
19 buckets.insert(buckets.end(), defaultBuckets.begin(), defaultBuckets.end());
20 buckets.push_back(std::numeric_limits<double>::infinity());
21 for (unsigned int i = 0; i < buckets.size(); i++) {
22 bucketMap[buckets[i]] = i;
25 confAvg.resize(maxConfirms);
26 curBlockConf.resize(maxConfirms);
27 unconfTxs.resize(maxConfirms);
28 for (unsigned int i = 0; i < maxConfirms; i++) {
29 confAvg[i].resize(buckets.size());
30 curBlockConf[i].resize(buckets.size());
31 unconfTxs[i].resize(buckets.size());
34 oldUnconfTxs.resize(buckets.size());
35 curBlockTxCt.resize(buckets.size());
36 txCtAvg.resize(buckets.size());
37 curBlockVal.resize(buckets.size());
38 avg.resize(buckets.size());
41 // Zero out the data for the current block
42 void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
44 for (unsigned int j = 0; j < buckets.size(); j++) {
45 oldUnconfTxs[j] += unconfTxs[nBlockHeight%unconfTxs.size()][j];
46 unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
47 for (unsigned int i = 0; i < curBlockConf.size(); i++)
48 curBlockConf[i][j] = 0;
54 unsigned int TxConfirmStats::FindBucketIndex(double val)
56 extern char ASSETCHAINS_SYMBOL[KOMODO_ASSETCHAIN_MAXLEN];
57 auto it = bucketMap.lower_bound(val);
58 if ( it != bucketMap.end() )
60 //static uint32_t counter;
61 //if ( counter++ < 1 )
62 // fprintf(stderr,"%s FindBucketIndex violation: from val %f\n",ASSETCHAINS_SYMBOL,val);
67 void TxConfirmStats::Record(int blocksToConfirm, double val)
69 // blocksToConfirm is 1-based
70 if (blocksToConfirm < 1)
72 unsigned int bucketindex = FindBucketIndex(val);
73 for (size_t i = blocksToConfirm; i <= curBlockConf.size(); i++) {
74 curBlockConf[i - 1][bucketindex]++;
76 curBlockTxCt[bucketindex]++;
77 curBlockVal[bucketindex] += val;
80 void TxConfirmStats::UpdateMovingAverages()
82 for (unsigned int j = 0; j < buckets.size(); j++) {
83 for (unsigned int i = 0; i < confAvg.size(); i++)
84 confAvg[i][j] = confAvg[i][j] * decay + curBlockConf[i][j];
85 avg[j] = avg[j] * decay + curBlockVal[j];
86 txCtAvg[j] = txCtAvg[j] * decay + curBlockTxCt[j];
90 // returns -1 on error conditions
91 double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
92 double successBreakPoint, bool requireGreater,
93 unsigned int nBlockHeight)
95 // Counters for a bucket (or range of buckets)
96 double nConf = 0; // Number of tx's confirmed within the confTarget
97 double totalNum = 0; // Total number of tx's that were ever confirmed
98 int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
100 int maxbucketindex = buckets.size() - 1;
102 // requireGreater means we are looking for the lowest fee/priority such that all higher
103 // values pass, so we start at maxbucketindex (highest fee) and look at succesively
104 // smaller buckets until we reach failure. Otherwise, we are looking for the highest
105 // fee/priority such that all lower values fail, and we go in the opposite direction.
106 unsigned int startbucket = requireGreater ? maxbucketindex : 0;
107 int step = requireGreater ? -1 : 1;
109 // We'll combine buckets until we have enough samples.
110 // The near and far variables will define the range we've combined
111 // The best variables are the last range we saw which still had a high
112 // enough confirmation rate to count as success.
113 // The cur variables are the current range we're counting.
114 unsigned int curNearBucket = startbucket;
115 unsigned int bestNearBucket = startbucket;
116 unsigned int curFarBucket = startbucket;
117 unsigned int bestFarBucket = startbucket;
119 bool foundAnswer = false;
120 unsigned int bins = unconfTxs.size();
122 // Start counting from highest(default) or lowest fee/pri transactions
123 for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) {
124 curFarBucket = bucket;
125 nConf += confAvg[confTarget - 1][bucket];
126 totalNum += txCtAvg[bucket];
127 for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
128 extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket];
129 extraNum += oldUnconfTxs[bucket];
130 // If we have enough transaction data points in this range of buckets,
131 // we can test for success
132 // (Only count the confirmed data points, so that each confirmation count
133 // will be looking at the same amount of data and same bucket breaks)
134 if (totalNum >= sufficientTxVal / (1 - decay)) {
135 double curPct = nConf / (totalNum + extraNum);
137 // Check to see if we are no longer getting confirmed at the success rate
138 if (requireGreater && curPct < successBreakPoint)
140 if (!requireGreater && curPct > successBreakPoint)
143 // Otherwise update the cumulative stats, and the bucket variables
144 // and reset the counters
150 bestNearBucket = curNearBucket;
151 bestFarBucket = curFarBucket;
152 curNearBucket = bucket + step;
160 // Calculate the "average" fee of the best bucket range that met success conditions
161 // Find the bucket with the median transaction and then report the average fee from that bucket
162 // This is a compromise between finding the median which we can't since we don't save all tx's
163 // and reporting the average which is less accurate
164 unsigned int minBucket = bestNearBucket < bestFarBucket ? bestNearBucket : bestFarBucket;
165 unsigned int maxBucket = bestNearBucket > bestFarBucket ? bestNearBucket : bestFarBucket;
166 for (unsigned int j = minBucket; j <= maxBucket; j++) {
169 if (foundAnswer && txSum != 0) {
171 for (unsigned int j = minBucket; j <= maxBucket; j++) {
172 if (txCtAvg[j] < txSum)
174 else { // we're in the right bucket
175 median = avg[j] / txCtAvg[j];
181 LogPrint("estimatefee", "%3d: For conf success %s %4.2f need %s %s: %12.5g from buckets %8g - %8g Cur Bucket stats %6.2f%% %8.1f/(%.1f+%d mempool)\n",
182 confTarget, requireGreater ? ">" : "<", successBreakPoint, dataTypeString,
183 requireGreater ? ">" : "<", median, buckets[minBucket], buckets[maxBucket],
184 100 * nConf / (totalNum + extraNum), nConf, totalNum, extraNum);
189 void TxConfirmStats::Write(CAutoFile& fileout)
198 void TxConfirmStats::Read(CAutoFile& filein)
200 // Read data file into temporary variables and do some very basic sanity checking
201 std::vector<double> fileBuckets;
202 std::vector<double> fileAvg;
203 std::vector<std::vector<double> > fileConfAvg;
204 std::vector<double> fileTxCtAvg;
210 if (fileDecay <= 0 || fileDecay >= 1)
211 throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
212 filein >> fileBuckets;
213 numBuckets = fileBuckets.size();
214 if (numBuckets <= 1 || numBuckets > 1000)
215 throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 fee/pri buckets");
217 if (fileAvg.size() != numBuckets)
218 throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri average bucket count");
219 filein >> fileTxCtAvg;
220 if (fileTxCtAvg.size() != numBuckets)
221 throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
222 filein >> fileConfAvg;
223 maxConfirms = fileConfAvg.size();
224 if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) // one week
225 throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
226 for (unsigned int i = 0; i < maxConfirms; i++) {
227 if (fileConfAvg[i].size() != numBuckets)
228 throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri conf average bucket count");
230 // Now that we've processed the entire fee estimate data file and not
231 // thrown any errors, we can copy it to our data structures
233 buckets = fileBuckets;
235 confAvg = fileConfAvg;
236 txCtAvg = fileTxCtAvg;
239 // Resize the current block variables which aren't stored in the data file
240 // to match the number of confirms and buckets
241 curBlockConf.resize(maxConfirms);
242 for (unsigned int i = 0; i < maxConfirms; i++) {
243 curBlockConf[i].resize(buckets.size());
245 curBlockTxCt.resize(buckets.size());
246 curBlockVal.resize(buckets.size());
248 unconfTxs.resize(maxConfirms);
249 for (unsigned int i = 0; i < maxConfirms; i++) {
250 unconfTxs[i].resize(buckets.size());
252 oldUnconfTxs.resize(buckets.size());
254 for (unsigned int i = 0; i < buckets.size(); i++)
255 bucketMap[buckets[i]] = i;
257 LogPrint("estimatefee", "Reading estimates: %u %s buckets counting confirms up to %u blocks\n",
258 numBuckets, dataTypeString, maxConfirms);
261 unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
263 unsigned int bucketindex = FindBucketIndex(val);
264 unsigned int blockIndex = nBlockHeight % unconfTxs.size();
265 unconfTxs[blockIndex][bucketindex]++;
266 LogPrint("estimatefee", "adding to %s", dataTypeString);
270 void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex)
272 //nBestSeenHeight is not updated yet for the new block
273 int blocksAgo = nBestSeenHeight - entryHeight;
274 if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
277 LogPrint("estimatefee", "Blockpolicy error, blocks ago is negative for mempool tx\n");
278 return; //This can't happen because we call this with our best seen height, no entries can have higher
281 if (blocksAgo >= (int)unconfTxs.size()) {
282 if (oldUnconfTxs[bucketindex] > 0)
283 oldUnconfTxs[bucketindex]--;
285 LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
289 unsigned int blockIndex = entryHeight % unconfTxs.size();
290 if (unconfTxs[blockIndex][bucketindex] > 0)
291 unconfTxs[blockIndex][bucketindex]--;
293 LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
294 blockIndex, bucketindex);
298 void CBlockPolicyEstimator::removeTx(uint256 hash)
300 std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
301 if (pos == mapMemPoolTxs.end()) {
302 LogPrint("estimatefee", "Blockpolicy error mempool tx %s not found for removeTx\n",
303 hash.ToString().c_str());
306 TxConfirmStats *stats = pos->second.stats;
307 unsigned int entryHeight = pos->second.blockHeight;
308 unsigned int bucketIndex = pos->second.bucketIndex;
311 stats->removeTx(entryHeight, nBestSeenHeight, bucketIndex);
312 mapMemPoolTxs.erase(hash);
315 CBlockPolicyEstimator::CBlockPolicyEstimator(const CFeeRate& _minRelayFee)
318 minTrackedFee = _minRelayFee < CFeeRate(MIN_FEERATE) ? CFeeRate(MIN_FEERATE) : _minRelayFee;
319 std::vector<double> vfeelist;
320 for (double bucketBoundary = minTrackedFee.GetFeePerK(); bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) {
321 vfeelist.push_back(bucketBoundary);
323 feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "FeeRate");
325 minTrackedPriority = AllowFreeThreshold() < MIN_PRIORITY ? MIN_PRIORITY : AllowFreeThreshold();
326 std::vector<double> vprilist;
327 for (double bucketBoundary = minTrackedPriority; bucketBoundary <= MAX_PRIORITY; bucketBoundary *= PRI_SPACING) {
328 vprilist.push_back(bucketBoundary);
330 priStats.Initialize(vprilist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "Priority");
332 feeUnlikely = CFeeRate(0);
333 feeLikely = CFeeRate(INF_FEERATE);
335 priLikely = INF_PRIORITY;
338 bool CBlockPolicyEstimator::isFeeDataPoint(const CFeeRate &fee, double pri)
340 if ((pri < minTrackedPriority && fee >= minTrackedFee) ||
341 (pri < priUnlikely && fee > feeLikely)) {
347 bool CBlockPolicyEstimator::isPriDataPoint(const CFeeRate &fee, double pri)
349 if ((fee < minTrackedFee && pri >= minTrackedPriority) ||
350 (fee < feeUnlikely && pri > priLikely)) {
356 void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate)
358 unsigned int txHeight = entry.GetHeight();
359 uint256 hash = entry.GetTx().GetHash();
360 if (mapMemPoolTxs[hash].stats != NULL) {
361 LogPrint("estimatefee", "Blockpolicy error mempool tx %s already being tracked\n",
362 hash.ToString().c_str());
366 if (txHeight < nBestSeenHeight) {
367 // Ignore side chains and re-orgs; assuming they are random they don't
368 // affect the estimate. We'll potentially double count transactions in 1-block reorgs.
372 // Only want to be updating estimates when our blockchain is synced,
373 // otherwise we'll miscalculate how many blocks its taking to get included.
374 if (!fCurrentEstimate)
377 if (!entry.WasClearAtEntry()) {
378 // This transaction depends on other transactions in the mempool to
379 // be included in a block before it will be able to be included, so
380 // we shouldn't include it in our calculations
384 // Fees are stored and reported as BTC-per-kb:
385 CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
387 // Want the priority of the tx at confirmation. However we don't know
388 // what that will be and its too hard to continue updating it
389 // so use starting priority as a proxy
390 double curPri = entry.GetPriority(txHeight);
391 mapMemPoolTxs[hash].blockHeight = txHeight;
393 LogPrint("estimatefee", "Blockpolicy mempool tx %s ", hash.ToString().substr(0,10));
394 // Record this as a priority estimate
395 if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) {
396 mapMemPoolTxs[hash].stats = &priStats;
397 mapMemPoolTxs[hash].bucketIndex = priStats.NewTx(txHeight, curPri);
399 // Record this as a fee estimate
400 else if (isFeeDataPoint(feeRate, curPri)) {
401 mapMemPoolTxs[hash].stats = &feeStats;
402 mapMemPoolTxs[hash].bucketIndex = feeStats.NewTx(txHeight, (double)feeRate.GetFeePerK());
405 LogPrint("estimatefee", "not adding");
407 LogPrint("estimatefee", "\n");
410 void CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry)
412 if (!entry.WasClearAtEntry()) {
413 // This transaction depended on other transactions in the mempool to
414 // be included in a block before it was able to be included, so
415 // we shouldn't include it in our calculations
419 // How many blocks did it take for miners to include this transaction?
420 // blocksToConfirm is 1-based, so a transaction included in the earliest
421 // possible block has confirmation count of 1
422 int blocksToConfirm = nBlockHeight - entry.GetHeight();
423 if (blocksToConfirm <= 0) {
424 // This can't happen because we don't process transactions from a block with a height
425 // lower than our greatest seen height
426 LogPrint("estimatefee", "Blockpolicy error Transaction had negative blocksToConfirm\n");
430 // Fees are stored and reported as BTC-per-kb:
431 CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
433 // Want the priority of the tx at confirmation. The priority when it
434 // entered the mempool could easily be very small and change quickly
435 double curPri = entry.GetPriority(nBlockHeight);
437 // Record this as a priority estimate
438 if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) {
439 priStats.Record(blocksToConfirm, curPri);
441 // Record this as a fee estimate
442 else if (isFeeDataPoint(feeRate, curPri)) {
443 feeStats.Record(blocksToConfirm, (double)feeRate.GetFeePerK());
447 void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
448 std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate)
450 if (nBlockHeight <= nBestSeenHeight) {
451 // Ignore side chains and re-orgs; assuming they are random
452 // they don't affect the estimate.
453 // And if an attacker can re-org the chain at will, then
454 // you've got much bigger problems than "attacker can influence
455 // transaction fees."
458 nBestSeenHeight = nBlockHeight;
460 // Only want to be updating estimates when our blockchain is synced,
461 // otherwise we'll miscalculate how many blocks its taking to get included.
462 if (!fCurrentEstimate)
465 // Update the dynamic cutoffs
466 // a fee/priority is "likely" the reason your tx was included in a block if >85% of such tx's
467 // were confirmed in 2 blocks and is "unlikely" if <50% were confirmed in 10 blocks
468 LogPrint("estimatefee", "Blockpolicy recalculating dynamic cutoffs:\n");
469 priLikely = priStats.EstimateMedianVal(2, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBlockHeight);
471 priLikely = INF_PRIORITY;
473 double feeLikelyEst = feeStats.EstimateMedianVal(2, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBlockHeight);
474 if (feeLikelyEst == -1)
475 feeLikely = CFeeRate(INF_FEERATE);
477 feeLikely = CFeeRate(feeLikelyEst);
479 priUnlikely = priStats.EstimateMedianVal(10, SUFFICIENT_PRITXS, UNLIKELY_PCT, false, nBlockHeight);
480 if (priUnlikely == -1)
483 double feeUnlikelyEst = feeStats.EstimateMedianVal(10, SUFFICIENT_FEETXS, UNLIKELY_PCT, false, nBlockHeight);
484 if (feeUnlikelyEst == -1)
485 feeUnlikely = CFeeRate(0);
487 feeUnlikely = CFeeRate(feeUnlikelyEst);
489 // Clear the current block states
490 feeStats.ClearCurrent(nBlockHeight);
491 priStats.ClearCurrent(nBlockHeight);
493 // Repopulate the current block states
494 for (unsigned int i = 0; i < entries.size(); i++)
495 processBlockTx(nBlockHeight, entries[i]);
497 // Update all exponential averages with the current block states
498 feeStats.UpdateMovingAverages();
499 priStats.UpdateMovingAverages();
501 LogPrint("estimatefee", "Blockpolicy after updating estimates for %u confirmed entries, new mempool map size %u\n",
502 entries.size(), mapMemPoolTxs.size());
505 CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
507 // Return failure if trying to analyze a target we're not tracking
508 if (confTarget <= 0 || (unsigned int)confTarget > feeStats.GetMaxConfirms())
511 double median = feeStats.EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
516 return CFeeRate(median);
519 double CBlockPolicyEstimator::estimatePriority(int confTarget)
521 // Return failure if trying to analyze a target we're not tracking
522 if (confTarget <= 0 || (unsigned int)confTarget > priStats.GetMaxConfirms())
525 return priStats.EstimateMedianVal(confTarget, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
528 void CBlockPolicyEstimator::Write(CAutoFile& fileout)
530 fileout << nBestSeenHeight;
531 feeStats.Write(fileout);
532 priStats.Write(fileout);
535 void CBlockPolicyEstimator::Read(CAutoFile& filein)
537 int nFileBestSeenHeight;
538 filein >> nFileBestSeenHeight;
539 feeStats.Read(filein);
540 priStats.Read(filein);
541 nBestSeenHeight = nFileBestSeenHeight;