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