diff --git a/src/avalanche.h b/src/avalanche.h --- a/src/avalanche.h +++ b/src/avalanche.h @@ -49,14 +49,16 @@ struct VoteRecord { private: // Historical record of votes. - uint16_t votes; + uint8_t votes; + // Each bit indicate if the vote is to be considered. + uint8_t consider; // confidence's LSB bit is the result. Higher bits are actual confidence // score. uint16_t confidence; public: - VoteRecord(bool accepted) : votes(0xaaaa), confidence(accepted) {} + VoteRecord(bool accepted) : votes(0), consider(0), confidence(accepted) {} bool isAccepted() const { return confidence & 0x01; } @@ -69,7 +71,7 @@ * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed. */ - bool registerVote(bool vote); + bool registerVote(uint32_t error); }; class AvalancheVote { @@ -82,7 +84,7 @@ : error(errorIn), hash(hashIn) {} const uint256 &GetHash() const { return hash; } - bool IsValid() const { return error == 0; } + uint32_t GetError() const { return error; } // serialization support ADD_SERIALIZE_METHODS; @@ -268,6 +270,7 @@ bool addBlockToReconcile(const CBlockIndex *pindex); bool isAccepted(const CBlockIndex *pindex) const; + int getConfidence(const CBlockIndex *pindex) const; bool registerVotes(NodeId nodeid, const AvalancheResponse &response, std::vector &updates); diff --git a/src/avalanche.cpp b/src/avalanche.cpp --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -31,26 +31,42 @@ #endif } -bool VoteRecord::registerVote(bool vote) { - votes = (votes << 1) | vote; - - auto bits = countBits(votes & 0xff); - bool yes = bits > 6; - bool no = bits < 2; - if (!yes && !no) { - // The vote is inconclusive. - return false; +bool VoteRecord::registerVote(uint32_t error) { + /** + * The result of the vote is determined from the erro 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 signficant 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 do 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) { - // If the vote is in agreement with our internal status, increase - // confidence. confidence += 2; return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } - // The vote did not agree with our internal state, in that case, reset - // confidence. + // The round changed our state. We reset the confidence. confidence = yes; return true; } @@ -109,6 +125,14 @@ return false; } +int AvalancheProcessor::getConfidence(const CBlockIndex *pindex) const { + if (auto vr = GetRecord(vote_records, pindex)) { + return vr->getConfidence(); + } + + return -1; +} + bool AvalancheProcessor::registerVotes( NodeId nodeid, const AvalancheResponse &response, std::vector &updates) { @@ -195,7 +219,7 @@ } auto &vr = it->second; - if (!vr.registerVote(v.IsValid())) { + if (!vr.registerVote(v.GetError())) { // This vote did not provide any extra information, move on. continue; } diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp --- a/src/test/avalanche_tests.cpp +++ b/src/test/avalanche_tests.cpp @@ -47,46 +47,66 @@ BOOST_CHECK_EQUAL(vr.hasFinalized(), false); BOOST_CHECK_EQUAL(vr.getConfidence(), 0); - // We register one vote for, which keep things at 4/4. - REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); - - // One more and we are at 5/3. - REGISTER_VOTE_AND_CHECK(vr, true, false, false, 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); + } - // One more and we are at 5/3. - REGISTER_VOTE_AND_CHECK(vr, true, 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); - // One more and we are at 6/2. - REGISTER_VOTE_AND_CHECK(vr, true, false, 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); + } - // One more and we are at 6/2. - REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); + // 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); + } - // Next vote will flip state, and confidence will increase as long as we - // vote yes. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - REGISTER_VOTE_AND_CHECK(vr, true, true, false, i); + // 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, false, true, true, - AVALANCHE_FINALIZATION_SCORE); + 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, false, true, true, + 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. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - REGISTER_VOTE_AND_CHECK(vr, false, false, false, i); + 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, true, false, true, - AVALANCHE_FINALIZATION_SCORE); + REGISTER_VOTE_AND_CHECK(vr, 0, false, true, AVALANCHE_FINALIZATION_SCORE); } BOOST_AUTO_TEST_CASE(block_update) { @@ -169,18 +189,59 @@ // Let's vote for this block a few times. AvalancheResponse resp{0, 0, {AvalancheVote(0, blockHash)}}; - for (int i = 0; i < 4; i++) { + for (int i = 0; i < 6; i++) { AvalancheTest::runEventLoop(p); BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), 0); + BOOST_CHECK_EQUAL(updates.size(), 0); + } + + // A single neutral vote do not change anything. + resp = {AvalancheTest::getRound(p), 0, {AvalancheVote(-1, blockHash)}}; + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), 0); + BOOST_CHECK_EQUAL(updates.size(), 0); + + resp = {AvalancheTest::getRound(p), 0, {AvalancheVote(0, blockHash)}}; + for (int i = 1; i < 7; i++) { + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), i); + BOOST_CHECK_EQUAL(updates.size(), 0); + } + + // Two neutral votes will stall progress. + resp = {AvalancheTest::getRound(p), 0, {AvalancheVote(-1, blockHash)}}; + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), 6); + BOOST_CHECK_EQUAL(updates.size(), 0); + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), 6); + BOOST_CHECK_EQUAL(updates.size(), 0); + + resp = {AvalancheTest::getRound(p), 0, {AvalancheVote(0, blockHash)}}; + for (int i = 2; i < 8; i++) { + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), 6); BOOST_CHECK_EQUAL(updates.size(), 0); } // We vote for it numerous times to finalize it. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { + for (int i = 7; i < AVALANCHE_FINALIZATION_SCORE; i++) { AvalancheTest::runEventLoop(p); BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), i); BOOST_CHECK_EQUAL(updates.size(), 0); } @@ -211,7 +272,7 @@ BOOST_CHECK(invs[0].hash == blockHash); resp = {AvalancheTest::getRound(p), 0, {AvalancheVote(1, blockHash)}}; - for (int i = 0; i < 4; i++) { + for (int i = 0; i < 6; i++) { AvalancheTest::runEventLoop(p); BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates)); BOOST_CHECK(p.isAccepted(pindex)); @@ -320,7 +381,7 @@ BOOST_CHECK(invs[1].hash == blockHashA); // Let's vote for these blocks a few times. - for (int i = 0; i < 3; i++) { + for (int i = 0; i < 4; i++) { NodeId nodeid = AvalancheTest::getSuitableNodeToQuery(p); AvalancheTest::runEventLoop(p); BOOST_CHECK(p.registerVotes(nodeid, next(resp), updates));