diff --git a/src/avalanche/test/voterecord_tests.cpp b/src/avalanche/test/voterecord_tests.cpp --- a/src/avalanche/test/voterecord_tests.cpp +++ b/src/avalanche/test/voterecord_tests.cpp @@ -20,10 +20,11 @@ BOOST_FIXTURE_TEST_SUITE(voterecord_tests, TestingSetup) -#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ +#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, stale, confidence) \ vr.registerVote(nextNodeId(nodeid), vote); \ BOOST_CHECK_EQUAL(vr.isAccepted(), state); \ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \ + BOOST_CHECK_EQUAL(vr.isStale(), stale); \ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence); BOOST_AUTO_TEST_CASE(vote_record) { @@ -33,6 +34,7 @@ // Check initial state. BOOST_CHECK_EQUAL(vraccepted.isAccepted(), true); BOOST_CHECK_EQUAL(vraccepted.hasFinalized(), false); + BOOST_CHECK_EQUAL(vraccepted.isStale(), false); BOOST_CHECK_EQUAL(vraccepted.getConfidence(), 0); VoteRecord vr(false); @@ -40,68 +42,71 @@ // Check initial state. BOOST_CHECK_EQUAL(vr.isAccepted(), false); BOOST_CHECK_EQUAL(vr.hasFinalized(), false); + BOOST_CHECK_EQUAL(vr.isStale(), 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); + REGISTER_VOTE_AND_CHECK(vr, 0, false, 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); + REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, 0); // A single neutral vote do not change anything. - REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 1); + REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 1); for (int i = 2; i < 8; i++) { - REGISTER_VOTE_AND_CHECK(vr, 0, true, false, i); + REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 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); + REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7); + REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7); for (int i = 2; i < 8; i++) { - REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 7); + REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 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); + REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, i); } // The next vote will finalize the decision. - REGISTER_VOTE_AND_CHECK(vr, 1, true, true, AVALANCHE_FINALIZATION_SCORE); + REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false, + 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, + REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false, 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); + REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 0); // A single neutral vote do not change anything. - REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 1); + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 1); for (int i = 2; i < 8; i++) { - REGISTER_VOTE_AND_CHECK(vr, 1, false, false, i); + REGISTER_VOTE_AND_CHECK(vr, 1, false, 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); + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7); + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7); for (int i = 2; i < 8; i++) { - REGISTER_VOTE_AND_CHECK(vr, 1, false, false, 7); + REGISTER_VOTE_AND_CHECK(vr, 1, false, 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); + REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, i); } // The next vote will finalize the decision. - REGISTER_VOTE_AND_CHECK(vr, 0, false, true, AVALANCHE_FINALIZATION_SCORE); + REGISTER_VOTE_AND_CHECK(vr, 0, false, true, false, + AVALANCHE_FINALIZATION_SCORE); // Check that inflight accounting work as expected. VoteRecord vrinflight(false); @@ -127,6 +132,185 @@ } } +// Test some cases where confidence never advances +BOOST_AUTO_TEST_CASE(stale_vote_always_inconclusive) { + NodeId nodeid = -1; + // Setup a record that is inconclusive so far + VoteRecord vr(false); + + for (uint32_t i = 0; i < AVALANCHE_VOTE_STALE_THRESHOLD / 8; i++) { + // Vote randomly, but such that there's always enough neutral votes to + // not gain confidence. + for (auto j = 0; j < 6; j++) { + REGISTER_VOTE_AND_CHECK(vr, InsecureRand32(), false, false, false, + 0); + } + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0); + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0); + } + + // Vote record becomes stale after too many rounds of inconclusive voting + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, true, 0); +} + +// Test all cases where records reach a specific confidence level and then go +// stale. +BOOST_AUTO_TEST_CASE(stale_vote_at_all_confidence_levels) { + NodeId nodeid = -1; + + for (uint32_t vote = 0; vote <= 1; vote++) { + for (uint32_t confidence = 0; confidence < AVALANCHE_FINALIZATION_SCORE; + confidence++) { + VoteRecord vr(!vote); + + // Prepare to increase confidence with some votes + for (auto i = 0; i < 5; i++) { + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 0); + } + + // Increase to target confidence + for (uint32_t i = 0; i < confidence; i++) { + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, i); + } + + uint32_t remainingVotes = + AVALANCHE_VOTE_STALE_THRESHOLD - confidence - 5; + + // Special case where staying at confidence of 1 requires a + // different vote between agreeing votes + if (confidence == 1) { + REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false, 0); + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 1); + remainingVotes -= 2; + } + + // Vote neutral until stale + if (confidence > + AVALANCHE_VOTE_STALE_THRESHOLD / AVALANCHE_VOTE_STALE_FACTOR) { + remainingVotes = + confidence * AVALANCHE_VOTE_STALE_FACTOR - confidence - 5; + } + for (uint32_t i = 0; i < remainingVotes; i++) { + REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false, + confidence); + } + REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, true, confidence); + } + } +} + +// Test some cases where confidence may flip flop and then goes stale. +BOOST_AUTO_TEST_CASE(stale_vote_random_then_inconclusive) { + NodeId nodeid = -1; + VoteRecord vr(false); + + for (uint32_t i = 0; i < AVALANCHE_FINALIZATION_SCORE - 14; i++) { + // Vote randomly. Confidence changes are ok. + vr.registerVote(nextNodeId(nodeid), InsecureRand32()); + BOOST_CHECK_EQUAL(vr.hasFinalized(), false); + BOOST_CHECK_EQUAL(vr.isStale(), false); + } + + // Reset confidence, no matter what it is right now + for (uint32_t i = 0; i < 7; i++) { + vr.registerVote(nextNodeId(nodeid), 0); + } + for (uint32_t i = 0; i < 7; i++) { + vr.registerVote(nextNodeId(nodeid), 1); + } + BOOST_CHECK_EQUAL(vr.hasFinalized(), false); + BOOST_CHECK_EQUAL(vr.isStale(), false); + + // Remainder of votes are neutral + for (uint32_t i = 0; + i < AVALANCHE_VOTE_STALE_THRESHOLD - AVALANCHE_FINALIZATION_SCORE; + i++) { + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 1); + } + + // Vote record becomes stale after too many rounds of voting + REGISTER_VOTE_AND_CHECK(vr, -1, false, false, true, 1); +} + +// Test all cases where confidence flips as much as possible, ending at all +// possible confidence levels. +BOOST_AUTO_TEST_CASE(stale_vote_with_confidence_flips) { + NodeId nodeid = -1; + + // Start testing with yes or no votes + for (uint32_t voteInit = 0; voteInit <= 1; voteInit++) { + // Test stalling at all confidence levels + for (auto offset = 0; offset < AVALANCHE_FINALIZATION_SCORE; offset++) { + uint32_t vote = voteInit; + VoteRecord vr(!vote); + uint32_t count = 0; + + // Offset with neutral votes + for (auto i = 0; i < offset; i++) { + REGISTER_VOTE_AND_CHECK(vr, -1, !vote, false, false, 0); + count++; + } + + // Prepare to increase confidence with some votes + for (auto i = 0; i < 5; i++) { + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, 0); + count++; + } + + while (true) { + // Increase confidence as fast as possible + for (uint32_t i = 0; i < AVALANCHE_FINALIZATION_SCORE - 1; + i++) { + if (i <= AVALANCHE_VOTE_STALE_THRESHOLD / + AVALANCHE_VOTE_STALE_FACTOR && + count >= AVALANCHE_VOTE_STALE_THRESHOLD) { + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, true, + i); + goto finalsanitycheck; + } + if (i > AVALANCHE_VOTE_STALE_THRESHOLD / + AVALANCHE_VOTE_STALE_FACTOR && + count >= i * AVALANCHE_VOTE_STALE_FACTOR) { + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, true, + i); + goto finalsanitycheck; + } + + REGISTER_VOTE_AND_CHECK(vr, vote, !vote, false, false, i); + count++; + } + + // Flip the vote + if (vote++ >= 1) { + vote = 0; + } + + // Reset confidence + for (auto i = 0; i < 6; i++) { + if (count >= (AVALANCHE_FINALIZATION_SCORE - 1) * + AVALANCHE_VOTE_STALE_FACTOR) { + REGISTER_VOTE_AND_CHECK(vr, vote, vote, false, true, + AVALANCHE_FINALIZATION_SCORE); + goto finalsanitycheck; + } + + REGISTER_VOTE_AND_CHECK(vr, vote, vote, false, false, + AVALANCHE_FINALIZATION_SCORE - 1); + count++; + } + + // If this fails, we are probably infinite looping for some + // reason + BOOST_CHECK(count <= AVALANCHE_FINALIZATION_SCORE * + AVALANCHE_VOTE_STALE_FACTOR); + } + + finalsanitycheck: + BOOST_CHECK(vr.isStale()); + } + } +} + BOOST_AUTO_TEST_CASE(duplicate_votes) { VoteRecord vr(true); NodeId nodeid = -1; diff --git a/src/avalanche/voterecord.h b/src/avalanche/voterecord.h --- a/src/avalanche/voterecord.h +++ b/src/avalanche/voterecord.h @@ -16,6 +16,18 @@ */ static constexpr int AVALANCHE_FINALIZATION_SCORE = 128; +/** + * Number of votes before a record may be considered as stale. + */ +static constexpr uint32_t AVALANCHE_VOTE_STALE_THRESHOLD = 4096; + +/** + * Scaling factor applied to confidence to determine staleness threshold. + * As confidence increases, the staleness threshold should as well. This + * ensures that slowly increasing confidence is not marked stale. + */ +static constexpr uint32_t AVALANCHE_VOTE_STALE_FACTOR = 64; + /** * How many inflight requests can exist for one item. */ @@ -70,6 +82,11 @@ return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } + bool isStale() const { + return successfulVotes > AVALANCHE_VOTE_STALE_THRESHOLD && + successfulVotes > getConfidence() * AVALANCHE_VOTE_STALE_FACTOR; + } + /** * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed.