251        m_unique_rounded_input_scores -= it->GetLatencyScore() - 1;
252        m_unique_orphan_usage -= it->GetMemUsage();
253
254        // Remove references in m_outpoint_to_orphan_wtxids
255        const auto& wtxid{it->m_tx->GetWitnessHash()};
256        for (const auto& input : it->m_tx->vin) {
257            auto it_prev = m_outpoint_to_orphan_wtxids.find(input.prevout);
258            if (it_prev != m_outpoint_to_orphan_wtxids.end()) {
259                it_prev->second.erase(wtxid);
260                // Clean up keys if they point to an empty set.
261                if (it_prev->second.empty()) {
262                    m_outpoint_to_orphan_wtxids.erase(it_prev);
263                }
264            }
265        }
266    }
267
268    // If this was the (unique) reconsiderable announcement for its wtxid, then the wtxid won't
269    // have any reconsiderable announcements left after erasing.
270    if (it->m_reconsider) m_reconsiderable_wtxids.erase(it->m_tx->GetWitnessHash());
271
272    m_orphans.get<Tag>().erase(it);
273}
274
275bool TxOrphanageImpl::IsUnique(Iter<ByWtxid> it) const
276{
277    // Iterators ByWtxid are sorted by wtxid, so check if neighboring elements have the same wtxid.
278    auto& index = m_orphans.get<ByWtxid>();
279    if (it == index.end()) return false;
280    if (std::next(it) != index.end() && std::next(it)->m_tx->GetWitnessHash() == it->m_tx->GetWitnessHash()) return false;
281    if (it != index.begin() && std::prev(it)->m_tx->GetWitnessHash() == it->m_tx->GetWitnessHash()) return false;
282    return true;
283}
284
285TxOrphanage::Usage TxOrphanageImpl::UsageByPeer(NodeId peer) const
286{
287    auto it = m_peer_orphanage_info.find(peer);
288    return it == m_peer_orphanage_info.end() ? 0 : it->second.m_total_usage;
289}
290
291TxOrphanage::Count TxOrphanageImpl::CountAnnouncements() const { return m_orphans.size(); }
292
293TxOrphanage::Usage TxOrphanageImpl::TotalOrphanUsage() const { return m_unique_orphan_usage; }
294
295TxOrphanage::Count TxOrphanageImpl::CountUniqueOrphans() const { return m_unique_orphans; }
296
297TxOrphanage::Count TxOrphanageImpl::AnnouncementsFromPeer(NodeId peer) const {
298    auto it = m_peer_orphanage_info.find(peer);
299    return it == m_peer_orphanage_info.end() ? 0 : it->second.m_count_announcements;
300}
301
302TxOrphanage::Count TxOrphanageImpl::LatencyScoreFromPeer(NodeId peer) const {
303    auto it = m_peer_orphanage_info.find(peer);
304    return it == m_peer_orphanage_info.end() ? 0 : it->second.m_total_latency_score;
305}
306
307bool TxOrphanageImpl::AddTx(const CTransactionRef& tx, NodeId peer)
308{
309    const auto& wtxid{tx->GetWitnessHash()};
310    const auto& txid{tx->GetHash()};
311
312    // Ignore transactions above max standard size to avoid a send-big-orphans memory exhaustion attack.
313    TxOrphanage::Usage sz = GetTransactionWeight(*tx);
314    if (sz > MAX_STANDARD_TX_WEIGHT) {
315        LogDebug(BCLog::TXPACKAGES, "ignoring large orphan tx (size: %u, txid: %s, wtxid: %s)\n", sz, txid.ToString(), wtxid.ToString());
316        return false;
317    }
318
319    // We will return false if the tx already exists under a different peer.
320    const bool brand_new{!HaveTx(wtxid)};
321
322    auto [iter, inserted] = m_orphans.get<ByWtxid>().emplace(tx, peer, m_current_sequence);
323    // If the announcement (same wtxid, same peer) already exists, emplacement fails. Return false.
324    if (!inserted) return false;
325
326    ++m_current_sequence;
327    auto& peer_info = m_peer_orphanage_info.try_emplace(peer).first->second;
328    peer_info.Add(*iter);
329
330    // Add links in m_outpoint_to_orphan_wtxids
331    if (brand_new) {
332        for (const auto& input : tx->vin) {
333            auto& wtxids_for_prevout = m_outpoint_to_orphan_wtxids.try_emplace(input.prevout).first->second;
334            wtxids_for_prevout.emplace(wtxid);
335        }
336
337        m_unique_orphans += 1;
338        m_unique_orphan_usage += iter->GetMemUsage();
339        m_unique_rounded_input_scores += iter->GetLatencyScore() - 1;
340
341        LogDebug(BCLog::TXPACKAGES, "stored orphan tx %s (wtxid=%s), weight: %u (mapsz %u outsz %u)\n",
342                    txid.ToString(), wtxid.ToString(), sz, m_orphans.size(), m_outpoint_to_orphan_wtxids.size());
343        Assume(IsUnique(iter));
344    } else {
345        LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s (wtxid=%s)\n",
346                    peer, txid.ToString(), wtxid.ToString());
347        Assume(!IsUnique(iter));
348    }
349
350    // DoS prevention: do not allow m_orphanage to grow unbounded (see CVE-2012-3789)
351    LimitOrphans();
352    return brand_new;
353}
354
355bool TxOrphanageImpl::AddAnnouncer(const Wtxid& wtxid, NodeId peer)
356{
357    auto& index_by_wtxid = m_orphans.get<ByWtxid>();
358    auto it = index_by_wtxid.lower_bound(ByWtxidView{wtxid, MIN_PEER});
359
360    // Do nothing if this transaction isn't already present. We can't create an entry if we don't
361    // have the tx data.
362    if (it == index_by_wtxid.end()) return false;
363    if (it->m_tx->GetWitnessHash() != wtxid) return false;
364
365    // Add another announcement, copying the CTransactionRef from one that already exists.
366    const auto& ptx = it->m_tx;
367    auto [iter, inserted] = index_by_wtxid.emplace(ptx, peer, m_current_sequence);
368    // If the announcement (same wtxid, same peer) already exists, emplacement fails. Return false.
369    if (!inserted) return false;
370
371    ++m_current_sequence;
372    auto& peer_info = m_peer_orphanage_info.try_emplace(peer).first->second;
373    peer_info.Add(*iter);
374
375    const auto& txid = ptx->GetHash();
376    LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s (wtxid=%s)\n",
377                peer, txid.ToString(), wtxid.ToString());
378
379    Assume(!IsUnique(iter));
380
381    // DoS prevention: do not allow m_orphanage to grow unbounded (see CVE-2012-3789)
382    LimitOrphans();
383    return true;
384}
385
386bool TxOrphanageImpl::EraseTxInternal(const Wtxid& wtxid)
387{
388    auto& index_by_wtxid = m_orphans.get<ByWtxid>();
389
390    auto it = index_by_wtxid.lower_bound(ByWtxidView{wtxid, MIN_PEER});
391    if (it == index_by_wtxid.end() || it->m_tx->GetWitnessHash() != wtxid) return false;
392
393    auto it_end = index_by_wtxid.upper_bound(ByWtxidView{wtxid, MAX_PEER});
394    unsigned int num_ann{0};
395    const auto txid = it->m_tx->GetHash();
396    while (it != it_end) {
397        Assume(it->m_tx->GetWitnessHash() == wtxid);
398        Erase<ByWtxid>(it++);
399        num_ann += 1;
400    }
401    LogDebug(BCLog::TXPACKAGES, "removed orphan tx %s (wtxid=%s) (%u announcements)\n", txid.ToString(), wtxid.ToString(), num_ann);
402
403    return true;
404}
405
406bool TxOrphanageImpl::EraseTx(const Wtxid& wtxid)
407{
408    const auto ret = EraseTxInternal(wtxid);
409
410    // Deletions can cause the orphanage's MaxGlobalUsage to decrease, so we may need to trim here.
411    LimitOrphans();
412
413    return ret;
414}
415
416/** Erase all entries by this peer. */
417void TxOrphanageImpl::EraseForPeer(NodeId peer)
418{
419    auto& index_by_peer = m_orphans.get<ByPeer>();
420    auto it = index_by_peer.lower_bound(ByPeerView{peer, false, 0});
421    if (it == index_by_peer.end() || it->m_announcer != peer) return;
422
423    unsigned int num_ann{0};
424    while (it != index_by_peer.end() && it->m_announcer == peer) {
425        // Delete item, cleaning up m_outpoint_to_orphan_wtxids iff this entry is unique by wtxid.
426        Erase<ByPeer>(it++);
427        num_ann += 1;
428    }
429    Assume(!m_peer_orphanage_info.contains(peer));
430
431    if (num_ann > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", num_ann, peer);
432
433    // Deletions can cause the orphanage's MaxGlobalUsage to decrease, so we may need to trim here.
434    LimitOrphans();
435}
436
437/** If the data structure needs trimming, evicts announcements by selecting the DoSiest peer and evicting its oldest
438 * announcement (sorting non-reconsiderable orphans first, to give reconsiderable orphans a greater chance of being
439 * processed). Does nothing if no global limits are exceeded.  This eviction strategy effectively "reserves" an
440 * amount of announcements and space for each peer. The reserved amount is protected from eviction even if there
441 * are peers spamming the orphanage.
442 */
443void TxOrphanageImpl::LimitOrphans()
444{
445    if (!NeedsTrim()) return;
446
447    const auto original_unique_txns{CountUniqueOrphans()};
448
449    // Even though it's possible for MaxPeerLatencyScore to increase within this call to LimitOrphans
450    // (e.g. if a peer's orphans are removed entirely, changing the number of peers), use consistent limits throughout.
451    const auto max_lat{MaxPeerLatencyScore()};
452    const auto max_mem{ReservedPeerUsage()};
453
454    // We have exceeded the global limit(s). Now, identify who is using too much and evict their orphans.
455    // Create a heap of pairs (NodeId, DoS score), sorted by descending DoS score.
456    std::vector<std::pair<NodeId, FeeFrac>> heap_peer_dos;
457    heap_peer_dos.reserve(m_peer_orphanage_info.size());
458    for (const auto& [nodeid, entry] : m_peer_orphanage_info) {
459        // Performance optimization: only consider peers with a DoS score > 1.
460        const auto dos_score = entry.GetDosScore(max_lat, max_mem);
461        if (ByRatio{dos_score} > ByRatio{FeeFrac{1, 1}}) {
462            heap_peer_dos.emplace_back(nodeid, dos_score);
463        }
464    }
465    static constexpr auto compare_score = [](const auto& left, const auto& right) {
466        if (left.second != right.second) {
467            // Note: if ratios are the same, this tiebreaks by denominator. In practice, since the
468            // latency denominator (number of announcements and inputs) is always lower, this means
469            // that a peer with only high latency scores will be targeted before a peer using a lot
470            // of memory, even if they have the same ratios.
471            return ByRatioNegSize{left.second} < ByRatioNegSize{right.second};
472        }
473        // Tiebreak by considering the more recent peer (higher NodeId) to be worse.
474        return left.first < right.first;
475    };
476    std::make_heap(heap_peer_dos.begin(), heap_peer_dos.end(), compare_score);
477
478    unsigned int num_erased{0};
479    // This outer loop finds the peer with the highest DoS score, which is a fraction of memory and latency scores
480    // over the respective allowances. We continue until the orphanage is within global limits. That means some peers
481    // might still have a DoS score > 1 at the end.
482    do {
483        Assume(!heap_peer_dos.empty());
484        // This is a max-heap, so the worst peer is at the front. pop_heap()
485        // moves it to the back, and the next worst peer is moved to the front.
486        std::pop_heap(heap_peer_dos.begin(), heap_peer_dos.end(), compare_score);
487        const auto [worst_peer, dos_score] = std::move(heap_peer_dos.back());
488        heap_peer_dos.pop_back();
489
490        // If needs trim, then at least one peer has a DoS score higher than 1.
491        Assume(ByRatio{dos_score} > ByRatio{FeeFrac(1, 1)});
492
493        auto it_worst_peer = m_peer_orphanage_info.find(worst_peer);
494
495        // This inner loop trims until this peer is no longer the DoSiest one or has a score within 1. The score 1 is
496        // just a conservative fallback: once the last peer goes below ratio 1, NeedsTrim() will return false anyway.
497        // We evict the oldest announcement(s) from this peer, sorting non-reconsiderable before reconsiderable.
498        // The number of inner loop iterations is bounded by the total number of announcements.
499        const auto& dos_threshold = heap_peer_dos.empty() ? FeeFrac{1, 1} : heap_peer_dos.front().second;
500        auto it_ann = m_orphans.get<ByPeer>().lower_bound(ByPeerView{worst_peer, false, 0});