Bitcoin Core  25.99.0
P2P Digital Currency
mini_miner.cpp
Go to the documentation of this file.
1 // Copyright (c) 2023 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <node/mini_miner.h>
6 
7 #include <consensus/amount.h>
8 #include <policy/feerate.h>
10 #include <util/check.h>
11 
12 #include <algorithm>
13 #include <numeric>
14 #include <utility>
15 
16 namespace node {
17 
18 MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
19 {
20  LOCK(mempool.cs);
21  // Find which outpoints to calculate bump fees for.
22  // Anything that's spent by the mempool is to-be-replaced
23  // Anything otherwise unavailable just has a bump fee of 0
24  for (const auto& outpoint : outpoints) {
25  if (!mempool.exists(GenTxid::Txid(outpoint.hash))) {
26  // This UTXO is either confirmed or not yet submitted to mempool.
27  // If it's confirmed, no bump fee is required.
28  // If it's not yet submitted, we have no information, so return 0.
29  m_bump_fees.emplace(outpoint, 0);
30  continue;
31  }
32 
33  // UXTO is created by transaction in mempool, add to map.
34  // Note: This will either create a missing entry or add the outpoint to an existing entry
35  m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
36 
37  if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
38  // This outpoint is already being spent by another transaction in the mempool. We
39  // assume that the caller wants to replace this transaction and its descendants. It
40  // would be unusual for the transaction to have descendants as the wallet won’t normally
41  // attempt to replace transactions with descendants. If the outpoint is from a mempool
42  // transaction, we still need to calculate its ancestors bump fees (added to
43  // m_requested_outpoints_by_txid below), but after removing the to-be-replaced entries.
44  //
45  // Note that the descendants of a transaction include the transaction itself. Also note,
46  // that this is only calculating bump fees. RBF fee rules should be handled separately.
47  CTxMemPool::setEntries descendants;
48  mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
49  for (const auto& desc_txiter : descendants) {
50  m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
51  }
52  }
53  }
54 
55  // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
56  if (m_requested_outpoints_by_txid.empty()) return;
57 
58  // Calculate the cluster and construct the entry map.
59  std::vector<uint256> txids_needed;
60  txids_needed.reserve(m_requested_outpoints_by_txid.size());
61  for (const auto& [txid, _]: m_requested_outpoints_by_txid) {
62  txids_needed.push_back(txid);
63  }
64  const auto cluster = mempool.GatherClusters(txids_needed);
65  if (cluster.empty()) {
66  // An empty cluster means that at least one of the transactions is missing from the mempool
67  // (should not be possible given processing above) or DoS limit was hit.
68  m_ready_to_calculate = false;
69  return;
70  }
71 
72  // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
73  for (const auto& txiter : cluster) {
74  if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
75  auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(), MiniMinerMempoolEntry(txiter));
76  m_entries.push_back(mapiter);
77  } else {
78  auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
79  if (outpoints_it != m_requested_outpoints_by_txid.end()) {
80  // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
81  // this UTXO is impossible as it will no longer exist after the replacement.
82  for (const auto& outpoint : outpoints_it->second) {
83  m_bump_fees.emplace(outpoint, 0);
84  }
85  m_requested_outpoints_by_txid.erase(outpoints_it);
86  }
87  }
88  }
89 
90  // Build the m_descendant_set_by_txid cache.
91  for (const auto& txiter : cluster) {
92  const auto& txid = txiter->GetTx().GetHash();
93  // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
94  // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
95  std::vector<MockEntryMap::iterator> cached_descendants;
96  const bool remove{m_to_be_replaced.count(txid) > 0};
97  CTxMemPool::setEntries descendants;
98  mempool.CalculateDescendants(txiter, descendants);
99  Assume(descendants.count(txiter) > 0);
100  for (const auto& desc_txiter : descendants) {
101  const auto txid_desc = desc_txiter->GetTx().GetHash();
102  const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
103  auto desc_it{m_entries_by_txid.find(txid_desc)};
104  Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
105  if (remove) Assume(remove_desc);
106  // It's possible that remove=false but remove_desc=true.
107  if (!remove && !remove_desc) {
108  cached_descendants.push_back(desc_it);
109  }
110  }
111  if (remove) {
112  Assume(cached_descendants.empty());
113  } else {
114  m_descendant_set_by_txid.emplace(txid, cached_descendants);
115  }
116  }
117 
118  // Release the mempool lock; we now have all the information we need for a subset of the entries
119  // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
120  Assume(m_in_block.empty());
121  Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
122  SanityCheck();
123 }
124 
125 // Compare by min(ancestor feerate, individual feerate), then iterator
126 //
127 // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
128 // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
129 // transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
131 {
132  template<typename I>
133  bool operator()(const I& a, const I& b) const {
134  auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
135  const CAmount ancestor_fee{e.GetModFeesWithAncestors()};
136  const int64_t ancestor_size{e.GetSizeWithAncestors()};
137  const CAmount tx_fee{e.GetModifiedFee()};
138  const int64_t tx_size{e.GetTxSize()};
139  // Comparing ancestor feerate with individual feerate:
140  // ancestor_fee / ancestor_size <= tx_fee / tx_size
141  // Avoid division and possible loss of precision by
142  // multiplying both sides by the sizes:
143  return ancestor_fee * tx_size < tx_fee * ancestor_size ?
144  CFeeRate(ancestor_fee, ancestor_size) :
145  CFeeRate(tx_fee, tx_size);
146  };
147  CFeeRate a_feerate{min_feerate(a->second)};
148  CFeeRate b_feerate{min_feerate(b->second)};
149  if (a_feerate != b_feerate) {
150  return a_feerate > b_feerate;
151  }
152  // Use txid as tiebreaker for stable sorting
153  return a->first < b->first;
154  }
155 };
156 
157 void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
158 {
159  Assume(ancestors.size() >= 1);
160  // "Mine" all transactions in this ancestor set.
161  for (auto& anc : ancestors) {
162  Assume(m_in_block.count(anc->first) == 0);
163  m_in_block.insert(anc->first);
164  m_total_fees += anc->second.GetModifiedFee();
165  m_total_vsize += anc->second.GetTxSize();
166  auto it = m_descendant_set_by_txid.find(anc->first);
167  // Each entry’s descendant set includes itself
168  Assume(it != m_descendant_set_by_txid.end());
169  for (auto& descendant : it->second) {
170  // If these fail, we must be double-deducting.
171  Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
172  Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
173  descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
174  }
175  }
176  // Delete these entries.
177  for (const auto& anc : ancestors) {
178  m_descendant_set_by_txid.erase(anc->first);
179  // The above loop should have deducted each ancestor's size and fees from each of their
180  // respective descendants exactly once.
181  Assume(anc->second.GetModFeesWithAncestors() == 0);
182  Assume(anc->second.GetSizeWithAncestors() == 0);
183  auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
184  Assume(vec_it != m_entries.end());
185  m_entries.erase(vec_it);
186  m_entries_by_txid.erase(anc);
187  }
188 }
189 
191 {
192  // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
193  Assume(m_entries.size() == m_entries_by_txid.size());
194  Assume(m_entries.size() == m_descendant_set_by_txid.size());
195  // Cached ancestor values should be at least as large as the transaction's own fee and size
196  Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
197  return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
198  entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
199  // None of the entries should be to-be-replaced transactions
200  Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
201  [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
202 }
203 
204 void MiniMiner::BuildMockTemplate(const CFeeRate& target_feerate)
205 {
206  while (!m_entries_by_txid.empty()) {
207  // Sort again, since transaction removal may change some m_entries' ancestor feerates.
208  std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
209 
210  // Pick highest ancestor feerate entry.
211  auto best_iter = m_entries.begin();
212  Assume(best_iter != m_entries.end());
213  const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
214  const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
215  // Stop here. Everything that didn't "make it into the block" has bumpfee.
216  if (ancestor_package_fee < target_feerate.GetFee(ancestor_package_size)) {
217  break;
218  }
219 
220  // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
221  // change at every iteration, so this is more efficient than maintaining a cache.
222  std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
223  {
224  std::set<MockEntryMap::iterator, IteratorComparator> to_process;
225  to_process.insert(*best_iter);
226  while (!to_process.empty()) {
227  auto iter = to_process.begin();
228  Assume(iter != to_process.end());
229  ancestors.insert(*iter);
230  for (const auto& input : (*iter)->second.GetTx().vin) {
231  if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
232  if (ancestors.count(parent_it) == 0) {
233  to_process.insert(parent_it);
234  }
235  }
236  }
237  to_process.erase(iter);
238  }
239  }
240  DeleteAncestorPackage(ancestors);
241  SanityCheck();
242  }
243  Assume(m_in_block.empty() || m_total_fees >= target_feerate.GetFee(m_total_vsize));
244  // Do not try to continue building the block template with a different feerate.
245  m_ready_to_calculate = false;
246 }
247 
248 std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
249 {
250  if (!m_ready_to_calculate) return {};
251  // Build a block template until the target feerate is hit.
252  BuildMockTemplate(target_feerate);
253 
254  // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
255  // ancestor package with at least the target feerate and don't need to be bumped.
256  for (const auto& txid : m_in_block) {
257  // Not all of the block transactions were necessarily requested.
258  auto it = m_requested_outpoints_by_txid.find(txid);
259  if (it != m_requested_outpoints_by_txid.end()) {
260  for (const auto& outpoint : it->second) {
261  m_bump_fees.emplace(outpoint, 0);
262  }
264  }
265  }
266 
267  // A transactions and its ancestors will only be picked into a block when
268  // both the ancestor set feerate and the individual feerate meet the target
269  // feerate.
270  //
271  // We had to convince ourselves that after running the mini miner and
272  // picking all eligible transactions into our MockBlockTemplate, there
273  // could still be transactions remaining that have a lower individual
274  // feerate than their ancestor feerate. So here is an example:
275  //
276  // ┌─────────────────┐
277  // │ │
278  // │ Grandparent │
279  // │ 1700 vB │
280  // │ 1700 sats │ Target feerate: 10 s/vB
281  // │ 1 s/vB │ GP Ancestor Set Feerate (ASFR): 1 s/vB
282  // │ │ P1_ASFR: 9.84 s/vB
283  // └──────▲───▲──────┘ P2_ASFR: 2.47 s/vB
284  // │ │ C_ASFR: 10.27 s/vB
285  // ┌───────────────┐ │ │ ┌──────────────┐
286  // │ ├────┘ └────┤ │ ⇒ C_FR < TFR < C_ASFR
287  // │ Parent 1 │ │ Parent 2 │
288  // │ 200 vB │ │ 200 vB │
289  // │ 17000 sats │ │ 3000 sats │
290  // │ 85 s/vB │ │ 15 s/vB │
291  // │ │ │ │
292  // └───────────▲───┘ └───▲──────────┘
293  // │ │
294  // │ ┌───────────┐ │
295  // └────┤ ├────┘
296  // │ Child │
297  // │ 100 vB │
298  // │ 900 sats │
299  // │ 9 s/vB │
300  // │ │
301  // └───────────┘
302  //
303  // We therefore calculate both the bump fee that is necessary to elevate
304  // the individual transaction to the target feerate:
305  // target_feerate × tx_size - tx_fees
306  // and the bump fee that is necessary to bump the entire ancestor set to
307  // the target feerate:
308  // target_feerate × ancestor_set_size - ancestor_set_fees
309  // By picking the maximum from the two, we ensure that a transaction meets
310  // both criteria.
311  for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
312  auto it = m_entries_by_txid.find(txid);
313  Assume(it != m_entries_by_txid.end());
314  if (it != m_entries_by_txid.end()) {
315  Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
316  CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
317  CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
318  const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
319  Assume(bump_fee >= 0);
320  for (const auto& outpoint : outpoints) {
321  m_bump_fees.emplace(outpoint, bump_fee);
322  }
323  }
324  }
325  return m_bump_fees;
326 }
327 
328 std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
329 {
330  if (!m_ready_to_calculate) return std::nullopt;
331  // Build a block template until the target feerate is hit.
332  BuildMockTemplate(target_feerate);
333 
334  // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
335  std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
336  std::set<MockEntryMap::iterator, IteratorComparator> to_process;
337  for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
338  // Skip any ancestors that already have a miner score higher than the target feerate
339  // (already "made it" into the block)
340  if (m_in_block.count(txid)) continue;
341  auto iter = m_entries_by_txid.find(txid);
342  if (iter == m_entries_by_txid.end()) continue;
343  to_process.insert(iter);
344  ancestors.insert(iter);
345  }
346 
347  std::set<uint256> has_been_processed;
348  while (!to_process.empty()) {
349  auto iter = to_process.begin();
350  const CTransaction& tx = (*iter)->second.GetTx();
351  for (const auto& input : tx.vin) {
352  if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
353  if (!has_been_processed.count(input.prevout.hash)) {
354  to_process.insert(parent_it);
355  }
356  ancestors.insert(parent_it);
357  }
358  }
359  has_been_processed.insert(tx.GetHash());
360  to_process.erase(iter);
361  }
362  const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
363  [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
364  const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
365  [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
366  return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
367 }
368 } // namespace node
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
#define Assume(val)
Assume is the identity function.
Definition: check.h:85
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
CAmount GetFee(uint32_t num_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
Definition: feerate.cpp:23
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:295
const uint256 & GetHash() const
Definition: transaction.h:337
const std::vector< CTxIn > vin
Definition: transaction.h:305
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:302
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:391
std::optional< txiter > GetIter(const uint256 &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Returns an iterator to the given hash, if found.
Definition: txmempool.cpp:956
std::vector< txiter > GatherClusters(const std::vector< uint256 > &txids) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Collect the entire cluster of connected transactions for each transaction in txids.
Definition: txmempool.cpp:1222
std::set< txiter, CompareIteratorByHash > setEntries
Definition: txmempool.h:397
bool exists(const GenTxid &gtxid) const
Definition: txmempool.h:678
const CTransaction * GetConflictTx(const COutPoint &prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Get the transaction in the pool that spends the same prevout.
Definition: txmempool.cpp:950
void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Populate setDescendants with all in-mempool descendants of hash.
Definition: txmempool.cpp:544
static GenTxid Txid(const uint256 &hash)
Definition: transaction.h:432
std::map< uint256, std::vector< MockEntryMap::iterator > > m_descendant_set_by_txid
Map of txid to its descendants.
Definition: mini_miner.h:93
int32_t m_total_vsize
Definition: mini_miner.h:83
void BuildMockTemplate(const CFeeRate &target_feerate)
Build a block template until the target feerate is hit.
Definition: mini_miner.cpp:204
CAmount m_total_fees
Definition: mini_miner.h:82
std::map< COutPoint, CAmount > CalculateBumpFees(const CFeeRate &target_feerate)
Construct a new block template and, for each outpoint corresponding to a transaction that did not mak...
Definition: mini_miner.cpp:248
std::map< uint256, std::vector< COutPoint > > m_requested_outpoints_by_txid
Definition: mini_miner.h:73
std::optional< CAmount > CalculateTotalBumpFees(const CFeeRate &target_feerate)
Construct a new block template and, calculate the cost of bumping all transactions that did not make ...
Definition: mini_miner.cpp:328
std::set< uint256 > m_in_block
Definition: mini_miner.h:79
void DeleteAncestorPackage(const std::set< MockEntryMap::iterator, IteratorComparator > &ancestors)
Consider this ancestor package "mined" so remove all these entries from our data structures.
Definition: mini_miner.cpp:157
std::map< uint256, MiniMinerMempoolEntry > m_entries_by_txid
Main data structure holding the entries, can be indexed by txid.
Definition: mini_miner.h:86
void SanityCheck() const
Perform some checks.
Definition: mini_miner.cpp:190
std::vector< MockEntryMap::iterator > m_entries
Vector of entries, can be sorted by ancestor feerate.
Definition: mini_miner.h:90
MiniMiner(const CTxMemPool &mempool, const std::vector< COutPoint > &outpoints)
Definition: mini_miner.cpp:18
std::set< uint256 > m_to_be_replaced
Definition: mini_miner.h:68
std::map< COutPoint, CAmount > m_bump_fees
Definition: mini_miner.h:76
bool m_ready_to_calculate
Definition: mini_miner.h:64
Definition: mini_miner.h:18
volatile double sum
Definition: examples.cpp:10
Definition: init.h:25
bool operator()(const I &a, const I &b) const
Definition: mini_miner.cpp:133
#define LOCK(cs)
Definition: sync.h:258
bilingual_str _(const char *psz)
Translation function.
Definition: translation.h:74