src/txmempool.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2014 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or https://www.opensource.org/licenses/mit-license.php .
   5
   6 #include "txmempool.h"
   7
   8 #include "clientversion.h"
   9 #include "consensus/consensus.h"
  10 #include "consensus/validation.h"
  11 #include "main.h"
  12 #include "policy/fees.h"
  13 #include "streams.h"
  14 #include "timedata.h"
  15 #include "util.h"
  16 #include "utilmoneystr.h"
  17 #include "version.h"
  18
  19 using namespace std;
  20
  21 CTxMemPoolEntry::CTxMemPoolEntry():
  22     nFee(0), nTxSize(0), nModSize(0), nUsageSize(0), nTime(0), dPriority(0.0),
  23     hadNoDependencies(false), spendsCoinbase(false)
  24 {
  25     nHeight = MEMPOOL_HEIGHT;
  26 }
  27
  28 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
  29                                  int64_t _nTime, double _dPriority,
  30                                  unsigned int _nHeight, bool poolHasNoInputsOf,
  31                                  bool _spendsCoinbase, uint32_t _nBranchId):
  32     tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight),
  33     hadNoDependencies(poolHasNoInputsOf),
  34     spendsCoinbase(_spendsCoinbase), nBranchId(_nBranchId)
  35 {
  36     nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
  37     nModSize = tx.CalculateModifiedSize(nTxSize);
  38     nUsageSize = RecursiveDynamicUsage(tx);
  39     feeRate = CFeeRate(nFee, nTxSize);
  40 }
  41
  42 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
  43 {
  44     *this = other;
  45 }
  46
  47 double
  48 CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
  49 {
  50     CAmount nValueIn = tx.GetValueOut()+nFee;
  51     double deltaPriority = ((double)(currentHeight-nHeight)*nValueIn)/nModSize;
  52     double dResult = dPriority + deltaPriority;
  53     return dResult;
  54 }
  55
  56 CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
  57     nTransactionsUpdated(0)
  58 {
  59     // Sanity checks off by default for performance, because otherwise
  60     // accepting transactions becomes O(N^2) where N is the number
  61     // of transactions in the pool
  62     nCheckFrequency = 0;
  63
  64     minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
  65 }
  66
  67 CTxMemPool::~CTxMemPool()
  68 {
  69     delete minerPolicyEstimator;
  70 }
  71
  72 void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
  73 {
  74     LOCK(cs);
  75
  76     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
  77
  78     // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
  79     while (it != mapNextTx.end() && it->first.hash == hashTx) {
  80         coins.Spend(it->first.n); // and remove those outputs from coins
  81         it++;
  82     }
  83 }
  84
  85 unsigned int CTxMemPool::GetTransactionsUpdated() const
  86 {
  87     LOCK(cs);
  88     return nTransactionsUpdated;
  89 }
  90
  91 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
  92 {
  93     LOCK(cs);
  94     nTransactionsUpdated += n;
  95 }
  96
  97
  98 bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
  99 {
 100     // Add to memory pool without checking anything.
 101     // Used by main.cpp AcceptToMemoryPool(), which DOES do
 102     // all the appropriate checks.
 103     LOCK(cs);
 104     mapTx.insert(entry);
 105     const CTransaction& tx = mapTx.find(hash)->GetTx();
 106     for (unsigned int i = 0; i < tx.vin.size(); i++)
 107         mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
 108     BOOST_FOREACH(const JSDescription &joinsplit, tx.vJoinSplit) {
 109         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 110             mapSproutNullifiers[nf] = &tx;
 111         }
 112     }
 113     for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 114         mapSaplingNullifiers[spendDescription.nullifier] = &tx;
 115     }
 116     nTransactionsUpdated++;
 117     totalTxSize += entry.GetTxSize();
 118     cachedInnerUsage += entry.DynamicMemoryUsage();
 119     minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
 120
 121     return true;
 122 }
 123
 124 void CTxMemPool::addAddressIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view)
 125 {
 126     LOCK(cs);
 127     const CTransaction& tx = entry.GetTx();
 128     std::vector<CMempoolAddressDeltaKey> inserted;
 129
 130     uint256 txhash = tx.GetHash();
 131     for (unsigned int j = 0; j < tx.vin.size(); j++) {
 132         const CTxIn input = tx.vin[j];
 133         const CTxOut &prevout = view.GetOutputFor(input);
 134         CScript::ScriptType type = prevout.scriptPubKey.GetType();
 135         if (type == CScript::UNKNOWN)
 136             continue;
 137         CMempoolAddressDeltaKey key(type, prevout.scriptPubKey.AddressHash(), txhash, j, 1);
 138         CMempoolAddressDelta delta(entry.GetTime(), prevout.nValue * -1, input.prevout.hash, input.prevout.n);
 139         mapAddress.insert(make_pair(key, delta));
 140         inserted.push_back(key);
 141     }
 142
 143     for (unsigned int j = 0; j < tx.vout.size(); j++) {
 144         const CTxOut &out = tx.vout[j];
 145         CScript::ScriptType type = out.scriptPubKey.GetType();
 146         if (type == CScript::UNKNOWN)
 147             continue;
 148         CMempoolAddressDeltaKey key(type, out.scriptPubKey.AddressHash(), txhash, j, 0);
 149         mapAddress.insert(make_pair(key, CMempoolAddressDelta(entry.GetTime(), out.nValue)));
 150         inserted.push_back(key);
 151     }
 152
 153     mapAddressInserted.insert(make_pair(txhash, inserted));
 154 }
 155
 156 // START insightexplorer
 157 void CTxMemPool::getAddressIndex(
 158     const std::vector<std::pair<uint160, int>>& addresses,
 159     std::vector<std::pair<CMempoolAddressDeltaKey, CMempoolAddressDelta>>& results)
 160 {
 161     LOCK(cs);
 162     for (const auto& it : addresses) {
 163         auto ait = mapAddress.lower_bound(CMempoolAddressDeltaKey(it.second, it.first));
 164         while (ait != mapAddress.end() && (*ait).first.addressBytes == it.first && (*ait).first.type == it.second) {
 165             results.push_back(*ait);
 166             ait++;
 167         }
 168     }
 169 }
 170
 171 void CTxMemPool::removeAddressIndex(const uint256& txhash)
 172 {
 173     LOCK(cs);
 174     auto it = mapAddressInserted.find(txhash);
 175
 176     if (it != mapAddressInserted.end()) {
 177         std::vector<CMempoolAddressDeltaKey> keys = it->second;
 178         for (const auto& mit : keys) {
 179             mapAddress.erase(mit);
 180         }
 181         mapAddressInserted.erase(it);
 182     }
 183 }
 184
 185 void CTxMemPool::addSpentIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view)
 186 {
 187     LOCK(cs);
 188     const CTransaction& tx = entry.GetTx();
 189     uint256 txhash = tx.GetHash();
 190     std::vector<CSpentIndexKey> inserted;
 191
 192     for (unsigned int j = 0; j < tx.vin.size(); j++) {
 193         const CTxIn input = tx.vin[j];
 194         const CTxOut &prevout = view.GetOutputFor(input);
 195         CSpentIndexKey key = CSpentIndexKey(input.prevout.hash, input.prevout.n);
 196         CSpentIndexValue value = CSpentIndexValue(txhash, j, -1, prevout.nValue,
 197             prevout.scriptPubKey.GetType(),
 198             prevout.scriptPubKey.AddressHash());
 199         mapSpent.insert(make_pair(key, value));
 200         inserted.push_back(key);
 201     }
 202     mapSpentInserted.insert(make_pair(txhash, inserted));
 203 }
 204
 205 bool CTxMemPool::getSpentIndex(const CSpentIndexKey &key, CSpentIndexValue &value)
 206 {
 207     LOCK(cs);
 208     std::map<CSpentIndexKey, CSpentIndexValue, CSpentIndexKeyCompare>::iterator it = mapSpent.find(key);
 209     if (it != mapSpent.end()) {
 210         value = it->second;
 211         return true;
 212     }
 213     return false;
 214 }
 215
 216 void CTxMemPool::removeSpentIndex(const uint256 txhash)
 217 {
 218     LOCK(cs);
 219     auto it = mapSpentInserted.find(txhash);
 220
 221     if (it != mapSpentInserted.end()) {
 222         std::vector<CSpentIndexKey> keys = (*it).second;
 223         for (std::vector<CSpentIndexKey>::iterator mit = keys.begin(); mit != keys.end(); mit++) {
 224             mapSpent.erase(*mit);
 225         }
 226         mapSpentInserted.erase(it);
 227     }
 228 }
 229 // END insightexplorer
 230
 231 void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
 232 {
 233     // Remove transaction from memory pool
 234     {
 235         LOCK(cs);
 236         std::deque<uint256> txToRemove;
 237         txToRemove.push_back(origTx.GetHash());
 238         if (fRecursive && !mapTx.count(origTx.GetHash())) {
 239             // If recursively removing but origTx isn't in the mempool
 240             // be sure to remove any children that are in the pool. This can
 241             // happen during chain re-orgs if origTx isn't re-accepted into
 242             // the mempool for any reason.
 243             for (unsigned int i = 0; i < origTx.vout.size(); i++) {
 244                 std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
 245                 if (it == mapNextTx.end())
 246                     continue;
 247                 txToRemove.push_back(it->second.ptx->GetHash());
 248             }
 249         }
 250         while (!txToRemove.empty())
 251         {
 252             uint256 hash = txToRemove.front();
 253             txToRemove.pop_front();
 254             if (!mapTx.count(hash))
 255                 continue;
 256             const CTransaction& tx = mapTx.find(hash)->GetTx();
 257             if (fRecursive) {
 258                 for (unsigned int i = 0; i < tx.vout.size(); i++) {
 259                     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
 260                     if (it == mapNextTx.end())
 261                         continue;
 262                     txToRemove.push_back(it->second.ptx->GetHash());
 263                 }
 264             }
 265             BOOST_FOREACH(const CTxIn& txin, tx.vin)
 266                 mapNextTx.erase(txin.prevout);
 267             BOOST_FOREACH(const JSDescription& joinsplit, tx.vJoinSplit) {
 268                 BOOST_FOREACH(const uint256& nf, joinsplit.nullifiers) {
 269                     mapSproutNullifiers.erase(nf);
 270                 }
 271             }
 272             for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 273                 mapSaplingNullifiers.erase(spendDescription.nullifier);
 274             }
 275             removed.push_back(tx);
 276             totalTxSize -= mapTx.find(hash)->GetTxSize();
 277             cachedInnerUsage -= mapTx.find(hash)->DynamicMemoryUsage();
 278             mapTx.erase(hash);
 279             nTransactionsUpdated++;
 280             minerPolicyEstimator->removeTx(hash);
 281
 282             // insightexplorer
 283             if (fAddressIndex)
 284                 removeAddressIndex(hash);
 285             if (fSpentIndex)
 286                 removeSpentIndex(hash);
 287         }
 288     }
 289 }
 290
 291 void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
 292 {
 293     // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
 294     LOCK(cs);
 295     list<CTransaction> transactionsToRemove;
 296     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 297         const CTransaction& tx = it->GetTx();
 298         if (!CheckFinalTx(tx, flags)) {
 299             transactionsToRemove.push_back(tx);
 300         } else if (it->GetSpendsCoinbase()) {
 301             BOOST_FOREACH(const CTxIn& txin, tx.vin) {
 302                 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 303                 if (it2 != mapTx.end())
 304                     continue;
 305                 const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
 306                 if (nCheckFrequency != 0) assert(coins);
 307                 if (!coins || (coins->IsCoinBase() && ((signed long)nMemPoolHeight) - coins->nHeight < COINBASE_MATURITY)) {
 308                     transactionsToRemove.push_back(tx);
 309                     break;
 310                 }
 311             }
 312         }
 313     }
 314     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 315         list<CTransaction> removed;
 316         remove(tx, removed, true);
 317     }
 318 }
 319
 320
 321 void CTxMemPool::removeWithAnchor(const uint256 &invalidRoot, ShieldedType type)
 322 {
 323     // If a block is disconnected from the tip, and the root changed,
 324     // we must invalidate transactions from the mempool which spend
 325     // from that root -- almost as though they were spending coinbases
 326     // which are no longer valid to spend due to coinbase maturity.
 327     LOCK(cs);
 328     list<CTransaction> transactionsToRemove;
 329
 330     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 331         const CTransaction& tx = it->GetTx();
 332         switch (type) {
 333             case SPROUT:
 334                 BOOST_FOREACH(const JSDescription& joinsplit, tx.vJoinSplit) {
 335                     if (joinsplit.anchor == invalidRoot) {
 336                         transactionsToRemove.push_back(tx);
 337                         break;
 338                     }
 339                 }
 340             break;
 341             case SAPLING:
 342                 BOOST_FOREACH(const SpendDescription& spendDescription, tx.vShieldedSpend) {
 343                     if (spendDescription.anchor == invalidRoot) {
 344                         transactionsToRemove.push_back(tx);
 345                         break;
 346                     }
 347                 }
 348             break;
 349             default:
 350                 throw runtime_error("Unknown shielded type");
 351             break;
 352         }
 353     }
 354
 355     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 356         list<CTransaction> removed;
 357         remove(tx, removed, true);
 358     }
 359 }
 360
 361 void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
 362 {
 363     // Remove transactions which depend on inputs of tx, recursively
 364     list<CTransaction> result;
 365     LOCK(cs);
 366     BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 367         std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
 368         if (it != mapNextTx.end()) {
 369             const CTransaction &txConflict = *it->second.ptx;
 370             if (txConflict != tx)
 371             {
 372                 remove(txConflict, removed, true);
 373             }
 374         }
 375     }
 376
 377     BOOST_FOREACH(const JSDescription &joinsplit, tx.vJoinSplit) {
 378         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 379             std::map<uint256, const CTransaction*>::iterator it = mapSproutNullifiers.find(nf);
 380             if (it != mapSproutNullifiers.end()) {
 381                 const CTransaction &txConflict = *it->second;
 382                 if (txConflict != tx) {
 383                     remove(txConflict, removed, true);
 384                 }
 385             }
 386         }
 387     }
 388     for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 389         std::map<uint256, const CTransaction*>::iterator it = mapSaplingNullifiers.find(spendDescription.nullifier);
 390         if (it != mapSaplingNullifiers.end()) {
 391             const CTransaction &txConflict = *it->second;
 392             if (txConflict != tx) {
 393                 remove(txConflict, removed, true);
 394             }
 395         }
 396     }
 397 }
 398
 399 void CTxMemPool::removeExpired(unsigned int nBlockHeight)
 400 {
 401     // Remove expired txs from the mempool
 402     LOCK(cs);
 403     list<CTransaction> transactionsToRemove;
 404     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++)
 405     {
 406         const CTransaction& tx = it->GetTx();
 407         if (IsExpiredTx(tx, nBlockHeight)) {
 408             transactionsToRemove.push_back(tx);
 409         }
 410     }
 411     for (const CTransaction& tx : transactionsToRemove) {
 412         list<CTransaction> removed;
 413         remove(tx, removed, true);
 414         LogPrint("mempool", "Removing expired txid: %s\n", tx.GetHash().ToString());
 415     }
 416 }
 417
 418 /**
 419  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 420  */
 421 void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 422                                 std::list<CTransaction>& conflicts, bool fCurrentEstimate)
 423 {
 424     LOCK(cs);
 425     std::vector<CTxMemPoolEntry> entries;
 426     BOOST_FOREACH(const CTransaction& tx, vtx)
 427     {
 428         uint256 hash = tx.GetHash();
 429
 430         indexed_transaction_set::iterator i = mapTx.find(hash);
 431         if (i != mapTx.end())
 432             entries.push_back(*i);
 433     }
 434     BOOST_FOREACH(const CTransaction& tx, vtx)
 435     {
 436         std::list<CTransaction> dummy;
 437         remove(tx, dummy, false);
 438         removeConflicts(tx, conflicts);
 439         ClearPrioritisation(tx.GetHash());
 440     }
 441     // After the txs in the new block have been removed from the mempool, update policy estimates
 442     minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
 443 }
 444
 445 /**
 446  * Called whenever the tip changes. Removes transactions which don't commit to
 447  * the given branch ID from the mempool.
 448  */
 449 void CTxMemPool::removeWithoutBranchId(uint32_t nMemPoolBranchId)
 450 {
 451     LOCK(cs);
 452     std::list<CTransaction> transactionsToRemove;
 453
 454     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 455         const CTransaction& tx = it->GetTx();
 456         if (it->GetValidatedBranchId() != nMemPoolBranchId) {
 457             transactionsToRemove.push_back(tx);
 458         }
 459     }
 460
 461     for (const CTransaction& tx : transactionsToRemove) {
 462         std::list<CTransaction> removed;
 463         remove(tx, removed, true);
 464     }
 465 }
 466
 467 void CTxMemPool::clear()
 468 {
 469     LOCK(cs);
 470     mapTx.clear();
 471     mapNextTx.clear();
 472     totalTxSize = 0;
 473     cachedInnerUsage = 0;
 474     ++nTransactionsUpdated;
 475 }
 476
 477 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 478 {
 479     if (nCheckFrequency == 0)
 480         return;
 481
 482     if (insecure_rand() >= nCheckFrequency)
 483         return;
 484
 485     LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 486
 487     uint64_t checkTotal = 0;
 488     uint64_t innerUsage = 0;
 489
 490     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 491     const int64_t nSpendHeight = GetSpendHeight(mempoolDuplicate);
 492
 493     LOCK(cs);
 494     list<const CTxMemPoolEntry*> waitingOnDependants;
 495     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 496         unsigned int i = 0;
 497         checkTotal += it->GetTxSize();
 498         innerUsage += it->DynamicMemoryUsage();
 499         const CTransaction& tx = it->GetTx();
 500         bool fDependsWait = false;
 501         BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 502             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 503             indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 504             if (it2 != mapTx.end()) {
 505                 const CTransaction& tx2 = it2->GetTx();
 506                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 507                 fDependsWait = true;
 508             } else {
 509                 const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
 510                 assert(coins && coins->IsAvailable(txin.prevout.n));
 511             }
 512             // Check whether its inputs are marked in mapNextTx.
 513             std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
 514             assert(it3 != mapNextTx.end());
 515             assert(it3->second.ptx == &tx);
 516             assert(it3->second.n == i);
 517             i++;
 518         }
 519
 520         boost::unordered_map<uint256, SproutMerkleTree, CCoinsKeyHasher> intermediates;
 521
 522         BOOST_FOREACH(const JSDescription &joinsplit, tx.vJoinSplit) {
 523             BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 524                 assert(!pcoins->GetNullifier(nf, SPROUT));
 525             }
 526
 527             SproutMerkleTree tree;
 528             auto it = intermediates.find(joinsplit.anchor);
 529             if (it != intermediates.end()) {
 530                 tree = it->second;
 531             } else {
 532                 assert(pcoins->GetSproutAnchorAt(joinsplit.anchor, tree));
 533             }
 534
 535             BOOST_FOREACH(const uint256& commitment, joinsplit.commitments)
 536             {
 537                 tree.append(commitment);
 538             }
 539
 540             intermediates.insert(std::make_pair(tree.root(), tree));
 541         }
 542         for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 543             SaplingMerkleTree tree;
 544
 545             assert(pcoins->GetSaplingAnchorAt(spendDescription.anchor, tree));
 546             assert(!pcoins->GetNullifier(spendDescription.nullifier, SAPLING));
 547         }
 548         if (fDependsWait)
 549             waitingOnDependants.push_back(&(*it));
 550         else {
 551             CValidationState state;
 552             bool fCheckResult = tx.IsCoinBase() ||
 553                 Consensus::CheckTxInputs(tx, state, mempoolDuplicate, nSpendHeight, Params().GetConsensus());
 554             assert(fCheckResult);
 555             UpdateCoins(tx, mempoolDuplicate, 1000000);
 556         }
 557     }
 558     unsigned int stepsSinceLastRemove = 0;
 559     while (!waitingOnDependants.empty()) {
 560         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 561         waitingOnDependants.pop_front();
 562         CValidationState state;
 563         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 564             waitingOnDependants.push_back(entry);
 565             stepsSinceLastRemove++;
 566             assert(stepsSinceLastRemove < waitingOnDependants.size());
 567         } else {
 568             bool fCheckResult = entry->GetTx().IsCoinBase() ||
 569                 Consensus::CheckTxInputs(entry->GetTx(), state, mempoolDuplicate, nSpendHeight, Params().GetConsensus());
 570             assert(fCheckResult);
 571             UpdateCoins(entry->GetTx(), mempoolDuplicate, 1000000);
 572             stepsSinceLastRemove = 0;
 573         }
 574     }
 575     for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
 576         uint256 hash = it->second.ptx->GetHash();
 577         indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
 578         const CTransaction& tx = it2->GetTx();
 579         assert(it2 != mapTx.end());
 580         assert(&tx == it->second.ptx);
 581         assert(tx.vin.size() > it->second.n);
 582         assert(it->first == it->second.ptx->vin[it->second.n].prevout);
 583     }
 584
 585     checkNullifiers(SPROUT);
 586     checkNullifiers(SAPLING);
 587
 588     assert(totalTxSize == checkTotal);
 589     assert(innerUsage == cachedInnerUsage);
 590 }
 591
 592 void CTxMemPool::checkNullifiers(ShieldedType type) const
 593 {
 594     const std::map<uint256, const CTransaction*>* mapToUse;
 595     switch (type) {
 596         case SPROUT:
 597             mapToUse = &mapSproutNullifiers;
 598             break;
 599         case SAPLING:
 600             mapToUse = &mapSaplingNullifiers;
 601             break;
 602         default:
 603             throw runtime_error("Unknown nullifier type");
 604     }
 605     for (const auto& entry : *mapToUse) {
 606         uint256 hash = entry.second->GetHash();
 607         CTxMemPool::indexed_transaction_set::const_iterator findTx = mapTx.find(hash);
 608         const CTransaction& tx = findTx->GetTx();
 609         assert(findTx != mapTx.end());
 610         assert(&tx == entry.second);
 611     }
 612 }
 613
 614 void CTxMemPool::queryHashes(vector<uint256>& vtxid)
 615 {
 616     vtxid.clear();
 617
 618     LOCK(cs);
 619     vtxid.reserve(mapTx.size());
 620     for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
 621         vtxid.push_back(mi->GetTx().GetHash());
 622 }
 623
 624 bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
 625 {
 626     LOCK(cs);
 627     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 628     if (i == mapTx.end()) return false;
 629     result = i->GetTx();
 630     return true;
 631 }
 632
 633 CFeeRate CTxMemPool::estimateFee(int nBlocks) const
 634 {
 635     LOCK(cs);
 636     return minerPolicyEstimator->estimateFee(nBlocks);
 637 }
 638 double CTxMemPool::estimatePriority(int nBlocks) const
 639 {
 640     LOCK(cs);
 641     return minerPolicyEstimator->estimatePriority(nBlocks);
 642 }
 643
 644 bool
 645 CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
 646 {
 647     try {
 648         LOCK(cs);
 649         fileout << 109900; // version required to read: 0.10.99 or later
 650         fileout << CLIENT_VERSION; // version that wrote the file
 651         minerPolicyEstimator->Write(fileout);
 652     }
 653     catch (const std::exception&) {
 654         LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
 655         return false;
 656     }
 657     return true;
 658 }
 659
 660 bool
 661 CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
 662 {
 663     try {
 664         int nVersionRequired, nVersionThatWrote;
 665         filein >> nVersionRequired >> nVersionThatWrote;
 666         if (nVersionRequired > CLIENT_VERSION)
 667             return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
 668
 669         LOCK(cs);
 670         minerPolicyEstimator->Read(filein);
 671     }
 672     catch (const std::exception&) {
 673         LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
 674         return false;
 675     }
 676     return true;
 677 }
 678
 679 void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
 680 {
 681     {
 682         LOCK(cs);
 683         std::pair<double, CAmount> &deltas = mapDeltas[hash];
 684         deltas.first += dPriorityDelta;
 685         deltas.second += nFeeDelta;
 686     }
 687     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 688 }
 689
 690 void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
 691 {
 692     LOCK(cs);
 693     std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
 694     if (pos == mapDeltas.end())
 695         return;
 696     const std::pair<double, CAmount> &deltas = pos->second;
 697     dPriorityDelta += deltas.first;
 698     nFeeDelta += deltas.second;
 699 }
 700
 701 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 702 {
 703     LOCK(cs);
 704     mapDeltas.erase(hash);
 705 }
 706
 707 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
 708 {
 709     for (unsigned int i = 0; i < tx.vin.size(); i++)
 710         if (exists(tx.vin[i].prevout.hash))
 711             return false;
 712     return true;
 713 }
 714
 715 bool CTxMemPool::nullifierExists(const uint256& nullifier, ShieldedType type) const
 716 {
 717     switch (type) {
 718         case SPROUT:
 719             return mapSproutNullifiers.count(nullifier);
 720         case SAPLING:
 721             return mapSaplingNullifiers.count(nullifier);
 722         default:
 723             throw runtime_error("Unknown nullifier type");
 724     }
 725 }
 726
 727 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 728
 729 bool CCoinsViewMemPool::GetNullifier(const uint256 &nf, ShieldedType type) const
 730 {
 731     return mempool.nullifierExists(nf, type) || base->GetNullifier(nf, type);
 732 }
 733
 734 bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
 735     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 736     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 737     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 738     CTransaction tx;
 739     if (mempool.lookup(txid, tx)) {
 740         coins = CCoins(tx, MEMPOOL_HEIGHT);
 741         return true;
 742     }
 743     return (base->GetCoins(txid, coins) && !coins.IsPruned());
 744 }
 745
 746 bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 747     return mempool.exists(txid) || base->HaveCoins(txid);
 748 }
 749
 750 size_t CTxMemPool::DynamicMemoryUsage() const {
 751     LOCK(cs);
 752     // Estimate the overhead of mapTx to be 6 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
 753     return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 6 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + cachedInnerUsage;
 754 }