]> Git Repo - VerusCoin.git/blob - src/policy/fees.cpp
Incorporate all Zcash updates through 2.0.7-3 in addition to PBaaS, reserves, etc.
[VerusCoin.git] / src / policy / fees.cpp
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 .
5
6 #include "policy/fees.h"
7
8 #include "amount.h"
9 #include "primitives/transaction.h"
10 #include "streams.h"
11 #include "txmempool.h"
12 #include "util.h"
13
14 void TxConfirmStats::Initialize(std::vector<double>& defaultBuckets,
15                                 unsigned int maxConfirms, double _decay, std::string _dataTypeString)
16 {
17     decay = _decay;
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;
23     }
24
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());
32     }
33
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());
39 }
40
41 // Zero out the data for the current block
42 void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
43 {
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;
49         curBlockTxCt[j] = 0;
50         curBlockVal[j] = 0;
51     }
52 }
53
54 unsigned int TxConfirmStats::FindBucketIndex(double val)
55 {
56     extern char ASSETCHAINS_SYMBOL[KOMODO_ASSETCHAIN_MAXLEN];
57     auto it = bucketMap.lower_bound(val);
58     if ( it != bucketMap.end() )
59     {
60         //static uint32_t counter;
61         //if ( counter++ < 1 )
62         //    fprintf(stderr,"%s FindBucketIndex violation: from val %f\n",ASSETCHAINS_SYMBOL,val);
63     }
64     return it->second;
65 }
66
67 void TxConfirmStats::Record(int blocksToConfirm, double val)
68 {
69     // blocksToConfirm is 1-based
70     if (blocksToConfirm < 1)
71         return;
72     unsigned int bucketindex = FindBucketIndex(val);
73     for (size_t i = blocksToConfirm; i <= curBlockConf.size(); i++) {
74         curBlockConf[i - 1][bucketindex]++;
75     }
76     curBlockTxCt[bucketindex]++;
77     curBlockVal[bucketindex] += val;
78 }
79
80 void TxConfirmStats::UpdateMovingAverages()
81 {
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];
87     }
88 }
89
90 // returns -1 on error conditions
91 double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
92                                          double successBreakPoint, bool requireGreater,
93                                          unsigned int nBlockHeight)
94 {
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
99
100     int maxbucketindex = buckets.size() - 1;
101
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;
108
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;
118
119     bool foundAnswer = false;
120     unsigned int bins = unconfTxs.size();
121
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);
136
137             // Check to see if we are no longer getting confirmed at the success rate
138             if (requireGreater && curPct < successBreakPoint)
139                 break;
140             if (!requireGreater && curPct > successBreakPoint)
141                 break;
142
143             // Otherwise update the cumulative stats, and the bucket variables
144             // and reset the counters
145             else {
146                 foundAnswer = true;
147                 nConf = 0;
148                 totalNum = 0;
149                 extraNum = 0;
150                 bestNearBucket = curNearBucket;
151                 bestFarBucket = curFarBucket;
152                 curNearBucket = bucket + step;
153             }
154         }
155     }
156
157     double median = -1;
158     double txSum = 0;
159
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++) {
167         txSum += txCtAvg[j];
168     }
169     if (foundAnswer && txSum != 0) {
170         txSum = txSum / 2;
171         for (unsigned int j = minBucket; j <= maxBucket; j++) {
172             if (txCtAvg[j] < txSum)
173                 txSum -= txCtAvg[j];
174             else { // we're in the right bucket
175                 median = avg[j] / txCtAvg[j];
176                 break;
177             }
178         }
179     }
180
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);
185
186     return median;
187 }
188
189 void TxConfirmStats::Write(CAutoFile& fileout)
190 {
191     fileout << decay;
192     fileout << buckets;
193     fileout << avg;
194     fileout << txCtAvg;
195     fileout << confAvg;
196 }
197
198 void TxConfirmStats::Read(CAutoFile& filein)
199 {
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;
205     double fileDecay;
206     size_t maxConfirms;
207     size_t numBuckets;
208
209     filein >> fileDecay;
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");
216     filein >> fileAvg;
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");
229     }
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
232     decay = fileDecay;
233     buckets = fileBuckets;
234     avg = fileAvg;
235     confAvg = fileConfAvg;
236     txCtAvg = fileTxCtAvg;
237     bucketMap.clear();
238
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());
244     }
245     curBlockTxCt.resize(buckets.size());
246     curBlockVal.resize(buckets.size());
247
248     unconfTxs.resize(maxConfirms);
249     for (unsigned int i = 0; i < maxConfirms; i++) {
250         unconfTxs[i].resize(buckets.size());
251     }
252     oldUnconfTxs.resize(buckets.size());
253
254     for (unsigned int i = 0; i < buckets.size(); i++)
255         bucketMap[buckets[i]] = i;
256
257     LogPrint("estimatefee", "Reading estimates: %u %s buckets counting confirms up to %u blocks\n",
258              numBuckets, dataTypeString, maxConfirms);
259 }
260
261 unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
262 {
263     unsigned int bucketindex = FindBucketIndex(val);
264     unsigned int blockIndex = nBlockHeight % unconfTxs.size();
265     unconfTxs[blockIndex][bucketindex]++;
266     LogPrint("estimatefee", "adding to %s", dataTypeString);
267     return bucketindex;
268 }
269
270 void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex)
271 {
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
275         blocksAgo = 0;
276     if (blocksAgo < 0) {
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
279     }
280
281     if (blocksAgo >= (int)unconfTxs.size()) {
282         if (oldUnconfTxs[bucketindex] > 0)
283             oldUnconfTxs[bucketindex]--;
284         else
285             LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
286                      bucketindex);
287     }
288     else {
289         unsigned int blockIndex = entryHeight % unconfTxs.size();
290         if (unconfTxs[blockIndex][bucketindex] > 0)
291             unconfTxs[blockIndex][bucketindex]--;
292         else
293             LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
294                      blockIndex, bucketindex);
295     }
296 }
297
298 void CBlockPolicyEstimator::removeTx(uint256 hash)
299 {
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());
304         return;
305     }
306     TxConfirmStats *stats = pos->second.stats;
307     unsigned int entryHeight = pos->second.blockHeight;
308     unsigned int bucketIndex = pos->second.bucketIndex;
309
310     if (stats != NULL)
311         stats->removeTx(entryHeight, nBestSeenHeight, bucketIndex);
312     mapMemPoolTxs.erase(hash);
313 }
314
315 CBlockPolicyEstimator::CBlockPolicyEstimator(const CFeeRate& _minRelayFee)
316     : nBestSeenHeight(0)
317 {
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);
322     }
323     feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "FeeRate");
324
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);
329     }
330     priStats.Initialize(vprilist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "Priority");
331
332     feeUnlikely = CFeeRate(0);
333     feeLikely = CFeeRate(INF_FEERATE);
334     priUnlikely = 0;
335     priLikely = INF_PRIORITY;
336 }
337
338 bool CBlockPolicyEstimator::isFeeDataPoint(const CFeeRate &fee, double pri)
339 {
340     if ((pri < minTrackedPriority && fee >= minTrackedFee) ||
341         (pri < priUnlikely && fee > feeLikely)) {
342         return true;
343     }
344     return false;
345 }
346
347 bool CBlockPolicyEstimator::isPriDataPoint(const CFeeRate &fee, double pri)
348 {
349     if ((fee < minTrackedFee && pri >= minTrackedPriority) ||
350         (fee < feeUnlikely && pri > priLikely)) {
351         return true;
352     }
353     return false;
354 }
355
356 void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate)
357 {
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());
363         return;
364     }
365
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.
369         return;
370     }
371
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)
375         return;
376
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
381         return;
382     }
383
384     // Fees are stored and reported as BTC-per-kb:
385     CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
386
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;
392
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);
398     }
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());
403     }
404     else {
405         LogPrint("estimatefee", "not adding");
406     }
407     LogPrint("estimatefee", "\n");
408 }
409
410 void CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry)
411 {
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
416         return;
417     }
418
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");
427         return;
428     }
429
430     // Fees are stored and reported as BTC-per-kb:
431     CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
432
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);
436
437     // Record this as a priority estimate
438     if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) {
439         priStats.Record(blocksToConfirm, curPri);
440     }
441     // Record this as a fee estimate
442     else if (isFeeDataPoint(feeRate, curPri)) {
443         feeStats.Record(blocksToConfirm, (double)feeRate.GetFeePerK());
444     }
445 }
446
447 void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
448                                          std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate)
449 {
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."
456         return;
457     }
458     nBestSeenHeight = nBlockHeight;
459
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)
463         return;
464
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);
470     if (priLikely == -1)
471         priLikely = INF_PRIORITY;
472
473     double feeLikelyEst = feeStats.EstimateMedianVal(2, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBlockHeight);
474     if (feeLikelyEst == -1)
475         feeLikely = CFeeRate(INF_FEERATE);
476     else
477         feeLikely = CFeeRate(feeLikelyEst);
478
479     priUnlikely = priStats.EstimateMedianVal(10, SUFFICIENT_PRITXS, UNLIKELY_PCT, false, nBlockHeight);
480     if (priUnlikely == -1)
481         priUnlikely = 0;
482
483     double feeUnlikelyEst = feeStats.EstimateMedianVal(10, SUFFICIENT_FEETXS, UNLIKELY_PCT, false, nBlockHeight);
484     if (feeUnlikelyEst == -1)
485         feeUnlikely = CFeeRate(0);
486     else
487         feeUnlikely = CFeeRate(feeUnlikelyEst);
488
489     // Clear the current block states
490     feeStats.ClearCurrent(nBlockHeight);
491     priStats.ClearCurrent(nBlockHeight);
492
493     // Repopulate the current block states
494     for (unsigned int i = 0; i < entries.size(); i++)
495         processBlockTx(nBlockHeight, entries[i]);
496
497     // Update all exponential averages with the current block states
498     feeStats.UpdateMovingAverages();
499     priStats.UpdateMovingAverages();
500
501     LogPrint("estimatefee", "Blockpolicy after updating estimates for %u confirmed entries, new mempool map size %u\n",
502              entries.size(), mapMemPoolTxs.size());
503 }
504
505 CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
506 {
507     // Return failure if trying to analyze a target we're not tracking
508     if (confTarget <= 0 || (unsigned int)confTarget > feeStats.GetMaxConfirms())
509         return CFeeRate(0);
510
511     double median = feeStats.EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
512
513     if (median < 0)
514         return CFeeRate(0);
515
516     return CFeeRate(median);
517 }
518
519 double CBlockPolicyEstimator::estimatePriority(int confTarget)
520 {
521     // Return failure if trying to analyze a target we're not tracking
522     if (confTarget <= 0 || (unsigned int)confTarget > priStats.GetMaxConfirms())
523         return -1;
524
525     return priStats.EstimateMedianVal(confTarget, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
526 }
527
528 void CBlockPolicyEstimator::Write(CAutoFile& fileout)
529 {
530     fileout << nBestSeenHeight;
531     feeStats.Write(fileout);
532     priStats.Write(fileout);
533 }
534
535 void CBlockPolicyEstimator::Read(CAutoFile& filein)
536 {
537     int nFileBestSeenHeight;
538     filein >> nFileBestSeenHeight;
539     feeStats.Read(filein);
540     priStats.Read(filein);
541     nBestSeenHeight = nFileBestSeenHeight;
542 }
This page took 0.055587 seconds and 4 git commands to generate.