Overhaul transaction request logic #19988

 * - 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)

?

Done, approximately.

exptime is slightly ambiguous with "expected time" to me, maybe replace with "timeout" or "expiry_time" or just "expiry" ?

Changed to "expiry".

"(see further for details)" is true of all these points, I think.

I was trying to refer to the specific section on the "first" marker. Made that more explicit.

This was confusing -- I read it as "the first of many markers" rather than "a marker indicating it was first" and wondered what these "markers" were. Adding quotes around "first" consistently might be better?

Done.

Incomplete sentence?

Removed. It was a leftover of what turned into the last comment section.

Add a reference to https://allquantor.at/blockchainbib/pdf/miller2015topology.pdf to document/explain the invblock terminology? "What does this have to do with an INV message about a block?"

Done.

"and not being influencable by attackers"

Done, approximately.

"uint64_t" as a parameter name?

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:

class TxRequestTracker
{
protected:
    TxRequestTracker() { } // pure virtual class, must instantiate via subclass
public:
    virtual ~TxRequestTracker();
    virtual void DeletedPeer(uint64_t peer) = 0;
    ...
};
std::unique_ptr<TxRequestTracker> CreateTxRequestTracker(bool deterministic = false);

static 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.

Ah, good point! That seems a sufficient reason, so going to mark this as resolved.

Are these needed for fuzz testing, or could they be deleted as well? (copy constructors are implicitly deleted because of the unique ptr, so I think currently this is just making the implicit defaults explicit)

Gone.

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)

I've added a commit that just reduces MAX_PEER_TX_ANNOUNCEMENTS; 100000 was ridiculous. It can be bypassed using the PF_RELAY permission.

"Run a check on consistency of request times after a call to GetRequestable (requires the same timestamp as was passed to GetRequestable)" might be a better description? (At first glance I thought it might have been timing the sanity check, or doing a limited sanity check that checked different things depending on how much time it was taking to run)

Renamed to PostGetRequestableSanityCheck, and updated comment.

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

Not sure I follow, the only asserts are comparisons between entry.m_time and now ? Or should I have said "entry times" because "request" times might only mean REQUESTED entries?

m_time is the reqtime for CANDIDATE_*, but expiry for REQUESTED entries.

Maybe this should be overloaded == ... || g_txrequest.CountCandidates() >= 5000 or similar? I'm not sure I have a plausible enough scenario where this would be a benefit to justify the added code though.

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.

Yeah, sounds good.

I think if you were to make RequestTx() a method of class PeerManager, you could make g_txrequest be a private member PeerManager::m_txrequest GUARDED_BY(cs_main) instead of a global. OTOH, might be better to not do that until other globals that PeerManager methods rely on (like mapNodeState) are also moved. cc @jnewbery

I haven't paid too much attention to that, but I'm happy to change this if desirable.

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.

Done.

Should replace this test with one that checks we start applying OVERLOAD_PEER_TX_DELAY ?

@ajtowns Feel like writing such a test?

Done.

Not sure if it's worth adding any explicit justification for picking that number. But for the record, my thinking is: if our peers use the same INVENTORY_BROADCAST_INTERVAL, INVENTORY_BROADCAST_MAX params as us (and assuming they also halve the interval when they consider us an outbound, ie when we consider them an inbound), then 5000 is about 16 minutes worth of INVs for our outbounds, and 5 minutes for our inbounds. (More presuming we actually receive txs and thus clear entries out, or already had them)

I added some rationale.

Rationale looks fine to me :+1:

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:

TxRequestTracker::~TxRequestTracker() = default;

Of course! Done.

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?

Nice, done.

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

diff --git a/src/txrequest.cpp b/src/txrequest.cpp
index f6c387f8f4..b7d90a1ba5 100644
--- a/src/txrequest.cpp
+++ b/src/txrequest.cpp
@@ -668,10 +668,8 @@ public:
     }
 };
 
-TxRequestTracker::TxRequestTracker(bool deterministic)
-{
-    m_impl = MakeUnique<TxRequestTracker::Impl>(deterministic);
-}
+TxRequestTracker::TxRequestTracker(bool deterministic) :
+    m_impl{MakeUnique<TxRequestTracker::Impl>(deterministic)} {}
 
 TxRequestTracker::~TxRequestTracker() {}
 
diff --git a/src/txrequest.h b/src/txrequest.h
index 6e892eebe1..83f6dbe2fe 100644
--- a/src/txrequest.h
+++ b/src/txrequest.h
@@ -119,7 +119,7 @@ public:
 private:
     // Avoid littering this header file with implementation details.
     class Impl;
