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 <consensus/amount.h>
8 : : #include <policy/feerate.h>
9 : : #include <primitives/transaction.h>
10 : : #include <util/check.h>
11 : :
12 : : #include <algorithm>
13 : : #include <numeric>
14 : : #include <utility>
15 : :
16 : : namespace node {
17 [ + - ]: 2 :
18 [ + - ]: 2 : MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
19 : : {
20 [ # # ][ # # ]: 0 : 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 [ # # ]: 0 : for (const auto& outpoint : outpoints) {
25 [ # # ][ # # ]: 0 : 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 [ # # ]: 0 : m_bump_fees.emplace(outpoint, 0);
30 : 0 : 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 [ # # ][ # # ]: 0 : m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
36 : :
37 [ # # ][ # # ]: 0 : 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 : 0 : CTxMemPool::setEntries descendants;
48 [ # # ][ # # ]: 0 : mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
[ # # ][ # # ]
49 [ # # ]: 0 : for (const auto& desc_txiter : descendants) {
50 [ # # ][ # # ]: 0 : m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
[ # # ][ # # ]
51 : : }
52 : 0 : }
53 : : }
54 : :
55 : : // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
56 [ # # ]: 0 : if (m_requested_outpoints_by_txid.empty()) return;
57 : :
58 : : // Calculate the cluster and construct the entry map.
59 : 0 : std::vector<uint256> txids_needed;
60 [ # # ]: 0 : txids_needed.reserve(m_requested_outpoints_by_txid.size());
61 [ # # ]: 0 : for (const auto& [txid, _]: m_requested_outpoints_by_txid) {
62 [ # # ]: 0 : txids_needed.push_back(txid);
63 : : }
64 [ # # ]: 0 : const auto cluster = mempool.GatherClusters(txids_needed);
65 [ # # ]: 0 : 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 : 0 : m_ready_to_calculate = false;
69 : 0 : return;
70 : : }
71 : :
72 : : // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
73 [ # # ]: 0 : for (const auto& txiter : cluster) {
74 [ # # ][ # # ]: 0 : if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
[ # # ][ # # ]
[ # # ]
75 [ # # ][ # # ]: 0 : auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(), MiniMinerMempoolEntry(txiter));
[ # # ][ # # ]
[ # # ]
76 [ # # ][ # # ]: 0 : m_entries.push_back(mapiter);
77 : 0 : } else {
78 [ # # ][ # # ]: 0 : auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
[ # # ][ # # ]
79 [ # # ]: 0 : 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 [ # # ]: 0 : for (const auto& outpoint : outpoints_it->second) {
83 [ # # ]: 0 : m_bump_fees.emplace(outpoint, 0);
84 : : }
85 [ # # ]: 0 : m_requested_outpoints_by_txid.erase(outpoints_it);
86 : 0 : }
87 : : }
88 : : }
89 : :
90 : : // Build the m_descendant_set_by_txid cache.
91 [ # # ]: 0 : for (const auto& txiter : cluster) {
92 [ # # ][ # # ]: 0 : 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 : 0 : std::vector<MockEntryMap::iterator> cached_descendants;
96 [ # # ]: 0 : const bool remove{m_to_be_replaced.count(txid) > 0};
97 : 0 : CTxMemPool::setEntries descendants;
98 [ # # ]: 0 : mempool.CalculateDescendants(txiter, descendants);
99 [ # # ][ # # ]: 0 : Assume(descendants.count(txiter) > 0);
100 [ # # ]: 0 : for (const auto& desc_txiter : descendants) {
101 [ # # ][ # # ]: 0 : const auto txid_desc = desc_txiter->GetTx().GetHash();
[ # # ]
102 [ # # ]: 0 : const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
103 [ # # ]: 0 : auto desc_it{m_entries_by_txid.find(txid_desc)};
104 [ # # ]: 0 : Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
105 [ # # ][ # # ]: 0 : if (remove) Assume(remove_desc);
106 : : // It's possible that remove=false but remove_desc=true.
107 [ # # ][ # # ]: 0 : if (!remove && !remove_desc) {
108 [ # # ]: 0 : cached_descendants.push_back(desc_it);
109 : 0 : }
110 : : }
111 [ # # ]: 0 : if (remove) {
112 [ # # ]: 0 : Assume(cached_descendants.empty());
113 : 0 : } else {
114 [ # # ]: 0 : m_descendant_set_by_txid.emplace(txid, cached_descendants);
115 : : }
116 : 0 : }
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 [ # # ]: 0 : Assume(m_in_block.empty());
121 [ # # ]: 0 : Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
122 [ # # ]: 0 : SanityCheck();
123 [ # # ]: 0 : }
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.
130 : : struct AncestorFeerateComparator
131 : : {
132 : : template<typename I>
133 : 0 : bool operator()(const I& a, const I& b) const {
134 : 0 : auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
135 : 0 : const CAmount ancestor_fee{e.GetModFeesWithAncestors()};
136 : 0 : const int64_t ancestor_size{e.GetSizeWithAncestors()};
137 : 0 : const CAmount tx_fee{e.GetModifiedFee()};
138 : 0 : 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 [ # # ]: 0 : return ancestor_fee * tx_size < tx_fee * ancestor_size ?
144 : 0 : CFeeRate(ancestor_fee, ancestor_size) :
145 : 0 : CFeeRate(tx_fee, tx_size);
146 : : };
147 : 0 : CFeeRate a_feerate{min_feerate(a->second)};
148 : 0 : CFeeRate b_feerate{min_feerate(b->second)};
149 [ # # ]: 0 : if (a_feerate != b_feerate) {
150 : 0 : return a_feerate > b_feerate;
151 : : }
152 : : // Use txid as tiebreaker for stable sorting
153 : 0 : return a->first < b->first;
154 : 0 : }
155 : : };
156 : :
157 : 0 : void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
158 : : {
159 : 0 : Assume(ancestors.size() >= 1);
160 : : // "Mine" all transactions in this ancestor set.
161 [ # # ]: 0 : for (auto& anc : ancestors) {
162 : 0 : Assume(m_in_block.count(anc->first) == 0);
163 : 0 : m_in_block.insert(anc->first);
164 : 0 : m_total_fees += anc->second.GetModifiedFee();
165 : 0 : m_total_vsize += anc->second.GetTxSize();
166 : 0 : auto it = m_descendant_set_by_txid.find(anc->first);
167 : : // Each entry’s descendant set includes itself
168 : 0 : Assume(it != m_descendant_set_by_txid.end());
169 [ # # ]: 0 : for (auto& descendant : it->second) {
170 : : // If these fail, we must be double-deducting.
171 : 0 : Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
172 : 0 : Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
173 : 0 : descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
174 : : }
175 : : }
176 : : // Delete these entries.
177 [ # # ]: 0 : for (const auto& anc : ancestors) {
178 : 0 : 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 : 0 : Assume(anc->second.GetModFeesWithAncestors() == 0);
182 : 0 : Assume(anc->second.GetSizeWithAncestors() == 0);
183 : 0 : auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
184 : 0 : Assume(vec_it != m_entries.end());
185 : 0 : m_entries.erase(vec_it);
186 : 0 : m_entries_by_txid.erase(anc);
187 : : }
188 : 0 : }
189 : :
190 : 0 : void MiniMiner::SanityCheck() const
191 : : {
192 : : // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
193 : 0 : Assume(m_entries.size() == m_entries_by_txid.size());
194 : 0 : 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 [ # # ]: 0 : 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 : 0 : 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 : 0 : }
203 : :
204 : 0 : void MiniMiner::BuildMockTemplate(const CFeeRate& target_feerate)
205 : : {
206 [ # # ]: 0 : while (!m_entries_by_txid.empty()) {
207 : : // Sort again, since transaction removal may change some m_entries' ancestor feerates.
208 : 0 : std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
209 : :
210 : : // Pick highest ancestor feerate entry.
211 : 0 : auto best_iter = m_entries.begin();
212 : 0 : Assume(best_iter != m_entries.end());
213 : 0 : const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
214 : 0 : const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
215 : : // Stop here. Everything that didn't "make it into the block" has bumpfee.
216 [ # # ]: 0 : if (ancestor_package_fee < target_feerate.GetFee(ancestor_package_size)) {
217 : 0 : 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 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
223 : : {
224 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
225 [ # # ]: 0 : to_process.insert(*best_iter);
226 [ # # ]: 0 : while (!to_process.empty()) {
227 : 0 : auto iter = to_process.begin();
228 [ # # ]: 0 : Assume(iter != to_process.end());
229 [ # # ]: 0 : ancestors.insert(*iter);
230 [ # # ][ # # ]: 0 : for (const auto& input : (*iter)->second.GetTx().vin) {
231 [ # # ][ # # ]: 0 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
232 [ # # ][ # # ]: 0 : if (ancestors.count(parent_it) == 0) {
233 [ # # ]: 0 : to_process.insert(parent_it);
234 : 0 : }
235 : 0 : }
236 : : }
237 [ # # ]: 0 : to_process.erase(iter);
238 : : }
239 : 0 : }
240 [ # # ]: 0 : DeleteAncestorPackage(ancestors);
241 [ # # ]: 0 : SanityCheck();
242 : 0 : }
243 [ # # ]: 0 : 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 : 0 : m_ready_to_calculate = false;
246 : 0 : }
247 : :
248 : 0 : std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
249 : : {
250 [ # # ]: 0 : if (!m_ready_to_calculate) return {};
251 : : // Build a block template until the target feerate is hit.
252 : 0 : 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 [ # # ]: 0 : for (const auto& txid : m_in_block) {
257 : : // Not all of the block transactions were necessarily requested.
258 : 0 : auto it = m_requested_outpoints_by_txid.find(txid);
259 [ # # ]: 0 : if (it != m_requested_outpoints_by_txid.end()) {
260 [ # # ]: 0 : for (const auto& outpoint : it->second) {
261 : 0 : m_bump_fees.emplace(outpoint, 0);
262 : : }
263 : 0 : m_requested_outpoints_by_txid.erase(it);
264 : 0 : }
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 [ # # ]: 0 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
312 : 0 : auto it = m_entries_by_txid.find(txid);
313 : 0 : Assume(it != m_entries_by_txid.end());
314 [ # # ]: 0 : if (it != m_entries_by_txid.end()) {
315 : 0 : Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
316 : 0 : CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
317 : 0 : CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
318 : 0 : const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
319 : 0 : Assume(bump_fee >= 0);
320 [ # # ]: 0 : for (const auto& outpoint : outpoints) {
321 : 0 : m_bump_fees.emplace(outpoint, bump_fee);
322 : : }
323 : 0 : }
324 : : }
325 : 0 : return m_bump_fees;
326 : 0 : }
327 : :
328 : 0 : std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
329 : : {
330 [ # # ]: 0 : if (!m_ready_to_calculate) return std::nullopt;
331 : : // Build a block template until the target feerate is hit.
332 : 0 : BuildMockTemplate(target_feerate);
333 : :
334 : : // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
335 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
336 : 0 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
337 [ # # ]: 0 : 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 [ # # ][ # # ]: 0 : if (m_in_block.count(txid)) continue;
[ # # ]
341 [ # # ][ # # ]: 0 : auto iter = m_entries_by_txid.find(txid);
342 [ # # ]: 0 : if (iter == m_entries_by_txid.end()) continue;
343 [ # # ]: 0 : to_process.insert(iter);
344 [ # # ]: 0 : ancestors.insert(iter);
345 : : }
346 : :
347 : 0 : std::set<uint256> has_been_processed;
348 [ # # ]: 0 : while (!to_process.empty()) {
349 : 0 : auto iter = to_process.begin();
350 [ # # ]: 0 : const CTransaction& tx = (*iter)->second.GetTx();
351 [ # # ]: 0 : for (const auto& input : tx.vin) {
352 [ # # ][ # # ]: 0 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
353 [ # # ][ # # ]: 0 : if (!has_been_processed.count(input.prevout.hash)) {
354 [ # # ]: 0 : to_process.insert(parent_it);
355 : 0 : }
356 [ # # ]: 0 : ancestors.insert(parent_it);
357 : 0 : }
358 : : }
359 [ # # ][ # # ]: 0 : has_been_processed.insert(tx.GetHash());
360 [ # # ]: 0 : to_process.erase(iter);
361 : : }
362 [ # # ]: 0 : const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
363 : 0 : [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
364 [ # # ]: 0 : const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
365 : 0 : [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
366 [ # # ]: 0 : return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
367 : 0 : }
368 : : } // namespace node
|
