diff options
Diffstat (limited to 'src/policy')
| -rw-r--r-- | src/policy/fees.cpp | 529 | ||||
| -rw-r--r-- | src/policy/fees.h | 276 |
2 files changed, 805 insertions, 0 deletions
diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp new file mode 100644 index 0000000000..b1491cec01 --- /dev/null +++ b/src/policy/fees.cpp @@ -0,0 +1,529 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2015 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "policy/fees.h" + +#include "amount.h" +#include "primitives/transaction.h" +#include "streams.h" +#include "txmempool.h" +#include "util.h" + +void TxConfirmStats::Initialize(std::vector<double>& defaultBuckets, + unsigned int maxConfirms, double _decay, std::string _dataTypeString) +{ + decay = _decay; + dataTypeString = _dataTypeString; + for (unsigned int i = 0; i < defaultBuckets.size(); i++) { + buckets.push_back(defaultBuckets[i]); + bucketMap[defaultBuckets[i]] = i; + } + confAvg.resize(maxConfirms); + curBlockConf.resize(maxConfirms); + unconfTxs.resize(maxConfirms); + for (unsigned int i = 0; i < maxConfirms; i++) { + confAvg[i].resize(buckets.size()); + curBlockConf[i].resize(buckets.size()); + unconfTxs[i].resize(buckets.size()); + } + + oldUnconfTxs.resize(buckets.size()); + curBlockTxCt.resize(buckets.size()); + txCtAvg.resize(buckets.size()); + curBlockVal.resize(buckets.size()); + avg.resize(buckets.size()); +} + +// Zero out the data for the current block +void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight) +{ + for (unsigned int j = 0; j < buckets.size(); j++) { + oldUnconfTxs[j] += unconfTxs[nBlockHeight%unconfTxs.size()][j]; + unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0; + for (unsigned int i = 0; i < curBlockConf.size(); i++) + curBlockConf[i][j] = 0; + curBlockTxCt[j] = 0; + curBlockVal[j] = 0; + } +} + + +void TxConfirmStats::Record(int blocksToConfirm, double val) +{ + // blocksToConfirm is 1-based + if (blocksToConfirm < 1) + return; + unsigned int bucketindex = bucketMap.lower_bound(val)->second; + for (size_t i = blocksToConfirm; i <= curBlockConf.size(); i++) { + curBlockConf[i - 1][bucketindex]++; + } + curBlockTxCt[bucketindex]++; + curBlockVal[bucketindex] += val; +} + +void TxConfirmStats::UpdateMovingAverages() +{ + for (unsigned int j = 0; j < buckets.size(); j++) { + for (unsigned int i = 0; i < confAvg.size(); i++) + confAvg[i][j] = confAvg[i][j] * decay + curBlockConf[i][j]; + avg[j] = avg[j] * decay + curBlockVal[j]; + txCtAvg[j] = txCtAvg[j] * decay + curBlockTxCt[j]; + } +} + +// returns -1 on error conditions +double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, + double successBreakPoint, bool requireGreater, + unsigned int nBlockHeight) +{ + // Counters for a bucket (or range of buckets) + double nConf = 0; // Number of tx's confirmed within the confTarget + double totalNum = 0; // Total number of tx's that were ever confirmed + int extraNum = 0; // Number of tx's still in mempool for confTarget or longer + + int maxbucketindex = buckets.size() - 1; + + // requireGreater means we are looking for the lowest fee/priority such that all higher + // values pass, so we start at maxbucketindex (highest fee) and look at succesively + // smaller buckets until we reach failure. Otherwise, we are looking for the highest + // fee/priority such that all lower values fail, and we go in the opposite direction. + unsigned int startbucket = requireGreater ? maxbucketindex : 0; + int step = requireGreater ? -1 : 1; + + // We'll combine buckets until we have enough samples. + // The near and far variables will define the range we've combined + // The best variables are the last range we saw which still had a high + // enough confirmation rate to count as success. + // The cur variables are the current range we're counting. + unsigned int curNearBucket = startbucket; + unsigned int bestNearBucket = startbucket; + unsigned int curFarBucket = startbucket; + unsigned int bestFarBucket = startbucket; + + bool foundAnswer = false; + unsigned int bins = unconfTxs.size(); + + // Start counting from highest(default) or lowest fee/pri transactions + for (int bucket = startbucket; bucket >= 0 && bucket <= maxbucketindex; bucket += step) { + curFarBucket = bucket; + nConf += confAvg[confTarget - 1][bucket]; + totalNum += txCtAvg[bucket]; + for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++) + extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket]; + extraNum += oldUnconfTxs[bucket]; + // If we have enough transaction data points in this range of buckets, + // we can test for success + // (Only count the confirmed data points, so that each confirmation count + // will be looking at the same amount of data and same bucket breaks) + if (totalNum >= sufficientTxVal / (1 - decay)) { + double curPct = nConf / (totalNum + extraNum); + + // Check to see if we are no longer getting confirmed at the success rate + if (requireGreater && curPct < successBreakPoint) + break; + if (!requireGreater && curPct > successBreakPoint) + break; + + // Otherwise update the cumulative stats, and the bucket variables + // and reset the counters + else { + foundAnswer = true; + nConf = 0; + totalNum = 0; + extraNum = 0; + bestNearBucket = curNearBucket; + bestFarBucket = curFarBucket; + curNearBucket = bucket + step; + } + } + } + + double median = -1; + double txSum = 0; + + // Calculate the "average" fee of the best bucket range that met success conditions + // Find the bucket with the median transaction and then report the average fee from that bucket + // This is a compromise between finding the median which we can't since we don't save all tx's + // and reporting the average which is less accurate + unsigned int minBucket = bestNearBucket < bestFarBucket ? bestNearBucket : bestFarBucket; + unsigned int maxBucket = bestNearBucket > bestFarBucket ? bestNearBucket : bestFarBucket; + for (unsigned int j = minBucket; j <= maxBucket; j++) { + txSum += txCtAvg[j]; + } + if (foundAnswer && txSum != 0) { + txSum = txSum / 2; + for (unsigned int j = minBucket; j <= maxBucket; j++) { + if (txCtAvg[j] < txSum) + txSum -= txCtAvg[j]; + else { // we're in the right bucket + median = avg[j] / txCtAvg[j]; + break; + } + } + } + + 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", + confTarget, requireGreater ? ">" : "<", successBreakPoint, dataTypeString, + requireGreater ? ">" : "<", median, buckets[minBucket], buckets[maxBucket], + 100 * nConf / (totalNum + extraNum), nConf, totalNum, extraNum); + + return median; +} + +void TxConfirmStats::Write(CAutoFile& fileout) +{ + fileout << decay; + fileout << buckets; + fileout << avg; + fileout << txCtAvg; + fileout << confAvg; +} + +void TxConfirmStats::Read(CAutoFile& filein) +{ + // Read data file into temporary variables and do some very basic sanity checking + std::vector<double> fileBuckets; + std::vector<double> fileAvg; + std::vector<std::vector<double> > fileConfAvg; + std::vector<double> fileTxCtAvg; + double fileDecay; + size_t maxConfirms; + size_t numBuckets; + + filein >> fileDecay; + if (fileDecay <= 0 || fileDecay >= 1) + throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)"); + filein >> fileBuckets; + numBuckets = fileBuckets.size(); + if (numBuckets <= 1 || numBuckets > 1000) + throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 fee/pri buckets"); + filein >> fileAvg; + if (fileAvg.size() != numBuckets) + throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri average bucket count"); + filein >> fileTxCtAvg; + if (fileTxCtAvg.size() != numBuckets) + throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count"); + filein >> fileConfAvg; + maxConfirms = fileConfAvg.size(); + if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) // one week + throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms"); + for (unsigned int i = 0; i < maxConfirms; i++) { + if (fileConfAvg[i].size() != numBuckets) + throw std::runtime_error("Corrupt estimates file. Mismatch in fee/pri conf average bucket count"); + } + // Now that we've processed the entire fee estimate data file and not + // thrown any errors, we can copy it to our data structures + decay = fileDecay; + buckets = fileBuckets; + avg = fileAvg; + confAvg = fileConfAvg; + txCtAvg = fileTxCtAvg; + bucketMap.clear(); + + // Resize the current block variables which aren't stored in the data file + // to match the number of confirms and buckets + curBlockConf.resize(maxConfirms); + for (unsigned int i = 0; i < maxConfirms; i++) { + curBlockConf[i].resize(buckets.size()); + } + curBlockTxCt.resize(buckets.size()); + curBlockVal.resize(buckets.size()); + + unconfTxs.resize(maxConfirms); + for (unsigned int i = 0; i < maxConfirms; i++) { + unconfTxs[i].resize(buckets.size()); + } + oldUnconfTxs.resize(buckets.size()); + + for (unsigned int i = 0; i < buckets.size(); i++) + bucketMap[buckets[i]] = i; + + LogPrint("estimatefee", "Reading estimates: %u %s buckets counting confirms up to %u blocks\n", + numBuckets, dataTypeString, maxConfirms); +} + +unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val) +{ + unsigned int bucketindex = bucketMap.lower_bound(val)->second; + unsigned int blockIndex = nBlockHeight % unconfTxs.size(); + unconfTxs[blockIndex][bucketindex]++; + LogPrint("estimatefee", "adding to %s\n", dataTypeString); + return bucketindex; +} + +void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex) +{ + //nBestSeenHeight is not updated yet for the new block + int blocksAgo = nBestSeenHeight - entryHeight; + if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet + blocksAgo = 0; + if (blocksAgo < 0) { + LogPrint("estimatefee", "Blockpolicy error, blocks ago is negative for mempool tx\n"); + return; //This can't happen becasue we call this with our best seen height, no entries can have higher + } + + if (blocksAgo >= (int)unconfTxs.size()) { + if (oldUnconfTxs[bucketindex] > 0) + oldUnconfTxs[bucketindex]--; + else + LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n", + bucketindex); + } + else { + unsigned int blockIndex = entryHeight % unconfTxs.size(); + if (unconfTxs[blockIndex][bucketindex] > 0) + unconfTxs[blockIndex][bucketindex]--; + else + LogPrint("estimatefee", "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n", + blockIndex, bucketindex); + } +} + +void CBlockPolicyEstimator::removeTx(uint256 hash) +{ + std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash); + if (pos == mapMemPoolTxs.end()) { + LogPrint("estimatefee", "Blockpolicy error mempool tx %s not found for removeTx\n", + hash.ToString().c_str()); + return; + } + TxConfirmStats *stats = pos->second.stats; + unsigned int entryHeight = pos->second.blockHeight; + unsigned int bucketIndex = pos->second.bucketIndex; + + if (stats != NULL) + stats->removeTx(entryHeight, nBestSeenHeight, bucketIndex); + mapMemPoolTxs.erase(hash); +} + +CBlockPolicyEstimator::CBlockPolicyEstimator(const CFeeRate& _minRelayFee) + : nBestSeenHeight(0) +{ + minTrackedFee = _minRelayFee < CFeeRate(MIN_FEERATE) ? CFeeRate(MIN_FEERATE) : _minRelayFee; + std::vector<double> vfeelist; + for (double bucketBoundary = minTrackedFee.GetFeePerK(); bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) { + vfeelist.push_back(bucketBoundary); + } + vfeelist.push_back(INF_FEERATE); + feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "FeeRate"); + + minTrackedPriority = AllowFreeThreshold() < MIN_PRIORITY ? MIN_PRIORITY : AllowFreeThreshold(); + std::vector<double> vprilist; + for (double bucketBoundary = minTrackedPriority; bucketBoundary <= MAX_PRIORITY; bucketBoundary *= PRI_SPACING) { + vprilist.push_back(bucketBoundary); + } + vprilist.push_back(INF_PRIORITY); + priStats.Initialize(vprilist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY, "Priority"); + + feeUnlikely = CFeeRate(0); + feeLikely = CFeeRate(INF_FEERATE); + priUnlikely = 0; + priLikely = INF_PRIORITY; +} + +bool CBlockPolicyEstimator::isFeeDataPoint(const CFeeRate &fee, double pri) +{ + if ((pri < minTrackedPriority && fee >= minTrackedFee) || + (pri < priUnlikely && fee > feeLikely)) { + return true; + } + return false; +} + +bool CBlockPolicyEstimator::isPriDataPoint(const CFeeRate &fee, double pri) +{ + if ((fee < minTrackedFee && pri >= minTrackedPriority) || + (fee < feeUnlikely && pri > priLikely)) { + return true; + } + return false; +} + +void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate) +{ + unsigned int txHeight = entry.GetHeight(); + uint256 hash = entry.GetTx().GetHash(); + if (mapMemPoolTxs[hash].stats != NULL) { + LogPrint("estimatefee", "Blockpolicy error mempool tx %s already being tracked\n", + hash.ToString().c_str()); + return; + } + + if (txHeight < nBestSeenHeight) { + // Ignore side chains and re-orgs; assuming they are random they don't + // affect the estimate. We'll potentially double count transactions in 1-block reorgs. + return; + } + + // Only want to be updating estimates when our blockchain is synced, + // otherwise we'll miscalculate how many blocks its taking to get included. + if (!fCurrentEstimate) + return; + + if (!entry.WasClearAtEntry()) { + // This transaction depends on other transactions in the mempool to + // be included in a block before it will be able to be included, so + // we shouldn't include it in our calculations + return; + } + + // Fees are stored and reported as BTC-per-kb: + CFeeRate feeRate(entry.GetFee(), entry.GetTxSize()); + + // Want the priority of the tx at confirmation. However we don't know + // what that will be and its too hard to continue updating it + // so use starting priority as a proxy + double curPri = entry.GetPriority(txHeight); + mapMemPoolTxs[hash].blockHeight = txHeight; + + LogPrint("estimatefee", "Blockpolicy mempool tx %s ", hash.ToString().substr(0,10)); + // Record this as a priority estimate + if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) { + mapMemPoolTxs[hash].stats = &priStats; + mapMemPoolTxs[hash].bucketIndex = priStats.NewTx(txHeight, curPri); + } + // Record this as a fee estimate + else if (isFeeDataPoint(feeRate, curPri)) { + mapMemPoolTxs[hash].stats = &feeStats; + mapMemPoolTxs[hash].bucketIndex = feeStats.NewTx(txHeight, (double)feeRate.GetFeePerK()); + } + else { + LogPrint("estimatefee", "not adding\n"); + } +} + +void CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry) +{ + if (!entry.WasClearAtEntry()) { + // This transaction depended on other transactions in the mempool to + // be included in a block before it was able to be included, so + // we shouldn't include it in our calculations + return; + } + + // How many blocks did it take for miners to include this transaction? + // blocksToConfirm is 1-based, so a transaction included in the earliest + // possible block has confirmation count of 1 + int blocksToConfirm = nBlockHeight - entry.GetHeight(); + if (blocksToConfirm <= 0) { + // This can't happen because we don't process transactions from a block with a height + // lower than our greatest seen height + LogPrint("estimatefee", "Blockpolicy error Transaction had negative blocksToConfirm\n"); + return; + } + + // Fees are stored and reported as BTC-per-kb: + CFeeRate feeRate(entry.GetFee(), entry.GetTxSize()); + + // Want the priority of the tx at confirmation. The priority when it + // entered the mempool could easily be very small and change quickly + double curPri = entry.GetPriority(nBlockHeight); + + // Record this as a priority estimate + if (entry.GetFee() == 0 || isPriDataPoint(feeRate, curPri)) { + priStats.Record(blocksToConfirm, curPri); + } + // Record this as a fee estimate + else if (isFeeDataPoint(feeRate, curPri)) { + feeStats.Record(blocksToConfirm, (double)feeRate.GetFeePerK()); + } +} + +void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight, + std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate) +{ + if (nBlockHeight <= nBestSeenHeight) { + // Ignore side chains and re-orgs; assuming they are random + // they don't affect the estimate. + // And if an attacker can re-org the chain at will, then + // you've got much bigger problems than "attacker can influence + // transaction fees." + return; + } + nBestSeenHeight = nBlockHeight; + + // Only want to be updating estimates when our blockchain is synced, + // otherwise we'll miscalculate how many blocks its taking to get included. + if (!fCurrentEstimate) + return; + + // Update the dynamic cutoffs + // a fee/priority is "likely" the reason your tx was included in a block if >85% of such tx's + // were confirmed in 2 blocks and is "unlikely" if <50% were confirmed in 10 blocks + LogPrint("estimatefee", "Blockpolicy recalculating dynamic cutoffs:\n"); + priLikely = priStats.EstimateMedianVal(2, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBlockHeight); + if (priLikely == -1) + priLikely = INF_PRIORITY; + + double feeLikelyEst = feeStats.EstimateMedianVal(2, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBlockHeight); + if (feeLikelyEst == -1) + feeLikely = CFeeRate(INF_FEERATE); + else + feeLikely = CFeeRate(feeLikelyEst); + + priUnlikely = priStats.EstimateMedianVal(10, SUFFICIENT_PRITXS, UNLIKELY_PCT, false, nBlockHeight); + if (priUnlikely == -1) + priUnlikely = 0; + + double feeUnlikelyEst = feeStats.EstimateMedianVal(10, SUFFICIENT_FEETXS, UNLIKELY_PCT, false, nBlockHeight); + if (feeUnlikelyEst == -1) + feeUnlikely = CFeeRate(0); + else + feeUnlikely = CFeeRate(feeUnlikelyEst); + + // Clear the current block states + feeStats.ClearCurrent(nBlockHeight); + priStats.ClearCurrent(nBlockHeight); + + // Repopulate the current block states + for (unsigned int i = 0; i < entries.size(); i++) + processBlockTx(nBlockHeight, entries[i]); + + // Update all exponential averages with the current block states + feeStats.UpdateMovingAverages(); + priStats.UpdateMovingAverages(); + + LogPrint("estimatefee", "Blockpolicy after updating estimates for %u confirmed entries, new mempool map size %u\n", + entries.size(), mapMemPoolTxs.size()); +} + +CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) +{ + // Return failure if trying to analyze a target we're not tracking + if (confTarget <= 0 || (unsigned int)confTarget > feeStats.GetMaxConfirms()) + return CFeeRate(0); + + double median = feeStats.EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight); + + if (median < 0) + return CFeeRate(0); + + return CFeeRate(median); +} + +double CBlockPolicyEstimator::estimatePriority(int confTarget) +{ + // Return failure if trying to analyze a target we're not tracking + if (confTarget <= 0 || (unsigned int)confTarget > priStats.GetMaxConfirms()) + return -1; + + return priStats.EstimateMedianVal(confTarget, SUFFICIENT_PRITXS, MIN_SUCCESS_PCT, true, nBestSeenHeight); +} + +void CBlockPolicyEstimator::Write(CAutoFile& fileout) +{ + fileout << nBestSeenHeight; + feeStats.Write(fileout); + priStats.Write(fileout); +} + +void CBlockPolicyEstimator::Read(CAutoFile& filein) +{ + int nFileBestSeenHeight; + filein >> nFileBestSeenHeight; + feeStats.Read(filein); + priStats.Read(filein); + nBestSeenHeight = nFileBestSeenHeight; +} diff --git a/src/policy/fees.h b/src/policy/fees.h new file mode 100644 index 0000000000..ce4d782566 --- /dev/null +++ b/src/policy/fees.h @@ -0,0 +1,276 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2015 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. +#ifndef BITCOIN_POLICYESTIMATOR_H +#define BITCOIN_POLICYESTIMATOR_H + +#include "amount.h" +#include "uint256.h" + +#include <map> +#include <string> +#include <vector> + +class CAutoFile; +class CFeeRate; +class CTxMemPoolEntry; + +/** \class CBlockPolicyEstimator + * The BlockPolicyEstimator is used for estimating the fee or priority needed + * for a transaction to be included in a block within a certain number of + * blocks. + * + * At a high level the algorithm works by grouping transactions into buckets + * based on having similar priorities or fees and then tracking how long it + * takes transactions in the various buckets to be mined. It operates under + * the assumption that in general transactions of higher fee/priority will be + * included in blocks before transactions of lower fee/priority. So for + * example if you wanted to know what fee you should put on a transaction to + * be included in a block within the next 5 blocks, you would start by looking + * at the bucket with with the highest fee transactions and verifying that a + * sufficiently high percentage of them were confirmed within 5 blocks and + * then you would look at the next highest fee bucket, and so on, stopping at + * the last bucket to pass the test. The average fee of transactions in this + * bucket will give you an indication of the lowest fee you can put on a + * transaction and still have a sufficiently high chance of being confirmed + * within your desired 5 blocks. + * + * When a transaction enters the mempool or is included within a block we + * decide whether it can be used as a data point for fee estimation, priority + * estimation or neither. If the value of exactly one of those properties was + * below the required minimum it can be used to estimate the other. In + * addition, if a priori our estimation code would indicate that the + * transaction would be much more quickly included in a block because of one + * of the properties compared to the other, we can also decide to use it as + * an estimate for that property. + * + * Here is a brief description of the implementation for fee estimation. + * When a transaction that counts for fee estimation enters the mempool, we + * track the height of the block chain at entry. Whenever a block comes in, + * we count the number of transactions in each bucket and the total amount of fee + * paid in each bucket. Then we calculate how many blocks Y it took each + * transaction to be mined and we track an array of counters in each bucket + * for how long it to took transactions to get confirmed from 1 to a max of 25 + * and we increment all the counters from Y up to 25. This is because for any + * number Z>=Y the transaction was successfully mined within Z blocks. We + * want to save a history of this information, so at any time we have a + * counter of the total number of transactions that happened in a given fee + * bucket and the total number that were confirmed in each number 1-25 blocks + * or less for any bucket. We save this history by keeping an exponentially + * decaying moving average of each one of these stats. Furthermore we also + * keep track of the number unmined (in mempool) transactions in each bucket + * and for how many blocks they have been outstanding and use that to increase + * the number of transactions we've seen in that fee bucket when calculating + * an estimate for any number of confirmations below the number of blocks + * they've been outstanding. + */ + +/** + * We will instantiate two instances of this class, one to track transactions + * that were included in a block due to fee, and one for tx's included due to + * priority. We will lump transactions into a bucket according to their approximate + * fee or priority and then track how long it took for those txs to be included in a block + * + * The tracking of unconfirmed (mempool) transactions is completely independent of the + * historical tracking of transactions that have been confirmed in a block. + */ +class TxConfirmStats +{ +private: + //Define the buckets we will group transactions into (both fee buckets and priority buckets) + std::vector<double> buckets; // The upper-bound of the range for the bucket (inclusive) + std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket + + // For each bucket X: + // Count the total # of txs in each bucket + // Track the historical moving average of this total over blocks + std::vector<double> txCtAvg; + // and calcuate the total for the current block to update the moving average + std::vector<int> curBlockTxCt; + + // Count the total # of txs confirmed within Y blocks in each bucket + // Track the historical moving average of theses totals over blocks + std::vector<std::vector<double> > confAvg; // confAvg[Y][X] + // and calcuate the totals for the current block to update the moving averages + std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X] + + // Sum the total priority/fee of all tx's in each bucket + // Track the historical moving average of this total over blocks + std::vector<double> avg; + // and calculate the total for the current block to update the moving average + std::vector<double> curBlockVal; + + // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X + // Combine the total value with the tx counts to calculate the avg fee/priority per bucket + + std::string dataTypeString; + double decay; + + // Mempool counts of outstanding transactions + // For each bucket X, track the number of transactions in the mempool + // that are unconfirmed for each possible confirmation value Y + std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X] + // transactions still unconfirmed after MAX_CONFIRMS for each bucket + std::vector<int> oldUnconfTxs; + +public: + /** + * Initialize the data structures. This is called by BlockPolicyEstimator's + * constructor with default values. + * @param defaultBuckets contains the upper limits for the bucket boundries + * @param maxConfirms max number of confirms to track + * @param decay how much to decay the historical moving average per block + * @param dataTypeString for logging purposes + */ + void Initialize(std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay, std::string dataTypeString); + + /** Clear the state of the curBlock variables to start counting for the new block */ + void ClearCurrent(unsigned int nBlockHeight); + + /** + * Record a new transaction data point in the current block stats + * @param blocksToConfirm the number of blocks it took this transaction to confirm + * @param val either the fee or the priority when entered of the transaction + * @warning blocksToConfirm is 1-based and has to be >= 1 + */ + void Record(int blocksToConfirm, double val); + + /** Record a new transaction entering the mempool*/ + unsigned int NewTx(unsigned int nBlockHeight, double val); + + /** Remove a transaction from mempool tracking stats*/ + void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, + unsigned int bucketIndex); + + /** Update our estimates by decaying our historical moving average and updating + with the data gathered from the current block */ + void UpdateMovingAverages(); + + /** + * Calculate a fee or priority estimate. Find the lowest value bucket (or range of buckets + * to make sure we have enough data points) whose transactions still have sufficient likelihood + * of being confirmed within the target number of confirmations + * @param confTarget target number of confirmations + * @param sufficientTxVal required average number of transactions per block in a bucket range + * @param minSuccess the success probability we require + * @param requireGreater return the lowest fee/pri such that all higher values pass minSuccess OR + * return the highest fee/pri such that all lower values fail minSuccess + * @param nBlockHeight the current block height + */ + double EstimateMedianVal(int confTarget, double sufficientTxVal, + double minSuccess, bool requireGreater, unsigned int nBlockHeight); + + /** Return the max number of confirms we're tracking */ + unsigned int GetMaxConfirms() { return confAvg.size(); } + + /** Write state of estimation data to a file*/ + void Write(CAutoFile& fileout); + + /** + * Read saved state of estimation data from a file and replace all internal data structures and + * variables with this state. + */ + void Read(CAutoFile& filein); +}; + + + +/** Track confirm delays up to 25 blocks, can't estimate beyond that */ +static const unsigned int MAX_BLOCK_CONFIRMS = 25; + +/** Decay of .998 is a half-life of 346 blocks or about 2.4 days */ +static const double DEFAULT_DECAY = .998; + +/** Require greater than 85% of X fee transactions to be confirmed within Y blocks for X to be big enough */ +static const double MIN_SUCCESS_PCT = .85; +static const double UNLIKELY_PCT = .5; + +/** Require an avg of 1 tx in the combined fee bucket per block to have stat significance */ +static const double SUFFICIENT_FEETXS = 1; + +/** Require only an avg of 1 tx every 5 blocks in the combined pri bucket (way less pri txs) */ +static const double SUFFICIENT_PRITXS = .2; + +// Minimum and Maximum values for tracking fees and priorities +static const double MIN_FEERATE = 10; +static const double MAX_FEERATE = 1e7; +static const double INF_FEERATE = MAX_MONEY; +static const double MIN_PRIORITY = 10; +static const double MAX_PRIORITY = 1e16; +static const double INF_PRIORITY = 1e9 * MAX_MONEY; + +// We have to lump transactions into buckets based on fee or priority, but we want to be able +// to give accurate estimates over a large range of potential fees and priorities +// Therefore it makes sense to exponentially space the buckets +/** Spacing of FeeRate buckets */ +static const double FEE_SPACING = 1.1; + +/** Spacing of Priority buckets */ +static const double PRI_SPACING = 2; + +/** + * We want to be able to estimate fees or priorities that are needed on tx's to be included in + * a certain number of blocks. Every time a block is added to the best chain, this class records + * stats on the transactions included in that block + */ +class CBlockPolicyEstimator +{ +public: + /** Create new BlockPolicyEstimator and initialize stats tracking classes with default values */ + CBlockPolicyEstimator(const CFeeRate& minRelayFee); + + /** Process all the transactions that have been included in a block */ + void processBlock(unsigned int nBlockHeight, + std::vector<CTxMemPoolEntry>& entries, bool fCurrentEstimate); + + /** Process a transaction confirmed in a block*/ + void processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry& entry); + + /** Process a transaction accepted to the mempool*/ + void processTransaction(const CTxMemPoolEntry& entry, bool fCurrentEstimate); + + /** Remove a transaction from the mempool tracking stats*/ + void removeTx(uint256 hash); + + /** Is this transaction likely included in a block because of its fee?*/ + bool isFeeDataPoint(const CFeeRate &fee, double pri); + + /** Is this transaction likely included in a block because of its priority?*/ + bool isPriDataPoint(const CFeeRate &fee, double pri); + + /** Return a fee estimate */ + CFeeRate estimateFee(int confTarget); + + /** Return a priority estimate */ + double estimatePriority(int confTarget); + + /** Write estimation data to a file */ + void Write(CAutoFile& fileout); + + /** Read estimation data from a file */ + void Read(CAutoFile& filein); + +private: + CFeeRate minTrackedFee; //! Passed to constructor to avoid dependency on main + double minTrackedPriority; //! Set to AllowFreeThreshold + unsigned int nBestSeenHeight; + struct TxStatsInfo + { + TxConfirmStats *stats; + unsigned int blockHeight; + unsigned int bucketIndex; + TxStatsInfo() : stats(NULL), blockHeight(0), bucketIndex(0) {} + }; + + // map of txids to information about that transaction + std::map<uint256, TxStatsInfo> mapMemPoolTxs; + + /** Classes to track historical data on transaction confirmations */ + TxConfirmStats feeStats, priStats; + + /** Breakpoints to help determine whether a transaction was confirmed by priority or Fee */ + CFeeRate feeLikely, feeUnlikely; + double priLikely, priUnlikely; +}; +#endif /*BITCOIN_POLICYESTIMATOR_H */ |