-    std::unique_ptr<Impl> m_impl;
+    const std::unique_ptr<Impl> m_impl;
 
 public:
     //! Construct a TxRequestTracker.

Done.

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.

Renamed to DisconnectedPeer.

     * whatever reason we no longer care about it. Only the hash field of gtxid is used.

Maybe talk about what it's used for instead of what it's not, or just change the interface to make it clear.

Changed the interface to take just a uint256.

COMPLETED sounds more like FAILED.

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

I'm not sure what you're suggesting here. FAILED seems like a bad name as it indeed doesn't imply failure.

apologies I wrote my comment in two frame of minds. I mean to say the comment doesn't mention "success" as a possibility to transition to this state. Update the comment and I'm happy.

Done. Better?

yes, thank you

    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

I'd prefer to move these into a friend TxRequestTrackerTester class (I thought I'd left a review comment suggesting that, but I appear to have lost it).

@jnewbery How do you suggest to do that in combination with the impl pattern?

Hmmm yes, very good question! I wonder if something along the lines of https://stackoverflow.com/a/34054983/933705 might work (but then again, it might not be worth it just to avoid putting these three test helper functions in the public interface).

I think it's not unreasonable to have sanity checking functions for involved data structures in code that actually deals with that data structure. It could possibly be called at runtime using something something similar to -checkmempool too if we wanted.

I agree. That seems reasonable.

tangentially-related nit: Comments above function are getting pretty stale.

Updated.

The witness-ness of GenTxid doesn't matter. I find the interface distracting since it needs to be passed in.

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.

I've merged the "first" marker section into this bulletpoint, and incorporated your suggested text.

"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.

"avoiding influenceable" doesn't make sense?

It are English perfect.

They is now anyhoo

Since Impl is now only defined in the cpp file, I think you can reasonably move State and the like outside of the class, ideally sticking it in an anonymous namespace so the internal class methods get internal linkage. Main benefit would be that it's easier to see what the actual data being put in Impl is, I think.

I like that. Moved all the type definitions out of ::Impl.

This isn't templated, so typename isn't needed, I think? Making an alias for the iterators in general might be useful: template<typename Tag> using IndexIter = typename Index::index<Tag>::type::iterator; and void PromoteCandidateReady(IndexIter<ByTxHash> it)?

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

I've added an Iter<Tag> 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:

// m_peerinfo can be exactly recalculated from the Index.
//
// This verifies the data in it, including the invariant
// that no entries with m_total_announcements==0 exist.
assert(m_peerinfo == GenSanityCheckPeerInfo(m_index));

