p2p: improve TxOrphanage denial of service bounds #31829

35@@ -36,9 +36,10 @@ bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
36         return false;
37     }
38 

42+    unsigned int m_reserved_weight_per_peer{DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER};
43+
44+    /** The maximum number of announcements across all peers, representing a computational upper bound,
45+     * i.e. the maximum number of evictions we might do at a time. There is no per-peer announcement
46+     * limit until the global limit is reached. Also, this limit is constant regardless of how many
47+     * peers we have: if we only have 1 peer, this is the number of orphans they may provide. As

43+
44+    /** The maximum number of announcements across all peers, representing a computational upper bound,
45+     * i.e. the maximum number of evictions we might do at a time. There is no per-peer announcement
46+     * limit until the global limit is reached. Also, this limit is constant regardless of how many
47+     * peers we have: if we only have 1 peer, this is the number of orphans they may provide. As
48+     * more peers are added, each peer's allocation is reduced. */

136@@ -111,7 +137,6 @@ class TxOrphanage {
137 
138 protected:
139     struct OrphanTx : public OrphanTxBase {

233+
234+    unsigned int GetGlobalMaxUsage() const {
235+        return std::max<unsigned int>(m_peer_orphanage_info.size() * m_reserved_weight_per_peer, 1);
236+    }
237+
238+    unsigned int GetPerPeerMaxAnnouncements() const {

182+            FeeFrac cpu_score(m_iter_list.size(), peer_max_ann);
183+            FeeFrac mem_score(m_total_usage, peer_max_mem);
184+            return std::max<FeeFrac>(cpu_score, mem_score);
185+        }
186     };
187     std::map<NodeId, PeerOrphanInfo> m_peer_orphanage_info;

108-        it_last->second.list_pos = old_pos;
109+        // Find this orphan iter's position in the list, and delete it.
110+        auto& orphan_list = peer_it->second.m_iter_list;
111+        size_t old_pos = std::distance(orphan_list.begin(), std::find(orphan_list.begin(), orphan_list.end(), it));
112+
113+        if (!Assume(old_pos < orphan_list.size())) continue;

200-        ++nEvicted;
201+        if (!Assume(!peer_it_heap.empty())) break;
202+        // Find the peer with the highest DoS score, which is a fraction of {usage, announcements} used
203+        // over the allowance. This metric causes us to naturally select peers who have exceeded
204+        // their limits (i.e. a DoS score > 1) before peers who haven't. We may choose the same peer
205+        // change since the last iteration of this loop.

242+        auto ptx = MakeTransactionSpending(/*outpoints=*/{}, det_rand);
243+        orphanage.AddTx(ptx, dos_peer);
244+    }
245+    peer_usages.emplace_back(orphanage.UsageByPeer(dos_peer));
246+
247+    // Force an eviction. Note that no limiting has happened yet at this point. LimitOrphans may

250+    orphanage.LimitOrphans(prev_count - 1, det_rand);
251+    BOOST_CHECK(orphanage.Size() <= prev_count - 1);
252+
253+    // The DoS peer's orphans have been evicted, nobody else's have.
254+    for (NodeId peer{0}; peer <= dos_peer; ++peer) {
255+        BOOST_CHECK_EQUAL(peer == dos_peer, peer_usages.at(peer) != orphanage.UsageByPeer(peer));

467+        peer_normal.wait_for_getdata([parent_txid_int])
468+
469+        self.log.info("Send another round of very large orphans from a DoSy peer")
470+        for large_orphan in large_orphans[60:]:
471+            peer_doser.send_and_ping(msg_tx(large_orphan))
472+

44+}
45+
46+static void OrphanageEvictionMany(benchmark::Bench& bench)
47+{
48+    NodeId NUM_PEERS{125};
49+    unsigned int NUM_TRANSACTIONS(DEFAULT_MAX_ORPHAN_ANNOUNCEMENTS / NUM_PEERS);

275+                // items that are no longer in the orphanage. We should only do this once per peer
276+                // per call to AddChildrenToWorkSet, so keep track of which peers we have trimmed.
277+                // We also never need to do it more than once since evictions don't happen in this
278+                // function.
279+                if (orphan_work_set.size() + 1 > MAX_ORPHAN_WORK_QUEUE && !peers_workset_trimmed.contains(announcer)) {
280+                    std::erase_if(orphan_work_set, [&](const auto& wtxid) { return m_orphans.contains(wtxid); });

281+                    peers_workset_trimmed.insert(announcer);
282+                }
283+
284+                // Add this tx to the work set. If the workset is full, even after trimming, don't
285+                // accept any new work items until the work queue has been flushed.
286+                if (orphan_work_set.size() < MAX_ORPHAN_WORK_QUEUE) {

139@@ -140,13 +140,12 @@ void TxOrphanage::EraseForPeer(NodeId peer)
140     if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", nErased, peer);
141 }
142 
143-void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)
144+unsigned int TxOrphanage::MaybeExpireOrphans()
145 {
146-    unsigned int nEvicted = 0;
147+    int nErased = 0;

175         ++nEvicted;
176     }
177+    return nEvicted;
178+}
179+
180+void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)

