diff --git a/doc/release-notes.md b/doc/release-notes.md index 640890c9a8..def41e76eb 100644 --- a/doc/release-notes.md +++ b/doc/release-notes.md @@ -1,5 +1,6 @@ Bitcoin ABC version 0.17.2 is now available from: This release includes the following features and fixes: + - Remove deprecated `estimatepriority` RPC. diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp index 7f86514c98..4070a67946 100644 --- a/src/policy/fees.cpp +++ b/src/policy/fees.cpp @@ -1,582 +1,578 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core 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 "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 double TxConfirmStats::EstimateMedianVal(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 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 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(const CFeeRate &_minRelayFee) : nBestSeenHeight(0), trackedTxs(0), untrackedTxs(0) { static_assert(MIN_FEERATE > Amount(0), "Min feerate must be nonzero"); CFeeRate minFeeRate(MIN_FEERATE); minTrackedFee = _minRelayFee < minFeeRate ? minFeeRate : _minRelayFee; std::vector vfeelist; for (double bucketBoundary = minTrackedFee.GetFeePerK().GetSatoshis(); bucketBoundary <= double(MAX_FEERATE.GetSatoshis()); bucketBoundary *= FEE_SPACING) { vfeelist.push_back(bucketBoundary); } vfeelist.push_back(double(INF_FEERATE.GetSatoshis())); 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().GetSatoshis())); } 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().GetSatoshis()); 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(0)); } double median = feeStats.EstimateMedianVal( confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight); if (median < 0) { return CFeeRate(Amount(0)); } return CFeeRate(Amount(int64_t(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(0)); } // It's not possible to get reasonable estimates for confTarget of 1 if (confTarget == 1) { confTarget = 2; } double median = -1; while (median < 0 && (unsigned int)confTarget <= feeStats.GetMaxConfirms()) { median = feeStats.EstimateMedianVal(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(0) && minPoolFee > Amount(int64_t(median))) { return CFeeRate(minPoolFee); } if (median < 0) { return CFeeRate(Amount(0)); } return CFeeRate(Amount(int64_t(median))); } -double CBlockPolicyEstimator::estimatePriority(int confTarget) { - return -1; -} - double CBlockPolicyEstimator::estimateSmartPriority(int confTarget, int *answerFoundAtTarget, const CTxMemPool &pool) { if (answerFoundAtTarget) { *answerFoundAtTarget = confTarget; } // If mempool is limiting txs, no priority txs are allowed Amount minPoolFee = pool.GetMinFee(gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000) .GetFeePerK(); if (minPoolFee > Amount(0)) { return double(INF_PRIORITY.GetSatoshis()); } return -1; } 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); } } FeeFilterRounder::FeeFilterRounder(const CFeeRate &minIncrementalFee) { Amount minFeeLimit = std::max(Amount(1), minIncrementalFee.GetFeePerK() / 2); feeset.insert(Amount(0)); for (double bucketBoundary = minFeeLimit.GetSatoshis(); bucketBoundary <= double(MAX_FEERATE.GetSatoshis()); bucketBoundary *= FEE_SPACING) { feeset.insert(Amount(int64_t(bucketBoundary))); } } Amount FeeFilterRounder::round(const Amount currentMinFee) { auto it = feeset.lower_bound(currentMinFee); if ((it != feeset.begin() && insecure_rand.rand32() % 3 != 0) || it == feeset.end()) { it--; } return *it; } diff --git a/src/policy/fees.h b/src/policy/fees.h index 4eb982069b..8a3b00bb37 100644 --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -1,306 +1,299 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core 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 "random.h" #include "uint256.h" #include #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 */ 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 95% of X feerate transactions to be confirmed within Y * blocks for X to be big enough */ static const double MIN_SUCCESS_PCT = .95; /** Require an avg of 1 tx in the combined feerate bucket per block to have stat * significance */ static const double SUFFICIENT_FEETXS = 1; // Minimum and Maximum values for tracking feerates static constexpr Amount MIN_FEERATE(10); static const Amount MAX_FEERATE(int64_t(1e7)); static const Amount INF_FEERATE(MAX_MONEY); static const Amount INF_PRIORITY(int64_t(1e9) * MAX_MONEY); // We have to lump transactions into buckets based on feerate, but we want to be // able to give accurate estimates over a large range of potential feerates. // Therefore it makes sense to exponentially space the buckets /** 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(const CFeeRate &minRelayFee); /** 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); - /** - * Return a priority estimate. - * DEPRECATED - * Returns -1 - */ - double estimatePriority(int confTarget); - /** * Estimate priority needed to get be included in a block within confTarget * blocks. * DEPRECATED * Returns -1 unless mempool is currently limited then returns INF_PRIORITY * answerFoundAtTarget is set to confTarget */ double estimateSmartPriority(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 CFeeRate minTrackedFee; 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: /** Create new FeeFilterRounder */ FeeFilterRounder(const CFeeRate &minIncrementalFee); /** Quantize a minimum fee for privacy purpose before broadcast **/ Amount round(const Amount currentMinFee); private: std::set feeset; FastRandomContext insecure_rand; }; #endif /*BITCOIN_POLICYESTIMATOR_H */ diff --git a/src/rpc/mining.cpp b/src/rpc/mining.cpp index dd36b58d23..1e3632bc31 100644 --- a/src/rpc/mining.cpp +++ b/src/rpc/mining.cpp @@ -1,1066 +1,1035 @@ // Copyright (c) 2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "rpc/mining.h" #include "amount.h" #include "chain.h" #include "chainparams.h" #include "config.h" #include "consensus/consensus.h" #include "consensus/params.h" #include "consensus/validation.h" #include "core_io.h" #include "dstencode.h" #include "init.h" #include "miner.h" #include "net.h" #include "policy/policy.h" #include "pow.h" #include "rpc/blockchain.h" #include "rpc/server.h" #include "txmempool.h" #include "util.h" #include "utilstrencodings.h" #include "validation.h" #include "validationinterface.h" #include #include #include /** * Return average network hashes per second based on the last 'lookup' blocks, * or from the last difficulty change if 'lookup' is nonpositive. If 'height' is * nonnegative, compute the estimate at the time when a given block was found. */ static UniValue GetNetworkHashPS(int lookup, int height) { CBlockIndex *pb = chainActive.Tip(); if (height >= 0 && height < chainActive.Height()) { pb = chainActive[height]; } if (pb == nullptr || !pb->nHeight) { return 0; } // If lookup is -1, then use blocks since last difficulty change. if (lookup <= 0) { lookup = pb->nHeight % Params().GetConsensus().DifficultyAdjustmentInterval() + 1; } // If lookup is larger than chain, then set it to chain length. if (lookup > pb->nHeight) { lookup = pb->nHeight; } CBlockIndex *pb0 = pb; int64_t minTime = pb0->GetBlockTime(); int64_t maxTime = minTime; for (int i = 0; i < lookup; i++) { pb0 = pb0->pprev; int64_t time = pb0->GetBlockTime(); minTime = std::min(time, minTime); maxTime = std::max(time, maxTime); } // In case there's a situation where minTime == maxTime, we don't want a // divide by zero exception. if (minTime == maxTime) { return 0; } arith_uint256 workDiff = pb->nChainWork - pb0->nChainWork; int64_t timeDiff = maxTime - minTime; return workDiff.getdouble() / timeDiff; } static UniValue getnetworkhashps(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() > 2) { throw std::runtime_error( "getnetworkhashps ( nblocks height )\n" "\nReturns the estimated network hashes per second based on the " "last n blocks.\n" "Pass in [blocks] to override # of blocks, -1 specifies since last " "difficulty change.\n" "Pass in [height] to estimate the network speed at the time when a " "certain block was found.\n" "\nArguments:\n" "1. nblocks (numeric, optional, default=120) The number of " "blocks, or -1 for blocks since last difficulty change.\n" "2. height (numeric, optional, default=-1) To estimate at the " "time of the given height.\n" "\nResult:\n" "x (numeric) Hashes per second estimated\n" "\nExamples:\n" + HelpExampleCli("getnetworkhashps", "") + HelpExampleRpc("getnetworkhashps", "")); } LOCK(cs_main); return GetNetworkHashPS( request.params.size() > 0 ? request.params[0].get_int() : 120, request.params.size() > 1 ? request.params[1].get_int() : -1); } UniValue generateBlocks(const Config &config, std::shared_ptr coinbaseScript, int nGenerate, uint64_t nMaxTries, bool keepScript) { static const int nInnerLoopCount = 0x100000; int nHeightStart = 0; int nHeightEnd = 0; int nHeight = 0; { // Don't keep cs_main locked. LOCK(cs_main); nHeightStart = chainActive.Height(); nHeight = nHeightStart; nHeightEnd = nHeightStart + nGenerate; } unsigned int nExtraNonce = 0; UniValue blockHashes(UniValue::VARR); while (nHeight < nHeightEnd) { std::unique_ptr pblocktemplate( BlockAssembler(config).CreateNewBlock( coinbaseScript->reserveScript)); if (!pblocktemplate.get()) { throw JSONRPCError(RPC_INTERNAL_ERROR, "Couldn't create new block"); } CBlock *pblock = &pblocktemplate->block; { LOCK(cs_main); IncrementExtraNonce(config, pblock, chainActive.Tip(), nExtraNonce); } while (nMaxTries > 0 && pblock->nNonce < nInnerLoopCount && !CheckProofOfWork(pblock->GetHash(), pblock->nBits, config)) { ++pblock->nNonce; --nMaxTries; } if (nMaxTries == 0) { break; } if (pblock->nNonce == nInnerLoopCount) { continue; } std::shared_ptr shared_pblock = std::make_shared(*pblock); if (!ProcessNewBlock(config, shared_pblock, true, nullptr)) { throw JSONRPCError(RPC_INTERNAL_ERROR, "ProcessNewBlock, block not accepted"); } ++nHeight; blockHashes.push_back(pblock->GetHash().GetHex()); // Mark script as important because it was used at least for one // coinbase output if the script came from the wallet. if (keepScript) { coinbaseScript->KeepScript(); } } return blockHashes; } static UniValue generatetoaddress(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() < 2 || request.params.size() > 3) { throw std::runtime_error( "generatetoaddress nblocks address (maxtries)\n" "\nMine blocks immediately to a specified address (before the RPC " "call returns)\n" "\nArguments:\n" "1. nblocks (numeric, required) How many blocks are generated " "immediately.\n" "2. address (string, required) The address to send the newly " "generated bitcoin to.\n" "3. maxtries (numeric, optional) How many iterations to try " "(default = 1000000).\n" "\nResult:\n" "[ blockhashes ] (array) hashes of blocks generated\n" "\nExamples:\n" "\nGenerate 11 blocks to myaddress\n" + HelpExampleCli("generatetoaddress", "11 \"myaddress\"")); } int nGenerate = request.params[0].get_int(); uint64_t nMaxTries = 1000000; if (request.params.size() > 2) { nMaxTries = request.params[2].get_int(); } CTxDestination destination = DecodeDestination(request.params[1].get_str(), config.GetChainParams()); if (!IsValidDestination(destination)) { throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Error: Invalid address"); } std::shared_ptr coinbaseScript = std::make_shared(); coinbaseScript->reserveScript = GetScriptForDestination(destination); return generateBlocks(config, coinbaseScript, nGenerate, nMaxTries, false); } static UniValue getmininginfo(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() != 0) { throw std::runtime_error( "getmininginfo\n" "\nReturns a json object containing mining-related information." "\nResult:\n" "{\n" " \"blocks\": nnn, (numeric) The current block\n" " \"currentblocksize\": nnn, (numeric) The last block size\n" " \"currentblocktx\": nnn, (numeric) The last block " "transaction\n" " \"difficulty\": xxx.xxxxx (numeric) The current difficulty\n" " \"errors\": \"...\" (string) Current errors\n" " \"networkhashps\": nnn, (numeric) The network hashes per " "second\n" " \"pooledtx\": n (numeric) The size of the mempool\n" " \"chain\": \"xxxx\", (string) current network name as " "defined in BIP70 (main, test, regtest)\n" "}\n" "\nExamples:\n" + HelpExampleCli("getmininginfo", "") + HelpExampleRpc("getmininginfo", "")); } LOCK(cs_main); UniValue obj(UniValue::VOBJ); obj.push_back(Pair("blocks", int(chainActive.Height()))); obj.push_back(Pair("currentblocksize", uint64_t(nLastBlockSize))); obj.push_back(Pair("currentblocktx", uint64_t(nLastBlockTx))); obj.push_back(Pair("difficulty", double(GetDifficulty(chainActive.Tip())))); obj.push_back( Pair("blockprioritypercentage", uint8_t(gArgs.GetArg("-blockprioritypercentage", DEFAULT_BLOCK_PRIORITY_PERCENTAGE)))); obj.push_back(Pair("errors", GetWarnings("statusbar"))); obj.push_back(Pair("networkhashps", getnetworkhashps(config, request))); obj.push_back(Pair("pooledtx", uint64_t(mempool.size()))); obj.push_back(Pair("chain", config.GetChainParams().NetworkIDString())); return obj; } // NOTE: Unlike wallet RPC (which use BCH values), mining RPCs follow GBT (BIP // 22) in using satoshi amounts static UniValue prioritisetransaction(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() != 3) { throw std::runtime_error( "prioritisetransaction \n" "Accepts the transaction into mined blocks at a higher (or lower) " "priority\n" "\nArguments:\n" "1. \"txid\" (string, required) The transaction id.\n" "2. priority_delta (numeric, required) The priority to add or " "subtract.\n" " The transaction selection algorithm considers " "the tx as it would have a higher priority.\n" " (priority of a transaction is calculated: " "coinage * value_in_satoshis / txsize) \n" "3. fee_delta (numeric, required) The fee value (in satoshis) " "to add (or subtract, if negative).\n" " The fee is not actually paid, only the " "algorithm for selecting transactions into a block\n" " considers the transaction as it would have paid " "a higher (or lower) fee.\n" "\nResult:\n" "true (boolean) Returns true\n" "\nExamples:\n" + HelpExampleCli("prioritisetransaction", "\"txid\" 0.0 10000") + HelpExampleRpc("prioritisetransaction", "\"txid\", 0.0, 10000")); } LOCK(cs_main); uint256 hash = ParseHashStr(request.params[0].get_str(), "txid"); Amount nAmount(request.params[2].get_int64()); mempool.PrioritiseTransaction(hash, request.params[0].get_str(), request.params[1].get_real(), nAmount); return true; } // NOTE: Assumes a conclusive result; if result is inconclusive, it must be // handled by caller static UniValue BIP22ValidationResult(const Config &config, const CValidationState &state) { if (state.IsValid()) { return NullUniValue; } std::string strRejectReason = state.GetRejectReason(); if (state.IsError()) { throw JSONRPCError(RPC_VERIFY_ERROR, strRejectReason); } if (state.IsInvalid()) { if (strRejectReason.empty()) { return "rejected"; } return strRejectReason; } // Should be impossible. return "valid?"; } std::string gbt_vb_name(const Consensus::DeploymentPos pos) { const struct BIP9DeploymentInfo &vbinfo = VersionBitsDeploymentInfo[pos]; std::string s = vbinfo.name; if (!vbinfo.gbt_force) { s.insert(s.begin(), '!'); } return s; } static UniValue getblocktemplate(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() > 1) { throw std::runtime_error( "getblocktemplate ( TemplateRequest )\n" "\nIf the request parameters include a 'mode' key, that is used to " "explicitly select between the default 'template' request or a " "'proposal'.\n" "It returns data needed to construct a block to work on.\n" "For full specification, see BIPs 22, 23, 9, and 145:\n" " " "https://github.com/bitcoin/bips/blob/master/bip-0022.mediawiki\n" " " "https://github.com/bitcoin/bips/blob/master/bip-0023.mediawiki\n" " " "https://github.com/bitcoin/bips/blob/master/" "bip-0009.mediawiki#getblocktemplate_changes\n" " " "https://github.com/bitcoin/bips/blob/master/bip-0145.mediawiki\n" "\nArguments:\n" "1. template_request (json object, optional) A json object " "in the following spec\n" " {\n" " \"mode\":\"template\" (string, optional) This must be " "set to \"template\", \"proposal\" (see BIP 23), or omitted\n" " \"capabilities\":[ (array, optional) A list of " "strings\n" " \"support\" (string) client side supported " "feature, 'longpoll', 'coinbasetxn', 'coinbasevalue', 'proposal', " "'serverlist', 'workid'\n" " ,...\n" " ],\n" " \"rules\":[ (array, optional) A list of " "strings\n" " \"support\" (string) client side supported " "softfork deployment\n" " ,...\n" " ]\n" " }\n" "\n" "\nResult:\n" "{\n" " \"version\" : n, (numeric) The preferred " "block version\n" " \"rules\" : [ \"rulename\", ... ], (array of strings) " "specific block rules that are to be enforced\n" " \"vbavailable\" : { (json object) set of " "pending, supported versionbit (BIP 9) softfork deployments\n" " \"rulename\" : bitnumber (numeric) identifies the " "bit number as indicating acceptance and readiness for the named " "softfork rule\n" " ,...\n" " },\n" " \"vbrequired\" : n, (numeric) bit mask of " "versionbits the server requires set in submissions\n" " \"previousblockhash\" : \"xxxx\", (string) The hash of " "current highest block\n" " \"transactions\" : [ (array) contents of " "non-coinbase transactions that should be included in the next " "block\n" " {\n" " \"data\" : \"xxxx\", (string) transaction " "data encoded in hexadecimal (byte-for-byte)\n" " \"txid\" : \"xxxx\", (string) transaction id " "encoded in little-endian hexadecimal\n" " \"hash\" : \"xxxx\", (string) hash encoded " "in little-endian hexadecimal (including witness data)\n" " \"depends\" : [ (array) array of numbers " "\n" " n (numeric) transactions " "before this one (by 1-based index in 'transactions' list) that " "must be present in the final block if this one is\n" " ,...\n" " ],\n" " \"fee\": n, (numeric) difference in " "value between transaction inputs and outputs (in Satoshis); for " "coinbase transactions, this is a negative Number of the total " "collected block fees (ie, not including the block subsidy); if " "key is not present, fee is unknown and clients MUST NOT assume " "there isn't one\n" " \"sigops\" : n, (numeric) total SigOps " "cost, as counted for purposes of block limits; if key is not " "present, sigop cost is unknown and clients MUST NOT assume it is " "zero\n" " \"required\" : true|false (boolean) if provided and " "true, this transaction must be in the final block\n" " }\n" " ,...\n" " ],\n" " \"coinbaseaux\" : { (json object) data that " "should be included in the coinbase's scriptSig content\n" " \"flags\" : \"xx\" (string) key name is to " "be ignored, and value included in scriptSig\n" " },\n" " \"coinbasevalue\" : n, (numeric) maximum allowable " "input to coinbase transaction, including the generation award and " "transaction fees (in Satoshis)\n" " \"coinbasetxn\" : { ... }, (json object) information " "for coinbase transaction\n" " \"target\" : \"xxxx\", (string) The hash target\n" " \"mintime\" : xxx, (numeric) The minimum " "timestamp appropriate for next block time in seconds since epoch " "(Jan 1 1970 GMT)\n" " \"mutable\" : [ (array of string) list of " "ways the block template may be changed \n" " \"value\" (string) A way the block " "template may be changed, e.g. 'time', 'transactions', " "'prevblock'\n" " ,...\n" " ],\n" " \"noncerange\" : \"00000000ffffffff\",(string) A range of valid " "nonces\n" " \"sigoplimit\" : n, (numeric) limit of sigops " "in blocks\n" " \"sizelimit\" : n, (numeric) limit of block " "size\n" " \"curtime\" : ttt, (numeric) current timestamp " "in seconds since epoch (Jan 1 1970 GMT)\n" " \"bits\" : \"xxxxxxxx\", (string) compressed " "target of next block\n" " \"height\" : n (numeric) The height of the " "next block\n" "}\n" "\nExamples:\n" + HelpExampleCli("getblocktemplate", "") + HelpExampleRpc("getblocktemplate", "")); } LOCK(cs_main); std::string strMode = "template"; UniValue lpval = NullUniValue; std::set setClientRules; int64_t nMaxVersionPreVB = -1; if (request.params.size() > 0) { const UniValue &oparam = request.params[0].get_obj(); const UniValue &modeval = find_value(oparam, "mode"); if (modeval.isStr()) { strMode = modeval.get_str(); } else if (modeval.isNull()) { /* Do nothing */ } else { throw JSONRPCError(RPC_INVALID_PARAMETER, "Invalid mode"); } lpval = find_value(oparam, "longpollid"); if (strMode == "proposal") { const UniValue &dataval = find_value(oparam, "data"); if (!dataval.isStr()) { throw JSONRPCError(RPC_TYPE_ERROR, "Missing data String key for proposal"); } CBlock block; if (!DecodeHexBlk(block, dataval.get_str())) { throw JSONRPCError(RPC_DESERIALIZATION_ERROR, "Block decode failed"); } uint256 hash = block.GetHash(); BlockMap::iterator mi = mapBlockIndex.find(hash); if (mi != mapBlockIndex.end()) { CBlockIndex *pindex = mi->second; if (pindex->IsValid(BLOCK_VALID_SCRIPTS)) { return "duplicate"; } if (pindex->nStatus & BLOCK_FAILED_MASK) { return "duplicate-invalid"; } return "duplicate-inconclusive"; } CBlockIndex *const pindexPrev = chainActive.Tip(); // TestBlockValidity only supports blocks built on the current Tip if (block.hashPrevBlock != pindexPrev->GetBlockHash()) { return "inconclusive-not-best-prevblk"; } CValidationState state; BlockValidationOptions validationOptions = BlockValidationOptions(false, true); TestBlockValidity(config, state, block, pindexPrev, validationOptions); return BIP22ValidationResult(config, state); } const UniValue &aClientRules = find_value(oparam, "rules"); if (aClientRules.isArray()) { for (size_t i = 0; i < aClientRules.size(); ++i) { const UniValue &v = aClientRules[i]; setClientRules.insert(v.get_str()); } } else { // NOTE: It is important that this NOT be read if versionbits is // supported const UniValue &uvMaxVersion = find_value(oparam, "maxversion"); if (uvMaxVersion.isNum()) { nMaxVersionPreVB = uvMaxVersion.get_int64(); } } } if (strMode != "template") { throw JSONRPCError(RPC_INVALID_PARAMETER, "Invalid mode"); } if (!g_connman) { throw JSONRPCError( RPC_CLIENT_P2P_DISABLED, "Error: Peer-to-peer functionality missing or disabled"); } if (g_connman->GetNodeCount(CConnman::CONNECTIONS_ALL) == 0) { throw JSONRPCError(RPC_CLIENT_NOT_CONNECTED, "Bitcoin is not connected!"); } if (IsInitialBlockDownload()) { throw JSONRPCError(RPC_CLIENT_IN_INITIAL_DOWNLOAD, "Bitcoin is downloading blocks..."); } static unsigned int nTransactionsUpdatedLast; if (!lpval.isNull()) { // Wait to respond until either the best block changes, OR a minute has // passed and there are more transactions uint256 hashWatchedChain; boost::system_time checktxtime; unsigned int nTransactionsUpdatedLastLP; if (lpval.isStr()) { // Format: std::string lpstr = lpval.get_str(); hashWatchedChain.SetHex(lpstr.substr(0, 64)); nTransactionsUpdatedLastLP = atoi64(lpstr.substr(64)); } else { // NOTE: Spec does not specify behaviour for non-string longpollid, // but this makes testing easier hashWatchedChain = chainActive.Tip()->GetBlockHash(); nTransactionsUpdatedLastLP = nTransactionsUpdatedLast; } // Release the wallet and main lock while waiting LEAVE_CRITICAL_SECTION(cs_main); { checktxtime = boost::get_system_time() + boost::posix_time::minutes(1); boost::unique_lock lock(csBestBlock); while (chainActive.Tip()->GetBlockHash() == hashWatchedChain && IsRPCRunning()) { if (!cvBlockChange.timed_wait(lock, checktxtime)) { // Timeout: Check transactions for update if (mempool.GetTransactionsUpdated() != nTransactionsUpdatedLastLP) { break; } checktxtime += boost::posix_time::seconds(10); } } } ENTER_CRITICAL_SECTION(cs_main); if (!IsRPCRunning()) { throw JSONRPCError(RPC_CLIENT_NOT_CONNECTED, "Shutting down"); } // TODO: Maybe recheck connections/IBD and (if something wrong) send an // expires-immediately template to stop miners? } // Update block static CBlockIndex *pindexPrev; static int64_t nStart; static std::unique_ptr pblocktemplate; if (pindexPrev != chainActive.Tip() || (mempool.GetTransactionsUpdated() != nTransactionsUpdatedLast && GetTime() - nStart > 5)) { // Clear pindexPrev so future calls make a new block, despite any // failures from here on pindexPrev = nullptr; // Store the pindexBest used before CreateNewBlock, to avoid races nTransactionsUpdatedLast = mempool.GetTransactionsUpdated(); CBlockIndex *pindexPrevNew = chainActive.Tip(); nStart = GetTime(); // Create new block CScript scriptDummy = CScript() << OP_TRUE; pblocktemplate = BlockAssembler(config).CreateNewBlock(scriptDummy); if (!pblocktemplate) { throw JSONRPCError(RPC_OUT_OF_MEMORY, "Out of memory"); } // Need to update only after we know CreateNewBlock succeeded pindexPrev = pindexPrevNew; } // pointer for convenience CBlock *pblock = &pblocktemplate->block; const Consensus::Params &consensusParams = config.GetChainParams().GetConsensus(); // Update nTime UpdateTime(pblock, config, pindexPrev); pblock->nNonce = 0; UniValue aCaps(UniValue::VARR); aCaps.push_back("proposal"); UniValue transactions(UniValue::VARR); std::map setTxIndex; int i = 0; for (const auto &it : pblock->vtx) { const CTransaction &tx = *it; uint256 txId = tx.GetId(); setTxIndex[txId] = i++; if (tx.IsCoinBase()) { continue; } UniValue entry(UniValue::VOBJ); entry.push_back(Pair("data", EncodeHexTx(tx))); entry.push_back(Pair("txid", txId.GetHex())); entry.push_back(Pair("hash", tx.GetHash().GetHex())); UniValue deps(UniValue::VARR); for (const CTxIn &in : tx.vin) { if (setTxIndex.count(in.prevout.hash)) deps.push_back(setTxIndex[in.prevout.hash]); } entry.push_back(Pair("depends", deps)); int index_in_template = i - 1; entry.push_back(Pair( "fee", pblocktemplate->vTxFees[index_in_template].GetSatoshis())); int64_t nTxSigOps = pblocktemplate->vTxSigOpsCount[index_in_template]; entry.push_back(Pair("sigops", nTxSigOps)); transactions.push_back(entry); } UniValue aux(UniValue::VOBJ); aux.push_back( Pair("flags", HexStr(COINBASE_FLAGS.begin(), COINBASE_FLAGS.end()))); arith_uint256 hashTarget = arith_uint256().SetCompact(pblock->nBits); UniValue aMutable(UniValue::VARR); aMutable.push_back("time"); aMutable.push_back("transactions"); aMutable.push_back("prevblock"); UniValue result(UniValue::VOBJ); result.push_back(Pair("capabilities", aCaps)); UniValue aRules(UniValue::VARR); UniValue vbavailable(UniValue::VOBJ); for (int j = 0; j < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; ++j) { Consensus::DeploymentPos pos = Consensus::DeploymentPos(j); ThresholdState state = VersionBitsState(pindexPrev, consensusParams, pos, versionbitscache); switch (state) { case THRESHOLD_DEFINED: case THRESHOLD_FAILED: // Not exposed to GBT at all break; case THRESHOLD_LOCKED_IN: { // Ensure bit is set in block version, then fallthrough to get // vbavailable set. pblock->nVersion |= VersionBitsMask(consensusParams, pos); } // FALLTHROUGH case THRESHOLD_STARTED: { const struct BIP9DeploymentInfo &vbinfo = VersionBitsDeploymentInfo[pos]; vbavailable.push_back(Pair( gbt_vb_name(pos), consensusParams.vDeployments[pos].bit)); if (setClientRules.find(vbinfo.name) == setClientRules.end()) { if (!vbinfo.gbt_force) { // If the client doesn't support this, don't indicate it // in the [default] version pblock->nVersion &= ~VersionBitsMask(consensusParams, pos); } } break; } case THRESHOLD_ACTIVE: { // Add to rules only const struct BIP9DeploymentInfo &vbinfo = VersionBitsDeploymentInfo[pos]; aRules.push_back(gbt_vb_name(pos)); if (setClientRules.find(vbinfo.name) == setClientRules.end()) { // Not supported by the client; make sure it's safe to // proceed if (!vbinfo.gbt_force) { // If we do anything other than throw an exception here, // be sure version/force isn't sent to old clients throw JSONRPCError( RPC_INVALID_PARAMETER, strprintf("Support for '%s' rule requires explicit " "client support", vbinfo.name)); } } break; } } } result.push_back(Pair("version", pblock->nVersion)); result.push_back(Pair("rules", aRules)); result.push_back(Pair("vbavailable", vbavailable)); result.push_back(Pair("vbrequired", int(0))); if (nMaxVersionPreVB >= 2) { // If VB is supported by the client, nMaxVersionPreVB is -1, so we won't // get here. Because BIP 34 changed how the generation transaction is // serialized, we can only use version/force back to v2 blocks. This is // safe to do [otherwise-]unconditionally only because we are throwing // an exception above if a non-force deployment gets activated. Note // that this can probably also be removed entirely after the first BIP9 // non-force deployment (ie, probably segwit) gets activated. aMutable.push_back("version/force"); } result.push_back(Pair("previousblockhash", pblock->hashPrevBlock.GetHex())); result.push_back(Pair("transactions", transactions)); result.push_back(Pair("coinbaseaux", aux)); result.push_back( Pair("coinbasevalue", (int64_t)pblock->vtx[0]->vout[0].nValue.GetSatoshis())); result.push_back(Pair("longpollid", chainActive.Tip()->GetBlockHash().GetHex() + i64tostr(nTransactionsUpdatedLast))); result.push_back(Pair("target", hashTarget.GetHex())); result.push_back( Pair("mintime", (int64_t)pindexPrev->GetMedianTimePast() + 1)); result.push_back(Pair("mutable", aMutable)); result.push_back(Pair("noncerange", "00000000ffffffff")); // FIXME: Allow for mining block greater than 1M. result.push_back( Pair("sigoplimit", GetMaxBlockSigOpsCount(DEFAULT_MAX_BLOCK_SIZE))); result.push_back(Pair("sizelimit", DEFAULT_MAX_BLOCK_SIZE)); result.push_back(Pair("curtime", pblock->GetBlockTime())); result.push_back(Pair("bits", strprintf("%08x", pblock->nBits))); result.push_back(Pair("height", (int64_t)(pindexPrev->nHeight + 1))); return result; } class submitblock_StateCatcher : public CValidationInterface { public: uint256 hash; bool found; CValidationState state; submitblock_StateCatcher(const uint256 &hashIn) : hash(hashIn), found(false), state() {} protected: void BlockChecked(const CBlock &block, const CValidationState &stateIn) override { if (block.GetHash() != hash) { return; } found = true; state = stateIn; } }; static UniValue submitblock(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() < 1 || request.params.size() > 2) { throw std::runtime_error( "submitblock \"hexdata\" ( \"jsonparametersobject\" )\n" "\nAttempts to submit new block to network.\n" "The 'jsonparametersobject' parameter is currently ignored.\n" "See https://en.bitcoin.it/wiki/BIP_0022 for full specification.\n" "\nArguments\n" "1. \"hexdata\" (string, required) the hex-encoded block " "data to submit\n" "2. \"parameters\" (string, optional) object of optional " "parameters\n" " {\n" " \"workid\" : \"id\" (string, optional) if the server " "provided a workid, it MUST be included with submissions\n" " }\n" "\nResult:\n" "\nExamples:\n" + HelpExampleCli("submitblock", "\"mydata\"") + HelpExampleRpc("submitblock", "\"mydata\"")); } std::shared_ptr blockptr = std::make_shared(); CBlock &block = *blockptr; if (!DecodeHexBlk(block, request.params[0].get_str())) { throw JSONRPCError(RPC_DESERIALIZATION_ERROR, "Block decode failed"); } if (block.vtx.empty() || !block.vtx[0]->IsCoinBase()) { throw JSONRPCError(RPC_DESERIALIZATION_ERROR, "Block does not start with a coinbase"); } uint256 hash = block.GetHash(); bool fBlockPresent = false; { LOCK(cs_main); BlockMap::iterator mi = mapBlockIndex.find(hash); if (mi != mapBlockIndex.end()) { CBlockIndex *pindex = mi->second; if (pindex->IsValid(BLOCK_VALID_SCRIPTS)) { return "duplicate"; } if (pindex->nStatus & BLOCK_FAILED_MASK) { return "duplicate-invalid"; } // Otherwise, we might only have the header - process the block // before returning fBlockPresent = true; } } submitblock_StateCatcher sc(block.GetHash()); RegisterValidationInterface(&sc); bool fAccepted = ProcessNewBlock(config, blockptr, true, nullptr); UnregisterValidationInterface(&sc); if (fBlockPresent) { if (fAccepted && !sc.found) { return "duplicate-inconclusive"; } return "duplicate"; } if (!sc.found) { return "inconclusive"; } return BIP22ValidationResult(config, sc.state); } static UniValue estimatefee(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() != 1) { throw std::runtime_error( "estimatefee nblocks\n" "\nEstimates the approximate fee per kilobyte needed for a " "transaction to begin\n" "confirmation within nblocks blocks.\n" "\nArguments:\n" "1. nblocks (numeric, required)\n" "\nResult:\n" "n (numeric) estimated fee-per-kilobyte\n" "\n" "A negative value is returned if not enough transactions and " "blocks\n" "have been observed to make an estimate.\n" "-1 is always returned for nblocks == 1 as it is impossible to " "calculate\n" "a fee that is high enough to get reliably included in the next " "block.\n" "\nExample:\n" + HelpExampleCli("estimatefee", "6")); } RPCTypeCheck(request.params, {UniValue::VNUM}); int nBlocks = request.params[0].get_int(); if (nBlocks < 1) { nBlocks = 1; } CFeeRate feeRate = mempool.estimateFee(nBlocks); if (feeRate == CFeeRate(Amount(0))) { return -1.0; } return ValueFromAmount(feeRate.GetFeePerK()); } -static UniValue estimatepriority(const Config &config, - const JSONRPCRequest &request) { - if (request.fHelp || request.params.size() != 1) { - throw std::runtime_error( - "estimatepriority nblocks\n" - "\nDEPRECATED. Estimates the approximate priority " - "a zero-fee transaction needs to begin\n" - "confirmation within nblocks blocks.\n" - "\nArguments:\n" - "1. nblocks (numeric, required)\n" - "\nResult:\n" - "n (numeric) estimated priority\n" - "\n" - "A negative value is returned if not enough " - "transactions and blocks\n" - "have been observed to make an estimate.\n" - "\nExample:\n" + - HelpExampleCli("estimatepriority", "6")); - } - - RPCTypeCheck(request.params, {UniValue::VNUM}); - - int nBlocks = request.params[0].get_int(); - if (nBlocks < 1) { - nBlocks = 1; - } - - return mempool.estimatePriority(nBlocks); -} - static UniValue estimatesmartfee(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() != 1) { throw std::runtime_error( "estimatesmartfee nblocks\n" "\nWARNING: This interface is unstable and may disappear or " "change!\n" "\nEstimates the approximate fee per kilobyte needed for a " "transaction to begin\n" "confirmation within nblocks blocks if possible and return the " "number of blocks\n" "for which the estimate is valid.\n" "\nArguments:\n" "1. nblocks (numeric)\n" "\nResult:\n" "{\n" " \"feerate\" : x.x, (numeric) estimate fee-per-kilobyte (in " "BCH)\n" " \"blocks\" : n (numeric) block number where estimate " "was found\n" "}\n" "\n" "A negative value is returned if not enough transactions and " "blocks\n" "have been observed to make an estimate for any number of blocks.\n" "However it will not return a value below the mempool reject fee.\n" "\nExample:\n" + HelpExampleCli("estimatesmartfee", "6")); } RPCTypeCheck(request.params, {UniValue::VNUM}); int nBlocks = request.params[0].get_int(); UniValue result(UniValue::VOBJ); int answerFound; CFeeRate feeRate = mempool.estimateSmartFee(nBlocks, &answerFound); result.push_back(Pair("feerate", feeRate == CFeeRate(Amount(0)) ? -1.0 : ValueFromAmount(feeRate.GetFeePerK()))); result.push_back(Pair("blocks", answerFound)); return result; } static UniValue estimatesmartpriority(const Config &config, const JSONRPCRequest &request) { if (request.fHelp || request.params.size() != 1) { throw std::runtime_error( "estimatesmartpriority nblocks\n" "\nDEPRECATED. WARNING: This interface is unstable and may " "disappear or change!\n" "\nEstimates the approximate priority a zero-fee transaction needs " "to begin\n" "confirmation within nblocks blocks if possible and return the " "number of blocks\n" "for which the estimate is valid.\n" "\nArguments:\n" "1. nblocks (numeric, required)\n" "\nResult:\n" "{\n" " \"priority\" : x.x, (numeric) estimated priority\n" " \"blocks\" : n (numeric) block number where estimate " "was found\n" "}\n" "\n" "A negative value is returned if not enough transactions and " "blocks\n" "have been observed to make an estimate for any number of blocks.\n" "However if the mempool reject fee is set it will return 1e9 * " "MAX_MONEY.\n" "\nExample:\n" + HelpExampleCli("estimatesmartpriority", "6")); } RPCTypeCheck(request.params, {UniValue::VNUM}); int nBlocks = request.params[0].get_int(); UniValue result(UniValue::VOBJ); int answerFound; double priority = mempool.estimateSmartPriority(nBlocks, &answerFound); result.push_back(Pair("priority", priority)); result.push_back(Pair("blocks", answerFound)); return result; } // clang-format off static const CRPCCommand commands[] = { // category name actor (function) okSafeMode // ---------- ------------------------ ---------------------- ---------- {"mining", "getnetworkhashps", getnetworkhashps, true, {"nblocks", "height"}}, {"mining", "getmininginfo", getmininginfo, true, {}}, {"mining", "prioritisetransaction", prioritisetransaction, true, {"txid", "priority_delta", "fee_delta"}}, {"mining", "getblocktemplate", getblocktemplate, true, {"template_request"}}, {"mining", "submitblock", submitblock, true, {"hexdata", "parameters"}}, {"generating", "generatetoaddress", generatetoaddress, true, {"nblocks", "address", "maxtries"}}, {"util", "estimatefee", estimatefee, true, {"nblocks"}}, - {"util", "estimatepriority", estimatepriority, true, {"nblocks"}}, {"util", "estimatesmartfee", estimatesmartfee, true, {"nblocks"}}, {"util", "estimatesmartpriority", estimatesmartpriority, true, {"nblocks"}}, }; // clang-format on void RegisterMiningRPCCommands(CRPCTable &t) { for (unsigned int vcidx = 0; vcidx < ARRAYLEN(commands); vcidx++) t.appendCommand(commands[vcidx].name, &commands[vcidx]); } diff --git a/src/txmempool.cpp b/src/txmempool.cpp index 22f966f742..2eb236ba4c 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1,1270 +1,1266 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "txmempool.h" #include "chainparams.h" // for GetConsensus. #include "clientversion.h" #include "consensus/consensus.h" #include "consensus/validation.h" #include "policy/fees.h" #include "policy/policy.h" #include "streams.h" #include "timedata.h" #include "util.h" #include "utilmoneystr.h" #include "utiltime.h" #include "validation.h" #include "version.h" #include CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef &_tx, const Amount _nFee, int64_t _nTime, double _entryPriority, unsigned int _entryHeight, Amount _inChainInputValue, bool _spendsCoinbase, int64_t _sigOpsCount, LockPoints lp) : tx(_tx), nFee(_nFee), nTime(_nTime), entryPriority(_entryPriority), entryHeight(_entryHeight), inChainInputValue(_inChainInputValue), spendsCoinbase(_spendsCoinbase), sigOpCount(_sigOpsCount), lockPoints(lp) { nTxSize = tx->GetTotalSize(); nModSize = tx->CalculateModifiedSize(GetTxSize()); nUsageSize = RecursiveDynamicUsage(tx); nCountWithDescendants = 1; nSizeWithDescendants = GetTxSize(); nModFeesWithDescendants = nFee; Amount nValueIn = tx->GetValueOut() + nFee; assert(inChainInputValue <= nValueIn); feeDelta = Amount(0); nCountWithAncestors = 1; nSizeWithAncestors = GetTxSize(); nModFeesWithAncestors = nFee; nSigOpCountWithAncestors = sigOpCount; } CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry &other) { *this = other; } double CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const { double deltaPriority = double((currentHeight - entryHeight) * inChainInputValue.GetSatoshis()) / nModSize; double dResult = entryPriority + deltaPriority; // This should only happen if it was called with a height below entry height if (dResult < 0) { dResult = 0; } return dResult; } void CTxMemPoolEntry::UpdateFeeDelta(Amount newFeeDelta) { nModFeesWithDescendants += newFeeDelta - feeDelta; nModFeesWithAncestors += newFeeDelta - feeDelta; feeDelta = newFeeDelta; } void CTxMemPoolEntry::UpdateLockPoints(const LockPoints &lp) { lockPoints = lp; } // Update the given tx for any in-mempool descendants. // Assumes that setMemPoolChildren is correct for the given tx and all // descendants. void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set &setExclude) { setEntries stageEntries, setAllDescendants; stageEntries = GetMemPoolChildren(updateIt); while (!stageEntries.empty()) { const txiter cit = *stageEntries.begin(); setAllDescendants.insert(cit); stageEntries.erase(cit); const setEntries &setChildren = GetMemPoolChildren(cit); for (const txiter childEntry : setChildren) { cacheMap::iterator cacheIt = cachedDescendants.find(childEntry); if (cacheIt != cachedDescendants.end()) { // We've already calculated this one, just add the entries for // this set but don't traverse again. for (const txiter cacheEntry : cacheIt->second) { setAllDescendants.insert(cacheEntry); } } else if (!setAllDescendants.count(childEntry)) { // Schedule for later processing stageEntries.insert(childEntry); } } } // setAllDescendants now contains all in-mempool descendants of updateIt. // Update and add to cached descendant map int64_t modifySize = 0; Amount modifyFee(0); int64_t modifyCount = 0; for (txiter cit : setAllDescendants) { if (!setExclude.count(cit->GetTx().GetId())) { modifySize += cit->GetTxSize(); modifyFee += cit->GetModifiedFee(); modifyCount++; cachedDescendants[updateIt].insert(cit); // Update ancestor state for each descendant mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCount())); } } mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount)); } // vHashesToUpdate is the set of transaction hashes from a disconnected block // which has been re-added to the mempool. For each entry, look for descendants // that are outside hashesToUpdate, and add fee/size information for such // descendants to the parent. For each such descendant, also update the ancestor // state to include the parent. void CTxMemPool::UpdateTransactionsFromBlock( const std::vector &vHashesToUpdate) { LOCK(cs); // For each entry in vHashesToUpdate, store the set of in-mempool, but not // in-vHashesToUpdate transactions, so that we don't have to recalculate // descendants when we come across a previously seen entry. cacheMap mapMemPoolDescendantsToUpdate; // Use a set for lookups into vHashesToUpdate (these entries are already // accounted for in the state of their ancestors) std::set setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end()); // Iterate in reverse, so that whenever we are looking at at a transaction // we are sure that all in-mempool descendants have already been processed. // This maximizes the benefit of the descendant cache and guarantees that // setMemPoolChildren will be updated, an assumption made in // UpdateForDescendants. for (const uint256 &hash : boost::adaptors::reverse(vHashesToUpdate)) { // we cache the in-mempool children to avoid duplicate updates setEntries setChildren; // calculate children from mapNextTx txiter it = mapTx.find(hash); if (it == mapTx.end()) { continue; } auto iter = mapNextTx.lower_bound(COutPoint(hash, 0)); // First calculate the children, and update setMemPoolChildren to // include them, and update their setMemPoolParents to include this tx. for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) { const uint256 &childHash = iter->second->GetId(); txiter childIter = mapTx.find(childHash); assert(childIter != mapTx.end()); // We can skip updating entries we've encountered before or that are // in the block (which are already accounted for). if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) { UpdateChild(it, childIter, true); UpdateParent(childIter, it, true); } } UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded); } } bool CTxMemPool::CalculateMemPoolAncestors( const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents /* = true */) const { LOCK(cs); setEntries parentHashes; const CTransaction &tx = entry.GetTx(); if (fSearchForParents) { // Get parents of this transaction that are in the mempool // GetMemPoolParents() is only valid for entries in the mempool, so we // iterate mapTx to find parents. for (const CTxIn &in : tx.vin) { txiter piter = mapTx.find(in.prevout.hash); if (piter == mapTx.end()) { continue; } parentHashes.insert(piter); if (parentHashes.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount); return false; } } } else { // If we're not searching for parents, we require this to be an entry in // the mempool already. txiter it = mapTx.iterator_to(entry); parentHashes = GetMemPoolParents(it); } size_t totalSizeWithAncestors = entry.GetTxSize(); while (!parentHashes.empty()) { txiter stageit = *parentHashes.begin(); setAncestors.insert(stageit); parentHashes.erase(stageit); totalSizeWithAncestors += stageit->GetTxSize(); if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) { errString = strprintf( "exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetId().ToString(), limitDescendantSize); return false; } if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) { errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetId().ToString(), limitDescendantCount); return false; } if (totalSizeWithAncestors > limitAncestorSize) { errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize); return false; } const setEntries &setMemPoolParents = GetMemPoolParents(stageit); for (const txiter &phash : setMemPoolParents) { // If this is a new ancestor, add it. if (setAncestors.count(phash) == 0) { parentHashes.insert(phash); } if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount); return false; } } } return true; } void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors) { setEntries parentIters = GetMemPoolParents(it); // add or remove this tx as a child of each parent for (txiter piter : parentIters) { UpdateChild(piter, it, add); } const int64_t updateCount = (add ? 1 : -1); const int64_t updateSize = updateCount * it->GetTxSize(); const Amount updateFee = updateCount * it->GetModifiedFee(); for (txiter ancestorIt : setAncestors) { mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount)); } } void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) { int64_t updateCount = setAncestors.size(); int64_t updateSize = 0; Amount updateFee(0); int64_t updateSigOpsCount = 0; for (txiter ancestorIt : setAncestors) { updateSize += ancestorIt->GetTxSize(); updateFee += ancestorIt->GetModifiedFee(); updateSigOpsCount += ancestorIt->GetSigOpCount(); } mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOpsCount)); } void CTxMemPool::UpdateChildrenForRemoval(txiter it) { const setEntries &setMemPoolChildren = GetMemPoolChildren(it); for (txiter updateIt : setMemPoolChildren) { UpdateParent(updateIt, it, false); } } void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) { // For each entry, walk back all ancestors and decrement size associated // with this transaction. const uint64_t nNoLimit = std::numeric_limits::max(); if (updateDescendants) { // updateDescendants should be true whenever we're not recursively // removing a tx and all its descendants, eg when a transaction is // confirmed in a block. Here we only update statistics and not data in // mapLinks (which we need to preserve until we're finished with all // operations that need to traverse the mempool). for (txiter removeIt : entriesToRemove) { setEntries setDescendants; CalculateDescendants(removeIt, setDescendants); setDescendants.erase(removeIt); // don't update state for self int64_t modifySize = -((int64_t)removeIt->GetTxSize()); Amount modifyFee = -1 * removeIt->GetModifiedFee(); int modifySigOps = -removeIt->GetSigOpCount(); for (txiter dit : setDescendants) { mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps)); } } } for (txiter removeIt : entriesToRemove) { setEntries setAncestors; const CTxMemPoolEntry &entry = *removeIt; std::string dummy; // Since this is a tx that is already in the mempool, we can call CMPA // with fSearchForParents = false. If the mempool is in a consistent // state, then using true or false should both be correct, though false // should be a bit faster. // However, if we happen to be in the middle of processing a reorg, then // the mempool can be in an inconsistent state. In this case, the set of // ancestors reachable via mapLinks will be the same as the set of // ancestors whose packages include this transaction, because when we // add a new transaction to the mempool in addUnchecked(), we assume it // has no children, and in the case of a reorg where that assumption is // false, the in-mempool children aren't linked to the in-block tx's // until UpdateTransactionsFromBlock() is called. So if we're being // called during a reorg, ie before UpdateTransactionsFromBlock() has // been called, then mapLinks[] will differ from the set of mempool // parents we'd calculate by searching, and it's important that we use // the mapLinks[] notion of ancestor transactions as the set of things // to update for removal. CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false); // Note that UpdateAncestorsOf severs the child links that point to // removeIt in the entries for the parents of removeIt. UpdateAncestorsOf(false, removeIt, setAncestors); } // After updating all the ancestor sizes, we can now sever the link between // each transaction being removed and any mempool children (ie, update // setMemPoolParents for each direct child of a transaction being removed). for (txiter removeIt : entriesToRemove) { UpdateChildrenForRemoval(removeIt); } } void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, Amount modifyFee, int64_t modifyCount) { nSizeWithDescendants += modifySize; assert(int64_t(nSizeWithDescendants) > 0); nModFeesWithDescendants += modifyFee; nCountWithDescendants += modifyCount; assert(int64_t(nCountWithDescendants) > 0); } void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, Amount modifyFee, int64_t modifyCount, int modifySigOps) { nSizeWithAncestors += modifySize; assert(int64_t(nSizeWithAncestors) > 0); nModFeesWithAncestors += modifyFee; nCountWithAncestors += modifyCount; assert(int64_t(nCountWithAncestors) > 0); nSigOpCountWithAncestors += modifySigOps; assert(int(nSigOpCountWithAncestors) >= 0); } CTxMemPool::CTxMemPool(const CFeeRate &_minReasonableRelayFee) : nTransactionsUpdated(0) { // lock free clear _clear(); // Sanity checks off by default for performance, because otherwise accepting // transactions becomes O(N^2) where N is the number of transactions in the // pool nCheckFrequency = 0; minerPolicyEstimator = new CBlockPolicyEstimator(_minReasonableRelayFee); } CTxMemPool::~CTxMemPool() { delete minerPolicyEstimator; } bool CTxMemPool::isSpent(const COutPoint &outpoint) { LOCK(cs); return mapNextTx.count(outpoint); } unsigned int CTxMemPool::GetTransactionsUpdated() const { LOCK(cs); return nTransactionsUpdated; } void CTxMemPool::AddTransactionsUpdated(unsigned int n) { LOCK(cs); nTransactionsUpdated += n; } bool CTxMemPool::addUnchecked(const uint256 &hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate) { NotifyEntryAdded(entry.GetSharedTx()); // Add to memory pool without checking anything. // Used by AcceptToMemoryPool(), which DOES do all the appropriate checks. LOCK(cs); indexed_transaction_set::iterator newit = mapTx.insert(entry).first; mapLinks.insert(make_pair(newit, TxLinks())); // Update transaction for any feeDelta created by PrioritiseTransaction // TODO: refactor so that the fee delta is calculated before inserting into // mapTx. std::map>::const_iterator pos = mapDeltas.find(hash); if (pos != mapDeltas.end()) { const std::pair &deltas = pos->second; if (deltas.second != Amount(0)) { mapTx.modify(newit, update_fee_delta(deltas.second)); } } // Update cachedInnerUsage to include contained transaction's usage. // (When we update the entry for in-mempool parents, memory usage will be // further updated.) cachedInnerUsage += entry.DynamicMemoryUsage(); const CTransaction &tx = newit->GetTx(); std::set setParentTransactions; for (const CTxIn &in : tx.vin) { mapNextTx.insert(std::make_pair(&in.prevout, &tx)); setParentTransactions.insert(in.prevout.hash); } // Don't bother worrying about child transactions of this one. Normal case // of a new transaction arriving is that there can't be any children, // because such children would be orphans. An exception to that is if a // transaction enters that used to be in a block. In that case, our // disconnect block logic will call UpdateTransactionsFromBlock to clean up // the mess we're leaving here. // Update ancestors with information about this tx for (const uint256 &phash : setParentTransactions) { txiter pit = mapTx.find(phash); if (pit != mapTx.end()) { UpdateParent(newit, pit, true); } } UpdateAncestorsOf(true, newit, setAncestors); UpdateEntryForAncestors(newit, setAncestors); nTransactionsUpdated++; totalTxSize += entry.GetTxSize(); minerPolicyEstimator->processTransaction(entry, validFeeEstimate); vTxHashes.emplace_back(tx.GetHash(), newit); newit->vTxHashesIdx = vTxHashes.size() - 1; return true; } 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); } if (vTxHashes.size() > 1) { vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back()); vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx; vTxHashes.pop_back(); if (vTxHashes.size() * 2 < vTxHashes.capacity()) { vTxHashes.shrink_to_fit(); } } else { vTxHashes.clear(); } totalTxSize -= it->GetTxSize(); cachedInnerUsage -= it->DynamicMemoryUsage(); cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children); mapLinks.erase(it); mapTx.erase(it); nTransactionsUpdated++; minerPolicyEstimator->removeTx(txid); } // Calculates descendants of entry that are not already in setDescendants, and // adds to setDescendants. Assumes entryit is already a tx in the mempool and // setMemPoolChildren is correct for tx and all descendants. Also assumes that // if an entry is in setDescendants already, then all in-mempool descendants of // it are already in setDescendants as well, so that we can save time by not // iterating over those entries. void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants) { setEntries stage; if (setDescendants.count(entryit) == 0) { stage.insert(entryit); } // Traverse down the children of entry, only adding children that are not // accounted for in setDescendants already (because those children have // either already been walked, or will be walked in this iteration). while (!stage.empty()) { txiter it = *stage.begin(); setDescendants.insert(it); stage.erase(it); const setEntries &setChildren = GetMemPoolChildren(it); for (const txiter &childiter : setChildren) { if (!setDescendants.count(childiter)) { stage.insert(childiter); } } } } void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason) { // Remove transaction from memory pool. LOCK(cs); setEntries txToRemove; txiter origit = mapTx.find(origTx.GetId()); if (origit != mapTx.end()) { txToRemove.insert(origit); } else { // When recursively removing but origTx isn't in the mempool be sure to // remove any children that are in the pool. This can happen during // chain re-orgs if origTx isn't re-accepted into the mempool for any // reason. for (size_t i = 0; i < origTx.vout.size(); i++) { auto it = mapNextTx.find(COutPoint(origTx.GetId(), i)); if (it == mapNextTx.end()) { continue; } txiter nextit = mapTx.find(it->second->GetId()); assert(nextit != mapTx.end()); txToRemove.insert(nextit); } } setEntries setAllRemoves; for (txiter it : txToRemove) { CalculateDescendants(it, setAllRemoves); } RemoveStaged(setAllRemoves, false, reason); } void CTxMemPool::removeForReorg(const Config &config, const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags) { // Remove transactions spending a coinbase which are now immature and // no-longer-final transactions. LOCK(cs); setEntries txToRemove; for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { const CTransaction &tx = it->GetTx(); LockPoints lp = it->GetLockPoints(); bool validLP = TestLockPointValidity(&lp); CValidationState state; if (!ContextualCheckTransactionForCurrentBlock(config, tx, state, flags) || !CheckSequenceLocks(tx, flags, &lp, validLP)) { // Note if CheckSequenceLocks fails the LockPoints may still be // invalid. So it's critical that we remove the tx and not depend on // the LockPoints. txToRemove.insert(it); } else if (it->GetSpendsCoinbase()) { for (const CTxIn &txin : tx.vin) { indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); if (it2 != mapTx.end()) { continue; } const Coin &coin = pcoins->AccessCoin(txin.prevout); if (nCheckFrequency != 0) { assert(!coin.IsSpent()); } if (coin.IsSpent() || (coin.IsCoinBase() && int64_t(nMemPoolHeight) - coin.GetHeight() < COINBASE_MATURITY)) { txToRemove.insert(it); break; } } } if (!validLP) { mapTx.modify(it, update_lock_points(lp)); } } setEntries setAllRemoves; for (txiter it : txToRemove) { CalculateDescendants(it, setAllRemoves); } RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG); } void CTxMemPool::removeConflicts(const CTransaction &tx) { // Remove transactions which depend on inputs of tx, recursively LOCK(cs); for (const CTxIn &txin : tx.vin) { auto it = mapNextTx.find(txin.prevout); if (it != mapNextTx.end()) { const CTransaction &txConflict = *it->second; if (txConflict != tx) { ClearPrioritisation(txConflict.GetId()); removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT); } } } } /** * Called when a block is connected. Removes from mempool and updates the miner * fee estimator. */ void CTxMemPool::removeForBlock(const std::vector &vtx, unsigned int nBlockHeight) { LOCK(cs); std::vector entries; for (const auto &tx : vtx) { uint256 txid = tx->GetId(); indexed_transaction_set::iterator i = mapTx.find(txid); if (i != mapTx.end()) { entries.push_back(&*i); } } // Before the txs in the new block have been removed from the mempool, // update policy estimates minerPolicyEstimator->processBlock(nBlockHeight, entries); for (const auto &tx : vtx) { txiter it = mapTx.find(tx->GetId()); if (it != mapTx.end()) { setEntries stage; stage.insert(it); RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK); } removeConflicts(*tx); ClearPrioritisation(tx->GetId()); } lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = true; } void CTxMemPool::_clear() { mapLinks.clear(); mapTx.clear(); mapNextTx.clear(); vTxHashes.clear(); totalTxSize = 0; cachedInnerUsage = 0; lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = false; rollingMinimumFeeRate = 0; ++nTransactionsUpdated; } void CTxMemPool::clear() { LOCK(cs); _clear(); } void CTxMemPool::check(const CCoinsViewCache *pcoins) const { if (nCheckFrequency == 0) { return; } if (GetRand(std::numeric_limits::max()) >= nCheckFrequency) { return; } LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size()); uint64_t checkTotal = 0; uint64_t innerUsage = 0; CCoinsViewCache mempoolDuplicate(const_cast(pcoins)); const int64_t nSpendHeight = GetSpendHeight(mempoolDuplicate); LOCK(cs); std::list waitingOnDependants; for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { unsigned int i = 0; checkTotal += it->GetTxSize(); innerUsage += it->DynamicMemoryUsage(); const CTransaction &tx = it->GetTx(); txlinksMap::const_iterator linksiter = mapLinks.find(it); assert(linksiter != mapLinks.end()); const TxLinks &links = linksiter->second; innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children); bool fDependsWait = false; setEntries setParentCheck; int64_t parentSizes = 0; int64_t parentSigOpCount = 0; for (const CTxIn &txin : tx.vin) { // Check that every mempool transaction's inputs refer to available // coins, or other mempool tx's. indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); if (it2 != mapTx.end()) { const CTransaction &tx2 = it2->GetTx(); assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); fDependsWait = true; if (setParentCheck.insert(it2).second) { parentSizes += it2->GetTxSize(); parentSigOpCount += it2->GetSigOpCount(); } } else { assert(pcoins->HaveCoin(txin.prevout)); } // Check whether its inputs are marked in mapNextTx. auto it3 = mapNextTx.find(txin.prevout); assert(it3 != mapNextTx.end()); assert(it3->first == &txin.prevout); assert(it3->second == &tx); i++; } assert(setParentCheck == GetMemPoolParents(it)); // Verify ancestor state is correct. setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits::max(); std::string dummy; CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); uint64_t nCountCheck = setAncestors.size() + 1; uint64_t nSizeCheck = it->GetTxSize(); Amount nFeesCheck = it->GetModifiedFee(); int64_t nSigOpCheck = it->GetSigOpCount(); for (txiter ancestorIt : setAncestors) { nSizeCheck += ancestorIt->GetTxSize(); nFeesCheck += ancestorIt->GetModifiedFee(); nSigOpCheck += ancestorIt->GetSigOpCount(); } assert(it->GetCountWithAncestors() == nCountCheck); assert(it->GetSizeWithAncestors() == nSizeCheck); assert(it->GetSigOpCountWithAncestors() == nSigOpCheck); assert(it->GetModFeesWithAncestors() == nFeesCheck); // Check children against mapNextTx CTxMemPool::setEntries setChildrenCheck; auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetId(), 0)); int64_t childSizes = 0; for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetId(); ++iter) { txiter childit = mapTx.find(iter->second->GetId()); // mapNextTx points to in-mempool transactions assert(childit != mapTx.end()); if (setChildrenCheck.insert(childit).second) { childSizes += childit->GetTxSize(); } } assert(setChildrenCheck == GetMemPoolChildren(it)); // Also check to make sure size is greater than sum with immediate // children. Just a sanity check, not definitive that this calc is // correct... assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize()); if (fDependsWait) { waitingOnDependants.push_back(&(*it)); } else { CValidationState state; bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs( tx, state, mempoolDuplicate, nSpendHeight); assert(fCheckResult); UpdateCoins(tx, mempoolDuplicate, 1000000); } } unsigned int stepsSinceLastRemove = 0; while (!waitingOnDependants.empty()) { const CTxMemPoolEntry *entry = waitingOnDependants.front(); waitingOnDependants.pop_front(); CValidationState state; if (!mempoolDuplicate.HaveInputs(entry->GetTx())) { waitingOnDependants.push_back(entry); stepsSinceLastRemove++; assert(stepsSinceLastRemove < waitingOnDependants.size()); } else { bool fCheckResult = entry->GetTx().IsCoinBase() || Consensus::CheckTxInputs(entry->GetTx(), state, mempoolDuplicate, nSpendHeight); assert(fCheckResult); UpdateCoins(entry->GetTx(), mempoolDuplicate, 1000000); stepsSinceLastRemove = 0; } } for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) { uint256 txid = it->second->GetId(); indexed_transaction_set::const_iterator it2 = mapTx.find(txid); const CTransaction &tx = it2->GetTx(); assert(it2 != mapTx.end()); assert(&tx == it->second); } assert(totalTxSize == checkTotal); assert(innerUsage == cachedInnerUsage); } bool CTxMemPool::CompareDepthAndScore(const uint256 &hasha, const uint256 &hashb) { LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(hasha); if (i == mapTx.end()) { return false; } indexed_transaction_set::const_iterator j = mapTx.find(hashb); if (j == mapTx.end()) { return true; } uint64_t counta = i->GetCountWithAncestors(); uint64_t countb = j->GetCountWithAncestors(); if (counta == countb) { return CompareTxMemPoolEntryByScore()(*i, *j); } return counta < countb; } namespace { class DepthAndScoreComparator { public: bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator &a, const CTxMemPool::indexed_transaction_set::const_iterator &b) { uint64_t counta = a->GetCountWithAncestors(); uint64_t countb = b->GetCountWithAncestors(); if (counta == countb) { return CompareTxMemPoolEntryByScore()(*a, *b); } return counta < countb; } }; } // namespace std::vector CTxMemPool::GetSortedDepthAndScore() const { std::vector iters; AssertLockHeld(cs); iters.reserve(mapTx.size()); for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) { iters.push_back(mi); } std::sort(iters.begin(), iters.end(), DepthAndScoreComparator()); return iters; } void CTxMemPool::queryHashes(std::vector &vtxid) { LOCK(cs); auto iters = GetSortedDepthAndScore(); vtxid.clear(); vtxid.reserve(mapTx.size()); for (auto it : iters) { vtxid.push_back(it->GetTx().GetId()); } } static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) { return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), CFeeRate(it->GetFee(), it->GetTxSize()), it->GetModifiedFee() - it->GetFee()}; } std::vector CTxMemPool::infoAll() const { LOCK(cs); auto iters = GetSortedDepthAndScore(); std::vector ret; ret.reserve(mapTx.size()); for (auto it : iters) { ret.push_back(GetInfo(it)); } return ret; } CTransactionRef CTxMemPool::get(const uint256 &txid) const { LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(txid); if (i == mapTx.end()) { return nullptr; } return i->GetSharedTx(); } TxMempoolInfo CTxMemPool::info(const uint256 &txid) const { LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(txid); if (i == mapTx.end()) { return TxMempoolInfo(); } return GetInfo(i); } CFeeRate CTxMemPool::estimateFee(int nBlocks) const { LOCK(cs); return minerPolicyEstimator->estimateFee(nBlocks); } CFeeRate CTxMemPool::estimateSmartFee(int nBlocks, int *answerFoundAtBlocks) const { LOCK(cs); return minerPolicyEstimator->estimateSmartFee(nBlocks, answerFoundAtBlocks, *this); } -double CTxMemPool::estimatePriority(int nBlocks) const { - LOCK(cs); - return minerPolicyEstimator->estimatePriority(nBlocks); -} double CTxMemPool::estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks) const { LOCK(cs); return minerPolicyEstimator->estimateSmartPriority( 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; } void CTxMemPool::PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const Amount nFeeDelta) { { LOCK(cs); std::pair &deltas = mapDeltas[hash]; deltas.first += dPriorityDelta; deltas.second += nFeeDelta; txiter it = mapTx.find(hash); if (it != mapTx.end()) { mapTx.modify(it, update_fee_delta(deltas.second)); // Now update all ancestors' modified fees with descendants setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits::max(); std::string dummy; CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false); for (txiter ancestorIt : setAncestors) { mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0)); } // Now update all descendants' modified fees with ancestors setEntries setDescendants; CalculateDescendants(it, setDescendants); setDescendants.erase(it); for (txiter descendantIt : setDescendants) { mapTx.modify(descendantIt, update_ancestor_state(0, nFeeDelta, 0, 0)); } } } LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta)); } void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, Amount &nFeeDelta) const { LOCK(cs); std::map>::const_iterator pos = mapDeltas.find(hash); if (pos == mapDeltas.end()) { return; } const std::pair &deltas = pos->second; dPriorityDelta += deltas.first; nFeeDelta += deltas.second; } void CTxMemPool::ClearPrioritisation(const uint256 hash) { LOCK(cs); mapDeltas.erase(hash); } bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const { for (const CTxIn &in : tx.vin) { if (exists(in.prevout.hash)) { return false; } } return true; } CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) {} bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const { // If an entry in the mempool exists, always return that one, as it's // guaranteed to never conflict with the underlying cache, and it cannot // have pruned entries (as it contains full) transactions. First checking // the underlying cache risks returning a pruned entry instead. CTransactionRef ptx = mempool.get(outpoint.hash); if (ptx) { if (outpoint.n < ptx->vout.size()) { coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false); return true; } return false; } return base->GetCoin(outpoint, coin) && !coin.IsSpent(); } bool CCoinsViewMemPool::HaveCoin(const COutPoint &outpoint) const { return mempool.exists(outpoint) || base->HaveCoin(outpoint); } size_t CTxMemPool::DynamicMemoryUsage() const { LOCK(cs); // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no // exact formula for boost::multi_index_contained is implemented. return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void *)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage; } void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) { AssertLockHeld(cs); UpdateForRemoveFromMempool(stage, updateDescendants); for (const txiter &it : stage) { removeUnchecked(it, reason); } } int CTxMemPool::Expire(int64_t time) { LOCK(cs); indexed_transaction_set::index::type::iterator it = mapTx.get().begin(); setEntries toremove; while (it != mapTx.get().end() && it->GetTime() < time) { toremove.insert(mapTx.project<0>(it)); it++; } setEntries stage; for (txiter removeit : toremove) { CalculateDescendants(removeit, stage); } RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY); return stage.size(); } bool CTxMemPool::addUnchecked(const uint256 &hash, const CTxMemPoolEntry &entry, bool validFeeEstimate) { LOCK(cs); setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits::max(); std::string dummy; CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); return addUnchecked(hash, entry, setAncestors, validFeeEstimate); } void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) { setEntries s; if (add && mapLinks[entry].children.insert(child).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); } else if (!add && mapLinks[entry].children.erase(child)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) { setEntries s; if (add && mapLinks[entry].parents.insert(parent).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); } else if (!add && mapLinks[entry].parents.erase(parent)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const { assert(entry != mapTx.end()); txlinksMap::const_iterator it = mapLinks.find(entry); assert(it != mapLinks.end()); return it->second.parents; } const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const { assert(entry != mapTx.end()); txlinksMap::const_iterator it = mapLinks.find(entry); assert(it != mapLinks.end()); return it->second.children; } CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const { LOCK(cs); if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0) { return CFeeRate(Amount(int64_t(rollingMinimumFeeRate))); } int64_t time = GetTime(); if (time > lastRollingFeeUpdate + 10) { double halflife = ROLLING_FEE_HALFLIFE; if (DynamicMemoryUsage() < sizelimit / 4) { halflife /= 4; } else if (DynamicMemoryUsage() < sizelimit / 2) { halflife /= 2; } rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife); lastRollingFeeUpdate = time; if (rollingMinimumFeeRate < (double)incrementalRelayFee.GetFeePerK().GetSatoshis() / 2) { rollingMinimumFeeRate = 0; return CFeeRate(Amount(0)); } } return std::max(CFeeRate(Amount(int64_t(rollingMinimumFeeRate))), incrementalRelayFee); } void CTxMemPool::trackPackageRemoved(const CFeeRate &rate) { AssertLockHeld(cs); if (rate.GetFeePerK().GetSatoshis() > rollingMinimumFeeRate) { rollingMinimumFeeRate = rate.GetFeePerK().GetSatoshis(); blockSinceLastRollingFeeBump = false; } } void CTxMemPool::TrimToSize(size_t sizelimit, std::vector *pvNoSpendsRemaining) { LOCK(cs); unsigned nTxnRemoved = 0; CFeeRate maxFeeRateRemoved(Amount(0)); while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) { indexed_transaction_set::index::type::iterator it = mapTx.get().begin(); // We set the new mempool min fee to the feerate of the removed set, // plus the "minimum reasonable fee rate" (ie some value under which we // consider txn to have 0 fee). This way, we don't allow txn to enter // mempool with feerate equal to txn which were removed with no block in // between. CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants()); removed += incrementalRelayFee; trackPackageRemoved(removed); maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed); setEntries stage; CalculateDescendants(mapTx.project<0>(it), stage); nTxnRemoved += stage.size(); std::vector txn; if (pvNoSpendsRemaining) { txn.reserve(stage.size()); for (txiter iter : stage) { txn.push_back(iter->GetTx()); } } RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT); if (pvNoSpendsRemaining) { for (const CTransaction &tx : txn) { for (const CTxIn &txin : tx.vin) { if (exists(txin.prevout.hash)) { continue; } if (!mapNextTx.count(txin.prevout)) { pvNoSpendsRemaining->push_back(txin.prevout); } } } } } if (maxFeeRateRemoved > CFeeRate(Amount(0))) { LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString()); } } bool CTxMemPool::TransactionWithinChainLimit(const uint256 &txid, size_t chainLimit) const { LOCK(cs); auto it = mapTx.find(txid); return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit && it->GetCountWithDescendants() < chainLimit); } SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits::max())), k1(GetRand(std::numeric_limits::max())) {} diff --git a/src/txmempool.h b/src/txmempool.h index 46a4658418..9d780c1ac9 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -1,908 +1,905 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_TXMEMPOOL_H #define BITCOIN_TXMEMPOOL_H #include "amount.h" #include "coins.h" #include "indirectmap.h" #include "primitives/transaction.h" #include "random.h" #include "sync.h" #include #include #include #include #include #include #include #include #include #include #include class CAutoFile; class CBlockIndex; class Config; inline double AllowFreeThreshold() { return COIN.GetSatoshis() * 144 / 250; } inline bool AllowFree(double dPriority) { // Large (in bytes) low-priority (new, small-coin) transactions need a fee. return dPriority > AllowFreeThreshold(); } /** * Fake height value used in Coins to signify they are only in the memory * pool(since 0.8) */ static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF; struct LockPoints { // Will be set to the blockchain height and median time past values that // would be necessary to satisfy all relative locktime constraints (BIP68) // of this tx given our view of block chain history int height; int64_t time; // As long as the current chain descends from the highest height block // containing one of the inputs used in the calculation, then the cached // values are still valid even after a reorg. CBlockIndex *maxInputBlock; LockPoints() : height(0), time(0), maxInputBlock(nullptr) {} }; class CTxMemPool; /** \class CTxMemPoolEntry * * CTxMemPoolEntry stores data about the corresponding transaction, as well as * data about all in-mempool transactions that depend on the transaction * ("descendant" transactions). * * When a new entry is added to the mempool, we update the descendant state * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) * for all ancestors of the newly added transaction. * * If updating the descendant state is skipped, we can mark the entry as * "dirty", and set nSizeWithDescendants/nModFeesWithDescendants to equal * nTxSize/nFee+feeDelta. (This can potentially happen during a reorg, where we * limit the amount of work we're willing to do to avoid consuming too much * CPU.) */ class CTxMemPoolEntry { private: CTransactionRef tx; //!< Cached to avoid expensive parent-transaction lookups Amount nFee; //!< ... and avoid recomputing tx size size_t nTxSize; //!< ... and modified size for priority size_t nModSize; //!< ... and total memory usage size_t nUsageSize; //!< Local time when entering the mempool int64_t nTime; //!< Priority when entering the mempool double entryPriority; //!< Chain height when entering the mempool unsigned int entryHeight; //!< Sum of all txin values that are already in blockchain Amount inChainInputValue; //!< keep track of transactions that spend a coinbase bool spendsCoinbase; //!< Total sigop plus P2SH sigops count int64_t sigOpCount; //!< Used for determining the priority of the transaction for mining in a //! block Amount feeDelta; //!< Track the height and time at which tx was final LockPoints lockPoints; // Information about descendants of this transaction that are in the // mempool; if we remove this transaction we must remove all of these // descendants as well. if nCountWithDescendants is 0, treat this entry as // dirty, and nSizeWithDescendants and nModFeesWithDescendants will not be // correct. //!< number of descendant transactions uint64_t nCountWithDescendants; //!< ... and size uint64_t nSizeWithDescendants; //!< ... and total fees (all including us) Amount nModFeesWithDescendants; // Analogous statistics for ancestor transactions uint64_t nCountWithAncestors; uint64_t nSizeWithAncestors; Amount nModFeesWithAncestors; int64_t nSigOpCountWithAncestors; public: CTxMemPoolEntry(const CTransactionRef &_tx, const Amount _nFee, int64_t _nTime, double _entryPriority, unsigned int _entryHeight, Amount _inChainInputValue, bool spendsCoinbase, int64_t nSigOpsCost, LockPoints lp); CTxMemPoolEntry(const CTxMemPoolEntry &other); const CTransaction &GetTx() const { return *this->tx; } CTransactionRef GetSharedTx() const { return this->tx; } /** * Fast calculation of lower bound of current priority as update from entry * priority. Only inputs that were originally in-chain will age. */ double GetPriority(unsigned int currentHeight) const; const Amount GetFee() const { return nFee; } size_t GetTxSize() const { return nTxSize; } int64_t GetTime() const { return nTime; } unsigned int GetHeight() const { return entryHeight; } int64_t GetSigOpCount() const { return sigOpCount; } Amount GetModifiedFee() const { return nFee + feeDelta; } size_t DynamicMemoryUsage() const { return nUsageSize; } const LockPoints &GetLockPoints() const { return lockPoints; } // Adjusts the descendant state, if this entry is not dirty. void UpdateDescendantState(int64_t modifySize, Amount modifyFee, int64_t modifyCount); // Adjusts the ancestor state void UpdateAncestorState(int64_t modifySize, Amount modifyFee, int64_t modifyCount, int modifySigOps); // Updates the fee delta used for mining priority score, and the // modified fees with descendants. void UpdateFeeDelta(Amount feeDelta); // Update the LockPoints after a reorg void UpdateLockPoints(const LockPoints &lp); uint64_t GetCountWithDescendants() const { return nCountWithDescendants; } uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; } Amount GetModFeesWithDescendants() const { return nModFeesWithDescendants; } bool GetSpendsCoinbase() const { return spendsCoinbase; } uint64_t GetCountWithAncestors() const { return nCountWithAncestors; } uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; } Amount GetModFeesWithAncestors() const { return nModFeesWithAncestors; } int64_t GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; } //!< Index in mempool's vTxHashes mutable size_t vTxHashesIdx; }; // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. struct update_descendant_state { update_descendant_state(int64_t _modifySize, Amount _modifyFee, int64_t _modifyCount) : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount) {} void operator()(CTxMemPoolEntry &e) { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); } private: int64_t modifySize; Amount modifyFee; int64_t modifyCount; }; struct update_ancestor_state { update_ancestor_state(int64_t _modifySize, Amount _modifyFee, int64_t _modifyCount, int64_t _modifySigOpsCost) : modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOpsCost(_modifySigOpsCost) {} void operator()(CTxMemPoolEntry &e) { e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOpsCost); } private: int64_t modifySize; Amount modifyFee; int64_t modifyCount; int64_t modifySigOpsCost; }; struct update_fee_delta { update_fee_delta(Amount _feeDelta) : feeDelta(_feeDelta) {} void operator()(CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); } private: Amount feeDelta; }; struct update_lock_points { update_lock_points(const LockPoints &_lp) : lp(_lp) {} void operator()(CTxMemPoolEntry &e) { e.UpdateLockPoints(lp); } private: const LockPoints &lp; }; // extracts a transaction hash from CTxMempoolEntry or CTransactionRef struct mempoolentry_txid { typedef uint256 result_type; result_type operator()(const CTxMemPoolEntry &entry) const { return entry.GetTx().GetId(); } result_type operator()(const CTransactionRef &tx) const { return tx->GetId(); } }; /** \class CompareTxMemPoolEntryByDescendantScore * * Sort an entry by max(score/size of entry's tx, score/size with all * descendants). */ class CompareTxMemPoolEntryByDescendantScore { public: bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const { bool fUseADescendants = UseDescendantScore(a); bool fUseBDescendants = UseDescendantScore(b); double aModFee = (fUseADescendants ? a.GetModFeesWithDescendants() : a.GetModifiedFee()) .GetSatoshis(); double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize(); double bModFee = (fUseBDescendants ? b.GetModFeesWithDescendants() : b.GetModifiedFee()) .GetSatoshis(); double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize(); // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). double f1 = aModFee * bSize; double f2 = aSize * bModFee; if (f1 == f2) { return a.GetTime() >= b.GetTime(); } return f1 < f2; } // Calculate which score to use for an entry (avoiding division). bool UseDescendantScore(const CTxMemPoolEntry &a) const { double f1 = double(a.GetSizeWithDescendants() * a.GetModifiedFee().GetSatoshis()); double f2 = double(a.GetTxSize() * a.GetModFeesWithDescendants().GetSatoshis()); return f2 > f1; } }; /** \class CompareTxMemPoolEntryByScore * * Sort by score of entry ((fee+delta)/size) in descending order */ class CompareTxMemPoolEntryByScore { public: bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const { double f1 = double(b.GetTxSize() * a.GetModifiedFee().GetSatoshis()); double f2 = double(a.GetTxSize() * b.GetModifiedFee().GetSatoshis()); if (f1 == f2) { return b.GetTx().GetId() < a.GetTx().GetId(); } return f1 > f2; } }; class CompareTxMemPoolEntryByEntryTime { public: bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const { return a.GetTime() < b.GetTime(); } }; class CompareTxMemPoolEntryByAncestorFee { public: bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const { double aFees = double(a.GetModFeesWithAncestors().GetSatoshis()); double aSize = a.GetSizeWithAncestors(); double bFees = double(b.GetModFeesWithAncestors().GetSatoshis()); double bSize = b.GetSizeWithAncestors(); // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). double f1 = aFees * bSize; double f2 = aSize * bFees; if (f1 == f2) { return a.GetTx().GetId() < b.GetTx().GetId(); } return f1 > f2; } }; // Multi_index tag names struct descendant_score {}; struct entry_time {}; struct mining_score {}; struct ancestor_score {}; class CBlockPolicyEstimator; /** * Information about a mempool transaction. */ struct TxMempoolInfo { /** The transaction itself */ CTransactionRef tx; /** Time the transaction entered the mempool. */ int64_t nTime; /** Feerate of the transaction. */ CFeeRate feeRate; /** The fee delta. */ Amount nFeeDelta; }; /** * Reason why a transaction was removed from the mempool, this is passed to the * notification signal. */ enum class MemPoolRemovalReason { //! Manually removed or unknown reason UNKNOWN = 0, //! Expired from mempool EXPIRY, //! Removed in size limiting SIZELIMIT, //! Removed for reorganization REORG, //! Removed for block BLOCK, //! Removed for conflict with in-block transaction CONFLICT, //! Removed for replacement REPLACED }; class SaltedTxidHasher { private: /** Salt */ const uint64_t k0, k1; public: SaltedTxidHasher(); size_t operator()(const uint256 &txid) const { return SipHashUint256(k0, k1, txid); } }; /** * CTxMemPool stores valid-according-to-the-current-best-chain transactions that * may be included in the next block. * * Transactions are added when they are seen on the network (or created by the * local node), but not all transactions seen are added to the pool. For * example, the following new transactions will not be added to the mempool: * - a transaction which doesn't meet the minimum fee requirements. * - a new transaction that double-spends an input of a transaction already in * the pool where the new transaction does not meet the Replace-By-Fee * requirements as defined in BIP 125. * - a non-standard transaction. * * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping: * * mapTx is a boost::multi_index that sorts the mempool on 4 criteria: * - transaction hash * - feerate [we use max(feerate of tx, feerate of tx with all descendants)] * - time in mempool * - mining score (feerate modified by any fee deltas from * PrioritiseTransaction) * * Note: the term "descendant" refers to in-mempool transactions that depend on * this one, while "ancestor" refers to in-mempool transactions that a given * transaction depends on. * * In order for the feerate sort to remain correct, we must update transactions * in the mempool when new descendants arrive. To facilitate this, we track the * set of in-mempool direct parents and direct children in mapLinks. Within each * CTxMemPoolEntry, we track the size and fees of all descendants. * * Usually when a new transaction is added to the mempool, it has no in-mempool * children (because any such children would be an orphan). So in * addUnchecked(), we: * - update a new entry's setMemPoolParents to include all in-mempool parents * - update the new entry's direct parents to include the new tx as a child * - update all ancestors of the transaction to include the new tx's size/fee * * When a transaction is removed from the mempool, we must: * - update all in-mempool parents to not track the tx in setMemPoolChildren * - update all ancestors to not include the tx's size/fees in descendant state * - update all in-mempool children to not include it as a parent * * These happen in UpdateForRemoveFromMempool(). (Note that when removing a * transaction along with its descendants, we must calculate that set of * transactions to be removed before doing the removal, or else the mempool can * be in an inconsistent state where it's impossible to walk the ancestors of a * transaction.) * * In the event of a reorg, the assumption that a newly added tx has no * in-mempool children is false. In particular, the mempool is in an * inconsistent state while new transactions are being added, because there may * be descendant transactions of a tx coming from a disconnected block that are * unreachable from just looking at transactions in the mempool (the linking * transactions may also be in the disconnected block, waiting to be added). * Because of this, there's not much benefit in trying to search for in-mempool * children in addUnchecked(). Instead, in the special case of transactions * being added from a disconnected block, we require the caller to clean up the * state, to account for in-mempool, out-of-block descendants for all the * in-block transactions by calling UpdateTransactionsFromBlock(). Note that * until this is called, the mempool state is not consistent, and in particular * mapLinks may not be correct (and therefore functions like * CalculateMemPoolAncestors() and CalculateDescendants() that rely on them to * walk the mempool are not generally safe to use). * * Computational limits: * * Updating all in-mempool ancestors of a newly added transaction can be slow, * if no bound exists on how many in-mempool ancestors there may be. * CalculateMemPoolAncestors() takes configurable limits that are designed to * prevent these calculations from being too CPU intensive. * * Adding transactions from a disconnected block can be very time consuming, * because we don't have a way to limit the number of in-mempool descendants. To * bound CPU processing, we limit the amount of work we're willing to do to * properly update the descendant information for a tx being added from a * disconnected block. If we would exceed the limit, then we instead mark the * entry as "dirty", and set the feerate for sorting purposes to be equal the * feerate of the transaction without any descendants. */ class CTxMemPool { private: //!< 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; //!< sum of dynamic memory usage of all the map elements (NOT the maps //! themselves) uint64_t cachedInnerUsage; mutable int64_t lastRollingFeeUpdate; mutable bool blockSinceLastRollingFeeBump; //!< minimum fee to get into the pool, decreases exponentially mutable double rollingMinimumFeeRate; void trackPackageRemoved(const CFeeRate &rate); public: // public only for testing static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; typedef boost::multi_index_container< CTxMemPoolEntry, boost::multi_index::indexed_by< // sorted by txid boost::multi_index::hashed_unique< mempoolentry_txid, SaltedTxidHasher>, // sorted by fee rate boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByDescendantScore>, // sorted by entry time boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByEntryTime>, // sorted by score (for mining prioritization) boost::multi_index::ordered_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByScore>, // sorted by fee rate with ancestors boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByAncestorFee>>> indexed_transaction_set; mutable CCriticalSection cs; indexed_transaction_set mapTx; typedef indexed_transaction_set::nth_index<0>::type::iterator txiter; //!< All tx hashes/entries in mapTx, in random order std::vector> vTxHashes; struct CompareIteratorByHash { bool operator()(const txiter &a, const txiter &b) const { return a->GetTx().GetId() < b->GetTx().GetId(); } }; typedef std::set setEntries; const setEntries &GetMemPoolParents(txiter entry) const; const setEntries &GetMemPoolChildren(txiter entry) const; private: typedef std::map cacheMap; struct TxLinks { setEntries parents; setEntries children; }; typedef std::map txlinksMap; txlinksMap mapLinks; void UpdateParent(txiter entry, txiter parent, bool add); void UpdateChild(txiter entry, txiter child, bool add); std::vector GetSortedDepthAndScore() const; public: indirectmap mapNextTx; std::map> mapDeltas; /** Create a new CTxMemPool. */ CTxMemPool(const CFeeRate &_minReasonableRelayFee); ~CTxMemPool(); /** * If sanity-checking is turned on, check makes sure the pool is consistent * (does not contain two transactions that spend the same inputs, all inputs * are in the mapNextTx array). If sanity-checking is turned off, check does * nothing. */ void check(const CCoinsViewCache *pcoins) const; void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = dFrequency * 4294967295.0; } // addUnchecked must updated state for all ancestors of a given transaction, // to track size/count of descendant transactions. First version of // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and // then invoke the second version. bool addUnchecked(const uint256 &hash, const CTxMemPoolEntry &entry, bool validFeeEstimate = true); bool addUnchecked(const uint256 &hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate = true); void removeRecursive( const CTransaction &tx, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN); void removeForReorg(const Config &config, const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags); void removeConflicts(const CTransaction &tx); void removeForBlock(const std::vector &vtx, unsigned int nBlockHeight); void clear(); // lock free void _clear(); bool CompareDepthAndScore(const uint256 &hasha, const uint256 &hashb); void queryHashes(std::vector &vtxid); bool isSpent(const COutPoint &outpoint); unsigned int GetTransactionsUpdated() const; void AddTransactionsUpdated(unsigned int n); /** * Check that none of this transactions inputs are in the mempool, and thus * the tx is not dependent on other mempool transactions to be included in a * block. */ bool HasNoInputsOf(const CTransaction &tx) const; /** Affect CreateNewBlock prioritisation of transactions */ void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const Amount nFeeDelta); void ApplyDeltas(const uint256 hash, double &dPriorityDelta, Amount &nFeeDelta) const; void ClearPrioritisation(const uint256 hash); public: /** * Remove a set of transactions from the mempool. If a transaction is in * this set, then all in-mempool descendants must also be in the set, unless * this transaction is being removed for being in a block. Set * updateDescendants to true when removing a tx that was in a block, so that * any in-mempool descendants have their ancestor state updated. */ void RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN); /** * When adding transactions from a disconnected block back to the mempool, * new mempool entries may have children in the mempool (which is generally * not the case when otherwise adding transactions). * UpdateTransactionsFromBlock() will find child transactions and update the * descendant state for each transaction in hashesToUpdate (excluding any * child transactions present in hashesToUpdate, which are already accounted * for). Note: hashesToUpdate should be the set of transactions from the * disconnected block that have been accepted back into the mempool. */ void UpdateTransactionsFromBlock(const std::vector &hashesToUpdate); /** * Try to calculate all in-mempool ancestors of entry. * (these are all calculated including the tx itself) * limitAncestorCount = max number of ancestors * limitAncestorSize = max size of ancestors * limitDescendantCount = max number of descendants any ancestor can have * limitDescendantSize = max size of descendants any ancestor can have * errString = populated with error reason if any limits are hit * fSearchForParents = whether to search a tx's vin for in-mempool parents, * or look up parents from mapLinks. Must be true for entries not in the * mempool */ bool CalculateMemPoolAncestors( const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true) const; /** * Populate setDescendants with all in-mempool descendants of hash. * Assumes that setDescendants includes all in-mempool descendants of * anything already in it. */ void CalculateDescendants(txiter it, setEntries &setDescendants); /** * The minimum fee to get into the mempool, which may itself not be enough * for larger-sized transactions. The incrementalRelayFee policy variable is * used to bound the time it takes the fee rate to go back down all the way * to 0. When the feerate would otherwise be half of this, it is set to 0 * instead. */ CFeeRate GetMinFee(size_t sizelimit) const; /** * Remove transactions from the mempool until its dynamic size is <= * sizelimit. pvNoSpendsRemaining, if set, will be populated with the list * of outpoints which are not in mempool which no longer have any spends in * this mempool. */ void TrimToSize(size_t sizelimit, std::vector *pvNoSpendsRemaining = nullptr); /** Expire all transaction (and their dependencies) in the mempool older * than time. Return the number of removed transactions. */ int Expire(int64_t time); /** Returns false if the transaction is in the mempool and not within the * chain limit specified. */ bool TransactionWithinChainLimit(const uint256 &txid, size_t chainLimit) const; unsigned long size() { LOCK(cs); return mapTx.size(); } uint64_t GetTotalTxSize() { LOCK(cs); return totalTxSize; } bool exists(uint256 hash) const { LOCK(cs); return mapTx.count(hash) != 0; } bool exists(const COutPoint &outpoint) const { LOCK(cs); auto it = mapTx.find(outpoint.hash); return it != mapTx.end() && outpoint.n < it->GetTx().vout.size(); } CTransactionRef get(const uint256 &hash) const; TxMempoolInfo info(const uint256 &hash) const; std::vector infoAll() const; /** * Estimate fee rate needed to get into the next nBlocks. If no answer can * be given at nBlocks, return an estimate at the lowest number of blocks * where one can be given. */ CFeeRate estimateSmartFee(int nBlocks, int *answerFoundAtBlocks = nullptr) const; /** Estimate fee rate needed to get into the next nBlocks */ CFeeRate estimateFee(int nBlocks) const; /** * Estimate priority needed to get into the next nBlocks. If no answer can * be given at nBlocks, return an estimate at the lowest number of blocks * where one can be given. */ double estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks = nullptr) const; - /** Estimate priority needed to get into the next nBlocks */ - double estimatePriority(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; boost::signals2::signal NotifyEntryRemoved; private: /** * UpdateForDescendants is used by UpdateTransactionsFromBlock to update the * descendants for a single transaction that has been added to the mempool * but may have child transactions in the mempool, eg during a chain reorg. * setExclude is the set of descendant transactions in the mempool that must * not be accounted for (because any descendants in setExclude were added to * the mempool after the transaction being updated and hence their state is * already reflected in the parent state). * * cachedDescendants will be updated with the descendants of the transaction * being updated, so that future invocations don't need to walk the same * transaction again, if encountered in another transaction chain. */ void UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set &setExclude); /** Update ancestors of hash to add/remove it as a descendant transaction. */ void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors); /** Set ancestor state for an entry */ void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors); /** * For each transaction being removed, update ancestors and any direct * children. If updateDescendants is true, then also update in-mempool * descendants' ancestor state. */ void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants); /** Sever link between specified transaction and direct children. */ void UpdateChildrenForRemoval(txiter entry); /** * Before calling removeUnchecked for a given transaction, * UpdateForRemoveFromMempool must be called on the entire (dependent) set * of transactions being removed at the same time. We use each * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a given * transaction that is removed, so we can't remove intermediate transactions * in a chain before we've updated all the state for the removal. */ void removeUnchecked( txiter entry, MemPoolRemovalReason reason = MemPoolRemovalReason::UNKNOWN); }; /** * CCoinsView that brings transactions from a memorypool into view. * It does not check for spendings by memory pool transactions. */ class CCoinsViewMemPool : public CCoinsViewBacked { protected: const CTxMemPool &mempool; public: CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn); bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; bool HaveCoin(const COutPoint &outpoint) const override; }; // We want to sort transactions by coin age priority typedef std::pair TxCoinAgePriority; struct TxCoinAgePriorityCompare { bool operator()(const TxCoinAgePriority &a, const TxCoinAgePriority &b) { if (a.first == b.first) { // Reverse order to make sort less than return CompareTxMemPoolEntryByScore()(*(b.second), *(a.second)); } return a.first < b.first; } }; /** * DisconnectedBlockTransactions * During the reorg, it's desirable to re-add previously confirmed transactions * to the mempool, so that anything not re-confirmed in the new chain is * available to be mined. However, it's more efficient to wait until the reorg * is complete and process all still-unconfirmed transactions at that time, * since we expect most confirmed transactions to (typically) still be * confirmed in the new chain, and re-accepting to the memory pool is expensive * (and therefore better to not do in the middle of reorg-processing). * Instead, store the disconnected transactions (in order!) as we go, remove any * that are included in blocks in the new chain, and then process the remaining * still-unconfirmed transactions at the end. */ // multi_index tag names struct txid_index {}; struct insertion_order {}; struct DisconnectedBlockTransactions { typedef boost::multi_index_container< CTransactionRef, boost::multi_index::indexed_by< // sorted by txid boost::multi_index::hashed_unique< boost::multi_index::tag, mempoolentry_txid, SaltedTxidHasher>, // sorted by order in the blockchain boost::multi_index::sequenced< boost::multi_index::tag>>> indexed_disconnected_transactions; // It's almost certainly a logic bug if we don't clear out queuedTx before // destruction, as we add to it while disconnecting blocks, and then we // need to re-process remaining transactions to ensure mempool consistency. // For now, assert() that we've emptied out this object on destruction. // This assert() can always be removed if the reorg-processing code were // to be refactored such that this assumption is no longer true (for // instance if there was some other way we cleaned up the mempool after a // reorg, besides draining this object). ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); } indexed_disconnected_transactions queuedTx; uint64_t cachedInnerUsage = 0; // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as // no exact formula for boost::multi_index_contained is implemented. size_t DynamicMemoryUsage() const { return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void *)) * queuedTx.size() + cachedInnerUsage; } void addTransaction(const CTransactionRef &tx) { queuedTx.insert(tx); cachedInnerUsage += RecursiveDynamicUsage(tx); } // Remove entries based on txid_index, and update memory usage. void removeForBlock(const std::vector &vtx) { // Short-circuit in the common case of a block being added to the tip if (queuedTx.empty()) { return; } for (auto const &tx : vtx) { auto it = queuedTx.find(tx->GetHash()); if (it != queuedTx.end()) { cachedInnerUsage -= RecursiveDynamicUsage(*it); queuedTx.erase(it); } } } // Remove an entry by insertion_order index, and update memory usage. void removeEntry(indexed_disconnected_transactions::index< insertion_order>::type::iterator entry) { cachedInnerUsage -= RecursiveDynamicUsage(*entry); queuedTx.get().erase(entry); } void clear() { cachedInnerUsage = 0; queuedTx.clear(); } }; #endif // BITCOIN_TXMEMPOOL_H