TxRequestTracker

class TxRequestTracker;

Description

=== Specification ===

We keep track of which peers have announced which transactions, and use that to determine which requests should go to which peer, when, and in what order.

The following information is tracked per peer/tx combination ("announcement"):

• Which peer announced it (through their NodeId)

• The txid or wtxid of the transaction (collectively called "txhash" in what follows)

• Whether it was a tx or wtx announcement (see BIP339).

• What the earliest permitted time is that the transaction can be requested from that peer (called "reqtime").

• Whether it's from a "preferred" peer or not. Which announcements get this flag is determined by the caller, but this is designed for outbound peers, or other peers that we have a higher level of trust in. Even when the peers' preferredness changes, the preferred flag of existing announcements from that peer won't change.

• Whether or not the transaction was requested already, and if so, when it times out (called "expiry").

• Whether or not the transaction request failed already (timed out, or invalid transaction or NOTFOUND was received).

Transaction requests are then assigned to peers, following these rules:

• No transaction is requested as long as another request for the same txhash is outstanding (it needs to fail first by passing expiry, or a NOTFOUND or invalid transaction has to be received for it).

Rationale: to avoid wasting bandwidth on multiple copies of the same transaction. Note that this only works per txhash, so if the same transaction is announced both through txid and wtxid, we have no means to prevent fetching both (the caller can however mitigate this by delaying one, see further).

• The same transaction is never requested twice from the same peer, unless the announcement was forgotten in between, and re-announced. Announcements are forgotten only:

• If a peer goes offline, all its announcements are forgotten.

• If a transaction has been successfully received, or is otherwise no longer needed, the caller can call ForgetTxHash, which removes all announcements across all peers with the specified txhash.

• If for a given txhash only already-failed announcements remain, they are all forgotten.

Rationale: giving a peer multiple chances to announce a transaction would allow them to bias requests in their favor, worsening transaction censoring attacks. The flip side is that as long as an attacker manages to prevent us from receiving a transaction, failed announcements (including those from honest peers) will linger longer, increasing memory usage somewhat. The impact of this is limited by imposing a cap on the number of tracked announcements per peer. As failed requests in response to announcements from honest peers should be rare, this almost solely hinders attackers. Transaction censoring attacks can be done by announcing transactions quickly while not answering requests for them. See https://www.cs.umd.edu/projects/coinscope/coinscope.pdf for more information.

• Transactions are not requested from a peer until its reqtime has passed.

Rationale: enable the calling code to define a delay for less-than-ideal peers, so that (presumed) better peers have a chance to give their announcement first.

• If multiple viable candidate peers exist according to the above rules, pick a peer as follows:

• If any preferred peers are available, non-preferred peers are not considered for what follows.

Rationale: preferred peers are more trusted by us, so are less likely to be under attacker control.

• Pick a uniformly random peer among the candidates.

Rationale: random assignments are hard to influence for attackers.

Together these rules strike a balance between being fast in non-adverserial conditions and minimizing susceptibility to censorship attacks. An attacker that races the network:

• Will be unsuccessful if all preferred connections are honest (and there is at least one preferred connection).

• If there are P preferred connections of which Ph>=1 are honest, the attacker can delay us from learning about a transaction by k expiration periods, where k ~ 1 + NHG(N=P-1,K=P-Ph-1,r=1), which has mean P/(Ph+1) (where NHG stands for Negative Hypergeometric distribution). The "1 +" is due to the fact that the attacker can be the first to announce through a preferred connection in this scenario, which very likely means they get the first request.

• If all P preferred connections are to the attacker, and there are NP non-preferred connections of which NPh>=1 are honest, where we assume that the attacker can disconnect and reconnect those connections, the distribution becomes k ~ P + NB(p=1-NPh/NP,r=1) (where NB stands for Negative Binomial distribution), which has mean P-1+NP/NPh.

Complexity:

• Memory usage is proportional to the total number of tracked announcements (Size()) plus the number of peers with a nonzero number of tracked announcements.

• CPU usage is generally logarithmic in the total number of tracked announcements, plus the number of announcements affected by an operation (amortized O(1) per announcement).

Context:

• In an earlier version of the transaction request logic it was possible for a peer to prevent us from seeing a specific transaction. See https://bitcoincore.org/en/2024/07/03/disclose_already_asked_for.