Bitcoin ABC  0.26.3
P2P Digital Currency
voterecord_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2018-2022 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 
5 #include <avalanche/voterecord.h>
6 
7 #include <test/util/setup_common.h>
8 
9 #include <boost/test/unit_test.hpp>
10 
11 using namespace avalanche;
12 
14  NodeId currentNodeId = -1;
15 
17  currentNodeId++;
18  if (currentNodeId >= 8) {
19  currentNodeId = 0;
20  }
21  return currentNodeId;
22  }
23 };
24 
26 
27 #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, stale, confidence) \
28  vr.registerVote(nextNodeId(), vote); \
29  BOOST_CHECK_EQUAL(vr.isAccepted(), state); \
30  BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \
31  BOOST_CHECK_EQUAL(vr.isStale(), stale); \
32  BOOST_CHECK_EQUAL(vr.getConfidence(), confidence);
33 
34 BOOST_AUTO_TEST_CASE(vote_record) {
35  VoteRecord vraccepted(true);
36 
37  // Check initial state.
38  BOOST_CHECK_EQUAL(vraccepted.isAccepted(), true);
39  BOOST_CHECK_EQUAL(vraccepted.hasFinalized(), false);
40  BOOST_CHECK_EQUAL(vraccepted.isStale(), false);
41  BOOST_CHECK_EQUAL(vraccepted.getConfidence(), 0);
42 
43  VoteRecord vr(false);
44 
45  // Check initial state.
46  BOOST_CHECK_EQUAL(vr.isAccepted(), false);
47  BOOST_CHECK_EQUAL(vr.hasFinalized(), false);
48  BOOST_CHECK_EQUAL(vr.isStale(), false);
50 
51  // We need to register 6 positive votes before we start counting.
52  for (int i = 0; i < 6; i++) {
53  REGISTER_VOTE_AND_CHECK(vr, 0, false, false, false, 0);
54  }
55 
56  // Next vote will flip state, and confidence will increase as long as we
57  // vote yes.
58  REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, 0);
59 
60  // A single neutral vote do not change anything.
61  REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 1);
62  for (int i = 2; i < 8; i++) {
63  REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, i);
64  }
65 
66  // Two neutral votes will stall progress.
67  REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7);
68  REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7);
69  for (int i = 2; i < 8; i++) {
70  REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, 7);
71  }
72 
73  // Now confidence will increase as long as we vote yes.
74  for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) {
75  REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, i);
76  }
77 
78  // The next vote will finalize the decision.
79  REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false,
81 
82  // Now that we have two no votes, confidence stop increasing.
83  for (int i = 0; i < 5; i++) {
84  REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false,
86  }
87 
88  // Next vote will flip state, and confidence will increase as long as we
89  // vote no.
90  REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 0);
91 
92  // A single neutral vote do not change anything.
93  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 1);
94  for (int i = 2; i < 8; i++) {
95  REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, i);
96  }
97 
98  // Two neutral votes will stall progress.
99  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7);
100  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7);
101  for (int i = 2; i < 8; i++) {
102  REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 7);
103  }
104 
105  // Now confidence will increase as long as we vote no.
106  for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) {
107  REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, i);
108  }
109 
110  // The next vote will finalize the decision.
111  REGISTER_VOTE_AND_CHECK(vr, 0, false, true, false,
113 
114  // Check that inflight accounting work as expected.
115  VoteRecord vrinflight(false);
116  for (int i = 0; i < 2 * AVALANCHE_MAX_INFLIGHT_POLL; i++) {
117  bool shouldPoll = vrinflight.shouldPoll();
119  BOOST_CHECK_EQUAL(vrinflight.registerPoll(), shouldPoll);
120  }
121 
122  // Clear various number of inflight requests and check everything behaves as
123  // expected.
124  for (int i = 1; i < AVALANCHE_MAX_INFLIGHT_POLL; i++) {
125  vrinflight.clearInflightRequest(i);
126  BOOST_CHECK(vrinflight.shouldPoll());
127 
128  for (int j = 1; j < i; j++) {
129  BOOST_CHECK(vrinflight.registerPoll());
130  BOOST_CHECK(vrinflight.shouldPoll());
131  }
132 
133  BOOST_CHECK(vrinflight.registerPoll());
134  BOOST_CHECK(!vrinflight.shouldPoll());
135  }
136 }
137 
138 // Test some cases where confidence never advances
139 BOOST_AUTO_TEST_CASE(stale_vote_always_inconclusive) {
140  // Setup a record that is inconclusive so far
141  VoteRecord vr(false);
142 
143  for (uint32_t i = 0; i < AVALANCHE_VOTE_STALE_THRESHOLD / 8; i++) {
144  // Vote randomly, but such that there's always enough neutral votes to
145  // not gain confidence.
146  for (auto j = 0; j < 6; j++) {
147  REGISTER_VOTE_AND_CHECK(vr, InsecureRand32(), false, false, false,
148  0);
149  }
150  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
151  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
152  }
153 
154  // Vote record becomes stale after too many rounds of inconclusive voting
155  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, true, 0);
156 }
157 
158 // Test all cases where records reach a specific confidence level and then go
159 // stale.
160 BOOST_AUTO_TEST_CASE(stale_vote_at_all_confidence_levels) {
161  for (uint32_t vote = 0; vote <= 1; vote++) {
162  for (uint32_t confidence = 0; confidence < AVALANCHE_FINALIZATION_SCORE;
163  confidence++) {
164  VoteRecord vr(!vote);
165 
166  // Prepare to increase confidence with some votes
167  for (auto i = 0; i < 5; i++) {
168  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 0);
169  }
170 
171  // Increase to target confidence
172  for (uint32_t i = 0; i < confidence; i++) {
173  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, i);
174  }
175 
176  uint32_t remainingVotes =
177  AVALANCHE_VOTE_STALE_THRESHOLD - confidence - 5;
178 
179  // Special case where staying at confidence of 1 requires a
180  // different vote between agreeing votes
181  if (confidence == 1) {
182  REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false, 0);
183  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 1);
184  remainingVotes -= 2;
185  }
186 
187  // Vote neutral until stale
188  if (confidence >
190  remainingVotes =
191  confidence * AVALANCHE_VOTE_STALE_FACTOR - confidence - 5;
192  }
193  for (uint32_t i = 0; i < remainingVotes; i++) {
194  REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false,
195  confidence);
196  }
197  REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, true, confidence);
198  }
199  }
200 }
201 
202 // Test some cases where confidence may flip flop and then goes stale.
203 BOOST_AUTO_TEST_CASE(stale_vote_random_then_inconclusive) {
204  VoteRecord vr(false);
205 
206  for (uint32_t i = 0; i < AVALANCHE_FINALIZATION_SCORE - 14; i++) {
207  // Vote randomly. Confidence changes are ok.
208  vr.registerVote(nextNodeId(), InsecureRand32());
209  BOOST_CHECK_EQUAL(vr.hasFinalized(), false);
210  BOOST_CHECK_EQUAL(vr.isStale(), false);
211  }
212 
213  // Reset confidence, no matter what it is right now
214  for (uint32_t i = 0; i < 7; i++) {
215  vr.registerVote(nextNodeId(), 0);
216  }
217  for (uint32_t i = 0; i < 7; i++) {
218  vr.registerVote(nextNodeId(), 1);
219  }
220  BOOST_CHECK_EQUAL(vr.hasFinalized(), false);
221  BOOST_CHECK_EQUAL(vr.isStale(), false);
222 
223  // Remainder of votes are neutral
224  for (uint32_t i = 0;
226  i++) {
227  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 1);
228  }
229 
230  // Vote record becomes stale after too many rounds of voting
231  REGISTER_VOTE_AND_CHECK(vr, -1, false, false, true, 1);
232 }
233 
234 // Test all cases where confidence flips as much as possible, ending at all
235 // possible confidence levels.
236 BOOST_AUTO_TEST_CASE(stale_vote_with_confidence_flips) {
237  // Start testing with yes or no votes
238  for (uint32_t voteInit = 0; voteInit <= 1; voteInit++) {
239  // Test stalling at all confidence levels
240  for (auto offset = 0; offset < AVALANCHE_FINALIZATION_SCORE; offset++) {
241  uint32_t vote = voteInit;
242  VoteRecord vr(!vote);
243  uint32_t count = 0;
244 
245  // Offset with neutral votes
246  for (auto i = 0; i < offset; i++) {
247  REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false, 0);
248  count++;
249  }
250 
251  // Prepare to increase confidence with some votes
252  for (auto i = 0; i < 5; i++) {
253  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 0);
254  count++;
255  }
256 
257  while (true) {
258  // Increase confidence as fast as possible
259  for (uint32_t i = 0; i < AVALANCHE_FINALIZATION_SCORE - 1;
260  i++) {
264  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, true,
265  i);
266  goto finalsanitycheck;
267  }
271  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, true,
272  i);
273  goto finalsanitycheck;
274  }
275 
276  REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, i);
277  count++;
278  }
279 
280  // Flip the vote
281  if (vote++ >= 1) {
282  vote = 0;
283  }
284 
285  // Reset confidence
286  for (auto i = 0; i < 6; i++) {
287  if (count >= (AVALANCHE_FINALIZATION_SCORE - 1) *
289  REGISTER_VOTE_AND_CHECK(vr, vote, vote, false, true,
291  goto finalsanitycheck;
292  }
293 
294  REGISTER_VOTE_AND_CHECK(vr, vote, vote, false, false,
296  count++;
297  }
298 
299  // If this fails, we are probably infinite looping for some
300  // reason
303  }
304 
305  finalsanitycheck:
306  BOOST_CHECK(vr.isStale());
307  }
308  }
309 }
310 
311 BOOST_AUTO_TEST_CASE(duplicate_votes) {
312  VoteRecord vr(true);
313 
314  // Register some votes, expecting confidence to increase
315  for (auto i = 0; i < 7; i++) {
317  BOOST_CHECK(!vr.registerVote(nextNodeId(), 0));
318  }
320 
321  // Multiple duplicate votes do not advance confidence
322  for (auto i = 0; i < 8; i++) {
323  BOOST_CHECK(!vr.registerVote(currentNodeId, 0));
325  }
326 
327  // Register more votes with duplicates mixed in. Confidence should only
328  // increase when duplicates are not used.
329  auto expectedConfidence = 1;
330  for (auto i = 0; i < 8; i++) {
331  BOOST_CHECK(!vr.registerVote(currentNodeId, 0));
332  BOOST_CHECK_EQUAL(vr.getConfidence(), expectedConfidence);
333  for (auto j = i; j < 8; j++) {
334  BOOST_CHECK(!vr.registerVote(nextNodeId(), 0));
335  BOOST_CHECK_EQUAL(vr.getConfidence(), ++expectedConfidence);
336  }
337  }
338 
339  // Register enough votes to get just before finalization
340  for (auto i = 0; i < 90; i++) {
341  BOOST_CHECK(!vr.registerVote(nextNodeId(), 0));
342  BOOST_CHECK_EQUAL(vr.getConfidence(), ++expectedConfidence);
343  }
344 
345  // Sanity check that finalization occurs on the expected vote
346  BOOST_CHECK(vr.registerVote(nextNodeId(), 0));
348 }
349 
int64_t NodeId
Definition: nodeid.h:10
#define BOOST_AUTO_TEST_SUITE_END()
Definition: object.cpp:16
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
#define BOOST_CHECK(expr)
Definition: object.cpp:17
Vote history.
Definition: voterecord.h:47
uint16_t getConfidence() const
Definition: voterecord.h:86
void clearInflightRequest(uint8_t count=1)
Clear count inflight requests.
Definition: voterecord.h:118
bool hasFinalized() const
Definition: voterecord.h:87
bool shouldPoll() const
Return if this item is in condition to be polled at the moment.
Definition: voterecord.h:113
bool registerVote(NodeId nodeid, uint32_t error)
Register a new vote for an item and update confidence accordingly.
Definition: voterecord.cpp:13
bool isStale(uint32_t staleThreshold=AVALANCHE_VOTE_STALE_THRESHOLD, uint32_t staleFactor=AVALANCHE_VOTE_STALE_FACTOR) const
Definition: voterecord.h:91
bool registerPoll() const
Register that a request is being made regarding that item.
Definition: voterecord.cpp:87
bool isAccepted() const
Vote accounting facilities.
Definition: voterecord.h:84
static int count
Definition: tests.c:31
static constexpr uint32_t AVALANCHE_VOTE_STALE_FACTOR
Scaling factor applied to confidence to determine staleness threshold.
Definition: voterecord.h:35
static constexpr int AVALANCHE_MAX_INFLIGHT_POLL
How many inflight requests can exist for one item.
Definition: voterecord.h:40
static constexpr uint32_t AVALANCHE_VOTE_STALE_THRESHOLD
Number of votes before a record may be considered as stale.
Definition: voterecord.h:22
static constexpr int AVALANCHE_FINALIZATION_SCORE
Finalization score.
Definition: voterecord.h:17
#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, stale, confidence)
BOOST_AUTO_TEST_CASE(vote_record)