Overhaul transaction request logic #19988

0 * - Whether it's from a "preferred" peer or not (outbound and noban peers are preferred).

style-nit: Would be good to mention the exact permission flag, because legacy whitelisted is discouraged, has been deprecated, and might be removed some time in the future.

(Same below)

I’d like to keep txrequest mostly about the decision logic and data structure, while leaving net_processing responsible for the actual policy choices (“what delays are given to which peers/requests”, “what timeouts are used”, “when exactly is a peer considered preferred”, “when exactly is a peer considered overloaded”, “how many announcements can be tracked per peer”).

Of course, the explanation here is ideally as comprehensive as possible and not full of “See some random comment in net_processing for the details” references. Still, do you think it would be reasonable to say instead:

Whether it’s from a “preferred” peer or not (what that means is up to the caller, but this is designed to correspond mostly to outbound peers, or others that are more trusted)

?

Apparently that’s not actually a 128-bit type ;)

Fixed.

Isn’t this exactly the same performance as having a subclass and making the methods virtual, except with all the dispatching written out explicitly? ie, could instead write something like:

 0class TxRequestTracker
 1{
 2protected:
 3    TxRequestTracker() { } // pure virtual class, must instantiate via subclass
 4public:
 5    virtual ~TxRequestTracker();
 6    virtual void DeletedPeer(uint64_t peer) = 0;
 7    ...
 8};
 9std::unique_ptr<TxRequestTracker> CreateTxRequestTracker(bool deterministic = false);
10
11static std::unique_ptr<TxRequestTracker> g_txrequest = CreateTxRequestTracker() GUARDED_BY(cs_main);

then hide the subclass in txrequest.cpp? Of course, “exactly the same” means no objective reason to prefer changing to this.

It’s not exactly the same, I think. Calling member functions on a TxRequestTracker would incur a lookup in the vtable to find the code to execute. The current solution has link-time determined code flow, and only an extra indirection to find the object’s storage.

I don’t think either is remotely relevant for performance here, and the subclass approach you suggest is probably somewhat lighter syntactically. I’m happy to change it if other reviewers agree.

Does anything limit the size of the returned vector? I think the main constraints are those in net_processing.cpp:RequestTx which could leave as many as 100k entries in CANDIDATE state for a given peer, so this could be a 4MB vector, which seems like it might be larger than desirable?

It’s also constrained by how many txs can be INVed by a peer inbetween calls to GetRequestable, so in normal circumstances I’d expect this to be perfectly fine. I think you could get the worst case by quickly sending two max-size INV messages and two max-size NOTFOUND messages once the first request comes in.

(I think this has to return a copy of the data items, because you want to iterate over them and request them, which would then modify the data structure, and that would invalidate the iterator you were using if you hadn’t made a copy)

Renamed to PostGetRequestableSanityCheck, and updated comment.

It’s not just a consistency check of request times.

With MAX_PEER_TX_ANNOUNCEMENTS reduced, is that still needed?

I’m a bit hesitant about this, as the number of announcements tracked for a peer is somewhat dependent on other peers’ behavior.

Yes, I think this would be an improvement for encapsulation and for being explicit about when the TxRequestManager is constructed/destructed. It’s my understanding that global static objects can be constructed before main() or later.

There isn’t any requirement to wait for mapNodeState to move to PeerManager.

I have a branch that moves TxRequestTracker and RequestTx() to be members of PeerManager here: https://github.com/jnewbery/bitcoin/tree/pr19988.1. The move is in a separate commit in that branch for ease of review, but should be squashed into Change transaction request logic to use txrequest.

Consider using the default syntax to indicate that you only included this in the cpp file so the m_impl unique ptr can be destructed:

0TxRequestTracker::~TxRequestTracker() = default;

It looks like this is only in the header so that the unit and fuzz tests can call GetPriorityComputer() and get the computer, and the only reason they do that is so they can call PriorityComputer::operator()().

Could you move all this to the implementation file, and add a public method ComputePriority to by used by the tests that calculates the priority internally and returns it?

Consider using an initializer list here instead of setting m_impl in the ctor function body.

If you did that, you could make m_impl const, which is fine since you’ve deleted the move constructor and assignment.

const unique_ptr communicates that this m_impl is always the object that TxRequestTracker owns. See Herb Sutter’s Leak-Freedom talk at https://youtu.be/JfmTagWcqoE?t=571

 0diff --git a/src/txrequest.cpp b/src/txrequest.cpp
 1index f6c387f8f4..b7d90a1ba5 100644
 2--- a/src/txrequest.cpp
 3+++ b/src/txrequest.cpp
 4@@ -668,10 +668,8 @@ public:
 5     }
 6 };
 7 
 8-TxRequestTracker::TxRequestTracker(bool deterministic)
 9-{
10-    m_impl = MakeUnique<TxRequestTracker::Impl>(deterministic);
11-}
12+TxRequestTracker::TxRequestTracker(bool deterministic) :
13+    m_impl{MakeUnique<TxRequestTracker::Impl>(deterministic)} {}
14 
15 TxRequestTracker::~TxRequestTracker() {}
16 
17diff --git a/src/txrequest.h b/src/txrequest.h
18index 6e892eebe1..83f6dbe2fe 100644
19--- a/src/txrequest.h
20+++ b/src/txrequest.h
21@@ -119,7 +119,7 @@ public:
22 private:
23     // Avoid littering this header file with implementation details.
24     class Impl;
25-    std::unique_ptr<Impl> m_impl;
26+    const std::unique_ptr<Impl> m_impl;
27 
28 public:
29     //! Construct a TxRequestTracker.

