diff --git a/src/avalanche/test/voterecord_tests.cpp b/src/avalanche/test/voterecord_tests.cpp index 861324cb3..96b035460 100644 --- a/src/avalanche/test/voterecord_tests.cpp +++ b/src/avalanche/test/voterecord_tests.cpp @@ -1,171 +1,170 @@ // Copyright (c) 2018-2022 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include using namespace avalanche; +NodeId nextNodeId(NodeId &nodeid) { + nodeid++; + if (nodeid >= 8) { + nodeid = 0; + } + return nodeid; +} + BOOST_FIXTURE_TEST_SUITE(voterecord_tests, TestingSetup) #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ - vr.registerVote(NO_NODE, vote); \ + vr.registerVote(nextNodeId(nodeid), vote); \ BOOST_CHECK_EQUAL(vr.isAccepted(), state); \ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence); BOOST_AUTO_TEST_CASE(vote_record) { + NodeId nodeid = -1; VoteRecord vraccepted(true); // Check initial state. BOOST_CHECK_EQUAL(vraccepted.isAccepted(), true); BOOST_CHECK_EQUAL(vraccepted.hasFinalized(), false); BOOST_CHECK_EQUAL(vraccepted.getConfidence(), 0); VoteRecord vr(false); // Check initial state. BOOST_CHECK_EQUAL(vr.isAccepted(), false); BOOST_CHECK_EQUAL(vr.hasFinalized(), false); BOOST_CHECK_EQUAL(vr.getConfidence(), 0); // We need to register 6 positive votes before we start counting. for (int i = 0; i < 6; i++) { REGISTER_VOTE_AND_CHECK(vr, 0, false, false, 0); } // Next vote will flip state, and confidence will increase as long as we // vote yes. REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 0); // A single neutral vote do not change anything. REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 1); for (int i = 2; i < 8; i++) { REGISTER_VOTE_AND_CHECK(vr, 0, true, false, i); } // Two neutral votes will stall progress. REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 7); REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 7); for (int i = 2; i < 8; i++) { REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 7); } // Now confidence will increase as long as we vote yes. for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) { REGISTER_VOTE_AND_CHECK(vr, 0, true, false, i); } // The next vote will finalize the decision. REGISTER_VOTE_AND_CHECK(vr, 1, true, true, AVALANCHE_FINALIZATION_SCORE); // Now that we have two no votes, confidence stop increasing. for (int i = 0; i < 5; i++) { REGISTER_VOTE_AND_CHECK(vr, 1, true, true, AVALANCHE_FINALIZATION_SCORE); } // Next vote will flip state, and confidence will increase as long as we // vote no. REGISTER_VOTE_AND_CHECK(vr, 1, false, false, 0); // A single neutral vote do not change anything. REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 1); for (int i = 2; i < 8; i++) { REGISTER_VOTE_AND_CHECK(vr, 1, false, false, i); } // Two neutral votes will stall progress. REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 7); REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 7); for (int i = 2; i < 8; i++) { REGISTER_VOTE_AND_CHECK(vr, 1, false, false, 7); } // Now confidence will increase as long as we vote no. for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) { REGISTER_VOTE_AND_CHECK(vr, 1, false, false, i); } // The next vote will finalize the decision. REGISTER_VOTE_AND_CHECK(vr, 0, false, true, AVALANCHE_FINALIZATION_SCORE); // Check that inflight accounting work as expected. VoteRecord vrinflight(false); for (int i = 0; i < 2 * AVALANCHE_MAX_INFLIGHT_POLL; i++) { bool shouldPoll = vrinflight.shouldPoll(); BOOST_CHECK_EQUAL(shouldPoll, i < AVALANCHE_MAX_INFLIGHT_POLL); BOOST_CHECK_EQUAL(vrinflight.registerPoll(), shouldPoll); } // Clear various number of inflight requests and check everything behaves as // expected. for (int i = 1; i < AVALANCHE_MAX_INFLIGHT_POLL; i++) { vrinflight.clearInflightRequest(i); BOOST_CHECK(vrinflight.shouldPoll()); for (int j = 1; j < i; j++) { BOOST_CHECK(vrinflight.registerPoll()); BOOST_CHECK(vrinflight.shouldPoll()); } BOOST_CHECK(vrinflight.registerPoll()); BOOST_CHECK(!vrinflight.shouldPoll()); } } -namespace { -NodeId nextNodeId(NodeId &nodeid) { - nodeid++; - if (nodeid >= 8) { - nodeid = 0; - } - return nodeid; -} -} // namespace - BOOST_AUTO_TEST_CASE(duplicate_votes) { VoteRecord vr(true); NodeId nodeid = -1; // Register some votes, expecting confidence to increase for (auto i = 0; i < 7; i++) { BOOST_CHECK_EQUAL(vr.getConfidence(), 0); BOOST_CHECK(!vr.registerVote(nextNodeId(nodeid), 0)); } BOOST_CHECK_EQUAL(vr.getConfidence(), 1); // Multiple duplicate votes do not advance confidence for (auto i = 0; i < 8; i++) { BOOST_CHECK(!vr.registerVote(nodeid, 0)); BOOST_CHECK_EQUAL(vr.getConfidence(), 1); } // Register more votes with duplicates mixed in. Confidence should only // increase when duplicates are not used. auto expectedConfidence = 1; for (auto i = 0; i < 8; i++) { BOOST_CHECK(!vr.registerVote(nodeid, 0)); BOOST_CHECK_EQUAL(vr.getConfidence(), expectedConfidence); for (auto j = i; j < 8; j++) { BOOST_CHECK(!vr.registerVote(nextNodeId(nodeid), 0)); BOOST_CHECK_EQUAL(vr.getConfidence(), ++expectedConfidence); } } // Register enough votes to get just before finalization for (auto i = 0; i < 90; i++) { BOOST_CHECK(!vr.registerVote(nextNodeId(nodeid), 0)); BOOST_CHECK_EQUAL(vr.getConfidence(), ++expectedConfidence); } // Sanity check that finalization occurs on the expected vote BOOST_CHECK(vr.registerVote(nextNodeId(nodeid), 0)); BOOST_CHECK(vr.hasFinalized()); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/avalanche/voterecord.cpp b/src/avalanche/voterecord.cpp index 19ea30416..d1ff520df 100644 --- a/src/avalanche/voterecord.cpp +++ b/src/avalanche/voterecord.cpp @@ -1,103 +1,98 @@ // Copyright (c) 2021 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include namespace avalanche { bool VoteRecord::registerVote(NodeId nodeid, uint32_t error) { // We just got a new vote, so there is one less inflight request. clearInflightRequest(); // We want to avoid having the same node voting twice in a quorum. if (!addNodeToQuorum(nodeid)) { return false; } /** * The result of the vote is determined from the error code. If the error * code is 0, there is no error and therefore the vote is yes. If there is * an error, we check the most significant bit to decide if the vote is a no * (for instance, the block is invalid) or is the vote inconclusive (for * instance, the queried node does not have the block yet). */ votes = (votes << 1) | (error == 0); consider = (consider << 1) | (int32_t(error) >= 0); /** * We compute the number of yes and/or no votes as follow: * * votes: 1010 * consider: 1100 * * yes votes: 1000 using votes & consider * no votes: 0100 using ~votes & consider */ bool yes = countBits(votes & consider & 0xff) > 6; if (!yes) { bool no = countBits(~votes & consider & 0xff) > 6; if (!no) { // The round is inconclusive. return false; } } // If the round is in agreement with previous rounds, increase confidence. if (isAccepted() == yes) { confidence += 2; return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } // The round changed our state. We reset the confidence. confidence = yes; return true; } bool VoteRecord::addNodeToQuorum(NodeId nodeid) { - if (nodeid == NO_NODE) { - // Helpful for testing. - return true; - } - // MMIX Linear Congruent Generator. const uint64_t r1 = 6364136223846793005 * uint64_t(nodeid) + 1442695040888963407; // Fibonacci hashing. const uint64_t r2 = 11400714819323198485ull * (nodeid ^ seed); // Combine and extract hash. const uint16_t h = (r1 + r2) >> 48; /** * Check if the node is in the filter. */ for (size_t i = 1; i < nodeFilter.size(); i++) { if (nodeFilter[(successfulVotes + i) % nodeFilter.size()] == h) { return false; } } /** * Add the node which just voted to the filter. */ nodeFilter[successfulVotes % nodeFilter.size()] = h; successfulVotes++; return true; } bool VoteRecord::registerPoll() const { uint8_t count = inflight.load(); while (count < AVALANCHE_MAX_INFLIGHT_POLL) { if (inflight.compare_exchange_weak(count, count + 1)) { return true; } } return false; } } // namespace avalanche