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