Deleted(past tense) is a bit weird since it’s actually deleting the peer.

At a risk of making it too verbose via self-documenting: DeletePeerEntries?

Alternatively we can name it like some of the other functions e.g. ReceivedInv et. al: DisconnectedPeer describing when it’s to be called and leaving the first sentence in the comment.

Ah, my thinking behind the name was the caller informing TxRequestTracker “Hey I have deleted peer X, you may want to forget about them”.

DisconnectedPeer sounds better.

COMPLETED sounds more like FAILED.

COMPLETED is also hit when the transaction is received properly, no?

0    std::vector<GenTxid> ExpireReqestedAndGetRequestable(uint64_t peer, std::chrono::microseconds now);

to make it less reliant on comments for intent

I’m not entirely sure, as the caller really doesn’t care about the fact that it also expires things. It just wants to know what should be requested.

It’s not an implementation detail, as the effect of expiration is observable (CountInFlight, CountTracked() and Size() go down), but I think that makes just specification details rather than the caller’s intent.

Wouldn’t hurt to make this block not publicly callable somehow.

Just an idea in case it’s not crazy: https://stackoverflow.com/a/23267346

My hope here was that making TxRequestTracker deal solely with GenTxids would simplify the interface. The caller just has these gtxids that it hands to TxRequestTracker, and gets gtxids back. The idea was that the knowledge about when the is_wtxid flag mattered in certain contexts could be restricted to TxRequestTracker. I don’t this idea really works. This optimization (in “Expedite removal”) specifically breaks it: it’s calling ForgetTx in a situation where we actually don’t have the tx already, relying on the fact that if txid and wtxid differ, it must be a witness transaction, and thus we certainly don’t need other transactions with the same witness.

I think there are two solutions to it:

• Add to ForgetTx logic that if a txid is provided, it deletes both txid and wtxid announcements, but if a wtxid is provided only wtxid announcements are deleted. This would avoid some of the complexity here in net_processing, but technically break the amortized O(1) complexity claim - you could call ForgetTx(wtxid) repeatedly, and it would every time consume time proportional to the number of txid announcements with the same hash.
• Give up on the perfect abstraction, and just make ForgetTx take a txhash (and rename it to ForgetTxHash, I guess).

Ok, I’ve looked into this more, and I believe the code looks a lot better with ForgetTxHash that just takes a uint256. This means the caller needs to understand the semantics for when calling with a txid/wtxid is fine, but that was the case already - just less obviously so. So I’ve switched the code to that.

I’ve also removed the “if (txid != wtxid) ForgetTx(wtxid);” optimization. I think it’s equivalent to just calling ForgetTxHash now with whatever is added to mempool/orphanpool/recentrejects, and the latter is far more obviously correct anyway (these things will be treated as AlreadyHaveTx() anyway, so deleting them early isn’t going to change anything).

Maybe “chose the first (non-overloaded) peer to have announced the transaction (managed by the “first” marker, see below)” would be a better description – ie focus on the aim, rather than the mechanism?

Might make sense to follow the “Rationale: in non-attack scenarios…” with “This is implemented via using a “first” marker, with the following rules:” rather than having those rules be in a separate section a bit lower.

“The “first” marker is given to announcements for which at the time they are received:” -> “given to announcements at the time they are received, provided:” might be clearer?

“(within the class of preferred or non-preferred announcements)” – everywhere else refers to preferred peers, not announcements. Might make sense to explicitly clarify that a peer may switch its preferred status at any time, but that preferred status is sticky to announcements so if a peer is now non-preferred earlier announcements when it was preferred will still be prioritised, and vice-versa? I think that scenario is exercised by the fuzzer but not by net_processing?

Done, and addressed the “preferredness” being changeable in the first section.

You’re right that fuzzer tests this, but isn’t reachable through the current net_processing layer.

I’m pretty sure it was needed at some point.

I’ve added an Iter type alias as suggested (outside of Impl, yay).

