diff --git a/src/avalanche.h b/src/avalanche.h --- a/src/avalanche.h +++ b/src/avalanche.h @@ -61,13 +61,17 @@ public: VoteRecord() : votes(0xaaaa), confidence(0) {} - bool isValid() const { return confidence & 0x01; } + bool isAccepted() const { return confidence & 0x01; } uint16_t getConfidence() const { return confidence >> 1; } bool hasFinalized() const { return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } + /** + * Register a new vote for an item and update confidence accordingly. + * Returns true if the acceptance or finalization state changed. + */ bool registerVote(bool vote) { votes = (votes << 1) | vote; @@ -79,16 +83,16 @@ return false; } - if (isValid() == yes) { + if (isAccepted() == yes) { // If the vote is in agreement with our internal status, increase // confidence. confidence += 2; - } else { - // The vote did not agree with our internal state, in that case, - // reset confidence. - confidence = yes; + return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } + // The vote did not agree with our internal state, in that case, reset + // confidence. + confidence = yes; return true; } }; @@ -135,6 +139,36 @@ } }; +class AvalancheBlockUpdate { + union { + CBlockIndex *pindex; + size_t raw; + }; + +public: + enum Status : uint8_t { + Invalid, + Rejected, + Accepted, + Finalized, + }; + + AvalancheBlockUpdate(CBlockIndex *pindexIn, Status statusIn) + : pindex(pindexIn) { + raw |= statusIn; + } + + Status getStatus() const { return Status(raw & 0x03); } + + CBlockIndex *getBlockIndex() { + return reinterpret_cast(raw & -size_t(0x04)); + } + + const CBlockIndex *getBlockIndex() const { + return const_cast(this)->getBlockIndex(); + } +}; + typedef std::map BlockVoteMap; @@ -160,9 +194,9 @@ bool addBlockToReconcile(const CBlockIndex *pindex); bool isAccepted(const CBlockIndex *pindex) const; - bool hasFinalized(const CBlockIndex *pindex) const; - bool registerVotes(const AvalancheResponse &response); + bool registerVotes(const AvalancheResponse &response, + std::vector &updates); bool startEventLoop(CScheduler &scheduler); bool stopEventLoop(); diff --git a/src/avalanche.cpp b/src/avalanche.cpp --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -31,24 +31,18 @@ bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const { if (auto vr = GetRecord(vote_records, pindex)) { - return vr->isValid(); + return vr->isAccepted(); } return false; } -bool AvalancheProcessor::hasFinalized(const CBlockIndex *pindex) const { - if (auto vr = GetRecord(vote_records, pindex)) { - return vr->hasFinalized(); - } - - return false; -} - -bool AvalancheProcessor::registerVotes(const AvalancheResponse &response) { +bool AvalancheProcessor::registerVotes( + const AvalancheResponse &response, + std::vector &updates) { const std::vector &votes = response.GetVotes(); - std::map responseIndex; + std::map responseIndex; { LOCK(cs_main); @@ -67,7 +61,7 @@ // Register votes. auto w = vote_records.getWriteView(); for (auto &p : responseIndex) { - const CBlockIndex *pindex = p.first; + CBlockIndex *pindex = p.first; const AvalancheVote &v = p.second; auto it = w->find(pindex); @@ -76,7 +70,29 @@ continue; } - it->second.registerVote(v.IsValid()); + auto &vr = it->second; + if (!vr.registerVote(v.IsValid())) { + // This vote did not provide any extra information, move on. + continue; + } + + if (!vr.hasFinalized()) { + // This item has note been finalized, so we have nothing more to + // do. + updates.emplace_back( + pindex, + vr.isAccepted() ? AvalancheBlockUpdate::Status::Accepted + : AvalancheBlockUpdate::Status::Rejected); + continue; + } + + // We just finalized a vote. If it is valid, then let the caller + // know. Either way, remove the item from the map. + updates.emplace_back(pindex, + vr.isAccepted() + ? AvalancheBlockUpdate::Status::Finalized + : AvalancheBlockUpdate::Status::Invalid); + w->erase(it); } } 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 @@ -18,7 +18,7 @@ #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ vr.registerVote(vote); \ - BOOST_CHECK_EQUAL(vr.isValid(), state); \ + BOOST_CHECK_EQUAL(vr.isAccepted(), state); \ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence); @@ -26,7 +26,7 @@ VoteRecord vr; // Check initial state. - BOOST_CHECK_EQUAL(vr.isValid(), false); + BOOST_CHECK_EQUAL(vr.isAccepted(), false); BOOST_CHECK_EQUAL(vr.hasFinalized(), false); BOOST_CHECK_EQUAL(vr.getConfidence(), 0); @@ -72,8 +72,27 @@ AVALANCHE_FINALIZATION_SCORE); } +BOOST_AUTO_TEST_CASE(block_update) { + CBlockIndex index; + CBlockIndex *pindex = &index; + + std::set status{ + AvalancheBlockUpdate::Status::Invalid, + AvalancheBlockUpdate::Status::Rejected, + AvalancheBlockUpdate::Status::Accepted, + AvalancheBlockUpdate::Status::Finalized, + }; + + for (auto s : status) { + AvalancheBlockUpdate abu(pindex, s); + BOOST_CHECK(abu.getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(abu.getStatus(), s); + } +} + BOOST_AUTO_TEST_CASE(block_register) { AvalancheProcessor p; + std::vector updates; CBlock block = CreateAndProcessBlock({}, CScript()); const uint256 blockHash = block.GetHash(); @@ -81,7 +100,6 @@ // Querying for random block returns false. BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); // Add a new block. Check it is added to the polls. BOOST_CHECK(p.addBlockToReconcile(pindex)); @@ -92,21 +110,29 @@ // Newly added blocks are also considered rejected. BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); // Let's vote for this block a few times. AvalancheResponse resp{0, {AvalancheVote(0, blockHash)}}; for (int i = 0; i < 5; i++) { - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } + // Now the state will flip. + p.registerVotes(resp, updates); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + // Now it is accepted, but we can vote for it numerous times. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - p.registerVotes(resp); + for (int i = 1; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp, updates); BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // As long as it is not finalized, we poll. @@ -116,27 +142,37 @@ BOOST_CHECK(invs[0].hash == blockHash); // Now finalize the decision. - resp = {0, {AvalancheVote(1, blockHash)}}; - p.registerVotes(resp); - BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // Once the decision is finalized, there is no poll for it. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 0); // Now let's undo this and finalize rejection. - for (int i = 0; i < 5; i++) { - p.registerVotes(resp); - BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + BOOST_CHECK(p.addBlockToReconcile(pindex)); + invs = AvalancheTest::getInvsForNextPoll(p); + BOOST_CHECK_EQUAL(invs.size(), 1); + BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); + BOOST_CHECK(invs[0].hash == blockHash); + + // Only 3 here as we don't need to flip state. + resp = {0, {AvalancheVote(1, blockHash)}}; + for (int i = 0; i < 3; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK(!p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // Now it is rejected, but we can vote for it numerous times. for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // As long as it is not finalized, we poll. @@ -146,24 +182,30 @@ BOOST_CHECK(invs[0].hash == blockHash); // Now finalize the decision. - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Invalid); + updates = {}; // Once the decision is finalized, there is no poll for it. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 0); // Adding the block twice does nothing. + BOOST_CHECK(p.addBlockToReconcile(pindex)); BOOST_CHECK(!p.addBlockToReconcile(pindex)); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); } BOOST_AUTO_TEST_CASE(multi_block_register) { AvalancheProcessor p; CBlockIndex indexA, indexB; + std::vector updates; + // Make sure the block has a hash. CBlock blockA = CreateAndProcessBlock({}, CScript()); const uint256 blockHashA = blockA.GetHash(); @@ -186,7 +228,8 @@ AvalancheResponse resp{ 0, {AvalancheVote(0, blockHashA), AvalancheVote(0, blockHashB)}}; - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); // Start voing on block B after one vote. BOOST_CHECK(p.addBlockToReconcile(pindexB)); @@ -199,13 +242,41 @@ BOOST_CHECK_EQUAL(invs[1].type, MSG_BLOCK); BOOST_CHECK(invs[1].hash == blockHashA); + // Let's vote for this block a few times. + for (int i = 0; i < 4; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); + } + + // Now the state will flip for A. + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexA); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + + // And then for B. + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexB); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + // Now it is rejected, but we can vote for it numerous times. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE + 4; i++) { - p.registerVotes(resp); + for (int i = 2; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); } // Next vote will finalize block A. - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexA); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // We do not vote on A anymore. invs = AvalancheTest::getInvsForNextPoll(p); @@ -214,7 +285,12 @@ BOOST_CHECK(invs[0].hash == blockHashB); // Next vote will finalize block B. - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexB); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // There is nothing left to vote on. invs = AvalancheTest::getInvsForNextPoll(p);