diff --git a/src/avalanche.h b/src/avalanche.h --- a/src/avalanche.h +++ b/src/avalanche.h @@ -66,9 +66,15 @@ // How many in flight requests exists for this element. mutable std::atomic inflight{0}; + // Seed for pseudorandom operations. + const uint32_t seed = 0; + // Track how many successful votes occured. uint32_t successfulVotes = 0; + // Track the nodes which are part of the quorum. + std::array nodeFilter{{0, 0, 0, 0, 0, 0, 0, 0}}; + public: VoteRecord(bool accepted) : confidence(accepted) {} @@ -78,7 +84,8 @@ VoteRecord(const VoteRecord &other) : confidence(other.confidence), votes(other.votes), consider(other.consider), inflight(other.inflight.load()), - successfulVotes(other.successfulVotes) {} + successfulVotes(other.successfulVotes), nodeFilter(other.nodeFilter) { + } /** * Vote accounting facilities. @@ -94,7 +101,7 @@ * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed. */ - bool registerVote(uint32_t error); + bool registerVote(NodeId nodeid, uint32_t error); /** * Register that a request is being made regarding that item. @@ -112,6 +119,14 @@ * Clear `count` inflight requests. */ void clearInflightRequest(uint8_t count = 1) { inflight -= count; } + +private: + /** + * Add the node to the quorum. + * Returns true if the node was added, false if the node already was in the + * quorum. + */ + bool addNodeToQuorum(NodeId nodeid); }; class AvalancheVote { diff --git a/src/avalanche.cpp b/src/avalanche.cpp --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -40,12 +40,14 @@ #endif } -bool VoteRecord::registerVote(uint32_t error) { +bool VoteRecord::registerVote(NodeId nodeid, uint32_t error) { // We just got a new vote, so there is one less inflight request. clearInflightRequest(); - // Keep track of how many votes were registered. - successfulVotes++; + // We want to avoid having the same node voting twice in a quorum. + if (!addNodeToQuorum(nodeid)) { + return false; + } /** * The result of the vote is determined from the error code. If the error @@ -86,6 +88,36 @@ return true; } +bool VoteRecord::addNodeToQuorum(NodeId nodeid) { + if (nodeid == NO_NODE) { + // Helpful for testing. + return true; + } + + // MMIX Linear Congruent Generator. + const uint64_t r1 = 6364136223846793005 * 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; + successfulVotes++; + return true; +} + bool VoteRecord::registerPoll() const { uint8_t count = inflight.load(); while (count < AVALANCHE_MAX_INFLIGHT_POLL) { @@ -237,7 +269,7 @@ } auto &vr = it->second; - if (!vr.registerVote(v.GetError())) { + if (!vr.registerVote(nodeid, 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 @@ -27,7 +27,7 @@ BOOST_FIXTURE_TEST_SUITE(avalanche_tests, TestChain100Setup) #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ - vr.registerVote(vote); \ + vr.registerVote(NO_NODE, vote); \ BOOST_CHECK_EQUAL(vr.isAccepted(), state); \ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence); @@ -204,7 +204,7 @@ const Config &config = GetConfig(); - // Create a node that supports avalanche. + // Create nodes that supports avalanche. auto avanodes = ConnectNodes(config, p, NODE_AVALANCHE, *peerLogic); // Querying for random block returns false. @@ -656,7 +656,7 @@ BOOST_CHECK(p.addBlockToReconcile(pindex)); // Ensure there are enough requests in flight. - std::map node_round_map; + std::map node_round_map; for (int i = 0; i < AVALANCHE_MAX_INFLIGHT_POLL; i++) { NodeId nodeid = AvalancheTest::getSuitableNodeToQuery(p); BOOST_CHECK(node_round_map.find(nodeid) == node_round_map.end()); @@ -692,6 +692,73 @@ CConnmanTest::ClearNodes(); } +BOOST_AUTO_TEST_CASE(quorum_diversity) { + AvalancheProcessor p(g_connman.get()); + std::vector updates; + + CBlock block = CreateAndProcessBlock({}, CScript()); + const uint256 blockHash = block.GetHash(); + const CBlockIndex *pindex = mapBlockIndex[blockHash]; + + const Config &config = GetConfig(); + + // Create nodes that supports avalanche. + auto avanodes = ConnectNodes(config, p, NODE_AVALANCHE, *peerLogic); + + // Querying for random block returns false. + BOOST_CHECK(!p.isAccepted(pindex)); + + // Add a new block. Check it is added to the polls. + BOOST_CHECK(p.addBlockToReconcile(pindex)); + + // Do one valid round of voting. + uint64_t round = AvalancheTest::getRound(p); + AvalancheResponse resp{round, 0, {AvalancheVote(0, blockHash)}}; + + // Check that all nodes can vote. + for (size_t i = 0; i < avanodes.size(); i++) { + AvalancheTest::runEventLoop(p); + BOOST_CHECK(p.registerVotes(avanodes[i]->GetId(), next(resp), updates)); + } + + // Generate a query for every single node. + const NodeId firstNodeId = AvalancheTest::getSuitableNodeToQuery(p); + std::map node_round_map; + round = AvalancheTest::getRound(p); + for (size_t i = 0; i < avanodes.size(); i++) { + NodeId nodeid = AvalancheTest::getSuitableNodeToQuery(p); + BOOST_CHECK(node_round_map.find(nodeid) == node_round_map.end()); + node_round_map[nodeid] = AvalancheTest::getRound(p); + AvalancheTest::runEventLoop(p); + } + + // Now only tge first node can vote. All others would be duplicate in the + // quorum. + auto confidence = p.getConfidence(pindex); + BOOST_REQUIRE(confidence > 0); + + for (auto &pair : node_round_map) { + NodeId nodeid = pair.first; + uint64_t r = pair.second; + + if (nodeid == firstNodeId) { + // Node 0 is the only one which can vote at this stage. + round = r; + continue; + } + + BOOST_CHECK(p.registerVotes( + nodeid, {r, 0, {AvalancheVote(0, blockHash)}}, updates)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), confidence); + } + + BOOST_CHECK(p.registerVotes( + firstNodeId, {round, 0, {AvalancheVote(0, blockHash)}}, updates)); + BOOST_CHECK_EQUAL(p.getConfidence(pindex), confidence + 1); + + CConnmanTest::ClearNodes(); +} + BOOST_AUTO_TEST_CASE(event_loop) { AvalancheProcessor p(g_connman.get()); CScheduler s;