The comments in txrequest.h are great. I feel like txrequest.cpp could use more though – there’s no real overview of how the optimised data structures are laid out though, and what the deeper invariants are. Maybe it would make sense to use the SanityCheck functions as a way of documenting them? Many of the comments are already there and sufficient, but maybe make it the first function in the class, and make it a bit more readable? If you construct the Counts and PeerInfo maps in separate, static GenSanityCheckFoo functions, what’s left seems pretty close to documentation:

 0// m_peerinfo can be exactly recalculated from the Index.
 1//
 2// This verifies the data in it, including the invariant
 3// that no entries with m_total_announcements==0 exist.
 4assert(m_peerinfo == GenSanityCheckPeerInfo(m_index));
 5
 6for (auto& el : GenSanityCheckCounts(m_index, m_computer)) {
 7    const uint256& hash = el.first;
 8    Counts& c = el.second;
 9    // Cannot have only COMPLETED peers (txid should have been deleted)
10    assert(c.m_candidate_delayed + c.m_candidate_ready + c.m_candidate_best + c.m_requested > 0);

I think using .CountInFlight() isn’t actually the right way to determine being overloaded. If a peer dumps 5000 INVs on us at once, they’ll all be inserted at a time when inflight==0, and thus all be eligible to get the “first” marker, and won’t get any delay penalty.

I’m not sure the original behaviour didn’t make more sense? If you have a peer that drops 5000 INVs at once, then gets requests for all of them 2s later, and replies to all those requests before sending any further INVs, is there any reason to consider that peer to be overloaded?

I think we’re not worrying about attackers getting the “first” flag – that’s addressed by limiting the impact to one attacker per txid – but even if we were, I don’t think this makes sense as an attack? You’re blocking 5000 txs for a single 60 second period, but your other peers are only going to announce ~1000 txs each over that period, and you have to successfully race them to be the first to announce the tx for it to matter. But if you’re able to ensure you announce first, then all you need to do is announce first by 2-6 seconds, and you delay a request from honest peers by 54-58 seconds rather than 60 seconds?

OTOH, I don’t think delaying a huge batch of 4900 txs by (an additional) 2s is much of a problem either.

Either way, it may make sense for noban or relay permission to override considering a peer to be overloaded?

The reason I don’t like using just in-flight is that it has this strong dependency on local ordering of events.

If you receive 100 INVs, then do a round of SendMessages, and request them, followed by 4900 of them, they get punished (no first, penalty OVERLOADED_PEER_TX_DELAY).

If you receive 100 INVs, then 4900 INVs, and then do a round of SendMessages, they don’t get punished.

I think we’re not worrying about attackers getting the “first” flag

Only minimally, but I think we are. There are plenty of spy peers that do weird things, and if they announce abundantly, they can interfere somewhat with ordering of dependent transactions (after the first request, they go out randomly, so parents and children may go to different peers, and the parent may arrive first).

OTOH, I don’t think delaying a huge batch of 4900 txs by (an additional) 2s is much of a problem either.

Judging by actual numbers, having 100 candidates simultaneously for any non-obviously-broken-peer basically doesn’t happen.

Either way, it may make sense for noban or relay permission to override considering a peer to be overloaded?

Yes, that may be a good idea.

Only minimally, but I think we are. There are plenty of spy peers that do weird things, and if they announce abundantly, they can interfere somewhat with ordering of dependent transactions (after the first request, they go out randomly, so parents and children may go to different peers, and the parent may arrive first).

Judging by actual numbers, having 100 candidates simultaneously for any non-obviously-broken-peer basically doesn’t happen.

Hmm. With the new change you could kind-of make that happen:

• find a victim who is an inbound connection
• make up 100 transactions
• INV them to your victim, but don’t respond to their GETDATA
• send the 100 transactions to everyone else
• everyone else will announce to victim
• all victims peers have 100+ CANDIDATE_* announcements, making all victim’s peers appear overloaded for the next real transaction that comes along

(That said, I’m still not really seeing how being falsely marked as “overloaded” is a problem)

If you receive 100 INVs, then do a round of SendMessages, and request them, followed by 4900 of them, they get punished … If you receive 100 INVs, then 4900 INVs, and then do a round of SendMessages, they don’t get punished.

Yeah. I’m looking at that as: “If you request 100 INVs, and then receive 4900 more INVs before receiving a response to your request, then the peer is overloaded” and “If all your requests have been responded too and you receive 4900 more INVs, then you don’t have a reason to think the peer is overloaded”. ie, “overloaded” == “am I getting responses, or am I just getting more and more announcements?” I think that means the peer is able to prioritise “respond to GETDATA” above “forward on more INVs” and thus ensure they’re never overloaded, even if they’re announcing txs in massive bursts, no matter what anyone else is doing (except when they do two large INVs in less than the RTT maybe).

That’s a pretty convincing argument.

If we assume that getting the “overloaded” treatment is relevant at all, it seems worse that an attacker can cause it to occur in “third party” connections than possibly missing out on getting that effect himself.

I also don’t see how a large at-once dump can be at all exploited. It means an attacker needs an excessive amount of transactions to begin with. If those are bogus/invalid or self-generated ones, the first marker has no effect as only attacker nodes will have it. If they’re valid under-attack transactions, it means there is something seriously wrong already that such a batch of transactions is being propagated (remember the max tx rate of INVs…), and the first marker isn’t going to change much.

I’m going to revert this change.

Either way, it may make sense for noban or relay permission to override considering a peer to be overloaded?

Also done.

I wonder if it wouldn’t make more sense to move the overloaded judgement entirely into ReceivedInv and instead pass the peer’s MAX_PEER_TX_LOAD in and have OVERLOADED_PEER_TX_DELAY passed in when constructingm_txrequest. So ReceivedInv would then do if (CountLoad(peer) > max_load) { first = false; reqtime += m_overloaded_delay; }.

The reason I say that is I think the “first” marker logic doesn’t really make sense if you don’t bump the reqtime for overloaded peers – you’d end up with the overloaded peer being selected while the first non-overloaded peer was still waiting for its reqtime to arrive.

The !preferred delay could also be handled the same way. I guess you’d need to pass in current_time and peer_delay = TXID_RELAY_DELAY (when appropriate) (so to speak) for that work. Again, there needs to be a positive delay for !preferred peers or the logic won’t work right, and while it can vary amongst announcements in limited ways without breaking things, I think it would be hard to do that correctly, so being set at the txrequest level wouldn’t be a big problem.

That might also have the advantage of being able to pass in delay == 0 rather than reqtime == microseconds::min() which seems a little bit more obvious.

I did this at first, but I like the current approach a lot more. It leaves the actual policy decisions inside net_processing, without needing configuration flags etc. in the txrequest interface.

Not a very strong opinion, but I like the fact that txrequest is mostly the data structure, and its responsibility is consistency and efficiency - not policy parameters. There are currently a lot of future improvements that can be made without changing txrequest - and that due to the nature of its current interface - are already covered by fuzz testing.

There are currently a lot of future improvements that can be made without changing txrequest - and that due to the nature of its current interface are already covered by fuzz testing.

Kind-of? I would have said the fuzz testing only really tests the optimisations work; it doesn’t really check that the basic implementation makes “sense”?

eg, we could check the “don’t request dependent transactions out of order” goal by adding a constraint that all peers announce tx i prior to tx j, and then checking that tx i is requested before tx j, but I think that would currently fail in the fuzzer due to random delays (and also fail in net_processing in rare cases, eg where a tx is only announced by one node, j is announced less than 2 seconds after i and the node becomes non-overloaded in that same period, or where all the non-wtxid-relay peers disappear in between).

I’m trying out some logging to see if the “first” marker actually does much good in practice. We’re calling GetRequestable/RequestedTx ten times a second for every peer (provided various queues don’t fill up anyway), so I think you’d have to be pretty unlucky for it to even matter.

 0--- a/src/txrequest.cpp
 1+++ b/src/txrequest.cpp
 2@@ -528,6 +528,29 @@ public:
 3         // in between, which preserve the state of other GenTxids).
 4         assert(it != m_index.get<ByPeer>().end());
 5         assert(it->GetState() == State::CANDIDATE_BEST);
 6+       {
 7+            auto bytxhashit = m_index.project<ByTxHash>(it);
 8+            auto bytxhashit_pre = bytxhashit;
 9+           int delayed = 0;
10+           int candidates = 0;
11+           while (bytxhashit_pre != m_index.get<ByTxHash>().begin()) {
12+               --bytxhashit_pre;
13+               if (bytxhashit_pre->GetState() != State::CANDIDATE_DELAYED || bytxhashit->m_txhash != it->m_txhash) break;
14+               ++delayed;
15+           }
16+           ++bytxhashit;
17+           while (bytxhashit != m_index.get<ByTxHash>().end() && bytxhashit->GetState() != State::COMPLETED && bytxhashit->m_txhash == it->m_txhash) {
18+               ++candidates;
19+               ++bytxhashit;
20+           }
21+           int completed = 0;
22+           while (bytxhashit != m_index.get<ByTxHash>().end() && bytxhashit->GetState() == State::COMPLETED && bytxhashit->m_txhash == it->m_txhash) {
23+               ++completed;
24+               ++bytxhashit;
25+           }
26+           assert(bytxhashit == m_index.get<ByTxHash>().end() || bytxhashit->m_txhash != it->m_txhash);
27+           LogPrintf("ABCD requested txid=%s preferred=%d first=%d delayed=%d candidates=%d completed=%d peer=%d\n", it->m_txhash.ToString(), it->m_preferred, it->m_first, delayed, candidates, completed, it->m_peer);
28+       }
29         Modify<ByPeer>(it, [expiry](Entry& entry) {
30             entry.SetState(State::REQUESTED);
31             entry.m_time = expiry;

After running it for a few minutes with ~20 peers, only 0.17% of requests actually had other announcements in CANDIDATE_READY, so for 99.82% of txs the first marker didn’t make any difference. About 1.6% of requests weren’t for a “first” marked announcement (a tor outbound managed to overload itself I think). Will let it go ’til it fills up the disk with logs or whatever, and see what it looks like then.

Kind-of? I would have said the fuzz testing only really tests the optimisations work; it doesn’t really check that the basic implementation makes “sense”?

Yeah, kind of.

The fuzz test only verifies consistency of the optimized data structure, and observational equivalence with the naive reimplementation. That naive reimplementation is hopefully close enough to the written specification in txrequest.h that we can say the test actually correctness according to the specification. It however does not test whether that specification actually results in desirable high-level behavior. That’s what the scenario unit tests are for, but they’re not nearly as detailed.

Still, as far as the specification goes, by keeping the policy out of txrequest and it tests, there is evidence that the data structure correctly implements it, and this doesn’t depend on coincidences like “non-preferred requests always have a reqtime in the future” that are currently true, but maybe won’t always be true. The interface doesn’t force such relations, so the fuzz tests should be covering both situations where they do and don’t hold.

Furthermore, I’m not sure there is much of a simplification in the interface that can be made by moving more into txrequest?

• Right now: ReceivedInv(peer, gtxid, preferred, overloaded, reqtime).
• Potentially: ReceivedInv(peer, gtxid, preferred, have_wtxid_peers, current_time).
• With the addition of bypassing overloaded under PF_RELAY you’d need to pass an additional argument pf_relay_peer argument even.

The fact that this last change could be made by just changing the parameters to ReceivedInv and not changing the interface - or the fuzz tests - is argument in favor of it, IMO.

Several potential changes like making delays dynamic in function of load/inflight, or adding randomness to it, are equally possible without impacting txrequest.

Yeah, agree with what you wrote. (Well, I was thinking you’d call ReceivedInv(peer, gtxid, preferred, max_load, current_time) and pass max_load=max() to bypass overloaded, fwiw)

I’m more thinking of the API in terms of what the caller has to do to ensure the txrequest modules behaves “sensibly” – avoids requesting txs out of order, avoiding double requesting a tx, etc. If there’s a way to make txrequest behave “sensibly” no matter how you call the API, that might be better than just documenting the expectations, or the consequences of violating the expectations. But I don’t fully understand what sensibly means or what restrictions that implies yet.

I see what you mean now.

There is no strict reason why we couldn’t have both. There could a class around TxRequestTracker that adds the policy and sanity checking of inputs, which just forwards to the inner TxRequestTracker. That would let the inner part still be tested for consistency, while permitting testing of the higher level construct for higher level “goal” properties.

As the logic in that outer layer would just be (part of) what is now in TxRequest(), I don’t think this is worth it - but maybe at some point it is.

Okay, so I’ve run some stats on this now. Results (for me) after just under 230k calls to RequestedTx are:

• in 77.9% of cases, it’s requesting the tx from a preferred peer, with no alternative (non-delayed) candidates
• in 18.2% of cases, it’s requesting the tx from a non-preferred peer, with no alternative (n-d) candidates
• in 1.3% of cases, it’s requesting the tx from a preferred peer, with the only (n-d) alternative candidates being non-preferred peers
• in 1.1% of cases, it’s requesting the tx from a preferred peer using the first marker, and other preferred candidates are available (!)
• in 1.0% of cases, it’s requesting the tx from a non-preferred peer using the first marker, with other non-preferred candidates available (and no preferred candidates available) (!)
• in 0.2% of cases, it’s requesting the tx from a non-preferred peer using random selection
• in 0.02% of cases, it’s requesting the tx from a non-preferred peer using random selection

(The remaining ~0.3% I didn’t sort through)

This implies that the first marker is only relevant in ~2.1% of cases – the rest of the time it’s determined by the first peer’s reqtime being reached at a call to GetRequestable() prior to any other announcement for that tx. That occurs because (unless I’ve missed something) we’re calling GetRequestable() for each peer about ten times per second (100ms delay in CConnman::ThreadMessageHandler between calls to SendMessages(pnode)), which means the “first” marker only matters for preferred nodes when the first two preferred nodes to announce a tx manage to both set their reqtimes in the same ~100ms period and thus get activated in the same call the GetRequestable.

I think what the “first” marker is actually doing is slightly different to what I was kind-of expecting. ie, “reqtime” and “preferredness” is almost always what’s used to actually choose which announcement to request first, and the “first” marker is a backup. It’s only relevant when (a) txrequest is used less frequently than every 100ms via some other implementation, (b) the 100ms delay is extended, eg due to cs_main being held while adding a new block or something, or (c) there’s a race and we want a consistent tie-breaker.

I haven’t instrumented it, but I’m not convinced this does much for dependent transactions. Assuming B spends an output of A, and peers P and Q both announce A prior to B, you could still see announcements as {Q:A, P:A, P:B} then call GetRequestable(P) and have A assigned to Q and B assigned to P, and requested immediately, with A requested from Q moments later. But if that’s not a big problem, what’s the advantage in locking A to Q via the “first” marker?

As it stands, I want to argue that the “first” marker is an unnecessary complication, and maybe we should remove it. But I’m not really convinced – for one, that claim relies on calling GetRequestable very frequently, and maybe we want the flexibility to not do that? But if we called it for a given peer once a second instead of 10x a second, that adds another 0.5s delay on average to requesting a tx, which is pretty significant compared to the existing delays, so maybe relying on calling GetRequetable frequently is perfectly reasonable?

That’s great data, and perhaps not very surprising: we’d hope to pick good peers as outbounds, so most announcements will come in from preferred peers (and even more within the first 2s after the first announcement from inbound connections). As we fetch immediately from preferred connections in general, the “first” marker shouldn’t do much.

Given that information, perhaps I wouldn’t have added this to the first iteration of this logic. Now that it’s implemented, I could argue that it may improve robustness in some cases:

• During the rollout of BIP339, we can expect to see many more transactions fetched from delayed (but possibly preferred) peers, as just one wtxid peer will cause a delay on all announcements from other peers. It’s hard to predict/measure what the impact of this will be.
• I can imagine we’d add (possibly random) delays even from fetches from preferred peers, for privacy reasons.
• Very well connected nodes (with way more inbound than outbound nodes) may see a larger percentage fetched from non-preferred connections.

I think all those cases would just change the distribution between the cases where the “first” marker doesn’t matter – ie they’re entirely determined by reqtime and preferredness.

I do think it might improve robustness somewhere though…

Also, if, in the future, we changed the code to either update current_time less, or to target specific reqtimes (“anything between t=0.0 and t=0.499 will be requested at t=1.234”), it might start mattering

During the rollout of BIP339, we can expect to see many more transactions fetched from delayed (but possibly preferred) peers, as just one wtxid peer will cause a delay on all announcements from other peers.

That’s a good point! I’ve restarted my node since the above numbers, and don’t have any logging as to whether any of them were wtxidrelay. However post-restart, I have two inbound wtxidrelay peers, so should already be suffering from BIP339 rollout. And I guess that means all my preferred nodes should be degraded to the same priority as the non-preferred wtxid nodes, which in turn probably explains why I got such a high percentage of non-preferred announcements as the very first request for a txid.

Yeah, collecting RequestedTx calls by peerid and whether they were preferred or not gives me:

• 1049 preferred=0 peer=2717
• 1500 preferred=0 peer=3993
• 3255 preferred=0 peer=3815
• 3270 preferred=1 peer=13
• 14216 preferred=1 peer=15
• 14651 preferred=1 peer=14
• 16918 preferred=1 peer=11
• 18635 preferred=1 peer=2
• 30675 preferred=0 peer=1163
• 37776 preferred=1 peer=1
• 39962 preferred=1 peer=16
• 52112 preferred=1 peer=0

(ignoring peers with under 1k requests). Which looks to me like the top 9 peers include the 8 outbounds I connected to initially, and a random inbound wtxidrelay peer which connected about 3h after my peer was restarted. That single node accounts for about 2/3rds of the “18.2% of cases” by the looks.

So I might desable wtxidrelay, and restart my node again, I think, which ironically seems like the easiest way to simulate an all-wtxid-relay world…

Ok, updated stats based on 257k RequestedTx calls with wtxidrelay disabled (added a false && to the if’s in net_processing)

I’m seeing 98.04% of requests being trivial cases – there’s no alternatives that have hit reqtime, and this is the first request of a tx. Despite having lots of (up to ~50?) inbounds, it’s still choosing outbounds for almost all txs.

Preferredness only mattered in 0.67% of cases, and only in 0.59% of cases did it matter for the first request.

“First” marker only mattered in 0.77% of cases, and only ever for choosing between two non-preferred peers; though it was at least (almost) always for the first actual request for the txid.

FWIW, ignoring the first hour, I got 520 “accepted orphan tx” messages. I’m running this node with mempool expiry set to 24h so that might be a bit high.

 086.59% 222556 ABCD  requested  preferred=1  first=1  candidates=[-,-]  completed=[-,-]
 111.45%  29429 ABCD  requested  preferred=0  first=1  candidates=[-,-]  completed=[-,-]
 2 0.18%    455 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,-]
 3 0.09%    222 ABCD  requested  preferred=0  first=1  candidates=[-,-]  completed=[Y,-]
 4 0.08%    201 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,-]
 5 0.05%    127 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,Y]
 6 0.04%    111 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,Y]
 7 0.03%     79 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,-]
 8 0.01%     17 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,Y]
 9 0.01%     15 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,Y]
