Page MenuHomePhabricator
Files F13115662

D2040.diff
No OneTemporary
Actions

D2040.diff
View Options

diff --git a/src/Makefile.am b/src/Makefile.am
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -102,6 +102,7 @@
BITCOIN_CORE_H = \
addrdb.h \
addrman.h \
+ avalanche_impl.h \
base58.h \
bloom.h \
blockencodings.h \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -25,11 +25,12 @@
# test_bitcoin binary #
BITCOIN_TESTS =\
- test/arith_uint256_tests.cpp \
test/scriptnum10.h \
test/addrman_tests.cpp \
- test/amount_tests.cpp \
test/allocator_tests.cpp \
+ test/amount_tests.cpp \
+ test/arith_uint256_tests.cpp \
+ test/avalanche_tests.cpp \
test/base32_tests.cpp \
test/base58_tests.cpp \
test/base64_tests.cpp \
diff --git a/src/avalanche_impl.h b/src/avalanche_impl.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche_impl.h
@@ -0,0 +1,82 @@
+// Copyright (c) 2018 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_AVALANCHE_IMPL_H
+#define BITCOIN_AVALANCHE_IMPL_H
+
+#include <cstdint>
+
+namespace {
+/**
+ * Finalization score.
+ */
+static int AVALANCHE_FINALIZATION_SCORE = 128;
+
+/**
+ * Vote history.
+ */
+struct VoteRecord {
+private:
+ // Historical record of votes.
+ uint16_t votes;
+
+ // confidence's LSB bit is the result. Higher bits are actual confidence
+ // score.
+ uint16_t confidence;
+
+ /**
+ * Return the number of bits set in an integer value.
+ * TODO: There are compiler intrinsics to do that, but we'd need to get them
+ * detected so this will do for now.
+ */
+ static uint32_t countBits(uint32_t value) {
+ uint32_t count = 0;
+ while (value) {
+ // If the value is non zero, then at least one bit is set.
+ count++;
+
+ // Clear the rightmost bit set.
+ value &= (value - 1);
+ }
+
+ return count;
+ }
+
+public:
+ VoteRecord() : votes(0xaaaa), confidence(0) {}
+
+ bool isValid() const { return confidence & 0x01; }
+
+ uint16_t getConfidence() const { return confidence >> 1; }
+ bool hasFinalized() const {
+ return getConfidence() >= AVALANCHE_FINALIZATION_SCORE;
+ }
+
+ bool 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;
+ }
+
+ if (isValid() == 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 true;
+ }
+};
+}
+
+#endif // BITCOIN_AVALANCHE_IMPL_H
diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt
--- a/src/test/CMakeLists.txt
+++ b/src/test/CMakeLists.txt
@@ -44,10 +44,11 @@
add_dependencies(check check-bitcoin)
add_test_to_suite(bitcoin test_bitcoin
- arith_uint256_tests.cpp
addrman_tests.cpp
- amount_tests.cpp
allocator_tests.cpp
+ amount_tests.cpp
+ arith_uint256_tests.cpp
+ avalanche_tests.cpp
base32_tests.cpp
base58_tests.cpp
base64_tests.cpp
diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/avalanche_tests.cpp
@@ -0,0 +1,69 @@
+// Copyright (c) 2010 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "avalanche_impl.h"
+
+#include "test/test_bitcoin.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_FIXTURE_TEST_SUITE(avalanche_tests, BasicTestingSetup)
+
+#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \
+ vr.registerVote(vote); \
+ BOOST_CHECK_EQUAL(vr.isValid(), state); \
+ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \
+ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence);
+
+BOOST_AUTO_TEST_CASE(vote_record) {
+ VoteRecord vr;
+
+ // Check initial state.
+ BOOST_CHECK_EQUAL(vr.isValid(), false);
+ 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);
+
+ // One more and we are at 5/3.
+ REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
+
+ // One more and we are at 6/2.
+ REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
+
+ // One more and we are at 6/2.
+ REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
+
+ // 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);
+ }
+
+ // The next vote will finalize the decision.
+ REGISTER_VOTE_AND_CHECK(vr, false, 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,
+ 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);
+ }
+
+ // The next vote will finalize the decision.
+ REGISTER_VOTE_AND_CHECK(vr, true, false, true,
+ AVALANCHE_FINALIZATION_SCORE);
+}
+
+BOOST_AUTO_TEST_SUITE_END()

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 1, 11:41 (2 h, 30 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5187662
Default Alt Text
D2040.diff (5 KB)

Event Timeline