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 2 : 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
|