10
11 0.59%   1524 ABCD  requested  preferred=1  first=1  candidates=[-,Y]  completed=[-,-]
12 0.02%     64 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[-,Y]
13 0.02%     51 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,Y]
14 0.02%     50 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,-]
15 0.01%     38 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,Y]
16 0.01%     32 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,-]
17 0.01%     24 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,Y]
18 0.00%     10 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,-]
19 0.00%      1 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[-,Y]
20 0.00%      1 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,Y]
21
22 0.77%   1978 ABCD  requested  preferred=0  first=1  candidates=[-,Y]  completed=[-,-]
23 0.01%     20 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,Y]
24 0.00%      8 ABCD  requested  preferred=0  first=1  candidates=[-,Y]  completed=[Y,-]
25 0.00%      2 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,-]
26 0.00%      1 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[-,Y]

Just considering the first request for a tx (ie, candidates=[-,-] completed=[-,-] cases) the number of announcements for the tx in CANDIDATE_DELAYED was distributed something like:

 0  48839 ABCD requested preferred=1 delayed=0
 1  37457 ABCD requested preferred=1 delayed=1
 2  32913 ABCD requested preferred=1 delayed=2
 3  27587 ABCD requested preferred=1 delayed=3
 4  22798 ABCD requested preferred=1 delayed=4
 5  17525 ABCD requested preferred=1 delayed=5
 6  12564 ABCD requested preferred=1 delayed=6
 7   8071 ABCD requested preferred=1 delayed=7
 8   5148 ABCD requested preferred=1 delayed=8
 9   2965 ABCD requested preferred=1 delayed=9