446+        # normal package request to time out.
447+        self.wait_until(lambda: len(node.getorphantxs()) == num_individual_dosers)
448+
449+        self.log.info("Send an orphan from a non-DoSy peer. Its orphan should not be evicted.")
450+        low_fee_parent = self.create_tx_below_mempoolminfee(self.wallet)
451+        high_fee_child = self.wallet.create_self_transfer(utxo_to_spend=low_fee_parent["new_utxo"], fee_rate=20*FEERATE_1SAT_VB)

495+                # runtime of this test.
496+                peer_doser_batch.send_message(msg_tx(tx))
497+
498+        self.log.info("Send an orphan from a non-DoSy peer. Its orphan should not be evicted.")
499+        low_fee_parent = self.create_tx_below_mempoolminfee(self.wallet)
500+        high_fee_child = self.wallet.create_self_transfer(utxo_to_spend=low_fee_parent["new_utxo"], fee_rate=20*FEERATE_1SAT_VB)

473+        self.log.info("Provide the orphan's parent. This 1p1c package should be successfully accepted.")
474+        peer_normal.send_and_ping(msg_tx(low_fee_parent["tx"]))
475+        assert_equal(node.getmempoolentry(orphan_tx.rehash())["ancestorcount"], 2)
476+
477+    @cleanup
478+    def test_orphanage_dos_many(self):

