diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -519,6 +519,8 @@ add_library(server addrdb.cpp addrman.cpp + avalanche/delegation.cpp + avalanche/delegationbuilder.cpp avalanche/peermanager.cpp avalanche/processor.cpp avalanche/proof.cpp diff --git a/src/avalanche/delegation.h b/src/avalanche/delegation.h new file mode 100644 --- /dev/null +++ b/src/avalanche/delegation.h @@ -0,0 +1,70 @@ +// Copyright (c) 2020 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_DELEGATION_H +#define BITCOIN_AVALANCHE_DELEGATION_H + +#include +#include +#include +#include + +#include + +namespace avalanche { + +class DelegationState; +class Proof; + +class Delegation { + ProofId proofid; + + DelegationId dgid; + DelegationId computeDelegationId() const; + + struct Level { + CPubKey pubkey; + std::array sig; + + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream &s, Operation ser_action) { + READWRITE(pubkey); + READWRITE(sig); + } + }; + + std::vector levels; + + friend class DelegationBuilder; + Delegation(const ProofId &proofid_, const DelegationId &dgid_, + std::vector levels_) + : proofid(proofid_), dgid(dgid_), levels(std::move(levels_)) {} + +public: + explicit Delegation() {} + + const DelegationId &getId() const { return dgid; } + const ProofId &getProofId() const { return proofid; } + + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream &s, Operation ser_action) { + READWRITE(proofid); + READWRITE(levels); + + if (ser_action.ForRead()) { + dgid = computeDelegationId(); + } + } + + bool verify(DelegationState &state, const Proof &proof, + CPubKey &auth) const; +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_DELEGATION_H diff --git a/src/avalanche/delegation.cpp b/src/avalanche/delegation.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/delegation.cpp @@ -0,0 +1,63 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include +#include +#include + +namespace avalanche { + +template +static bool reduceLevels(uint256 &hash, const std::vector &levels, F f) { + for (const auto &l : levels) { + CHashWriter ss(SER_GETHASH, 0); + ss << hash; + ss << l.pubkey; + hash = ss.GetHash(); + + if (!f(l)) { + return false; + } + } + + return true; +} + +template +static bool reduceLevels(uint256 &hash, const std::vector &levels) { + return reduceLevels(hash, levels, [](const L &) { return true; }); +} + +DelegationId Delegation::computeDelegationId() const { + uint256 hash = proofid; + reduceLevels(hash, levels); + return DelegationId(hash); +} + +bool Delegation::verify(DelegationState &state, const Proof &proof, + CPubKey &auth) const { + if (proof.getId() != proofid) { + return state.Invalid(DelegationResult::INCORRECT_PROOF); + } + + uint256 hash = proofid; + const CPubKey *pauth = &proof.getMaster(); + + bool ret = reduceLevels(hash, levels, [&](const Level &l) { + if (!pauth->VerifySchnorr(hash, l.sig)) { + return state.Invalid(DelegationResult::INVALID_SIGNATURE); + } + + // This key is valid, now up to the next delegation level. + pauth = &l.pubkey; + return true; + }); + + auth = *pauth; + return ret; +} + +} // namespace avalanche diff --git a/src/avalanche/delegationbuilder.h b/src/avalanche/delegationbuilder.h new file mode 100644 --- /dev/null +++ b/src/avalanche/delegationbuilder.h @@ -0,0 +1,36 @@ +// Copyright (c) 2020 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_DELEGATIONBUILDER_H +#define BITCOIN_AVALANCHE_DELEGATIONBUILDER_H + +#include +#include +#include + +#include + +class CKey; + +namespace avalanche { + +class Proof; + +class DelegationBuilder { + ProofId proofid; + DelegationId dgid; + + std::vector levels; + +public: + DelegationBuilder(const Proof &p); + + bool addLevel(const CKey &key, const CPubKey &newMaster); + + Delegation build() const; +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_DELEGATIONBUILDER_H diff --git a/src/avalanche/delegationbuilder.cpp b/src/avalanche/delegationbuilder.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/delegationbuilder.cpp @@ -0,0 +1,45 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include + +namespace avalanche { + +DelegationBuilder::DelegationBuilder(const Proof &p) + : proofid(p.getId()), dgid(proofid) { + levels.push_back({p.getMaster(), {}}); +} + +bool DelegationBuilder::addLevel(const CKey &key, const CPubKey &master) { + // Ensures that the private key provided is the one we need. + if (levels.back().pubkey != key.GetPubKey()) { + return false; + } + + CHashWriter ss(SER_GETHASH, 0); + ss << dgid; + ss << master; + auto hash = ss.GetHash(); + + if (!key.SignSchnorr(hash, levels.back().sig)) { + return false; + } + + dgid = DelegationId(hash); + levels.push_back({master, {}}); + return true; +} + +Delegation DelegationBuilder::build() const { + std::vector dglvls; + for (size_t i = 1; i < levels.size(); i++) { + dglvls.push_back({levels[i].pubkey, levels[i - 1].sig}); + } + + return Delegation(proofid, dgid, std::move(dglvls)); +} + +} // namespace avalanche diff --git a/src/avalanche/delegationid.h b/src/avalanche/delegationid.h new file mode 100644 --- /dev/null +++ b/src/avalanche/delegationid.h @@ -0,0 +1,27 @@ +// Copyright (c) 2020 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_DELEGATIONID_H +#define BITCOIN_AVALANCHE_DELEGATIONID_H + +#include + +#include + +namespace avalanche { + +struct DelegationId : public uint256 { + explicit DelegationId() : uint256() {} + explicit DelegationId(const uint256 &b) : uint256(b) {} + + static DelegationId fromHex(const std::string &str) { + DelegationId r; + r.SetHex(str); + return r; + } +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_DELEGATIONID_H diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -4,6 +4,7 @@ #include +#include #include #include #include // For ChainstateActive() diff --git a/src/avalanche/proof.h b/src/avalanche/proof.h --- a/src/avalanche/proof.h +++ b/src/avalanche/proof.h @@ -6,10 +6,10 @@ #define BITCOIN_AVALANCHE_PROOF_H #include +#include #include #include #include -#include #include #include @@ -21,17 +21,6 @@ class ProofValidationState; -struct ProofId : public uint256 { - explicit ProofId() : uint256() {} - explicit ProofId(const uint256 &b) : uint256(b) {} - - static ProofId fromHex(const std::string &str) { - ProofId r; - r.SetHex(str); - return r; - } -}; - class Stake { COutPoint utxo; diff --git a/src/avalanche/proofid.h b/src/avalanche/proofid.h new file mode 100644 --- /dev/null +++ b/src/avalanche/proofid.h @@ -0,0 +1,26 @@ +// Copyright (c) 2020 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_PROOFID_H +#define BITCOIN_AVALANCHE_PROOFID_H + +#include + +#include + +namespace avalanche { + +struct ProofId : public uint256 { + explicit ProofId() : uint256() {} + explicit ProofId(const uint256 &b) : uint256(b) {} + + static ProofId fromHex(const std::string &str) { + ProofId r; + r.SetHex(str); + return r; + } +}; +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_PROOFID_H diff --git a/src/avalanche/test/CMakeLists.txt b/src/avalanche/test/CMakeLists.txt --- a/src/avalanche/test/CMakeLists.txt +++ b/src/avalanche/test/CMakeLists.txt @@ -13,6 +13,7 @@ util.cpp TESTS + delegation_tests.cpp peermanager_tests.cpp processor_tests.cpp proof_tests.cpp diff --git a/src/avalanche/test/delegation_tests.cpp b/src/avalanche/test/delegation_tests.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/test/delegation_tests.cpp @@ -0,0 +1,177 @@ +// Copyright (c) 2020 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include +#include +#include +#include + +#include + +#include + +#include +#include + +using namespace avalanche; + +BOOST_FIXTURE_TEST_SUITE(delegation_tests, TestingSetup) + +static void CheckDelegation(const Delegation &dg, const Proof &p, + const CPubKey &expected_pubkey) { + DelegationState state; + CPubKey pubkey; + BOOST_CHECK(dg.verify(state, p, pubkey)); + BOOST_CHECK(state.GetResult() == DelegationResult::NONE); + BOOST_CHECK(pubkey == expected_pubkey); + + const Proof altp = buildRandomProof(654321); + BOOST_CHECK(!dg.verify(state, altp, pubkey)); + BOOST_CHECK(state.GetResult() == DelegationResult::INCORRECT_PROOF); +} + +BOOST_AUTO_TEST_CASE(verify_random) { + CKey key; + key.MakeNewKey(true); + + const Proof p = buildRandomProof(123456, key.GetPubKey()); + DelegationBuilder dgb(p); + + { + Delegation dg = dgb.build(); + BOOST_CHECK_EQUAL(dg.getId(), p.getId()); + CheckDelegation(dg, p, p.getMaster()); + } + + CKey l1key; + l1key.MakeNewKey(true); + BOOST_CHECK(!dgb.addLevel(l1key, key.GetPubKey())); + + dgb.addLevel(key, l1key.GetPubKey()); + CheckDelegation(dgb.build(), p, l1key.GetPubKey()); + + CKey l2key; + l2key.MakeNewKey(true); + BOOST_CHECK(!dgb.addLevel(key, l2key.GetPubKey())); + BOOST_CHECK(!dgb.addLevel(l2key, l2key.GetPubKey())); + + dgb.addLevel(l1key, l2key.GetPubKey()); + CheckDelegation(dgb.build(), p, l2key.GetPubKey()); +} + +static Proof getProof() { + Proof p; + CDataStream stream( + ParseHex( + "0000000000000000ffffffff000000002103717ba63ac0a84495aca04d0cbffea2" + "684d2306ec53f3b90c064989f9d0e8761701bee72758084395310b5a7ccc98a836" + "11dff786f0a469d1d66626ba286b0423870000000000108dbe1c000000a4090000" + "21021a766cd1dc8bd54252a61592c9c3b1c06495f2f6965ad950dbe9f8b1890670" + "bdb68872cb4bea3a981986a6a6b5d84636d4adc8f8c0e956392dd114b2241ec8df" + "a79ff1580d8b4fd6bfdecea98a164ee2fd23157a97f31624cc740063a7b69b4f"), + SER_NETWORK, 0); + stream >> p; + BOOST_CHECK_EQUAL(p.getId(), + ProofId::fromHex("004caaf05fb28c2e12fbf930b7f941baf06d2e3" + "db210d8e55b22a4cd11d41d71")); + return p; +} + +struct TestVector { + std::string name; + std::string hex; + std::string dgid; + std::string pubkey; + DelegationResult result; +}; + +BOOST_AUTO_TEST_CASE(deserialization) { + Proof p = getProof(); + + std::vector testcases{ + {"Empty delegation", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0000", + "004caaf05fb28c2e12fbf930b7f941baf06d2e3db210d8e55b22a4cd11d41d71", + "03717ba63ac0a84495aca04d0cbffea2684d2306ec53f3b90c064989f9d0e87617", + DelegationResult::NONE}, + {"One delegation", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0001210" + "3e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7cccccc38bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c78", + "70aa515da27335d39db7a7a721d14a3dce07bc5d919982e2082d2fa6c5cc4652", + "03e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab", + DelegationResult::NONE}, + {"Two delegation", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0002210" + "3e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7cccccc38bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c782103068e41c1a9" + "4a095cc0fcda08cf2add169e00d39f126d9dfa0c6f4bdfb397819f3a8ebb3ef304147" + "087f7fa3b2ae60921a241a503bcbd844bf63cf88f75380aebeae9ef0592fab2c66730" + "bc64d09387d97ac7019171b83a3cac43c3350c85d61a", + "232cb4c5c9261ba92b885ba1af63212c0b9b9d1e0e0bc68c80e22b05a7a48887", + "03068e41c1a94a095cc0fcda08cf2add169e00d39f126d9dfa0c6f4bdfb397819f", + DelegationResult::NONE}, + {"Incorrect proof", + "721dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0000", + "004caaf05fb28c2e12fbf930b7f941baf06d2e3db210d8e55b22a4cd11d41d72", "", + DelegationResult::INCORRECT_PROOF}, + {"Invalid pubkey", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0001210" + "3e1f0e1af3f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7cccccc38bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c78", + "101319ff1c4153492a0b14d4e2539396b2da92452756bbf8069f28690cbdba4e", + "03717ba63ac0a84495aca04d0cbffea2684d2306ec53f3b90c064989f9d0e87617", + DelegationResult::INVALID_SIGNATURE}, + {"Invalid signature", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0001210" + "3e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7ccccccc8bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c78", + "70aa515da27335d39db7a7a721d14a3dce07bc5d919982e2082d2fa6c5cc4652", + "03717ba63ac0a84495aca04d0cbffea2684d2306ec53f3b90c064989f9d0e87617", + DelegationResult::INVALID_SIGNATURE}, + {"Second invalid key", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0002210" + "3e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7cccccc38bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c782103068e41c2a9" + "4a095cc0fcda08cf2add169e00d39f126d9dfa0c6f4bdfb397819f3a8ebb3ef304147" + "087f7fa3b2ae60921a241a503bcbd844bf63cf88f75380aebeae9ef0592fab2c66730" + "bc64d09387d97ac7019171b83a3cac43c3350c85d61a", + "78c9222e1031fd85f0efe619de1f58c78ad4497a23693bc38c3fd20466215b1a", + "03e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab", + DelegationResult::INVALID_SIGNATURE}, + {"Second invalid signature", + "711dd411cda4225be5d810b23d2e6df0ba41f9b730f9fb122e8cb25ff0aa4c0002210" + "3e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab0347" + "5811c001c4c7cccccc38bb3308917c116187cd2becd4a0158072a5b8f3b64fcd8667c" + "cb06beed29b48dd4cd113570779136e1dba6892343c104832675c782103068e41c1a9" + "4a095cc0fcda08cf2add169e00d39f126d9dfa0c6f4bdfb397819f3a8ebb3ef304147" + "087f7fa3b2ae60921a241a504bcbd844bf63cf88f75380aebeae9ef0592fab2c66730" + "bc64d09387d97ac7019171b83a3cac43c3350c85d61a", + "232cb4c5c9261ba92b885ba1af63212c0b9b9d1e0e0bc68c80e22b05a7a48887", + "03e1f0e1af2f5cd09bb0b37be8c4e100788dda36b2aa8c9b45fac54728177aaaab", + DelegationResult::INVALID_SIGNATURE}, + }; + + for (auto &c : testcases) { + CDataStream stream(ParseHex(c.hex), SER_NETWORK, 0); + Delegation dg; + stream >> dg; + BOOST_CHECK_EQUAL(dg.getId(), DelegationId::fromHex(c.dgid)); + + DelegationState state; + CPubKey pubkey; + BOOST_CHECK_EQUAL(dg.verify(state, p, pubkey), + c.result == DelegationResult::NONE); + BOOST_CHECK(state.GetResult() == c.result); + BOOST_CHECK(pubkey == CPubKey(ParseHex(c.pubkey))); + } +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp --- a/src/avalanche/test/peermanager_tests.cpp +++ b/src/avalanche/test/peermanager_tests.cpp @@ -6,7 +6,6 @@ #include #include