net: make room in the block fetch table instead of refusing new blocks

Nothing on the path from inv to insertion can tell a real block hash
from thirty-two random bytes. AlreadyHave only asks whether we already
hold the block, and with no header there is no work to check. So one inv
carrying eight hashes that never existed filled all eight slots, and
because a full table refused new entries outright, no genuinely new
block was tracked again until the give-up timer expired ten minutes
later. One message per ten minutes from a single connection switched
failover off for the whole node -- not eight wasted slots, an off-switch.

A full table now evicts. Eviction on its own would just be the same
attack in a new shape, so the victim is chosen by occupancy: a peer may
only take a slot from a peer holding strictly more slots than itself,
and otherwise recycles one of its own oldest. A peer that has filled the
table is the heaviest holder by definition, so its own entries are the
only ones it can displace; a peer announcing its first block holds
nothing, so it always evicts from the heaviest. A genuine announcement
is therefore never refused a slot, whatever an attacker holds or across
however many connections it holds it.

Entries carry the announcing peer for this, set once on creation --
the failover sweep asks other peers later and none of them chose to
announce the hash, so none of them should be charged for it.

The two timestamps also get member initialisers. The insertion path uses
operator[] and tests nTimeFirstAsked == 0 to spot a fresh entry, which
worked on value-initialisation alone, but only until somebody gave the
struct a constructor -- and this commit gives it a member that wants one.

1 files changed, 97 insertions, 13 deletions

diff --git a/src/main.cpp b/src/main.cpp
index 8926d57..9ab1f44 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -75,12 +75,24 @@ multimap<uint256, CBlock*> mapOrphanBlocksByPrev;
 // Capped small on purpose. At the tip there is one block in flight; during
 // initial download there are legitimately hundreds outstanding to one peer,
 // and rotating those would duplicate the whole download to every other peer.
-// Anything past the cap is simply not tracked and behaves as before.
+//
+// The cap is a shared resource and nothing on the path from inv to insertion
+// can tell a real block hash from 32 random bytes -- AlreadyHave only asks
+// whether we already hold the block, and there is no header to check work
+// against. So the table does not refuse a new hash when it is full; it makes
+// room. See MakeRoomInBlockFetch for the rule, which is what stops one peer
+// filling all eight slots and switching failover off for everybody.
+//
+// The initialisers matter: the insertion path uses operator[] and then tests
+// nTimeFirstAsked == 0 to detect a fresh entry. That worked on
+// value-initialisation alone, but only for as long as nobody gave this struct
+// a constructor.
 struct CBlockFetch
 {
-    int64 nTimeFirstAsked;  // when the first getdata for this block went out
-    int64 nTimeAsked;       // when the latest getdata went out
-    set<CAddress> setAsked; // peers tried since the round last restarted
+    int64 nTimeFirstAsked = 0;  // when the first getdata for this block went out
+    int64 nTimeAsked      = 0;  // when the latest getdata went out
+    CAddress addrAnnounced;     // peer whose announcement put this hash here
+    set<CAddress> setAsked;     // peers tried since the round last restarted
 };
 map<uint256, CBlockFetch> mapBlockFetch;
 static const int BLOCK_FETCH_TRACK_MAX = 8;
@@ -89,6 +101,62 @@ static const int BLOCK_FETCH_TRACK_MAX = 8;
 // forever; a re-announcement recreates it.
 static const int BLOCK_FETCH_GIVEUP_SECS = 10 * 60;
 