for (auto& el : GenSanityCheckCounts(m_index, m_computer)) {
    const uint256& hash = el.first;
    Counts& c = el.second;
    // Cannot have only COMPLETED peers (txid should have been deleted)
    assert(c.m_candidate_delayed + c.m_candidate_ready + c.m_candidate_best + c.m_requested > 0);

I haven't addressed this yet.

Done. Also included some more comments from your branch linked above.

for (const Entry& entry : m_index) { Counts& counts = table[entry.m_txhash]; ?

I've changed it to c for Counts objects and e for Entry objects.

Similar change would be good for the peerinfo reconstruction; it has auto& entry = for a PeerInfo.

= (1 << 1) ? Maybe I'm dumb but it took me a bit to realise these are getting or'ed together. Seems slightly weird to have m_per_txhash : 2 instead of m_last_preferred : 1 and m_last_nonpreferred : 1 ("If you ain't first, you're last" - Ricky Bobby), but I guess it simplifies the code that updates these values enough to make sense.

At some point I had more flags than 2. I've changed it to two bools now (this makes the SanityCheck code for it a lot more readable in particular).

Might make sense to drop this method and move the logic directly into EntryTxHashExtractor. If done that way, then can move the PriorityComputer definition after Entry and move theEntry::ComputePriority logic into a PriorityComputer::ComputePriority(const Entry&) const method (changing the entry.ComputePriority(computer) calls to computer.ComputePriority(entry) calls). That pretty much lets the definition of Entry be the first thing in the file which seems a lot more logical.

Yep, done. To match the "functor" concept I'm overloading operator() instead of having a ComputePriority function.

(txid,peer)

(txhash,peer) actually, fixed in many places.

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.

Done.

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.

--- a/src/txrequest.cpp
+++ b/src/txrequest.cpp
@@ -528,6 +528,29 @@ public:
         // in between, which preserve the state of other GenTxids).
         assert(it != m_index.get<ByPeer>().end());
         assert(it->GetState() == State::CANDIDATE_BEST);
+       {
+            auto bytxhashit = m_index.project<ByTxHash>(it);
+            auto bytxhashit_pre = bytxhashit;
+           int delayed = 0;
+           int candidates = 0;
+           while (bytxhashit_pre != m_index.get<ByTxHash>().begin()) {
+               --bytxhashit_pre;
+               if (bytxhashit_pre->GetState() != State::CANDIDATE_DELAYED || bytxhashit->m_txhash != it->m_txhash) break;
+               ++delayed;
+           }
+           ++bytxhashit;
+           while (bytxhashit != m_index.get<ByTxHash>().end() && bytxhashit->GetState() != State::COMPLETED && bytxhashit->m_txhash == it->m_txhash) {
+               ++candidates;
+               ++bytxhashit;
+           }
+           int completed = 0;
+           while (bytxhashit != m_index.get<ByTxHash>().end() && bytxhashit->GetState() == State::COMPLETED && bytxhashit->m_txhash == it->m_txhash) {
+               ++completed;
+               ++bytxhashit;
+           }
+           assert(bytxhashit == m_index.get<ByTxHash>().end() || bytxhashit->m_txhash != it->m_txhash);
+           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);
+       }
         Modify<ByPeer>(it, [expiry](Entry& entry) {
             entry.SetState(State::REQUESTED);
             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.

Yeah. I don't think a wrapper would really be an improvement on documenting the expectations, and agree that sticking fixed params in txrequest is really too restrictive. Going to mark this thread as resolved, but still continue thinking about it.

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.

86.59% 222556 ABCD  requested  preferred=1  first=1  candidates=[-,-]  completed=[-,-]
11.45%  29429 ABCD  requested  preferred=0  first=1  candidates=[-,-]  completed=[-,-]
 0.18%    455 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,-]
 0.09%    222 ABCD  requested  preferred=0  first=1  candidates=[-,-]  completed=[Y,-]
 0.08%    201 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,-]
 0.05%    127 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,Y]
 0.04%    111 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,Y]
 0.03%     79 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,-]
 0.01%     17 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,Y]
 0.01%     15 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,Y]

 0.59%   1524 ABCD  requested  preferred=1  first=1  candidates=[-,Y]  completed=[-,-]
 0.02%     64 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[-,Y]
 0.02%     51 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,Y]
 0.02%     50 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,-]
 0.01%     38 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,Y]
 0.01%     32 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,-]
 0.01%     24 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,Y]
 0.00%     10 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,-]
 0.00%      1 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[-,Y]
 0.00%      1 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,Y]

 0.77%   1978 ABCD  requested  preferred=0  first=1  candidates=[-,Y]  completed=[-,-]
 0.01%     20 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,Y]
 0.00%      8 ABCD  requested  preferred=0  first=1  candidates=[-,Y]  completed=[Y,-]
 0.00%      2 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,-]
 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:

  48839 ABCD requested preferred=1 delayed=0
  37457 ABCD requested preferred=1 delayed=1
  32913 ABCD requested preferred=1 delayed=2
  27587 ABCD requested preferred=1 delayed=3
  22798 ABCD requested preferred=1 delayed=4
  17525 ABCD requested preferred=1 delayed=5
  12564 ABCD requested preferred=1 delayed=6
   8071 ABCD requested preferred=1 delayed=7
   5148 ABCD requested preferred=1 delayed=8
   2965 ABCD requested preferred=1 delayed=9
   1822 ABCD requested preferred=1 delayed=10

   4437 ABCD requested preferred=0 delayed=0
   2025 ABCD requested preferred=0 delayed=5
   1981 ABCD requested preferred=0 delayed=6
   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:

   1048 ABCD requested preferred=0 peer=2013
   1294 ABCD requested preferred=0 peer=4076
   1359 ABCD requested preferred=0 peer=4096
   1725 ABCD requested preferred=0 peer=235
   2193 ABCD requested preferred=0 peer=3370
   2630 ABCD requested preferred=0 peer=1950
   2694 ABCD requested preferred=0 peer=2304
   2843 ABCD requested preferred=0 peer=2095
   3618 ABCD requested preferred=0 peer=1853

      9 ABCD requested preferred=1 peer=6529
     21 ABCD requested preferred=1 peer=5853
     25 ABCD requested preferred=1 peer=1737
     39 ABCD requested preferred=1 peer=1624
     44 ABCD requested preferred=1 peer=30
     57 ABCD requested preferred=1 peer=644
    853 ABCD requested preferred=1 peer=22
   2312 ABCD requested preferred=1 peer=11
   5470 ABCD requested preferred=1 peer=202
  13974 ABCD requested preferred=1 peer=0
  14062 ABCD requested preferred=1 peer=2238
  14427 ABCD requested preferred=1 peer=14
  16520 ABCD requested preferred=1 peer=16
  23714 ABCD requested preferred=1 peer=3385
  37178 ABCD requested preferred=1 peer=24
  46702 ABCD requested preferred=1 peer=29
  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...

