eviction.cpp
1 // Copyright (c) 2022-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <node/eviction.h> 6 7 #include <algorithm> 8 #include <array> 9 #include <chrono> 10 #include <cstdint> 11 #include <functional> 12 #include <map> 13 #include <vector> 14 15 16 static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) 17 { 18 return a.m_min_ping_time > b.m_min_ping_time; 19 } 20 21 static bool ReverseCompareNodeTimeConnected(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) 22 { 23 return a.m_connected > b.m_connected; 24 } 25 26 static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) { 27 return a.nKeyedNetGroup < b.nKeyedNetGroup; 28 } 29 30 static bool CompareNodeBlockTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) 31 { 32 // There is a fall-through here because it is common for a node to have many peers which have not yet relayed a block. 33 if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time; 34 if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices; 35 return a.m_connected > b.m_connected; 36 } 37 38 static bool CompareNodeTXTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) 39 { 40 // There is a fall-through here because it is common for a node to have more than a few peers that have not yet relayed txn. 41 if (a.m_last_tx_time != b.m_last_tx_time) return a.m_last_tx_time < b.m_last_tx_time; 42 if (a.m_relay_txs != b.m_relay_txs) return b.m_relay_txs; 43 if (a.fBloomFilter != b.fBloomFilter) return a.fBloomFilter; 44 return a.m_connected > b.m_connected; 45 } 46 47 // Pick out the potential block-relay only peers, and sort them by last block time. 48 static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) 49 { 50 if (a.m_relay_txs != b.m_relay_txs) return a.m_relay_txs; 51 if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time; 52 if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices; 53 return a.m_connected > b.m_connected; 54 } 55 56 /** 57 * Sort eviction candidates by network/localhost and connection uptime. 58 * Candidates near the beginning are more likely to be evicted, and those 59 * near the end are more likely to be protected, e.g. less likely to be evicted. 60 * - First, nodes that are not `is_local` and that do not belong to `network`, 61 * sorted by increasing uptime (from most recently connected to connected longer). 62 * - Then, nodes that are `is_local` or belong to `network`, sorted by increasing uptime. 63 */ 64 struct CompareNodeNetworkTime { 65 const bool m_is_local; 66 const Network m_network; 67 CompareNodeNetworkTime(bool is_local, Network network) : m_is_local(is_local), m_network(network) {} 68 bool operator()(const NodeEvictionCandidate& a, const NodeEvictionCandidate& b) const 69 { 70 if (m_is_local && a.m_is_local != b.m_is_local) return b.m_is_local; 71 if ((a.m_network == m_network) != (b.m_network == m_network)) return b.m_network == m_network; 72 return a.m_connected > b.m_connected; 73 }; 74 }; 75 76 //! Sort an array by the specified comparator, then erase the last K elements where predicate is true. 77 template <typename T, typename Comparator> 78 static void EraseLastKElements( 79 std::vector<T>& elements, Comparator comparator, size_t k, 80 std::function<bool(const NodeEvictionCandidate&)> predicate = [](const NodeEvictionCandidate& n) { return true; }) 81 { 82 std::sort(elements.begin(), elements.end(), comparator); 83 size_t eraseSize = std::min(k, elements.size()); 84 elements.erase(std::remove_if(elements.end() - eraseSize, elements.end(), predicate), elements.end()); 85 } 86 87 void ProtectNoBanConnections(std::vector<NodeEvictionCandidate>& eviction_candidates) 88 { 89 eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(), 90 [](NodeEvictionCandidate const& n) { 91 return n.m_noban; 92 }), 93 eviction_candidates.end()); 94 } 95 96 void ProtectOutboundConnections(std::vector<NodeEvictionCandidate>& eviction_candidates) 97 { 98 eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(), 99 [](NodeEvictionCandidate const& n) { 100 return n.m_conn_type != ConnectionType::INBOUND; 101 }), 102 eviction_candidates.end()); 103 } 104 105 void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& eviction_candidates) 106 { 107 // Protect the half of the remaining nodes which have been connected the longest. 108 // This replicates the non-eviction implicit behavior, and precludes attacks that start later. 109 // To favorise the diversity of our peer connections, reserve up to half of these protected 110 // spots for Tor/onion, localhost, I2P, and CJDNS peers, even if they're not longest uptime 111 // overall. This helps protect these higher-latency peers that tend to be otherwise 112 // disadvantaged under our eviction criteria. 113 const size_t initial_size = eviction_candidates.size(); 114 const size_t total_protect_size{initial_size / 2}; 115 116 // Disadvantaged networks to protect. In the case of equal counts, earlier array members 117 // have the first opportunity to recover unused slots from the previous iteration. 118 struct Net { bool is_local; Network id; size_t count; }; 119 std::array<Net, 4> networks{ 120 {{false, NET_CJDNS, 0}, {false, NET_I2P, 0}, {/*localhost=*/true, NET_MAX, 0}, {false, NET_ONION, 0}}}; 121 122 // Count and store the number of eviction candidates per network. 123 for (Net& n : networks) { 124 n.count = std::count_if(eviction_candidates.cbegin(), eviction_candidates.cend(), 125 [&n](const NodeEvictionCandidate& c) { 126 return n.is_local ? c.m_is_local : c.m_network == n.id; 127 }); 128 } 129 // Sort `networks` by ascending candidate count, to give networks having fewer candidates 130 // the first opportunity to recover unused protected slots from the previous iteration. 131 std::stable_sort(networks.begin(), networks.end(), [](Net a, Net b) { return a.count < b.count; }); 132 133 // Protect up to 25% of the eviction candidates by disadvantaged network. 134 const size_t max_protect_by_network{total_protect_size / 2}; 135 size_t num_protected{0}; 136 137 while (num_protected < max_protect_by_network) { 138 // Count the number of disadvantaged networks from which we have peers to protect. 139 auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; }); 140 if (num_networks == 0) { 141 break; 142 } 143 const size_t disadvantaged_to_protect{max_protect_by_network - num_protected}; 144 const size_t protect_per_network{std::max(disadvantaged_to_protect / num_networks, static_cast<size_t>(1))}; 145 // Early exit flag if there are no remaining candidates by disadvantaged network. 146 bool protected_at_least_one{false}; 147 148 for (Net& n : networks) { 149 if (n.count == 0) continue; 150 const size_t before = eviction_candidates.size(); 151 EraseLastKElements(eviction_candidates, CompareNodeNetworkTime(n.is_local, n.id), 152 protect_per_network, [&n](const NodeEvictionCandidate& c) { 153 return n.is_local ? c.m_is_local : c.m_network == n.id; 154 }); 155 const size_t after = eviction_candidates.size(); 156 if (before > after) { 157 protected_at_least_one = true; 158 const size_t delta{before - after}; 159 num_protected += delta; 160 if (num_protected >= max_protect_by_network) { 161 break; 162 } 163 n.count -= delta; 164 } 165 } 166 if (!protected_at_least_one) { 167 break; 168 } 169 } 170 171 // Calculate how many we removed, and update our total number of peers that 172 // we want to protect based on uptime accordingly. 173 assert(num_protected == initial_size - eviction_candidates.size()); 174 const size_t remaining_to_protect{total_protect_size - num_protected}; 175 EraseLastKElements(eviction_candidates, ReverseCompareNodeTimeConnected, remaining_to_protect); 176 } 177 178 [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates) 179 { 180 // Protect connections with certain characteristics 181 182 ProtectNoBanConnections(vEvictionCandidates); 183 184 ProtectOutboundConnections(vEvictionCandidates); 185 186 // Deterministically select 4 peers to protect by netgroup. 187 // An attacker cannot predict which netgroups will be protected 188 EraseLastKElements(vEvictionCandidates, CompareNetGroupKeyed, 4); 189 // Protect the 8 nodes with the lowest minimum ping time. 190 // An attacker cannot manipulate this metric without physically moving nodes closer to the target. 191 EraseLastKElements(vEvictionCandidates, ReverseCompareNodeMinPingTime, 8); 192 // Protect 4 nodes that most recently sent us novel transactions accepted into our mempool. 193 // An attacker cannot manipulate this metric without performing useful work. 194 EraseLastKElements(vEvictionCandidates, CompareNodeTXTime, 4); 195 // Protect up to 8 non-tx-relay peers that have sent us novel blocks. 196 EraseLastKElements(vEvictionCandidates, CompareNodeBlockRelayOnlyTime, 8, 197 [](const NodeEvictionCandidate& n) { return !n.m_relay_txs && n.fRelevantServices; }); 198 199 // Protect 4 nodes that most recently sent us novel blocks. 200 // An attacker cannot manipulate this metric without performing useful work. 201 EraseLastKElements(vEvictionCandidates, CompareNodeBlockTime, 4); 202 203 // Protect some of the remaining eviction candidates by ratios of desirable 204 // or disadvantaged characteristics. 205 ProtectEvictionCandidatesByRatio(vEvictionCandidates); 206 207 if (vEvictionCandidates.empty()) return std::nullopt; 208 209 // If any remaining peers are preferred for eviction consider only them. 210 // This happens after the other preferences since if a peer is really the best by other criteria (esp relaying blocks) 211 // then we probably don't want to evict it no matter what. 212 if (std::any_of(vEvictionCandidates.begin(),vEvictionCandidates.end(),[](NodeEvictionCandidate const &n){return n.prefer_evict;})) { 213 vEvictionCandidates.erase(std::remove_if(vEvictionCandidates.begin(),vEvictionCandidates.end(), 214 [](NodeEvictionCandidate const &n){return !n.prefer_evict;}),vEvictionCandidates.end()); 215 } 216 217 // Identify the network group with the most connections and youngest member. 218 // (vEvictionCandidates is already sorted by reverse connect time) 219 uint64_t naMostConnections; 220 unsigned int nMostConnections = 0; 221 NodeClock::time_point nMostConnectionsTime{NodeClock::epoch}; 222 std::map<uint64_t, std::vector<NodeEvictionCandidate> > mapNetGroupNodes; 223 for (const NodeEvictionCandidate &node : vEvictionCandidates) { 224 std::vector<NodeEvictionCandidate> &group = mapNetGroupNodes[node.nKeyedNetGroup]; 225 group.push_back(node); 226 const auto grouptime{group[0].m_connected}; 227 228 if (group.size() > nMostConnections || (group.size() == nMostConnections && grouptime > nMostConnectionsTime)) { 229 nMostConnections = group.size(); 230 nMostConnectionsTime = grouptime; 231 naMostConnections = node.nKeyedNetGroup; 232 } 233 } 234 235 // Reduce to the network group with the most connections 236 vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]); 237 238 // Disconnect from the network group with the most connections 239 return vEvictionCandidates.front().id; 240 }