src/miner.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2015 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 "miner.h"
   7
   8 #include "amount.h"
   9 #include "chain.h"
  10 #include "chainparams.h"
  11 #include "coins.h"
  12 #include "consensus/consensus.h"
  13 #include "consensus/merkle.h"
  14 #include "consensus/validation.h"
  15 #include "hash.h"
  16 #include "main.h"
  17 #include "net.h"
  18 #include "policy/policy.h"
  19 #include "pow.h"
  20 #include "primitives/transaction.h"
  21 #include "script/standard.h"
  22 #include "timedata.h"
  23 #include "txmempool.h"
  24 #include "util.h"
  25 #include "utilmoneystr.h"
  26 #include "validationinterface.h"
  27
  28 #include <algorithm>
  29 #include <boost/thread.hpp>
  30 #include <boost/tuple/tuple.hpp>
  31 #include <queue>
  32
  33 using namespace std;
  34
  35 //////////////////////////////////////////////////////////////////////////////
  36 //
  37 // BitcoinMiner
  38 //
  39
  40 //
  41 // Unconfirmed transactions in the memory pool often depend on other
  42 // transactions in the memory pool. When we select transactions from the
  43 // pool, we select by highest priority or fee rate, so we might consider
  44 // transactions that depend on transactions that aren't yet in the block.
  45
  46 uint64_t nLastBlockTx = 0;
  47 uint64_t nLastBlockSize = 0;
  48 uint64_t nLastBlockWeight = 0;
  49
  50 class ScoreCompare
  51 {
  52 public:
  53     ScoreCompare() {}
  54
  55     bool operator()(const CTxMemPool::txiter a, const CTxMemPool::txiter b)
  56     {
  57         return CompareTxMemPoolEntryByScore()(*b,*a); // Convert to less than
  58     }
  59 };
  60
  61 int64_t UpdateTime(CBlockHeader* pblock, const Consensus::Params& consensusParams, const CBlockIndex* pindexPrev)
  62 {
  63     int64_t nOldTime = pblock->nTime;
  64     int64_t nNewTime = std::max(pindexPrev->GetMedianTimePast()+1, GetAdjustedTime());
  65
  66     if (nOldTime < nNewTime)
  67         pblock->nTime = nNewTime;
  68
  69     // Updating time can change work required on testnet:
  70     if (consensusParams.fPowAllowMinDifficultyBlocks)
  71         pblock->nBits = GetNextWorkRequired(pindexPrev, pblock, consensusParams);
  72
  73     return nNewTime - nOldTime;
  74 }
  75
  76 BlockAssembler::BlockAssembler(const CChainParams& _chainparams)
  77     : chainparams(_chainparams)
  78 {
  79     // Block resource limits
  80     // If neither -blockmaxsize or -blockmaxweight is given, limit to DEFAULT_BLOCK_MAX_*
  81     // If only one is given, only restrict the specified resource.
  82     // If both are given, restrict both.
  83     nBlockMaxWeight = DEFAULT_BLOCK_MAX_WEIGHT;
  84     nBlockMaxSize = DEFAULT_BLOCK_MAX_SIZE;
  85     bool fWeightSet = false;
  86     if (mapArgs.count("-blockmaxweight")) {
  87         nBlockMaxWeight = GetArg("-blockmaxweight", DEFAULT_BLOCK_MAX_WEIGHT);
  88         nBlockMaxSize = MAX_BLOCK_SERIALIZED_SIZE;
  89         fWeightSet = true;
  90     }
  91     if (mapArgs.count("-blockmaxsize")) {
  92         nBlockMaxSize = GetArg("-blockmaxsize", DEFAULT_BLOCK_MAX_SIZE);
  93         if (!fWeightSet) {
  94             nBlockMaxWeight = nBlockMaxSize * WITNESS_SCALE_FACTOR;
  95         }
  96     }
  97
  98     // Limit weight to between 4K and MAX_BLOCK_WEIGHT-4K for sanity:
  99     nBlockMaxWeight = std::max((unsigned int)4000, std::min((unsigned int)(MAX_BLOCK_WEIGHT-4000), nBlockMaxWeight));
 100     // Limit size to between 1K and MAX_BLOCK_SERIALIZED_SIZE-1K for sanity:
 101     nBlockMaxSize = std::max((unsigned int)1000, std::min((unsigned int)(MAX_BLOCK_SERIALIZED_SIZE-1000), nBlockMaxSize));
 102
 103     // Whether we need to account for byte usage (in addition to weight usage)
 104     fNeedSizeAccounting = (nBlockMaxSize < MAX_BLOCK_SERIALIZED_SIZE-1000);
 105 }
 106
 107 void BlockAssembler::resetBlock()
 108 {
 109     inBlock.clear();
 110
 111     // Reserve space for coinbase tx
 112     nBlockSize = 1000;
 113     nBlockWeight = 4000;
 114     nBlockSigOpsCost = 400;
 115     fIncludeWitness = false;
 116
 117     // These counters do not include coinbase tx
 118     nBlockTx = 0;
 119     nFees = 0;
 120
 121     lastFewTxs = 0;
 122     blockFinished = false;
 123 }
 124
 125 CBlockTemplate* BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn)
 126 {
 127     resetBlock();
 128
 129     pblocktemplate.reset(new CBlockTemplate());
 130
 131     if(!pblocktemplate.get())
 132         return NULL;
 133     pblock = &pblocktemplate->block; // pointer for convenience
 134
 135     // Add dummy coinbase tx as first transaction
 136     pblock->vtx.push_back(CTransaction());
 137     pblocktemplate->vTxFees.push_back(-1); // updated at end
 138     pblocktemplate->vTxSigOpsCost.push_back(-1); // updated at end
 139
 140     LOCK2(cs_main, mempool.cs);
 141     CBlockIndex* pindexPrev = chainActive.Tip();
 142     nHeight = pindexPrev->nHeight + 1;
 143
 144     pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
 145     // -regtest only: allow overriding block.nVersion with
 146     // -blockversion=N to test forking scenarios
 147     if (chainparams.MineBlocksOnDemand())
 148         pblock->nVersion = GetArg("-blockversion", pblock->nVersion);
 149
 150     pblock->nTime = GetAdjustedTime();
 151     const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast();
 152
 153     nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST)
 154                        ? nMedianTimePast
 155                        : pblock->GetBlockTime();
 156
 157     // Decide whether to include witness transactions
 158     // This is only needed in case the witness softfork activation is reverted
 159     // (which would require a very deep reorganization) or when
 160     // -promiscuousmempoolflags is used.
 161     // TODO: replace this with a call to main to assess validity of a mempool
 162     // transaction (which in most cases can be a no-op).
 163     fIncludeWitness = IsWitnessEnabled(pindexPrev, chainparams.GetConsensus());
 164
 165     addPriorityTxs();
 166     addPackageTxs();
 167
 168     nLastBlockTx = nBlockTx;
 169     nLastBlockSize = nBlockSize;
 170     nLastBlockWeight = nBlockWeight;
 171     LogPrintf("CreateNewBlock(): total size %u txs: %u fees: %ld sigops %d\n", nBlockSize, nBlockTx, nFees, nBlockSigOpsCost);
 172
 173     // Create coinbase transaction.
 174     CMutableTransaction coinbaseTx;
 175     coinbaseTx.vin.resize(1);
 176     coinbaseTx.vin[0].prevout.SetNull();
 177     coinbaseTx.vout.resize(1);
 178     coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn;
 179     coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus());
 180     coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0;
 181     pblock->vtx[0] = coinbaseTx;
 182     pblocktemplate->vchCoinbaseCommitment = GenerateCoinbaseCommitment(*pblock, pindexPrev, chainparams.GetConsensus());
 183     pblocktemplate->vTxFees[0] = -nFees;
 184
 185     // Fill in header
 186     pblock->hashPrevBlock  = pindexPrev->GetBlockHash();
 187     UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev);
 188     pblock->nBits          = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus());
 189     pblock->nNonce         = 0;
 190     pblocktemplate->vTxSigOpsCost[0] = WITNESS_SCALE_FACTOR * GetLegacySigOpCount(pblock->vtx[0]);
 191
 192     CValidationState state;
 193     if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) {
 194         throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state)));
 195     }
 196
 197     return pblocktemplate.release();
 198 }
 199
 200 bool BlockAssembler::isStillDependent(CTxMemPool::txiter iter)
 201 {
 202     BOOST_FOREACH(CTxMemPool::txiter parent, mempool.GetMemPoolParents(iter))
 203     {
 204         if (!inBlock.count(parent)) {
 205             return true;
 206         }
 207     }
 208     return false;
 209 }
 210
 211 void BlockAssembler::onlyUnconfirmed(CTxMemPool::setEntries& testSet)
 212 {
 213     for (CTxMemPool::setEntries::iterator iit = testSet.begin(); iit != testSet.end(); ) {
 214         // Only test txs not already in the block
 215         if (inBlock.count(*iit)) {
 216             testSet.erase(iit++);
 217         }
 218         else {
 219             iit++;
 220         }
 221     }
 222 }
 223
 224 bool BlockAssembler::TestPackage(uint64_t packageSize, int64_t packageSigOpsCost)
 225 {
 226     // TODO: switch to weight-based accounting for packages instead of vsize-based accounting.
 227     if (nBlockWeight + WITNESS_SCALE_FACTOR * packageSize >= nBlockMaxWeight)
 228         return false;
 229     if (nBlockSigOpsCost + packageSigOpsCost >= MAX_BLOCK_SIGOPS_COST)
 230         return false;
 231     return true;
 232 }
 233
 234 // Perform transaction-level checks before adding to block:
 235 // - transaction finality (locktime)
 236 // - premature witness (in case segwit transactions are added to mempool before
 237 //   segwit activation)
 238 // - serialized size (in case -blockmaxsize is in use)
 239 bool BlockAssembler::TestPackageTransactions(const CTxMemPool::setEntries& package)
 240 {
 241     uint64_t nPotentialBlockSize = nBlockSize; // only used with fNeedSizeAccounting
 242     BOOST_FOREACH (const CTxMemPool::txiter it, package) {
 243         if (!IsFinalTx(it->GetTx(), nHeight, nLockTimeCutoff))
 244             return false;
 245         if (!fIncludeWitness && !it->GetTx().wit.IsNull())
 246             return false;
 247         if (fNeedSizeAccounting) {
 248             uint64_t nTxSize = ::GetSerializeSize(it->GetTx(), SER_NETWORK, PROTOCOL_VERSION);
 249             if (nPotentialBlockSize + nTxSize >= nBlockMaxSize) {
 250                 return false;
 251             }
 252             nPotentialBlockSize += nTxSize;
 253         }
 254     }
 255     return true;
 256 }
 257
 258 bool BlockAssembler::TestForBlock(CTxMemPool::txiter iter)
 259 {
 260     if (nBlockWeight + iter->GetTxWeight() >= nBlockMaxWeight) {
 261         // If the block is so close to full that no more txs will fit
 262         // or if we've tried more than 50 times to fill remaining space
 263         // then flag that the block is finished
 264         if (nBlockWeight >  nBlockMaxWeight - 400 || lastFewTxs > 50) {
 265              blockFinished = true;
 266              return false;
 267         }
 268         // Once we're within 4000 weight of a full block, only look at 50 more txs
 269         // to try to fill the remaining space.
 270         if (nBlockWeight > nBlockMaxWeight - 4000) {
 271             lastFewTxs++;
 272         }
 273         return false;
 274     }
 275
 276     if (fNeedSizeAccounting) {
 277         if (nBlockSize + ::GetSerializeSize(iter->GetTx(), SER_NETWORK, PROTOCOL_VERSION) >= nBlockMaxSize) {
 278             if (nBlockSize >  nBlockMaxSize - 100 || lastFewTxs > 50) {
 279                  blockFinished = true;
 280                  return false;
 281             }
 282             if (nBlockSize > nBlockMaxSize - 1000) {
 283                 lastFewTxs++;
 284             }
 285             return false;
 286         }
 287     }
 288
 289     if (nBlockSigOpsCost + iter->GetSigOpCost() >= MAX_BLOCK_SIGOPS_COST) {
 290         // If the block has room for no more sig ops then
 291         // flag that the block is finished
 292         if (nBlockSigOpsCost > MAX_BLOCK_SIGOPS_COST - 8) {
 293             blockFinished = true;
 294             return false;
 295         }
 296         // Otherwise attempt to find another tx with fewer sigops
 297         // to put in the block.
 298         return false;
 299     }
 300
 301     // Must check that lock times are still valid
 302     // This can be removed once MTP is always enforced
 303     // as long as reorgs keep the mempool consistent.
 304     if (!IsFinalTx(iter->GetTx(), nHeight, nLockTimeCutoff))
 305         return false;
 306
 307     return true;
 308 }
 309
 310 void BlockAssembler::AddToBlock(CTxMemPool::txiter iter)
 311 {
 312     pblock->vtx.push_back(iter->GetTx());
 313     pblocktemplate->vTxFees.push_back(iter->GetFee());
 314     pblocktemplate->vTxSigOpsCost.push_back(iter->GetSigOpCost());
 315     if (fNeedSizeAccounting) {
 316         nBlockSize += ::GetSerializeSize(iter->GetTx(), SER_NETWORK, PROTOCOL_VERSION);
 317     }
 318     nBlockWeight += iter->GetTxWeight();
 319     ++nBlockTx;
 320     nBlockSigOpsCost += iter->GetSigOpCost();
 321     nFees += iter->GetFee();
 322     inBlock.insert(iter);
 323
 324     bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY);
 325     if (fPrintPriority) {
 326         double dPriority = iter->GetPriority(nHeight);
 327         CAmount dummy;
 328         mempool.ApplyDeltas(iter->GetTx().GetHash(), dPriority, dummy);
 329         LogPrintf("priority %.1f fee %s txid %s\n",
 330                   dPriority,
 331                   CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(),
 332                   iter->GetTx().GetHash().ToString());
 333     }
 334 }
 335
 336 void BlockAssembler::UpdatePackagesForAdded(const CTxMemPool::setEntries& alreadyAdded,
 337         indexed_modified_transaction_set &mapModifiedTx)
 338 {
 339     BOOST_FOREACH(const CTxMemPool::txiter it, alreadyAdded) {
 340         CTxMemPool::setEntries descendants;
 341         mempool.CalculateDescendants(it, descendants);
 342         // Insert all descendants (not yet in block) into the modified set
 343         BOOST_FOREACH(CTxMemPool::txiter desc, descendants) {
 344             if (alreadyAdded.count(desc))
 345                 continue;
 346             modtxiter mit = mapModifiedTx.find(desc);
 347             if (mit == mapModifiedTx.end()) {
 348                 CTxMemPoolModifiedEntry modEntry(desc);
 349                 modEntry.nSizeWithAncestors -= it->GetTxSize();
 350                 modEntry.nModFeesWithAncestors -= it->GetModifiedFee();
 351                 modEntry.nSigOpCostWithAncestors -= it->GetSigOpCost();
 352                 mapModifiedTx.insert(modEntry);
 353             } else {
 354                 mapModifiedTx.modify(mit, update_for_parent_inclusion(it));
 355             }
 356         }
 357     }
 358 }
 359
 360 // Skip entries in mapTx that are already in a block or are present
 361 // in mapModifiedTx (which implies that the mapTx ancestor state is
 362 // stale due to ancestor inclusion in the block)
 363 // Also skip transactions that we've already failed to add. This can happen if
 364 // we consider a transaction in mapModifiedTx and it fails: we can then
 365 // potentially consider it again while walking mapTx.  It's currently
 366 // guaranteed to fail again, but as a belt-and-suspenders check we put it in
 367 // failedTx and avoid re-evaluation, since the re-evaluation would be using
 368 // cached size/sigops/fee values that are not actually correct.
 369 bool BlockAssembler::SkipMapTxEntry(CTxMemPool::txiter it, indexed_modified_transaction_set &mapModifiedTx, CTxMemPool::setEntries &failedTx)
 370 {
 371     assert (it != mempool.mapTx.end());
 372     if (mapModifiedTx.count(it) || inBlock.count(it) || failedTx.count(it))
 373         return true;
 374     return false;
 375 }
 376
 377 void BlockAssembler::SortForBlock(const CTxMemPool::setEntries& package, CTxMemPool::txiter entry, std::vector<CTxMemPool::txiter>& sortedEntries)
 378 {
 379     // Sort package by ancestor count
 380     // If a transaction A depends on transaction B, then A's ancestor count
 381     // must be greater than B's.  So this is sufficient to validly order the
 382     // transactions for block inclusion.
 383     sortedEntries.clear();
 384     sortedEntries.insert(sortedEntries.begin(), package.begin(), package.end());
 385     std::sort(sortedEntries.begin(), sortedEntries.end(), CompareTxIterByAncestorCount());
 386 }
 387
 388 // This transaction selection algorithm orders the mempool based
 389 // on feerate of a transaction including all unconfirmed ancestors.
 390 // Since we don't remove transactions from the mempool as we select them
 391 // for block inclusion, we need an alternate method of updating the feerate
 392 // of a transaction with its not-yet-selected ancestors as we go.
 393 // This is accomplished by walking the in-mempool descendants of selected
 394 // transactions and storing a temporary modified state in mapModifiedTxs.
 395 // Each time through the loop, we compare the best transaction in
 396 // mapModifiedTxs with the next transaction in the mempool to decide what
 397 // transaction package to work on next.
 398 void BlockAssembler::addPackageTxs()
 399 {
 400     // mapModifiedTx will store sorted packages after they are modified
 401     // because some of their txs are already in the block
 402     indexed_modified_transaction_set mapModifiedTx;
 403     // Keep track of entries that failed inclusion, to avoid duplicate work
 404     CTxMemPool::setEntries failedTx;
 405
 406     // Start by adding all descendants of previously added txs to mapModifiedTx
 407     // and modifying them for their already included ancestors
 408     UpdatePackagesForAdded(inBlock, mapModifiedTx);
 409
 410     CTxMemPool::indexed_transaction_set::index<ancestor_score>::type::iterator mi = mempool.mapTx.get<ancestor_score>().begin();
 411     CTxMemPool::txiter iter;
 412     while (mi != mempool.mapTx.get<ancestor_score>().end() || !mapModifiedTx.empty())
 413     {
 414         // First try to find a new transaction in mapTx to evaluate.
 415         if (mi != mempool.mapTx.get<ancestor_score>().end() &&
 416                 SkipMapTxEntry(mempool.mapTx.project<0>(mi), mapModifiedTx, failedTx)) {
 417             ++mi;
 418             continue;
 419         }
 420
 421         // Now that mi is not stale, determine which transaction to evaluate:
 422         // the next entry from mapTx, or the best from mapModifiedTx?
 423         bool fUsingModified = false;
 424
 425         modtxscoreiter modit = mapModifiedTx.get<ancestor_score>().begin();
 426         if (mi == mempool.mapTx.get<ancestor_score>().end()) {
 427             // We're out of entries in mapTx; use the entry from mapModifiedTx
 428             iter = modit->iter;
 429             fUsingModified = true;
 430         } else {
 431             // Try to compare the mapTx entry to the mapModifiedTx entry
 432             iter = mempool.mapTx.project<0>(mi);
 433             if (modit != mapModifiedTx.get<ancestor_score>().end() &&
 434                     CompareModifiedEntry()(*modit, CTxMemPoolModifiedEntry(iter))) {
 435                 // The best entry in mapModifiedTx has higher score
 436                 // than the one from mapTx.
 437                 // Switch which transaction (package) to consider
 438                 iter = modit->iter;
 439                 fUsingModified = true;
 440             } else {
 441                 // Either no entry in mapModifiedTx, or it's worse than mapTx.
 442                 // Increment mi for the next loop iteration.
 443                 ++mi;
 444             }
 445         }
 446
 447         // We skip mapTx entries that are inBlock, and mapModifiedTx shouldn't
 448         // contain anything that is inBlock.
 449         assert(!inBlock.count(iter));
 450
 451         uint64_t packageSize = iter->GetSizeWithAncestors();
 452         CAmount packageFees = iter->GetModFeesWithAncestors();
 453         int64_t packageSigOpsCost = iter->GetSigOpCostWithAncestors();
 454         if (fUsingModified) {
 455             packageSize = modit->nSizeWithAncestors;
 456             packageFees = modit->nModFeesWithAncestors;
 457             packageSigOpsCost = modit->nSigOpCostWithAncestors;
 458         }
 459
 460         if (packageFees < ::minRelayTxFee.GetFee(packageSize)) {
 461             // Everything else we might consider has a lower fee rate
 462             return;
 463         }
 464
 465         if (!TestPackage(packageSize, packageSigOpsCost)) {
 466             if (fUsingModified) {
 467                 // Since we always look at the best entry in mapModifiedTx,
 468                 // we must erase failed entries so that we can consider the
 469                 // next best entry on the next loop iteration
 470                 mapModifiedTx.get<ancestor_score>().erase(modit);
 471                 failedTx.insert(iter);
 472             }
 473             continue;
 474         }
 475
 476         CTxMemPool::setEntries ancestors;
 477         uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 478         std::string dummy;
 479         mempool.CalculateMemPoolAncestors(*iter, ancestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 480
 481         onlyUnconfirmed(ancestors);
 482         ancestors.insert(iter);
 483
 484         // Test if all tx's are Final
 485         if (!TestPackageTransactions(ancestors)) {
 486             if (fUsingModified) {
 487                 mapModifiedTx.get<ancestor_score>().erase(modit);
 488                 failedTx.insert(iter);
 489             }
 490             continue;
 491         }
 492
 493         // Package can be added. Sort the entries in a valid order.
 494         vector<CTxMemPool::txiter> sortedEntries;
 495         SortForBlock(ancestors, iter, sortedEntries);
 496
 497         for (size_t i=0; i<sortedEntries.size(); ++i) {
 498             AddToBlock(sortedEntries[i]);
 499             // Erase from the modified set, if present
 500             mapModifiedTx.erase(sortedEntries[i]);
 501         }
 502
 503         // Update transactions that depend on each of these
 504         UpdatePackagesForAdded(ancestors, mapModifiedTx);
 505     }
 506 }
 507
 508 void BlockAssembler::addPriorityTxs()
 509 {
 510     // How much of the block should be dedicated to high-priority transactions,
 511     // included regardless of the fees they pay
 512     unsigned int nBlockPrioritySize = GetArg("-blockprioritysize", DEFAULT_BLOCK_PRIORITY_SIZE);
 513     nBlockPrioritySize = std::min(nBlockMaxSize, nBlockPrioritySize);
 514
 515     if (nBlockPrioritySize == 0) {
 516         return;
 517     }
 518
 519     bool fSizeAccounting = fNeedSizeAccounting;
 520     fNeedSizeAccounting = true;
 521
 522     // This vector will be sorted into a priority queue:
 523     vector<TxCoinAgePriority> vecPriority;
 524     TxCoinAgePriorityCompare pricomparer;
 525     std::map<CTxMemPool::txiter, double, CTxMemPool::CompareIteratorByHash> waitPriMap;
 526     typedef std::map<CTxMemPool::txiter, double, CTxMemPool::CompareIteratorByHash>::iterator waitPriIter;
 527     double actualPriority = -1;
 528
 529     vecPriority.reserve(mempool.mapTx.size());
 530     for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin();
 531          mi != mempool.mapTx.end(); ++mi)
 532     {
 533         double dPriority = mi->GetPriority(nHeight);
 534         CAmount dummy;
 535         mempool.ApplyDeltas(mi->GetTx().GetHash(), dPriority, dummy);
 536         vecPriority.push_back(TxCoinAgePriority(dPriority, mi));
 537     }
 538     std::make_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 539
 540     CTxMemPool::txiter iter;
 541     while (!vecPriority.empty() && !blockFinished) { // add a tx from priority queue to fill the blockprioritysize
 542         iter = vecPriority.front().second;
 543         actualPriority = vecPriority.front().first;
 544         std::pop_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 545         vecPriority.pop_back();
 546
 547         // If tx already in block, skip
 548         if (inBlock.count(iter)) {
 549             assert(false); // shouldn't happen for priority txs
 550             continue;
 551         }
 552
 553         // cannot accept witness transactions into a non-witness block
 554         if (!fIncludeWitness && !iter->GetTx().wit.IsNull())
 555             continue;
 556
 557         // If tx is dependent on other mempool txs which haven't yet been included
 558         // then put it in the waitSet
 559         if (isStillDependent(iter)) {
 560             waitPriMap.insert(std::make_pair(iter, actualPriority));
 561             continue;
 562         }
 563
 564         // If this tx fits in the block add it, otherwise keep looping
 565         if (TestForBlock(iter)) {
 566             AddToBlock(iter);
 567
 568             // If now that this txs is added we've surpassed our desired priority size
 569             // or have dropped below the AllowFreeThreshold, then we're done adding priority txs
 570             if (nBlockSize >= nBlockPrioritySize || !AllowFree(actualPriority)) {
 571                 break;
 572             }
 573
 574             // This tx was successfully added, so
 575             // add transactions that depend on this one to the priority queue to try again
 576             BOOST_FOREACH(CTxMemPool::txiter child, mempool.GetMemPoolChildren(iter))
 577             {
 578                 waitPriIter wpiter = waitPriMap.find(child);
 579                 if (wpiter != waitPriMap.end()) {
 580                     vecPriority.push_back(TxCoinAgePriority(wpiter->second,child));
 581                     std::push_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 582                     waitPriMap.erase(wpiter);
 583                 }
 584             }
 585         }
 586     }
 587     fNeedSizeAccounting = fSizeAccounting;
 588 }
 589
 590 void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned int& nExtraNonce)
 591 {
 592     // Update nExtraNonce
 593     static uint256 hashPrevBlock;
 594     if (hashPrevBlock != pblock->hashPrevBlock)
 595     {
 596         nExtraNonce = 0;
 597         hashPrevBlock = pblock->hashPrevBlock;
 598     }
 599     ++nExtraNonce;
 600     unsigned int nHeight = pindexPrev->nHeight+1; // Height first in coinbase required for block.version=2
 601     CMutableTransaction txCoinbase(pblock->vtx[0]);
 602     txCoinbase.vin[0].scriptSig = (CScript() << nHeight << CScriptNum(nExtraNonce)) + COINBASE_FLAGS;
 603     assert(txCoinbase.vin[0].scriptSig.size() <= 100);
 604
 605     pblock->vtx[0] = txCoinbase;
 606     pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
 607 }