Done, I've changed this PR to drop the "first" marker logic, based on your branch + adjusting fuzz tester and some extra comments. The commit to add it back is here: https://github.com/sipa/bitcoin/commits/202009_txrequest_rand_wtxid_first

(replying to resolved thread without marking it unresolved)

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

 324484 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,-] -- 81.7%
  61457 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,-] -- 15.5%
    599 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,Y]
    122 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[-,Y]
    110 ABCD  requested  preferred=0  first=0  candidates=[-,-]  completed=[Y,-]
     87 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,Y]
     60 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[Y,-]
     13 ABCD  requested  preferred=1  first=0  candidates=[-,-]  completed=[-,Y]

   2949 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,-] -- 0.7%
    543 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,Y]
    214 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,Y]
     51 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[-,Y]
     24 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[-,Y]
      5 ABCD  requested  preferred=1  first=0  candidates=[Y,Y]  completed=[Y,-]
      5 ABCD  requested  preferred=1  first=0  candidates=[-,Y]  completed=[Y,-]
      4 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,Y]
      3 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[Y,-]
      1 ABCD  requested  preferred=1  first=0  candidates=[Y,-]  completed=[-,Y]

   3285 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[-,-] -- 0.8%
   2910 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[Y,Y] -- 0.7%
    107 ABCD  requested  preferred=0  first=0  candidates=[-,Y]  completed=[-,Y]
      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:

   1088 ABCD requested preferred=0 peer=8236
   1245 ABCD requested preferred=0 peer=7422
   1470 ABCD requested preferred=0 peer=7219
   1486 ABCD requested preferred=0 peer=7712
   1540 ABCD requested preferred=0 peer=7342
  13124 ABCD requested preferred=0 peer=53
  22367 ABCD requested preferred=0 peer=12516

    159 ABCD requested preferred=1 peer=20
    166 ABCD requested preferred=1 peer=7
    746 ABCD requested preferred=1 peer=6
  16624 ABCD requested preferred=1 peer=31
  22917 ABCD requested preferred=1 peer=122
  25830 ABCD requested preferred=1 peer=24
  54666 ABCD requested preferred=1 peer=30
  55279 ABCD requested preferred=1 peer=27
  72306 ABCD requested preferred=1 peer=29
  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:

      1 delayed=114
...
      7 delayed=60
     12 delayed=59
     12 delayed=58
...
    744 delayed=12
    904 delayed=11
   1025 delayed=10
   1146 delayed=9
   1252 delayed=8
   1389 delayed=7
   1448 delayed=6
   1335 delayed=5
   1354 delayed=4
   1096 delayed=3
    706 delayed=2
    420 delayed=1
    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.

Not 100% on topic for this PR I guess, but if (!gtixd.m_is_wtxid && g_wtxid_relay_peers > 0) perhaps? That was we delay requesting a parent by txid when handing orphans in case we might have already been requesting the parent by wtxid from some peer (even this one if they were announced/requested/replied out of order for some reason).

Good point; I think was overlooked in #19569.

Fixed in a separate commit.

Unmatched ) parse error

Fixed.

Maybe personal preference, but I really don't like the invblock terminology (for this reason: #19988 (review)) and would prefer not to introduce it to the Bitcoin Core codebase.

I've replaced it with "transaction censorship attacks".

I think this depends on your definition of progress? If all of your peers are announcing but not relaying transactions, then it doesn't matter how many times you request the tx, you're never making progress.

"progress towards forgetting a transaction" is unambiguous I think? Every minute one peer is crossed off the list of candidates, so eventually you will run out. Note that this section isn't about successfully receiving the transaction, but bounding memory usage.

Actually, thinking more about this, it isn't exactly true, because for non-preferred connections we should assume the attacker can disconnect and reconnect, giving them a new opportunity. I think this should be restated as: an attacker can force us to keep a transaction in memory (even in the queues of honest peers) for as long as they can prevent us from receiving the transaction. That's not necessarily bounded, but in cases where it isn't, we have bigger problems. Actual OOM is prevented using per-peer queue size limits.

