src/miner.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 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 "validation.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 #include <utility>
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //
  36 // BitcoinMiner
  37 //
  38
  39 //
  40 // Unconfirmed transactions in the memory pool often depend on other
  41 // transactions in the memory pool. When we select transactions from the
  42 // pool, we select by highest fee rate of a transaction combined with all
  43 // its ancestors.
  44
  45 uint64_t nLastBlockTx = 0;
  46 uint64_t nLastBlockSize = 0;
  47 uint64_t nLastBlockWeight = 0;
  48
  49 class ScoreCompare
  50 {
  51 public:
  52     ScoreCompare() {}
  53
  54     bool operator()(const CTxMemPool::txiter a, const CTxMemPool::txiter b)
  55     {
  56         return CompareTxMemPoolEntryByScore()(*b,*a); // Convert to less than
  57     }
  58 };
  59
  60 int64_t UpdateTime(CBlockHeader* pblock, const Consensus::Params& consensusParams, const CBlockIndex* pindexPrev)
  61 {
  62     int64_t nOldTime = pblock->nTime;
  63     int64_t nNewTime = std::max(pindexPrev->GetMedianTimePast()+1, GetAdjustedTime());
  64
  65     if (nOldTime < nNewTime)
  66         pblock->nTime = nNewTime;
  67
  68     // Updating time can change work required on testnet:
  69     if (consensusParams.fPowAllowMinDifficultyBlocks)
  70         pblock->nBits = GetNextWorkRequired(pindexPrev, pblock, consensusParams);
  71
  72     return nNewTime - nOldTime;
  73 }
  74
  75 BlockAssembler::Options::Options() {
  76     blockMinFeeRate = CFeeRate(DEFAULT_BLOCK_MIN_TX_FEE);
  77     nBlockMaxWeight = DEFAULT_BLOCK_MAX_WEIGHT;
  78     nBlockMaxSize = DEFAULT_BLOCK_MAX_SIZE;
  79 }
  80
  81 BlockAssembler::BlockAssembler(const CChainParams& params, const Options& options) : chainparams(params)
  82 {
  83     blockMinFeeRate = options.blockMinFeeRate;
  84     // Limit weight to between 4K and MAX_BLOCK_WEIGHT-4K for sanity:
  85     nBlockMaxWeight = std::max<size_t>(4000, std::min<size_t>(MAX_BLOCK_WEIGHT - 4000, options.nBlockMaxWeight));
  86     // Limit size to between 1K and MAX_BLOCK_SERIALIZED_SIZE-1K for sanity:
  87     nBlockMaxSize = std::max<size_t>(1000, std::min<size_t>(MAX_BLOCK_SERIALIZED_SIZE - 1000, options.nBlockMaxSize));
  88     // Whether we need to account for byte usage (in addition to weight usage)
  89     fNeedSizeAccounting = (nBlockMaxSize < MAX_BLOCK_SERIALIZED_SIZE - 1000);
  90 }
  91
  92 static BlockAssembler::Options DefaultOptions(const CChainParams& params)
  93 {
  94     // Block resource limits
  95     // If neither -blockmaxsize or -blockmaxweight is given, limit to DEFAULT_BLOCK_MAX_*
  96     // If only one is given, only restrict the specified resource.
  97     // If both are given, restrict both.
  98     BlockAssembler::Options options;
  99     options.nBlockMaxWeight = DEFAULT_BLOCK_MAX_WEIGHT;
 100     options.nBlockMaxSize = DEFAULT_BLOCK_MAX_SIZE;
 101     bool fWeightSet = false;
 102     if (IsArgSet("-blockmaxweight")) {
 103         options.nBlockMaxWeight = GetArg("-blockmaxweight", DEFAULT_BLOCK_MAX_WEIGHT);
 104         options.nBlockMaxSize = MAX_BLOCK_SERIALIZED_SIZE;
 105         fWeightSet = true;
 106     }
 107     if (IsArgSet("-blockmaxsize")) {
 108         options.nBlockMaxSize = GetArg("-blockmaxsize", DEFAULT_BLOCK_MAX_SIZE);
 109         if (!fWeightSet) {
 110             options.nBlockMaxWeight = options.nBlockMaxSize * WITNESS_SCALE_FACTOR;
 111         }
 112     }
 113     if (IsArgSet("-blockmintxfee")) {
 114         CAmount n = 0;
 115         ParseMoney(GetArg("-blockmintxfee", ""), n);
 116         options.blockMinFeeRate = CFeeRate(n);
 117     } else {
 118         options.blockMinFeeRate = CFeeRate(DEFAULT_BLOCK_MIN_TX_FEE);
 119     }
 120     return options;
 121 }
 122
 123 BlockAssembler::BlockAssembler(const CChainParams& params) : BlockAssembler(params, DefaultOptions(params)) {}
 124
 125 void BlockAssembler::resetBlock()
 126 {
 127     inBlock.clear();
 128
 129     // Reserve space for coinbase tx
 130     nBlockSize = 1000;
 131     nBlockWeight = 4000;
 132     nBlockSigOpsCost = 400;
 133     fIncludeWitness = false;
 134
 135     // These counters do not include coinbase tx
 136     nBlockTx = 0;
 137     nFees = 0;
 138 }
 139
 140 std::unique_ptr<CBlockTemplate> BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn, bool fMineWitnessTx)
 141 {
 142     resetBlock();
 143
 144     pblocktemplate.reset(new CBlockTemplate());
 145
 146     if(!pblocktemplate.get())
 147         return nullptr;
 148     pblock = &pblocktemplate->block; // pointer for convenience
 149
 150     // Add dummy coinbase tx as first transaction
 151     pblock->vtx.emplace_back();
 152     pblocktemplate->vTxFees.push_back(-1); // updated at end
 153     pblocktemplate->vTxSigOpsCost.push_back(-1); // updated at end
 154
 155     LOCK2(cs_main, mempool.cs);
 156     CBlockIndex* pindexPrev = chainActive.Tip();
 157     nHeight = pindexPrev->nHeight + 1;
 158
 159     pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
 160     // -regtest only: allow overriding block.nVersion with
 161     // -blockversion=N to test forking scenarios
 162     if (chainparams.MineBlocksOnDemand())
 163         pblock->nVersion = GetArg("-blockversion", pblock->nVersion);
 164
 165     pblock->nTime = GetAdjustedTime();
 166     const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast();
 167
 168     nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST)
 169                        ? nMedianTimePast
 170                        : pblock->GetBlockTime();
 171
 172     // Decide whether to include witness transactions
 173     // This is only needed in case the witness softfork activation is reverted
 174     // (which would require a very deep reorganization) or when
 175     // -promiscuousmempoolflags is used.
 176     // TODO: replace this with a call to main to assess validity of a mempool
 177     // transaction (which in most cases can be a no-op).
 178     fIncludeWitness = IsWitnessEnabled(pindexPrev, chainparams.GetConsensus()) && fMineWitnessTx;
 179
 180     addPackageTxs();
 181
 182     nLastBlockTx = nBlockTx;
 183     nLastBlockSize = nBlockSize;
 184     nLastBlockWeight = nBlockWeight;
 185
 186     // Create coinbase transaction.
 187     CMutableTransaction coinbaseTx;
 188     coinbaseTx.vin.resize(1);
 189     coinbaseTx.vin[0].prevout.SetNull();
 190     coinbaseTx.vout.resize(1);
 191     coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn;
 192     coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus());
 193     coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0;
 194     pblock->vtx[0] = MakeTransactionRef(std::move(coinbaseTx));
 195     pblocktemplate->vchCoinbaseCommitment = GenerateCoinbaseCommitment(*pblock, pindexPrev, chainparams.GetConsensus());
 196     pblocktemplate->vTxFees[0] = -nFees;
 197
 198     uint64_t nSerializeSize = GetSerializeSize(*pblock, SER_NETWORK, PROTOCOL_VERSION);
 199     LogPrintf("CreateNewBlock(): total size: %u block weight: %u txs: %u fees: %ld sigops %d\n", nSerializeSize, GetBlockWeight(*pblock), nBlockTx, nFees, nBlockSigOpsCost);
 200
 201     // Fill in header
 202     pblock->hashPrevBlock  = pindexPrev->GetBlockHash();
 203     UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev);
 204     pblock->nBits          = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus());
 205     pblock->nNonce         = 0;
 206     pblocktemplate->vTxSigOpsCost[0] = WITNESS_SCALE_FACTOR * GetLegacySigOpCount(*pblock->vtx[0]);
 207
 208     CValidationState state;
 209     if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) {
 210         throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state)));
 211     }
 212
 213     return std::move(pblocktemplate);
 214 }
 215
 216 void BlockAssembler::onlyUnconfirmed(CTxMemPool::setEntries& testSet)
 217 {
 218     for (CTxMemPool::setEntries::iterator iit = testSet.begin(); iit != testSet.end(); ) {
 219         // Only test txs not already in the block
 220         if (inBlock.count(*iit)) {
 221             testSet.erase(iit++);
 222         }
 223         else {
 224             iit++;
 225         }
 226     }
 227 }
 228
 229 bool BlockAssembler::TestPackage(uint64_t packageSize, int64_t packageSigOpsCost)
 230 {
 231     // TODO: switch to weight-based accounting for packages instead of vsize-based accounting.
 232     if (nBlockWeight + WITNESS_SCALE_FACTOR * packageSize >= nBlockMaxWeight)
 233         return false;
 234     if (nBlockSigOpsCost + packageSigOpsCost >= MAX_BLOCK_SIGOPS_COST)
 235         return false;
 236     return true;
 237 }
 238
 239 // Perform transaction-level checks before adding to block:
 240 // - transaction finality (locktime)
 241 // - premature witness (in case segwit transactions are added to mempool before
 242 //   segwit activation)
 243 // - serialized size (in case -blockmaxsize is in use)
 244 bool BlockAssembler::TestPackageTransactions(const CTxMemPool::setEntries& package)
 245 {
 246     uint64_t nPotentialBlockSize = nBlockSize; // only used with fNeedSizeAccounting
 247     BOOST_FOREACH (const CTxMemPool::txiter it, package) {
 248         if (!IsFinalTx(it->GetTx(), nHeight, nLockTimeCutoff))
 249             return false;
 250         if (!fIncludeWitness && it->GetTx().HasWitness())
 251             return false;
 252         if (fNeedSizeAccounting) {
 253             uint64_t nTxSize = ::GetSerializeSize(it->GetTx(), SER_NETWORK, PROTOCOL_VERSION);
 254             if (nPotentialBlockSize + nTxSize >= nBlockMaxSize) {
 255                 return false;
 256             }
 257             nPotentialBlockSize += nTxSize;
 258         }
 259     }
 260     return true;
 261 }
 262
 263 void BlockAssembler::AddToBlock(CTxMemPool::txiter iter)
 264 {
 265     pblock->vtx.emplace_back(iter->GetSharedTx());
 266     pblocktemplate->vTxFees.push_back(iter->GetFee());
 267     pblocktemplate->vTxSigOpsCost.push_back(iter->GetSigOpCost());
 268     if (fNeedSizeAccounting) {
 269         nBlockSize += ::GetSerializeSize(iter->GetTx(), SER_NETWORK, PROTOCOL_VERSION);
 270     }
 271     nBlockWeight += iter->GetTxWeight();
 272     ++nBlockTx;
 273     nBlockSigOpsCost += iter->GetSigOpCost();
 274     nFees += iter->GetFee();
 275     inBlock.insert(iter);
 276
 277     bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY);
 278     if (fPrintPriority) {
 279         LogPrintf("fee %s txid %s\n",
 280                   CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(),
 281                   iter->GetTx().GetHash().ToString());
 282     }
 283 }
 284
 285 void BlockAssembler::UpdatePackagesForAdded(const CTxMemPool::setEntries& alreadyAdded,
 286         indexed_modified_transaction_set &mapModifiedTx)
 287 {
 288     BOOST_FOREACH(const CTxMemPool::txiter it, alreadyAdded) {
 289         CTxMemPool::setEntries descendants;
 290         mempool.CalculateDescendants(it, descendants);
 291         // Insert all descendants (not yet in block) into the modified set
 292         BOOST_FOREACH(CTxMemPool::txiter desc, descendants) {
 293             if (alreadyAdded.count(desc))
 294                 continue;
 295             modtxiter mit = mapModifiedTx.find(desc);
 296             if (mit == mapModifiedTx.end()) {
 297                 CTxMemPoolModifiedEntry modEntry(desc);
 298                 modEntry.nSizeWithAncestors -= it->GetTxSize();
 299                 modEntry.nModFeesWithAncestors -= it->GetModifiedFee();
 300                 modEntry.nSigOpCostWithAncestors -= it->GetSigOpCost();
 301                 mapModifiedTx.insert(modEntry);
 302             } else {
 303                 mapModifiedTx.modify(mit, update_for_parent_inclusion(it));
 304             }
 305         }
 306     }
 307 }
 308
 309 // Skip entries in mapTx that are already in a block or are present
 310 // in mapModifiedTx (which implies that the mapTx ancestor state is
 311 // stale due to ancestor inclusion in the block)
 312 // Also skip transactions that we've already failed to add. This can happen if
 313 // we consider a transaction in mapModifiedTx and it fails: we can then
 314 // potentially consider it again while walking mapTx.  It's currently
 315 // guaranteed to fail again, but as a belt-and-suspenders check we put it in
 316 // failedTx and avoid re-evaluation, since the re-evaluation would be using
 317 // cached size/sigops/fee values that are not actually correct.
 318 bool BlockAssembler::SkipMapTxEntry(CTxMemPool::txiter it, indexed_modified_transaction_set &mapModifiedTx, CTxMemPool::setEntries &failedTx)
 319 {
 320     assert (it != mempool.mapTx.end());
 321     if (mapModifiedTx.count(it) || inBlock.count(it) || failedTx.count(it))
 322         return true;
 323     return false;
 324 }
 325
 326 void BlockAssembler::SortForBlock(const CTxMemPool::setEntries& package, CTxMemPool::txiter entry, std::vector<CTxMemPool::txiter>& sortedEntries)
 327 {
 328     // Sort package by ancestor count
 329     // If a transaction A depends on transaction B, then A's ancestor count
 330     // must be greater than B's.  So this is sufficient to validly order the
 331     // transactions for block inclusion.
 332     sortedEntries.clear();
 333     sortedEntries.insert(sortedEntries.begin(), package.begin(), package.end());
 334     std::sort(sortedEntries.begin(), sortedEntries.end(), CompareTxIterByAncestorCount());
 335 }
 336
 337 // This transaction selection algorithm orders the mempool based
 338 // on feerate of a transaction including all unconfirmed ancestors.
 339 // Since we don't remove transactions from the mempool as we select them
 340 // for block inclusion, we need an alternate method of updating the feerate
 341 // of a transaction with its not-yet-selected ancestors as we go.
 342 // This is accomplished by walking the in-mempool descendants of selected
 343 // transactions and storing a temporary modified state in mapModifiedTxs.
 344 // Each time through the loop, we compare the best transaction in
 345 // mapModifiedTxs with the next transaction in the mempool to decide what
 346 // transaction package to work on next.
 347 void BlockAssembler::addPackageTxs()
 348 {
 349     // mapModifiedTx will store sorted packages after they are modified
 350     // because some of their txs are already in the block
 351     indexed_modified_transaction_set mapModifiedTx;
 352     // Keep track of entries that failed inclusion, to avoid duplicate work
 353     CTxMemPool::setEntries failedTx;
 354
 355     // Start by adding all descendants of previously added txs to mapModifiedTx
 356     // and modifying them for their already included ancestors
 357     UpdatePackagesForAdded(inBlock, mapModifiedTx);
 358
 359     CTxMemPool::indexed_transaction_set::index<ancestor_score>::type::iterator mi = mempool.mapTx.get<ancestor_score>().begin();
 360     CTxMemPool::txiter iter;
 361     while (mi != mempool.mapTx.get<ancestor_score>().end() || !mapModifiedTx.empty())
 362     {
 363         // First try to find a new transaction in mapTx to evaluate.
 364         if (mi != mempool.mapTx.get<ancestor_score>().end() &&
 365                 SkipMapTxEntry(mempool.mapTx.project<0>(mi), mapModifiedTx, failedTx)) {
 366             ++mi;
 367             continue;
 368         }
 369
 370         // Now that mi is not stale, determine which transaction to evaluate:
 371         // the next entry from mapTx, or the best from mapModifiedTx?
 372         bool fUsingModified = false;
 373
 374         modtxscoreiter modit = mapModifiedTx.get<ancestor_score>().begin();
 375         if (mi == mempool.mapTx.get<ancestor_score>().end()) {
 376             // We're out of entries in mapTx; use the entry from mapModifiedTx
 377             iter = modit->iter;
 378             fUsingModified = true;
 379         } else {
 380             // Try to compare the mapTx entry to the mapModifiedTx entry
 381             iter = mempool.mapTx.project<0>(mi);
 382             if (modit != mapModifiedTx.get<ancestor_score>().end() &&
 383                     CompareModifiedEntry()(*modit, CTxMemPoolModifiedEntry(iter))) {
 384                 // The best entry in mapModifiedTx has higher score
 385                 // than the one from mapTx.
 386                 // Switch which transaction (package) to consider
 387                 iter = modit->iter;
 388                 fUsingModified = true;
 389             } else {
 390                 // Either no entry in mapModifiedTx, or it's worse than mapTx.
 391                 // Increment mi for the next loop iteration.
 392                 ++mi;
 393             }
 394         }
 395
 396         // We skip mapTx entries that are inBlock, and mapModifiedTx shouldn't
 397         // contain anything that is inBlock.
 398         assert(!inBlock.count(iter));
 399
 400         uint64_t packageSize = iter->GetSizeWithAncestors();
 401         CAmount packageFees = iter->GetModFeesWithAncestors();
 402         int64_t packageSigOpsCost = iter->GetSigOpCostWithAncestors();
 403         if (fUsingModified) {
 404             packageSize = modit->nSizeWithAncestors;
 405             packageFees = modit->nModFeesWithAncestors;
 406             packageSigOpsCost = modit->nSigOpCostWithAncestors;
 407         }
 408
 409         if (packageFees < blockMinFeeRate.GetFee(packageSize)) {
 410             // Everything else we might consider has a lower fee rate
 411             return;
 412         }
 413
 414         if (!TestPackage(packageSize, packageSigOpsCost)) {
 415             if (fUsingModified) {
 416                 // Since we always look at the best entry in mapModifiedTx,
 417                 // we must erase failed entries so that we can consider the
 418                 // next best entry on the next loop iteration
 419                 mapModifiedTx.get<ancestor_score>().erase(modit);
 420                 failedTx.insert(iter);
 421             }
 422             continue;
 423         }
 424
 425         CTxMemPool::setEntries ancestors;
 426         uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 427         std::string dummy;
 428         mempool.CalculateMemPoolAncestors(*iter, ancestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 429
 430         onlyUnconfirmed(ancestors);
 431         ancestors.insert(iter);
 432
 433         // Test if all tx's are Final
 434         if (!TestPackageTransactions(ancestors)) {
 435             if (fUsingModified) {
 436                 mapModifiedTx.get<ancestor_score>().erase(modit);
 437                 failedTx.insert(iter);
 438             }
 439             continue;
 440         }
 441
 442         // Package can be added. Sort the entries in a valid order.
 443         std::vector<CTxMemPool::txiter> sortedEntries;
 444         SortForBlock(ancestors, iter, sortedEntries);
 445
 446         for (size_t i=0; i<sortedEntries.size(); ++i) {
 447             AddToBlock(sortedEntries[i]);
 448             // Erase from the modified set, if present
 449             mapModifiedTx.erase(sortedEntries[i]);
 450         }
 451
 452         // Update transactions that depend on each of these
 453         UpdatePackagesForAdded(ancestors, mapModifiedTx);
 454     }
 455 }
 456
 457 void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned int& nExtraNonce)
 458 {
 459     // Update nExtraNonce
 460     static uint256 hashPrevBlock;
 461     if (hashPrevBlock != pblock->hashPrevBlock)
 462     {
 463         nExtraNonce = 0;
 464         hashPrevBlock = pblock->hashPrevBlock;
 465     }
 466     ++nExtraNonce;
 467     unsigned int nHeight = pindexPrev->nHeight+1; // Height first in coinbase required for block.version=2
 468     CMutableTransaction txCoinbase(*pblock->vtx[0]);
 469     txCoinbase.vin[0].scriptSig = (CScript() << nHeight << CScriptNum(nExtraNonce)) + COINBASE_FLAGS;
 470     assert(txCoinbase.vin[0].scriptSig.size() <= 100);
 471
 472     pblock->vtx[0] = MakeTransactionRef(std::move(txCoinbase));
 473     pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
 474 }