diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -10,6 +10,7 @@
#include <avalanche/proof.h>
#include <avalanche/proofcomparator.h>
#include <avalanche/protocol.h>
+#include <avalanche/voterecord.h> // For AVALANCHE_MAX_INFLIGHT_POLL
#include <blockindex.h>
#include <blockindexcomparators.h>
#include <bloom.h>
@@ -54,6 +55,17 @@
static constexpr std::chrono::milliseconds AVALANCHE_DEFAULT_QUERY_TIMEOUT{
10000};
+/**
+ * The size of the finalized items filter. It should be large enough that an
+ * influx of inventories cannot roll any particular item out of the filter on
+ * demand. For example, transactions will roll blocks out of the filter.
+ * Tracking many more items than can possibly be polled at once ensures that
+ * recently polled items will come to a stable state on the network before
+ * rolling out of the filter.
+ */
+static constexpr uint32_t AVALANCHE_FINALIZED_ITEMS_FILTER_NUM_ELEMENTS =
+ AVALANCHE_MAX_INFLIGHT_POLL * 20;
+
namespace avalanche {
class Delegation;
@@ -302,14 +314,29 @@
EXCLUSIVE_LOCKS_REQUIRED(cs_delayedAvahelloNodeIds);
AnyVoteItem getVoteItemFromInv(const CInv &inv) const;
+ /**
+ * We don't need many blocks but a low false positive rate.
+ * In the event of a false positive the node might skip polling this block.
+ * Such a block will not get marked as finalized until it is reconsidered
+ * for polling (if the filter changed its state) or another block is found.
+ */
mutable Mutex cs_invalidatedBlocks;
- // We don't need much blocks but a low false positive rate.
- // In the event of a false positive the node might skip polling this block.
- // Such a block will not get marked as finalized until it is reconsidered
- // for polling (if the filter changed its state) or another block is found.
CRollingBloomFilter invalidatedBlocks GUARDED_BY(cs_invalidatedBlocks){
100, 0.0000001};
+ /**
+ * Rolling bloom filter to track recently finalized inventory items of any
+ * type. Once placed in this filter, those items will not be polled again
+ * unless they roll out. Note that this one filter tracks all types so
+ * blocks may be rolled out by transaction activity for example.
+ *
+ * We want a low false positive rate to prevent accidentally not polling
+ * for an item when it is first seen.
+ */
+ mutable Mutex cs_finalizedItems;
+ CRollingBloomFilter finalizedItems GUARDED_BY(cs_finalizedItems){
+ AVALANCHE_FINALIZED_ITEMS_FILTER_NUM_ELEMENTS, 0.0000001};
+
struct IsWorthPolling {
const Processor &processor;
@@ -321,9 +348,7 @@
LOCKS_EXCLUDED(cs_peerManager);
bool operator()(const CTransactionRef &tx) const;
};
- bool isWorthPolling(const AnyVoteItem &item) const {
- return std::visit(IsWorthPolling(*this), item);
- }
+ bool isWorthPolling(const AnyVoteItem &item) const;
struct GetLocalAcceptance {
const Processor &processor;
diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -34,6 +34,24 @@
std::unique_ptr<avalanche::Processor> g_avalanche;
namespace avalanche {
+static const uint256 GetVoteItemId(const AnyVoteItem &item) {
+ return std::visit(variant::overloaded{
+ [](const ProofRef &proof) {
+ uint256 id = proof->getId();
+ return id;
+ },
+ [](const CBlockIndex *pindex) {
+ uint256 hash = pindex->GetBlockHash();
+ return hash;
+ },
+ [](const CTransactionRef &tx) {
+ uint256 id = tx->GetId();
+ return id;
+ },
+ },
+ item);
+}
+
static bool VerifyProof(const Amount &stakeUtxoDustThreshold,
const Proof &proof, bilingual_str &error) {
ProofValidationState proof_state;
@@ -569,18 +587,31 @@
}
const auto &item = update.getVoteItem();
+
+ if (update.getStatus() == VoteStatus::Finalized) {
+ // Always track finalized items regardless of type. Once finalized
+ // they should never become invalid.
+ WITH_LOCK(cs_finalizedItems,
+ return finalizedItems.insert(GetVoteItemId(item)));
+ }
+
if (!std::holds_alternative<const CBlockIndex *>(item)) {
continue;
}
- const CBlockIndex *pindex = std::get<const CBlockIndex *>(item);
if (update.getStatus() == VoteStatus::Invalid) {
+ // Track invalidated blocks. Other invalidated types are not
+ // tracked because they may be rejected for transient reasons
+ // (ex: immature proofs or orphaned txs) With blocks this is not
+ // the case. A rejected block will not be mined on. To prevent
+ // reorgs, invalidated blocks should never be polled again.
LOCK(cs_invalidatedBlocks);
- invalidatedBlocks.insert(pindex->GetBlockHash());
+ invalidatedBlocks.insert(GetVoteItemId(item));
continue;
}
// At this point the block index can only be finalized
+ const CBlockIndex *pindex = std::get<const CBlockIndex *>(item);
LOCK(cs_finalizationTip);
if (finalizationTip &&
finalizationTip->GetAncestor(pindex->nHeight) == pindex) {
@@ -1012,6 +1043,12 @@
return processor.mempool->exists(tx->GetId()));
}
+bool Processor::isWorthPolling(const AnyVoteItem &item) const {
+ return std::visit(IsWorthPolling(*this), item) &&
+ WITH_LOCK(cs_finalizedItems,
+ return !finalizedItems.contains(GetVoteItemId(item)));
+}
+
bool Processor::GetLocalAcceptance::operator()(
const CBlockIndex *pindex) const {
AssertLockNotHeld(cs_main);
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
@@ -61,8 +61,26 @@
static void clearavaproofsNodeCounter(Processor &p) {
p.avaproofsNodeCounter = 0;
}
+
+ static void addVoteRecord(Processor &p, AnyVoteItem &item,
+ VoteRecord &voteRecord) {
+ p.voteRecords.getWriteView()->insert(
+ std::make_pair(item, voteRecord));
+ }
+
+ static void setFinalizationTip(Processor &p,
+ const CBlockIndex *pindex) {
+ LOCK(p.cs_finalizationTip);
+ p.finalizationTip = pindex;
+ }
};
} // namespace
+
+struct TestVoteRecord : public VoteRecord {
+ explicit TestVoteRecord(uint16_t conf) : VoteRecord(true) {
+ confidence |= conf << 1;
+ }
+};
} // namespace avalanche
namespace {
@@ -431,15 +449,85 @@
}
}
+namespace {
+Response next(Response &r) {
+ auto copy = r;
+ r = {r.getRound() + 1, r.getCooldown(), r.GetVotes()};
+ return copy;
+}
+} // namespace
+
BOOST_AUTO_TEST_CASE_TEMPLATE(item_reconcile_twice, P, VoteItemProviders) {
P provider(this);
+ const CBlockIndex *chaintip = Assert(m_node.chainman)->ActiveTip();
auto item = provider.buildVoteItem();
+ auto itemid = provider.getVoteItemId(item);
// Adding the item twice does nothing.
BOOST_CHECK(addToReconcile(item));
BOOST_CHECK(!addToReconcile(item));
BOOST_CHECK(m_processor->isAccepted(item));
+
+ // Create nodes that supports avalanche so we can finalize the item.
+ auto avanodes = ConnectNodes();
+
+ int nextNodeIndex = 0;
+ std::vector<avalanche::VoteItemUpdate> updates;
+ auto registerNewVote = [&](const Response &resp) {
+ runEventLoop();
+ auto nodeid = avanodes[nextNodeIndex++ % avanodes.size()]->GetId();
+ BOOST_CHECK(registerVotes(nodeid, resp, updates));
+ };
+
+ // Finalize the item.
+ auto finalize = [&](const auto finalizeItemId) {
+ Response resp = {getRound(), 0, {Vote(0, finalizeItemId)}};
+ for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE + 6; i++) {
+ registerNewVote(next(resp));
+ if (updates.size() > 0) {
+ break;
+ }
+ }
+ BOOST_CHECK_EQUAL(updates.size(), 1);
+ BOOST_CHECK(updates[0].getStatus() == VoteStatus::Finalized);
+ updates.clear();
+ };
+ finalize(itemid);
+
+ // The finalized item cannot be reconciled for a while.
+ BOOST_CHECK(!addToReconcile(item));
+
+ auto finalizeNewItem = [&]() {
+ auto anotherItem = provider.buildVoteItem();
+ AnyVoteItem anotherVoteItem = AnyVoteItem(anotherItem);
+ auto anotherItemId = provider.getVoteItemId(anotherItem);
+
+ TestVoteRecord voteRecord(AVALANCHE_FINALIZATION_SCORE - 1);
+ AvalancheTest::addVoteRecord(*m_processor, anotherVoteItem, voteRecord);
+ finalize(anotherItemId);
+ };
+
+ // The filter can have new items added up to its size and the item will
+ // still not reconcile.
+ for (uint32_t i = 0; i < AVALANCHE_FINALIZED_ITEMS_FILTER_NUM_ELEMENTS;
+ i++) {
+ finalizeNewItem();
+ BOOST_CHECK(!addToReconcile(item));
+ }
+
+ // But if we keep going it will eventually roll out of the filter and can
+ // be reconciled again.
+ for (uint32_t i = 0; i < AVALANCHE_FINALIZED_ITEMS_FILTER_NUM_ELEMENTS;
+ i++) {
+ finalizeNewItem();
+ }
+
+ // Roll back the finalization point so that reconciling the old block does
+ // not fail the finalization check. This is a no-op for other types.
+ AvalancheTest::setFinalizationTip(*m_processor, chaintip);
+
+ BOOST_CHECK(addToReconcile(item));
}
BOOST_AUTO_TEST_CASE_TEMPLATE(item_null, P, VoteItemProviders) {
@@ -463,14 +551,6 @@
BOOST_CHECK_EQUAL(m_processor->getConfidence(nullptr), -1);
}
-namespace {
-Response next(Response &r) {
- auto copy = r;
- r = {r.getRound() + 1, r.getCooldown(), r.GetVotes()};
- return copy;
-}
-} // namespace
-
BOOST_AUTO_TEST_CASE_TEMPLATE(vote_item_register, P, VoteItemProviders) {
P provider(this);
const uint32_t invType = provider.invType;
diff --git a/src/avalanche/voterecord.h b/src/avalanche/voterecord.h
--- a/src/avalanche/voterecord.h
+++ b/src/avalanche/voterecord.h
@@ -41,6 +41,8 @@
namespace avalanche {
+struct TestVoteRecord;
+
/**
* Vote history.
*/
@@ -124,6 +126,8 @@
* quorum.
*/
bool addNodeToQuorum(NodeId nodeid);
+
+ friend struct ::avalanche::TestVoteRecord;
};
} // namespace avalanche