Bitcoin ABC  0.22.12
P2P Digital Currency
peermanager_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
8 #include <avalanche/test/util.h>
9 #include <script/standard.h>
10 #include <validation.h>
11 
12 #include <test/util/setup_common.h>
13 
14 #include <boost/test/unit_test.hpp>
15 
16 using namespace avalanche;
17 
18 BOOST_FIXTURE_TEST_SUITE(peermanager_tests, TestingSetup)
19 
20 BOOST_AUTO_TEST_CASE(select_peer_linear) {
21  // No peers.
24 
25  // One peer
26  const std::vector<Slot> oneslot = {{100, 100, 23}};
27 
28  // Undershoot
29  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 0, 300), NO_PEER);
30  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 42, 300), NO_PEER);
31  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 99, 300), NO_PEER);
32 
33  // Nailed it
34  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 100, 300), 23);
35  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 142, 300), 23);
36  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 199, 300), 23);
37 
38  // Overshoot
39  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 200, 300), NO_PEER);
40  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 242, 300), NO_PEER);
41  BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 299, 300), NO_PEER);
42 
43  // Two peers
44  const std::vector<Slot> twoslots = {{100, 100, 69}, {300, 100, 42}};
45 
46  // Undershoot
47  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 0, 500), NO_PEER);
48  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 42, 500), NO_PEER);
49  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 99, 500), NO_PEER);
50 
51  // First entry
52  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 100, 500), 69);
53  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 142, 500), 69);
54  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 199, 500), 69);
55 
56  // In between
57  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 200, 500), NO_PEER);
58  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 242, 500), NO_PEER);
59  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 299, 500), NO_PEER);
60 
61  // Second entry
62  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 300, 500), 42);
63  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 342, 500), 42);
64  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 399, 500), 42);
65 
66  // Overshoot
67  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 400, 500), NO_PEER);
68  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 442, 500), NO_PEER);
69  BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 499, 500), NO_PEER);
70 }
71 
72 BOOST_AUTO_TEST_CASE(select_peer_dichotomic) {
73  std::vector<Slot> slots;
74 
75  // 100 peers of size 1 with 1 empty element apart.
76  uint64_t max = 1;
77  for (int i = 0; i < 100; i++) {
78  slots.emplace_back(max, 1, i);
79  max += 2;
80  }
81 
82  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 4, max), NO_PEER);
83 
84  // Check that we get what we expect.
85  for (int i = 0; i < 100; i++) {
86  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER);
87  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i + 1, max), i);
88  }
89 
90  BOOST_CHECK_EQUAL(selectPeerImpl(slots, max, max), NO_PEER);
91 
92  // Update the slots to be heavily skewed toward the last element.
93  slots[99] = slots[99].withScore(101);
94  max = slots[99].getStop();
95  BOOST_CHECK_EQUAL(max, 300);
96 
97  for (int i = 0; i < 100; i++) {
98  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER);
99  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i + 1, max), i);
100  }
101 
102  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 200, max), 99);
103  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 256, max), 99);
104  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 299, max), 99);
105  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 300, max), NO_PEER);
106 
107  // Update the slots to be heavily skewed toward the first element.
108  for (int i = 0; i < 100; i++) {
109  slots[i] = slots[i].withStart(slots[i].getStart() + 100);
110  }
111 
112  slots[0] = Slot(1, slots[0].getStop() - 1, slots[0].getPeerId());
113  slots[99] = slots[99].withScore(1);
114  max = slots[99].getStop();
115  BOOST_CHECK_EQUAL(max, 300);
116 
117  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 0, max), NO_PEER);
118  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 1, max), 0);
119  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 42, max), 0);
120 
121  for (int i = 0; i < 100; i++) {
122  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 100 + 2 * i + 1, max), i);
123  BOOST_CHECK_EQUAL(selectPeerImpl(slots, 100 + 2 * i + 2, max), NO_PEER);
124  }
125 }
126 
127 BOOST_AUTO_TEST_CASE(select_peer_random) {
128  for (int c = 0; c < 1000; c++) {
129  size_t size = InsecureRandBits(10) + 1;
130  std::vector<Slot> slots;
131  slots.reserve(size);
132 
133  uint64_t max = InsecureRandBits(3);
134  auto next = [&]() {
135  uint64_t r = max;
136  max += InsecureRandBits(3);
137  return r;
138  };
139 
140  for (size_t i = 0; i < size; i++) {
141  const uint64_t start = next();
142  const uint32_t score = InsecureRandBits(3);
143  max += score;
144  slots.emplace_back(start, score, i);
145  }
146 
147  for (int k = 0; k < 100; k++) {
148  uint64_t s = max > 0 ? InsecureRandRange(max) : 0;
149  auto i = selectPeerImpl(slots, s, max);
150  // /!\ Because of the way we construct the vector, the peer id is
151  // always the index. This might not be the case in practice.
152  BOOST_CHECK(i == NO_PEER || slots[i].contains(s));
153  }
154  }
155 }
156 
157 BOOST_AUTO_TEST_CASE(peer_probabilities) {
158  // No peers.
159  PeerManager pm;
161 
162  const NodeId node0 = 42, node1 = 69, node2 = 37;
163 
164  // One peer, we always return it.
165  Proof proof0 = buildRandomProof(100);
166  Delegation dg0 = DelegationBuilder(proof0).build();
167  pm.addNode(node0, proof0, dg0);
168  BOOST_CHECK_EQUAL(pm.selectNode(), node0);
169 
170  // Two peers, verify ratio.
171  Proof proof1 = buildRandomProof(200);
172  Delegation dg1 = DelegationBuilder(proof1).build();
173  pm.addNode(node1, proof1, dg1);
174 
175  std::unordered_map<PeerId, int> results = {};
176  for (int i = 0; i < 10000; i++) {
177  size_t n = pm.selectNode();
178  BOOST_CHECK(n == node0 || n == node1);
179  results[n]++;
180  }
181 
182  BOOST_CHECK(abs(2 * results[0] - results[1]) < 500);
183 
184  // Three peers, verify ratio.
185  Proof proof2 = buildRandomProof(100);
186  Delegation dg2 = DelegationBuilder(proof2).build();
187  pm.addNode(node2, proof2, dg2);
188 
189  results.clear();
190  for (int i = 0; i < 10000; i++) {
191  size_t n = pm.selectNode();
192  BOOST_CHECK(n == node0 || n == node1 || n == node2);
193  results[n]++;
194  }
195 
196  BOOST_CHECK(abs(results[0] - results[1] + results[2]) < 500);
197 }
198 
199 BOOST_AUTO_TEST_CASE(remove_peer) {
200  // No peers.
201  PeerManager pm;
203 
204  // Add 4 peers.
205  std::array<PeerId, 8> peerids;
206  for (int i = 0; i < 4; i++) {
207  Proof p = buildRandomProof(100);
208  peerids[i] = pm.getPeerId(p);
209  BOOST_CHECK(
210  pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
211  }
212 
213  BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
215 
216  for (int i = 0; i < 100; i++) {
217  PeerId p = pm.selectPeer();
218  BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
219  p == peerids[3]);
220  }
221 
222  // Remove one peer, it nevers show up now.
223  BOOST_CHECK(pm.removePeer(peerids[2]));
224  BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
226 
227  // Make sure we compact to never get NO_PEER.
228  BOOST_CHECK_EQUAL(pm.compact(), 100);
229  BOOST_CHECK(pm.verify());
230  BOOST_CHECK_EQUAL(pm.getSlotCount(), 300);
232 
233  for (int i = 0; i < 100; i++) {
234  PeerId p = pm.selectPeer();
235  BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[3]);
236  }
237 
238  // Add 4 more peers.
239  for (int i = 0; i < 4; i++) {
240  Proof p = buildRandomProof(100);
241  peerids[i + 4] = pm.getPeerId(p);
242  BOOST_CHECK(
243  pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
244  }
245 
246  BOOST_CHECK_EQUAL(pm.getSlotCount(), 700);
248 
249  BOOST_CHECK(pm.removePeer(peerids[0]));
250  BOOST_CHECK_EQUAL(pm.getSlotCount(), 700);
252 
253  // Removing the last entry do not increase fragmentation.
254  BOOST_CHECK(pm.removePeer(peerids[7]));
255  BOOST_CHECK_EQUAL(pm.getSlotCount(), 600);
257 
258  // Make sure we compact to never get NO_PEER.
259  BOOST_CHECK_EQUAL(pm.compact(), 100);
260  BOOST_CHECK(pm.verify());
261  BOOST_CHECK_EQUAL(pm.getSlotCount(), 500);
263 
264  for (int i = 0; i < 100; i++) {
265  PeerId p = pm.selectPeer();
266  BOOST_CHECK(p == peerids[1] || p == peerids[3] || p == peerids[4] ||
267  p == peerids[5] || p == peerids[6]);
268  }
269 
270  // Removing non existent peers fails.
271  BOOST_CHECK(!pm.removePeer(peerids[0]));
272  BOOST_CHECK(!pm.removePeer(peerids[2]));
273  BOOST_CHECK(!pm.removePeer(peerids[7]));
275 }
276 
277 BOOST_AUTO_TEST_CASE(compact_slots) {
278  PeerManager pm;
279 
280  // Add 4 peers.
281  std::array<PeerId, 4> peerids;
282  for (int i = 0; i < 4; i++) {
283  Proof p = buildRandomProof(100);
284  peerids[i] = pm.getPeerId(p);
285  BOOST_CHECK(
286  pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
287  }
288 
289  // Remove all peers.
290  for (auto p : peerids) {
291  pm.removePeer(p);
292  }
293 
294  BOOST_CHECK_EQUAL(pm.getSlotCount(), 300);
296 
297  for (int i = 0; i < 100; i++) {
299  }
300 
301  BOOST_CHECK_EQUAL(pm.compact(), 300);
302  BOOST_CHECK(pm.verify());
305 }
306 
308  PeerManager pm;
309 
310  // Create one peer.
311  Proof proof = buildRandomProof(100000000);
312  Delegation dg = DelegationBuilder(proof).build();
314 
315  // Add 4 nodes.
316  for (int i = 0; i < 4; i++) {
317  BOOST_CHECK(pm.addNode(i, proof, dg));
318  }
319 
320  for (int i = 0; i < 100; i++) {
321  NodeId n = pm.selectNode();
322  BOOST_CHECK(n >= 0 && n < 4);
323  BOOST_CHECK(
324  pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
325  }
326 
327  // Remove a node, check that it doesn't show up.
328  BOOST_CHECK(pm.removeNode(2));
329 
330  for (int i = 0; i < 100; i++) {
331  NodeId n = pm.selectNode();
332  BOOST_CHECK(n == 0 || n == 1 || n == 3);
333  BOOST_CHECK(
334  pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
335  }
336 
337  // Push a node's timeout in the future, so that it doesn't show up.
338  BOOST_CHECK(pm.updateNextRequestTime(1, std::chrono::steady_clock::now() +
339  std::chrono::hours(24)));
340 
341  for (int i = 0; i < 100; i++) {
342  NodeId n = pm.selectNode();
343  BOOST_CHECK(n == 0 || n == 3);
344  BOOST_CHECK(
345  pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
346  }
347 
348  // Move a node from a peer to another. This peer has a very low score such
349  // as chances of being picked are 1 in a billion.
350  Proof altproof = buildRandomProof(1);
351  Delegation altdg = DelegationBuilder(altproof).build();
352  BOOST_CHECK(pm.addNode(3, altproof, altdg));
353 
354  int node3selected = 0;
355  for (int i = 0; i < 100; i++) {
356  NodeId n = pm.selectNode();
357  if (n == 3) {
358  // Selecting this node should be exceedingly unlikely.
359  BOOST_CHECK(node3selected++ < 1);
360  } else {
361  BOOST_CHECK_EQUAL(n, 0);
362  }
363  BOOST_CHECK(
364  pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
365  }
366 }
367 
368 BOOST_AUTO_TEST_CASE(proof_conflict) {
369  CKey key;
370  key.MakeNewKey(true);
371  const CScript script = GetScriptForDestination(PKHash(key.GetPubKey()));
372 
373  TxId txid1(GetRandHash());
374  TxId txid2(GetRandHash());
375  BOOST_CHECK(txid1 != txid2);
376 
377  const Amount v = 5 * COIN;
378  const int height = 1234;
379 
380  {
381  LOCK(cs_main);
383 
384  for (int i = 0; i < 10; i++) {
385  coins.AddCoin(COutPoint(txid1, i),
386  Coin(CTxOut(v, script), height, false), false);
387  coins.AddCoin(COutPoint(txid2, i),
388  Coin(CTxOut(v, script), height, false), false);
389  }
390  }
391 
392  PeerManager pm;
393  const auto getPeerId = [&](const std::vector<COutPoint> &outpoints) {
394  ProofBuilder pb(0, 0, CPubKey());
395  for (const auto &o : outpoints) {
396  pb.addUTXO(o, v, height, false, key);
397  }
398 
399  return pm.getPeerId(pb.build());
400  };
401 
402  // Add one peer.
403  const PeerId peer1 = getPeerId({COutPoint(txid1, 0)});
404  BOOST_CHECK(peer1 != NO_PEER);
405 
406  // Same proof, same peer.
407  BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0)}), peer1);
408 
409  // Different txid, different proof.
410  const PeerId peer2 = getPeerId({COutPoint(txid2, 0)});
411  BOOST_CHECK(peer2 != NO_PEER && peer2 != peer1);
412 
413  // Different index, different proof.
414  const PeerId peer3 = getPeerId({COutPoint(txid1, 1)});
415  BOOST_CHECK(peer3 != NO_PEER && peer3 != peer1);
416 
417  // Empty proof, no peer.
418  BOOST_CHECK_EQUAL(getPeerId({}), NO_PEER);
419 
420  // Multiple inputs.
421  const PeerId peer4 = getPeerId({COutPoint(txid1, 2), COutPoint(txid2, 2)});
422  BOOST_CHECK(peer4 != NO_PEER && peer4 != peer1);
423 
424  // Duplicated input.
425  BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 3), COutPoint(txid1, 3)}),
426  NO_PEER);
427 
428  // Multiple inputs, collision on first input.
429  BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0), COutPoint(txid2, 4)}),
430  NO_PEER);
431 
432  // Mutliple inputs, collision on second input.
433  BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 4), COutPoint(txid2, 0)}),
434  NO_PEER);
435 
436  // Mutliple inputs, collision on both inputs.
437  BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0), COutPoint(txid2, 2)}),
438  NO_PEER);
439 }
440 
static constexpr NodeId NO_NODE
Special NodeId that represent no node.
Definition: net.h:116
NodeId selectNode()
Randomly select a node to poll.
A UTXO entry.
Definition: coins.h:27
uint64_t getFragmentation() const
Definition: peermanager.h:186
CPubKey GetPubKey() const
Compute the public key from a private key.
Definition: key.cpp:210
uint256 GetRandHash() noexcept
Definition: random.cpp:654
uint64_t compact()
Trigger maintenance of internal datastructures.
Definition: amount.h:17
bool updateNextRequestTime(NodeId nodeid, TimePoint timeout)
PeerId selectPeerImpl(const std::vector< Slot > &slots, const uint64_t slot, const uint64_t max)
This is an internal method that is exposed for testing purposes.
Proof buildRandomProof(uint32_t score, const CPubKey &master)
Definition: util.cpp:18
CChainState & ChainstateActive()
Definition: validation.cpp:67
static constexpr Amount COIN
Definition: amount.h:153
bool removePeer(const PeerId peerid)
Remove an existing peer.
#define LOCK(cs)
Definition: sync.h:230
An encapsulated public key.
Definition: pubkey.h:31
bool addUTXO(COutPoint utxo, Amount amount, uint32_t height, bool is_coinbase, CKey key)
void MakeNewKey(bool fCompressed)
Generate a new private key using a cryptographic PRNG.
Definition: key.cpp:183
RecursiveMutex cs_main
Global state.
Definition: validation.cpp:90
bool removeNode(NodeId nodeid)
Definition: peermanager.cpp:76
BOOST_AUTO_TEST_CASE(select_peer_linear)
int64_t NodeId
Definition: net.h:111
An output of a transaction.
Definition: transaction.h:141
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
Definition: standard.cpp:246
bool verify() const
Perform consistency check on internal data structures.
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:22
bool addNode(NodeId nodeid, const Proof &proof, const Delegation &delegation)
Node API.
Definition: peermanager.cpp:16
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:429
A TxId is the identifier of a transaction.
Definition: txid.h:14
#define BOOST_AUTO_TEST_SUITE_END()
Definition: object.cpp:16
CCoinsViewCache & CoinsTip() EXCLUSIVE_LOCKS_REQUIRED(cs_main)
Definition: validation.h:831
void AddCoin(const COutPoint &outpoint, Coin coin, bool potential_overwrite)
Add a coin.
Definition: coins.cpp:103
An encapsulated secp256k1 private key.
Definition: key.h:25
uint64_t getSlotCount() const
Definition: peermanager.h:185
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:204
static constexpr PeerId NO_PEER
Definition: node.h:15
PeerId selectPeer() const
Randomly select a peer to poll.
PeerId getPeerId(const Proof &proof)
Provide the PeerId associated with the given proof.
#define BOOST_CHECK(expr)
Definition: object.cpp:17
uint32_t PeerId
Definition: node.h:14