I've adjusted the comments, merging this paragraph into the previous one (they were already kind of circularly referring to each other). Also changed the formula for delay to take this potential for reconnection behavior into account.

change 'net_processing' to 'caller'

Done.

remove "(outbound, whitelisted)". The caller chooses which peers are preferred, so it's best to avoid what we expect the caller to do here.

Done.

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")

Gone (moved to https://github.com/sipa/bitcoin/commits/202009_txrequest_rand_wtxid_first).

"when backwards" -> "went backwards"?

Fixed.

Perhaps comment that this is only used in sanity testing, or even better remove it entirely and move the logic into TxRequestTracker::Impl::SanityCheck() (since it's only called in one place).

Actually, I think just a comment saying that his is just used for sanity checking is sufficient.

Done.

Consider moving this logic into SanityCheck(), since it's only called in one place.

Marking as resolved. AJ asked you to separate this, and I don't have a strong opionion.

What's the thinking behind having this logic in a separate function, rather than contained in SanityCheck()? It's only called in one place.

Marking as resolved. AJ asked you to separate this, and I don't have a strong opionion.

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.

I think this delay applies to non-preferred peers which is strictly a different set than inbound ones as some of them might be PF_NOBAN==true. Variable name can be updated to reflect this.

Done.

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. So it doesn't matter that all delay penalties are actually 2 seconds. They order peers inside a class, not across ?

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).

Commit for this change says "orphan fetches" but it's really "fetches of orphan's parents"...

Fixed.

Why not pass current_time only for false-branch of ternary ? Entry should be promoted to {READY/BEST} in SetTimePoint anyway.

Agree, the current code is just unnecessarily complicated. Fixed.

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)

Yes, that was the original reasoning, but I'm not sure clocks going backward is worth extra complexity (it should do something sane, and be tested, but it should be sufficiently rare that the actual behavior doesn't matter too much).

Have you considered moving m_txrequest under it's own lock as it's a well-contained, new data structure ? a) useless as we already take cs_main independently in all code paths reaching m_txrequest or b) too much work and this PR is already complex enough?

I don't think there is a benefit to giving it a separate lock. There may be one at some point, but probably together with the majority of net_processing moving from cs_main to its own lock(s). At this point, cs_main is already held anyway.

I also have a slight preference that this is guarded by its own mutex since I don't like adding yet more non-validation state to cs_main, but agree that it should be straightforward to move it later.

I agree with the goal of eventually having this not under cs_main, but the hard part will be disentangling the existing code calling into txrequest not covered by cs_main. Just adding another lock in addition to cs_main here isn't helping with that part, so I prefer doing this as a follow-up (together with probably a bigger part of net_processing also losing cs_main).

I think this comment isn't clear with other comments spread elsewhere like "Lower priorities are selected first".

I've removed it, preferredness is explained much better in the .h file now then when this comment was added.

to convert to CANDIDATE_BEST?

Done.

Is there a caveat here if the same transaction is announced concurrently by txid and wtxid ? You may have a download collision due to transaction identifier ambiguity.

As far as txrequest is converned, transactions are identified by its txhash. If there is both a txid and wtxid announcement for the same transaction (and the wtxid differs from the txid), it'll be treated as two transactions, and they could be fetched both. That is exactly the reason why an extra delay for txid announcements was introduced (prior to this PR), to avoid downloading the same thing twice.

Okay so the only download duplication we may have is if any preferred, wtxid-relay peers is really slow, requiring from a txid-relay peer and receiving both. Really a edge case once the network is sufficiently upgraded I guess.

I don't expect it to be super rare, but the risk of double fetching during rollout is inherent to BIP339 (and exists in the same form in current master, so I don't think it's significantly affected by this PR).

Added a note about this.

I find this confusing. Is "Announcements" denoting all Entry under the same txhash or a given (peer/txhash) Entry. In the former, a peer going offline shouldn't carry deletion of other different-peer/same-txhash Entries.

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've elaborated this a bit. Is it clearer now?

Yes, better!

At least one what ? An attacker controlled-peer, a non-buggy honest preferred connection?

I've clarified this, I think.

How does entry uniqueness is enforced w.r.t to wtxid/txid ? For segwit txn, the ByPeer can't dissociate between a txid and wtxid announcement, it's different hash ?

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.

I think I hurted on "Note that this means a second INV with the same txhash from the same peer will be ignored, even if one is a txid and the other is wtxid". I interpreted it "As if first is txid, does nothing even if a second announcement is wtxid". That's my English here, nevermind.

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).

