mini_miner.cpp
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 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 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 bool operator()(const I& a, const I& b) const { 186 auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate { 187 const CAmount ancestor_fee{e.GetModFeesWithAncestors()}; 188 const int64_t ancestor_size{e.GetSizeWithAncestors()}; 189 const CAmount tx_fee{e.GetModifiedFee()}; 190 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 return ancestor_fee * tx_size < tx_fee * ancestor_size ? 196 CFeeRate(ancestor_fee, ancestor_size) : 197 CFeeRate(tx_fee, tx_size); 198 }; 199 CFeeRate a_feerate{min_feerate(a->second)}; 200 CFeeRate b_feerate{min_feerate(b->second)}; 201 if (a_feerate != b_feerate) { 202 return a_feerate > b_feerate; 203 } 204 // Use txid as tiebreaker for stable sorting 205 return a->first < b->first; 206 } 207 }; 208 209 void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors) 210 { 211 Assume(ancestors.size() >= 1); 212 // "Mine" all transactions in this ancestor set. 213 for (auto& anc : ancestors) { 214 Assume(m_in_block.count(anc->first) == 0); 215 m_in_block.insert(anc->first); 216 m_total_fees += anc->second.GetModifiedFee(); 217 m_total_vsize += anc->second.GetTxSize(); 218 auto it = m_descendant_set_by_txid.find(anc->first); 219 // Each entry’s descendant set includes itself 220 Assume(it != m_descendant_set_by_txid.end()); 221 for (auto& descendant : it->second) { 222 // If these fail, we must be double-deducting. 223 Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee()); 224 Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize()); 225 descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee()); 226 } 227 } 228 // Delete these entries. 229 for (const auto& anc : ancestors) { 230 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 Assume(anc->second.GetModFeesWithAncestors() == 0); 234 Assume(anc->second.GetSizeWithAncestors() == 0); 235 auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc); 236 Assume(vec_it != m_entries.end()); 237 m_entries.erase(vec_it); 238 m_entries_by_txid.erase(anc); 239 } 240 } 241 242 void MiniMiner::SanityCheck() const 243 { 244 // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size 245 Assume(m_entries.size() == m_entries_by_txid.size()); 246 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 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 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 } 255 256 void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate) 257 { 258 const auto num_txns{m_entries_by_txid.size()}; 259 uint32_t sequence_num{0}; 260 while (!m_entries_by_txid.empty()) { 261 // Sort again, since transaction removal may change some m_entries' ancestor feerates. 262 std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator()); 263 264 // Pick highest ancestor feerate entry. 265 auto best_iter = m_entries.begin(); 266 Assume(best_iter != m_entries.end()); 267 const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors(); 268 const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors(); 269 // Stop here. Everything that didn't "make it into the block" has bumpfee. 270 if (target_feerate.has_value() && 271 ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) { 272 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 std::set<MockEntryMap::iterator, IteratorComparator> ancestors; 278 { 279 std::set<MockEntryMap::iterator, IteratorComparator> to_process; 280 to_process.insert(*best_iter); 281 while (!to_process.empty()) { 282 auto iter = to_process.begin(); 283 Assume(iter != to_process.end()); 284 ancestors.insert(*iter); 285 for (const auto& input : (*iter)->second.GetTx().vin) { 286 if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) { 287 if (ancestors.count(parent_it) == 0) { 288 to_process.insert(parent_it); 289 } 290 } 291 } 292 to_process.erase(iter); 293 } 294 } 295 // Track the order in which transactions were selected. 296 for (const auto& ancestor : ancestors) { 297 m_inclusion_order.emplace(Txid::FromUint256(ancestor->first), sequence_num); 298 } 299 DeleteAncestorPackage(ancestors); 300 SanityCheck(); 301 ++sequence_num; 302 } 303 if (!target_feerate.has_value()) { 304 Assume(m_in_block.size() == num_txns); 305 } else { 306 Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize)); 307 } 308 Assume(m_in_block.empty() || sequence_num > 0); 309 Assume(m_in_block.size() == m_inclusion_order.size()); 310 // Do not try to continue building the block template with a different feerate. 311 m_ready_to_calculate = false; 312 } 313 314 315 std::map<Txid, uint32_t> MiniMiner::Linearize() 316 { 317 BuildMockTemplate(std::nullopt); 318 return m_inclusion_order; 319 } 320 321 std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate) 322 { 323 if (!m_ready_to_calculate) return {}; 324 // Build a block template until the target feerate is hit. 325 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 for (const auto& txid : m_in_block) { 330 // Not all of the block transactions were necessarily requested. 331 auto it = m_requested_outpoints_by_txid.find(txid); 332 if (it != m_requested_outpoints_by_txid.end()) { 333 for (const auto& outpoint : it->second) { 334 m_bump_fees.emplace(outpoint, 0); 335 } 336 m_requested_outpoints_by_txid.erase(it); 337 } 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 for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) { 385 auto it = m_entries_by_txid.find(txid); 386 Assume(it != m_entries_by_txid.end()); 387 if (it != m_entries_by_txid.end()) { 388 Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors())); 389 CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors(); 390 CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee(); 391 const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)}; 392 Assume(bump_fee >= 0); 393 for (const auto& outpoint : outpoints) { 394 m_bump_fees.emplace(outpoint, bump_fee); 395 } 396 } 397 } 398 return m_bump_fees; 399 } 400 401 std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate) 402 { 403 if (!m_ready_to_calculate) return std::nullopt; 404 // Build a block template until the target feerate is hit. 405 BuildMockTemplate(target_feerate); 406 407 // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives 408 std::set<MockEntryMap::iterator, IteratorComparator> ancestors; 409 std::set<MockEntryMap::iterator, IteratorComparator> to_process; 410 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 if (m_in_block.count(txid)) continue; 414 auto iter = m_entries_by_txid.find(txid); 415 if (iter == m_entries_by_txid.end()) continue; 416 to_process.insert(iter); 417 ancestors.insert(iter); 418 } 419 420 std::set<uint256> has_been_processed; 421 while (!to_process.empty()) { 422 auto iter = to_process.begin(); 423 const CTransaction& tx = (*iter)->second.GetTx(); 424 for (const auto& input : tx.vin) { 425 if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) { 426 if (!has_been_processed.count(input.prevout.hash)) { 427 to_process.insert(parent_it); 428 } 429 ancestors.insert(parent_it); 430 } 431 } 432 has_been_processed.insert(tx.GetHash()); 433 to_process.erase(iter); 434 } 435 const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0}, 436 [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();}); 437 const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0}, 438 [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();}); 439 return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee; 440 } 441 } // namespace node