Page MenuHomePhabricator
Files F13711389

D11474.diff
No OneTemporary
Actions

D11474.diff
View Options

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 <typename VoteItem> 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<BlockProvider, ProofProvider>;
-#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<VoteStatus> 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;
}
}

File Metadata

Mime Type
text/plain
Expires
Sat, Apr 26, 11:50 (2 h, 31 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5573458
Default Alt Text
D11474.diff (14 KB)

Event Timeline