I've rewritten the comment.

Yes clearer.

Question: why wasn't entry.IsSelectable() used instead?

That would also compute the priority for entries in the CANDIDATE_BEST state. That would be harmless as it wouldn't change behavior, but the computation of priority isn't exactly free either, so better avoid it when not needed.

I interpret this comment to mean that ForgetTxHash i.e. the TxRequestTracker is responsible for deleting the transaction by txid and wtxid, but I don't think this is the case... that's PeerManager's job right?

TxRequestTracker is a data structure that manages the set of announced txids/wtxids for all peers, exposes ways to alter that set, and answers queries about it. Its responsibility is maintaining the consistency of that data structure, and doing as it's told; it isn't responsible for deciding what mutations to make and when; that's net_processing's job.

This function is the mutator that removes all entries with a given txid or wtxid. It does just that. Net_processing calls it whenever it is no longer interested in a particular txid/wtxid.

In https://github.com/bitcoin/bitcoin/pull/19988/commits/987b27176e41f38b997f7b732f087a518fa678ca

Please forgive me but I just want to make sure I'm understanding this commit correctly... we want to add a delay for transactions by txid just in case we're able to get it by wtxid from another peer. But when we get an orphan, we only have the txid of the missing parent. -Using the logic of peer's m_wtxid_relay doesn't apply to requests for missing parents because we can only request by txid, even if the peer is wtxid relay? -But using transaction's IsWtxid means we're interested in potentially receiving the missing parent (from anyone) as a wtxid relay before we ask this peer for the missing parent?

Imagine we have multiple announcements for the same witness transaction, and all peers have different witnesses for it. So the transaction will be known by one txid, but multiple distinct wtxids. We don't know that these are all for the same transaction, as all the (non-txid) requests have different hashes.

No matter who we ask, or what we receive, we'll always be able to delete all txid-based announcements for it (we'll compute the txid of the received transaction, which will be the same for all). However, we can't delete all wtxid announcements, only the one for the wtxid announcement for the witness we actually received. Thus we want to prioritize fetching by wtxid, as a successful response to that will allow us to delete at least one wtxid-based announcements + plus all txid-based announcements (while a txid based request only guarantees deleting all txid-based announcements).

