Line data Source code
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 :
16 1075356 : static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
17 : {
18 1075356 : return a.m_min_ping_time > b.m_min_ping_time;
19 : }
20 :
21 648908 : static bool ReverseCompareNodeTimeConnected(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
22 : {
23 648908 : return a.m_connected > b.m_connected;
24 : }
25 :
26 1243914 : static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) {
27 1243914 : return a.nKeyedNetGroup < b.nKeyedNetGroup;
28 : }
29 :
30 1200082 : 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 1200082 : if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
34 37980 : if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
35 20204 : return a.m_connected > b.m_connected;
36 1200082 : }
37 :
38 1010578 : 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 1010578 : if (a.m_last_tx_time != b.m_last_tx_time) return a.m_last_tx_time < b.m_last_tx_time;
42 61216 : if (a.m_relay_txs != b.m_relay_txs) return b.m_relay_txs;
43 32618 : if (a.fBloomFilter != b.fBloomFilter) return a.fBloomFilter;
44 16957 : return a.m_connected > b.m_connected;
45 1010578 : }
46 :
47 : // Pick out the potential block-relay only peers, and sort them by last block time.
48 1058991 : static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
49 : {
50 1058991 : if (a.m_relay_txs != b.m_relay_txs) return a.m_relay_txs;
51 905808 : if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
52 20389 : if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
53 10559 : return a.m_connected > b.m_connected;
54 1058991 : }
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 14606 : CompareNodeNetworkTime(bool is_local, Network network) : m_is_local(is_local), m_network(network) {}
68 4286579 : bool operator()(const NodeEvictionCandidate& a, const NodeEvictionCandidate& b) const
69 : {
70 4286579 : if (m_is_local && a.m_is_local != b.m_is_local) return b.m_is_local;
71 4173158 : if ((a.m_network == m_network) != (b.m_network == m_network)) return b.m_network == m_network;
72 3768292 : return a.m_connected > b.m_connected;
73 4286579 : };
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 16899 : static void EraseLastKElements(
79 : std::vector<T>& elements, Comparator comparator, size_t k,
80 60953 : std::function<bool(const NodeEvictionCandidate&)> predicate = [](const NodeEvictionCandidate& n) { return true; })
81 : {
82 16899 : std::sort(elements.begin(), elements.end(), comparator);
83 16899 : size_t eraseSize = std::min(k, elements.size());
84 16899 : elements.erase(std::remove_if(elements.end() - eraseSize, elements.end(), predicate), elements.end());
85 16899 : }
86 :
87 1594 : void ProtectNoBanConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
88 : {
89 3188 : eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(),
90 159046 : [](NodeEvictionCandidate const& n) {
91 159046 : return n.m_noban;
92 : }),
93 1594 : eviction_candidates.end());
94 1594 : }
95 :
96 1594 : void ProtectOutboundConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
97 : {
98 3188 : eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(),
99 159046 : [](NodeEvictionCandidate const& n) {
100 159046 : return n.m_conn_type != ConnectionType::INBOUND;
101 : }),
102 1594 : eviction_candidates.end());
103 1594 : }
104 :
105 1626 : 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 1626 : const size_t initial_size = eviction_candidates.size();
114 1626 : 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 1626 : 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 8130 : for (Net& n : networks) {
124 13008 : n.count = std::count_if(eviction_candidates.cbegin(), eviction_candidates.cend(),
125 496592 : [&n](const NodeEvictionCandidate& c) {
126 490088 : 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 8822 : 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 1626 : const size_t max_protect_by_network{total_protect_size / 2};
135 1626 : size_t num_protected{0};
136 :
137 4023 : while (num_protected < max_protect_by_network) {
138 : // Count the number of disadvantaged networks from which we have peers to protect.
139 11995 : auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
140 2399 : if (num_networks == 0) {
141 2 : break;
142 : }
143 2397 : const size_t disadvantaged_to_protect{max_protect_by_network - num_protected};
144 2397 : 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 2397 : bool protected_at_least_one{false};
147 :
148 8569 : for (Net& n : networks) {
149 7585 : if (n.count == 0) continue;
150 7303 : const size_t before = eviction_candidates.size();
151 14606 : EraseLastKElements(eviction_candidates, CompareNodeNetworkTime(n.is_local, n.id),
152 37450 : protect_per_network, [&n](const NodeEvictionCandidate& c) {
153 30147 : return n.is_local ? c.m_is_local : c.m_network == n.id;
154 : });
155 7303 : const size_t after = eviction_candidates.size();
156 7303 : if (before > after) {
157 7303 : protected_at_least_one = true;
158 7303 : const size_t delta{before - after};
159 7303 : num_protected += delta;
160 7303 : if (num_protected >= max_protect_by_network) {
161 1413 : break;
162 : }
163 5890 : n.count -= delta;
164 5890 : }
165 : }
166 2397 : if (!protected_at_least_one) {
167 0 : 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 1626 : assert(num_protected == initial_size - eviction_candidates.size());
174 1626 : const size_t remaining_to_protect{total_protect_size - num_protected};
175 1626 : EraseLastKElements(eviction_candidates, ReverseCompareNodeTimeConnected, remaining_to_protect);
176 1626 : }
177 :
178 1594 : [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)
179 : {
180 : // Protect connections with certain characteristics
181 :
182 1594 : ProtectNoBanConnections(vEvictionCandidates);
183 :
184 1594 : ProtectOutboundConnections(vEvictionCandidates);
185 :
186 : // Deterministically select 4 peers to protect by netgroup.
187 : // An attacker cannot predict which netgroups will be protected
188 1594 : 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 1594 : 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 1594 : EraseLastKElements(vEvictionCandidates, CompareNodeTXTime, 4);
195 : // Protect up to 8 non-tx-relay peers that have sent us novel blocks.
196 3188 : EraseLastKElements(vEvictionCandidates, CompareNodeBlockRelayOnlyTime, 8,
197 13034 : [](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 1594 : EraseLastKElements(vEvictionCandidates, CompareNodeBlockTime, 4);
202 :
203 : // Protect some of the remaining eviction candidates by ratios of desirable
204 : // or disadvantaged characteristics.
205 1594 : ProtectEvictionCandidatesByRatio(vEvictionCandidates);
206 :
207 1594 : 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 4124 : if (std::any_of(vEvictionCandidates.begin(),vEvictionCandidates.end(),[](NodeEvictionCandidate const &n){return n.prefer_evict;})) {
213 2784 : vEvictionCandidates.erase(std::remove_if(vEvictionCandidates.begin(),vEvictionCandidates.end(),
214 62761 : [](NodeEvictionCandidate const &n){return !n.prefer_evict;}),vEvictionCandidates.end());
215 1392 : }
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 1412 : unsigned int nMostConnections = 0;
221 1412 : std::chrono::seconds nMostConnectionsTime{0};
222 1412 : std::map<uint64_t, std::vector<NodeEvictionCandidate> > mapNetGroupNodes;
223 32105 : for (const NodeEvictionCandidate &node : vEvictionCandidates) {
224 30693 : std::vector<NodeEvictionCandidate> &group = mapNetGroupNodes[node.nKeyedNetGroup];
225 30693 : group.push_back(node);
226 30693 : const auto grouptime{group[0].m_connected};
227 :
228 30693 : if (group.size() > nMostConnections || (group.size() == nMostConnections && grouptime > nMostConnectionsTime)) {
229 2738 : nMostConnections = group.size();
230 2738 : nMostConnectionsTime = grouptime;
231 2738 : naMostConnections = node.nKeyedNetGroup;
232 2738 : }
233 : }
234 :
235 : // Reduce to the network group with the most connections
236 1412 : vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]);
237 :
238 : // Disconnect from the network group with the most connections
239 1412 : return vEvictionCandidates.front().id;
240 1594 : }
|
