Bitcoin Core  24.99.0
P2P Digital Currency
eviction.cpp
Go to the documentation of this file.
1 // Copyright (c) 2022 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 
17 {
18  return a.m_min_ping_time > b.m_min_ping_time;
19 }
20 
22 {
23  return a.m_connected > b.m_connected;
24 }
25 
27  return a.nKeyedNetGroup < b.nKeyedNetGroup;
28 }
29 
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.
35  return a.m_connected > b.m_connected;
36 }
37 
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.
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.
49 {
50  if (a.m_relay_txs != b.m_relay_txs) return a.m_relay_txs;
53  return a.m_connected > b.m_connected;
54 }
55 
65  const bool m_is_local;
67  CompareNodeNetworkTime(bool is_local, Network network) : m_is_local(is_local), m_network(network) {}
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 
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  std::chrono::seconds nMostConnectionsTime{0};
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 }
static bool CompareNodeBlockTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:30
static void EraseLastKElements(std::vector< T > &elements, Comparator comparator, size_t k, std::function< bool(const NodeEvictionCandidate &)> predicate=[](const NodeEvictionCandidate &n) { return true;})
Sort an array by the specified comparator, then erase the last K elements where predicate is true.
Definition: eviction.cpp:78
static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:48
void ProtectNoBanConnections(std::vector< NodeEvictionCandidate > &eviction_candidates)
Definition: eviction.cpp:87
static bool ReverseCompareNodeTimeConnected(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:21
static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:26
void ProtectEvictionCandidatesByRatio(std::vector< NodeEvictionCandidate > &eviction_candidates)
Protect desirable or disadvantaged inbound peers from eviction by ratio.
Definition: eviction.cpp:105
static bool CompareNodeTXTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:38
std::optional< NodeId > SelectNodeToEvict(std::vector< NodeEvictionCandidate > &&vEvictionCandidates)
Select an inbound peer to evict after filtering out (protecting) peers having distinct,...
Definition: eviction.cpp:178
void ProtectOutboundConnections(std::vector< NodeEvictionCandidate > &eviction_candidates)
Definition: eviction.cpp:96
static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
Definition: eviction.cpp:16
Definition: init.h:25
Network
A network type.
Definition: netaddress.h:44
@ NET_I2P
I2P.
Definition: netaddress.h:58
@ NET_CJDNS
CJDNS.
Definition: netaddress.h:61
@ NET_MAX
Dummy value to indicate the number of NET_* constants.
Definition: netaddress.h:68
@ NET_ONION
TOR (v2 or v3)
Definition: netaddress.h:55
Sort eviction candidates by network/localhost and connection uptime.
Definition: eviction.cpp:64
CompareNodeNetworkTime(bool is_local, Network network)
Definition: eviction.cpp:67
const Network m_network
Definition: eviction.cpp:66
bool operator()(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) const
Definition: eviction.cpp:68
const bool m_is_local
Definition: eviction.cpp:65
std::chrono::seconds m_last_tx_time
Definition: eviction.h:23
std::chrono::seconds m_connected
Definition: eviction.h:20
std::chrono::seconds m_last_block_time
Definition: eviction.h:22
std::chrono::microseconds m_min_ping_time
Definition: eviction.h:21
uint64_t nKeyedNetGroup
Definition: eviction.h:27
static int count
Definition: tests.c:33
assert(!tx.IsCoinBase())