p2p: track and use all potential peers for orphan resolution

glozow commented at 9:06 pm on November 30, 2024: member

Part of #27463.

(Transaction) orphan resolution is a process that kicks off when we are missing UTXOs to validate an unconfirmed transaction. We currently request missing parents by txid; BIP 331 also defines a way to explicitly request ancestors.

Currently, when we find that a transaction is an orphan, we only try to resolve it with the peer who provided the tx. If this doesn’t work out (e.g. they send a notfound or don’t respond), we do not try again. We actually can’t, because we’ve already forgotten who else could resolve this orphan (i.e. all the other peers who announced the transaction).

What is wrong with this? It makes transaction download less reliable, particularly for 1p1c packages which must go through orphan resolution in order to be downloaded.

Can we fix this with BIP 331 / is this “duct tape” before the real solution? BIP 331 (receiver-initiated ancestor package relay) is also based on the idea that there is an orphan that needs resolution, but it’s just a new way of communicating information. It’s not inherently more honest; you can request ancestor package information and get a notfound. So ancestor package relay still requires some kind of procedure for retrying when an orphan resolution attempt fails. See the #27742 implementation which builds on this orphan resolution tracker to keep track of what packages to download (it just isn’t rebased on this exact branch). The difference when using BIP 331 is that we request ancpkginfo and then pkgtxns instead of the parent txids.

Zooming out, we’d like orphan handling to be:

Bandwidth-efficient: don’t have too many requests out at once. As already implemented today, transaction requests for orphan parents and regular download both go through the TxRequestTracker so that we don’t have duplicate requests out.
Not vulnerable to censorship: don’t give up too easily, use all candidate peers. See e.g. https://bitcoincore.org/en/2024/07/03/disclose_already_asked_for/
Load-balance between peers: don’t overload peers; use all peers available. This is also useful for when we introduce per-peer orphan protection, since each peer will have limited slots.

The approach taken in this PR is to think of each peer who announces an orphan as a potential “orphan resolution candidate.” These candidates include:

the peer who sent us the orphan tx
any peers who announced the orphan prior to us downloading it
any peers who subsequently announce the orphan after we have started trying to resolve it For each orphan resolution candidate, we treat them as having “announced” all of the missing parents to us at the time of receipt of this orphan transaction (or at the time they announced the tx if they do so after we’ve already started tracking it as an orphan). We add the missing parents as entries to m_txrequest, incorporating the logic of typical txrequest processing, which means we prefer outbounds, try not to have duplicate requests in flight, don’t overload peers, etc.

glozow added the label P2P on Nov 30, 2024

DrahtBot commented at 9:06 pm on November 30, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31397.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	marcofleon, instagibbs, dergoegge, mzumsande
Concept ACK	sipa

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31628 (test: add coverage for immediate orphanage eviction case by instagibbs)
#28031 (Package Relay 1/3: Introduce TxDownloadManager and improve orphan-handling by glozow)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in src/txorphanage.cpp:25 in 3e16a36959 outdated

22+    if (it != m_orphans.end()) {
23+        Assume(!it->second.announcers.empty());
24+        const auto ret = it->second.announcers.insert(peer);
25+        if (ret.second) {
26+            LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s\n", peer, wtxid.ToString());
27+        }

dergoegge commented at 12:04 pm on December 2, 2024:

0    if (auto it{m_orphans.find(wtxid)}; it != m_orphans.end()) {
1        AddAnnouncer(wtxid, peer);

Duplicating the map lookup is better than duplicating the code imo.

glozow commented at 12:01 pm on December 6, 2024:

largely agree, done

in test/functional/p2p_opportunistic_1p1c.py:251 in 3e16a36959 outdated

249         node_mempool = node.getrawmempool()
250         assert low_fee_parent["txid"] not in node_mempool
251         assert tx_orphan_bad_wit.rehash() not in node_mempool
252 
253-        # 5. Peer that sent a consensus-invalid transaction should be disconnected.
254-        bad_orphan_sender.wait_for_disconnect()

instagibbs commented at 3:45 pm on December 2, 2024:

we should cause the disconnect still to make sure we’re disconnecting on consensus failure

glozow commented at 12:10 pm on December 6, 2024:

Good point, added a line where this sender sends the parent too

in test/functional/p2p_opportunistic_1p1c.py:294 in 3e16a36959 outdated

289-        # 5. Peer sent a consensus-invalid transaction.
290-        fake_parent_sender.wait_for_disconnect()
291-
292         self.log.info("Check that fake parent does not cause orphan to be deleted and real package can still be submitted")
293-        # 6. Child-sending should not have been punished and the orphan should remain in orphanage.
294+        # 5. Child-sending should not have been punished and the orphan should remain in orphanage.

instagibbs commented at 3:58 pm on December 2, 2024:

while we’re touching this, we can directly assert via getorphantxs now

glozow commented at 12:33 pm on December 11, 2024:

Done, and added a multi-announcer test to rpc_orphans.py

in src/node/txdownloadman_impl.cpp:262 in 3e16a36959 outdated

357@@ -356,34 +358,6 @@ std::optional<PackageToValidate> TxDownloadManagerImpl::Find1P1CPackage(const CT
358             return PackageToValidate{ptx, child, nodeid, nodeid};
359         }
360     }
361-
362-    // If no suitable candidate from the same peer is found, also try children that were provided by

instagibbs commented at 3:59 pm on December 2, 2024:

3e16a36959f70da59846621f099c1f1df4a210ed love this cleanup of logic :)

glozow commented at 11:55 am on December 6, 2024:

That’s why I made them separate functions! Easy deletion.

in src/node/txdownloadman_impl.cpp:357 in 938659fbd8 outdated

307@@ -308,7 +308,7 @@ node::RejectedTxTodo TxDownloadManagerImpl::MempoolRejectedTx(const CTransaction
308     // Whether we should call AddToCompactExtraTransactions at the end
309     bool add_extra_compact_tx{first_time_failure};
310     // Hashes to pass to AddKnownTx later
311-    std::vector<uint256> unique_parents;
312+    std::vector<Txid> unique_parents;

instagibbs commented at 4:40 pm on December 3, 2024:

nit: could also adapt the for loop over unique_parents in ProcessInvalidTx

glozow commented at 12:26 pm on December 6, 2024:

done

in src/txorphanage.h:96 in 7badc7e004 outdated

88@@ -84,6 +89,8 @@ class TxOrphanage {
89 protected:
90     struct OrphanTx : public OrphanTxBase {
91         size_t list_pos;
92+        /** Txids of the missing parents to request. Determined by peerman. */

instagibbs commented at 5:17 pm on December 3, 2024:

as of introduction commit 7badc7e004e288aef645404b1b09699be8b87d1e this is storing all parent txids, missing or not.

mzumsande commented at 10:41 pm on December 10, 2024:

now determined by txdownloadman

glozow commented at 3:37 pm on January 3, 2025:

deleted

in src/test/orphanage_tests.cpp:129 in 7badc7e004 outdated

134@@ -135,7 +135,7 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
135         tx.vout[0].nValue = 1*CENT;
136         tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey()));
137 
138-        orphanage.AddTx(MakeTransactionRef(tx), i);
139+        orphanage.AddTx(MakeTransactionRef(tx), i, {});

instagibbs commented at 5:19 pm on December 3, 2024:

7badc7e004e288aef645404b1b09699be8b87d1e In this test and the fuzz harness, I’m not sure I’m happy with this new field sometimes being populated and sometimes not.

Could you make a test util that automatically fills in this argument properly via just looking at the tx inputs?

instagibbs commented at 2:58 pm on December 6, 2024:

alternatively, just don’t set them ever unless they’re intended to be used in the test, deleting most of these(?) won’t invalidate tests

in src/txorphanage.cpp:186 in acaa7c13fa outdated

182@@ -152,6 +183,12 @@ bool TxOrphanage::HaveTx(const Wtxid& wtxid) const
183     return m_orphans.count(wtxid);
184 }
185 
186+bool TxOrphanage::HaveTxAndPeer(const Wtxid& wtxid, NodeId peer) const

instagibbs commented at 5:26 pm on December 3, 2024:

s/HaveTxAndPeer/HaveTxFromPeer/ or similar?

glozow commented at 12:09 pm on December 6, 2024:

changed

in src/txorphanage.h:83 in acaa7c13fa outdated

