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 "util.h"
  15 #include "utilmoneystr.h"
  16 #include "version.h"
  17
  18 using namespace std;
  19
  20 CTxMemPoolEntry::CTxMemPoolEntry():
  21     nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0), hadNoDependencies(false)
  22 {
  23     nHeight = MEMPOOL_HEIGHT;
  24 }
  25
  26 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
  27                                  int64_t _nTime, double _dPriority,
  28                                  unsigned int _nHeight, bool poolHasNoInputsOf):
  29     tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight),
  30     hadNoDependencies(poolHasNoInputsOf)
  31 {
  32     nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
  33     nModSize = tx.CalculateModifiedSize(nTxSize);
  34 }
  35
  36 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
  37 {
  38     *this = other;
  39 }
  40
  41 double
  42 CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
  43 {
  44     CAmount nValueIn = tx.GetValueOut()+nFee;
  45     double deltaPriority = ((double)(currentHeight-nHeight)*nValueIn)/nModSize;
  46     double dResult = dPriority + deltaPriority;
  47     return dResult;
  48 }
  49
  50 CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
  51     nTransactionsUpdated(0)
  52 {
  53     // Sanity checks off by default for performance, because otherwise
  54     // accepting transactions becomes O(N^2) where N is the number
  55     // of transactions in the pool
  56     fSanityCheck = false;
  57
  58     minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
  59 }
  60
  61 CTxMemPool::~CTxMemPool()
  62 {
  63     delete minerPolicyEstimator;
  64 }
  65
  66 void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
  67 {
  68     LOCK(cs);
  69
  70     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
  71
  72     // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
  73     while (it != mapNextTx.end() && it->first.hash == hashTx) {
  74         coins.Spend(it->first.n); // and remove those outputs from coins
  75         it++;
  76     }
  77 }
  78
  79 unsigned int CTxMemPool::GetTransactionsUpdated() const
  80 {
  81     LOCK(cs);
  82     return nTransactionsUpdated;
  83 }
  84
  85 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
  86 {
  87     LOCK(cs);
  88     nTransactionsUpdated += n;
  89 }
  90
  91
  92 bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
  93 {
  94     // Add to memory pool without checking anything.
  95     // Used by main.cpp AcceptToMemoryPool(), which DOES do
  96     // all the appropriate checks.
  97     LOCK(cs);
  98     mapTx[hash] = entry;
  99     const CTransaction& tx = mapTx[hash].GetTx();
 100     for (unsigned int i = 0; i < tx.vin.size(); i++)
 101         mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
 102     BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 103         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 104             mapNullifiers[nf] = &tx;
 105         }
 106     }
 107     nTransactionsUpdated++;
 108     totalTxSize += entry.GetTxSize();
 109     minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
 110
 111     return true;
 112 }
 113
 114
 115 void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
 116 {
 117     // Remove transaction from memory pool
 118     {
 119         LOCK(cs);
 120         std::deque<uint256> txToRemove;
 121         txToRemove.push_back(origTx.GetHash());
 122         if (fRecursive && !mapTx.count(origTx.GetHash())) {
 123             // If recursively removing but origTx isn't in the mempool
 124             // be sure to remove any children that are in the pool. This can
 125             // happen during chain re-orgs if origTx isn't re-accepted into
 126             // the mempool for any reason.
 127             for (unsigned int i = 0; i < origTx.vout.size(); i++) {
 128                 std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
 129                 if (it == mapNextTx.end())
 130                     continue;
 131                 txToRemove.push_back(it->second.ptx->GetHash());
 132             }
 133         }
 134         while (!txToRemove.empty())
 135         {
 136             uint256 hash = txToRemove.front();
 137             txToRemove.pop_front();
 138             if (!mapTx.count(hash))
 139                 continue;
 140             const CTransaction& tx = mapTx[hash].GetTx();
 141             if (fRecursive) {
 142                 for (unsigned int i = 0; i < tx.vout.size(); i++) {
 143                     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
 144                     if (it == mapNextTx.end())
 145                         continue;
 146                     txToRemove.push_back(it->second.ptx->GetHash());
 147                 }
 148             }
 149             BOOST_FOREACH(const CTxIn& txin, tx.vin)
 150                 mapNextTx.erase(txin.prevout);
 151             BOOST_FOREACH(const JSDescription& joinsplit, tx.vjoinsplit) {
 152                 BOOST_FOREACH(const uint256& nf, joinsplit.nullifiers) {
 153                     mapNullifiers.erase(nf);
 154                 }
 155             }
 156
 157             removed.push_back(tx);
 158             totalTxSize -= mapTx[hash].GetTxSize();
 159             mapTx.erase(hash);
 160             nTransactionsUpdated++;
 161             minerPolicyEstimator->removeTx(hash);
 162         }
 163     }
 164 }
 165
 166 void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight)
 167 {
 168     // Remove transactions spending a coinbase which are now immature
 169     LOCK(cs);
 170     list<CTransaction> transactionsToRemove;
 171     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 172         const CTransaction& tx = it->second.GetTx();
 173         BOOST_FOREACH(const CTxIn& txin, tx.vin) {
 174             std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
 175             if (it2 != mapTx.end())
 176                 continue;
 177             const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
 178             if (fSanityCheck) assert(coins);
 179             if (!coins || (coins->IsCoinBase() && nMemPoolHeight - coins->nHeight < COINBASE_MATURITY)) {
 180                 transactionsToRemove.push_back(tx);
 181                 break;
 182             }
 183         }
 184     }
 185     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 186         list<CTransaction> removed;
 187         remove(tx, removed, true);
 188     }
 189 }
 190
 191
 192 void CTxMemPool::removeWithAnchor(const uint256 &invalidRoot)
 193 {
 194     // If a block is disconnected from the tip, and the root changed,
 195     // we must invalidate transactions from the mempool which spend
 196     // from that root -- almost as though they were spending coinbases
 197     // which are no longer valid to spend due to coinbase maturity.
 198     LOCK(cs);
 199     list<CTransaction> transactionsToRemove;
 200
 201     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 202         const CTransaction& tx = it->second.GetTx();
 203         BOOST_FOREACH(const JSDescription& joinsplit, tx.vjoinsplit) {
 204             if (joinsplit.anchor == invalidRoot) {
 205                 transactionsToRemove.push_back(tx);
 206                 break;
 207             }
 208         }
 209     }
 210
 211     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 212         list<CTransaction> removed;
 213         remove(tx, removed, true);
 214     }
 215 }
 216
 217 void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
 218 {
 219     // Remove transactions which depend on inputs of tx, recursively
 220     list<CTransaction> result;
 221     LOCK(cs);
 222     BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 223         std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
 224         if (it != mapNextTx.end()) {
 225             const CTransaction &txConflict = *it->second.ptx;
 226             if (txConflict != tx)
 227             {
 228                 remove(txConflict, removed, true);
 229             }
 230         }
 231     }
 232
 233     BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 234         BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 235             std::map<uint256, const CTransaction*>::iterator it = mapNullifiers.find(nf);
 236             if (it != mapNullifiers.end()) {
 237                 const CTransaction &txConflict = *it->second;
 238                 if (txConflict != tx)
 239                 {
 240                     remove(txConflict, removed, true);
 241                 }
 242             }
 243         }
 244     }
 245 }
 246
 247 /**
 248  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 249  */
 250 void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 251                                 std::list<CTransaction>& conflicts, bool fCurrentEstimate)
 252 {
 253     LOCK(cs);
 254     std::vector<CTxMemPoolEntry> entries;
 255     BOOST_FOREACH(const CTransaction& tx, vtx)
 256     {
 257         uint256 hash = tx.GetHash();
 258         if (mapTx.count(hash))
 259             entries.push_back(mapTx[hash]);
 260     }
 261     BOOST_FOREACH(const CTransaction& tx, vtx)
 262     {
 263         std::list<CTransaction> dummy;
 264         remove(tx, dummy, false);
 265         removeConflicts(tx, conflicts);
 266         ClearPrioritisation(tx.GetHash());
 267     }
 268     // After the txs in the new block have been removed from the mempool, update policy estimates
 269     minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
 270 }
 271
 272 void CTxMemPool::clear()
 273 {
 274     LOCK(cs);
 275     mapTx.clear();
 276     mapNextTx.clear();
 277     totalTxSize = 0;
 278     ++nTransactionsUpdated;
 279 }
 280
 281 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 282 {
 283     if (!fSanityCheck)
 284         return;
 285
 286     LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 287
 288     uint64_t checkTotal = 0;
 289
 290     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 291
 292     LOCK(cs);
 293     list<const CTxMemPoolEntry*> waitingOnDependants;
 294     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 295         unsigned int i = 0;
 296         checkTotal += it->second.GetTxSize();
 297         const CTransaction& tx = it->second.GetTx();
 298         bool fDependsWait = false;
 299         BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 300             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 301             std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
 302             if (it2 != mapTx.end()) {
 303                 const CTransaction& tx2 = it2->second.GetTx();
 304                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 305                 fDependsWait = true;
 306             } else {
 307                 const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
 308                 assert(coins && coins->IsAvailable(txin.prevout.n));
 309             }
 310             // Check whether its inputs are marked in mapNextTx.
 311             std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
 312             assert(it3 != mapNextTx.end());
 313             assert(it3->second.ptx == &tx);
 314             assert(it3->second.n == i);
 315             i++;
 316         }
 317
 318         boost::unordered_map<uint256, ZCIncrementalMerkleTree, CCoinsKeyHasher> intermediates;
 319
 320         BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit) {
 321             BOOST_FOREACH(const uint256 &nf, joinsplit.nullifiers) {
 322                 assert(!pcoins->GetNullifier(nf));
 323             }
 324
 325             ZCIncrementalMerkleTree tree;
 326             auto it = intermediates.find(joinsplit.anchor);
 327             if (it != intermediates.end()) {
 328                 tree = it->second;
 329             } else {
 330                 assert(pcoins->GetAnchorAt(joinsplit.anchor, tree));
 331             }
 332
 333             BOOST_FOREACH(const uint256& commitment, joinsplit.commitments)
 334             {
 335                 tree.append(commitment);
 336             }
 337
 338             intermediates.insert(std::make_pair(tree.root(), tree));
 339         }
 340         if (fDependsWait)
 341             waitingOnDependants.push_back(&it->second);
 342         else {
 343             CValidationState state;
 344             assert(ContextualCheckInputs(tx, state, mempoolDuplicate, false, 0, false, Params().GetConsensus(), NULL));
 345             UpdateCoins(tx, state, mempoolDuplicate, 1000000);
 346         }
 347     }
 348     unsigned int stepsSinceLastRemove = 0;
 349     while (!waitingOnDependants.empty()) {
 350         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 351         waitingOnDependants.pop_front();
 352         CValidationState state;
 353         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 354             waitingOnDependants.push_back(entry);
 355             stepsSinceLastRemove++;
 356             assert(stepsSinceLastRemove < waitingOnDependants.size());
 357         } else {
 358             assert(ContextualCheckInputs(entry->GetTx(), state, mempoolDuplicate, false, 0, false, Params().GetConsensus(), NULL));
 359             UpdateCoins(entry->GetTx(), state, mempoolDuplicate, 1000000);
 360             stepsSinceLastRemove = 0;
 361         }
 362     }
 363     for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
 364         uint256 hash = it->second.ptx->GetHash();
 365         map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(hash);
 366         const CTransaction& tx = it2->second.GetTx();
 367         assert(it2 != mapTx.end());
 368         assert(&tx == it->second.ptx);
 369         assert(tx.vin.size() > it->second.n);
 370         assert(it->first == it->second.ptx->vin[it->second.n].prevout);
 371     }
 372
 373     for (std::map<uint256, const CTransaction*>::const_iterator it = mapNullifiers.begin(); it != mapNullifiers.end(); it++) {
 374         uint256 hash = it->second->GetHash();
 375         map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(hash);
 376         const CTransaction& tx = it2->second.GetTx();
 377         assert(it2 != mapTx.end());
 378         assert(&tx == it->second);
 379     }
 380
 381     assert(totalTxSize == checkTotal);
 382 }
 383
 384 void CTxMemPool::queryHashes(vector<uint256>& vtxid)
 385 {
 386     vtxid.clear();
 387
 388     LOCK(cs);
 389     vtxid.reserve(mapTx.size());
 390     for (map<uint256, CTxMemPoolEntry>::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
 391         vtxid.push_back((*mi).first);
 392 }
 393
 394 bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
 395 {
 396     LOCK(cs);
 397     map<uint256, CTxMemPoolEntry>::const_iterator i = mapTx.find(hash);
 398     if (i == mapTx.end()) return false;
 399     result = i->second.GetTx();
 400     return true;
 401 }
 402
 403 CFeeRate CTxMemPool::estimateFee(int nBlocks) const
 404 {
 405     LOCK(cs);
 406     return minerPolicyEstimator->estimateFee(nBlocks);
 407 }
 408 double CTxMemPool::estimatePriority(int nBlocks) const
 409 {
 410     LOCK(cs);
 411     return minerPolicyEstimator->estimatePriority(nBlocks);
 412 }
 413
 414 bool
 415 CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
 416 {
 417     try {
 418         LOCK(cs);
 419         fileout << 109900; // version required to read: 0.10.99 or later
 420         fileout << CLIENT_VERSION; // version that wrote the file
 421         minerPolicyEstimator->Write(fileout);
 422     }
 423     catch (const std::exception&) {
 424         LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
 425         return false;
 426     }
 427     return true;
 428 }
 429
 430 bool
 431 CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
 432 {
 433     try {
 434         int nVersionRequired, nVersionThatWrote;
 435         filein >> nVersionRequired >> nVersionThatWrote;
 436         if (nVersionRequired > CLIENT_VERSION)
 437             return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
 438
 439         LOCK(cs);
 440         minerPolicyEstimator->Read(filein);
 441     }
 442     catch (const std::exception&) {
 443         LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
 444         return false;
 445     }
 446     return true;
 447 }
 448
 449 void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
 450 {
 451     {
 452         LOCK(cs);
 453         std::pair<double, CAmount> &deltas = mapDeltas[hash];
 454         deltas.first += dPriorityDelta;
 455         deltas.second += nFeeDelta;
 456     }
 457     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 458 }
 459
 460 void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
 461 {
 462     LOCK(cs);
 463     std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
 464     if (pos == mapDeltas.end())
 465         return;
 466     const std::pair<double, CAmount> &deltas = pos->second;
 467     dPriorityDelta += deltas.first;
 468     nFeeDelta += deltas.second;
 469 }
 470
 471 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 472 {
 473     LOCK(cs);
 474     mapDeltas.erase(hash);
 475 }
 476
 477 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
 478 {
 479     for (unsigned int i = 0; i < tx.vin.size(); i++)
 480         if (exists(tx.vin[i].prevout.hash))
 481             return false;
 482     return true;
 483 }
 484
 485 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 486
 487 bool CCoinsViewMemPool::GetNullifier(const uint256 &nf) const {
 488     if (mempool.mapNullifiers.count(nf))
 489         return true;
 490
 491     return base->GetNullifier(nf);
 492 }
 493
 494 bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
 495     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 496     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 497     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 498     CTransaction tx;
 499     if (mempool.lookup(txid, tx)) {
 500         coins = CCoins(tx, MEMPOOL_HEIGHT);
 501         return true;
 502     }
 503     return (base->GetCoins(txid, coins) && !coins.IsPruned());
 504 }
 505
 506 bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 507     return mempool.exists(txid) || base->HaveCoins(txid);
 508 }