10   1822 ABCD requested preferred=1 delayed=10
11
12   4437 ABCD requested preferred=0 delayed=0
13   2025 ABCD requested preferred=0 delayed=5
14   1981 ABCD requested preferred=0 delayed=6
15   1780 ABCD requested preferred=0 delayed=4

which looks pretty reasonable, I think. (I didn’t break the delayed count into preferred/non-preferred, so the delayed= figure should include both inbounds and any overloaded outbounds)

I wasn’t quite as lucky with my outbounds staying around the entire timeby the looks, but got a much more even looking distribution of requests between the different prefrences:

 0   1048 ABCD requested preferred=0 peer=2013
 1   1294 ABCD requested preferred=0 peer=4076
 2   1359 ABCD requested preferred=0 peer=4096
 3   1725 ABCD requested preferred=0 peer=235
 4   2193 ABCD requested preferred=0 peer=3370
 5   2630 ABCD requested preferred=0 peer=1950
 6   2694 ABCD requested preferred=0 peer=2304
 7   2843 ABCD requested preferred=0 peer=2095
 8   3618 ABCD requested preferred=0 peer=1853
 9
10      9 ABCD requested preferred=1 peer=6529
11     21 ABCD requested preferred=1 peer=5853
12     25 ABCD requested preferred=1 peer=1737
13     39 ABCD requested preferred=1 peer=1624
14     44 ABCD requested preferred=1 peer=30
15     57 ABCD requested preferred=1 peer=644
16    853 ABCD requested preferred=1 peer=22
17   2312 ABCD requested preferred=1 peer=11
18   5470 ABCD requested preferred=1 peer=202
19  13974 ABCD requested preferred=1 peer=0
20  14062 ABCD requested preferred=1 peer=2238
21  14427 ABCD requested preferred=1 peer=14
22  16520 ABCD requested preferred=1 peer=16
23  23714 ABCD requested preferred=1 peer=3385
24  37178 ABCD requested preferred=1 peer=24
25  46702 ABCD requested preferred=1 peer=29
26  49527 ABCD requested preferred=1 peer=44