89@@ -80,7 +90,8 @@ class TxOrphanage {
90     /** Allows providing orphan information externally */
91     struct OrphanTxBase {
92         CTransactionRef tx;
93-        NodeId fromPeer;
94+        /** Peers added with AddTx or AddAnnouncer. */

instagibbs commented at 5:28 pm on December 3, 2024:

noting as of acaa7c13fac3e35a55daf2c62c27ab85172b4964 AddAnnouncer isnt called

3 2 cases?

announced as INV (AddAnnouncer @ c04d1a876cdbcd159c53dde55d57a55675c41f38) ~~2. parent of another orphan given (?)~~ because txid, not wtxid
given directly (AddTx on all tracked advertisements of it too)

glozow commented at 12:20 pm on December 6, 2024:

Correct. I think this is not too misleading? Added “unused for now” in the commit messages.

instagibbs commented at 2:42 pm on December 6, 2024:

kind of just exposing my thoughts as I review!

in src/txorphanage.cpp:26 in acaa7c13fa outdated

22+        Assume(!it->second.announcers.empty());
23+        const auto ret = it->second.announcers.insert(peer);
24+        if (ret.second) {
25+            LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s\n", peer, wtxid.ToString());
26+        }
27+        // Even if an announcer was added, no new orphan entry was created.

instagibbs commented at 5:40 pm on December 3, 2024:

0        // Since an additional announcer was added, no new orphan entry was created.

glozow commented at 12:05 pm on December 6, 2024:

We haven’t necessarily added an announcer. But I updated this comment.

in src/txorphanage.cpp:140 in 83d276c7dd outdated

138         while (iter != m_orphans.end())
139         {
140             std::map<Wtxid, OrphanTx>::iterator maybeErase = iter++;
141             if (maybeErase->second.nTimeExpire <= nNow) {
142-                nErased += EraseTx(maybeErase->second.tx->GetWitnessHash());
143+                const auto& wtxid = maybeErase->second.tx->GetWitnessHash();

instagibbs commented at 5:48 pm on December 3, 2024:

isn’t MaybeErase.first the wtxid?

glozow commented at 12:06 pm on December 6, 2024:

switched

in src/txorphanage.cpp:155 in 83d276c7dd outdated

155     while (m_orphans.size() > max_orphans)
156     {
157         // Evict a random orphan:
158         size_t randompos = rng.randrange(m_orphan_list.size());
159-        EraseTx(m_orphan_list[randompos]->second.tx->GetWitnessHash());
160+        const auto& wtxid = m_orphan_list[randompos]->second.tx->GetWitnessHash();

instagibbs commented at 5:49 pm on December 3, 2024:

not much shorter but m_orphan_list[randompos]->first is wtxid?

glozow commented at 12:07 pm on December 6, 2024:

done

in src/node/txdownloadman_impl.cpp:390 in b64be9ed2c outdated

347@@ -348,6 +348,12 @@ node::RejectedTxTodo TxDownloadManagerImpl::MempoolRejectedTx(const CTransaction
348                 }
349             }
350             if (!fRejectedParents) {

instagibbs commented at 6:14 pm on December 3, 2024:

commit message b64be9ed2ce9b68aef178684dac3be998f18bbdd

“announcments,”

glozow commented at 11:57 am on December 6, 2024:

fixed

in src/node/txdownloadman_impl.cpp:181 in c04d1a876c outdated

179@@ -174,10 +180,27 @@ void TxDownloadManagerImpl::DisconnectedPeer(NodeId nodeid)
180 
181 bool TxDownloadManagerImpl::AddTxAnnouncement(NodeId peer, const GenTxid& gtxid, std::chrono::microseconds now, bool p2p_inv)

instagibbs commented at 6:29 pm on December 3, 2024:

as of c04d1a876cdbcd159c53dde55d57a55675c41f38 p2p_inv=false has no usage aside from fuzz harness

glozow commented at 12:01 pm on December 6, 2024:

added a commit to clean this up

in src/node/txdownloadman_impl.cpp:202 in c04d1a876c outdated

197+
198+    const bool already_had{AlreadyHaveTx(gtxid, /*include_reconsiderable=*/true)};
199+
200     // If this is an inv received from a peer and we already have it, we can drop it.
201     // If this is a request for the parent of an orphan, we don't drop transactions that we already have. In particular,
202     // we *do* want to request parents that are in m_lazy_recent_rejects_reconsiderable, since they can be CPFP'd.

instagibbs commented at 6:52 pm on December 3, 2024:

these comments seem outdated since AddTxAnnouncement is only being called for explicit INV related reasons now

glozow commented at 12:01 pm on December 6, 2024:

cleaned up

in src/node/txdownloadman_impl.cpp:198 in c04d1a876c outdated

193+            }
194+        }
195+        return true;
196+    }
197+
198+    const bool already_had{AlreadyHaveTx(gtxid, /*include_reconsiderable=*/true)};

instagibbs commented at 6:53 pm on December 3, 2024:

already_had used exactly once, seems like we don’t need it

glozow commented at 12:01 pm on December 6, 2024:

cleaned up

in src/node/txdownloadman_impl.cpp:243 in 3e16a36959 outdated

238+    if (!info.m_relay_permissions) {
239+        // This mirrors the delaying and dropping behavior in AddTxAnnouncement in order to preserve
240+        // existing behavior: drop if we are tracking too many invs for this peer already. Each
241+        // orphan resolution involves at least 1 transaction request which may or may not be
242+        // currently tracked in m_txrequest, so we include that in the count.
243+        if (m_txrequest.Count(nodeid) + m_orphan_resolution_tracker.Count(nodeid) >= MAX_PEER_TX_ANNOUNCEMENTS) return std::nullopt;

glozow commented at 2:34 pm on December 4, 2024:

Ah, need to add the size of unique_parents to this. Surprised fuzzer has not tripped on it…

glozow commented at 11:57 am on December 6, 2024:

deleted, no longer applicable

in test/functional/p2p_orphan_handling.py:674 in 3e16a36959 outdated

669+        peer_early_unresponsive = node.add_p2p_connection(PeerTxRelayer())
670+
671+        # Announces after tx is sent
672+        peer_late_announcer = node.add_p2p_connection(PeerTxRelayer())
673+
674+        # Both peers send invs for the orphan, so the node an expect both to know its ancestors.

dergoegge commented at 10:06 am on December 5, 2024:

0        # Both peers send invs for the orphan, so the node can expect both to know its ancestors.

glozow commented at 12:25 pm on December 6, 2024:

done

dergoegge commented at 11:25 am on December 5, 2024: member

Concept ACK

I implemented what I was talking about in the review club yesterday here: https://github.com/dergoegge/bitcoin/commits/2024-12-rslv-orphns/ (the only difference is the main commit 3928b400d805f75e0ba5b9947d5d441a828aa5be) and it looks like it passes your functional test additions! So perhaps it’s worth exploring if we actually need another tracker…

 017:34 	<dergoegge> I was wondering why we need another txrequest tracker instance for this? couldn’t we just keep track of announcers in the orphanage (same as in the PR) and then add requests for the parents to the existing tracker on future announcements?
 117:35 	<glozow> dergoegge: that's an idea. How would you schedule the requests?
 217:35 	<dergoegge> ideally at the same time
 317:35 	<glozow> Is there a cost to having another txrequest tracker? It's not that different from adding another std::map
 417:35 	<glozow> No, I mean, how would you load-balance between peers, bake in preferences, etc.
 517:36 	<dergoegge> isn't that what the existing tracker does?
 617:36 	<glozow> Oh, you mean adding a new type to the tracker? So we'd have txid type, wtxid type, and orphan?
 717:37 	<glozow> also note that the parent requests are added to the txrequest tracker
 817:39 	<dergoegge> I guess I'm wondering why we need the concept of tracking the resolution by orphan id, as opposed to just putting the requests for the parents in the existing tracker
 917:39 	<glozow> we do put the requests for the parents in the existing tracker
1017:39 	<glozow> Maybe we are crossing wires?
1117:39 	<instagibbs> mmmm he's asking why the add to new tracker, then "immediately" add to old one, vs just add to old one, I think
1217:40 	<dergoegge> yea
1317:40 	<instagibbs> add to old one with "proper delays"
1417:40 	<instagibbs> I didn't get far enough in my review to figure this out either 😅
1517:40 	<glozow> We might have multiple candidates for orphan resolution
1617:41 	<glozow> Oh I see what you're saying
1717:42 	<dergoegge> "multiple candidates" as in same parents different orphan?
1817:42 	<glozow> Perhaps that could work, where you're treating it as if all of them just announced the missing parents? I don't know how you'd add `ancpkginfo` orphan resolution easily this way though.
1917:43 	<glozow> different peers same orphan
2017:43 	<instagibbs> You'd also have to somehow track that you're no longer asking for any parents of an orphan in order to EraseOrphanOfPeer?
2117:43 	<marcofleon> yeah i was thinking it made sense with GetCandidatePeers. Having another tracker to separate out the orphan reso process
2217:46 	<glozow> will think about this idea some more
2317:47 	<dergoegge> me too 👍
2417:47 	<glozow> I think it's possible it works? My main questions would be (1) what is the cost of having a second tracker? Because it's the perfect data structure for this. (2) how do we make it extensible to package relay still.
2517:48 	<instagibbs> imo the cost is mostly an additional structure lying around that needs to stay in sync with other things
2617:48 	<dergoegge> 1) if we don't need it then it's just extra complexity 2) fair!
2717:48 	<marcofleon> The fact that there are candidates that be added or not added to that new tracker is why it made sense to me in the first place I guess is what i was saying
2817:48 	<marcofleon> can be*
2917:49 	<glozow> (1) shoving it into the existing tracker but needing to have extra logic could also be complexity!
3017:49 	<dergoegge> well in my mind it wouldn't need extra logic but I might be wrong, need to think more
3117:49 	<instagibbs> proof of code for this I think..
3217:49 	<glozow> but yeah, I don't like that we need to ensure m_orphanage and m_orphan_resolution_tracker are in sync. that's super fair
3317:49 	<dergoegge> frfr
3417:50 	<glozow> yeah let's see what the code would look like
3517:50 	<marcofleon> fr
3617:50 	<glozow> fr r r

glozow commented at 1:00 pm on December 5, 2024: member

Thanks @dergoegge, will spend some time thinking about whether there are any problems with it. Perhaps we can do this easier version now and cross the orphan reso tracker bridge when we need to build the 2-step orphan resolution protocol (info and then transactions).

glozow force-pushed on Dec 6, 2024

glozow commented at 12:27 pm on December 6, 2024: member

Changed to the new approach, cleaned up a bunch of things, addressed most comments. I think I have 1 or 2 more to get to, and need to write an RPC test.

glozow commented at 12:33 pm on December 6, 2024: member

The 2 main functional differences I noticed with this approach are (1) If there are multiple missing parents, we may be using different peers to request them. (2) We don’t EraseOrphanOfPeer if orphan resolution expires. This also means we don’t delete the orphan after we’ve exhausted all potential orphan resolution candidates. This is similar to what we have today - it’ll stay for 20min before orphanage expires the entry.

in src/node/txdownloadman.h:40 in 1cc9e0fda9 outdated

35@@ -36,6 +36,8 @@ static constexpr auto NONPREF_PEER_TX_DELAY{2s};
36 static constexpr auto OVERLOADED_PEER_TX_DELAY{2s};
37 /** How long to wait before downloading a transaction from an additional peer */
38 static constexpr auto GETDATA_TX_INTERVAL{60s};
39+/** How long to wait before requesting orphan parents from an additional peer. */
40+static constexpr auto ORPHAN_ANCESTOR_GETDATA_INTERVAL{60s};

instagibbs commented at 3:36 pm on December 6, 2024:

unused now since we’re Just using the regular txtracker flow (python tests still using is erroneously too)

glozow commented at 11:59 am on December 11, 2024:

Yes - deleted now

in src/node/txdownloadman_impl.cpp:184 in 1cc9e0fda9 outdated

179+    // - received as an p2p inv
180+    // - is wtxid matching something in orphanage
181+    // - exists in orphanage
182+    // - peer can be an orphan resolution candidate
183+    if (p2p_inv && gtxid.IsWtxid()) {
184+        if (auto parent_txids{m_orphanage.GetParentTxids(Wtxid::FromUint256(gtxid.GetHash()))}) {

instagibbs commented at 3:52 pm on December 6, 2024:

1cc9e0fda9d8136bc36a247009676f07d5d84fb6

0        const auto wtxid = Wtxid::FromUint256(gtxid.GetHash());
1        if (auto parent_txids{m_orphanage.GetParentTxids(wtxid)) {

as well as re-using next 2 lines, and the LogDebug?

instagibbs commented at 3:54 pm on December 6, 2024:

also, should we ever have something in our orphanage that doesn’t have a parent txid?

glozow commented at 12:47 pm on December 10, 2024:

also, should we ever have something in our orphanage that doesn’t have a parent txid?

Yeah we shouldn’t ever have that situation. However I like the std:optional<X> GetX() interface convention.

in test/functional/p2p_1p1c_network.py:153 in b86dcb01cf outdated

155             submitpackage_result = self.nodes[0].submitpackage(package_hex)
156             assert_equal(submitpackage_result["package_msg"], "success")
157 
158         self.log.info("Wait for mempools to sync")
159-        self.sync_mempools(timeout=20)
160+        self.sync_mempools(timeout=62)

instagibbs commented at 6:28 pm on December 6, 2024:

62 is very magical looking, can we do better?

glozow commented at 12:07 pm on December 11, 2024:

deleted now, I think it was a hack for some intermittent thing that I should have removed a while ago

instagibbs commented at 6:43 pm on December 6, 2024: member

took another pass with the major new commit f96df3d60a943b87eecd3a6915fcace0eee2838f

DrahtBot added the label CI failed on Dec 9, 2024

in src/test/orphanage_tests.cpp:377 in a0e427b46e outdated

389@@ -390,4 +390,177 @@ BOOST_AUTO_TEST_CASE(too_large_orphan_tx)
390     BOOST_CHECK(orphanage.AddTx(MakeTransactionRef(tx), 0, {}));
391 }
392 
393+BOOST_AUTO_TEST_CASE(process_block)

mzumsande commented at 11:32 pm on December 10, 2024:

Does process_block relate to the changes wrt multiple announcers? Could adjust the commit message to explain why it’s added.

glozow commented at 3:19 pm on January 3, 2025:

I’ve moved that test to its own commit

glozow force-pushed on Dec 11, 2024

DrahtBot removed the label CI failed on Dec 11, 2024

in src/txorphanage.cpp:109 in 9a77d84a56 outdated

105@@ -89,9 +106,14 @@ void TxOrphanage::EraseForPeer(NodeId peer)
106     while (iter != m_orphans.end())
107     {
108         // increment to avoid iterator becoming invalid after erasure
109-        const auto& [wtxid, orphan] = *iter++;
110-        if (orphan.fromPeer == peer) {
111-            nErased += EraseTx(wtxid);
112+        auto& [wtxid, orphan] = *iter++;

instagibbs commented at 3:31 pm on December 11, 2024:

nitty suggestion

 0diff --git a/src/txorphanage.cpp b/src/txorphanage.cpp
 1index 62c55c2975..cea0c05b9d 100644
 2--- a/src/txorphanage.cpp
 3+++ b/src/txorphanage.cpp
 4@@ -105,17 +105,15 @@ void TxOrphanage::EraseForPeer(NodeId peer)
 5     std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
 6     while (iter != m_orphans.end())
 7     {
 8         // increment to avoid iterator becoming invalid after erasure
 9         auto& [wtxid, orphan] = *iter++;
10-        if (orphan.announcers.contains(peer)) {
11-            if (orphan.announcers.size() == 1) {
12-                nErased += EraseTx(orphan.tx->GetWitnessHash());
13-            } else {
14-                // Don't erase this orphan. Another peer has also announced it, so it may still be useful.
15-                orphan.announcers.erase(peer);
16-            }
17+        orphan.announcers.erase(peer);
18+
19+        // No remaining annoncers; cleanup orphanage entry
20+        if (orphan.announcers.empty()) {
21+            nErased += EraseTx(orphan.tx->GetWitnessHash());
22         }
23     }
24     if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", nErased, peer);
25 }

glozow commented at 3:35 pm on January 3, 2025:

done

in src/txorphanage.cpp:19 in 9a77d84a56 outdated

15@@ -16,8 +16,11 @@ bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer, const std::vecto
16 {
17     const Txid& hash = tx->GetHash();
18     const Wtxid& wtxid = tx->GetWitnessHash();
19-    if (m_orphans.count(wtxid))
20+    if (auto it{m_orphans.find(wtxid)}; it != m_orphans.end()) {

instagibbs commented at 3:35 pm on December 11, 2024:

Just AddAnnouncer and short-circuit if it returns true instead of doing the lookup here?

glozow commented at 3:32 pm on January 3, 2025:

The conditions aren’t exactly the same since AddAnnouncer also returns false if we already HaveTxFromPeer. We’d need to make the return result tri-state.

in src/test/orphanage_tests.cpp:441 in 5e5fbed1c9 outdated

436+    orphanage.EraseForBlock(block);
437+    for (const auto& expected_removed : {bo_tx_same_txid, o_tx_same_txid_diff_witness, o_tx_conflict, o_tx_conflict_partial_2}) {
438+        const auto& expected_removed_wtxid = expected_removed->GetWitnessHash();
439+        BOOST_CHECK(!orphanage.HaveTx(expected_removed_wtxid));
440+    }
441+    BOOST_CHECK_EQUAL(orphanage.Size(), 0);

instagibbs commented at 3:41 pm on December 11, 2024:

probably should add one innocent bystander that isn’t evicted to ensure we’re not doing the stupidest thing of wiping all orphans on each block or something

glozow commented at 3:23 pm on January 3, 2025:

good point, added

in src/test/orphanage_tests.cpp:474 in 5e5fbed1c9 outdated

469+        auto ptx_mutated{MakeMutation(ptx)};
470+        BOOST_CHECK(orphanage.AddTx(ptx_mutated, node0, {}));
471+        BOOST_CHECK(orphanage.HaveTx(ptx_mutated->GetWitnessHash()));
472+        expected_total_count += 1;
473+
474+        // It's too late to add parent_txids through AddTx.

instagibbs commented at 3:45 pm on December 11, 2024:

0        // parent_txids is ignored on subsequent AddTx for the same wtxid

glozow commented at 3:23 pm on January 3, 2025:

deleted now that parent_txids is gone

in src/test/orphanage_tests.cpp:480 in 5e5fbed1c9 outdated

487+
488+        // if EraseForPeer is called for an orphan with multiple announcers, the orphanage should only
489+        // erase that peer from the announcers set.
490+        orphanage.EraseForPeer(node0);
491+        BOOST_CHECK(orphanage.HaveTx(ptx->GetWitnessHash()));
492+        // node0 is the only one that announced ptx_mutated

instagibbs commented at 3:50 pm on December 11, 2024:

0        // node0 is the only one that announced ptx_mutated
1        BOOST_CHECK(!orphanage.HaveTx(ptx_mutated->GetWitnessHash()))

glozow commented at 3:27 pm on January 3, 2025:

added

in src/test/orphanage_tests.cpp:481 in 5e5fbed1c9 outdated

476+        // Parent txids is empty because the tx exists but no parent_txids were provided.
477+        BOOST_CHECK(orphanage.GetParentTxids(wtxid)->empty());
478+        BOOST_CHECK(orphanage.GetParentTxids(ptx_mutated->GetWitnessHash())->empty());
479+
480+        // Adding a new announcer should not change overall accounting.
481+        orphanage.AddAnnouncer(ptx->GetWitnessHash(), node2);

instagibbs commented at 3:59 pm on December 11, 2024:

Can we check value of AddAnnouncer everywhere and include the already-HaveTxFromPeer case?

glozow commented at 3:26 pm on January 3, 2025:

added

in src/node/txdownloadman_impl.cpp:100 in a32d396ef2 outdated

 96@@ -97,6 +97,7 @@ void TxDownloadManagerImpl::ActiveTipChange()
 97 
 98 void TxDownloadManagerImpl::BlockConnected(const std::shared_ptr<const CBlock>& pblock)
 99 {
100+    // Orphanage may include transactions conflicted by this block.

instagibbs commented at 4:08 pm on December 11, 2024:

micro-nit: this being added in a32d396ef27d626e0c60e7ee8a74cbe3d918acb1 is weird

glozow commented at 3:02 pm on January 3, 2025:

removed

in src/txorphanage.cpp:294 in 6e57412d51 outdated

286@@ -287,3 +287,10 @@ std::vector<TxOrphanage::OrphanTxBase> TxOrphanage::GetOrphanTransactions() cons
287     }
288     return ret;
289 }
290+
291+std::optional<std::vector<Txid>> TxOrphanage::GetParentTxids(const Wtxid& wtxid)
292+{
293+    const auto it = m_orphans.find(wtxid);
294+    if (it != m_orphans.end()) return it->second.parent_txids;

mzumsande commented at 4:17 pm on December 11, 2024:

Could we assume here that the returned vector isn’t empty? As far as I can see, orphans with no missing parents shouldn’t be possible. (this only seems to break some unit test that don’t set the parent)

glozow commented at 3:36 pm on January 3, 2025:

Fwiw makes sense, but this function doesn’t exist anymore, so marking resolved

in src/txorphanage.h:71 in 6e57412d51 outdated

67@@ -66,6 +68,9 @@ class TxOrphanage {
68      * which peer provided each tx. */
69     std::vector<std::pair<CTransactionRef, NodeId>> GetChildrenFromDifferentPeer(const CTransactionRef& parent, NodeId nodeid) const;
70 
71+    /** Get an orphan's parent_txids, or std::nullopt if the orphan is not present. */

mzumsande commented at 4:23 pm on December 11, 2024:

parent_txids could be updated to txids of missing parents with 1ff1a90baa395d231e7a3d66da74851302090b40

glozow commented at 3:37 pm on January 3, 2025:

Deleted

in src/node/txdownloadman_impl.cpp:251 in a32d396ef2 outdated

240+        // orphan resolution involves at least 1 transaction request which may or may not be
241+        // currently tracked in m_txrequest, so we include that in the count.
242+        if (m_txrequest.Count(nodeid) >= MAX_PEER_TX_ANNOUNCEMENTS) return std::nullopt;
243+    }
244+
245+    std::chrono::seconds delay{0s};

instagibbs commented at 4:43 pm on December 11, 2024:

take or leave suggestion: instead of copying and pasting, make the delay computation re-usable?

 0diff --git a/src/node/txdownloadman_impl.cpp b/src/node/txdownloadman_impl.cpp
 1index 41d1badadf..d6e44c321b 100644
 2--- a/src/node/txdownloadman_impl.cpp
 3+++ b/src/node/txdownloadman_impl.cpp
 4@@ -171,10 +171,28 @@ void TxDownloadManagerImpl::DisconnectedPeer(NodeId nodeid)
 5         m_peer_info.erase(it);
 6     }
 7 
 8 }
 9 
10+std::chrono::seconds TxDownloadManagerImpl::GetTxRequestDelay(NodeId peer, const TxDownloadConnectionInfo& info, const GenTxid& gtxid)
11+{
12+    // Decide the TxRequestTracker parameters for this announcement:
13+    // - "preferred": if fPreferredDownload is set (= outbound, or NetPermissionFlags::NoBan permission)
14+    // - "reqtime": current time plus delays for:
15+    //   - NONPREF_PEER_TX_DELAY for announcements from non-preferred connections
16+    //   - TXID_RELAY_DELAY for txid announcements while wtxid peers are available
17+    //   - OVERLOADED_PEER_TX_DELAY for announcements from peers which have at least
18+    //     MAX_PEER_TX_REQUEST_IN_FLIGHT requests in flight (and don't have NetPermissionFlags::Relay).
19+    auto delay{0s};
20+    if (!info.m_preferred) delay += NONPREF_PEER_TX_DELAY;
21+    if (!gtxid.IsWtxid() && m_num_wtxid_peers > 0) delay += TXID_RELAY_DELAY;
22+    const bool overloaded = !info.m_relay_permissions && m_txrequest.CountInFlight(peer) >= MAX_PEER_TX_REQUEST_IN_FLIGHT;
23+    if (overloaded) delay += OVERLOADED_PEER_TX_DELAY;
24+
25+    return delay;
26+}
27+
28 bool TxDownloadManagerImpl::AddTxAnnouncement(NodeId peer, const GenTxid& gtxid, std::chrono::microseconds now, bool p2p_inv)
29 {
30     // If this is an orphan we are trying to resolve, consider this peer as a orphan resolution candidate instead.
31     // - received as an p2p inv
32     // - is wtxid matching something in orphanage
33@@ -206,24 +224,12 @@ bool TxDownloadManagerImpl::AddTxAnnouncement(NodeId peer, const GenTxid& gtxid,
34     const auto& info = it->second.m_connection_info;
35     if (!info.m_relay_permissions && m_txrequest.Count(peer) >= MAX_PEER_TX_ANNOUNCEMENTS) {
36         // Too many queued announcements for this peer
37         return false;
38     }
39-    // Decide the TxRequestTracker parameters for this announcement:
40-    // - "preferred": if fPreferredDownload is set (= outbound, or NetPermissionFlags::NoBan permission)
41-    // - "reqtime": current time plus delays for:
42-    //   - NONPREF_PEER_TX_DELAY for announcements from non-preferred connections
43-    //   - TXID_RELAY_DELAY for txid announcements while wtxid peers are available
44-    //   - OVERLOADED_PEER_TX_DELAY for announcements from peers which have at least
45-    //     MAX_PEER_TX_REQUEST_IN_FLIGHT requests in flight (and don't have NetPermissionFlags::Relay).
46-    auto delay{0us};
47-    if (!info.m_preferred) delay += NONPREF_PEER_TX_DELAY;
48-    if (!gtxid.IsWtxid() && m_num_wtxid_peers > 0) delay += TXID_RELAY_DELAY;
49-    const bool overloaded = !info.m_relay_permissions && m_txrequest.CountInFlight(peer) >= MAX_PEER_TX_REQUEST_IN_FLIGHT;
50-    if (overloaded) delay += OVERLOADED_PEER_TX_DELAY;
51 
52-    m_txrequest.ReceivedInv(peer, gtxid, info.m_preferred, now + delay);
53+    m_txrequest.ReceivedInv(peer, gtxid, info.m_preferred, now + GetTxRequestDelay(peer, info, gtxid));
54 
55     return false;
56 }
57 
58 std::optional<std::chrono::seconds> TxDownloadManagerImpl::OrphanResolutionCandidate(NodeId nodeid, const Wtxid& orphan_wtxid)
59@@ -240,21 +246,12 @@ std::optional<std::chrono::seconds> TxDownloadManagerImpl::OrphanResolutionCandi
60         // orphan resolution involves at least 1 transaction request which may or may not be
61         // currently tracked in m_txrequest, so we include that in the count.
62         if (m_txrequest.Count(nodeid) >= MAX_PEER_TX_ANNOUNCEMENTS) return std::nullopt;
63     }
64 
65-    std::chrono::seconds delay{0s};
66-    if (!info.m_preferred) delay += NONPREF_PEER_TX_DELAY;
67-    // The orphan wtxid is used, but resolution entails requesting the parents by txid. Sometimes
68-    // parent and child are announced and thus requested around the same time, and we happen to
69-    // receive child sooner. Waiting a few seconds may allow us to cancel the orphan resolution
70-    // request if the parent arrives in that time.
71-    if (m_num_wtxid_peers > 0) delay += TXID_RELAY_DELAY;
72-    const bool overloaded = !info.m_relay_permissions && m_txrequest.CountInFlight(nodeid) >= MAX_PEER_TX_REQUEST_IN_FLIGHT;
73-    if (overloaded) delay += OVERLOADED_PEER_TX_DELAY;
74-
75-    return delay;
76+    // We're fetching parents via txid; so pass in as a txid
77+    return GetTxRequestDelay(nodeid, info, GenTxid::Txid(orphan_wtxid));
78 }
79 
80 std::vector<GenTxid> TxDownloadManagerImpl::GetRequestsToSend(NodeId nodeid, std::chrono::microseconds current_time)
81 {
82     std::vector<GenTxid> requests;
83diff --git a/src/node/txdownloadman_impl.h b/src/node/txdownloadman_impl.h
84index 560802ab5d..0bd673e956 100644
85--- a/src/node/txdownloadman_impl.h
86+++ b/src/node/txdownloadman_impl.h
87@@ -158,10 +158,12 @@ public:
88     bool AlreadyHaveTx(const GenTxid& gtxid, bool include_reconsiderable);
89 
90     void ConnectedPeer(NodeId nodeid, const TxDownloadConnectionInfo& info);
91     void DisconnectedPeer(NodeId nodeid);
92 
93+    std::chrono::seconds GetTxRequestDelay(NodeId peer, const TxDownloadConnectionInfo& info, const GenTxid& gtxid);
94+
95     /** Consider adding this tx hash to txrequest. Should be called whenever a new inv has been received.
96      * Also called internally when a transaction is missing parents so that we can request them.
97      */
98     bool AddTxAnnouncement(NodeId peer, const GenTxid& gtxid, std::chrono::microseconds now, bool p2p_inv);

glozow commented at 3:11 pm on January 3, 2025:

Hm, I don’t really like the part where we cast orphan_wtxid to a Txid to bypass the gtxid.IsWtixd() check, feels a bit hacky. It’s only a few lines. In the future we’d have them deviate if/when we add an alternative method for orphan reso, so gonna leave as is for now.

in src/node/txdownloadman_impl.cpp:433 in a32d396ef2 outdated

438+
439+                // If there is no candidate for orphan resolution, AddTx will not be called. This means
440+                // that if a peer is overloading us with invs and orphans, they will eventually not be
441+                // able to add any more transactions to the orphanage.
442+                add_orphan_reso_candidate(ptx, unique_parents, nodeid, now);
443+                for (const auto& candidate : m_txrequest.GetCandidatePeers(wtxid)) {

instagibbs commented at 4:52 pm on December 11, 2024:

question: since GetCandidatePeers is only used in this context, can we just have it take a transaction ref and fetch both txid and wtxid under the hood?

glozow commented at 3:18 pm on January 3, 2025:

Done

instagibbs approved

instagibbs commented at 4:58 pm on December 11, 2024: member

ACK 40abc3f4f1a2b7c6da657f2cdffd2b61f5b1b91a

non-blocking suggestions only

DrahtBot requested review from dergoegge on Dec 11, 2024

in src/node/txdownloadman_impl.cpp:179 in 5768fc2b6f outdated

172@@ -173,14 +173,14 @@ void TxDownloadManagerImpl::DisconnectedPeer(NodeId nodeid)
173 
174 }
175 
176-bool TxDownloadManagerImpl::AddTxAnnouncement(NodeId peer, const GenTxid& gtxid, std::chrono::microseconds now, bool p2p_inv)
177+bool TxDownloadManagerImpl::AddTxAnnouncement(NodeId peer, const GenTxid& gtxid, std::chrono::microseconds now)
178 {
179     // If this is an orphan we are trying to resolve, consider this peer as a orphan resolution candidate instead.
180     // - received as an p2p inv

mzumsande commented at 7:30 pm on December 11, 2024:

this is now trivially true with 5768fc2b6f82fe43e712947e6f663ef14be23c6f, so maybe remove the line

glozow commented at 3:02 pm on January 3, 2025:

done

in src/node/txdownloadman_impl.cpp:242 in a32d396ef2 outdated

237+    if (!info.m_relay_permissions) {
238+        // This mirrors the delaying and dropping behavior in AddTxAnnouncement in order to preserve
239+        // existing behavior: drop if we are tracking too many invs for this peer already. Each
240+        // orphan resolution involves at least 1 transaction request which may or may not be
241+        // currently tracked in m_txrequest, so we include that in the count.
242+        if (m_txrequest.Count(nodeid) >= MAX_PEER_TX_ANNOUNCEMENTS) return std::nullopt;

mzumsande commented at 7:35 pm on December 11, 2024:

I think we can exceed MAX_PEER_TX_ANNOUNCEMENTS now, because after doing the check, we may add more than 1 parent tx. Is that a problem?

instagibbs commented at 8:57 pm on December 11, 2024:

The fuzzer should theoretically hit this if so, though the limit is probably high enough to make this hard to hit.

glozow commented at 3:02 pm on January 3, 2025:

Yes, added a num_parents param

in src/txorphanage.h:93 in 6e57412d51 outdated

88@@ -84,6 +89,8 @@ class TxOrphanage {
89 protected:
90     struct OrphanTx : public OrphanTxBase {
91         size_t list_pos;
92+        /** Txids of the missing parents to request. Determined by peerman. */
93+        std::vector<Txid> parent_txids;

mzumsande commented at 7:41 pm on December 11, 2024:

FWIW originally I thought I’d prefer calculating the parents when needed instead of storing them - while there might be a few more AlreadyHaveTx calls (is this function particularly expensive?), we’d be operating on more up-to-date data and wouldn’t create tx requests for parents that have already arrived and therefore will never be sent out. Plus, the code will be simpler. (I later saw that there was a short discussion in the review club about this.)

But if we store the missing parents anyway - would it be possible in future work to actually keep them up-to-date, by removing entries from parent_txids in AddChildrenToWorkSet() / Block processing, and only attempting to re-validate the tx once we have all mssing parents / parent_txids is empty - to save us from doing unnecessary work if only one of multiple missing parents has arrived?

glozow commented at 9:03 pm on December 11, 2024:

only attempting to re-validate the tx once we have all mssing parents / parent_txids is empty

That’s a good idea! Especially for 1p1cs 🤔 . We could update parent_txids at the same time as AddChildrenToWorkSet and only add them to workset when empty.

glozow commented at 9:19 pm on December 11, 2024:

Oh, I just had a thought that maybe it’s kind of bad that we’re locked in to the parent_txids we started with… even if we’re able to remove some, what happens if a new parent goes missing?

Get tx that spends [A, B, C]. We are missing inputs A and B. Store in tx orphanage. Request A and B from peers…
C gets replaced* or falls out of mempool somehow
We keep only requesting A and B. We receive and accept them.
AddChildrenToWorkSet… C is still an orphan. We can’t figure out how to resolve it properly though.

So maybe we do this, but also need to update parent_txids on every MempoolRejectedTx TX_MISSING_INPUTS as well.

instagibbs commented at 3:44 pm on December 12, 2024:

Note that also A could immediately be replaced after fetching it, before B is received. There are probably a bunch of ways this and other ancestor fetching can fail.

Even if we manage to recover the entire ancestry tree (like in this example ABC+tx), if C was replaced, we’d likely be relying on general package RBF to have the tx successfully submitted.

That’s a good idea! Especially for 1p1cs 🤔 . We could update parent_txids at the same time as AddChildrenToWorkSet and only add them to workset when empty.

This seems reasonable on its own.

glozow commented at 8:29 pm on December 17, 2024:

Perhaps we start with recalculating every time and consider doing this later? I agree it doesn’t seem too expensive.

glozow commented at 3:37 pm on January 3, 2025:

Changed approach to recalculate every time, and added a test case

mzumsande commented at 8:06 pm on December 11, 2024: contributor

Concept ACK Did a first round of review, mostly comment nits (it’s been a while since I last looked at the orphanage).

in src/txrequest.cpp:577 in 503e52a7fe outdated

573@@ -574,6 +574,17 @@ class TxRequestTracker::Impl {
574         }
575     }
576 
577+    std::vector<NodeId> GetCandidatePeers(const uint256& txhash) const

sipa commented at 10:00 pm on December 11, 2024:

In commit “[txrequest] GetCandidatePeers”

Would it be possible to add an invocation/comparison with this function in the src/test/fuzz/txrequest.cpp fuzz test?

glozow commented at 7:23 pm on January 16, 2025:

Added in #31666

in src/txorphanage.cpp:161 in 9a77d84a56 outdated

163-                // Add this tx to the work set
164-                orphan_work_set.insert(elem->first);
165-                LogDebug(BCLog::TXPACKAGES, "added %s (wtxid=%s) to peer %d workset\n",
166-                         tx.GetHash().ToString(), tx.GetWitnessHash().ToString(), elem->second.fromPeer);
167+                // Belt and suspenders, each orphan should always have at least 1 announcer.
168+                if (!Assume(!elem->second.announcers.empty())) break;

instagibbs commented at 3:48 pm on December 12, 2024:

Why break? Do we not want to try another orphan? We keep trying the other tx’s outpoints regardless.

glozow commented at 3:36 pm on January 3, 2025:

Changed to continue

glozow force-pushed on Jan 3, 2025

glozow commented at 4:35 pm on January 3, 2025: member

Thanks for the reviews @mzumsande @instagibbs! Just got back from holiday, addressed all the comments. Biggest change was recalculating missing parents each time we add a new orphan reso candidate. I also wrote a test for #31397 (review)

DrahtBot added the label CI failed on Jan 3, 2025

sipa commented at 7:23 pm on January 3, 2025: member

I wonder if it’s possible to avoid keeping track of the announcers in m_orphans, as I think it should match m_txrequest.GetCandidatePeers(orphan_tx)?

glozow commented at 7:38 pm on January 3, 2025: member

I wonder if it’s possible to avoid keeping track of the announcers in m_orphans, as I think it should match m_txrequest.GetCandidatePeers(orphan_tx)?

That’s true immediately after receiving the orphan, but we delete the entries from m_txrequest once we’ve added this tx to the orphanage - m_txrequest only stores what we haven’t successfully downloaded yet. So I think we need to store the announcers somewhere else to remember that information, remove candidates that fail to resolve the orphan, and add new candidates if they announce the tx. TxOrphanage seems like the best place for it.

sipa commented at 8:01 pm on January 3, 2025: member

That’s true immediately after receiving the orphan, but we delete the entries from m_txrequest once we’ve added this tx to the orphanage - m_txrequest only stores what we haven’t successfully downloaded yet.

Right, of course!

in src/node/txdownloadman_impl.cpp:335 in a2ab8d2a69 outdated

328@@ -301,14 +329,29 @@ void TxDownloadManagerImpl::MempoolAcceptedTx(const CTransactionRef& tx)
329     m_orphanage.EraseTx(tx->GetWitnessHash());
330 }
331 
332+std::vector<Txid> TxDownloadManagerImpl::GetUniqueParents(const CTransaction& tx)

sipa commented at 8:52 pm on January 3, 2025:

Should this attempt to recurse, and give all ancestors? Not relevant for 1p1c, but in general, in both call sites that seems desirable (an announcement for an orphan should be seen as an announcement for all its ancestors, resolving an orphan means all ancestors can be considered received).

glozow commented at 1:01 pm on January 6, 2025:

Could you elaborate on how we would get missing ancestors beyond parents? We could iterate through the vin of parents we already have, but I don’t see how any of those could be missing. And we can’t look through the vin of a missing parent.

sipa commented at 3:13 pm on January 6, 2025:

Ah, by recursing through transactions in the orphanage I meant.

Imagine a sequence A->B->C (A spends on output of B, B spends an output of C). We have received A and B already (in orphanage), but C is still missing. An announcement from a new peer for transaction A can reasonably be treated as an announcement for C from that peer.

glozow commented at 1:47 pm on January 9, 2025:

Ah I see what you mean, yes!

in src/txrequest.cpp:591 in a2ab8d2a69 outdated

586+            while (it != m_index.get<ByTxHash>().end() && it->m_txhash == txhash) {
587+                if (it->GetState() != State::COMPLETED) result_peers.push_back(it->m_peer);
588+                ++it;
589+            }
590+        }
591+        return result_peers;

sipa commented at 8:54 pm on January 3, 2025:

Should this attempt to deduplicate? Is it possible that we have both an txid and wtxid announcement from the same peer for the same transaction?

glozow commented at 12:57 pm on January 6, 2025:

Yes it’s possible (have a comment “The resulting vector may contain duplicate NodeIds”). The cases I can think of, from least likely to most likely:

the peer announced both txid and wtxid to us (Bitcoin Core wouldn’t do this)
there is a transaction circulating with and without a witness (very rare?)
the tx is announced by wtxid and we are also trying to fetch it by txid because its child is in our orphanage

So I expect duplicates will be very rare. Also, the worst case is that a NodeId appears twice. When there is a deduplicate, we exit at the top of OrphanResolutionCandidate(). This makes me think that attempting to deduplicate may not be worth it?

sipa commented at 8:40 pm on January 6, 2025:

The second isn’t possible today, as no standard transaction output supports spending with both empty and non-empty witnesses (P2A is invalid with non-empty witness; P2WPKH/P2WSH/P2TR are invalid with empty witness).

Indeed, doesn’t seem a big concern. Marking resolved.

in src/txrequest.cpp:587 in a2ab8d2a69 outdated

582+
583+        std::vector<NodeId> result_peers;
584+        for (const uint256& txhash : hashes) {
585+            auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
586+            while (it != m_index.get<ByTxHash>().end() && it->m_txhash == txhash) {
587+                if (it->GetState() != State::COMPLETED) result_peers.push_back(it->m_peer);

sipa commented at 8:58 pm on January 3, 2025:

Since State::COMPLETED is the final state, it’s possible to move this condition into the loop (it->m_txhash == txhash && it->GetState() != State::COMPLETED); hitting COMPLETED means we’re done with that hash.

glozow commented at 1:57 pm on January 6, 2025:

Nice, thanks!

in src/txorphanage.cpp:110 in 25308d05b9 outdated

105@@ -89,9 +106,14 @@ void TxOrphanage::EraseForPeer(NodeId peer)
106     while (iter != m_orphans.end())
107     {
108         // increment to avoid iterator becoming invalid after erasure
109-        const auto& [wtxid, orphan] = *iter++;
110-        if (orphan.fromPeer == peer) {
111-            nErased += EraseTx(wtxid);
112+        auto& [wtxid, orphan] = *iter++;
113+        if (orphan.announcers.contains(peer)) {

sipa commented at 9:25 pm on January 3, 2025:

I think this can be written to avoid a repeated lookup:

0auto orphan_it = orphan.announcers.find(peer);
1if (orphan_it != orphan.announcers.end()) {
2    orphan.announcers.erase(orphan_it);
3    if (orphan.announcers.empty()) {
4        nErased += EraseTx(orphan.tx->GetWitnessHash());
5    }
6}

glozow commented at 1:15 pm on January 6, 2025:

done

in src/txorphanage.cpp:184 in 25308d05b9 outdated

177@@ -152,6 +178,12 @@ bool TxOrphanage::HaveTx(const Wtxid& wtxid) const
178     return m_orphans.count(wtxid);
179 }
180 
181+bool TxOrphanage::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
182+{
183+    auto it = m_orphans.find(wtxid);
184+    return (it != m_orphans.end() && it->second.announcers.count(peer) > 0);

sipa commented at 9:29 pm on January 3, 2025:

Nit: can use contains(peer) instead of count(peer) > 0.

glozow commented at 1:54 pm on January 6, 2025:

thanks, done

in src/txorphanage.cpp:308 in 25308d05b9 outdated

304@@ -273,7 +305,9 @@ std::vector<std::pair<CTransactionRef, NodeId>> TxOrphanage::GetChildrenFromDiff
305     std::vector<std::pair<CTransactionRef, NodeId>> children_found;
306     children_found.reserve(iters.size());
307     for (const auto& child_iter : iters) {
308-        children_found.emplace_back(child_iter->second.tx, child_iter->second.fromPeer);
309+        // Use first peer in announcers list

sipa commented at 9:42 pm on January 3, 2025:

What if the first peer in the announcer list equals nodeid?

EDIT: I see this function is removed in a later commit anyway, so it probably doesn’t matter much.

in src/node/txdownloadman_impl.cpp:191 in d7bc6e841c outdated

185+            std::erase_if(unique_parents, [&](const auto& txid){
186+                return AlreadyHaveTx(GenTxid::Txid(txid), /*include_reconsiderable=*/false);
187+            });
188+
189+            if (auto delay{OrphanResolutionCandidate(peer, Wtxid::FromUint256(gtxid.GetHash()), unique_parents.size())}) {
190+                m_orphanage.AddAnnouncer(Wtxid::FromUint256(gtxid.GetHash()), peer);

sipa commented at 9:51 pm on January 3, 2025:

Is it possible that unique_parents is empty here? I guess that would mean the orphan can be / should have been processed already? If so, should we call AddAnnouncer even?

glozow commented at 2:17 pm on January 6, 2025:

Hm right, I don’t think we can assume that it’s never empty - I’ve added an exit case

in src/node/txdownloadman_impl.cpp:427 in d7bc6e841c outdated

432+                const auto& wtxid = ptx->GetWitnessHash();
433+                // Potentially flip add_extra_compact_tx to false if tx is already in orphanage, which
434+                // means it was already added to vExtraTxnForCompact.
435+                add_extra_compact_tx &= !m_orphanage.HaveTx(wtxid);
436+
437+                auto add_orphan_reso_candidate = [&](const CTransactionRef& orphan_tx, std::vector<Txid> unique_parents, NodeId nodeid, std::chrono::microseconds now) {

sipa commented at 10:06 pm on January 3, 2025:

Pass unique_parents by reference to avoid a copy for each invocation of add_orphan_reso_candidate.

glozow commented at 1:58 pm on January 6, 2025:

Of course, done

in src/node/txdownloadman_impl.cpp:405 in d7bc6e841c outdated

434+                // means it was already added to vExtraTxnForCompact.
435+                add_extra_compact_tx &= !m_orphanage.HaveTx(wtxid);
436+
437+                auto add_orphan_reso_candidate = [&](const CTransactionRef& orphan_tx, std::vector<Txid> unique_parents, NodeId nodeid, std::chrono::microseconds now) {
438+                    const auto& wtxid = orphan_tx->GetWitnessHash();
439+                    if (auto delay{OrphanResolutionCandidate(nodeid, wtxid, unique_parents.size())}) {

sipa commented at 10:07 pm on January 3, 2025:

This logic looks very similar to that in TxDownloadManagerImpl::AddTxAnnouncement. Is it possible to abstract it out?

glozow commented at 2:22 pm on January 6, 2025:

Yes, it is similar. I’m open to code diff suggestions.

I tried a few times to refactor but found some things a bit ugly to work around: we force the IsWtxid check to be false since we’re requesting parents by txid, and the number of requests is not always 1 (also see #31397 (review)). In the future, the function may deviate when we add more per-peer orphan resolution limits and/or another way to do orphan resolution.

sipa commented at 9:43 pm on January 7, 2025:

Something like this?

 0bool TxDownloadManagerImpl::DoOrphanThingRenameMe(const std::vector<Txid>& unique_parents, const Wtxid& wtxid, NodeId nodeid, std::chrono::microseconds now)
 1{
 2    if (auto delay{OrphanResolutionCandidate(nodeid, wtxid, unique_parents.size())}) {
 3        const auto& info = m_peer_info.at(nodeid).m_connection_info;
 4        for (const auto& parent_txid : unique_parents) {
 5            m_txrequest.ReceivedInv(nodeid, GenTxid::Txid(parent_txid), info.m_preferred, now + *delay);
 6        }
 7        LogDebug(BCLog::TXPACKAGES, "added peer=%d as a candidate for resolving orphan %s\n", nodeid, wtxid.ToString());
 8        return true;
 9    }
10    return false;
11}

in add_orphan_reso_candidate:

0if (DoOrphanThingRenameMe(unique_parents, orphan_tx->GetWitnessHash(), nodeid, now)) {
1    m_orphanage.AddTx(orphan_tx, nodeid);
2}

in TxDownloadManagerImpl::AddTxAnnouncement:

0DoOrphanThingRenameMe(unique_parents, Wtxid::FromUint256(gtxid.GetHash()), peer, now);

glozow commented at 7:24 pm on January 16, 2025:

Ah, makes sense - I thought you meant a different bit of code. Added in #31666

sipa commented at 10:10 pm on January 3, 2025: member

Concept ACK, some nits/questions:

[txrequest] GetCandidatePeers

Needed for a later commit adding logic to ask the TxRequestTracker for a
list of announcers.  These announcers should know the parents of the
transaction they announced.

6951ddcefd

[refactor] change type of unique_parents to Txid 62a9ff1870

[txorphanage] support multiple announcers

Add ability to add and track multiple announcers per orphan transaction,
erasing announcers but not the entire orphan.

The tx creation code in orphanage_tests needs to be updated so that each
tx is unique, because the CountOrphans() check assumes that calling
EraseForPeer necessarily means its orphans are deleted.

Unused for now.

e810842acd

[txorphanage] add GetTx so that orphan vin can be read 04448ce32a

[unit test] TxOrphanage EraseForBlock 96c1a822a2

[unit test] multiple orphan announcers 22b023b09d

[fuzz] orphanage multiple announcer functions 163aaf285a

[txdownload] remove unique_parents that we already have

This means we no longer return parents we already have in the
m_unique_parents result from MempoolRejectedTx.

We need to separate the loop that checks AlreadyHave parents from the
loop that adds parents as announcements, because we may do the latter
loop multiple times for different peers.

c6893b0f0b

[refactor] move creation of unique_parents to helper function

This function will be reused in a later commit.

1d2e1d709c

[p2p] try multiple peers for orphan resolution

Co-authored-by: dergoegge <n.goeggi@gmail.com>

b6ea4a9afe

[functional test] orphan handling with multiple announcers 0da693f7e1

[functional test] getorphantxs reflects multiple announcers 063c1324c1

[cleanup] remove p2p_inv from AddTxAnnouncement

This param is no longer needed since orphan parent requests are added to
the TxRequestTracker directly.

f7658d9b14

[p2p] only attempt 1p1c when both txns provided by the same peer

Now that we track all announcers of an orphan, it's not helpful to
consider an orphan provided by a peer that didn't send us this parent.
It can only hurt our chances of finding the right orphan when there are
multiple candidates.

Adapt the 2 tests in p2p_opportunistic_1p1c.py that looked at 1p1c
packages from different peers. Instead of checking that the right peer
is punished, we now check that the package is not submitted. We can't
use the functional test to see that the package was not considered
because the behavior is indistinguishable (except for the logs).

86d7135e36

glozow force-pushed on Jan 6, 2025

DrahtBot removed the label CI failed on Jan 6, 2025

in src/node/txdownloadman_impl.cpp:188 in 86d7135e36

184+            auto unique_parents{GetUniqueParents(*orphan_tx)};
185+            std::erase_if(unique_parents, [&](const auto& txid){
186+                return AlreadyHaveTx(GenTxid::Txid(txid), /*include_reconsiderable=*/false);
187+            });
188+
189+            if (unique_parents.empty()) return true;

marcofleon commented at 7:04 pm on January 7, 2025:

Took me a bit to figure out how this could happen, so a comment might be helpful here.

glozow commented at 1:30 pm on January 16, 2025:

Added a comment in followup ~~and also think we can EraseTx here.~~ (EDIT: realized that was a bad idea, added a comment) See #31666

in src/node/txdownloadman_impl.cpp:369 in 86d7135e36

371-                // We start with all parents, and then remove duplicates below.
372-                unique_parents.push_back(txin.prevout.hash);
373-            }
374-            std::sort(unique_parents.begin(), unique_parents.end());
375-            unique_parents.erase(std::unique(unique_parents.begin(), unique_parents.end()), unique_parents.end());
376+            unique_parents = GetUniqueParents(tx);

marcofleon commented at 7:14 pm on January 7, 2025:

In the loop below this, should it be const Txid& parent_txid? However, if this is more rework of this function than you’re looking to do (adding multiple ToUint256), then seems fine to leave as is for now.

glozow commented at 7:24 pm on January 16, 2025:

I feel like they’re about the same, so going to leave as is

in src/node/txdownloadman_impl.h:195 in 86d7135e36

188@@ -189,6 +189,16 @@ class TxDownloadManagerImpl {
189     void CheckIsEmpty(NodeId nodeid);
190 
191     std::vector<TxOrphanage::OrphanTxBase> GetOrphanTransactions() const;
192+
193+protected:
194+    /** Helper for getting deduplicated vector of Txids in vin. */
195+    std::vector<Txid> GetUniqueParents(const CTransaction& tx);

marcofleon commented at 7:44 pm on January 7, 2025:

nit: This doesn’t use any member variables of TxDownloadManagerImpl so it could be just a standalone helper function in txdownloadman_impl.cpp.

glozow commented at 10:19 pm on January 16, 2025:

Right. Not changing for now because it may be useful to recurse in-orphanage ancestors in this function.

in src/node/txdownloadman_impl.cpp:183 in b6ea4a9afe outdated

178+    // - received as an p2p inv
179+    // - is wtxid matching something in orphanage
180+    // - exists in orphanage
181+    // - peer can be an orphan resolution candidate
182+    if (p2p_inv && gtxid.IsWtxid()) {
183+        if (auto orphan_tx{m_orphanage.GetTx(Wtxid::FromUint256(gtxid.GetHash()))}) {

instagibbs commented at 8:15 pm on January 7, 2025:

0        const auto wtxid{Wtxid::FromUint256(gtxid.GetHash()))};
1        if (auto orphan_tx{m_orphanage.GetTx(wtxid)}) {

and use wtxid below in the other two locations

glozow commented at 7:24 pm on January 16, 2025:

Added in #31666

in test/functional/p2p_orphan_handling.py:778 in 0da693f7e1 outdated

774+        # Replace parent_peekaboo_AB so that is is a newly missing parent.
775+        # Then, replace the replacement so that it can be resubmitted.
776+        node.sendrawtransaction(tx_replacer_BC["hex"])
777+        assert tx_replacer_BC["txid"] in node.getrawmempool()
778+        node.sendrawtransaction(tx_replacer_C["hex"])
779+        assert tx_replacer_BC["txid"] not in node.getrawmempool()

instagibbs commented at 8:21 pm on January 7, 2025:

0        assert parent_peekaboo_AB["txid"] not in node.getrawmempool()
1        assert tx_replacer_BC["txid"] not in node.getrawmempool()

glozow commented at 7:24 pm on January 16, 2025:

Added in #31666

in test/functional/p2p_orphan_handling.py:781 in 0da693f7e1 outdated

777+        assert tx_replacer_BC["txid"] in node.getrawmempool()
778+        node.sendrawtransaction(tx_replacer_C["hex"])
779+        assert tx_replacer_BC["txid"] not in node.getrawmempool()
780+        assert tx_replacer_C["txid"] in node.getrawmempool()
781+
782+        # Second peer is an additional announcer for this orphan

instagibbs commented at 8:26 pm on January 7, 2025:

0        # Second peer is an additional announcer for this orphan with different missing parents than prior announcement

micro-nit something like?

glozow commented at 7:25 pm on January 16, 2025:

Added in #31666

in test/functional/p2p_orphan_handling.py:788 in 0da693f7e1 outdated

784+        peer2.send_and_ping(msg_inv([orphan_inv]))
785+        assert_equal(len(node.getorphantxs(verbosity=2)[0]["from"]), 2)
786+
787+        # Disconnect peer1. peer2 should become the new candidate for orphan resolution.
788+        peer1.peer_disconnect()
789+        node.bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY)

instagibbs commented at 8:28 pm on January 7, 2025:

think this should work too?

0        node.bumpmocktime(TXREQUEST_TIME_SKIP)

glozow commented at 7:25 pm on January 16, 2025:

Added in #31666

marcofleon commented at 8:33 pm on January 7, 2025: contributor

Code review ACK 86d7135e36efd39781cf4c969011df99f0cbb69d

Ran all the relevant tests, including the fuzz tests for about 50 cpu hours each. The implementation here of keeping track of multiple peers that announce an orphan looks good to me. It makes sense to not be locked in to only one peer for orphan resolution, as that peer could disconnect (in which case we lose the orphan) or be malicious.

Just left some non-blocking nits below.

Also quick question for my own understanding. Is it true that in the honest case, orphan resolution will probably happen with the first peer that announced it to us? The peer should have the ancestors, so those txs should be sent shortly after the orphan tx was received by us, right?

DrahtBot requested review from instagibbs on Jan 7, 2025

DrahtBot requested review from sipa on Jan 7, 2025

DrahtBot requested review from mzumsande on Jan 7, 2025

instagibbs approved

instagibbs commented at 8:36 pm on January 7, 2025: member

reACK 86d7135e36efd39781cf4c969011df99f0cbb69d

feel completely ok to ignore all my comments

Major change is recomputing the missing parents per announcement of orphan, rather than a static list for the lifetime of the orphan when first received, and also correctly accounting for those missing parents when deciding when to rate-limit the announcements for a specific peer..

instagibbs commented at 8:43 pm on January 7, 2025: member

@marcofleon

Also quick question for my own understanding. Is it true that in the honest case, orphan resolution will probably happen with the first peer that announced it to us?

It Depends(TM). If the first announcer was an inbound connection and second was an outbound connection less than 2(?) seconds later, the outbound will be chosen first. see the functional test case test_orphan_handling_prefer_outbound

dergoegge approved

dergoegge commented at 10:29 am on January 13, 2025: member

Code review ACK 86d7135e36efd39781cf4c969011df99f0cbb69d

Other reviewers already mentioned the nits that I would have had as well. I think they are fine to address in a follow up.

mzumsande commented at 9:47 pm on January 15, 2025: contributor

ACK 86d7135e36efd39781cf4c969011df99f0cbb69d

I reviewed the code and tested it a bit on mainnet with some extra logging: The large majority of orphans gets resolved, a few orphans get stuck for 20 minutes if all of our candidates send NOTFOUNDs for the parent requests, presumably because the parent got removed from their mempools (this has been mentioned in #31397 (comment) ).

in src/txorphanage.cpp:166 in e810842acd outdated

168+                // Belt and suspenders, each orphan should always have at least 1 announcer.
169+                if (!Assume(!elem->second.announcers.empty())) continue;
170+                for (const auto announcer: elem->second.announcers) {
171+                    // Get this source peer's work set, emplacing an empty set if it didn't exist
172+                    // (note: if this peer wasn't still connected, we would have removed the orphan tx already)
173+                    std::set<Wtxid>& orphan_work_set = m_peer_work_set.try_emplace(announcer).first->second;

mzumsande commented at 2:00 am on January 16, 2025:

It seem a bit redundant to add the tx to more than one workset. Either we have all the parents now or we don’t, so I don’t see a point in attempting to validate it multiple times. Assigning it to just one peer work set would run the risk of that peer disconnecting just after we assigned it to them, but that could be prevented by adding a last call to ProcessOrphanTx() in FinalizeNode() .

On the other hand, checking if we have all parents is probably cheap enough that it doesn’t really matter either way?!

glozow commented at 7:19 pm on January 16, 2025:

Good point. I seem to recall drafting a version that randomly selected 1 peer. That maybe saves us from a peer purposefully disconnecting (since they don’t know whether we assigned them), but doesn’t have this redundancy problem? What do you think?

mzumsande commented at 7:42 pm on January 16, 2025:

Yes, taking a random peer would be ok. Though I kinda like the idea of calling ProcessOrphanTx() in FinalizeNode() in general, even if just 1 peer is involved - this is scheduled work that is assigned to but doesn’t need any input from the peer, so there is no reason not do it just because the peer decides to disconnect at the wrong time.

glozow commented at 9:54 pm on January 16, 2025:

I like that idea too. But what if there is a large amount of orphans left? There shouldn’t be a ton, but I don’t know how to feel about a peer being granted more than the normal amount of compute because they are going to be disconnected.

mzumsande commented at 4:38 pm on January 17, 2025:

Right, withProcessOrphanTx() doing at most one actual validation, it would probably not be good to call it in a loop until all outstanding work is done. Maybe calling it just once (as if it was this peer’s next turn) would already help in most cases, but to find out it’d probably be best to get some empirical data from mainnet.

fanquake merged this on Jan 16, 2025

fanquake closed this on Jan 16, 2025

in test/functional/p2p_orphan_handling.py:62 in 86d7135e36

57@@ -58,6 +58,10 @@ def wrapper(self):
58             self.generate(self.nodes[0], 1)
59             self.nodes[0].disconnect_p2ps()
60             self.nodes[0].bumpmocktime(LONG_TIME_SKIP)
61+            # Check that mempool and orphanage have been cleared
62+            assert_equal(0, len(self.nodes[0].getorphantxs()))

maflcko commented at 3:18 pm on January 16, 2025:

Looks like this fails CI https://cirrus-ci.com/task/4584274617171968?logs=ci#L2784:

 0[15:13:20.370]  test  2025-01-16T15:13:19.950000Z TestFramework (ERROR): Assertion failed 
 1[15:13:20.370]                                    Traceback (most recent call last):
 2[15:13:20.370]                                      File "/ci_container_base/test/functional/test_framework/test_framework.py", line 135, in main
 3[15:13:20.370]                                        self.run_test()
 4[15:13:20.370]                                      File "/ci_container_base/ci/scratch/build-x86_64-pc-linux-gnu/test/functional/p2p_orphan_handling.py", line 812, in run_test
 5[15:13:20.370]                                        self.test_orphan_of_orphan()
 6[15:13:20.370]                                      File "/ci_container_base/ci/scratch/build-x86_64-pc-linux-gnu/test/functional/p2p_orphan_handling.py", line 62, in wrapper
 7[15:13:20.370]                                        assert_equal(0, len(self.nodes[0].getorphantxs()))
 8[15:13:20.370]                                      File "/ci_container_base/test/functional/test_framework/util.py", line 77, in assert_equal
 9[15:13:20.370]                                        raise AssertionError("not(%s)" % " == ".join(str(arg) for arg in (thing1, thing2) + args))
10[15:13:20.370]                                    AssertionError: not(0 == 2)

instagibbs commented at 3:19 pm on January 16, 2025:

wait until?

glozow commented at 4:06 pm on January 16, 2025:

yes, I think it needs to be a wait_until

glozow commented at 6:58 pm on January 16, 2025:

#31675

glozow deleted the branch on Jan 16, 2025

glozow commented at 10:18 pm on January 16, 2025: member

Followup #31666 wraps up all the comments here except for 2 things which might be a little more involved:

#31397 (review) (because we need to add a txid index) #31397 (review)

TheCharlatan referenced this in commit 230a439a4a on Jan 17, 2025

p2p: track and use all potential peers for orphan resolution #31397

Code Coverage & Benchmarks

Reviews

Conflicts