InvRequestTrackerImplInterface Class Reference

Data structure to keep track of, and schedule, inventory downloads from peers. More...

#include <invrequest.h>

Inheritance diagram for InvRequestTrackerImplInterface:

Public Types
using	ClearExpiredFun = const std::function< void()> &
using	EmplaceExpiredFun = const std::function< void(const NodeId &, const uint256 &)> &

Public Member Functions
virtual	~InvRequestTrackerImplInterface ()=default
virtual void	ReceivedInv (NodeId peer, const uint256 &invid, bool preferred, std::chrono::microseconds reqtime)=0
virtual void	DisconnectedPeer (NodeId peer)=0
virtual void	ForgetInvId (const uint256 &invid)=0
virtual std::vector< uint256 >	GetRequestable (NodeId peer, std::chrono::microseconds now, ClearExpiredFun clearExpired, EmplaceExpiredFun emplaceExpired)=0
virtual void	RequestedData (NodeId peer, const uint256 &invid, std::chrono::microseconds expiry)=0
virtual void	ReceivedResponse (NodeId peer, const uint256 &invid)=0
virtual size_t	CountInFlight (NodeId peer) const =0
virtual size_t	CountCandidates (NodeId peer) const =0
virtual size_t	Count (NodeId peer) const =0
virtual size_t	Size () const =0
virtual uint64_t	ComputePriority (const uint256 &invid, NodeId peer, bool preferred) const =0
virtual void	SanityCheck () const =0
virtual void	PostGetRequestableSanityCheck (std::chrono::microseconds now) const =0

Static Private Member Functions
static std::unique_ptr< InvRequestTrackerImplInterface >	BuildImpl (bool deterministic)

Friends
template<class InvId >
class	InvRequestTracker

Detailed Description

Data structure to keep track of, and schedule, inventory downloads from peers.

=== Specification ===

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

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

• Which peer announced it (through their NodeId)
• The invid of the inventory
• What the earliest permitted time is that that inventory 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 inventory was requested already, and if so, when it times out (called "expiry").
• Whether or not the inventory request failed already (timed out, or invalid inventory or NOTFOUND was received).

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

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

  Rationale: to avoid wasting bandwidth on multiple copies of the same inventory.

• The same inventory 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 an inventory has been successfully received, or is otherwise no longer needed, the caller can call ForgetInvId, which removes all announcements across all peers with the specified invid.
  • If for a given invid only already-failed announcements remain, they are all forgotten.

  Rationale: giving a peer multiple chances to announce an inventory would allow them to bias requests in their favor, worsening inventory censoring attacks. The flip side is that as long as an attacker manages to prevent us from receiving an inventory, 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 inventories quickly while not answering requests for them. See https://allquantor.at/blockchainbib/pdf/miller2015topology.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 an inventory 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).

Definition at line 121 of file invrequest.h.

Member Typedef Documentation

ClearExpiredFun

using InvRequestTrackerImplInterface::ClearExpiredFun = const std::function<void()> &

Definition at line 131 of file invrequest.h.

EmplaceExpiredFun

using InvRequestTrackerImplInterface::EmplaceExpiredFun = const std::function<void(const NodeId &, const uint256 &)> &

Definition at line 132 of file invrequest.h.

Constructor & Destructor Documentation

~InvRequestTrackerImplInterface()

virtual InvRequestTrackerImplInterface::~InvRequestTrackerImplInterface ( )

virtualdefault

Member Function Documentation

BuildImpl()

std::unique_ptr< InvRequestTrackerImplInterface > InvRequestTrackerImplInterface::BuildImpl ( bool  deterministic )

staticprivate

Definition at line 863 of file invrequest.cpp.

ComputePriority()

virtual uint64_t InvRequestTrackerImplInterface::ComputePriority ( const uint256 &  invid, NodeId  peer, bool  preferred  ) const

pure virtual

Implemented in InvRequestTrackerImpl.

Count()

virtual size_t InvRequestTrackerImplInterface::Count ( NodeId  peer ) const

pure virtual

Implemented in InvRequestTrackerImpl.

CountCandidates()

virtual size_t InvRequestTrackerImplInterface::CountCandidates ( NodeId  peer ) const

pure virtual

Implemented in InvRequestTrackerImpl.

CountInFlight()

virtual size_t InvRequestTrackerImplInterface::CountInFlight ( NodeId  peer ) const

pure virtual

Implemented in InvRequestTrackerImpl.

DisconnectedPeer()

virtual void InvRequestTrackerImplInterface::DisconnectedPeer ( NodeId  peer )

pure virtual

Implemented in InvRequestTrackerImpl.

ForgetInvId()

virtual void InvRequestTrackerImplInterface::ForgetInvId ( const uint256 &  invid )

pure virtual

Implemented in InvRequestTrackerImpl.

GetRequestable()

virtual std::vector< uint256 > InvRequestTrackerImplInterface::GetRequestable ( NodeId  peer, std::chrono::microseconds  now, ClearExpiredFun  clearExpired, EmplaceExpiredFun  emplaceExpired  )

pure virtual

Implemented in InvRequestTrackerImpl.

PostGetRequestableSanityCheck()

virtual void InvRequestTrackerImplInterface::PostGetRequestableSanityCheck ( std::chrono::microseconds  now ) const

pure virtual

Implemented in InvRequestTrackerImpl.

ReceivedInv()

virtual void InvRequestTrackerImplInterface::ReceivedInv ( NodeId  peer, const uint256 &  invid, bool  preferred, std::chrono::microseconds  reqtime  )

pure virtual

Implemented in InvRequestTrackerImpl.

ReceivedResponse()

virtual void InvRequestTrackerImplInterface::ReceivedResponse ( NodeId  peer, const uint256 &  invid  )

pure virtual

Implemented in InvRequestTrackerImpl.

RequestedData()

virtual void InvRequestTrackerImplInterface::RequestedData ( NodeId  peer, const uint256 &  invid, std::chrono::microseconds  expiry  )

pure virtual

Implemented in InvRequestTrackerImpl.

SanityCheck()

virtual void InvRequestTrackerImplInterface::SanityCheck ( ) const

pure virtual

Implemented in InvRequestTrackerImpl.

Size()

virtual size_t InvRequestTrackerImplInterface::Size ( ) const

pure virtual

Implemented in InvRequestTrackerImpl.

Friends And Related Symbol Documentation

InvRequestTracker

template<class InvId >

friend class InvRequestTracker

friend

Definition at line 122 of file invrequest.h.

---

The documentation for this class was generated from the following files:

• src/invrequest.h
• src/invrequest.cpp