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