1 // Copyright (c) 2021-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/txorphanage.h>
6 7 #include <consensus/validation.h>
8 #include <policy/policy.h>
9 #include <primitives/transaction.h>
10 #include <util/feefrac.h>
11 #include <util/hasher.h>
12 #include <util/log.h>
13 #include <util/time.h>
14 15 #include <boost/multi_index/indexed_by.hpp>
16 #include <boost/multi_index/ordered_index.hpp>
17 #include <boost/multi_index/tag.hpp>
18 #include <boost/multi_index_container.hpp>
19 20 #include <cassert>
21 #include <cmath>
22 #include <unordered_map>
23 24 namespace node {
25 /** Minimum NodeId for lower_bound lookups (in practice, NodeIds start at 0). */
26 static constexpr NodeId MIN_PEER{std::numeric_limits<NodeId>::min()};
27 /** Maximum NodeId for upper_bound lookups. */
28 static constexpr NodeId MAX_PEER{std::numeric_limits<NodeId>::max()};
29 class TxOrphanageImpl final : public TxOrphanage {
30 // Type alias for sequence numbers
31 using SequenceNumber = uint64_t;
32 /** Global sequence number, increment each time an announcement is added. */
33 SequenceNumber m_current_sequence{0};
34 35 /** One orphan announcement. Each announcement (i.e. combination of wtxid, nodeid) is unique. There may be multiple
36 * announcements for the same tx, and multiple transactions with the same txid but different wtxid are possible. */
37 struct Announcement
38 {
39 const CTransactionRef m_tx;
40 /** Which peer announced this tx */
41 const NodeId m_announcer;
42 /** What order this transaction entered the orphanage. */
43 const SequenceNumber m_entry_sequence;
44 /** Whether this tx should be reconsidered. Always starts out false. A peer's workset is the collection of all
45 * announcements with m_reconsider=true. */
46 bool m_reconsider{false};
47 48 Announcement(const CTransactionRef& tx, NodeId peer, SequenceNumber seq) :
49 m_tx{tx}, m_announcer{peer}, m_entry_sequence{seq}
50 { }
51 52 /** Get an approximation for "memory usage". The total memory is a function of the memory used to store the
53 * transaction itself, each entry in m_orphans, and each entry in m_outpoint_to_orphan_wtxids. We use weight because
54 * it is often higher than the actual memory usage of the transaction. This metric conveniently encompasses
55 * m_outpoint_to_orphan_wtxids usage since input data does not get the witness discount, and makes it easier to
56 * reason about each peer's limits using well-understood transaction attributes. */
57 TxOrphanage::Usage GetMemUsage() const {
58 return GetTransactionWeight(*m_tx);
59 }
60 61 /** Get an approximation of how much this transaction contributes to latency in EraseForBlock and EraseForPeer.
62 * The computation time is a function of the number of entries in m_orphans (thus 1 per announcement) and the
63 * number of entries in m_outpoint_to_orphan_wtxids (thus an additional 1 for every 10 inputs). Transactions with a
64 * small number of inputs (9 or fewer) are counted as 1 to make it easier to reason about each peer's limits in
65 * terms of "normal" transactions. */
66 TxOrphanage::Count GetLatencyScore() const {
67 return 1 + (m_tx->vin.size() / 10);
68 }
69 };
70 71 // Index by wtxid, then peer
72 struct ByWtxid {};
73 using ByWtxidView = std::tuple<Wtxid, NodeId>;
74 struct WtxidExtractor
75 {
76 using result_type = ByWtxidView;
77 result_type operator()(const Announcement& ann) const
78 {
79 return ByWtxidView{ann.m_tx->GetWitnessHash(), ann.m_announcer};
80 }
81 };
82 83 // Sort by peer, then by whether it is ready to reconsider, then by recency.
84 struct ByPeer {};
85 using ByPeerView = std::tuple<NodeId, bool, SequenceNumber>;
86 struct ByPeerViewExtractor {
87 using result_type = ByPeerView;
88 result_type operator()(const Announcement& ann) const
89 {
90 return ByPeerView{ann.m_announcer, ann.m_reconsider, ann.m_entry_sequence};
91 }
92 };
93 94 using AnnouncementMap = boost::multi_index::multi_index_container<
95 Announcement,
96 boost::multi_index::indexed_by<
97 boost::multi_index::ordered_unique<boost::multi_index::tag<ByWtxid>, WtxidExtractor>,
98 boost::multi_index::ordered_unique<boost::multi_index::tag<ByPeer>, ByPeerViewExtractor>
99 >
100 >;
101 template<typename Tag>
102 using Iter = typename AnnouncementMap::index<Tag>::type::iterator;
103 AnnouncementMap m_orphans;
104 105 const TxOrphanage::Count m_max_global_latency_score{DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE};
106 const TxOrphanage::Usage m_reserved_usage_per_peer{DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER};
107 108 /** Number of unique orphans by wtxid. Less than or equal to the number of entries in m_orphans. */
109 TxOrphanage::Count m_unique_orphans{0};
110 111 /** Memory used by orphans (see Announcement::GetMemUsage()), deduplicated by wtxid. */
112 TxOrphanage::Usage m_unique_orphan_usage{0};
113 114 /** The sum of each unique transaction's latency scores including the inputs only (see Announcement::GetLatencyScore
115 * but subtract 1 for the announcements themselves). The total orphanage's latency score is given by this value +
116 * the number of entries in m_orphans. */
117 TxOrphanage::Count m_unique_rounded_input_scores{0};
118 119 /** Index from the parents' outputs to wtxids that exist in m_orphans. Used to find children of
120 * a transaction that can be reconsidered and to remove entries that conflict with a block.*/
121 std::unordered_map<COutPoint, std::set<Wtxid>, SaltedOutpointHasher> m_outpoint_to_orphan_wtxids;
122 123 /** Set of Wtxids for which (exactly) one announcement with m_reconsider=true exists. */
124 std::set<Wtxid> m_reconsiderable_wtxids;
125 126 struct PeerDoSInfo {
127 TxOrphanage::Usage m_total_usage{0};
128 TxOrphanage::Count m_count_announcements{0};
129 TxOrphanage::Count m_total_latency_score{0};
130 bool operator==(const PeerDoSInfo& other) const
131 {
132 return m_total_usage == other.m_total_usage &&
133 m_count_announcements == other.m_count_announcements &&
134 m_total_latency_score == other.m_total_latency_score;
135 }
136 void Add(const Announcement& ann)
137 {
138 m_total_usage += ann.GetMemUsage();
139 m_total_latency_score += ann.GetLatencyScore();
140 m_count_announcements += 1;
141 }
142 bool Subtract(const Announcement& ann)
143 {
144 Assume(m_total_usage >= ann.GetMemUsage());
145 Assume(m_total_latency_score >= ann.GetLatencyScore());
146 Assume(m_count_announcements >= 1);
147 148 m_total_usage -= ann.GetMemUsage();
149 m_total_latency_score -= ann.GetLatencyScore();
150 m_count_announcements -= 1;
151 return m_count_announcements == 0;
152 }
153 /** There are 2 DoS scores:
154 * - Latency score (ratio of total latency score / max allowed latency score)
155 * - Memory score (ratio of total memory usage / max allowed memory usage).
156 *
157 * If the peer is using more than the allowed for either resource, its DoS score is > 1.
158 * A peer having a DoS score > 1 does not necessarily mean that something is wrong, since we
159 * do not trim unless the orphanage exceeds global limits, but it means that this peer will
160 * be selected for trimming sooner. If the global latency score or global memory usage
161 * limits are exceeded, it must be that there is a peer whose DoS score > 1. */
162 FeeFrac GetDosScore(TxOrphanage::Count max_peer_latency_score, TxOrphanage::Usage max_peer_memory) const
163 {
164 assert(max_peer_latency_score > 0);
165 assert(max_peer_memory > 0);
166 const FeeFrac latency_score(m_total_latency_score, max_peer_latency_score);
167 const FeeFrac mem_score(m_total_usage, max_peer_memory);
168 return std::max<ByRatioNegSize<FeeFrac>>(latency_score, mem_score);
169 }
170 };
171 /** Store per-peer statistics. Used to determine each peer's DoS score. The size of this map is used to determine the
172 * number of peers and thus global {latency score, memory} limits. */
173 std::unordered_map<NodeId, PeerDoSInfo> m_peer_orphanage_info;
174 175 /** Erase from m_orphans and update m_peer_orphanage_info. */
176 template<typename Tag>
177 void Erase(Iter<Tag> it);
178 179 /** Erase by wtxid. */
180 bool EraseTxInternal(const Wtxid& wtxid);
181 182 /** Check if there is exactly one announcement with the same wtxid as it. */
183 bool IsUnique(Iter<ByWtxid> it) const;
184 185 /** Check if the orphanage needs trimming. */
186 bool NeedsTrim() const;
187 188 /** Limit the orphanage to MaxGlobalLatencyScore and MaxGlobalUsage. */
189 void LimitOrphans();
190 191 public:
192 TxOrphanageImpl() = default;
193 TxOrphanageImpl(Count max_global_latency_score, Usage reserved_peer_usage) :
194 m_max_global_latency_score{max_global_latency_score},
195 m_reserved_usage_per_peer{reserved_peer_usage}
196 {}
197 ~TxOrphanageImpl() noexcept override = default;
198 199 TxOrphanage::Count CountAnnouncements() const override;
200 TxOrphanage::Count CountUniqueOrphans() const override;
201 TxOrphanage::Count AnnouncementsFromPeer(NodeId peer) const override;
202 TxOrphanage::Count LatencyScoreFromPeer(NodeId peer) const override;
203 TxOrphanage::Usage UsageByPeer(NodeId peer) const override;
204 205 TxOrphanage::Count MaxGlobalLatencyScore() const override;
206 TxOrphanage::Count TotalLatencyScore() const override;
207 TxOrphanage::Usage ReservedPeerUsage() const override;
208 209 /** Maximum allowed (deduplicated) latency score for all transactions (see Announcement::GetLatencyScore()). Dynamic
210 * based on number of peers. Each peer has an equal amount, but the global maximum latency score stays constant. The
211 * number of peers times MaxPeerLatencyScore() (rounded) adds up to MaxGlobalLatencyScore(). As long as every peer's
212 * m_total_latency_score / MaxPeerLatencyScore() < 1, MaxGlobalLatencyScore() is not exceeded. */
213 TxOrphanage::Count MaxPeerLatencyScore() const override;
214 215 /** Maximum allowed (deduplicated) memory usage for all transactions (see Announcement::GetMemUsage()). Dynamic based
216 * on number of peers. More peers means more allowed memory usage. The number of peers times ReservedPeerUsage()
217 * adds up to MaxGlobalUsage(). As long as every peer's m_total_usage / ReservedPeerUsage() < 1, MaxGlobalUsage() is
218 * not exceeded. */
219 TxOrphanage::Usage MaxGlobalUsage() const override;
220 221 bool AddTx(const CTransactionRef& tx, NodeId peer) override;
222 bool AddAnnouncer(const Wtxid& wtxid, NodeId peer) override;
223 CTransactionRef GetTx(const Wtxid& wtxid) const override;
224 bool HaveTx(const Wtxid& wtxid) const override;
225 bool HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const override;
226 CTransactionRef GetTxToReconsider(NodeId peer) override;
227 bool EraseTx(const Wtxid& wtxid) override;
228 void EraseForPeer(NodeId peer) override;
229 void EraseForBlock(const CBlock& block) override;
230 std::vector<std::pair<Wtxid, NodeId>> AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng) override;
231 bool HaveTxToReconsider(NodeId peer) override;
232 std::vector<CTransactionRef> GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId nodeid) const override;
233 std::vector<OrphanInfo> GetOrphanTransactions() const override;
234 TxOrphanage::Usage TotalOrphanUsage() const override;
235 void SanityCheck() const override;
236 };
237 238 template<typename Tag>
239 void TxOrphanageImpl::Erase(Iter<Tag> it)
240 {
241 // Update m_peer_orphanage_info and clean up entries if they point to an empty struct.
242 // This means peers that are not storing any orphans do not have an entry in
243 // m_peer_orphanage_info (they can be added back later if they announce another orphan) and
244 // ensures disconnected peers are not tracked forever.
245 auto peer_it = m_peer_orphanage_info.find(it->m_announcer);
246 Assume(peer_it != m_peer_orphanage_info.end());
247 if (peer_it->second.Subtract(*it)) m_peer_orphanage_info.erase(peer_it);
248 249 if (IsUnique(m_orphans.project<ByWtxid>(it))) {
250 m_unique_orphans -= 1;
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 275 bool 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 285 TxOrphanage::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 291 TxOrphanage::Count TxOrphanageImpl::CountAnnouncements() const { return m_orphans.size(); }
292 293 TxOrphanage::Usage TxOrphanageImpl::TotalOrphanUsage() const { return m_unique_orphan_usage; }
294 295 TxOrphanage::Count TxOrphanageImpl::CountUniqueOrphans() const { return m_unique_orphans; }
296 297 TxOrphanage::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 302 TxOrphanage::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 307 bool 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 355 bool 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 386 bool 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 406 bool 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. */
417 void 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 */
443 void 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});
501 unsigned int num_erased_this_round{0};
502 unsigned int starting_num_ann{it_worst_peer->second.m_count_announcements};
503 while (NeedsTrim()) {
504 if (!Assume(it_ann != m_orphans.get<ByPeer>().end())) break;
505 if (!Assume(it_ann->m_announcer == worst_peer)) break;
506 507 Erase<ByPeer>(it_ann++);
508 num_erased += 1;
509 num_erased_this_round += 1;
510 511 // If we erased the last orphan from this peer, it_worst_peer will be invalidated.
512 it_worst_peer = m_peer_orphanage_info.find(worst_peer);
513 if (it_worst_peer == m_peer_orphanage_info.end() ||
514 ByRatioNegSize{it_worst_peer->second.GetDosScore(max_lat, max_mem)} <= ByRatioNegSize{dos_threshold}) break;
515 }
516 LogDebug(BCLog::TXPACKAGES, "peer=%d orphanage overflow, removed %u of %u announcements\n", worst_peer, num_erased_this_round, starting_num_ann);
517 518 if (!NeedsTrim()) break;
519 520 // Unless this peer is empty, put it back in the heap so we continue to consider evicting its orphans.
521 // We may select this peer for evictions again if there are multiple DoSy peers.
522 if (it_worst_peer != m_peer_orphanage_info.end() && it_worst_peer->second.m_count_announcements > 0) {
523 heap_peer_dos.emplace_back(worst_peer, it_worst_peer->second.GetDosScore(max_lat, max_mem));
524 std::push_heap(heap_peer_dos.begin(), heap_peer_dos.end(), compare_score);
525 }
526 } while (true);
527 528 const auto remaining_unique_orphans{CountUniqueOrphans()};
529 LogDebug(BCLog::TXPACKAGES, "orphanage overflow, removed %u tx (%u announcements)\n", original_unique_txns - remaining_unique_orphans, num_erased);
530 }
531 532 std::vector<std::pair<Wtxid, NodeId>> TxOrphanageImpl::AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng)
533 {
534 std::vector<std::pair<Wtxid, NodeId>> ret;
535 auto& index_by_wtxid = m_orphans.get<ByWtxid>();
536 for (unsigned int i = 0; i < tx.vout.size(); i++) {
537 const auto it_by_prev = m_outpoint_to_orphan_wtxids.find(COutPoint(tx.GetHash(), i));
538 if (it_by_prev != m_outpoint_to_orphan_wtxids.end()) {
539 for (const auto& wtxid : it_by_prev->second) {
540 // If a reconsiderable announcement for this wtxid already exists, skip it.
541 if (m_reconsiderable_wtxids.contains(wtxid)) continue;
542 543 // Belt and suspenders, each entry in m_outpoint_to_orphan_wtxids should always have at least 1 announcement.
544 auto it = index_by_wtxid.lower_bound(ByWtxidView{wtxid, MIN_PEER});
545 if (!Assume(it != index_by_wtxid.end() && it->m_tx->GetWitnessHash() == wtxid)) continue;
546 547 // Select a random peer to assign orphan processing, reducing wasted work if the orphan is still missing
548 // inputs. However, we don't want to create an issue in which the assigned peer can purposefully stop us
549 // from processing the orphan by disconnecting.
550 auto it_end = index_by_wtxid.upper_bound(ByWtxidView{wtxid, MAX_PEER});
551 const auto num_announcers{std::distance(it, it_end)};
552 if (!Assume(num_announcers > 0)) continue;
553 std::advance(it, rng.randrange(num_announcers));
554 555 if (!Assume(it->m_tx->GetWitnessHash() == wtxid)) break;
556 557 // Mark this orphan as ready to be reconsidered.
558 static constexpr auto mark_reconsidered_modifier = [](auto& ann) { ann.m_reconsider = true; };
559 Assume(!it->m_reconsider);
560 index_by_wtxid.modify(it, mark_reconsidered_modifier);
561 ret.emplace_back(wtxid, it->m_announcer);
562 m_reconsiderable_wtxids.insert(wtxid);
563 564 LogDebug(BCLog::TXPACKAGES, "added %s (wtxid=%s) to peer %d workset\n",
565 it->m_tx->GetHash().ToString(), it->m_tx->GetWitnessHash().ToString(), it->m_announcer);
566 }
567 }
568 }
569 return ret;
570 }
571 572 bool TxOrphanageImpl::HaveTx(const Wtxid& wtxid) const
573 {
574 auto it_lower = m_orphans.get<ByWtxid>().lower_bound(ByWtxidView{wtxid, MIN_PEER});
575 return it_lower != m_orphans.get<ByWtxid>().end() && it_lower->m_tx->GetWitnessHash() == wtxid;
576 }
577 578 CTransactionRef TxOrphanageImpl::GetTx(const Wtxid& wtxid) const
579 {
580 auto it_lower = m_orphans.get<ByWtxid>().lower_bound(ByWtxidView{wtxid, MIN_PEER});
581 if (it_lower != m_orphans.get<ByWtxid>().end() && it_lower->m_tx->GetWitnessHash() == wtxid) return it_lower->m_tx;
582 return nullptr;
583 }
584 585 bool TxOrphanageImpl::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
586 {
587 return m_orphans.get<ByWtxid>().count(ByWtxidView{wtxid, peer}) > 0;
588 }
589 590 /** If there is a tx that can be reconsidered, return it and set it back to
591 * non-reconsiderable. Otherwise, return a nullptr. */
592 CTransactionRef TxOrphanageImpl::GetTxToReconsider(NodeId peer)
593 {
594 auto it = m_orphans.get<ByPeer>().lower_bound(ByPeerView{peer, true, 0});
595 if (it != m_orphans.get<ByPeer>().end() && it->m_announcer == peer && it->m_reconsider) {
596 // Flip m_reconsider. Even if this transaction stays in orphanage, it shouldn't be
597 // reconsidered again until there is a new reason to do so.
598 static constexpr auto mark_reconsidered_modifier = [](auto& ann) { ann.m_reconsider = false; };
599 m_orphans.get<ByPeer>().modify(it, mark_reconsidered_modifier);
600 // As there is exactly one m_reconsider announcement per reconsiderable wtxids, flipping
601 // the m_reconsider flag means the wtxid is no longer reconsiderable.
602 m_reconsiderable_wtxids.erase(it->m_tx->GetWitnessHash());
603 return it->m_tx;
604 }
605 return nullptr;
606 }
607 608 /** Return whether there is a tx that can be reconsidered. */
609 bool TxOrphanageImpl::HaveTxToReconsider(NodeId peer)
610 {
611 auto it = m_orphans.get<ByPeer>().lower_bound(ByPeerView{peer, true, 0});
612 return it != m_orphans.get<ByPeer>().end() && it->m_announcer == peer && it->m_reconsider;
613 }
614 615 void TxOrphanageImpl::EraseForBlock(const CBlock& block)
616 {
617 if (m_orphans.empty()) return;
618 619 std::set<Wtxid> wtxids_to_erase;
620 for (const CTransactionRef& ptx : block.vtx) {
621 const CTransaction& block_tx = *ptx;
622 623 // Which orphan pool entries must we evict?
624 for (const auto& input : block_tx.vin) {
625 auto it_prev = m_outpoint_to_orphan_wtxids.find(input.prevout);
626 if (it_prev != m_outpoint_to_orphan_wtxids.end()) {
627 // Copy all wtxids to wtxids_to_erase.
628 std::copy(it_prev->second.cbegin(), it_prev->second.cend(), std::inserter(wtxids_to_erase, wtxids_to_erase.end()));
629 }
630 }
631 }
632 633 unsigned int num_erased{0};
634 for (const auto& wtxid : wtxids_to_erase) {
635 // Don't use EraseTx here because it calls LimitOrphans and announcements deleted in that call are not reflected
636 // in its return result. Waiting until the end to do LimitOrphans helps save repeated computation and allows us
637 // to check that num_erased is what we expect.
638 num_erased += EraseTxInternal(wtxid) ? 1 : 0;
639 }
640 641 if (num_erased != 0) {
642 LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) included or conflicted by block\n", num_erased);
643 }
644 Assume(wtxids_to_erase.size() == num_erased);
645 646 // Deletions can cause the orphanage's MaxGlobalUsage to decrease, so we may need to trim here.
647 LimitOrphans();
648 }
649 650 std::vector<CTransactionRef> TxOrphanageImpl::GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId peer) const
651 {
652 std::vector<CTransactionRef> children_found;
653 const auto& parent_txid{parent->GetHash()};
654 655 // Iterate through all orphans from this peer, in reverse order, so that more recent
656 // transactions are added first. Doing so helps avoid work when one of the orphans replaced
657 // an earlier one. Since we require the NodeId to match, one peer's announcement order does
658 // not bias how we process other peer's orphans.
659 auto& index_by_peer = m_orphans.get<ByPeer>();
660 auto it_upper = index_by_peer.upper_bound(ByPeerView{peer, true, std::numeric_limits<uint64_t>::max()});
661 auto it_lower = index_by_peer.lower_bound(ByPeerView{peer, false, 0});
662 663 while (it_upper != it_lower) {
664 --it_upper;
665 if (!Assume(it_upper->m_announcer == peer)) break;
666 // Check if this tx spends from parent.
667 for (const auto& input : it_upper->m_tx->vin) {
668 if (input.prevout.hash == parent_txid) {
669 children_found.emplace_back(it_upper->m_tx);
670 break;
671 }
672 }
673 }
674 return children_found;
675 }
676 677 std::vector<TxOrphanage::OrphanInfo> TxOrphanageImpl::GetOrphanTransactions() const
678 {
679 std::vector<TxOrphanage::OrphanInfo> result;
680 result.reserve(m_unique_orphans);
681 682 auto& index_by_wtxid = m_orphans.get<ByWtxid>();
683 auto it = index_by_wtxid.begin();
684 std::set<NodeId> this_orphan_announcers;
685 while (it != index_by_wtxid.end()) {
686 this_orphan_announcers.insert(it->m_announcer);
687 // If this is the last entry, or the next entry has a different wtxid, build a OrphanInfo.
688 if (std::next(it) == index_by_wtxid.end() || std::next(it)->m_tx->GetWitnessHash() != it->m_tx->GetWitnessHash()) {
689 result.emplace_back(it->m_tx, std::move(this_orphan_announcers));
690 this_orphan_announcers.clear();
691 }
692 693 ++it;
694 }
695 Assume(m_unique_orphans == result.size());
696 697 return result;
698 }
699 700 void TxOrphanageImpl::SanityCheck() const
701 {
702 std::unordered_map<NodeId, PeerDoSInfo> reconstructed_peer_info;
703 std::map<Wtxid, std::pair<TxOrphanage::Usage, TxOrphanage::Count>> unique_wtxids_to_scores;
704 std::set<COutPoint> all_outpoints;
705 std::set<Wtxid> reconstructed_reconsiderable_wtxids;
706 707 for (auto it = m_orphans.begin(); it != m_orphans.end(); ++it) {
708 for (const auto& input : it->m_tx->vin) {
709 all_outpoints.insert(input.prevout);
710 }
711 unique_wtxids_to_scores.emplace(it->m_tx->GetWitnessHash(), std::make_pair(it->GetMemUsage(), it->GetLatencyScore() - 1));
712 713 auto& peer_info = reconstructed_peer_info[it->m_announcer];
714 peer_info.m_total_usage += it->GetMemUsage();
715 peer_info.m_count_announcements += 1;
716 peer_info.m_total_latency_score += it->GetLatencyScore();
717 718 if (it->m_reconsider) {
719 auto [_, added] = reconstructed_reconsiderable_wtxids.insert(it->m_tx->GetWitnessHash());
720 // Check that there is only ever 1 announcement per wtxid with m_reconsider set.
721 assert(added);
722 }
723 }
724 assert(reconstructed_peer_info.size() == m_peer_orphanage_info.size());
725 726 // Recalculated per-peer stats are identical to m_peer_orphanage_info
727 assert(reconstructed_peer_info == m_peer_orphanage_info);
728 729 // Recalculated set of reconsiderable wtxids must match.
730 assert(m_reconsiderable_wtxids == reconstructed_reconsiderable_wtxids);
731 732 // All outpoints exist in m_outpoint_to_orphan_wtxids, all keys in m_outpoint_to_orphan_wtxids correspond to some
733 // orphan, and all wtxids referenced in m_outpoint_to_orphan_wtxids are also in m_orphans.
734 // This ensures m_outpoint_to_orphan_wtxids is cleaned up.
735 assert(all_outpoints.size() == m_outpoint_to_orphan_wtxids.size());
736 for (const auto& [outpoint, wtxid_set] : m_outpoint_to_orphan_wtxids) {
737 assert(all_outpoints.contains(outpoint));
738 for (const auto& wtxid : wtxid_set) {
739 assert(unique_wtxids_to_scores.contains(wtxid));
740 }
741 }
742 743 // Cached m_unique_orphans value is correct.
744 assert(m_orphans.size() >= m_unique_orphans);
745 assert(m_orphans.size() <= m_peer_orphanage_info.size() * m_unique_orphans);
746 assert(unique_wtxids_to_scores.size() == m_unique_orphans);
747 748 const auto calculated_dedup_usage = std::accumulate(unique_wtxids_to_scores.begin(), unique_wtxids_to_scores.end(),
749 TxOrphanage::Usage{0}, [](TxOrphanage::Usage sum, const auto pair) { return sum + pair.second.first; });
750 assert(calculated_dedup_usage == m_unique_orphan_usage);
751 752 // Global usage is deduplicated, should be less than or equal to the sum of all per-peer usages.
753 const auto summed_peer_usage = std::accumulate(m_peer_orphanage_info.begin(), m_peer_orphanage_info.end(),
754 TxOrphanage::Usage{0}, [](TxOrphanage::Usage sum, const auto pair) { return sum + pair.second.m_total_usage; });
755 assert(summed_peer_usage >= m_unique_orphan_usage);
756 757 // Cached m_unique_rounded_input_scores value is correct.
758 const auto calculated_total_latency_score = std::accumulate(unique_wtxids_to_scores.begin(), unique_wtxids_to_scores.end(),
759 TxOrphanage::Count{0}, [](TxOrphanage::Count sum, const auto pair) { return sum + pair.second.second; });
760 assert(calculated_total_latency_score == m_unique_rounded_input_scores);
761 762 // Global latency score is deduplicated, should be less than or equal to the sum of all per-peer latency scores.
763 const auto summed_peer_latency_score = std::accumulate(m_peer_orphanage_info.begin(), m_peer_orphanage_info.end(),
764 TxOrphanage::Count{0}, [](TxOrphanage::Count sum, const auto pair) { return sum + pair.second.m_total_latency_score; });
765 assert(summed_peer_latency_score >= m_unique_rounded_input_scores + m_orphans.size());
766 767 assert(!NeedsTrim());
768 }
769 770 TxOrphanage::Count TxOrphanageImpl::MaxGlobalLatencyScore() const { return m_max_global_latency_score; }
771 TxOrphanage::Count TxOrphanageImpl::TotalLatencyScore() const { return m_unique_rounded_input_scores + m_orphans.size(); }
772 TxOrphanage::Usage TxOrphanageImpl::ReservedPeerUsage() const { return m_reserved_usage_per_peer; }
773 TxOrphanage::Count TxOrphanageImpl::MaxPeerLatencyScore() const { return m_max_global_latency_score / std::max<unsigned int>(m_peer_orphanage_info.size(), 1); }
774 TxOrphanage::Usage TxOrphanageImpl::MaxGlobalUsage() const { return m_reserved_usage_per_peer * std::max<int64_t>(m_peer_orphanage_info.size(), 1); }
775 776 bool TxOrphanageImpl::NeedsTrim() const
777 {
778 return TotalLatencyScore() > MaxGlobalLatencyScore() || TotalOrphanUsage() > MaxGlobalUsage();
779 }
780 std::unique_ptr<TxOrphanage> MakeTxOrphanage() noexcept
781 {
782 return std::make_unique<TxOrphanageImpl>();
783 }
784 std::unique_ptr<TxOrphanage> MakeTxOrphanage(TxOrphanage::Count max_global_latency_score, TxOrphanage::Usage reserved_peer_usage) noexcept
785 {
786 return std::make_unique<TxOrphanageImpl>(max_global_latency_score, reserved_peer_usage);
787 }
788 } // namespace node
789