Now imagine that instead all our peers are BIP339 (wtxid) peers, and there are transactions A and B, where B spends one of A's outputs. For most peers, we receive A first and then B. But from one peer, we only receive B (e.g. because we just connected and weren't connected when A was sent), and B is fetched first. That makes it an orphan, and its "prevout" entry in its input for A is treated as a txid announcement (we don't have its wtxid), despite being from a wtxid peer. Thus we end up with a txid announcement for A, and a bunch of wtxid announcements for it (from the other peers). The same reasoning applies here: we want to fetch by one of the wtxid ones first, because it is guaranteed to allow us to forget the txid announcement PLUS at least one wtxid one.

static constexpr std::chrono::seconds NONPREF_PEER_TX_DELAY{2};

This can be written shorter, as the compiler will do the chrono conversion for you

(Same below)

Done. I've changed it to static constexpr auto VARNAME = std::chrono::seconds{2};, as I think it's slightly more readable to have the unit and the magnitude together.

==() doesn't need to be a friend, since it's not accessing any private/protected members:

diff --git a/src/txrequest.cpp b/src/txrequest.cpp
index bef3460dd6..b7347d8d34 100644
--- a/src/txrequest.cpp
+++ b/src/txrequest.cpp
@@ -206,14 +206,15 @@ struct PeerInfo {
     size_t m_completed = 0; //!< Number of COMPLETED entries for this peer.
     size_t m_requested = 0; //!< Number of REQUESTED entries for this peer.
 
-    /** Compare two PeerInfo objects. Only used for sanity checking. */
-    friend bool operator==(const PeerInfo& a, const PeerInfo& b)
-    {
-        return std::tie(a.m_total, a.m_completed, a.m_requested) ==
-               std::tie(b.m_total, b.m_completed, b.m_requested);
-    }
 };
 
+/** Compare two PeerInfo objects. Only used for sanity checking. */
+bool operator==(const PeerInfo& a, const PeerInfo& b)
+{
+    return std::tie(a.m_total, a.m_completed, a.m_requested) ==
+           std::tie(b.m_total, b.m_completed, b.m_requested);
+}
+

Feels slightly clearer to me, but obviously doesn't make much difference.

Done.

This is really just a stylistic thing, but is there a reason to make any members of an impl class private? By definition it doesn't have an exposed interface, so theoretically everything could just be public. The first two examples at https://en.cppreference.com/w/cpp/language/pimpl are actually declared as structs (although the third example does have a private data member)

It may be matter of personal taste.

In general I think it still makes sense to have non-exposed classes with private/public fields/members. It's not there to prevent external code from messing with the internals, obviously, but it does still kind of define a layer between what is part of the class's representation and what is its (even just internally) exposed interface.

In this case with the pimpl pattern... maybe that's silly, as the glue layer to forward calls on TxRequestTracker to TxRequestTracker::Impl is super thin, and it's already obvious what the exposed part is.

Happy to change it if there are strong opinions.

No strong opinion. Feel free to mark this resolved.

Is there a reason not to use NodeId throughout instead of uint64_t? It seems to me that NodeId would be more consistent with net/net_processing, and more readable in function signatures/returns types/typedefs.

The only reason not to is avoiding a dependency on net.h.

You mean in the header file? Could you make the public functions take int64_t and use NodeId internally in the cpp file (which already includes net.h)?

I think the observable "c++ file dependencies" are only an approximation for what actually matters in terms of code organization: "conceptual dependencies between modules". What you're suggesting is just as much a dependency of txrequest on net in my view - just slightly more hidden.

All of this to say: I'd like to avoid a dependency on net, and am therefore using uint64_t as opaque peer identifier rather than NodeId.

But if we feel that's not worth the cost, it should be changed to use NodeId everywhere (in both the .h and the .cpp).

I do feel like we should use the same type to represent node ids in all components. Perhaps the purest way to do it would be to move the typedef NodeId int64_t somewhere outside net.h, but that seems a bit overkill.

Even if you don't use NodeId, is there a reason that you're using uint64_t rather than int64_t like everywhere else?

I've bitten the bullet and converted everything to NodeId.

I believe it being a uint64_t dates back to a time when I was trying to squeeze out bits by using less than 64 bits for the peer (and signed bitfields are implementation defined, IIRC). This was a bad idea.

s/takes it/takes its/

Done.

s/AlreadyHave/ForgetTxHash/

Done.

Delete all this. It's no longer needed now that there's no 'first' marker.

Done.

Delete

Done.

It's still here :)

Really done.

s/ForgetTx/ForgetTxHash/

Done.

Possible changes to this interface:

1. Change the GenTxid argument to uint256. The function doesn't make any distinction between txids and wtxids, so why make it part of the interface?
2. Pass a const std::vector<uint256>&, with all txs that have been requested, rather than repeatedly calling the same function with different tx hashes.
3. Also pass in a const std::vector<uint256>& hashes_to_forget, with all txs to forget.

Doing all of those would change the condition "This can ONLY be called immediately after GetRequestable was called (for the same peer), with only ForgetTxHash and other RequestedTx calls (both for other txhashes) in between." to the much stronger condition "This can ONLY be called immediately after a GetRequestable call with no other calls in between".

Constructing vectors instead of repeatedly calling the function seems worse to me, fwiw, but agree that it would be nice to have a simpler description of the constraint.

Maybe tying it to the return value of GetRequestable might be better: "each value returned by GetRequestable may used with either ForgetTxHash or RequestedTx for the given peer, but not both, and at most only once. Any other calls to non-const methods on TxRequestTracker invalidate all the results from GetRequestable" ?

It wouldn't be too hard to just drop the constraint, and instead specify it as:

• If no announcement with the specified (peer, txhash) exists, or it isn't in CANDIDATE state, the call has no effect.
• The specified announcement is changed from CANDIDATE to REQUESTED.
• If another announcement for the same txhash was already in REQUESTED state, it is marked COMPLETED.

It'd be a bit more code, but would make the function fully specified. I've avoided it, as there is really no point for that functionality in practice, but it does make things a bit nicer. WDYT?

If we don't do that, I like @ajtowns's way of describing the functionality.

Either is fine. I also like @ajtowns's description.

Whichever way we go, I still think the function should be changed to take a txhash - I should have left that as a separate comment.

Changed to AJ's description.

Here is the patch to make RequestedTx fully specified:

diff --git a/src/txrequest.cpp b/src/txrequest.cpp
index af4b59755b..581b498180 100644
--- a/src/txrequest.cpp
+++ b/src/txrequest.cpp
@@ -590,11 +590,29 @@ public:
     void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
     {
         auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
-        // RequestedTx can only be called on CANDIDATE_BEST announcements (this is implied by its condition that it
-        // can only be called on GenTxids returned by GetRequestable (and only ForgetTxHash and RequestedTx can be
-        // called in between, which preserve the state of other GenTxids).
-        assert(it != m_index.get<ByPeer>().end());
-        assert(it->GetState() == State::CANDIDATE_BEST);
+        if (it == m_index.get<ByPeer>().end()) {
+            // There is no CANDIDATE_BEST entry, look for _READY or _DELAYED instead.
+            it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash});
+            if (it == m_index.get<ByPeer>().end() || (it->GetState() != State::CANDIDATE_DELAYED &&
+                it->GetState() != State::CANDIDATE_READY)) {
+                // There is no CANDIDATE_* entry at all, give up.
+                return;
+            }
+
+            // Look for an existing CANDIDATE_BEST to demote to _READY, or REQUESTED to make COMPLETED.
+            auto it_old = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_BEST, 0});
+            if (it_old != m_index.get<ByTxHash>().end() && it_old->m_txhash == txhash) {
+                if (it_old->GetState() == State::CANDIDATE_BEST) {
+                    // It doesn't matter whether we pick CANDIDATE_READY or _DELAYED here, as SetTimePoint()
+                    // will correct it at GetRequestable() time. If time only goes forward, it will always be
+                    // _READY, so pick that to avoid extra work in SetTimePoint().
+                    Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); });
+                } else if (it_old->GetState() == State::REQUESTED) {
+                    Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); });
+                }
+            }
+        }
+
         Modify<ByPeer>(it, [expiry](Announcement& ann) {
             ann.SetState(State::REQUESTED);
             ann.m_time = expiry;

When combined with the corresponding changes in src/test/fuzz/txrequest.cpp it's actually a net reduction in code. WDYT?

Added as an extra commit on top.

I think that ~without~ following this change all the remaining asserts are redundant internal checks, rather than "invalid use of API" ones, which I think is a plus. Also makes perfect sense (in retrospect) that that would then make the fuzz tester a bunch simpler.

I think that means that you can call TxRequestTracker methods with any params and the behaviours well-defined, reasonably logical, and as efficient as possible. I think this even maintains the amortized complexity, which surprises me.

So yeah, I like this! Maybe change the "There is no CANDIDATE_BEST entry" comment to note that this path only occurs if the API caller requests an txid that wasn't just returned from GetRequestable -- ie, they either have a bug due to a race condition of not dealing with the results of GetRequestable for one peer before calling it again later, or they're doing their own selection of which announcement to request beyond relying on TxRequestTracker's algorithm?

Maybe the "give up" case would be clearer if there was a bit more of the "why" spelled out too?

            if (it == m_index.get<ByPeer>().end()) {
                // This txid wasn't tracked for this peer; caller should have called ReceivedInv() first.
                return;
            } else if (it->GetState() != State::CANDIDATE_DELAYED && it->GetState() != State::CANDIDATE_READY)) {
                // Only progress to REQUESTED from CANDIDATE to ensure the state machine is finite
                return;
           }

Done, switched to the fully-defined version (squashed into the appropriate commits). I added some of @ajtowns's comments, and more.

I also like this. Good change!

overloaded isn't a TxRequestTracker parameter, so I think it's fine just to have the OVERLOADED_PEER_TX_DELAY comment in the sub-bullet below

Done.

s/announcements from txid peers/txid announcements/ (since requesting an orphan tx from a wtxid peer counts as a txid announcement)

Done.

s/How many microseconds/How long/ (commenting that a std::chrono::microseconds constant is microseconds is redundant)

Done.

Delete all this. No longer needed since you removed the 'first' marker.

Done.

I don't understand this comment about catching a non-CANDIDATE_BEST entry automatically. m_index.get<ByPeer>().count() will return 0 in that case.

Edit: Ah! I've just seen the comment below. Perhaps update this comment to say "will be caught by the uniqueness property when we try to emplace the new Entry object".

Done.

Why not just index by (peer, txhash), and then in GetRequestable() just add an if (it_peer->GetState() == State::CANDIDATE_BEST) before adding the hash to selected? It seems like in all other places (DisconnectedPeer(), ReceivedInv() and ReceivedResponse()), we're actually interested in all the outstanding Entry objects for a given peer.

That would make GetRequestable be O(nr_announcements) instead of O(nr_best) which I think makes the complexity blow out in worst case scenarios.

Yes, makes sense. Thanks!

Yes, that's exactly the reason.

Maybe assert that it is not end() at the top of this function?

Done (and in a few more places).

This can be changed to take a hash instead of a GenTxid. The function doesn't do anything with whether it's a txid or wtxid, so it shouldn't be part of the interface.