Branch data Line data Source code
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 <boost/multi_index/detail/hash_index_iterator.hpp>
8 : : #include <boost/operators.hpp>
9 : : #include <consensus/amount.h>
10 : : #include <policy/feerate.h>
11 : : #include <primitives/transaction.h>
12 : : #include <sync.h>
13 : : #include <txmempool.h>
14 : : #include <uint256.h>
15 : : #include <util/check.h>
16 : :
17 : : #include <algorithm>
18 : : #include <numeric>
19 : : #include <utility>
20 : :
21 : : namespace node {
22 : :
23 : 0 : MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
24 : : {
25 [ # # ][ # # ]: 0 : LOCK(mempool.cs);
26 : : // Find which outpoints to calculate bump fees for.
27 : : // Anything that's spent by the mempool is to-be-replaced
28 : : // Anything otherwise unavailable just has a bump fee of 0
29 [ # # ]: 0 : for (const auto& outpoint : outpoints) {
30 [ # # ][ # # ]: 0 : if (!mempool.exists(GenTxid::Txid(outpoint.hash))) {
[ # # ][ # # ]
31 : : // This UTXO is either confirmed or not yet submitted to mempool.
32 : : // If it's confirmed, no bump fee is required.
33 : : // If it's not yet submitted, we have no information, so return 0.
34 [ # # ]: 0 : m_bump_fees.emplace(outpoint, 0);
35 : 0 : continue;
36 : : }
37 : :
38 : : // UXTO is created by transaction in mempool, add to map.
39 : : // Note: This will either create a missing entry or add the outpoint to an existing entry
40 [ # # ][ # # ]: 0 : m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
[ # # ]
41 : :
42 [ # # ][ # # ]: 0 : if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
43 : : // This outpoint is already being spent by another transaction in the mempool. We
44 : : // assume that the caller wants to replace this transaction and its descendants. It
45 : : // would be unusual for the transaction to have descendants as the wallet won’t normally
46 : : // attempt to replace transactions with descendants. If the outpoint is from a mempool
47 : : // transaction, we still need to calculate its ancestors bump fees (added to
48 : : // m_requested_outpoints_by_txid below), but after removing the to-be-replaced entries.
49 : : //
50 : : // Note that the descendants of a transaction include the transaction itself. Also note,
51 : : // that this is only calculating bump fees. RBF fee rules should be handled separately.
52 : 0 : CTxMemPool::setEntries descendants;
53 [ # # ][ # # ]: 0 : mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
[ # # ][ # # ]
[ # # ]
54 [ # # ]: 0 : for (const auto& desc_txiter : descendants) {
55 [ # # ][ # # ]: 0 : m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
[ # # ][ # # ]
[ # # ]
56 : : }
57 : 0 : }
58 : : }
59 : :
60 : : // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
61 [ # # ]: 0 : if (m_requested_outpoints_by_txid.empty()) return;
62 : :
63 : : // Calculate the cluster and construct the entry map.
64 : 0 : std::vector<uint256> txids_needed;
65 [ # # ]: 0 : txids_needed.reserve(m_requested_outpoints_by_txid.size());
66 [ # # ]: 0 : for (const auto& [txid, _]: m_requested_outpoints_by_txid) {
67 [ # # ]: 0 : txids_needed.push_back(txid);
68 : : }
69 [ # # ]: 0 : const auto cluster = mempool.GatherClusters(txids_needed);
70 [ # # ]: 0 : if (cluster.empty()) {
71 : : // An empty cluster means that at least one of the transactions is missing from the mempool
72 : : // (should not be possible given processing above) or DoS limit was hit.
73 : 0 : m_ready_to_calculate = false;
74 : 0 : return;
75 : : }
76 : :
77 : : // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
78 [ # # ]: 0 : for (const auto& txiter : cluster) {
79 [ # # ][ # # ]: 0 : if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
[ # # ][ # # ]
[ # # ][ # # ]
80 [ # # ][ # # ]: 0 : auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
[ # # ][ # # ]
81 [ # # ][ # # ]: 0 : MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
[ # # ]
82 [ # # ][ # # ]: 0 : /*vsize_self=*/txiter->GetTxSize(),
83 [ # # ][ # # ]: 0 : /*vsize_ancestor=*/txiter->GetSizeWithAncestors(),
84 [ # # ][ # # ]: 0 : /*fee_self=*/txiter->GetModifiedFee(),
85 [ # # ][ # # ]: 0 : /*fee_ancestor=*/txiter->GetModFeesWithAncestors()});
86 [ # # ][ # # ]: 0 : m_entries.push_back(mapiter);
87 : 0 : } else {
88 [ # # ][ # # ]: 0 : auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
[ # # ][ # # ]
[ # # ]
89 [ # # ]: 0 : if (outpoints_it != m_requested_outpoints_by_txid.end()) {
90 : : // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
91 : : // this UTXO is impossible as it will no longer exist after the replacement.
92 [ # # ]: 0 : for (const auto& outpoint : outpoints_it->second) {
93 [ # # ]: 0 : m_bump_fees.emplace(outpoint, 0);
94 : : }
95 [ # # ]: 0 : m_requested_outpoints_by_txid.erase(outpoints_it);
96 : 0 : }
97 : : }
98 : : }
99 : :
100 : : // Build the m_descendant_set_by_txid cache.
101 [ # # ]: 0 : for (const auto& txiter : cluster) {
102 [ # # ][ # # ]: 0 : const auto& txid = txiter->GetTx().GetHash();
[ # # ]
103 : : // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
104 : 0 : // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
105 : 0 : std::vector<MockEntryMap::iterator> cached_descendants;
106 [ # # ][ # # ]: 0 : const bool remove{m_to_be_replaced.count(txid) > 0};
107 : 0 : CTxMemPool::setEntries descendants;
108 [ # # ]: 0 : mempool.CalculateDescendants(txiter, descendants);
109 [ # # ][ # # ]: 0 : Assume(descendants.count(txiter) > 0);
110 [ # # ]: 0 : for (const auto& desc_txiter : descendants) {
111 [ # # ][ # # ]: 0 : const auto txid_desc = desc_txiter->GetTx().GetHash();
[ # # ]
112 [ # # ][ # # ]: 0 : const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
113 [ # # ][ # # ]: 0 : auto desc_it{m_entries_by_txid.find(txid_desc)};
114 [ # # ]: 0 : Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
115 [ # # ][ # # ]: 0 : if (remove) Assume(remove_desc);
116 : : // It's possible that remove=false but remove_desc=true.
117 [ # # ][ # # ]: 0 : if (!remove && !remove_desc) {
118 [ # # ]: 0 : cached_descendants.push_back(desc_it);
119 : 0 : }
120 : : }
121 [ # # ]: 0 : if (remove) {
122 [ # # ]: 0 : Assume(cached_descendants.empty());
123 : 0 : } else {
124 [ # # ]: 0 : m_descendant_set_by_txid.emplace(txid, cached_descendants);
125 : : }
126 : 0 : }
127 : :
128 : : // Release the mempool lock; we now have all the information we need for a subset of the entries
129 : : // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
130 [ # # ]: 0 : Assume(m_in_block.empty());
131 [ # # ]: 0 : Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
132 [ # # ]: 0 : SanityCheck();
133 [ # # ]: 0 : }
134 : :
135 : 0 : MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
136 : : const std::map<Txid, std::set<Txid>>& descendant_caches)
137 : : {
138 [ # # ]: 0 : for (const auto& entry : manual_entries) {
139 [ # # ][ # # ]: 0 : const auto& txid = entry.GetTx().GetHash();
140 : : // We need to know the descendant set of every transaction.
141 [ # # ][ # # ]: 0 : if (!Assume(descendant_caches.count(txid) > 0)) {
[ # # ]
142 : 0 : m_ready_to_calculate = false;
143 : 0 : return;
144 : : }
145 : : // Just forward these args onto MiniMinerMempoolEntry
146 [ # # ]: 0 : auto [mapiter, success] = m_entries_by_txid.emplace(txid, entry);
147 : : // Txids must be unique; this txid shouldn't already be an entry in m_entries_by_txid
148 [ # # ][ # # ]: 0 : if (Assume(success)) m_entries.push_back(mapiter);
[ # # ][ # # ]
149 : : }
150 : : // Descendant cache is already built, but we need to translate them to m_entries_by_txid iters.
151 [ # # ]: 0 : for (const auto& [txid, desc_txids] : descendant_caches) {
152 : : // Descendant cache should include at least the tx itself.
153 [ # # ][ # # ]: 0 : if (!Assume(!desc_txids.empty())) {
154 : 0 : m_ready_to_calculate = false;
155 : 0 : return;
156 : : }
157 : 0 : std::vector<MockEntryMap::iterator> descendants;
158 [ # # ]: 0 : for (const auto& desc_txid : desc_txids) {
159 [ # # ][ # # ]: 0 : auto desc_it{m_entries_by_txid.find(desc_txid)};
160 : : // Descendants should only include transactions with corresponding entries.
161 [ # # ][ # # ]: 0 : if (!Assume(desc_it != m_entries_by_txid.end())) {
162 : 0 : m_ready_to_calculate = false;
163 : 0 : return;
164 : : } else {
165 [ # # ]: 0 : descendants.emplace_back(desc_it);
166 : : }
167 : : }
168 [ # # ][ # # ]: 0 : m_descendant_set_by_txid.emplace(txid, descendants);
169 [ # # # ]: 0 : }
170 [ # # ]: 0 : Assume(m_to_be_replaced.empty());
171 [ # # ]: 0 : Assume(m_requested_outpoints_by_txid.empty());
172 [ # # ]: 0 : Assume(m_bump_fees.empty());
173 [ # # ]: 0 : Assume(m_inclusion_order.empty());
174 [ # # ]: 0 : SanityCheck();
175 : 0 : }
176 : :
177 : : // Compare by min(ancestor feerate, individual feerate), then iterator
178 : : //
179 : : // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
180 : : // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
181 : : // transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
182 : : struct AncestorFeerateComparator
183 : : {
184 : : template<typename I>
185 : 0 : bool operator()(const I& a, const I& b) const {
186 : 0 : auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
187 : 0 : const CAmount ancestor_fee{e.GetModFeesWithAncestors()};
188 : 0 : const int64_t ancestor_size{e.GetSizeWithAncestors()};
189 : 0 : const CAmount tx_fee{e.GetModifiedFee()};
190 : 0 : const int64_t tx_size{e.GetTxSize()};
191 : : // Comparing ancestor feerate with individual feerate:
192 : : // ancestor_fee / ancestor_size <= tx_fee / tx_size
193 : : // Avoid division and possible loss of precision by
194 : : // multiplying both sides by the sizes:
195 [ # # ]: 0 : return ancestor_fee * tx_size < tx_fee * ancestor_size ?
196 : 0 : CFeeRate(ancestor_fee, ancestor_size) :
197 : 0 : CFeeRate(tx_fee, tx_size);
198 : : };
199 : 0 : CFeeRate a_feerate{min_feerate(a->second)};
200 : 0 : CFeeRate b_feerate{min_feerate(b->second)};
201 [ # # ]: 0 : if (a_feerate != b_feerate) {
202 : 0 : return a_feerate > b_feerate;
203 : : }
204 : : // Use txid as tiebreaker for stable sorting
205 : 0 : return a->first < b->first;
206 : 0 : }
207 : : };
208 : :
209 : 0 : void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
210 : : {
211 : 0 : Assume(ancestors.size() >= 1);
212 : : // "Mine" all transactions in this ancestor set.
213 [ # # ]: 0 : for (auto& anc : ancestors) {
214 : 0 : Assume(m_in_block.count(anc->first) == 0);
215 : 0 : m_in_block.insert(anc->first);
216 : 0 : m_total_fees += anc->second.GetModifiedFee();
217 : 0 : m_total_vsize += anc->second.GetTxSize();
218 : 0 : auto it = m_descendant_set_by_txid.find(anc->first);
219 : : // Each entry’s descendant set includes itself
220 : 0 : Assume(it != m_descendant_set_by_txid.end());
221 [ # # ]: 0 : for (auto& descendant : it->second) {
222 : : // If these fail, we must be double-deducting.
223 : 0 : Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
224 : 0 : Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
225 : 0 : descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
226 : : }
227 : : }
228 : : // Delete these entries.
229 [ # # ]: 0 : for (const auto& anc : ancestors) {
230 : 0 : m_descendant_set_by_txid.erase(anc->first);
231 : : // The above loop should have deducted each ancestor's size and fees from each of their
232 : : // respective descendants exactly once.
233 : 0 : Assume(anc->second.GetModFeesWithAncestors() == 0);
234 : 0 : Assume(anc->second.GetSizeWithAncestors() == 0);
235 : 0 : auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
236 : 0 : Assume(vec_it != m_entries.end());
237 : 0 : m_entries.erase(vec_it);
238 : 0 : m_entries_by_txid.erase(anc);
239 : : }
240 : 0 : }
241 : :
242 : 0 : void MiniMiner::SanityCheck() const
243 : : {
244 : : // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
245 : 0 : Assume(m_entries.size() == m_entries_by_txid.size());
246 : 0 : Assume(m_entries.size() == m_descendant_set_by_txid.size());
247 : : // Cached ancestor values should be at least as large as the transaction's own fee and size
248 [ # # ]: 0 : Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
249 : : return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
250 : : entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
251 : : // None of the entries should be to-be-replaced transactions
252 : 0 : Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
253 : : [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
254 : 0 : }
255 : :
256 : 0 : void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
257 : : {
258 : 0 : const auto num_txns{m_entries_by_txid.size()};
259 : 0 : uint32_t sequence_num{0};
260 [ # # ]: 0 : while (!m_entries_by_txid.empty()) {
261 : : // Sort again, since transaction removal may change some m_entries' ancestor feerates.
262 : 0 : std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
263 : :
264 : : // Pick highest ancestor feerate entry.
265 : 0 : auto best_iter = m_entries.begin();
266 : 0 : Assume(best_iter != m_entries.end());
267 : 0 : const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
268 : 0 : const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
269 : : // Stop here. Everything that didn't "make it into the block" has bumpfee.
270 [ # # ][ # # ]: 0 : if (target_feerate.has_value() &&
271 : 0 : ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) {
272 : 0 : break;
273 : : }
274 : :
275 : : // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
276 : : // change at every iteration, so this is more efficient than maintaining a cache.
277 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
278 : : {
279 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
280 [ # # ]: 0 : to_process.insert(*best_iter);
281 [ # # ]: 0 : while (!to_process.empty()) {
282 : 0 : auto iter = to_process.begin();
283 [ # # ]: 0 : Assume(iter != to_process.end());
284 [ # # ]: 0 : ancestors.insert(*iter);
285 [ # # ][ # # ]: 0 : for (const auto& input : (*iter)->second.GetTx().vin) {
286 [ # # ][ # # ]: 0 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
[ # # ]
287 [ # # ][ # # ]: 0 : if (ancestors.count(parent_it) == 0) {
288 [ # # ]: 0 : to_process.insert(parent_it);
289 : 0 : }
290 : 0 : }
291 : : }
292 [ # # ]: 0 : to_process.erase(iter);
293 : : }
294 : 0 : }
295 : : // Track the order in which transactions were selected.
296 [ # # ]: 0 : for (const auto& ancestor : ancestors) {
297 [ # # ][ # # ]: 0 : m_inclusion_order.emplace(Txid::FromUint256(ancestor->first), sequence_num);
298 : : }
299 [ # # ]: 0 : DeleteAncestorPackage(ancestors);
300 [ # # ]: 0 : SanityCheck();
301 : 0 : ++sequence_num;
302 : 0 : }
303 [ # # ]: 0 : if (!target_feerate.has_value()) {
304 : 0 : Assume(m_in_block.size() == num_txns);
305 : 0 : } else {
306 [ # # ]: 0 : Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize));
307 : : }
308 [ # # ]: 0 : Assume(m_in_block.empty() || sequence_num > 0);
309 : 0 : Assume(m_in_block.size() == m_inclusion_order.size());
310 : : // Do not try to continue building the block template with a different feerate.
311 : 0 : m_ready_to_calculate = false;
312 : 0 : }
313 : :
314 : :
315 : 0 : std::map<Txid, uint32_t> MiniMiner::Linearize()
316 : : {
317 : 0 : BuildMockTemplate(std::nullopt);
318 : 0 : return m_inclusion_order;
319 : : }
320 : :
321 : 0 : std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
322 : : {
323 [ # # ]: 0 : if (!m_ready_to_calculate) return {};
324 : : // Build a block template until the target feerate is hit.
325 : 0 : BuildMockTemplate(target_feerate);
326 : :
327 : : // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
328 : : // ancestor package with at least the target feerate and don't need to be bumped.
329 [ # # ]: 0 : for (const auto& txid : m_in_block) {
330 : : // Not all of the block transactions were necessarily requested.
331 : 0 : auto it = m_requested_outpoints_by_txid.find(txid);
332 [ # # ]: 0 : if (it != m_requested_outpoints_by_txid.end()) {
333 [ # # ]: 0 : for (const auto& outpoint : it->second) {
334 : 0 : m_bump_fees.emplace(outpoint, 0);
335 : : }
336 : 0 : m_requested_outpoints_by_txid.erase(it);
337 : 0 : }
338 : : }
339 : :
340 : : // A transactions and its ancestors will only be picked into a block when
341 : : // both the ancestor set feerate and the individual feerate meet the target
342 : : // feerate.
343 : : //
344 : : // We had to convince ourselves that after running the mini miner and
345 : : // picking all eligible transactions into our MockBlockTemplate, there
346 : : // could still be transactions remaining that have a lower individual
347 : : // feerate than their ancestor feerate. So here is an example:
348 : : //
349 : : // ┌─────────────────┐
350 : : // │ │
351 : : // │ Grandparent │
352 : : // │ 1700 vB │
353 : : // │ 1700 sats │ Target feerate: 10 s/vB
354 : : // │ 1 s/vB │ GP Ancestor Set Feerate (ASFR): 1 s/vB
355 : : // │ │ P1_ASFR: 9.84 s/vB
356 : : // └──────▲───▲──────┘ P2_ASFR: 2.47 s/vB
357 : : // │ │ C_ASFR: 10.27 s/vB
358 : : // ┌───────────────┐ │ │ ┌──────────────┐
359 : : // │ ├────┘ └────┤ │ ⇒ C_FR < TFR < C_ASFR
360 : : // │ Parent 1 │ │ Parent 2 │
361 : : // │ 200 vB │ │ 200 vB │
362 : : // │ 17000 sats │ │ 3000 sats │
363 : : // │ 85 s/vB │ │ 15 s/vB │
364 : : // │ │ │ │
365 : : // └───────────▲───┘ └───▲──────────┘
366 : : // │ │
367 : : // │ ┌───────────┐ │
368 : : // └────┤ ├────┘
369 : : // │ Child │
370 : : // │ 100 vB │
371 : : // │ 900 sats │
372 : : // │ 9 s/vB │
373 : : // │ │
374 : : // └───────────┘
375 : : //
376 : : // We therefore calculate both the bump fee that is necessary to elevate
377 : : // the individual transaction to the target feerate:
378 : : // target_feerate × tx_size - tx_fees
379 : : // and the bump fee that is necessary to bump the entire ancestor set to
380 : : // the target feerate:
381 : : // target_feerate × ancestor_set_size - ancestor_set_fees
382 : : // By picking the maximum from the two, we ensure that a transaction meets
383 : : // both criteria.
384 [ # # ]: 0 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
385 : 0 : auto it = m_entries_by_txid.find(txid);
386 : 0 : Assume(it != m_entries_by_txid.end());
387 [ # # ]: 0 : if (it != m_entries_by_txid.end()) {
388 : 0 : Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
389 : 0 : CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
390 : 0 : CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
391 : 0 : const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
392 : 0 : Assume(bump_fee >= 0);
393 [ # # ]: 0 : for (const auto& outpoint : outpoints) {
394 : 0 : m_bump_fees.emplace(outpoint, bump_fee);
395 : : }
396 : 0 : }
397 : : }
398 : 0 : return m_bump_fees;
399 : 0 : }
400 : :
401 : 0 : std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
402 : : {
403 [ # # ]: 0 : if (!m_ready_to_calculate) return std::nullopt;
404 : : // Build a block template until the target feerate is hit.
405 : 0 : BuildMockTemplate(target_feerate);
406 : :
407 : : // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
408 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
409 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
410 [ # # ]: 0 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
411 : : // Skip any ancestors that already have a miner score higher than the target feerate
412 : : // (already "made it" into the block)
413 [ # # ][ # # ]: 0 : if (m_in_block.count(txid)) continue;
[ # # ]
414 [ # # ][ # # ]: 0 : auto iter = m_entries_by_txid.find(txid);
415 [ # # ]: 0 : if (iter == m_entries_by_txid.end()) continue;
416 [ # # ]: 0 : to_process.insert(iter);
417 [ # # ]: 0 : ancestors.insert(iter);
418 : : }
419 : :
420 : 0 : std::set<uint256> has_been_processed;
421 [ # # ]: 0 : while (!to_process.empty()) {
422 : 0 : auto iter = to_process.begin();
423 [ # # ]: 0 : const CTransaction& tx = (*iter)->second.GetTx();
424 [ # # ]: 0 : for (const auto& input : tx.vin) {
425 [ # # ][ # # ]: 0 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
[ # # ]
426 [ # # ][ # # ]: 0 : if (!has_been_processed.count(input.prevout.hash)) {
[ # # ]
427 [ # # ]: 0 : to_process.insert(parent_it);
428 : 0 : }
429 [ # # ]: 0 : ancestors.insert(parent_it);
430 : 0 : }
431 : : }
432 [ # # ][ # # ]: 0 : has_been_processed.insert(tx.GetHash());
[ # # ]
433 [ # # ]: 0 : to_process.erase(iter);
434 : : }
435 [ # # ]: 0 : const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
436 : 0 : [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
437 [ # # ]: 0 : const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
438 : 0 : [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
439 [ # # ]: 0 : return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
440 : 0 : }
441 : : } // namespace node
|
