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