diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 5ca3983c8..de54f2b68 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -1,62 +1,62 @@ // Copyright (c) 2012-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 "bench.h" #include "wallet/wallet.h" #include -static void addCoin(const CAmount &nValue, const CWallet &wallet, +static void addCoin(const Amount nValue, const CWallet &wallet, std::vector &vCoins) { int nInput = 0; static int nextLockTime = 0; CMutableTransaction tx; // so all transactions get different hashes tx.nLockTime = nextLockTime++; tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; CWalletTx *wtx = new CWalletTx(&wallet, MakeTransactionRef(std::move(tx))); int nAge = 6 * 24; COutput output(wtx, nInput, nAge, true, true); vCoins.push_back(output); } // Simple benchmark for wallet coin selection. Note that it maybe be necessary // to build up more complicated scenarios in order to get meaningful // measurements of performance. From laanwj, "Wallet coin selection is probably // the hardest, as you need a wider selection of scenarios, just testing the // same one over and over isn't too useful. Generating random isn't useful // either for measurements." // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484) static void CoinSelection(benchmark::State &state) { const CWallet wallet; std::vector vCoins; LOCK(wallet.cs_wallet); while (state.KeepRunning()) { // Empty wallet. for (COutput output : vCoins) { delete output.tx; } vCoins.clear(); // Add coins. for (int i = 0; i < 1000; i++) addCoin(1000 * COIN.GetSatoshis(), wallet, vCoins); addCoin(3 * COIN.GetSatoshis(), wallet, vCoins); std::set> setCoinsRet; CAmount nValueRet; bool success = wallet.SelectCoinsMinConf( 1003 * COIN.GetSatoshis(), 1, 6, 0, vCoins, setCoinsRet, nValueRet); assert(success); assert(nValueRet == 1003 * COIN); assert(setCoinsRet.size() == 2); } } BENCHMARK(CoinSelection); diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp index aec467ad5..060971169 100644 --- a/src/policy/fees.cpp +++ b/src/policy/fees.cpp @@ -1,577 +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("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( "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("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("estimatefee", "Blockpolicy error, mempool tx removed " "from >25 blocks,bucketIndex=%u already\n", bucketindex); } } else { unsigned int blockIndex = entryHeight % unconfTxs.size(); if (unconfTxs[blockIndex][bucketindex] > 0) { unconfTxs[blockIndex][bucketindex]--; } else { LogPrint("estimatefee", "Blockpolicy error, mempool tx removed " "from blockIndex=%u,bucketIndex=%u " "already\n", blockIndex, bucketindex); } } } // 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()) { feeStats.removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex); mapMemPoolTxs.erase(hash); return true; } else { return false; } } CBlockPolicyEstimator::CBlockPolicyEstimator(const CFeeRate &_minRelayFee) : nBestSeenHeight(0), trackedTxs(0), untrackedTxs(0) { static_assert(MIN_FEERATE > 0, "Min feerate must be nonzero"); minTrackedFee = _minRelayFee < CFeeRate(Amount(int64_t(MIN_FEERATE))) ? CFeeRate(Amount(int64_t(MIN_FEERATE))) : _minRelayFee; std::vector vfeelist; - for (double bucketBoundary = minTrackedFee.GetFeePerK().GetSatoshis(); - bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) { - vfeelist.push_back(bucketBoundary); + for (Amount bucketBoundary = minTrackedFee.GetFeePerK(); + bucketBoundary <= MAX_FEERATE; + bucketBoundary += bucketBoundary / FEE_SPACING_FRACTION) { + vfeelist.push_back(double(bucketBoundary.GetSatoshis())); } - vfeelist.push_back(INF_FEERATE); + 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("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 BCC-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( "estimatefee", "Blockpolicy error Transaction had negative blocksToConfirm\n"); return false; } // Feerates are stored and reported as BCC-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("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(0); } double median = feeStats.EstimateMedianVal( confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight); if (median < 0) { return CFeeRate(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(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(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000) .GetFeePerK(); if (minPoolFee > 0 && minPoolFee > int64_t(median)) { return CFeeRate(minPoolFee); } if (median < 0) { return CFeeRate(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(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000) .GetFeePerK(); if (minPoolFee > 0) { - return INF_PRIORITY; + 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(0); - for (double bucketBoundary = minFeeLimit.GetSatoshis(); - bucketBoundary <= MAX_FEERATE; bucketBoundary *= FEE_SPACING) { + feeset.insert(Amount(0)); + for (Amount bucketBoundary = minFeeLimit; bucketBoundary <= MAX_FEERATE; + bucketBoundary += bucketBoundary / FEE_SPACING_FRACTION) { feeset.insert(bucketBoundary); } } -CAmount FeeFilterRounder::round(CAmount currentMinFee) { - std::set::iterator it = feeset.lower_bound(currentMinFee); +Amount FeeFilterRounder::round(const Amount currentMinFee) { + std::set::iterator 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 d5449bfee..8c624fb96 100644 --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -1,306 +1,306 @@ // 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 double MIN_FEERATE = 10; -static const double MAX_FEERATE = 1e7; -static const double INF_FEERATE = MAX_MONEY.GetSatoshis(); -static const double INF_PRIORITY = 1e9 * MAX_MONEY.GetSatoshis(); +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; +static const int64_t FEE_SPACING_FRACTION = 10; /** * 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 **/ - CAmount round(CAmount currentMinFee); + Amount round(const Amount currentMinFee); private: - std::set feeset; + std::set feeset; FastRandomContext insecure_rand; }; #endif /*BITCOIN_POLICYESTIMATOR_H */ diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp index 90d8658c1..0cbd5c2d7 100644 --- a/src/test/policyestimator_tests.cpp +++ b/src/test/policyestimator_tests.cpp @@ -1,241 +1,242 @@ // Copyright (c) 2011-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/policy.h" #include "policy/fees.h" #include "txmempool.h" #include "uint256.h" #include "util.h" #include "test/test_bitcoin.h" #include BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, BasicTestingSetup) BOOST_AUTO_TEST_CASE(BlockPolicyEstimates) { CTxMemPool mpool(CFeeRate(1000)); TestMemPoolEntryHelper entry; - CAmount basefee(2000); - CAmount deltaFee(100); - std::vector feeV; + Amount basefee(2000); + Amount deltaFee(100); + std::vector feeV; // Populate vectors of increasing fees for (int j = 0; j < 10; j++) { - feeV.push_back(basefee * (j + 1)); + feeV.push_back((j + 1) * basefee); } // Store the hashes of transactions that have been added to the mempool by // their associate fee txHashes[j] is populated with transactions either of // fee = basefee * (j+1) std::vector txHashes[10]; // Create a transaction template CScript garbage; for (unsigned int i = 0; i < 128; i++) garbage.push_back('X'); CMutableTransaction tx; tx.vin.resize(1); tx.vin[0].scriptSig = garbage; tx.vout.resize(1); tx.vout[0].nValue = 0LL; CFeeRate baseRate(basefee, GetTransactionSize(tx)); // Create a fake block std::vector block; int blocknum = 0; // Loop through 200 blocks // At a decay .998 and 4 fee transactions per block // This makes the tx count about 1.33 per bucket, above the 1 threshold while (blocknum < 200) { // For each fee for (int j = 0; j < 10; j++) { // add 4 fee txs for (int k = 0; k < 4; k++) { // make transaction unique tx.vin[0].prevout.n = 10000 * blocknum + 100 * j + k; uint256 hash = tx.GetId(); mpool.addUnchecked(hash, entry.Fee(feeV[j]) .Time(GetTime()) .Priority(0) .Height(blocknum) .FromTx(tx, &mpool)); txHashes[j].push_back(hash); } } // Create blocks where higher fee txs are included more often for (int h = 0; h <= blocknum % 10; h++) { // 10/10 blocks add highest fee transactions // 9/10 blocks add 2nd highest and so on until ... // 1/10 blocks add lowest fee transactions while (txHashes[9 - h].size()) { CTransactionRef ptx = mpool.get(txHashes[9 - h].back()); if (ptx) block.push_back(ptx); txHashes[9 - h].pop_back(); } } mpool.removeForBlock(block, ++blocknum); block.clear(); if (blocknum == 30) { // At this point we should need to combine 5 buckets to get enough // data points. So estimateFee(1,2,3) should fail and estimateFee(4) // should return somewhere around 8*baserate. estimateFee(4) %'s // are 100,100,100,100,90 = average 98% BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(0)); BOOST_CHECK(mpool.estimateFee(2) == CFeeRate(0)); BOOST_CHECK(mpool.estimateFee(3) == CFeeRate(0)); BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() < 8 * baseRate.GetFeePerK() + deltaFee); BOOST_CHECK(mpool.estimateFee(4).GetFeePerK() > 8 * baseRate.GetFeePerK() - deltaFee); int answerFound; BOOST_CHECK(mpool.estimateSmartFee(1, &answerFound) == mpool.estimateFee(4) && answerFound == 4); BOOST_CHECK(mpool.estimateSmartFee(3, &answerFound) == mpool.estimateFee(4) && answerFound == 4); BOOST_CHECK(mpool.estimateSmartFee(4, &answerFound) == mpool.estimateFee(4) && answerFound == 4); BOOST_CHECK(mpool.estimateSmartFee(8, &answerFound) == mpool.estimateFee(8) && answerFound == 8); } } std::vector origFeeEst; // Highest feerate is 10*baseRate and gets in all blocks, second highest // feerate is 9*baseRate and gets in 9/10 blocks = 90%, third highest // feerate is 8*base rate, and gets in 8/10 blocks = 80%, so estimateFee(1) // would return 10*baseRate but is hardcoded to return failure. Second // highest feerate has 100% chance of being included by 2 blocks, so // estimateFee(2) should return 9*baseRate etc... for (int i = 1; i < 10; i++) { origFeeEst.push_back(mpool.estimateFee(i).GetFeePerK()); // Fee estimates should be monotonically decreasing if (i > 2) { BOOST_CHECK(origFeeEst[i - 1] <= origFeeEst[i - 2]); } int mult = 11 - i; if (i > 1) { BOOST_CHECK(origFeeEst[i - 1] < mult * baseRate.GetFeePerK() + deltaFee); BOOST_CHECK(origFeeEst[i - 1] > mult * baseRate.GetFeePerK() - deltaFee); } else { BOOST_CHECK(origFeeEst[i - 1] == CFeeRate(0).GetFeePerK()); } } // Mine 50 more blocks with no transactions happening, estimates shouldn't // change. We haven't decayed the moving average enough so we still have // enough data points in every bucket while (blocknum < 250) mpool.removeForBlock(block, ++blocknum); BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(0)); for (int i = 2; i < 10; i++) { BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < origFeeEst[i - 1] + deltaFee); BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > origFeeEst[i - 1] - deltaFee); } // Mine 15 more blocks with lots of transactions happening and not getting // mined. Estimates should go up while (blocknum < 265) { // For each fee multiple for (int j = 0; j < 10; j++) { // add 4 fee txs for (int k = 0; k < 4; k++) { tx.vin[0].prevout.n = 10000 * blocknum + 100 * j + k; uint256 txid = tx.GetId(); mpool.addUnchecked(txid, entry.Fee(feeV[j]) .Time(GetTime()) .Priority(0) .Height(blocknum) .FromTx(tx, &mpool)); txHashes[j].push_back(txid); } } mpool.removeForBlock(block, ++blocknum); } int answerFound; for (int i = 1; i < 10; i++) { BOOST_CHECK(mpool.estimateFee(i) == CFeeRate(0) || mpool.estimateFee(i).GetFeePerK() > origFeeEst[i - 1] - deltaFee); Amount a1 = mpool.estimateSmartFee(i, &answerFound).GetFeePerK(); Amount a2 = origFeeEst[answerFound - 1] - deltaFee; BOOST_CHECK(a1 > a2); } // Mine all those transactions // Estimates should still not be below original for (int j = 0; j < 10; j++) { while (txHashes[j].size()) { CTransactionRef ptx = mpool.get(txHashes[j].back()); if (ptx) block.push_back(ptx); txHashes[j].pop_back(); } } mpool.removeForBlock(block, 265); block.clear(); BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(0)); for (int i = 2; i < 10; i++) { BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() > origFeeEst[i - 1] - deltaFee); } // Mine 200 more blocks where everything is mined every block // Estimates should be below original estimates while (blocknum < 465) { // For each fee multiple for (int j = 0; j < 10; j++) { // add 4 fee txs for (int k = 0; k < 4; k++) { tx.vin[0].prevout.n = 10000 * blocknum + 100 * j + k; uint256 txid = tx.GetId(); mpool.addUnchecked(txid, entry.Fee(feeV[j]) .Time(GetTime()) .Priority(0) .Height(blocknum) .FromTx(tx, &mpool)); CTransactionRef ptx = mpool.get(txid); if (ptx) block.push_back(ptx); } } mpool.removeForBlock(block, ++blocknum); block.clear(); } BOOST_CHECK(mpool.estimateFee(1) == CFeeRate(0)); for (int i = 2; i < 10; i++) { BOOST_CHECK(mpool.estimateFee(i).GetFeePerK() < origFeeEst[i - 1] - deltaFee); } // Test that if the mempool is limited, estimateSmartFee won't return a // value below the mempool min fee and that estimateSmartPriority returns // essentially an infinite value mpool.addUnchecked( tx.GetId(), entry.Fee(feeV[5]).Time(GetTime()).Priority(0).Height(blocknum).FromTx( tx, &mpool)); // evict that transaction which should set a mempool min fee of // minRelayTxFee + feeV[5] mpool.TrimToSize(1); BOOST_CHECK(mpool.GetMinFee(1).GetFeePerK() > feeV[5]); for (int i = 1; i < 10; i++) { BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= mpool.estimateFee(i).GetFeePerK()); BOOST_CHECK(mpool.estimateSmartFee(i).GetFeePerK() >= mpool.GetMinFee(1).GetFeePerK()); - BOOST_CHECK(mpool.estimateSmartPriority(i) == INF_PRIORITY); + BOOST_CHECK(mpool.estimateSmartPriority(i) == + double(INF_PRIORITY.GetSatoshis())); } } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/test_bitcoin.h b/src/test/test_bitcoin.h index 8ef8e4eac..da891a142 100644 --- a/src/test/test_bitcoin.h +++ b/src/test/test_bitcoin.h @@ -1,112 +1,112 @@ // Copyright (c) 2015-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_TEST_TEST_BITCOIN_H #define BITCOIN_TEST_TEST_BITCOIN_H #include "chainparamsbase.h" #include "key.h" #include "pubkey.h" #include "txdb.h" #include "txmempool.h" #include #include /** Basic testing setup. * This just configures logging and chain parameters. */ struct BasicTestingSetup { ECCVerifyHandle globalVerifyHandle; BasicTestingSetup(const std::string &chainName = CBaseChainParams::MAIN); ~BasicTestingSetup(); }; /** Testing setup that configures a complete environment. * Included are data directory, coins database, script check threads setup. */ class CConnman; struct TestingSetup : public BasicTestingSetup { CCoinsViewDB *pcoinsdbview; boost::filesystem::path pathTemp; boost::thread_group threadGroup; CConnman *connman; TestingSetup(const std::string &chainName = CBaseChainParams::MAIN); ~TestingSetup(); }; class CBlock; struct CMutableTransaction; class CScript; // // Testing fixture that pre-creates a // 100-block REGTEST-mode block chain // struct TestChain100Setup : public TestingSetup { TestChain100Setup(); // Create a new block with just given transactions, coinbase paying to // scriptPubKey, and try to add it to the current chain. CBlock CreateAndProcessBlock(const std::vector &txns, const CScript &scriptPubKey); ~TestChain100Setup(); // For convenience, coinbase transactions. std::vector coinbaseTxns; // private/public key needed to spend coinbase transactions. CKey coinbaseKey; }; class CTxMemPoolEntry; class CTxMemPool; struct TestMemPoolEntryHelper { // Default values - CAmount nFee; + Amount nFee; int64_t nTime; double dPriority; unsigned int nHeight; bool spendsCoinbase; unsigned int sigOpCost; LockPoints lp; TestMemPoolEntryHelper() : nFee(0), nTime(0), dPriority(0.0), nHeight(1), spendsCoinbase(false), sigOpCost(4) {} CTxMemPoolEntry FromTx(const CMutableTransaction &tx, CTxMemPool *pool = nullptr); CTxMemPoolEntry FromTx(const CTransaction &tx, CTxMemPool *pool = nullptr); // Change the default value - TestMemPoolEntryHelper &Fee(CAmount _fee) { + TestMemPoolEntryHelper &Fee(Amount _fee) { nFee = _fee; return *this; } TestMemPoolEntryHelper &Time(int64_t _time) { nTime = _time; return *this; } TestMemPoolEntryHelper &Priority(double _priority) { dPriority = _priority; return *this; } TestMemPoolEntryHelper &Height(unsigned int _height) { nHeight = _height; return *this; } TestMemPoolEntryHelper &SpendsCoinbase(bool _flag) { spendsCoinbase = _flag; return *this; } TestMemPoolEntryHelper &SigOpsCost(unsigned int _sigopsCost) { sigOpCost = _sigopsCost; return *this; } }; #endif