(ignoring non-preferred peers that didn’t have >1000 requests)

EDIT: I’m guessing the lack of “used the first marker to tie-break between two preferred peers” cases means that none of my preferred peers were overloaded for any length of time, and always had reqtime=min(), and thus the ThreadMessageHandler loop would see the INV and immediately request it in a single iteration with no chance to consider any other peer, no matter how simultaneous the announcements were.

The previous 1.1% figure was due to the wtxidrelay delay causing all my preferred peers to have a 2s delay, so that if the outbounds were within 100ms there’d be a tie-breaker, ie they’d get added to the index, then both their reqtimes would pass while the thread was sleeping, and both would progress to READY/BEST in a single GetRequestable call.

Am currently running a test to see if removing “first” markers has a noticable effect on orphans (or anything else), but my current feeling is that the benefits of “first” markers don’t justify the complexity. I’ve had a quick go at pulling the feature out into its own commit at https://github.com/ajtowns/bitcoin/commits/202009-txoverhaul-sep-first to see how much complexity that is, fwiw.

I think the robustness that it adds is preserving the “first announcer” when multiple candidate announcements become ready at the same time. At present it only does that when their reqtimes were very similar from the word go, relative to how often GetRequestable is called.

One thing that might be worth considering is extending that towards a firmer guarantee, eg if a later, equally-preferred peer’s announcement ends up with an earlier reqtime (due to time going backwards or randomized delays maybe) automatically adjust the “first” peer’s announcement’s reqtime to the same figure. (That would make a difference even with the current net_processing code in this PR, I think. Namely in the case where a non-wtxid-relay announces txid X, then a wtxid-relay-node announces wtxid X, ie X has no witness – it’d bump the reqtime of the original peer’s announcement at that point, rather than making it wait for the full TXID_RELAY_DELAY)

