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     if (!tx.IsCoinImport()) {
 108         for (unsigned int i = 0; i < tx.vin.size(); i++)
 109             mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
 110     }
 111     BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 112         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 113             mapSproutNullifiers[nf] = &tx;
 114         }
 115     }
 116     for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 117         mapSaplingNullifiers[spendDescription.nullifier] = &tx;
 118     }
 119     nTransactionsUpdated++;
 120     totalTxSize += entry.GetTxSize();
 121     cachedInnerUsage += entry.DynamicMemoryUsage();
 122     minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
 123
 124     return true;
 125 }
 126
 127 void CTxMemPool::addAddressIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view)
 128 {
 129     LOCK(cs);
 130     const CTransaction& tx = entry.GetTx();
 131     std::vector<CMempoolAddressDeltaKey> inserted;
 132
 133     uint256 txhash = tx.GetHash();
 134     for (unsigned int j = 0; j < tx.vin.size(); j++) {
 135         const CTxIn input = tx.vin[j];
 136         const CTxOut &prevout = view.GetOutputFor(input);
 137         if (prevout.scriptPubKey.IsPayToScriptHash()) {
 138             vector<unsigned char> hashBytes(prevout.scriptPubKey.begin()+2, prevout.scriptPubKey.begin()+22);
 139             CMempoolAddressDeltaKey key(2, uint160(hashBytes), txhash, j, 1);
 140             CMempoolAddressDelta delta(entry.GetTime(), prevout.nValue * -1, input.prevout.hash, input.prevout.n);
 141             mapAddress.insert(make_pair(key, delta));
 142             inserted.push_back(key);
 143         }
 144         else if (prevout.scriptPubKey.IsPayToPublicKeyHash()) {
 145             vector<unsigned char> hashBytes(prevout.scriptPubKey.begin()+3, prevout.scriptPubKey.begin()+23);
 146             CMempoolAddressDeltaKey key(1, uint160(hashBytes), txhash, j, 1);
 147             CMempoolAddressDelta delta(entry.GetTime(), prevout.nValue * -1, input.prevout.hash, input.prevout.n);
 148             mapAddress.insert(make_pair(key, delta));
 149             inserted.push_back(key);
 150         }
 151         else if (prevout.scriptPubKey.IsPayToPublicKey()) {
 152             vector<unsigned char> hashBytes(prevout.scriptPubKey.begin()+1, prevout.scriptPubKey.begin()+34);
 153             CMempoolAddressDeltaKey key(1, Hash160(hashBytes), txhash, j, 1);
 154             CMempoolAddressDelta delta(entry.GetTime(), prevout.nValue * -1, input.prevout.hash, input.prevout.n);
 155             mapAddress.insert(make_pair(key, delta));
 156             inserted.push_back(key);
 157         }
 158         else if (prevout.scriptPubKey.IsPayToCryptoCondition()) {
 159             vector<unsigned char> hashBytes(prevout.scriptPubKey.begin(), prevout.scriptPubKey.end());
 160             CMempoolAddressDeltaKey key(1, Hash160(hashBytes), txhash, j, 1);
 161             CMempoolAddressDelta delta(entry.GetTime(), prevout.nValue * -1, input.prevout.hash, input.prevout.n);
 162             mapAddress.insert(make_pair(key, delta));
 163             inserted.push_back(key);
 164         }   }
 165
 166     for (unsigned int k = 0; k < tx.vout.size(); k++) {
 167         const CTxOut &out = tx.vout[k];
 168         if (out.scriptPubKey.IsPayToScriptHash()) {
 169             vector<unsigned char> hashBytes(out.scriptPubKey.begin()+2, out.scriptPubKey.begin()+22);
 170             CMempoolAddressDeltaKey key(2, uint160(hashBytes), txhash, k, 0);
 171             mapAddress.insert(make_pair(key, CMempoolAddressDelta(entry.GetTime(), out.nValue)));
 172             inserted.push_back(key);
 173         }
 174         else if (out.scriptPubKey.IsPayToPublicKeyHash()) {
 175             vector<unsigned char> hashBytes(out.scriptPubKey.begin()+3, out.scriptPubKey.begin()+23);
 176             std::pair<addressDeltaMap::iterator,bool> ret;
 177             CMempoolAddressDeltaKey key(1, uint160(hashBytes), txhash, k, 0);
 178             mapAddress.insert(make_pair(key, CMempoolAddressDelta(entry.GetTime(), out.nValue)));
 179             inserted.push_back(key);
 180         }
 181         else if (out.scriptPubKey.IsPayToPublicKey()) {
 182             vector<unsigned char> hashBytes(out.scriptPubKey.begin()+1, out.scriptPubKey.begin()+34);
 183             std::pair<addressDeltaMap::iterator,bool> ret;
 184             CMempoolAddressDeltaKey key(1, Hash160(hashBytes), txhash, k, 0);
 185             mapAddress.insert(make_pair(key, CMempoolAddressDelta(entry.GetTime(), out.nValue)));
 186             inserted.push_back(key);
 187         }
 188         else if (out.scriptPubKey.IsPayToCryptoCondition()) {
 189             vector<unsigned char> hashBytes(out.scriptPubKey.begin(), out.scriptPubKey.end());
 190             std::pair<addressDeltaMap::iterator,bool> ret;
 191             CMempoolAddressDeltaKey key(1, Hash160(hashBytes), txhash, k, 0);
 192             mapAddress.insert(make_pair(key, CMempoolAddressDelta(entry.GetTime(), out.nValue)));
 193             inserted.push_back(key);
 194         }
 195     }
 196
 197     mapAddressInserted.insert(make_pair(txhash, inserted));
 198 }
 199
 200 bool CTxMemPool::getAddressIndex(std::vector<std::pair<uint160, int> > &addresses,
 201                                  std::vector<std::pair<CMempoolAddressDeltaKey, CMempoolAddressDelta> > &results)
 202 {
 203     LOCK(cs);
 204     for (std::vector<std::pair<uint160, int> >::iterator it = addresses.begin(); it != addresses.end(); it++) {
 205         addressDeltaMap::iterator ait = mapAddress.lower_bound(CMempoolAddressDeltaKey((*it).second, (*it).first));
 206         while (ait != mapAddress.end() && (*ait).first.addressBytes == (*it).first && (*ait).first.type == (*it).second) {
 207             results.push_back(*ait);
 208             ait++;
 209         }
 210     }
 211     return true;
 212 }
 213
 214 bool CTxMemPool::removeAddressIndex(const uint256 txhash)
 215 {
 216     LOCK(cs);
 217     addressDeltaMapInserted::iterator it = mapAddressInserted.find(txhash);
 218
 219     if (it != mapAddressInserted.end()) {
 220         std::vector<CMempoolAddressDeltaKey> keys = (*it).second;
 221         for (std::vector<CMempoolAddressDeltaKey>::iterator mit = keys.begin(); mit != keys.end(); mit++) {
 222             mapAddress.erase(*mit);
 223         }
 224         mapAddressInserted.erase(it);
 225     }
 226
 227     return true;
 228 }
 229
 230 void CTxMemPool::addSpentIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view)
 231 {
 232     LOCK(cs);
 233
 234     const CTransaction& tx = entry.GetTx();
 235     std::vector<CSpentIndexKey> inserted;
 236
 237     uint256 txhash = tx.GetHash();
 238     for (unsigned int j = 0; j < tx.vin.size(); j++) {
 239         const CTxIn input = tx.vin[j];
 240         const CTxOut &prevout = view.GetOutputFor(input);
 241         uint160 addressHash;
 242         int addressType;
 243
 244         if (prevout.scriptPubKey.IsPayToScriptHash()) {
 245             addressHash = uint160(vector<unsigned char> (prevout.scriptPubKey.begin()+2, prevout.scriptPubKey.begin()+22));
 246             addressType = 2;
 247         }
 248         else if (prevout.scriptPubKey.IsPayToPublicKeyHash()) {
 249             addressHash = uint160(vector<unsigned char> (prevout.scriptPubKey.begin()+3, prevout.scriptPubKey.begin()+23));
 250             addressType = 1;
 251         }
 252         else if (prevout.scriptPubKey.IsPayToPublicKey()) {
 253             addressHash = Hash160(vector<unsigned char> (prevout.scriptPubKey.begin()+1, prevout.scriptPubKey.begin()+34));
 254             addressType = 1;
 255         }
 256         else if (prevout.scriptPubKey.IsPayToCryptoCondition()) {
 257             addressHash = Hash160(vector<unsigned char> (prevout.scriptPubKey.begin(), prevout.scriptPubKey.end()));
 258             addressType = 1;
 259         }
 260         else {
 261             addressHash.SetNull();
 262             addressType = 0;
 263         }
 264
 265         CSpentIndexKey key = CSpentIndexKey(input.prevout.hash, input.prevout.n);
 266         CSpentIndexValue value = CSpentIndexValue(txhash, j, -1, prevout.nValue, addressType, addressHash);
 267
 268         mapSpent.insert(make_pair(key, value));
 269         inserted.push_back(key);
 270
 271     }
 272
 273     mapSpentInserted.insert(make_pair(txhash, inserted));
 274 }
 275
 276 bool CTxMemPool::getSpentIndex(CSpentIndexKey &key, CSpentIndexValue &value)
 277 {
 278     LOCK(cs);
 279     mapSpentIndex::iterator it;
 280
 281     it = mapSpent.find(key);
 282     if (it != mapSpent.end()) {
 283         value = it->second;
 284         return true;
 285     }
 286     return false;
 287 }
 288
 289 bool CTxMemPool::removeSpentIndex(const uint256 txhash)
 290 {
 291     LOCK(cs);
 292     mapSpentIndexInserted::iterator it = mapSpentInserted.find(txhash);
 293
 294     if (it != mapSpentInserted.end()) {
 295         std::vector<CSpentIndexKey> keys = (*it).second;
 296         for (std::vector<CSpentIndexKey>::iterator mit = keys.begin(); mit != keys.end(); mit++) {
 297             mapSpent.erase(*mit);
 298         }
 299         mapSpentInserted.erase(it);
 300     }
 301
 302     return true;
 303 }
 304
 305 void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
 306 {
 307     // Remove transaction from memory pool
 308     {
 309         LOCK(cs);
 310         std::deque<uint256> txToRemove;
 311         txToRemove.push_back(origTx.GetHash());
 312         if (fRecursive && !mapTx.count(origTx.GetHash())) {
 313             // If recursively removing but origTx isn't in the mempool
 314             // be sure to remove any children that are in the pool. This can
 315             // happen during chain re-orgs if origTx isn't re-accepted into
 316             // the mempool for any reason.
 317             for (unsigned int i = 0; i < origTx.vout.size(); i++) {
 318                 std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
 319                 if (it == mapNextTx.end())
 320                     continue;
 321                 txToRemove.push_back(it->second.ptx->GetHash());
 322             }
 323         }
 324         while (!txToRemove.empty())
 325         {
 326             uint256 hash = txToRemove.front();
 327             txToRemove.pop_front();
 328             if (!mapTx.count(hash))
 329                 continue;
 330             const CTransaction& tx = mapTx.find(hash)->GetTx();
 331             if (fRecursive) {
 332                 for (unsigned int i = 0; i < tx.vout.size(); i++) {
 333                     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
 334                     if (it == mapNextTx.end())
 335                         continue;
 336                     txToRemove.push_back(it->second.ptx->GetHash());
 337                 }
 338             }
 339             BOOST_FOREACH(const CTxIn& txin, tx.vin)
 340                 mapNextTx.erase(txin.prevout);
 341             BOOST_FOREACH(const JSDescription& joinsplit, tx.vjoinsplit) {
 342                 BOOST_FOREACH(const uint256& nf, joinsplit.nullifiers) {
 343                     mapSproutNullifiers.erase(nf);
 344                 }
 345             }
 346             for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 347                 mapSaplingNullifiers.erase(spendDescription.nullifier);
 348             }
 349             removed.push_back(tx);
 350             totalTxSize -= mapTx.find(hash)->GetTxSize();
 351             cachedInnerUsage -= mapTx.find(hash)->DynamicMemoryUsage();
 352             mapTx.erase(hash);
 353             nTransactionsUpdated++;
 354             minerPolicyEstimator->removeTx(hash);
 355             removeAddressIndex(hash);
 356             removeSpentIndex(hash);
 357         }
 358     }
 359 }
 360
 361 extern uint64_t ASSETCHAINS_TIMELOCKGTE;
 362 int64_t komodo_block_unlocktime(uint32_t nHeight);
 363
 364 void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
 365 {
 366     // Remove transactions spending a coinbase which are now immature
 367     extern char ASSETCHAINS_SYMBOL[KOMODO_ASSETCHAIN_MAXLEN];
 368     if ( ASSETCHAINS_SYMBOL[0] == 0 )
 369         COINBASE_MATURITY = _COINBASE_MATURITY;
 370     // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
 371     LOCK(cs);
 372     list<CTransaction> transactionsToRemove;
 373     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 374         const CTransaction& tx = it->GetTx();
 375         if (!CheckFinalTx(tx, flags)) {
 376             transactionsToRemove.push_back(tx);
 377         } else if (it->GetSpendsCoinbase()) {
 378             BOOST_FOREACH(const CTxIn& txin, tx.vin) {
 379                 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 380                 if (it2 != mapTx.end())
 381                     continue;
 382                 const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
 383                         if (nCheckFrequency != 0) assert(coins);
 384                 if (!coins || (coins->IsCoinBase() && (((signed long)nMemPoolHeight) - coins->nHeight < COINBASE_MATURITY) &&
 385                                                        ((signed long)nMemPoolHeight < komodo_block_unlocktime(coins->nHeight) &&
 386                                                          coins->IsAvailable(0) && coins->vout[0].nValue >= ASSETCHAINS_TIMELOCKGTE))) {
 387                     transactionsToRemove.push_back(tx);
 388                     break;
 389                 }
 390             }
 391         }
 392     }
 393     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 394         list<CTransaction> removed;
 395         remove(tx, removed, true);
 396     }
 397 }
 398
 399
 400 void CTxMemPool::removeWithAnchor(const uint256 &invalidRoot, ShieldedType type)
 401 {
 402     // If a block is disconnected from the tip, and the root changed,
 403     // we must invalidate transactions from the mempool which spend
 404     // from that root -- almost as though they were spending coinbases
 405     // which are no longer valid to spend due to coinbase maturity.
 406     LOCK(cs);
 407     list<CTransaction> transactionsToRemove;
 408
 409     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 410         const CTransaction& tx = it->GetTx();
 411         switch (type) {
 412             case SPROUT:
 413                 BOOST_FOREACH(const JSDescription& joinsplit, tx.vjoinsplit) {
 414                     if (joinsplit.anchor == invalidRoot) {
 415                         transactionsToRemove.push_back(tx);
 416                         break;
 417                     }
 418                 }
 419             break;
 420             case SAPLING:
 421                 BOOST_FOREACH(const SpendDescription& spendDescription, tx.vShieldedSpend) {
 422                     if (spendDescription.anchor == invalidRoot) {
 423                         transactionsToRemove.push_back(tx);
 424                         break;
 425                     }
 426                 }
 427             break;
 428             default:
 429                 throw runtime_error("Unknown shielded type");
 430             break;
 431         }
 432     }
 433
 434     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 435         list<CTransaction> removed;
 436         remove(tx, removed, true);
 437     }
 438 }
 439
 440 void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
 441 {
 442     // Remove transactions which depend on inputs of tx, recursively
 443     list<CTransaction> result;
 444     LOCK(cs);
 445     BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 446         std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
 447         if (it != mapNextTx.end()) {
 448             const CTransaction &txConflict = *it->second.ptx;
 449             if (txConflict != tx)
 450             {
 451                 remove(txConflict, removed, true);
 452             }
 453         }
 454     }
 455
 456     BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 457         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 458             std::map<uint256, const CTransaction*>::iterator it = mapSproutNullifiers.find(nf);
 459             if (it != mapSproutNullifiers.end()) {
 460                 const CTransaction &txConflict = *it->second;
 461                 if (txConflict != tx) {
 462                     remove(txConflict, removed, true);
 463                 }
 464             }
 465         }
 466     }
 467     for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 468         std::map<uint256, const CTransaction*>::iterator it = mapSaplingNullifiers.find(spendDescription.nullifier);
 469         if (it != mapSaplingNullifiers.end()) {
 470             const CTransaction &txConflict = *it->second;
 471             if (txConflict != tx) {
 472                 remove(txConflict, removed, true);
 473             }
 474         }
 475     }
 476 }
 477
 478 int32_t komodo_validate_interest(const CTransaction &tx,int32_t txheight,uint32_t nTime,int32_t dispflag);
 479 extern char ASSETCHAINS_SYMBOL[];
 480
 481 void CTxMemPool::removeExpired(unsigned int nBlockHeight)
 482 {
 483     CBlockIndex *tipindex;
 484     // Remove expired txs from the mempool
 485     LOCK(cs);
 486     list<CTransaction> transactionsToRemove;
 487     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++)
 488     {
 489         const CTransaction& tx = it->GetTx();
 490         tipindex = chainActive.LastTip();
 491         if (IsExpiredTx(tx, nBlockHeight) || (ASSETCHAINS_SYMBOL[0] == 0 && tipindex != 0 && komodo_validate_interest(tx,tipindex->GetHeight()+1,tipindex->GetMedianTimePast() + 777,0)) < 0)
 492         {
 493             transactionsToRemove.push_back(tx);
 494         }
 495     }
 496     for (const CTransaction& tx : transactionsToRemove) {
 497         list<CTransaction> removed;
 498         remove(tx, removed, true);
 499         LogPrint("mempool", "Removing expired txid: %s\n", tx.GetHash().ToString());
 500     }
 501 }
 502
 503 /**
 504  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 505  */
 506 void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 507                                 std::list<CTransaction>& conflicts, bool fCurrentEstimate)
 508 {
 509     LOCK(cs);
 510     std::vector<CTxMemPoolEntry> entries;
 511     BOOST_FOREACH(const CTransaction& tx, vtx)
 512     {
 513         uint256 hash = tx.GetHash();
 514
 515         indexed_transaction_set::iterator i = mapTx.find(hash);
 516         if (i != mapTx.end())
 517             entries.push_back(*i);
 518     }
 519     BOOST_FOREACH(const CTransaction& tx, vtx)
 520     {
 521         std::list<CTransaction> dummy;
 522         remove(tx, dummy, false);
 523         removeConflicts(tx, conflicts);
 524         ClearPrioritisation(tx.GetHash());
 525     }
 526     // After the txs in the new block have been removed from the mempool, update policy estimates
 527     minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
 528 }
 529
 530 /**
 531  * Called whenever the tip changes. Removes transactions which don't commit to
 532  * the given branch ID from the mempool.
 533  */
 534 void CTxMemPool::removeWithoutBranchId(uint32_t nMemPoolBranchId)
 535 {
 536     LOCK(cs);
 537     std::list<CTransaction> transactionsToRemove;
 538
 539     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 540         const CTransaction& tx = it->GetTx();
 541         if (it->GetValidatedBranchId() != nMemPoolBranchId) {
 542             transactionsToRemove.push_back(tx);
 543         }
 544     }
 545
 546     for (const CTransaction& tx : transactionsToRemove) {
 547         std::list<CTransaction> removed;
 548         remove(tx, removed, true);
 549     }
 550 }
 551
 552 void CTxMemPool::clear()
 553 {
 554     LOCK(cs);
 555     mapTx.clear();
 556     mapNextTx.clear();
 557     totalTxSize = 0;
 558     cachedInnerUsage = 0;
 559     ++nTransactionsUpdated;
 560 }
 561
 562 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 563 {
 564     if (nCheckFrequency == 0)
 565         return;
 566
 567     if (insecure_rand() >= nCheckFrequency)
 568         return;
 569
 570     LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 571
 572     uint64_t checkTotal = 0;
 573     uint64_t innerUsage = 0;
 574
 575     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 576     const int64_t nSpendHeight = GetSpendHeight(mempoolDuplicate);
 577
 578     LOCK(cs);
 579     list<const CTxMemPoolEntry*> waitingOnDependants;
 580     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 581         unsigned int i = 0;
 582         checkTotal += it->GetTxSize();
 583         innerUsage += it->DynamicMemoryUsage();
 584         const CTransaction& tx = it->GetTx();
 585         bool fDependsWait = false;
 586         BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 587             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 588             indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 589             if (it2 != mapTx.end()) {
 590                 const CTransaction& tx2 = it2->GetTx();
 591                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 592                 fDependsWait = true;
 593             } else {
 594                 const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
 595                 assert(coins && coins->IsAvailable(txin.prevout.n));
 596             }
 597             // Check whether its inputs are marked in mapNextTx.
 598             std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
 599             assert(it3 != mapNextTx.end());
 600             assert(it3->second.ptx == &tx);
 601             assert(it3->second.n == i);
 602             i++;
 603         }
 604
 605         boost::unordered_map<uint256, SproutMerkleTree, CCoinsKeyHasher> intermediates;
 606
 607         BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 608             BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 609                 assert(!pcoins->GetNullifier(nf, SPROUT));
 610             }
 611
 612             SproutMerkleTree tree;
 613             auto it = intermediates.find(joinsplit.anchor);
 614             if (it != intermediates.end()) {
 615                 tree = it->second;
 616             } else {
 617                 assert(pcoins->GetSproutAnchorAt(joinsplit.anchor, tree));
 618             }
 619
 620             BOOST_FOREACH(const uint256& commitment, joinsplit.commitments)
 621             {
 622                 tree.append(commitment);
 623             }
 624
 625             intermediates.insert(std::make_pair(tree.root(), tree));
 626         }
 627         for (const SpendDescription &spendDescription : tx.vShieldedSpend) {
 628             SaplingMerkleTree tree;
 629
 630             assert(pcoins->GetSaplingAnchorAt(spendDescription.anchor, tree));
 631             assert(!pcoins->GetNullifier(spendDescription.nullifier, SAPLING));
 632         }
 633         if (fDependsWait)
 634             waitingOnDependants.push_back(&(*it));
 635         else {
 636             CValidationState state;
 637             bool fCheckResult = tx.IsCoinBase() ||
 638                 Consensus::CheckTxInputs(tx, state, mempoolDuplicate, nSpendHeight, Params().GetConsensus());
 639             assert(fCheckResult);
 640             UpdateCoins(tx, mempoolDuplicate, 1000000);
 641         }
 642     }
 643     unsigned int stepsSinceLastRemove = 0;
 644     while (!waitingOnDependants.empty()) {
 645         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 646         waitingOnDependants.pop_front();
 647         CValidationState state;
 648         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 649             waitingOnDependants.push_back(entry);
 650             stepsSinceLastRemove++;
 651             assert(stepsSinceLastRemove < waitingOnDependants.size());
 652         } else {
 653             bool fCheckResult = entry->GetTx().IsCoinBase() ||
 654                 Consensus::CheckTxInputs(entry->GetTx(), state, mempoolDuplicate, nSpendHeight, Params().GetConsensus());
 655             assert(fCheckResult);
 656             UpdateCoins(entry->GetTx(), mempoolDuplicate, 1000000);
 657             stepsSinceLastRemove = 0;
 658         }
 659     }
 660     for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
 661         uint256 hash = it->second.ptx->GetHash();
 662         indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
 663         const CTransaction& tx = it2->GetTx();
 664         assert(it2 != mapTx.end());
 665         assert(&tx == it->second.ptx);
 666         assert(tx.vin.size() > it->second.n);
 667         assert(it->first == it->second.ptx->vin[it->second.n].prevout);
 668     }
 669
 670     checkNullifiers(SPROUT);
 671     checkNullifiers(SAPLING);
 672
 673     assert(totalTxSize == checkTotal);
 674     assert(innerUsage == cachedInnerUsage);
 675 }
 676
 677 void CTxMemPool::checkNullifiers(ShieldedType type) const
 678 {
 679     const std::map<uint256, const CTransaction*>* mapToUse;
 680     switch (type) {
 681         case SPROUT:
 682             mapToUse = &mapSproutNullifiers;
 683             break;
 684         case SAPLING:
 685             mapToUse = &mapSaplingNullifiers;
 686             break;
 687         default:
 688             throw runtime_error("Unknown nullifier type");
 689     }
 690     for (const auto& entry : *mapToUse) {
 691         uint256 hash = entry.second->GetHash();
 692         CTxMemPool::indexed_transaction_set::const_iterator findTx = mapTx.find(hash);
 693         const CTransaction& tx = findTx->GetTx();
 694         assert(findTx != mapTx.end());
 695         assert(&tx == entry.second);
 696     }
 697 }
 698
 699 void CTxMemPool::queryHashes(vector<uint256>& vtxid)
 700 {
 701     vtxid.clear();
 702
 703     LOCK(cs);
 704     vtxid.reserve(mapTx.size());
 705     for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
 706         vtxid.push_back(mi->GetTx().GetHash());
 707 }
 708
 709 bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
 710 {
 711     LOCK(cs);
 712     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 713     if (i == mapTx.end()) return false;
 714     result = i->GetTx();
 715     return true;
 716 }
 717
 718 CFeeRate CTxMemPool::estimateFee(int nBlocks) const
 719 {
 720     LOCK(cs);
 721     return minerPolicyEstimator->estimateFee(nBlocks);
 722 }
 723 double CTxMemPool::estimatePriority(int nBlocks) const
 724 {
 725     LOCK(cs);
 726     return minerPolicyEstimator->estimatePriority(nBlocks);
 727 }
 728
 729 bool
 730 CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
 731 {
 732     try {
 733         LOCK(cs);
 734         fileout << 109900; // version required to read: 0.10.99 or later
 735         fileout << CLIENT_VERSION; // version that wrote the file
 736         minerPolicyEstimator->Write(fileout);
 737     }
 738     catch (const std::exception&) {
 739         LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
 740         return false;
 741     }
 742     return true;
 743 }
 744
 745 bool
 746 CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
 747 {
 748     try {
 749         int nVersionRequired, nVersionThatWrote;
 750         filein >> nVersionRequired >> nVersionThatWrote;
 751         if (nVersionRequired > CLIENT_VERSION)
 752             return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
 753
 754         LOCK(cs);
 755         minerPolicyEstimator->Read(filein);
 756     }
 757     catch (const std::exception&) {
 758         LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
 759         return false;
 760     }
 761     return true;
 762 }
 763
 764 void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
 765 {
 766     {
 767         LOCK(cs);
 768         std::pair<double, CAmount> &deltas = mapDeltas[hash];
 769         deltas.first += dPriorityDelta;
 770         deltas.second += nFeeDelta;
 771     }
 772     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 773 }
 774
 775 void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
 776 {
 777     LOCK(cs);
 778     std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
 779     if (pos == mapDeltas.end())
 780         return;
 781     const std::pair<double, CAmount> &deltas = pos->second;
 782     dPriorityDelta += deltas.first;
 783     nFeeDelta += deltas.second;
 784 }
 785
 786 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 787 {
 788     LOCK(cs);
 789     mapDeltas.erase(hash);
 790 }
 791
 792 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
 793 {
 794     for (unsigned int i = 0; i < tx.vin.size(); i++)
 795         if (exists(tx.vin[i].prevout.hash))
 796             return false;
 797     return true;
 798 }
 799
 800 bool CTxMemPool::nullifierExists(const uint256& nullifier, ShieldedType type) const
 801 {
 802     switch (type) {
 803         case SPROUT:
 804             return mapSproutNullifiers.count(nullifier);
 805         case SAPLING:
 806             return mapSaplingNullifiers.count(nullifier);
 807         default:
 808             throw runtime_error("Unknown nullifier type");
 809     }
 810 }
 811
 812 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 813
 814 bool CCoinsViewMemPool::GetNullifier(const uint256 &nf, ShieldedType type) const
 815 {
 816     return mempool.nullifierExists(nf, type) || base->GetNullifier(nf, type);
 817 }
 818
 819 bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
 820     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 821     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 822     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 823     CTransaction tx;
 824     if (mempool.lookup(txid, tx)) {
 825         coins = CCoins(tx, MEMPOOL_HEIGHT);
 826         return true;
 827     }
 828     return (base->GetCoins(txid, coins) && !coins.IsPruned());
 829 }
 830
 831 bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 832     return mempool.exists(txid) || base->HaveCoins(txid);
 833 }
 834
 835 size_t CTxMemPool::DynamicMemoryUsage() const {
 836     LOCK(cs);
 837     // Estimate the overhead of mapTx to be 6 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
 838     return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 6 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + cachedInnerUsage;
 839 }