1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-2022 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 <node/miner.h>
  7  
  8  #include <chain.h>
  9  #include <chainparams.h>
 10  #include <coins.h>
 11  #include <common/args.h>
 12  #include <consensus/amount.h>
 13  #include <consensus/consensus.h>
 14  #include <consensus/merkle.h>
 15  #include <consensus/tx_verify.h>
 16  #include <consensus/validation.h>
 17  #include <deploymentstatus.h>
 18  #include <logging.h>
 19  #include <policy/feerate.h>
 20  #include <policy/policy.h>
 21  #include <pow.h>
 22  #include <primitives/transaction.h>
 23  #include <util/moneystr.h>
 24  #include <util/time.h>
 25  #include <validation.h>
 26  
 27  #include <algorithm>
 28  #include <utility>
 29  
 30  namespace node {
 31  int64_t UpdateTime(CBlockHeader* pblock, const Consensus::Params& consensusParams, const CBlockIndex* pindexPrev)
 32  {
 33      int64_t nOldTime = pblock->nTime;
 34      int64_t nNewTime{std::max<int64_t>(pindexPrev->GetMedianTimePast() + 1, TicksSinceEpoch<std::chrono::seconds>(NodeClock::now()))};
 35  
 36      if (nOldTime < nNewTime) {
 37          pblock->nTime = nNewTime;
 38      }
 39  
 40      // Updating time can change work required on testnet:
 41      if (consensusParams.fPowAllowMinDifficultyBlocks) {
 42          pblock->nBits = GetNextWorkRequired(pindexPrev, pblock, consensusParams);
 43      }
 44  
 45      return nNewTime - nOldTime;
 46  }
 47  
 48  void RegenerateCommitments(CBlock& block, ChainstateManager& chainman)
 49  {
 50      CMutableTransaction tx{*block.vtx.at(0)};
 51      tx.vout.erase(tx.vout.begin() + GetWitnessCommitmentIndex(block));
 52      block.vtx.at(0) = MakeTransactionRef(tx);
 53  
 54      const CBlockIndex* prev_block = WITH_LOCK(::cs_main, return chainman.m_blockman.LookupBlockIndex(block.hashPrevBlock));
 55      chainman.GenerateCoinbaseCommitment(block, prev_block);
 56  
 57      block.hashMerkleRoot = BlockMerkleRoot(block);
 58  }
 59  
 60  static BlockAssembler::Options ClampOptions(BlockAssembler::Options options)
 61  {
 62      // Limit weight to between 4K and DEFAULT_BLOCK_MAX_WEIGHT for sanity:
 63      options.nBlockMaxWeight = std::clamp<size_t>(options.nBlockMaxWeight, 4000, DEFAULT_BLOCK_MAX_WEIGHT);
 64      return options;
 65  }
 66  
 67  BlockAssembler::BlockAssembler(Chainstate& chainstate, const CTxMemPool* mempool, const Options& options)
 68      : chainparams{chainstate.m_chainman.GetParams()},
 69        m_mempool{mempool},
 70        m_chainstate{chainstate},
 71        m_options{ClampOptions(options)}
 72  {
 73  }
 74  
 75  void ApplyArgsManOptions(const ArgsManager& args, BlockAssembler::Options& options)
 76  {
 77      // Block resource limits
 78      options.nBlockMaxWeight = args.GetIntArg("-blockmaxweight", options.nBlockMaxWeight);
 79      if (const auto blockmintxfee{args.GetArg("-blockmintxfee")}) {
 80          if (const auto parsed{ParseMoney(*blockmintxfee)}) options.blockMinFeeRate = CFeeRate{*parsed};
 81      }
 82  }
 83  static BlockAssembler::Options ConfiguredOptions()
 84  {
 85      BlockAssembler::Options options;
 86      ApplyArgsManOptions(gArgs, options);
 87      return options;
 88  }
 89  
 90  BlockAssembler::BlockAssembler(Chainstate& chainstate, const CTxMemPool* mempool)
 91      : BlockAssembler(chainstate, mempool, ConfiguredOptions()) {}
 92  
 93  void BlockAssembler::resetBlock()
 94  {
 95      inBlock.clear();
 96  
 97      // Reserve space for coinbase tx
 98      nBlockWeight = 4000;
 99      nBlockSigOpsCost = 400;
100  
101      // These counters do not include coinbase tx
102      nBlockTx = 0;
103      nFees = 0;
104  }
105  
106  std::unique_ptr<CBlockTemplate> BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn)
107  {
108      const auto time_start{SteadyClock::now()};
109  
110      resetBlock();
111  
112      pblocktemplate.reset(new CBlockTemplate());
113  
114      if (!pblocktemplate.get()) {
115          return nullptr;
116      }
117      CBlock* const pblock = &pblocktemplate->block; // pointer for convenience
118  
119      // Add dummy coinbase tx as first transaction
120      pblock->vtx.emplace_back();
121      pblocktemplate->vTxFees.push_back(-1); // updated at end
122      pblocktemplate->vTxSigOpsCost.push_back(-1); // updated at end
123  
124      LOCK(::cs_main);
125      CBlockIndex* pindexPrev = m_chainstate.m_chain.Tip();
126      assert(pindexPrev != nullptr);
127      nHeight = pindexPrev->nHeight + 1;
128  
129      pblock->nVersion = m_chainstate.m_chainman.m_versionbitscache.ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
130      // -regtest only: allow overriding block.nVersion with
131      // -blockversion=N to test forking scenarios
132      if (chainparams.MineBlocksOnDemand()) {
133          pblock->nVersion = gArgs.GetIntArg("-blockversion", pblock->nVersion);
134      }
135  
136      pblock->nTime = TicksSinceEpoch<std::chrono::seconds>(NodeClock::now());
137      m_lock_time_cutoff = pindexPrev->GetMedianTimePast();
138  
139      int nPackagesSelected = 0;
140      int nDescendantsUpdated = 0;
141      if (m_mempool) {
142          LOCK(m_mempool->cs);
143          addPackageTxs(*m_mempool, nPackagesSelected, nDescendantsUpdated);
144      }
145  
146      const auto time_1{SteadyClock::now()};
147  
148      m_last_block_num_txs = nBlockTx;
149      m_last_block_weight = nBlockWeight;
150  
151      // Create coinbase transaction.
152      CMutableTransaction coinbaseTx;
153      coinbaseTx.vin.resize(1);
154      coinbaseTx.vin[0].prevout.SetNull();
155      coinbaseTx.vout.resize(1);
156      coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn;
157      coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus());
158      coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0;
159      pblock->vtx[0] = MakeTransactionRef(std::move(coinbaseTx));
160      pblocktemplate->vchCoinbaseCommitment = m_chainstate.m_chainman.GenerateCoinbaseCommitment(*pblock, pindexPrev);
161      pblocktemplate->vTxFees[0] = -nFees;
162  
163      LogPrintf("CreateNewBlock(): block weight: %u txs: %u fees: %ld sigops %d\n", GetBlockWeight(*pblock), nBlockTx, nFees, nBlockSigOpsCost);
164  
165      // Fill in header
166      pblock->hashPrevBlock  = pindexPrev->GetBlockHash();
167      UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev);
168      pblock->nBits          = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus());
169      pblock->nNonce         = 0;
170      pblocktemplate->vTxSigOpsCost[0] = WITNESS_SCALE_FACTOR * GetLegacySigOpCount(*pblock->vtx[0]);
171  
172      BlockValidationState state;
173      if (m_options.test_block_validity && !TestBlockValidity(state, chainparams, m_chainstate, *pblock, pindexPrev,
174                                                              /*fCheckPOW=*/false, /*fCheckMerkleRoot=*/false)) {
175          throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, state.ToString()));
176      }
177      const auto time_2{SteadyClock::now()};
178  
179      LogPrint(BCLog::BENCH, "CreateNewBlock() packages: %.2fms (%d packages, %d updated descendants), validity: %.2fms (total %.2fms)\n",
180               Ticks<MillisecondsDouble>(time_1 - time_start), nPackagesSelected, nDescendantsUpdated,
181               Ticks<MillisecondsDouble>(time_2 - time_1),
182               Ticks<MillisecondsDouble>(time_2 - time_start));
183  
184      return std::move(pblocktemplate);
185  }
186  
187  void BlockAssembler::onlyUnconfirmed(CTxMemPool::setEntries& testSet)
188  {
189      for (CTxMemPool::setEntries::iterator iit = testSet.begin(); iit != testSet.end(); ) {
190          // Only test txs not already in the block
191          if (inBlock.count((*iit)->GetSharedTx()->GetHash())) {
192              testSet.erase(iit++);
193          } else {
194              iit++;
195          }
196      }
197  }
198  
199  bool BlockAssembler::TestPackage(uint64_t packageSize, int64_t packageSigOpsCost) const
200  {
201      // TODO: switch to weight-based accounting for packages instead of vsize-based accounting.
202      if (nBlockWeight + WITNESS_SCALE_FACTOR * packageSize >= m_options.nBlockMaxWeight) {
203          return false;
204      }
205      if (nBlockSigOpsCost + packageSigOpsCost >= MAX_BLOCK_SIGOPS_COST) {
206          return false;
207      }
208      return true;
209  }
210  
211  // Perform transaction-level checks before adding to block:
212  // - transaction finality (locktime)
213  bool BlockAssembler::TestPackageTransactions(const CTxMemPool::setEntries& package) const
214  {
215      for (CTxMemPool::txiter it : package) {
216          if (!IsFinalTx(it->GetTx(), nHeight, m_lock_time_cutoff)) {
217              return false;
218          }
219      }
220      return true;
221  }
222  
223  void BlockAssembler::AddToBlock(CTxMemPool::txiter iter)
224  {
225      pblocktemplate->block.vtx.emplace_back(iter->GetSharedTx());
226      pblocktemplate->vTxFees.push_back(iter->GetFee());
227      pblocktemplate->vTxSigOpsCost.push_back(iter->GetSigOpCost());
228      nBlockWeight += iter->GetTxWeight();
229      ++nBlockTx;
230      nBlockSigOpsCost += iter->GetSigOpCost();
231      nFees += iter->GetFee();
232      inBlock.insert(iter->GetSharedTx()->GetHash());
233  
234      bool fPrintPriority = gArgs.GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY);
235      if (fPrintPriority) {
236          LogPrintf("fee rate %s txid %s\n",
237                    CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(),
238                    iter->GetTx().GetHash().ToString());
239      }
240  }
241  
242  /** Add descendants of given transactions to mapModifiedTx with ancestor
243   * state updated assuming given transactions are inBlock. Returns number
244   * of updated descendants. */
245  static int UpdatePackagesForAdded(const CTxMemPool& mempool,
246                                    const CTxMemPool::setEntries& alreadyAdded,
247                                    indexed_modified_transaction_set& mapModifiedTx) EXCLUSIVE_LOCKS_REQUIRED(mempool.cs)
248  {
249      AssertLockHeld(mempool.cs);
250  
251      int nDescendantsUpdated = 0;
252      for (CTxMemPool::txiter it : alreadyAdded) {
253          CTxMemPool::setEntries descendants;
254          mempool.CalculateDescendants(it, descendants);
255          // Insert all descendants (not yet in block) into the modified set
256          for (CTxMemPool::txiter desc : descendants) {
257              if (alreadyAdded.count(desc)) {
258                  continue;
259              }
260              ++nDescendantsUpdated;
261              modtxiter mit = mapModifiedTx.find(desc);
262              if (mit == mapModifiedTx.end()) {
263                  CTxMemPoolModifiedEntry modEntry(desc);
264                  mit = mapModifiedTx.insert(modEntry).first;
265              }
266              mapModifiedTx.modify(mit, update_for_parent_inclusion(it));
267          }
268      }
269      return nDescendantsUpdated;
270  }
271  
272  void BlockAssembler::SortForBlock(const CTxMemPool::setEntries& package, std::vector<CTxMemPool::txiter>& sortedEntries)
273  {
274      // Sort package by ancestor count
275      // If a transaction A depends on transaction B, then A's ancestor count
276      // must be greater than B's.  So this is sufficient to validly order the
277      // transactions for block inclusion.
278      sortedEntries.clear();
279      sortedEntries.insert(sortedEntries.begin(), package.begin(), package.end());
280      std::sort(sortedEntries.begin(), sortedEntries.end(), CompareTxIterByAncestorCount());
281  }
282  
283  // This transaction selection algorithm orders the mempool based
284  // on feerate of a transaction including all unconfirmed ancestors.
285  // Since we don't remove transactions from the mempool as we select them
286  // for block inclusion, we need an alternate method of updating the feerate
287  // of a transaction with its not-yet-selected ancestors as we go.
288  // This is accomplished by walking the in-mempool descendants of selected
289  // transactions and storing a temporary modified state in mapModifiedTxs.
290  // Each time through the loop, we compare the best transaction in
291  // mapModifiedTxs with the next transaction in the mempool to decide what
292  // transaction package to work on next.
293  void BlockAssembler::addPackageTxs(const CTxMemPool& mempool, int& nPackagesSelected, int& nDescendantsUpdated)
294  {
295      AssertLockHeld(mempool.cs);
296  
297      // mapModifiedTx will store sorted packages after they are modified
298      // because some of their txs are already in the block
299      indexed_modified_transaction_set mapModifiedTx;
300      // Keep track of entries that failed inclusion, to avoid duplicate work
301      std::set<Txid> failedTx;
302  
303      CTxMemPool::indexed_transaction_set::index<ancestor_score>::type::iterator mi = mempool.mapTx.get<ancestor_score>().begin();
304      CTxMemPool::txiter iter;
305  
306      // Limit the number of attempts to add transactions to the block when it is
307      // close to full; this is just a simple heuristic to finish quickly if the
308      // mempool has a lot of entries.
309      const int64_t MAX_CONSECUTIVE_FAILURES = 1000;
310      int64_t nConsecutiveFailed = 0;
311  
312      while (mi != mempool.mapTx.get<ancestor_score>().end() || !mapModifiedTx.empty()) {
313          // First try to find a new transaction in mapTx to evaluate.
314          //
315          // Skip entries in mapTx that are already in a block or are present
316          // in mapModifiedTx (which implies that the mapTx ancestor state is
317          // stale due to ancestor inclusion in the block)
318          // Also skip transactions that we've already failed to add. This can happen if
319          // we consider a transaction in mapModifiedTx and it fails: we can then
320          // potentially consider it again while walking mapTx.  It's currently
321          // guaranteed to fail again, but as a belt-and-suspenders check we put it in
322          // failedTx and avoid re-evaluation, since the re-evaluation would be using
323          // cached size/sigops/fee values that are not actually correct.
324          /** Return true if given transaction from mapTx has already been evaluated,
325           * or if the transaction's cached data in mapTx is incorrect. */
326          if (mi != mempool.mapTx.get<ancestor_score>().end()) {
327              auto it = mempool.mapTx.project<0>(mi);
328              assert(it != mempool.mapTx.end());
329              if (mapModifiedTx.count(it) || inBlock.count(it->GetSharedTx()->GetHash()) || failedTx.count(it->GetSharedTx()->GetHash())) {
330                  ++mi;
331                  continue;
332              }
333          }
334  
335          // Now that mi is not stale, determine which transaction to evaluate:
336          // the next entry from mapTx, or the best from mapModifiedTx?
337          bool fUsingModified = false;
338  
339          modtxscoreiter modit = mapModifiedTx.get<ancestor_score>().begin();
340          if (mi == mempool.mapTx.get<ancestor_score>().end()) {
341              // We're out of entries in mapTx; use the entry from mapModifiedTx
342              iter = modit->iter;
343              fUsingModified = true;
344          } else {
345              // Try to compare the mapTx entry to the mapModifiedTx entry
346              iter = mempool.mapTx.project<0>(mi);
347              if (modit != mapModifiedTx.get<ancestor_score>().end() &&
348                      CompareTxMemPoolEntryByAncestorFee()(*modit, CTxMemPoolModifiedEntry(iter))) {
349                  // The best entry in mapModifiedTx has higher score
350                  // than the one from mapTx.
351                  // Switch which transaction (package) to consider
352                  iter = modit->iter;
353                  fUsingModified = true;
354              } else {
355                  // Either no entry in mapModifiedTx, or it's worse than mapTx.
356                  // Increment mi for the next loop iteration.
357                  ++mi;
358              }
359          }
360  
361          // We skip mapTx entries that are inBlock, and mapModifiedTx shouldn't
362          // contain anything that is inBlock.
363          assert(!inBlock.count(iter->GetSharedTx()->GetHash()));
364  
365          uint64_t packageSize = iter->GetSizeWithAncestors();
366          CAmount packageFees = iter->GetModFeesWithAncestors();
367          int64_t packageSigOpsCost = iter->GetSigOpCostWithAncestors();
368          if (fUsingModified) {
369              packageSize = modit->nSizeWithAncestors;
370              packageFees = modit->nModFeesWithAncestors;
371              packageSigOpsCost = modit->nSigOpCostWithAncestors;
372          }
373  
374          if (packageFees < m_options.blockMinFeeRate.GetFee(packageSize)) {
375              // Everything else we might consider has a lower fee rate
376              return;
377          }
378  
379          if (!TestPackage(packageSize, packageSigOpsCost)) {
380              if (fUsingModified) {
381                  // Since we always look at the best entry in mapModifiedTx,
382                  // we must erase failed entries so that we can consider the
383                  // next best entry on the next loop iteration
384                  mapModifiedTx.get<ancestor_score>().erase(modit);
385                  failedTx.insert(iter->GetSharedTx()->GetHash());
386              }
387  
388              ++nConsecutiveFailed;
389  
390              if (nConsecutiveFailed > MAX_CONSECUTIVE_FAILURES && nBlockWeight >
391                      m_options.nBlockMaxWeight - 4000) {
392                  // Give up if we're close to full and haven't succeeded in a while
393                  break;
394              }
395              continue;
396          }
397  
398          auto ancestors{mempool.AssumeCalculateMemPoolAncestors(__func__, *iter, CTxMemPool::Limits::NoLimits(), /*fSearchForParents=*/false)};
399  
400          onlyUnconfirmed(ancestors);
401          ancestors.insert(iter);
402  
403          // Test if all tx's are Final
404          if (!TestPackageTransactions(ancestors)) {
405              if (fUsingModified) {
406                  mapModifiedTx.get<ancestor_score>().erase(modit);
407                  failedTx.insert(iter->GetSharedTx()->GetHash());
408              }
409              continue;
410          }
411  
412          // This transaction will make it in; reset the failed counter.
413          nConsecutiveFailed = 0;
414  
415          // Package can be added. Sort the entries in a valid order.
416          std::vector<CTxMemPool::txiter> sortedEntries;
417          SortForBlock(ancestors, sortedEntries);
418  
419          for (size_t i = 0; i < sortedEntries.size(); ++i) {
420              AddToBlock(sortedEntries[i]);
421              // Erase from the modified set, if present
422              mapModifiedTx.erase(sortedEntries[i]);
423          }
424  
425          ++nPackagesSelected;
426  
427          // Update transactions that depend on each of these
428          nDescendantsUpdated += UpdatePackagesForAdded(mempool, ancestors, mapModifiedTx);
429      }
430  }
431  } // namespace node