Even if that’s a good idea though, I’m not really convinced it makes sense to do it now, rather than later, with code to actually randomize times and thus make it relevant, and we can see if it covers all the cases that actually make sense. eg, would probably want to bump the reqtime of the “first” preferred announcement upon receipt of a non-preferred announcement with earlier reqtime, but probably not the reverse…

(replying to resolved thread without marking it unresolved)

With “first” marker disabled (essentially treating every peer as oveloaded), I got:

 0 324484 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,-] -- 81.7%
 1  61457 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,-] -- 15.5%
 2    599 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,Y]
 3    122 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,Y]
 4    110 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,-]
 5     87 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,Y]
 6     60 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,-]
 7     13 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,Y]
 8
 9   2949 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,-] -- 0.7%
10    543 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,Y]
11    214 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,Y]
12     51 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[-,Y]
13     24 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,Y]
14      5 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,-]
15      5 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,-]
16      4 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,Y]
17      3 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,-]
18      1 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[-,Y]
19
20   3285 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[-,-] -- 0.8%
21   2910 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,Y] -- 0.7%
22    107 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[-,Y]
23      8 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,-]

I got 561 “accepted orphan tx” entries (ignoring the first first hour), compared to 520 last time, which is an 8% increase in orphans compared to running for about 90% longer or doing 54% more requests; so seems like any differences in behaviour are lost in the noise.

