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