1 // Copyright (c) 2023 The Limenka 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 MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
24 {
25 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 for (const auto& outpoint : outpoints) {
30 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 m_bump_fees.emplace(outpoint, 0);
35 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 m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
41 42 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 CTxMemPool::setEntries descendants;
53 mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
54 for (const auto& desc_txiter : descendants) {
55 m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
56 }
57 }
58 }
59 60 // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
61 if (m_requested_outpoints_by_txid.empty()) return;
62 63 // Calculate the cluster and construct the entry map.
64 std::vector<uint256> txids_needed;
65 txids_needed.reserve(m_requested_outpoints_by_txid.size());
66 for (const auto& [txid, _]: m_requested_outpoints_by_txid) {
67 txids_needed.push_back(txid);
68 }
69 const auto cluster = mempool.GatherClusters(txids_needed);
70 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 m_ready_to_calculate = false;
74 return;
75 }
76 77 // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
78 for (const auto& txiter : cluster) {
79 if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
80 auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
81 MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
82 /*vsize_self=*/txiter->GetTxSize(),
83 /*vsize_ancestor=*/txiter->GetSizeWithAncestors(),
84 /*fee_self=*/txiter->GetModifiedFee(),
85 /*fee_ancestor=*/txiter->GetModFeesWithAncestors()});
86 m_entries.push_back(mapiter);
87 } else {
88 auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
89 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 for (const auto& outpoint : outpoints_it->second) {
93 m_bump_fees.emplace(outpoint, 0);
94 }
95 m_requested_outpoints_by_txid.erase(outpoints_it);
96 }
97 }
98 }
99 100 // Build the m_descendant_set_by_txid cache.
101 for (const auto& txiter : cluster) {
102 const auto& txid = txiter->GetTx().GetHash();
103 // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
104 // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
105 std::vector<MockEntryMap::iterator> cached_descendants;
106 const bool remove{m_to_be_replaced.count(txid) > 0};
107 CTxMemPool::setEntries descendants;
108 mempool.CalculateDescendants(txiter, descendants);
109 Assume(descendants.count(txiter) > 0);
110 for (const auto& desc_txiter : descendants) {
111 const auto txid_desc = desc_txiter->GetTx().GetHash();
112 const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
113 auto desc_it{m_entries_by_txid.find(txid_desc)};
114 Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
115 if (remove) Assume(remove_desc);
116 // It's possible that remove=false but remove_desc=true.
117 if (!remove && !remove_desc) {
118 cached_descendants.push_back(desc_it);
119 }
120 }
121 if (remove) {
122 Assume(cached_descendants.empty());
123 } else {
124 m_descendant_set_by_txid.emplace(txid, cached_descendants);
125 }
126 }
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 Assume(m_in_block.empty());
131 Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
132 SanityCheck();
133 }
134 135 MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
136 const std::map<Txid, std::set<Txid>>& descendant_caches)
137 {
138 for (const auto& entry : manual_entries) {
139 const auto& txid = entry.GetTx().GetHash();
140 // We need to know the descendant set of every transaction.
141 if (!Assume(descendant_caches.count(txid) > 0)) {
142 m_ready_to_calculate = false;
143 return;
144 }
145 // Just forward these args onto MiniMinerMempoolEntry
146 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 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 for (const auto& [txid, desc_txids] : descendant_caches) {
152 // Descendant cache should include at least the tx itself.
153 if (!Assume(!desc_txids.empty())) {
154 m_ready_to_calculate = false;
155 return;
156 }
157 std::vector<MockEntryMap::iterator> descendants;
158 for (const auto& desc_txid : desc_txids) {
159 auto desc_it{m_entries_by_txid.find(desc_txid)};
160 // Descendants should only include transactions with corresponding entries.
161 if (!Assume(desc_it != m_entries_by_txid.end())) {
162 m_ready_to_calculate = false;
163 return;
164 } else {
165 descendants.emplace_back(desc_it);
166 }
167 }
168 m_descendant_set_by_txid.emplace(txid, descendants);
169 }
170 Assume(m_to_be_replaced.empty());
171 Assume(m_requested_outpoints_by_txid.empty());
172 Assume(m_bump_fees.empty());
173 Assume(m_inclusion_order.empty());
174 SanityCheck();
175 }
176 177 // Compare by min(ancestor feerate, individual feerate), then txid
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 bool operator()(const I& a, const I& b) const {
186 auto min_feerate = [](const MiniMinerMempoolEntry& e) -> FeeFrac {
187 FeeFrac self_feerate(e.GetModifiedFee(), e.GetTxSize());
188 FeeFrac ancestor_feerate(e.GetModFeesWithAncestors(), e.GetSizeWithAncestors());
189 return std::min(ancestor_feerate, self_feerate);
190 };
191 FeeFrac a_feerate{min_feerate(a->second)};
192 FeeFrac b_feerate{min_feerate(b->second)};
193 if (a_feerate != b_feerate) {
194 return a_feerate > b_feerate;
195 }
196 // Use txid as tiebreaker for stable sorting
197 return a->first < b->first;
198 }
199 };
200 201 void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
202 {
203 Assume(ancestors.size() >= 1);
204 // "Mine" all transactions in this ancestor set.
205 for (auto& anc : ancestors) {
206 Assume(m_in_block.count(anc->first) == 0);
207 m_in_block.insert(anc->first);
208 m_total_fees += anc->second.GetModifiedFee();
209 m_total_vsize += anc->second.GetTxSize();
210 auto it = m_descendant_set_by_txid.find(anc->first);
211 // Each entry’s descendant set includes itself
212 Assume(it != m_descendant_set_by_txid.end());
213 for (auto& descendant : it->second) {
214 // If this fails, we must be double-deducting. Don't check fees because negative is possible.
215 Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
216 descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
217 }
218 }
219 // Delete these entries.
220 for (const auto& anc : ancestors) {
221 m_descendant_set_by_txid.erase(anc->first);
222 // The above loop should have deducted each ancestor's size and fees from each of their
223 // respective descendants exactly once.
224 Assume(anc->second.GetModFeesWithAncestors() == 0);
225 Assume(anc->second.GetSizeWithAncestors() == 0);
226 auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
227 Assume(vec_it != m_entries.end());
228 m_entries.erase(vec_it);
229 m_entries_by_txid.erase(anc);
230 }
231 }
232 233 void MiniMiner::SanityCheck() const
234 {
235 // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
236 Assume(m_entries.size() == m_entries_by_txid.size());
237 Assume(m_entries.size() == m_descendant_set_by_txid.size());
238 // Cached ancestor values should be at least as large as the transaction's own size
239 Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
240 return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize();}));
241 // None of the entries should be to-be-replaced transactions
242 Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
243 [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
244 }
245 246 void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
247 {
248 const auto num_txns{m_entries_by_txid.size()};
249 uint32_t sequence_num{0};
250 while (!m_entries_by_txid.empty()) {
251 // Sort again, since transaction removal may change some m_entries' ancestor feerates.
252 std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
253 254 // Pick highest ancestor feerate entry.
255 auto best_iter = m_entries.begin();
256 Assume(best_iter != m_entries.end());
257 const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
258 const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
259 // Stop here. Everything that didn't "make it into the block" has bumpfee.
260 if (target_feerate.has_value() &&
261 ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) {
262 break;
263 }
264 265 // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
266 // change at every iteration, so this is more efficient than maintaining a cache.
267 std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
268 {
269 std::set<MockEntryMap::iterator, IteratorComparator> to_process;
270 to_process.insert(*best_iter);
271 while (!to_process.empty()) {
272 auto iter = to_process.begin();
273 Assume(iter != to_process.end());
274 ancestors.insert(*iter);
275 for (const auto& input : (*iter)->second.GetTx().vin) {
276 if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
277 if (ancestors.count(parent_it) == 0) {
278 to_process.insert(parent_it);
279 }
280 }
281 }
282 to_process.erase(iter);
283 }
284 }
285 // Track the order in which transactions were selected.
286 for (const auto& ancestor : ancestors) {
287 m_inclusion_order.emplace(Txid::FromUint256(ancestor->first), sequence_num);
288 }
289 DeleteAncestorPackage(ancestors);
290 SanityCheck();
291 ++sequence_num;
292 }
293 if (!target_feerate.has_value()) {
294 Assume(m_in_block.size() == num_txns);
295 } else {
296 Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize));
297 }
298 Assume(m_in_block.empty() || sequence_num > 0);
299 Assume(m_in_block.size() == m_inclusion_order.size());
300 // Do not try to continue building the block template with a different feerate.
301 m_ready_to_calculate = false;
302 }
303 304 305 std::map<Txid, uint32_t> MiniMiner::Linearize()
306 {
307 BuildMockTemplate(std::nullopt);
308 return m_inclusion_order;
309 }
310 311 std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
312 {
313 if (!m_ready_to_calculate) return {};
314 // Build a block template until the target feerate is hit.
315 BuildMockTemplate(target_feerate);
316 317 // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
318 // ancestor package with at least the target feerate and don't need to be bumped.
319 for (const auto& txid : m_in_block) {
320 // Not all of the block transactions were necessarily requested.
321 auto it = m_requested_outpoints_by_txid.find(txid);
322 if (it != m_requested_outpoints_by_txid.end()) {
323 for (const auto& outpoint : it->second) {
324 m_bump_fees.emplace(outpoint, 0);
325 }
326 m_requested_outpoints_by_txid.erase(it);
327 }
328 }
329 330 // A transactions and its ancestors will only be picked into a block when
331 // both the ancestor set feerate and the individual feerate meet the target
332 // feerate.
333 //
334 // We had to convince ourselves that after running the mini miner and
335 // picking all eligible transactions into our MockBlockTemplate, there
336 // could still be transactions remaining that have a lower individual
337 // feerate than their ancestor feerate. So here is an example:
338 //
339 // ┌─────────────────┐
340 // │ │
341 // │ Grandparent │
342 // │ 1700 vB │
343 // │ 1700 sats │ Target feerate: 10 s/vB
344 // │ 1 s/vB │ GP Ancestor Set Feerate (ASFR): 1 s/vB
345 // │ │ P1_ASFR: 9.84 s/vB
346 // └──────▲───▲──────┘ P2_ASFR: 2.47 s/vB
347 // │ │ C_ASFR: 10.27 s/vB
348 // ┌───────────────┐ │ │ ┌──────────────┐
349 // │ ├────┘ └────┤ │ ⇒ C_FR < TFR < C_ASFR
350 // │ Parent 1 │ │ Parent 2 │
351 // │ 200 vB │ │ 200 vB │
352 // │ 17000 sats │ │ 3000 sats │
353 // │ 85 s/vB │ │ 15 s/vB │
354 // │ │ │ │
355 // └───────────▲───┘ └───▲──────────┘
356 // │ │
357 // │ ┌───────────┐ │
358 // └────┤ ├────┘
359 // │ Child │
360 // │ 100 vB │
361 // │ 900 sats │
362 // │ 9 s/vB │
363 // │ │
364 // └───────────┘
365 //
366 // We therefore calculate both the bump fee that is necessary to elevate
367 // the individual transaction to the target feerate:
368 // target_feerate × tx_size - tx_fees
369 // and the bump fee that is necessary to bump the entire ancestor set to
370 // the target feerate:
371 // target_feerate × ancestor_set_size - ancestor_set_fees
372 // By picking the maximum from the two, we ensure that a transaction meets
373 // both criteria.
374 for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
375 auto it = m_entries_by_txid.find(txid);
376 Assume(it != m_entries_by_txid.end());
377 if (it != m_entries_by_txid.end()) {
378 Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
379 CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
380 CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
381 const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
382 Assume(bump_fee >= 0);
383 for (const auto& outpoint : outpoints) {
384 m_bump_fees.emplace(outpoint, bump_fee);
385 }
386 }
387 }
388 return m_bump_fees;
389 }
390 391 std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
392 {
393 if (!m_ready_to_calculate) return std::nullopt;
394 // Build a block template until the target feerate is hit.
395 BuildMockTemplate(target_feerate);
396 397 // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
398 std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
399 std::set<MockEntryMap::iterator, IteratorComparator> to_process;
400 for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
401 // Skip any ancestors that already have a miner score higher than the target feerate
402 // (already "made it" into the block)
403 if (m_in_block.count(txid)) continue;
404 auto iter = m_entries_by_txid.find(txid);
405 if (iter == m_entries_by_txid.end()) continue;
406 to_process.insert(iter);
407 ancestors.insert(iter);
408 }
409 410 std::set<uint256> has_been_processed;
411 while (!to_process.empty()) {
412 auto iter = to_process.begin();
413 const CTransaction& tx = (*iter)->second.GetTx();
414 for (const auto& input : tx.vin) {
415 if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
416 if (!has_been_processed.count(input.prevout.hash)) {
417 to_process.insert(parent_it);
418 }
419 ancestors.insert(parent_it);
420 }
421 }
422 has_been_processed.insert(tx.GetHash());
423 to_process.erase(iter);
424 }
425 const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
426 [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
427 const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
428 [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
429 return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
430 }
431 } // namespace node
432