+// Drop one entry so a hash announced by addrNew can be tracked.
+//
+// Refusing the insertion instead was a remote off-switch for the whole
+// feature. An inv carrying eight hashes that never existed filled every slot
+// -- nothing between inv and here can tell those from real blocks -- and no
+// genuinely new block was tracked again until the give-up timer expired ten
+// minutes later, re-armable for one message per ten minutes from a single
+// connection.
+//
+// So evict instead, by occupancy: a peer may only take a slot from a peer
+// holding strictly more slots than itself, and otherwise recycles one of its
+// own. That is what keeps eviction from becoming the same attack in a new
+// shape. A peer that has filled the table is by definition the heaviest
+// holder, so its own entries are the only ones it can displace, while a peer
+// announcing its first block holds nothing and therefore always evicts from
+// the heaviest -- a genuine announcement is never refused a slot, whatever the
+// attacker holds or however many connections it holds it from. The one case
+// that costs a real fetch is eight distinct peers holding one entry each,
+// where a ninth takes the oldest; that is a busy healthy node, not an attack,
+// and losing the oldest of eight beats refusing the ninth.
+static void MakeRoomInBlockFetch(const CAddress& addrNew)
+{
+    if (mapBlockFetch.empty())
+        return;
+
+    map<CAddress, int> mapHeld;
+    for (map<uint256, CBlockFetch>::iterator mi = mapBlockFetch.begin(); mi != mapBlockFetch.end(); ++mi)
+        mapHeld[(*mi).second.addrAnnounced]++;
+
+    int nMine = mapHeld.count(addrNew) ? mapHeld[addrNew] : 0;
+
+    int nMax = 0;
+    CAddress addrVictim;
+    for (map<CAddress, int>::iterator mi = mapHeld.begin(); mi != mapHeld.end(); ++mi)
+        if ((*mi).second > nMax)
+        {
+            nMax = (*mi).second;
+            addrVictim = (*mi).first;
+        }
+
+    // Nobody is holding more than this peer, so it recycles its own oldest
+    // rather than taking a slot off an equal.
+    if (nMax <= nMine)
+        addrVictim = addrNew;
+
+    map<uint256, CBlockFetch>::iterator miVictim = mapBlockFetch.end();
+    for (map<uint256, CBlockFetch>::iterator mi = mapBlockFetch.begin(); mi != mapBlockFetch.end(); ++mi)
+        if ((*mi).second.addrAnnounced == addrVictim &&
+            (miVictim == mapBlockFetch.end() ||
+             (*mi).second.nTimeFirstAsked < (*miVictim).second.nTimeFirstAsked))
+            miVictim = mi;
+
+    if (miVictim != mapBlockFetch.end())
+        mapBlockFetch.erase(miVictim);
+}
+
 map<uint256, CDataStream*> mapOrphanTransactions;
 multimap<uint256, CDataStream*> mapOrphanTransactionsByPrev;
 
@@ -3470,16 +3538,32 @@ bool SendMessages(CNode* pto)
             {
                 vAskFor.push_back(inv);
                 // Blocks get their delivery tracked so the failover pass
-                // below can chase the ones that go quiet. See mapBlockFetch
-                // for why anything past the cap is left untracked.
-                if (inv.type == MSG_BLOCK &&
-                    (mapBlockFetch.count(inv.hash) || mapBlockFetch.size() < BLOCK_FETCH_TRACK_MAX))
+                // below can chase the ones that go quiet.
+                if (inv.type == MSG_BLOCK)
                 {
-                    CBlockFetch& fetch = mapBlockFetch[inv.hash];
-                    if (fetch.nTimeFirstAsked == 0)
-                        fetch.nTimeFirstAsked = GetTime();
-                    fetch.nTimeAsked = GetTime();
-                    fetch.setAsked.insert(pto->addr);
+                    // Full, and this is a hash we are not already tracking:
+                    // make room rather than drop it on the floor, or one peer
+                    // announcing eight hashes turns failover off for everyone.
+                    if (!mapBlockFetch.count(inv.hash) &&
+                        mapBlockFetch.size() >= BLOCK_FETCH_TRACK_MAX)
+                        MakeRoomInBlockFetch(pto->addr);
+
+                    if (mapBlockFetch.count(inv.hash) ||
+                        mapBlockFetch.size() < BLOCK_FETCH_TRACK_MAX)
+                    {
+                        CBlockFetch& fetch = mapBlockFetch[inv.hash];
+                        if (fetch.nTimeFirstAsked == 0)
+                        {
+                            fetch.nTimeFirstAsked = GetTime();
+                            // Who is answerable for this hash existing. Set
+                            // once, on creation: the failover sweep asks other
+                            // peers later, and none of them chose to announce
+                            // it, so none of them should be charged for it.
+                            fetch.addrAnnounced = pto->addr;
+                        }
+                        fetch.nTimeAsked = GetTime();
+                        fetch.setAsked.insert(pto->addr);
+                    }
                 }
             }
             pto->mapAskFor.erase(pto->mapAskFor.begin());