diff --git a/doc/files.md b/doc/files.md --- a/doc/files.md +++ b/doc/files.md @@ -9,7 +9,6 @@ * database/*: BDB database environment; only used for wallet since 0.8.0 * db.log: wallet database log file * debug.log: contains debug information and general logging generated by bitcoind or bitcoin-qt -* fee_estimates.dat: stores statistics used to estimate minimum transaction fees and priorities required for confirmation; since 0.10.0 * mempool.dat: dump of the mempool's transactions; since 0.14.0. * peers.dat: peer IP address database (custom format); since 0.7.0 * wallet.dat: personal wallet (BDB) with keys and transactions diff --git a/doc/release-notes.md b/doc/release-notes.md --- a/doc/release-notes.md +++ b/doc/release-notes.md @@ -15,3 +15,5 @@ - Wallet `listreceivedbylabel`, `listreceivedbyaccount` and `listunspent` RPCs add `label` fields to returned JSON objects that previously only had `account` fields. + - Remove miner policy estimator in favor of minimum fees, also remove `fee_estimates.dat`. + Old copies will be left in place. \ No newline at end of file diff --git a/src/init.cpp b/src/init.cpp --- a/src/init.cpp +++ b/src/init.cpp @@ -69,7 +69,6 @@ #include "zmq/zmqnotificationinterface.h" #endif -bool fFeeEstimatesInitialized = false; static const bool DEFAULT_PROXYRANDOMIZE = true; static const bool DEFAULT_REST_ENABLE = false; static const bool DEFAULT_STOPAFTERBLOCKIMPORT = false; @@ -89,8 +88,6 @@ #define MIN_CORE_FILEDESCRIPTORS 150 #endif -static const char *FEE_ESTIMATES_FILENAME = "fee_estimates.dat"; - ////////////////////////////////////////////////////////////////////////////// // // Shutdown @@ -210,19 +207,6 @@ DumpMempool(); } - if (fFeeEstimatesInitialized) { - fs::path est_path = GetDataDir() / FEE_ESTIMATES_FILENAME; - CAutoFile est_fileout(fsbridge::fopen(est_path, "wb"), SER_DISK, - CLIENT_VERSION); - if (!est_fileout.IsNull()) { - g_mempool.WriteFeeEstimates(est_fileout); - } else { - LogPrintf("%s: Failed to write fee estimates to %s\n", __func__, - est_path.string()); - } - fFeeEstimatesInitialized = false; - } - // FlushStateToDisk generates a SetBestChain callback, which we should avoid // missing if (pcoinsTip != nullptr) { @@ -2189,15 +2173,6 @@ } LogPrintf(" block index %15dms\n", GetTimeMillis() - nStart); - fs::path est_path = GetDataDir() / FEE_ESTIMATES_FILENAME; - CAutoFile est_filein(fsbridge::fopen(est_path, "rb"), SER_DISK, - CLIENT_VERSION); - // Allowed to fail as this file IS missing on first startup. - if (!est_filein.IsNull()) { - g_mempool.ReadFeeEstimates(est_filein); - } - fFeeEstimatesInitialized = true; - // Encoded addresses using cashaddr instead of base58 // Activates by default on Jan, 14 config.SetCashAddrEncoding( diff --git a/src/policy/fees.h b/src/policy/fees.h --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -13,175 +13,7 @@ #include #include -class CAutoFile; class CFeeRate; -class CTxMemPoolEntry; -class CTxMemPool; - -/** \class CBlockPolicyEstimator - * The BlockPolicyEstimator is used for estimating the feerate 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 feerates 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 feerate will be included in - * blocks before transactions of lower feerate. So for example if you wanted to - * know what feerate 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 the - * highest feerate transactions and verifying that a sufficiently high - * percentage of them were confirmed within 5 blocks and then you would look at - * the next highest feerate bucket, and so on, stopping at the last bucket to - * pass the test. The average feerate of transactions in this bucket will give - * you an indication of the lowest feerate you can put on a transaction and - * still have a sufficiently high chance of being confirmed within your desired - * 5 blocks. - * - * Here is a brief description of the implementation: - * When a transaction 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 feerate 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 feerate 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 feerate bucket when calculating an estimate for any number of - * confirmations below the number of blocks they've been outstanding. - */ - -/** - * We will instantiate an instance of this class to track transactions that were - * included in a block. We will lump transactions into a bucket according to - * their approximate feerate 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 - // The upper-bound of the range for the bucket (inclusive) - std::vector buckets; - // Map of bucket upper-bound to index into all vectors by bucket - std::map bucketMap; - - // For each bucket X: - // Count the total # of txs in each bucket - // Track the historical moving average of this total over blocks - std::vector txCtAvg; - // and calculate the total for the current block to update the moving - // average - std::vector curBlockTxCt; - - // Count the total # of txs confirmed within Y blocks in each bucket - // Track the historical moving average of theses totals over blocks - // confAvg[Y][X] - std::vector> confAvg; - // and calculate the totals for the current block to update the moving - // averages - // curBlockConf[Y][X] - std::vector> curBlockConf; - - // Sum the total feerate of all tx's in each bucket - // Track the historical moving average of this total over blocks - std::vector avg; - // and calculate the total for the current block to update the moving - // average - std::vector 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 feerate per bucket - 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 - // unconfTxs[Y][X] - std::vector> unconfTxs; - // transactions still unconfirmed after MAX_CONFIRMS for each bucket - std::vector 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 boundaries - * @param maxConfirms max number of confirms to track - * @param decay how much to decay the historical moving average per block - */ - void Initialize(std::vector &defaultBuckets, - unsigned int maxConfirms, double decay); - - /** - * 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 the feerate 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 feerate 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 feerate such that all higher - * values pass minSuccess OR - * return the highest feerate such that all lower values fail - * minSuccess - * @param nBlockHeight the current block height - */ - CFeeRate EstimateMedianFeeRate(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; @@ -209,69 +41,6 @@ /** Spacing of FeeRate buckets */ static const double FEE_SPACING = 1.1; -/** - * We want to be able to estimate feerates 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(); - - /** Process all the transactions that have been included in a block */ - void processBlock(unsigned int nBlockHeight, - std::vector &entries); - - /** Process a transaction confirmed in a block*/ - bool processBlockTx(unsigned int nBlockHeight, - const CTxMemPoolEntry *entry); - - /** Process a transaction accepted to the mempool*/ - void processTransaction(const CTxMemPoolEntry &entry, - bool validFeeEstimate); - - /** Remove a transaction from the mempool tracking stats*/ - bool removeTx(uint256 hash); - - /** Return a feerate estimate */ - CFeeRate estimateFee(int confTarget); - - /** Estimate feerate needed to get be included in a block within - * confTarget blocks. If no answer can be given at confTarget, return an - * estimate at the lowest target where one can be given. - */ - CFeeRate estimateSmartFee(int confTarget, int *answerFoundAtTarget, - const CTxMemPool &pool); - - /** Write estimation data to a file */ - void Write(CAutoFile &fileout); - - /** Read estimation data from a file */ - void Read(CAutoFile &filein, int nFileVersion); - -private: - //!< Passed to constructor to avoid dependency on main - unsigned int nBestSeenHeight; - struct TxStatsInfo { - unsigned int blockHeight; - unsigned int bucketIndex; - TxStatsInfo() : blockHeight(0), bucketIndex(0) {} - }; - - // map of txids to information about that transaction - std::map mapMemPoolTxs; - - /** Classes to track historical data on transaction confirmations */ - TxConfirmStats feeStats; - - unsigned int trackedTxs; - unsigned int untrackedTxs; -}; class FeeFilterRounder { public: diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp --- a/src/policy/fees.cpp +++ b/src/policy/fees.cpp @@ -5,537 +5,9 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "policy/fees.h" -#include "policy/policy.h" #include "amount.h" -#include "primitives/transaction.h" -#include "random.h" -#include "streams.h" -#include "txmempool.h" -#include "util.h" - -void TxConfirmStats::Initialize(std::vector &defaultBuckets, - unsigned int maxConfirms, double _decay) { - decay = _decay; - for (size_t 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 (size_t j = 0; j < buckets.size(); j++) { - oldUnconfTxs[j] += unconfTxs[nBlockHeight % unconfTxs.size()][j]; - unconfTxs[nBlockHeight % unconfTxs.size()][j] = 0; - for (size_t 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 -CFeeRate TxConfirmStats::EstimateMedianFeeRate(int confTarget, - double sufficientTxVal, - double successBreakPoint, - bool requireGreater, - unsigned int nBlockHeight) { - // Counters for a bucket (or range of buckets) - // Number of tx's confirmed within the confTarget - double nConf = 0; - // Total number of tx's that were ever confirmed - double totalNum = 0; - // Number of tx's still in mempool for confTarget or longer - int extraNum = 0; - - int maxbucketindex = buckets.size() - 1; - - // requireGreater means we are looking for the lowest feerate such that all - // higher values pass, so we start at maxbucketindex (highest feerate) and - // look at successively smaller buckets until we reach failure. Otherwise, - // we are looking for the highest feerate 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 feerate 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 - foundAnswer = true; - nConf = 0; - totalNum = 0; - extraNum = 0; - bestNearBucket = curNearBucket; - bestFarBucket = curFarBucket; - curNearBucket = bucket + step; - } - } - - double median = -1; - double txSum = 0; - - // Calculate the "average" feerate of the best bucket range that met success - // conditions. Find the bucket with the median transaction and then report - // the average feerate 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(BCLog::ESTIMATEFEE, "%3d: For conf success %s %4.2f need feerate " - "%s: %12.5g from buckets %8g - %8g Cur " - "Bucket stats %6.2f%% %8.1f/(%.1f+%d " - "mempool)\n", - confTarget, requireGreater ? ">" : "<", successBreakPoint, - requireGreater ? ">" : "<", median, buckets[minBucket], - buckets[maxBucket], 100 * nConf / (totalNum + extraNum), nConf, - totalNum, extraNum); - - return CFeeRate(int64_t(ceill(median)) * SATOSHI); -} - -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 fileBuckets; - std::vector fileAvg; - std::vector> fileConfAvg; - std::vector 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 feerate buckets"); - } - filein >> fileAvg; - if (fileAvg.size() != numBuckets) { - throw std::runtime_error( - "Corrupt estimates file. Mismatch in feerate 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 " - "feerate conf average bucket count"); - } - } - // Now that we've processed the entire feerate 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 (size_t i = 0; i < buckets.size(); i++) { - bucketMap[buckets[i]] = i; - } - - LogPrint( - BCLog::ESTIMATEFEE, - "Reading estimates: %u buckets counting confirms up to %u blocks\n", - numBuckets, 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]++; - 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) { - // This can't happen because we call this with our best seen height, no - // entries can have higher - LogPrint(BCLog::ESTIMATEFEE, - "Blockpolicy error, blocks ago is negative for mempool tx\n"); - return; - } - - if (blocksAgo >= (int)unconfTxs.size()) { - if (oldUnconfTxs[bucketindex] > 0) { - oldUnconfTxs[bucketindex]--; - } else { - LogPrint(BCLog::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(BCLog::ESTIMATEFEE, - "Blockpolicy error, mempool tx removed from " - "blockIndex=%u,bucketIndex=%u already\n", - blockIndex, bucketindex); - } - } -} - -// This function is called from CTxMemPool::removeUnchecked to ensure txs -// removed from the mempool for any reason are no longer tracked. Txs that were -// part of a block have already been removed in processBlockTx to ensure they -// are never double tracked, but it is of no harm to try to remove them again. -bool CBlockPolicyEstimator::removeTx(uint256 hash) { - std::map::iterator pos = mapMemPoolTxs.find(hash); - if (pos == mapMemPoolTxs.end()) { - return false; - } - - feeStats.removeTx(pos->second.blockHeight, nBestSeenHeight, - pos->second.bucketIndex); - mapMemPoolTxs.erase(hash); - return true; -} - -CBlockPolicyEstimator::CBlockPolicyEstimator() - : nBestSeenHeight(0), trackedTxs(0), untrackedTxs(0) { - static_assert(MIN_FEERATE > Amount::zero(), "Min feerate must be nonzero"); - CFeeRate minFeeRate(MIN_FEERATE); - std::vector vfeelist; - for (double bucketBoundary = minFeeRate.GetFeePerK() / SATOSHI; - bucketBoundary <= double(MAX_FEERATE / SATOSHI); - bucketBoundary *= FEE_SPACING) { - vfeelist.push_back(bucketBoundary); - } - - vfeelist.push_back(double(INF_FEERATE / SATOSHI)); - feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY); -} - -void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry &entry, - bool validFeeEstimate) { - uint32_t txHeight = entry.GetHeight(); - uint256 txid = entry.GetTx().GetId(); - if (mapMemPoolTxs.count(txid)) { - LogPrint(BCLog::ESTIMATEFEE, - "Blockpolicy error mempool tx %s already being tracked\n", - txid.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. Ignore txs if BlockPolicyEstimator is not in sync - // with chainActive.Tip(). It will be synced next time a block is - // processed. - 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 (!validFeeEstimate) { - untrackedTxs++; - return; - } - trackedTxs++; - - // Feerates are stored and reported as BCH-per-kb: - CFeeRate feeRate(entry.GetFee(), entry.GetTxSize()); - - mapMemPoolTxs[txid].blockHeight = txHeight; - mapMemPoolTxs[txid].bucketIndex = - feeStats.NewTx(txHeight, double(feeRate.GetFeePerK() / SATOSHI)); -} - -bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, - const CTxMemPoolEntry *entry) { - if (!removeTx(entry->GetTx().GetId())) { - // This transaction wasn't being tracked for fee estimation - return false; - } - - // 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( - BCLog::ESTIMATEFEE, - "Blockpolicy error Transaction had negative blocksToConfirm\n"); - return false; - } - - // Feerates are stored and reported as BCH-per-kb: - CFeeRate feeRate(entry->GetFee(), entry->GetTxSize()); - - feeStats.Record(blocksToConfirm, double(feeRate.GetFeePerK() / SATOSHI)); - return true; -} - -void CBlockPolicyEstimator::processBlock( - unsigned int nBlockHeight, std::vector &entries) { - 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; - } - - // Must update nBestSeenHeight in sync with ClearCurrent so that calls to - // removeTx (via processBlockTx) correctly calculate age of unconfirmed txs - // to remove from tracking. - nBestSeenHeight = nBlockHeight; - - // Clear the current block state and update unconfirmed circular buffer - feeStats.ClearCurrent(nBlockHeight); - - unsigned int countedTxs = 0; - // Repopulate the current block states - for (size_t i = 0; i < entries.size(); i++) { - if (processBlockTx(nBlockHeight, entries[i])) { - countedTxs++; - } - } - - // Update all exponential averages with the current block state - feeStats.UpdateMovingAverages(); - - LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy after updating estimates for %u " - "of %u txs in block, since last block %u of " - "%u tracked, new mempool map size %u\n", - countedTxs, entries.size(), trackedTxs, trackedTxs + untrackedTxs, - mapMemPoolTxs.size()); - - trackedTxs = 0; - untrackedTxs = 0; -} - -CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) { - // Return failure if trying to analyze a target we're not tracking - // It's not possible to get reasonable estimates for confTarget of 1 - if (confTarget <= 1 || - (unsigned int)confTarget > feeStats.GetMaxConfirms()) { - return CFeeRate(Amount::zero()); - } - - CFeeRate median = feeStats.EstimateMedianFeeRate( - confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight); - - if (median < CFeeRate(Amount::zero())) { - return CFeeRate(Amount::zero()); - } - - return median; -} - -CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, - int *answerFoundAtTarget, - const CTxMemPool &pool) { - if (answerFoundAtTarget) { - *answerFoundAtTarget = confTarget; - } - // Return failure if trying to analyze a target we're not tracking - if (confTarget <= 0 || - (unsigned int)confTarget > feeStats.GetMaxConfirms()) { - return CFeeRate(Amount::zero()); - } - - // It's not possible to get reasonable estimates for confTarget of 1 - if (confTarget == 1) { - confTarget = 2; - } - - CFeeRate median = CFeeRate(-1 * SATOSHI); - while (median < CFeeRate(Amount::zero()) && - uint32_t(confTarget) <= feeStats.GetMaxConfirms()) { - median = feeStats.EstimateMedianFeeRate(confTarget++, SUFFICIENT_FEETXS, - MIN_SUCCESS_PCT, true, - nBestSeenHeight); - } - - if (answerFoundAtTarget) { - *answerFoundAtTarget = confTarget - 1; - } - - // If mempool is limiting txs , return at least the min feerate from the - // mempool - Amount minPoolFee = - pool.GetMinFee(gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * - 1000000) - .GetFeePerK(); - if (minPoolFee > Amount::zero() && minPoolFee > median.GetFeePerK()) { - return CFeeRate(minPoolFee); - } - - if (median < CFeeRate(Amount::zero())) { - return CFeeRate(Amount::zero()); - } - - return median; -} - -void CBlockPolicyEstimator::Write(CAutoFile &fileout) { - fileout << nBestSeenHeight; - feeStats.Write(fileout); -} - -void CBlockPolicyEstimator::Read(CAutoFile &filein, int nFileVersion) { - int nFileBestSeenHeight; - filein >> nFileBestSeenHeight; - feeStats.Read(filein); - nBestSeenHeight = nFileBestSeenHeight; - if (nFileVersion < 139900) { - TxConfirmStats priStats; - priStats.Read(filein); - } -} +#include "feerate.h" FeeFilterRounder::FeeFilterRounder(const CFeeRate &minIncrementalFee) { Amount minFeeLimit = std::max(SATOSHI, minIncrementalFee.GetFeePerK() / 2); diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp --- a/src/test/policyestimator_tests.cpp +++ b/src/test/policyestimator_tests.cpp @@ -14,242 +14,6 @@ BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, BasicTestingSetup) -BOOST_AUTO_TEST_CASE(BlockPolicyEstimates) { - CTxMemPool mpool; - TestMemPoolEntryHelper entry; - Amount basefee = 2000 * SATOSHI; - Amount deltaFee = 100 * SATOSHI; - std::vector feeV; - - // Populate vectors of increasing fees - for (int j = 0; j < 10; j++) { - feeV.push_back((j + 1) * basefee); - } - - // Store the hashes of transactions that have been added to the mempool by - // their associate fee txIds[j] is populated with transactions either of - // fee = basefee * (j+1) - std::array, 10> txIds; - - // Create a transaction template - CScript garbage; - for (unsigned int i = 0; i < 128; i++) { - garbage.push_back('X'); - } - - CMutableTransaction tx; - tx.vin.resize(1); - tx.vin[0].scriptSig = garbage; - tx.vout.resize(1); - tx.vout[0].nValue = Amount::zero(); - CFeeRate baseRate(basefee, CTransaction(tx).GetTotalSize()); - - // Create a fake block - std::vector block; - int blocknum = 0; - - // Loop through 200 blocks - // At a decay .998 and 4 fee transactions per block - // This makes the tx count about 1.33 per bucket, above the 1 threshold - while (blocknum < 200) { - // For each fee - for (size_t j = 0; j < txIds.size(); j++) { - // add 4 fee txs - for (int k = 0; k < 4; k++) { - // make transaction unique - tx.vin[0].nSequence = 10000 * blocknum + 100 * j + k; - TxId txid = tx.GetId(); - mpool.addUnchecked(txid, - entry.Fee(feeV[j]) - .Time(GetTime()) - .Priority(0) - .Height(blocknum) - .FromTx(tx, &mpool)); - txIds[j].push_back(txid); - } - } - // Create blocks where higher fee txs are included more often - for (size_t h = 0; h <= blocknum % txIds.size(); h++) { - // 10/10 blocks add highest fee transactions - // 9/10 blocks add 2nd highest and so on until ... - // 1/10 blocks add lowest fee transactions - size_t i = txIds.size() - h - 1; - while (txIds[i].size()) { - CTransactionRef ptx = mpool.get(txIds[i].back()); - if (ptx) { - block.push_back(ptx); - } - txIds[i].pop_back(); - } - } - mpool.removeForBlock(block, ++blocknum); - block.clear(); - if (blocknum == 30) { - // At this point we should need to combine 5 buckets to get enough - // data points. So estimateFee(1,2,3) should fail and estimateFee(4) - // should return somewhere around 8*baserate. estimateFee(4) %'s - // are 100,100,100,100,90 = average 98% - BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(Amount::zero())); - BOOST_CHECK(mpool.estimateFee(2) == CFeeRate(Amount::zero())); - BOOST_CHECK(mpool.estimateFee(3) == CFeeRate(Amount::zero())); - BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() < - 8 * baseRate.GetFeePerK() + deltaFee); - BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() > - 8 * baseRate.GetFeePerK() - deltaFee); - int answerFound; - BOOST_CHECK(mpool.estimateSmartFee(1, &answerFound) == - mpool.estimateFee(4) && - answerFound == 4); - BOOST_CHECK(mpool.estimateSmartFee(3, &answerFound) == - mpool.estimateFee(4) && - answerFound == 4); - BOOST_CHECK(mpool.estimateSmartFee(4, &answerFound) == - mpool.estimateFee(4) && - answerFound == 4); - BOOST_CHECK(mpool.estimateSmartFee(8, &answerFound) == - mpool.estimateFee(8) && - answerFound == 8); - } - } - - std::vector origFeeEst; - // Highest feerate is 10*baseRate and gets in all blocks, second highest - // feerate is 9*baseRate and gets in 9/10 blocks = 90%, third highest - // feerate is 8*base rate, and gets in 8/10 blocks = 80%, so estimateFee(1) - // would return 10*baseRate but is hardcoded to return failure. Second - // highest feerate has 100% chance of being included by 2 blocks, so - // estimateFee(2) should return 9*baseRate etc... - for (int i = 1; i < 10; i++) { - origFeeEst.push_back(mpool.estimateFee(i).GetFeePerK()); - // Fee estimates should be monotonically decreasing - if (i > 2) { - BOOST_CHECK(origFeeEst[i - 1] <= origFeeEst[i - 2]); - } - int mult = 11 - i; - if (i > 1) { - BOOST_CHECK(origFeeEst[i - 1] < - mult * baseRate.GetFeePerK() + deltaFee); - BOOST_CHECK(origFeeEst[i - 1] > - mult * baseRate.GetFeePerK() - deltaFee); - } else { - BOOST_CHECK(origFeeEst[i - 1] == - CFeeRate(Amount::zero()).GetFeePerK()); - } - } - - // Mine 50 more blocks with no transactions happening, estimates shouldn't - // change. We haven't decayed the moving average enough so we still have - // enough data points in every bucket - while (blocknum < 250) { - mpool.removeForBlock(block, ++blocknum); - } - - BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(Amount::zero())); - for (int i = 2; i < 10; i++) { - BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < - origFeeEst[i - 1] + deltaFee); - BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > - origFeeEst[i - 1] - deltaFee); - } - - // Mine 15 more blocks with lots of transactions happening and not getting - // mined. Estimates should go up - while (blocknum < 265) { - // For each fee multiple - for (size_t j = 0; j < txIds.size(); j++) { - // add 4 fee txs - for (int k = 0; k < 4; k++) { - tx.vin[0].nSequence = 10000 * blocknum + 100 * j + k; - TxId txid = tx.GetId(); - mpool.addUnchecked(txid, - entry.Fee(feeV[j]) - .Time(GetTime()) - .Priority(0) - .Height(blocknum) - .FromTx(tx, &mpool)); - txIds[j].push_back(txid); - } - } - mpool.removeForBlock(block, ++blocknum); - } - - int answerFound; - for (int i = 1; i < 10; i++) { - BOOST_CHECK(mpool.estimateFee(i) == CFeeRate(Amount::zero()) || - mpool.estimateFee(i).GetFeePerK() > - origFeeEst[i - 1] - deltaFee); - Amount a1 = mpool.estimateSmartFee(i, &answerFound).GetFeePerK(); - Amount a2 = origFeeEst[answerFound - 1] - deltaFee; - BOOST_CHECK(a1 > a2); - } - - // Mine all those transactions - // Estimates should still not be below original - for (size_t j = 0; j < txIds.size(); j++) { - while (txIds[j].size()) { - CTransactionRef ptx = mpool.get(txIds[j].back()); - if (ptx) { - block.push_back(ptx); - } - txIds[j].pop_back(); - } - } - mpool.removeForBlock(block, 265); - block.clear(); - BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(Amount::zero())); - for (int i = 2; i < 10; i++) { - BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > - origFeeEst[i - 1] - deltaFee); - } - - // Mine 200 more blocks where everything is mined every block - // Estimates should be below original estimates - while (blocknum < 465) { - // For each fee multiple - for (size_t j = 0; j < txIds.size(); j++) { - // add 4 fee txs - for (int k = 0; k < 4; k++) { - tx.vin[0].nSequence = 10000 * blocknum + 100 * j + k; - TxId txid = tx.GetId(); - mpool.addUnchecked(txid, - entry.Fee(feeV[j]) - .Time(GetTime()) - .Priority(0) - .Height(blocknum) - .FromTx(tx, &mpool)); - CTransactionRef ptx = mpool.get(txid); - if (ptx) { - block.push_back(ptx); - } - } - } - mpool.removeForBlock(block, ++blocknum); - block.clear(); - } - BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(Amount::zero())); - for (int i = 2; i < 10; i++) { - BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < - origFeeEst[i - 1] - deltaFee); - } - - // Test that if the mempool is limited, estimateSmartFee won't return a - // value below the mempool min - mpool.addUnchecked( - tx.GetId(), - entry.Fee(feeV[5]).Time(GetTime()).Priority(0).Height(blocknum).FromTx( - tx, &mpool)); - // evict that transaction which should set a mempool min fee of - // minRelayTxFee + feeV[5] - mpool.TrimToSize(1); - BOOST_CHECK(mpool.GetMinFee(1).GetFeePerK() > feeV[5]); - for (int i = 1; i < 10; i++) { - BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= - mpool.estimateFee(i).GetFeePerK()); - BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= - mpool.GetMinFee(1).GetFeePerK()); - } -} - BOOST_AUTO_TEST_CASE(MempoolMinimumFeeEstimate) { CTxMemPool mpool; TestMemPoolEntryHelper entry; diff --git a/src/txmempool.h b/src/txmempool.h --- a/src/txmempool.h +++ b/src/txmempool.h @@ -494,7 +494,6 @@ //!< Value n means that n times in 2^32 we check. uint32_t nCheckFrequency; unsigned int nTransactionsUpdated; - CBlockPolicyEstimator *minerPolicyEstimator; //!< sum of all mempool tx's virtual sizes. uint64_t totalTxSize; @@ -756,10 +755,6 @@ /** Estimate fee rate needed to get into the next nBlocks */ CFeeRate estimateFee(int nBlocks) const; - /** Write/Read estimates to disk */ - bool WriteFeeEstimates(CAutoFile &fileout) const; - bool ReadFeeEstimates(CAutoFile &filein); - size_t DynamicMemoryUsage() const; boost::signals2::signal NotifyEntryAdded; diff --git a/src/txmempool.cpp b/src/txmempool.cpp --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -7,6 +7,7 @@ #include "chainparams.h" // for GetConsensus. #include "clientversion.h" +#include "config.h" #include "consensus/consensus.h" #include "consensus/tx_verify.h" #include "consensus/validation.h" @@ -414,13 +415,9 @@ // transactions becomes O(N^2) where N is the number of transactions in the // pool nCheckFrequency = 0; - - minerPolicyEstimator = new CBlockPolicyEstimator(); } -CTxMemPool::~CTxMemPool() { - delete minerPolicyEstimator; -} +CTxMemPool::~CTxMemPool() {} bool CTxMemPool::isSpent(const COutPoint &outpoint) { LOCK(cs); @@ -487,7 +484,6 @@ nTransactionsUpdated++; totalTxSize += entry.GetTxSize(); - minerPolicyEstimator->processTransaction(entry, validFeeEstimate); vTxHashes.emplace_back(tx.GetHash(), newit); newit->vTxHashesIdx = vTxHashes.size() - 1; @@ -497,7 +493,6 @@ void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason) { NotifyEntryRemoved(it->GetSharedTx(), reason); - const uint256 txid = it->GetTx().GetId(); for (const CTxIn &txin : it->GetTx().vin) { mapNextTx.erase(txin.prevout); } @@ -520,7 +515,6 @@ mapLinks.erase(it); mapTx.erase(it); nTransactionsUpdated++; - minerPolicyEstimator->removeTx(txid); } // Calculates descendants of entry that are not already in setDescendants, and @@ -676,9 +670,6 @@ } } - // Before the txs in the new block have been removed from the mempool, - // update policy estimates - minerPolicyEstimator->processBlock(nBlockHeight, entries); for (const CTransactionRef &tx : boost::adaptors::reverse( disconnectpool.GetQueuedTx().get())) { txiter it = mapTx.find(tx->GetId()); @@ -973,52 +964,16 @@ // may disagree with the rollingMinimumFeerate under certain scenarios // where the mempool increases rapidly, or blocks are being mined which // do not contain propagated transactions. - return std::max(minerPolicyEstimator->estimateFee(nBlocks), - GetMinFee(maxMempoolSize)); + return std::max(GetConfig().GetMinFeePerKB(), GetMinFee(maxMempoolSize)); } CFeeRate CTxMemPool::estimateSmartFee(int nBlocks, int *answerFoundAtBlocks) const { - LOCK(cs); + if (answerFoundAtBlocks != nullptr) { + *answerFoundAtBlocks = 1; + } // estimateSmartFee already includes the GetMinFee check, this is the // reason it takes `*this`. It does not need std::max as above. - return minerPolicyEstimator->estimateSmartFee(nBlocks, answerFoundAtBlocks, - *this); -} - -bool CTxMemPool::WriteFeeEstimates(CAutoFile &fileout) const { - try { - LOCK(cs); - // version required to read: 0.13.99 or later - fileout << 139900; - // version that wrote the file - fileout << CLIENT_VERSION; - minerPolicyEstimator->Write(fileout); - } catch (const std::exception &) { - LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy " - "estimator data (non-fatal)\n"); - return false; - } - return true; -} - -bool CTxMemPool::ReadFeeEstimates(CAutoFile &filein) { - try { - int nVersionRequired, nVersionThatWrote; - filein >> nVersionRequired >> nVersionThatWrote; - if (nVersionRequired > CLIENT_VERSION) { - return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee " - "estimate file", - nVersionRequired); - } - - LOCK(cs); - minerPolicyEstimator->Read(filein, nVersionThatWrote); - } catch (const std::exception &) { - LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy " - "estimator data (non-fatal)\n"); - return false; - } - return true; + return estimateFee(nBlocks); } void CTxMemPool::PrioritiseTransaction(const uint256 hash, diff --git a/test/functional/test_framework/test_framework.py b/test/functional/test_framework/test_framework.py --- a/test/functional/test_framework/test_framework.py +++ b/test/functional/test_framework/test_framework.py @@ -452,8 +452,6 @@ os.remove(log_filename(self.options.cachedir, i, "debug.log")) os.remove(log_filename(self.options.cachedir, i, "db.log")) os.remove(log_filename(self.options.cachedir, i, "peers.dat")) - os.remove(log_filename( - self.options.cachedir, i, "fee_estimates.dat")) for i in range(self.num_nodes): from_dir = os.path.join(self.options.cachedir, "node" + str(i))