diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -181,6 +181,7 @@ add_library(server addrman.cpp addrdb.cpp + avalanche.cpp bloom.cpp blockencodings.cpp chain.cpp diff --git a/src/Makefile.am b/src/Makefile.am --- a/src/Makefile.am +++ b/src/Makefile.am @@ -102,7 +102,7 @@ BITCOIN_CORE_H = \ addrdb.h \ addrman.h \ - avalanche_impl.h \ + avalanche.h \ base58.h \ bloom.h \ blockencodings.h \ @@ -227,6 +227,7 @@ libbitcoin_server_a_SOURCES = \ addrman.cpp \ addrdb.cpp \ + avalanche.cpp \ bloom.cpp \ blockencodings.cpp \ chain.cpp \ diff --git a/src/avalanche_impl.h b/src/avalanche.h rename from src/avalanche_impl.h rename to src/avalanche.h --- a/src/avalanche_impl.h +++ b/src/avalanche.h @@ -2,16 +2,28 @@ // 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 +#ifndef BITCOIN_AVALANCHE_H +#define BITCOIN_AVALANCHE_H + +#include "net.h" // for NodeId +#include "protocol.h" // for CInv +#include "rwcollection.h" +#include "serialize.h" +#include "uint256.h" #include +#include + +class Config; +class CBlockIndex; +class CScheduler; namespace { /** * Finalization score. */ static int AVALANCHE_FINALIZATION_SCORE = 128; +} /** * Vote history. @@ -77,6 +89,60 @@ return true; } }; -} -#endif // BITCOIN_AVALANCHE_IMPL_H +class AvalancheVote { + uint256 hash; + uint64_t error; + +public: + AvalancheVote(uint256 hashIn, uint64_t errorIn) + : hash(hashIn), error(errorIn) {} + + const uint256 &GetHash() const { return hash; } + bool IsValid() const { return error == 0; } + + // serialization support + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream &s, Operation ser_action) { + READWRITE(hash); + READWRITE(error); + } +}; + +class AvalancheResponse { + std::vector votes; + +public: + AvalancheResponse(std::vector votesIn) : votes(votesIn) {} + + const std::vector &GetVotes() const { return votes; } + + // serialization support + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream &s, Operation ser_action) { + READWRITE(votes); + } +}; + +class AvalancheProcessor { +private: + /** + * Blocks to run avalanche on. + */ + RWCollection> vote_records; + +public: + AvalancheProcessor() {} + + bool addBlockToReconciliate(const CBlockIndex *pindex); + bool isAccepted(const CBlockIndex *pindex) const; + bool hasFinalized(const CBlockIndex *pindex) const; + + bool registerVotes(const AvalancheResponse &response); +}; + +#endif // BITCOIN_AVALANCHE_H diff --git a/src/avalanche.cpp b/src/avalanche.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche.cpp @@ -0,0 +1,55 @@ +// 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. + +#include "avalanche.h" + +#include "chain.h" +#include "netmessagemaker.h" +#include "scheduler.h" + +bool AvalancheProcessor::addBlockToReconciliate(const CBlockIndex *pindex) { + return vote_records.getWriteView() + ->insert(std::make_pair(pindex->GetBlockHash(), VoteRecord())) + .second; +} + +static const VoteRecord * +GetRecord(const RWCollection> &vote_records, + const CBlockIndex *pindex) { + auto r = vote_records.getReadView(); + auto it = r->find(pindex->GetBlockHash()); + if (it == r.end()) { + return nullptr; + } + + return &it->second; +} + +bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const { + if (auto vr = GetRecord(vote_records, pindex)) { + return vr->isValid(); + } + + 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) { + const std::vector &votes = response.GetVotes(); + + // Register votes. + auto w = vote_records.getWriteView(); + for (auto &v : votes) { + w[v.GetHash()].registerVote(v.IsValid()); + } + + return true; +} 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 @@ -2,7 +2,7 @@ // 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 "avalanche.h" #include "test/test_bitcoin.h" @@ -66,4 +66,67 @@ AVALANCHE_FINALIZATION_SCORE); } +BOOST_AUTO_TEST_CASE(block_register) { + AvalancheProcessor p; + CBlockIndex index; + + // Make sure the block has a hash. + const uint256 zeroHash; + index.phashBlock = &zeroHash; + + // Querying for random block returns false. + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(!p.hasFinalized(&index)); + + // Newly added blocks are also considered rejected. + BOOST_CHECK(p.addBlockToReconciliate(&index)); + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(!p.hasFinalized(&index)); + + // Let's vote for this block a few times. + AvalancheResponse resp{{AvalancheVote(zeroHash, 0)}}; + for (int i = 0; i < 5; i++) { + p.registerVotes(resp); + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(!p.hasFinalized(&index)); + } + + // Now it is accepeted, but we can vote for it numerous times. + for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp); + BOOST_CHECK(p.isAccepted(&index)); + BOOST_CHECK(!p.hasFinalized(&index)); + } + + // Now finalize the decision. + resp = {{AvalancheVote(zeroHash, 1)}}; + p.registerVotes(resp); + BOOST_CHECK(p.isAccepted(&index)); + BOOST_CHECK(p.hasFinalized(&index)); + + // Now let's undo this and finalize rejection. + for (int i = 0; i < 5; i++) { + p.registerVotes(resp); + BOOST_CHECK(p.isAccepted(&index)); + BOOST_CHECK(p.hasFinalized(&index)); + } + + // Now it is rejected, but we can vote for it numerous times. + for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp); + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(!p.hasFinalized(&index)); + } + + // Now finalize the decision. + p.registerVotes(resp); + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(p.hasFinalized(&index)); + + // Adding the block twice does nothing. + BOOST_CHECK(!p.addBlockToReconciliate(&index)); + BOOST_CHECK(!p.isAccepted(&index)); + BOOST_CHECK(p.hasFinalized(&index)); +} + BOOST_AUTO_TEST_SUITE_END()