diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h --- a/src/avalanche/processor.h +++ b/src/avalanche/processor.h @@ -60,6 +60,7 @@ Rejected, Accepted, Finalized, + Stale, }; template class VoteItemUpdate { diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp --- a/src/avalanche/processor.cpp +++ b/src/avalanche/processor.cpp @@ -494,6 +494,9 @@ auto &vr = it->second; if (!vr.registerVote(nodeid, v.GetError())) { + if (vr.isStale()) { + updates.emplace_back(item, VoteStatus::Stale); + } // This vote did not provide any extra information, move on. continue; } diff --git a/src/avalanche/test/processor_tests.cpp b/src/avalanche/test/processor_tests.cpp --- a/src/avalanche/test/processor_tests.cpp +++ b/src/avalanche/test/processor_tests.cpp @@ -314,10 +314,11 @@ // FIXME A std::tuple can be used instead of boost::mpl::list after boost 1.67 using VoteItemProviders = boost::mpl::list; -#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ +#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, stale, confidence) \ vr.registerVote(NO_NODE, 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) { @@ -326,6 +327,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); @@ -333,68 +335,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); @@ -418,6 +423,28 @@ BOOST_CHECK(vrinflight.registerPoll()); BOOST_CHECK(!vrinflight.shouldPoll()); } + + // Vote record becomes stale after too many rounds of inconclusive voting + VoteRecord vrstale(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. + REGISTER_VOTE_AND_CHECK(vrstale, InsecureRand32(), false, false, false, + 0); + REGISTER_VOTE_AND_CHECK(vrstale, InsecureRand32(), false, false, false, + 0); + REGISTER_VOTE_AND_CHECK(vrstale, InsecureRand32(), false, false, false, + 0); + REGISTER_VOTE_AND_CHECK(vrstale, InsecureRand32(), false, false, false, + 0); + REGISTER_VOTE_AND_CHECK(vrstale, InsecureRand32(), false, false, false, + 0); + REGISTER_VOTE_AND_CHECK(vrstale, -1, false, false, false, 0); + REGISTER_VOTE_AND_CHECK(vrstale, -1, false, false, false, 0); + REGISTER_VOTE_AND_CHECK(vrstale, -1, false, false, false, 0); + } + // After this vote, the record is flagged as stale + REGISTER_VOTE_AND_CHECK(vrstale, -1, false, false, true, 0); } BOOST_AUTO_TEST_CASE(block_update) { @@ -425,10 +452,8 @@ CBlockIndex *pindex = &index; std::set status{ - VoteStatus::Invalid, - VoteStatus::Rejected, - VoteStatus::Accepted, - VoteStatus::Finalized, + VoteStatus::Invalid, VoteStatus::Rejected, VoteStatus::Accepted, + VoteStatus::Finalized, VoteStatus::Stale, }; for (auto s : status) { 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,11 @@ */ static constexpr int AVALANCHE_FINALIZATION_SCORE = 128; +/** + * Number of votes before a record is flagged as stale. + */ +static constexpr uint32_t AVALANCHE_VOTE_STALE_THRESHOLD = 1024; + /** * How many inflight requests can exist for one item. */ @@ -70,6 +75,10 @@ return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } + bool isStale() const { + return successfulVotes > AVALANCHE_VOTE_STALE_THRESHOLD; + } + /** * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed. diff --git a/src/avalanche/voterecord.cpp b/src/avalanche/voterecord.cpp --- a/src/avalanche/voterecord.cpp +++ b/src/avalanche/voterecord.cpp @@ -59,32 +59,27 @@ } 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; + // Using NO_NODE is helpful for testing. + if (nodeid != NO_NODE) { + // 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; } - /** - * Add the node which just voted to the filter. - */ - nodeFilter[successfulVotes % nodeFilter.size()] = h; successfulVotes++; return true; } diff --git a/src/net_processing.cpp b/src/net_processing.cpp --- a/src/net_processing.cpp +++ b/src/net_processing.cpp @@ -5188,6 +5188,9 @@ case avalanche::VoteStatus::Finalized: voteOutcome = "finalized"; break; + case avalanche::VoteStatus::Stale: + voteOutcome = "marked as stale"; + break; // No default case, so the compiler can warn about missing // cases @@ -5246,6 +5249,12 @@ proofid.GetHex()); } break; + case avalanche::VoteStatus::Stale: + // This proof is likely conflicting and unknown to most + // peers. + // TODO: Initiate peer discovery requests so we can resolve + // the conflict with the best proof. + break; } } @@ -5271,6 +5280,14 @@ LOCK(cs_main); ::ChainstateActive().UnparkBlock(pindex); } break; + case avalanche::VoteStatus::Stale: + // For now, we shouldn't need to do anything in this + // situation, since we rely on aggressive block + // relaying. + LogPrintf("Warning: Unexpected avalanche marked block " + "%s as stale.\n", + pindex->GetBlockHash().ToString()); + break; } }