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 <boost/thread.hpp>
  29 #include <boost/tuple/tuple.hpp>
  30 #include <queue>
  31
  32 using namespace std;
  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 priority or fee rate, so we might consider
  43 // transactions that depend on transactions that aren't yet in the block.
  44
  45 uint64_t nLastBlockTx = 0;
  46 uint64_t nLastBlockSize = 0;
  47
  48 class ScoreCompare
  49 {
  50 public:
  51     ScoreCompare() {}
  52
  53     bool operator()(const CTxMemPool::txiter a, const CTxMemPool::txiter b)
  54     {
  55         return CompareTxMemPoolEntryByScore()(*b,*a); // Convert to less than
  56     }
  57 };
  58
  59 int64_t UpdateTime(CBlockHeader* pblock, const Consensus::Params& consensusParams, const CBlockIndex* pindexPrev)
  60 {
  61     int64_t nOldTime = pblock->nTime;
  62     int64_t nNewTime = std::max(pindexPrev->GetMedianTimePast()+1, GetAdjustedTime());
  63
  64     if (nOldTime < nNewTime)
  65         pblock->nTime = nNewTime;
  66
  67     // Updating time can change work required on testnet:
  68     if (consensusParams.fPowAllowMinDifficultyBlocks)
  69         pblock->nBits = GetNextWorkRequired(pindexPrev, pblock, consensusParams);
  70
  71     return nNewTime - nOldTime;
  72 }
  73
  74 BlockAssembler::BlockAssembler(const CChainParams& _chainparams)
  75     : chainparams(_chainparams)
  76 {
  77     // Largest block you're willing to create:
  78     nBlockMaxSize = GetArg("-blockmaxsize", DEFAULT_BLOCK_MAX_SIZE);
  79     // Limit to between 1K and MAX_BLOCK_SIZE-1K for sanity:
  80     nBlockMaxSize = std::max((unsigned int)1000, std::min((unsigned int)(MAX_BLOCK_SIZE-1000), nBlockMaxSize));
  81
  82     // Minimum block size you want to create; block will be filled with free transactions
  83     // until there are no more or the block reaches this size:
  84     nBlockMinSize = GetArg("-blockminsize", DEFAULT_BLOCK_MIN_SIZE);
  85     nBlockMinSize = std::min(nBlockMaxSize, nBlockMinSize);
  86 }
  87
  88 void BlockAssembler::resetBlock()
  89 {
  90     inBlock.clear();
  91
  92     // Reserve space for coinbase tx
  93     nBlockSize = 1000;
  94     nBlockSigOps = 100;
  95
  96     // These counters do not include coinbase tx
  97     nBlockTx = 0;
  98     nFees = 0;
  99
 100     lastFewTxs = 0;
 101     blockFinished = false;
 102 }
 103
 104 CBlockTemplate* BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn)
 105 {
 106     resetBlock();
 107
 108     pblocktemplate.reset(new CBlockTemplate());
 109
 110     if(!pblocktemplate.get())
 111         return NULL;
 112     pblock = &pblocktemplate->block; // pointer for convenience
 113
 114     // Add dummy coinbase tx as first transaction
 115     pblock->vtx.push_back(CTransaction());
 116     pblocktemplate->vTxFees.push_back(-1); // updated at end
 117     pblocktemplate->vTxSigOps.push_back(-1); // updated at end
 118
 119     LOCK2(cs_main, mempool.cs);
 120     CBlockIndex* pindexPrev = chainActive.Tip();
 121     nHeight = pindexPrev->nHeight + 1;
 122
 123     pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
 124     // -regtest only: allow overriding block.nVersion with
 125     // -blockversion=N to test forking scenarios
 126     if (chainparams.MineBlocksOnDemand())
 127         pblock->nVersion = GetArg("-blockversion", pblock->nVersion);
 128
 129     pblock->nTime = GetAdjustedTime();
 130     const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast();
 131
 132     nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST)
 133                        ? nMedianTimePast
 134                        : pblock->GetBlockTime();
 135
 136     addPriorityTxs();
 137     addScoreTxs();
 138
 139     nLastBlockTx = nBlockTx;
 140     nLastBlockSize = nBlockSize;
 141     LogPrintf("CreateNewBlock(): total size %u txs: %u fees: %ld sigops %d\n", nBlockSize, nBlockTx, nFees, nBlockSigOps);
 142
 143     // Create coinbase transaction.
 144     CMutableTransaction coinbaseTx;
 145     coinbaseTx.vin.resize(1);
 146     coinbaseTx.vin[0].prevout.SetNull();
 147     coinbaseTx.vout.resize(1);
 148     coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn;
 149     coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus());
 150     coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0;
 151     pblock->vtx[0] = coinbaseTx;
 152     pblocktemplate->vTxFees[0] = -nFees;
 153
 154     // Fill in header
 155     pblock->hashPrevBlock  = pindexPrev->GetBlockHash();
 156     UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev);
 157     pblock->nBits          = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus());
 158     pblock->nNonce         = 0;
 159     pblocktemplate->vTxSigOps[0] = GetLegacySigOpCount(pblock->vtx[0]);
 160
 161     CValidationState state;
 162     if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) {
 163         throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state)));
 164     }
 165
 166     return pblocktemplate.release();
 167 }
 168
 169 bool BlockAssembler::isStillDependent(CTxMemPool::txiter iter)
 170 {
 171     BOOST_FOREACH(CTxMemPool::txiter parent, mempool.GetMemPoolParents(iter))
 172     {
 173         if (!inBlock.count(parent)) {
 174             return true;
 175         }
 176     }
 177     return false;
 178 }
 179
 180
 181
 182 bool BlockAssembler::TestForBlock(CTxMemPool::txiter iter)
 183 {
 184     if (nBlockSize + iter->GetTxSize() >= nBlockMaxSize) {
 185         // If the block is so close to full that no more txs will fit
 186         // or if we've tried more than 50 times to fill remaining space
 187         // then flag that the block is finished
 188         if (nBlockSize >  nBlockMaxSize - 100 || lastFewTxs > 50) {
 189              blockFinished = true;
 190              return false;
 191         }
 192         // Once we're within 1000 bytes of a full block, only look at 50 more txs
 193         // to try to fill the remaining space.
 194         if (nBlockSize > nBlockMaxSize - 1000) {
 195             lastFewTxs++;
 196         }
 197         return false;
 198     }
 199
 200     if (nBlockSigOps + iter->GetSigOpCount() >= MAX_BLOCK_SIGOPS) {
 201         // If the block has room for no more sig ops then
 202         // flag that the block is finished
 203         if (nBlockSigOps > MAX_BLOCK_SIGOPS - 2) {
 204             blockFinished = true;
 205             return false;
 206         }
 207         // Otherwise attempt to find another tx with fewer sigops
 208         // to put in the block.
 209         return false;
 210     }
 211
 212     // Must check that lock times are still valid
 213     // This can be removed once MTP is always enforced
 214     // as long as reorgs keep the mempool consistent.
 215     if (!IsFinalTx(iter->GetTx(), nHeight, nLockTimeCutoff))
 216         return false;
 217
 218     return true;
 219 }
 220
 221 void BlockAssembler::AddToBlock(CTxMemPool::txiter iter)
 222 {
 223     pblock->vtx.push_back(iter->GetTx());
 224     pblocktemplate->vTxFees.push_back(iter->GetFee());
 225     pblocktemplate->vTxSigOps.push_back(iter->GetSigOpCount());
 226     nBlockSize += iter->GetTxSize();
 227     ++nBlockTx;
 228     nBlockSigOps += iter->GetSigOpCount();
 229     nFees += iter->GetFee();
 230     inBlock.insert(iter);
 231
 232     bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY);
 233     if (fPrintPriority) {
 234         double dPriority = iter->GetPriority(nHeight);
 235         CAmount dummy;
 236         mempool.ApplyDeltas(iter->GetTx().GetHash(), dPriority, dummy);
 237         LogPrintf("priority %.1f fee %s txid %s\n",
 238                   dPriority,
 239                   CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(),
 240                   iter->GetTx().GetHash().ToString());
 241     }
 242 }
 243
 244 void BlockAssembler::addScoreTxs()
 245 {
 246     std::priority_queue<CTxMemPool::txiter, std::vector<CTxMemPool::txiter>, ScoreCompare> clearedTxs;
 247     CTxMemPool::setEntries waitSet;
 248     CTxMemPool::indexed_transaction_set::index<mining_score>::type::iterator mi = mempool.mapTx.get<mining_score>().begin();
 249     CTxMemPool::txiter iter;
 250     while (!blockFinished && (mi != mempool.mapTx.get<mining_score>().end() || !clearedTxs.empty()))
 251     {
 252         // If no txs that were previously postponed are available to try
 253         // again, then try the next highest score tx
 254         if (clearedTxs.empty()) {
 255             iter = mempool.mapTx.project<0>(mi);
 256             mi++;
 257         }
 258         // If a previously postponed tx is available to try again, then it
 259         // has higher score than all untried so far txs
 260         else {
 261             iter = clearedTxs.top();
 262             clearedTxs.pop();
 263         }
 264
 265         // If tx already in block, skip  (added by addPriorityTxs)
 266         if (inBlock.count(iter)) {
 267             continue;
 268         }
 269
 270         // If tx is dependent on other mempool txs which haven't yet been included
 271         // then put it in the waitSet
 272         if (isStillDependent(iter)) {
 273             waitSet.insert(iter);
 274             continue;
 275         }
 276
 277         // If the fee rate is below the min fee rate for mining, then we're done
 278         // adding txs based on score (fee rate)
 279         if (iter->GetModifiedFee() < ::minRelayTxFee.GetFee(iter->GetTxSize()) && nBlockSize >= nBlockMinSize) {
 280             return;
 281         }
 282
 283         // If this tx fits in the block add it, otherwise keep looping
 284         if (TestForBlock(iter)) {
 285             AddToBlock(iter);
 286
 287             // This tx was successfully added, so
 288             // add transactions that depend on this one to the priority queue to try again
 289             BOOST_FOREACH(CTxMemPool::txiter child, mempool.GetMemPoolChildren(iter))
 290             {
 291                 if (waitSet.count(child)) {
 292                     clearedTxs.push(child);
 293                     waitSet.erase(child);
 294                 }
 295             }
 296         }
 297     }
 298 }
 299
 300 void BlockAssembler::addPriorityTxs()
 301 {
 302     // How much of the block should be dedicated to high-priority transactions,
 303     // included regardless of the fees they pay
 304     unsigned int nBlockPrioritySize = GetArg("-blockprioritysize", DEFAULT_BLOCK_PRIORITY_SIZE);
 305     nBlockPrioritySize = std::min(nBlockMaxSize, nBlockPrioritySize);
 306
 307     if (nBlockPrioritySize == 0) {
 308         return;
 309     }
 310
 311     // This vector will be sorted into a priority queue:
 312     vector<TxCoinAgePriority> vecPriority;
 313     TxCoinAgePriorityCompare pricomparer;
 314     std::map<CTxMemPool::txiter, double, CTxMemPool::CompareIteratorByHash> waitPriMap;
 315     typedef std::map<CTxMemPool::txiter, double, CTxMemPool::CompareIteratorByHash>::iterator waitPriIter;
 316     double actualPriority = -1;
 317
 318     vecPriority.reserve(mempool.mapTx.size());
 319     for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin();
 320          mi != mempool.mapTx.end(); ++mi)
 321     {
 322         double dPriority = mi->GetPriority(nHeight);
 323         CAmount dummy;
 324         mempool.ApplyDeltas(mi->GetTx().GetHash(), dPriority, dummy);
 325         vecPriority.push_back(TxCoinAgePriority(dPriority, mi));
 326     }
 327     std::make_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 328
 329     CTxMemPool::txiter iter;
 330     while (!vecPriority.empty() && !blockFinished) { // add a tx from priority queue to fill the blockprioritysize
 331         iter = vecPriority.front().second;
 332         actualPriority = vecPriority.front().first;
 333         std::pop_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 334         vecPriority.pop_back();
 335
 336         // If tx already in block, skip
 337         if (inBlock.count(iter)) {
 338             assert(false); // shouldn't happen for priority txs
 339             continue;
 340         }
 341
 342         // If tx is dependent on other mempool txs which haven't yet been included
 343         // then put it in the waitSet
 344         if (isStillDependent(iter)) {
 345             waitPriMap.insert(std::make_pair(iter, actualPriority));
 346             continue;
 347         }
 348
 349         // If this tx fits in the block add it, otherwise keep looping
 350         if (TestForBlock(iter)) {
 351             AddToBlock(iter);
 352
 353             // If now that this txs is added we've surpassed our desired priority size
 354             // or have dropped below the AllowFreeThreshold, then we're done adding priority txs
 355             if (nBlockSize >= nBlockPrioritySize || !AllowFree(actualPriority)) {
 356                 return;
 357             }
 358
 359             // This tx was successfully added, so
 360             // add transactions that depend on this one to the priority queue to try again
 361             BOOST_FOREACH(CTxMemPool::txiter child, mempool.GetMemPoolChildren(iter))
 362             {
 363                 waitPriIter wpiter = waitPriMap.find(child);
 364                 if (wpiter != waitPriMap.end()) {
 365                     vecPriority.push_back(TxCoinAgePriority(wpiter->second,child));
 366                     std::push_heap(vecPriority.begin(), vecPriority.end(), pricomparer);
 367                     waitPriMap.erase(wpiter);
 368                 }
 369             }
 370         }
 371     }
 372 }
 373
 374 void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned int& nExtraNonce)
 375 {
 376     // Update nExtraNonce
 377     static uint256 hashPrevBlock;
 378     if (hashPrevBlock != pblock->hashPrevBlock)
 379     {
 380         nExtraNonce = 0;
 381         hashPrevBlock = pblock->hashPrevBlock;
 382     }
 383     ++nExtraNonce;
 384     unsigned int nHeight = pindexPrev->nHeight+1; // Height first in coinbase required for block.version=2
 385     CMutableTransaction txCoinbase(pblock->vtx[0]);
 386     txCoinbase.vin[0].scriptSig = (CScript() << nHeight << CScriptNum(nExtraNonce)) + COINBASE_FLAGS;
 387     assert(txCoinbase.vin[0].scriptSig.size() <= 100);
 388
 389     pblock->vtx[0] = txCoinbase;
 390     pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
 391 }