diff --git a/src/avalanche/avalanche.h b/src/avalanche/avalanche.h --- a/src/avalanche/avalanche.h +++ b/src/avalanche/avalanche.h @@ -24,6 +24,11 @@ */ static constexpr bool AVALANCHE_DEFAULT_PEER_DISCOVERY_ENABLED = false; +/** + * Is avalanche proof conflict resolution by voting enabled by default. + */ +static constexpr bool AVALANCHE_DEFAULT_PROOF_VOTING_ENABLED = false; + /** * Avalanche default cooldown in milliseconds. */ diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h --- a/src/avalanche/peermanager.h +++ b/src/avalanche/peermanager.h @@ -8,8 +8,10 @@ #include #include #include +#include #include #include +#include #include #include @@ -35,6 +37,7 @@ static constexpr size_t AVALANCHE_ORPHANPROOFPOOL_SIZE = 10000; class Delegation; +struct VoteRecord; namespace { struct TestPeerManager; @@ -173,6 +176,18 @@ */ std::unordered_set m_unbroadcast_proofids; + struct ProofSharedPointerComparator { + bool operator()(const std::shared_ptr &lhs, + const std::shared_ptr &rhs) const; + }; + using ProofVoteMap = std::map, VoteRecord, + ProofSharedPointerComparator>; + + /** + * Proofs to run avalanche on. + */ + RWCollection conflicting_proofs; + public: /** * Node API. @@ -216,6 +231,12 @@ return it != pview.end() && func(*it); } + template + bool forPeer(const PeerId &peerid, Callable &&func) const { + auto it = peers.find(peerid); + return it != peers.end() && func(*it); + } + template void forEachPeer(Callable &&func) const { for (const auto &p : peers) { func(p); @@ -234,6 +255,13 @@ void removeUnbroadcastProof(const ProofId &proofid); auto getUnbroadcastProofs() const { return m_unbroadcast_proofids; } + /** + * Conflicting proofs API + */ + auto getConflictingProofs() const { + return conflicting_proofs.getReadView(); + } + /**************************************************** * Functions which are public for testing purposes. * ****************************************************/ diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -257,11 +257,19 @@ // Attach UTXOs to this proof. std::unordered_set conflicting_peerids; + bool accepted = true; for (const auto &s : proof->getStakes()) { auto p = utxos.emplace(s.getStake().getUTXO(), peerid); if (!p.second) { // We have a collision with an existing proof. conflicting_peerids.insert(p.first->second); + + accepted &= forPeer(p.first->second, [&](const Peer &peer) { + if (proof->getSequence() > peer.proof->getSequence()) { + return true; + } + return false; + }); } } @@ -277,6 +285,8 @@ } } + conflicting_proofs.getWriteView()->emplace(proof, VoteRecord(accepted)); + return peers.end(); } @@ -527,4 +537,17 @@ m_unbroadcast_proofids.erase(proofid); } +bool PeerManager::ProofSharedPointerComparator::operator()( + const std::shared_ptr &lhs, + const std::shared_ptr &rhs) const { + uint32_t scoreLhs = lhs->getScore(); + uint32_t scoreRhs = rhs->getScore(); + + if (scoreLhs != scoreRhs) { + return scoreLhs > scoreRhs; + } + + return lhs->getId() < rhs->getId(); +} + } // namespace avalanche diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp --- a/src/avalanche/processor.cpp +++ b/src/avalanche/processor.cpp @@ -4,6 +4,7 @@ #include +#include #include #include #include @@ -480,6 +481,24 @@ std::vector Processor::getInvsForNextPoll(bool forPoll) { std::vector invs; + if (gArgs.GetBoolArg("-enableavalancheproofvoting", + AVALANCHE_DEFAULT_PROOF_VOTING_ENABLED)) { + auto getConflictingProofs = [this]() { + LOCK(cs_peerManager); + return peerManager->getConflictingProofs(); + }; + auto conflictingProofsReadView = getConflictingProofs(); + + auto it = conflictingProofsReadView.begin(); + // Clamp to AVALANCHE_MAX_ELEMENT_POLL - 1 so we're always able to poll + // for a new block. + while (it != conflictingProofsReadView.end() && + invs.size() < AVALANCHE_MAX_ELEMENT_POLL - 1) { + invs.emplace_back(MSG_AVA_PROOF, it->first->getId()); + ++it; + } + } + // First remove all blocks that are not worth polling. { LOCK(cs_main); diff --git a/src/init.cpp b/src/init.cpp --- a/src/init.cpp +++ b/src/init.cpp @@ -1248,6 +1248,11 @@ strprintf("Enable avalanche peer discovery (default: %u)", AVALANCHE_DEFAULT_PEER_DISCOVERY_ENABLED), ArgsManager::ALLOW_ANY, OptionsCategory::AVALANCHE); + argsman.AddArg("-enableavalancheproofvoting", + strprintf("Enable avalanche proof conflict resolution by " + "voting on the proofs (default: %u)", + AVALANCHE_DEFAULT_PROOF_VOTING_ENABLED), + ArgsManager::ALLOW_BOOL, OptionsCategory::AVALANCHE); argsman.AddArg( "-avacooldown", strprintf("Mandatory cooldown between two avapoll (default: %u)", diff --git a/test/functional/abc_p2p_avalanche_proof_voting.py b/test/functional/abc_p2p_avalanche_proof_voting.py new file mode 100755 --- /dev/null +++ b/test/functional/abc_p2p_avalanche_proof_voting.py @@ -0,0 +1,104 @@ +#!/usr/bin/env python3 +# Copyright (c) 2020-2021 The Bitcoin developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. +"""Test the conflicting proofs voting.""" +from test_framework.avatools import ( + create_coinbase_stakes, + gen_proof, + get_ava_p2p_interface, + get_proof_ids, +) +from test_framework.key import ( + ECKey, +) +from test_framework.messages import ( + AvalancheProof, + CInv, + FromHex, + MSG_AVA_PROOF, +) +from test_framework.p2p import p2p_lock +from test_framework.test_framework import BitcoinTestFramework +from test_framework.util import ( + assert_equal, + assert_raises_rpc_error, + wait_until, +) + +QUORUM_NODE_COUNT = 16 + + +class AvalancheProofVotingTest(BitcoinTestFramework): + def set_test_params(self): + self.setup_clean_chain = True + self.num_nodes = 1 + self.extra_args = [[ + '-enableavalanche=1', + '-enableavalancheproofvoting=1', + '-avacooldown=0', + ]] + + def run_test(self): + node = self.nodes[0] + + # Build a fake quorum of nodes. + def get_quorum(): + nodes = [] + for i in range(QUORUM_NODE_COUNT): + n = get_ava_p2p_interface(node) + key, proof = gen_proof(node) + assert node.addavalanchenode( + n.nodeid, + key.get_pubkey().get_bytes().hex(), + proof.serialize().hex(), + ) + nodes.append(n) + return nodes + + # Pick on node from the quorum for polling. + quorum = get_quorum() + assert_equal(len(node.getavalanchepeerinfo()), QUORUM_NODE_COUNT) + + privkey = ECKey() + privkey.generate() + pubkey = privkey.get_pubkey() + + addrkey0 = node.get_deterministic_priv_key() + blockhashes = node.generatetoaddress(1, addrkey0.address) + stakes = create_coinbase_stakes(node, blockhashes, addrkey0.key) + + def get_proof_with_sequence_number(sequence_number): + proof = node.buildavalancheproof( + sequence_number, 2000000000, pubkey.get_bytes().hex(), stakes) + proofid = FromHex(AvalancheProof(), proof).proofid + return proofid, proof + + proofid_seq10, proof_seq10 = get_proof_with_sequence_number(10) + proofid_seq20, proof_seq20 = get_proof_with_sequence_number(20) + proofid_seq30, proof_seq30 = get_proof_with_sequence_number(30) + + node.sendavalancheproof(proof_seq20) + assert proofid_seq20 in get_proof_ids(node) + + def avapoll_found(proofid): + inv = CInv(t=MSG_AVA_PROOF, h=proofid) + with p2p_lock: + return any(peer.last_message.get( + "avapoll") and inv in peer.last_message["avapoll"].poll.invs for peer in quorum) + + def check_proof_is_polled(proofid, proof): + assert_raises_rpc_error(-8, "The proof has conflicting utxo with an existing proof", + node.sendavalancheproof, proof) + wait_until(lambda: avapoll_found(proofid)) + assert proofid not in get_proof_ids(node) + + self.log.info("Check the node is polling for conflicting proofs") + # Conflicting proof with higher sequence number + check_proof_is_polled(proofid_seq30, proof_seq30) + # Conflicting proof with lower sequence number + check_proof_is_polled(proofid_seq10, proof_seq10) + + +if __name__ == '__main__': + AvalancheProofVotingTest().main()