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,12 @@ auto &vr = it->second; if (!vr.registerVote(nodeid, v.GetError())) { + if (vr.isStale()) { + // Just drop stale votes. If we see this item again, we'll + // do a new vote. + updates.emplace_back(item, VoteStatus::Stale); + voteRecordsWriteView->erase(it); + } // This vote did not provide any extra information, move on. continue; } @@ -588,9 +594,8 @@ return true; } - const bool shouldPoll = - forPoll ? voteRecord.registerPoll() : voteRecord.shouldPoll(); - + const bool shouldPoll = voteRecord.shouldPoll() && + (!forPoll || voteRecord.registerPoll()); if (!shouldPoll) { 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,36 @@ 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++) { + BOOST_CHECK(vrstale.shouldPoll()); + for (int p = 0; p < 8; p++) { + BOOST_CHECK(vrstale.registerPoll()); + } + + // 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 + BOOST_CHECK(vrstale.shouldPoll()); + BOOST_CHECK(vrstale.registerPoll()); + REGISTER_VOTE_AND_CHECK(vrstale, -1, false, false, true, 0); + BOOST_CHECK(!vrstale.shouldPoll()); } BOOST_AUTO_TEST_CASE(block_update) { @@ -425,10 +460,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) { @@ -703,6 +736,60 @@ BOOST_CHECK_EQUAL(invs.size(), 0); } +BOOST_AUTO_TEST_CASE_TEMPLATE(vote_item_register_stale, P, VoteItemProviders) { + P provider(this); + auto &updates = provider.updates; + const uint32_t invType = provider.invType; + + const auto item = provider.buildVoteItem(); + const auto itemid = provider.getVoteItemId(item); + + // Create nodes that supports avalanche. + auto avanodes = ConnectNodes(); + + // Add a new item. + BOOST_CHECK(provider.addToReconcile(item)); + auto invs = getInvsForNextPoll(); + BOOST_CHECK_EQUAL(invs.size(), 1); + BOOST_CHECK_EQUAL(invs[0].type, invType); + BOOST_CHECK(invs[0].hash == itemid); + + int nextNodeIndex = 0; + auto registerNewVote = [&](const Response &resp) { + runEventLoop(); + auto nodeid = avanodes[nextNodeIndex++ % avanodes.size()]->GetId(); + BOOST_CHECK(provider.registerVotes(nodeid, resp)); + }; + + // Let's vote for this item a few times. + Response resp{0, 0, {Vote(-1, itemid)}}; + for (uint32_t i = 0; i < AVALANCHE_VOTE_STALE_THRESHOLD; i++) { + registerNewVote(next(resp)); + BOOST_CHECK_EQUAL(m_processor->getConfidence(item), 0); + BOOST_CHECK_EQUAL(updates.size(), 0); + + // As long as it is not stale, we poll. + invs = getInvsForNextPoll(); + BOOST_CHECK_EQUAL(invs.size(), 1); + BOOST_CHECK_EQUAL(invs[0].type, invType); + BOOST_CHECK(invs[0].hash == itemid); + } + + // Next neutral vote makes the record stale. + resp = {getRound(), 0, {Vote(-1, itemid)}}; + registerNewVote(next(resp)); + BOOST_CHECK(!m_processor->isAccepted(item)); + BOOST_CHECK_EQUAL(m_processor->getConfidence(item), -1); + + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getVoteItem() == item); + BOOST_CHECK(updates[0].getStatus() == VoteStatus::Stale); + + // Once the record is stale, there is no poll for it. + invs = getInvsForNextPoll(); + BOOST_CHECK_EQUAL(invs.size(), 0); +} + BOOST_AUTO_TEST_CASE_TEMPLATE(poll_and_response, P, VoteItemProviders) { P provider(this); auto &updates = provider.updates; 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. @@ -86,7 +95,9 @@ /** * Return if this item is in condition to be polled at the moment. */ - bool shouldPoll() const { return inflight < AVALANCHE_MAX_INFLIGHT_POLL; } + bool shouldPoll() const { + return inflight < AVALANCHE_MAX_INFLIGHT_POLL && !isStale(); + } /** * Clear `count` inflight requests. 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,11 @@ proofid.GetHex()); } break; + case avalanche::VoteStatus::Stale: + // This proof is likely conflicting and unknown to most + // peers. + // TODO: Do something with this proof. + break; } } @@ -5271,6 +5279,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; } }