Looking at the per-peer behaviour, one non-preferred peer got a lot of requests:

 0   1088 ABCD requested preferred=0 peer=8236
 1   1245 ABCD requested preferred=0 peer=7422
 2   1470 ABCD requested preferred=0 peer=7219
 3   1486 ABCD requested preferred=0 peer=7712
 4   1540 ABCD requested preferred=0 peer=7342
 5  13124 ABCD requested preferred=0 peer=53
 6  22367 ABCD requested preferred=0 peer=12516
 7
 8    159 ABCD requested preferred=1 peer=20
 9    166 ABCD requested preferred=1 peer=7
10    746 ABCD requested preferred=1 peer=6
11  16624 ABCD requested preferred=1 peer=31
12  22917 ABCD requested preferred=1 peer=122
13  25830 ABCD requested preferred=1 peer=24
14  54666 ABCD requested preferred=1 peer=30
15  55279 ABCD requested preferred=1 peer=27
16  72306 ABCD requested preferred=1 peer=29
17  79637 ABCD requested preferred=1 peer=23

(ignores preferred peers that got less than 100 requests, and non-preferred peers that got less than 1000).

For peer=12516, almost every request (21625) was when it was the only candidate and no other peer had already been tried for the tx. It looks like it just happened to be fastest most of the time, with plenty of other inbounds (presumably) having already announced when we actually make the request:

 0      1 delayed=114
 1...
 2      7 delayed=60
 3     12 delayed=59
 4     12 delayed=58
 5...
 6    744 delayed=12
 7    904 delayed=11
 8   1025 delayed=10
 9   1146 delayed=9
10   1252 delayed=8
11   1389 delayed=7
12   1448 delayed=6
13   1335 delayed=5
14   1354 delayed=4
15   1096 delayed=3
16    706 delayed=2
17    420 delayed=1
18    193 delayed=0

Results for peer=53 look pretty similar to me, though it had a higher proportion of announcements where delayed=0 or delayed=1.

So I think that just means it’s showing a heavy bias towards fast peers/first announcers? The bias part is fine and desirable, but maybe it would be good to reduce the heaviness in future by mildly varying peers’ delays, either randomly or based on load in some way? Something to worry about in a followup.

Good point; I think was overlooked in #19569.

Fixed in a separate commit.

Perhaps reword this to be singular i.e. “..marker is given to an announcement at the time it is received … The peer that announced it was not overloaded.”

Currently your mixing plural (“announcements”) with singular (“its txhash”, “the same txhash”)

You can add “pushback mechanisms (OVERLOADED_PEER_TX_DELAY)”.

A future improvement of pushback mechanism could be to scale it up by the number of times of MAX_PEER_TX_IN_FLIGHT is reached, like m_txrequest.CountInFlightMagnitude(nodeid, MAX_PEER_TX_IN_FLIGHT) ? Thus delaying further and further a likely-malicious peer.

You can add “pushback mechanisms (OVERLOADED_PEER_TX_DELAY)”.

Done.

A future improvement of pushback mechanism could be to scale it up by the number of times of MAX_PEER_TX_IN_FLIGHT is reached, like m_txrequest.CountInFlightMagnitude(nodeid, MAX_PEER_TX_IN_FLIGHT) ? Thus delaying further and further a likely-malicious peer.

Yes, there are a number of possibilities there.

It’s documented in TxRequestTracker specification but I think you could recall that a preferred, txid-relay peer will be always favored on a non-preferred, wtxid-relay one.

I’d rather not duplicate the explanations; it’ll just risk things becoming inconsistent and confusing.

So it doesn’t matter that all delay penalties are actually 2 seconds. They order peers inside a class, not across ?

reqtimes don’t really order, they set the earliest request time. Actual requests are picked randomly from all announcements past their reqtime (preferred first, then non-preferred).

With this change, if time goes slightly backwards due to a non-monotonic clock, a later announcement may get requested first, even when no delay is intended:

• t=1.000 peer=1 preferred=1 txid=X –> ReceivedInv –> reqtime=1.000 state=CANDIDATE_DELAYED
• t=0.997 GetRequestable(peer=1) –> (no change)
• t=0.998 peer=2 preferred=1 txid=X –> ReceivedInv –> reqtime=0.999 state=CANDIDATE_DELAYED
• t=0.999 GetRequestable(peer=2) –> peer=2 txid=X state –> CANDIDATE_BEST

The previous code would have ensured that when no delay is desired, the announcement will always go to READY or BEST the next time GetRequestable is called.

(No opinion on whether that edge case is worth the conditional. If it is, might be nice to just pass in (current_time, delay) and have the addition/min done in ReceivedInv though)

This is the specification, there is no concept of Entry here.

Earlier in the file it says that a txhash/peer combination is called an announcement, so I don’t think this is ambiguous.

I think that’s explained exactly in this paragraph? “if one already exists for that (txhash, peer) combination”. Uniqueness is on that combination.

If the txhash is the same, it’s the same. If they’re not, they’re not.

Just so we’re on the same page. The scenario is:

• Peer P announces txid H
• Peer P announces wtxid H

In this case, the second announcement is ignored, because one already exists for peer/txhash combination (P, H). This is harmless for two reasons:

• The txid and wtxid being identical implies it’s a non-segwit transaction, so it doesn’t matter how we fetch.
• BIP339 prescribes that all announcements have to be wtxid when enabled (though I now realize that orphan fetching could actually mean this can actually still occur; I’ll improve the comment).