230+    unsigned int GetPerPeerMaxUsage() const {
231+        return m_reserved_weight_per_peer;
232+    }
233+
234+    unsigned int GetGlobalMaxUsage() const {
235+        return std::max<unsigned int>(m_peer_orphanage_info.size() * m_reserved_weight_per_peer, 1);

169@@ -165,13 +170,68 @@ unsigned int TxOrphanage::MaybeExpireOrphans()
170 
171 unsigned int TxOrphanage::MaybeTrimOrphans(unsigned int max_orphans, FastRandomContext& rng)
172 {
173+    // Exit early to avoid building the heap unnecessarily
174+    if (!NeedsTrim() && m_orphans.size() <= max_orphans) return 0;
175+
176+    std::vector<PeerMap::iterator> peer_it_heap;
177+    for (auto it = m_peer_orphanage_info.begin(); it != m_peer_orphanage_info.end(); ++it) peer_it_heap.push_back(it);
178+    peer_it_heap.reserve(m_peer_orphanage_info.size());

169@@ -165,13 +170,68 @@ unsigned int TxOrphanage::MaybeExpireOrphans()
170 
171 unsigned int TxOrphanage::MaybeTrimOrphans(unsigned int max_orphans, FastRandomContext& rng)
172 {
173+    // Exit early to avoid building the heap unnecessarily
174+    if (!NeedsTrim() && m_orphans.size() <= max_orphans) return 0;

748+            peer_doser.send_and_ping(msg_tx(large_orphan))
749+
750+        self.log.info("Provide the top ancestor. The whole package should be re-evaluated after enough time.")
751+        peer_normal.send_and_ping(msg_tx(ancestor_package[0]["tx"]))
752+
753+        self.wait_until(lambda: node.getmempoolentry(ancestor_package[-1]["txid"])["ancestorcount"] == DEFAULT_ANCESTOR_LIMIT)

60-            self.nodes[0].bumpmocktime(LONG_TIME_SKIP)
61             # Check that mempool and orphanage have been cleared
62             self.wait_until(lambda: len(self.nodes[0].getorphantxs()) == 0)
63             assert_equal(0, len(self.nodes[0].getrawmempool()))
64+
65+            self.restart_node(0, extra_args=["-persistmempool=0"])

169@@ -138,10 +170,27 @@ class TxOrphanage {
170          * m_total_orphan_size. If a peer is removed as an announcer, even if the orphan still
171          * remains in the orphanage, this number will be decremented. */
172         int64_t m_total_usage{0};
173+
174+        /** Orphan transactions in vector for quick random eviction */
175+        std::vector<OrphanMap::iterator> m_iter_list;

181+         * If the peer is using more than the allowed for either resource, its DoS score is > 1.
182+         * A peer having a DoS score > 1 does not necessarily mean that something is wrong, since we
183+         * do not trim unless the orphanage exceeds global limits, but it means that this peer will
184+         * be selected for trimming sooner. */
185+        FeeFrac GetDoSScore(unsigned int peer_max_ann, unsigned int peer_max_mem) {
186+            FeeFrac cpu_score(m_iter_list.size(), peer_max_ann);

178+
179+    // Sort peers that have the highest ratio of DoSiness first
180+    auto compare_peer = [this](PeerMap::iterator left, PeerMap::iterator right) {
181+        const auto max_ann{GetPerPeerMaxAnnouncements()};
182+        const auto max_mem{GetPerPeerMaxUsage()};
183+        return left->second.GetDoSScore(max_ann, max_mem) < right->second.GetDoSScore(max_ann, max_mem);

501+                # Don't sync with ping or wait for responses, because it dramatically increases the
502+                # runtime of this test.
503+                peer_doser_batch.send_message(msg_tx(tx))
504+
505+        # Something was evicted
506+        self.wait_until(lambda: len(node.getorphantxs()) < batch_size * num_peers)

535+            peer_doser_shared = node.add_p2p_connection(P2PInterface())
536+            for orphan in shared_orphans:
537+                peer_doser_shared.send_message(msg_tx(orphan))
538+
539+        # Something was evicted; the orphanage does not contain all DoS orphans + the 1p1c child
540+        self.wait_until(lambda: len(node.getorphantxs()) < batch_size * num_peers + len(shared_orphans) + 1)

41+
42+    // We have NUM_PEERS, of which Peer==0 is the "honest" one
43+    // who will never exceed their reserved weight of announcement
44+    // count, and should therefore never be evicted.
45+    const unsigned int NUM_PEERS = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 125);
46+    const unsigned int global_announcement_limit = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(NUM_PEERS, 1'000);

45+    const unsigned int NUM_PEERS = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 125);
46+    const unsigned int global_announcement_limit = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(NUM_PEERS, 1'000);
47+    // This must match announcement limit (or exceed) otherwise "honest" peer can be evicted
48+    const unsigned int global_tx_limit = global_announcement_limit;
49+    const unsigned int per_peer_announcements = global_announcement_limit / NUM_PEERS;
50+    const unsigned int per_peer_weight_reservation = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 4'000);

247+    // Force an eviction. Note that no limiting has happened yet at this point (we haven't called
248+    // LimitOrphans yet) so it may be oversize and LimitOrphans may evict more than 1 transaction.
249+    // All evictions will be from the dos_peer's transactions.
250+    const auto prev_count = orphanage.Size();
251+    orphanage.LimitOrphans(prev_count - 1, det_rand);
252+    BOOST_CHECK(orphanage.Size() <= prev_count - 1);

473+        self.log.info("Send another round of very large orphans from a DoSy peer")
474+        for large_orphan in large_orphans[60:]:
475+            peer_doser.send_and_ping(msg_tx(large_orphan))
476+
477+        # Something was evicted; the orphanage does not contain all large orphans + the 1p1c child
478+        self.wait_until(lambda: len(node.getorphantxs()) < len(large_orphans) + 1)

 96         auto peer_it = m_peer_orphanage_info.find(peer);
 97         if (Assume(peer_it != m_peer_orphanage_info.end())) {
 98             peer_it->second.m_total_usage -= tx_size;
 99+
100+            auto& orphan_list = peer_it->second.m_iter_list;
101+            size_t old_pos = std::distance(orphan_list.begin(), std::find(orphan_list.begin(), orphan_list.end(), it));

648-        assert_equal(len(orphanage), DEFAULT_MAX_ORPHAN_TRANSACTIONS)
649-
650-        self.log.info("Clearing the orphanage")
651-        for index, parent_orphan in enumerate(parent_orphans):
652-            peer_1.send_and_ping(msg_tx(parent_orphan))
653-        self.wait_until(lambda: len(node.getorphantxs()) == 0)

35@@ -36,8 +36,12 @@ bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
36         return false;
37     }
38 
39-    auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});
40+    auto& orphan_list = m_peer_orphanage_info.try_emplace(peer).first->second.m_iter_list;
41+    std::map<NodeId, size_t> announcer_list_pos{{peer, orphan_list.size()}};
42+    auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, announcer_list_pos, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});

153+        /** Orphan transactions announced by this peer. */
154+        std::vector<OrphanMap::iterator> m_iter_list;
155+
156+        /** Remove the element at list_pos in m_iter_list in O(1) time by swapping the last element
157+         * with the one at list_pos and popping the back if there are multiple elements. Returns the
158+         * swapped element, if applicable, so that the caller can update its list_pos.

110@@ -104,6 +111,7 @@ int TxOrphanage::EraseTx(const Wtxid& wtxid)
111         m_orphan_list[old_pos] = it_last;
112         it_last->second.list_pos = old_pos;

 96@@ -97,4 +97,105 @@ static void OrphanageEraseForBlockSinglePeer(benchmark::Bench& bench)
 97     });
 98 }
 99 
100+static void OrphanageEvictionManyPeers(benchmark::Bench& bench)

0@@ -0,0 +1,100 @@
1+// Copyright (c) 2011-2022 The Bitcoin Core developers

179@@ -168,6 +180,10 @@ class TxOrphanage {
180 
181     /** If there are more than max_orphans total orphans, evict randomly until that is no longer the case. */
182     unsigned int MaybeTrimOrphans(unsigned int max_orphans, FastRandomContext& rng);
183+
184+    /** Remove the element at list_pos in m_iter_list in O(1) time by swapping the last element

332@@ -332,16 +333,19 @@ void TxOrphanage::EraseForBlock(const CBlock& block)
333             if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
334             for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
335                 const CTransaction& orphanTx = *(*mi)->second.tx;
336-                vOrphanErase.push_back(orphanTx.GetWitnessHash());
337+                wtxids_to_erase.insert(orphanTx.GetWitnessHash());
338+                // Stop to avoid doing too much work. If there are more orphans to erase, rely on
339+                // expiration and evictions to clean up everything eventually.
340+                if (wtxids_to_erase.size() >= 100) break;

215+        // ratios.
216+        std::pop_heap(peer_it_heap.begin(), peer_it_heap.end(), compare_peer);
217+        auto it_worst_peer = peer_it_heap.back();
218+        peer_it_heap.pop_back();
219+
220+        // Evict a random orphan from this peer.

219+
220+        // Evict a random orphan from this peer.
221+        size_t randompos = rng.randrange(it_worst_peer->second.m_iter_list.size());
222+        auto it_to_evict = it_worst_peer->second.m_iter_list.at(randompos);
223+
224+        // Only erase this peer as an announcer, unless it is the only announcer. Otherwise peers

242+    int64_t GetPerPeerMaxUsage() const {
243+        return m_reserved_weight_per_peer;
244+    }
245+
246+    int64_t GetGlobalMaxUsage() const {
247+        return std::max<int64_t>(int64_t(m_peer_orphanage_info.size()) * m_reserved_weight_per_peer, 1);

33@@ -27,7 +34,26 @@ static constexpr auto ORPHAN_TX_EXPIRE_INTERVAL{5min};
34  * Not thread-safe. Requires external synchronization.
35  */
36 class TxOrphanage {
37+    /** The usage (weight) reserved for each peer, representing the amount of memory we are willing
38+     * to allocate for orphanage space. Note that this number is a reservation, not a limit: peers
39+     * are allowed to exceed this reservation until the global limit is reached, and peers are
40+     * effectively guaranteed this amount of space. Reservation is per-peer, so the global upper
41+     * bound on memory usage scales up with more peers. */
42+    unsigned int m_reserved_weight_per_peer{DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER};

216+            ++it;
217+        }
218+        return count;
219+    }
220+
221+    /** Return number of announcements with this wtxid. */

624+
625+            // If needs trim, then at least one peer has a DoS score higher than 1.
626+            Assume(dos_score.fee > dos_score.size);
627+
628+            // Evict the oldest announcement from this peer, sorting non-reconsiderable before reconsiderable.
629+            auto it_ann = m_orphans.get<ByPeer>().lower_bound(ByPeerView{worst_peer, false, 0});

326@@ -327,10 +327,10 @@ void TxOrphanage::SanityCheck() const
327     // Check that cached m_total_announcements is correct
328     unsigned int counted_total_announcements{0};
329     // Check that m_total_orphan_usage is correct
330-    unsigned int counted_total_usage{0};
331+    int64_t counted_total_usage{0};

36@@ -37,7 +37,7 @@ bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
37         return false;
38     }
39 
40-    auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});
41+    auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});

303@@ -305,9 +304,9 @@ FUZZ_TARGET(txdownloadman_impl, .init = initialize)
304     // Initialize a TxDownloadManagerImpl
305     bilingual_str error;
306     CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
307-    const auto max_orphan_count = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 300);
308+    const auto max_orphan_count = node::DEFAULT_MAX_ORPHAN_TRANSACTIONS;

72+        int64_t GetUsage()  const {
73+            return GetTransactionWeight(*m_tx);
74+        }
75+    };
76+
77+    // Index by wtxid, then peer. Uses:

83+    struct ByWtxid {};
84+    using ByWtxidView = std::tuple<Wtxid, NodeId>;
85+    struct WtxidExtractor
86+    {
87+        using result_type = ByWtxidView;
88+        result_type operator()(const Announcement& ann) const