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