diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -149,6 +149,7 @@ scheduler.cpp script/sign.cpp script/standard.cpp + utxocommit.cpp warnings.cpp ) diff --git a/src/Makefile.am b/src/Makefile.am --- a/src/Makefile.am +++ b/src/Makefile.am @@ -170,6 +170,7 @@ util.h \ utilmoneystr.h \ utiltime.h \ + utxocommit.cpp \ validation.h \ validationinterface.h \ versionbits.h \ diff --git a/src/Makefile.test.include b/src/Makefile.test.include --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -104,6 +104,7 @@ test/undo_tests.cpp \ test/univalue_tests.cpp \ test/util_tests.cpp \ + test/utxocommit_tests.cpp \ test/validation_tests.cpp if ENABLE_WALLET diff --git a/src/coins.h b/src/coins.h --- a/src/coins.h +++ b/src/coins.h @@ -20,9 +20,13 @@ /** * A UTXO entry. * - * Serialized format: + * Serialized format for storage: * - VARINT((coinbase ? 1 : 0) | (height << 1)) * - the non-spent CTxOut (via CTxOutCompressor) + * + * Serialized format for network is used for UTXO commitment + * - CompactSize((coinbase ? 1 : 0) | (height << 1)) + * - the non-spent CTxOut (uncompressed) */ class Coin { //! Unspent transaction output. @@ -54,9 +58,16 @@ } template void Serialize(Stream &s) const { - assert(!IsSpent()); - ::Serialize(s, VARINT(nHeightAndIsCoinBase)); - ::Serialize(s, CTxOutCompressor(REF(out))); + if (s.GetType() & SER_DISK) { + assert(!IsSpent()); + ::Serialize(s, VARINT(nHeightAndIsCoinBase)); + // only compress for disk format + ::Serialize(s, CTxOutCompressor(REF(out))); + } else { + // UTXO commitment format + ::WriteCompactSize(s, nHeightAndIsCoinBase); + ::Serialize(s, REF(out)); + } } template void Unserialize(Stream &s) { diff --git a/src/secp256k1/include/secp256k1_multiset.h b/src/secp256k1/include/secp256k1_multiset.h --- a/src/secp256k1/include/secp256k1_multiset.h +++ b/src/secp256k1/include/secp256k1_multiset.h @@ -18,7 +18,7 @@ /** Opaque multiset; this is actually a group element **/ typedef struct { - unsigned char d[96]; + unsigned char data[96]; } secp256k1_multiset; diff --git a/src/secp256k1/src/modules/multiset/main_impl.h b/src/secp256k1/src/modules/multiset/main_impl.h --- a/src/secp256k1/src/modules/multiset/main_impl.h +++ b/src/secp256k1/src/modules/multiset/main_impl.h @@ -20,11 +20,11 @@ */ static void multiset_from_gej_var(secp256k1_multiset *target, const secp256k1_gej *input) { if (input->infinity) { - memset(&target->d, 0, sizeof(target->d)); + memset(&target->data, 0, sizeof(target->data)); } else { - secp256k1_fe_get_b32(target->d, &input->x); - secp256k1_fe_get_b32(target->d+32, &input->y); - secp256k1_fe_get_b32(target->d+64, &input->z); + secp256k1_fe_get_b32(target->data, &input->x); + secp256k1_fe_get_b32(target->data+32, &input->y); + secp256k1_fe_get_b32(target->data+64, &input->z); } } @@ -32,9 +32,9 @@ * Infinite uses special value, z = 0 */ static void gej_from_multiset_var(secp256k1_gej *target, const secp256k1_multiset *input) { - secp256k1_fe_set_b32(&target->x, input->d); - secp256k1_fe_set_b32(&target->y, input->d+32); - secp256k1_fe_set_b32(&target->z, input->d+64); + secp256k1_fe_set_b32(&target->x, input->data); + secp256k1_fe_set_b32(&target->y, input->data+32); + secp256k1_fe_set_b32(&target->z, input->data+64); target->infinity = secp256k1_fe_is_zero(&target->z) ? 1 : 0; } @@ -106,6 +106,7 @@ gej_from_multiset_var(&source, multiset); ge_from_data_var(&newelm, input, inputLen, remove); + secp256k1_gej_clear(&target); secp256k1_gej_add_ge_var(&target, &source, &newelm, NULL); secp256k1_fe_normalize(&target.x); diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -115,6 +115,7 @@ undo_tests.cpp univalue_tests.cpp util_tests.cpp + utxocommit_tests.cpp validation_tests.cpp # Tests generated from JSON diff --git a/src/test/test_bitcoin.h b/src/test/test_bitcoin.h --- a/src/test/test_bitcoin.h +++ b/src/test/test_bitcoin.h @@ -62,6 +62,7 @@ */ class CConnman; struct TestingSetup : public BasicTestingSetup { +public: CCoinsViewDB *pcoinsdbview; fs::path pathTemp; boost::thread_group threadGroup; diff --git a/src/test/utxocommit_tests.cpp b/src/test/utxocommit_tests.cpp new file mode 100644 --- /dev/null +++ b/src/test/utxocommit_tests.cpp @@ -0,0 +1,173 @@ +// 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. + +// Tests for CUtxoCommit wrapper. +// Mostly redundant with libsecp256k1_multiset tests + +#include "coins.h" +#include "test/test_bitcoin.h" +#include "testutil.h" +#include "util.h" + +#include + +#include + +#include "secp256k1/include/secp256k1_multiset.h" +#include "utxocommit.h" + +static COutPoint RandomOutpoint() { + const COutPoint op(InsecureRand256(), insecure_rand()); + return op; +} + +static Coin RandomCoin() { + const Coin c(CTxOut(Amount(InsecureRandRange(1000)), + CScript(InsecureRandBytes(insecure_rand() % 0x3f))), + insecure_rand(), InsecureRandBool()); + return c; +} + +BOOST_FIXTURE_TEST_SUITE(utxocommit_tests, TestingSetup) + +BOOST_AUTO_TEST_CASE(utxo_commit_order) { + + // Test order independence + + const COutPoint op1 = RandomOutpoint(); + const COutPoint op2 = RandomOutpoint(); + const COutPoint op3 = RandomOutpoint(); + const Coin c1 = RandomCoin(); + const Coin c2 = RandomCoin(); + const Coin c3 = RandomCoin(); + + CUtxoCommit uc1, uc2, uc3; + BOOST_CHECK(uc1 == uc2); + uc1.Add(op1, c1); + uc1.Add(op2, c2); + uc1.Add(op3, c3); + + uc2.Add(op2, c2); + BOOST_CHECK(uc1 != uc2); + uc2.Add(op3, c3); + uc2.Add(op1, c1); + BOOST_CHECK(uc1 == uc2); + + // remove ordering + uc2.Remove(op2, c2); + uc2.Remove(op3, c3); + + uc1.Remove(op2, c2); + uc1.Remove(op3, c3); + + BOOST_CHECK(uc1 == uc2); + + // odd but allowed + uc3.Remove(op2, c2); + uc3.Add(op2, c2); + uc3.Add(op1, c1); + BOOST_CHECK(uc1 == uc3); +} + +BOOST_AUTO_TEST_CASE(utxo_commit_serialize) { + + // Test whether the serialization is as expected + + // some coin & output + const std::vector txid = ParseHex( + "38115d014104c6ec27cffce0823c3fecb162dbd576c88dd7cda0b7b32b096118"); + const uint32_t output = 2; + const uint32_t height = 7; + const uint64_t amount = 100; + + const auto script = + CScript(ParseHex("76A9148ABCDEFABBAABBAABBAABBAABBAABBAABBAABBA88AC")); + + const COutPoint op(uint256(txid), output); + const Coin coin = Coin(CTxOut(Amount(amount), script), height, false); + CScript s; + + // find commit + CUtxoCommit commit; + commit.Add(op, coin); + uint256 hash = commit.GetHash(); + + // try the same manually + std::vector expected; + + // txid + expected.insert(expected.end(), txid.begin(), txid.end()); + + // output + auto outputbytes = ParseHex("02000000"); + expected.insert(expected.end(), outputbytes.begin(), outputbytes.end()); + + // height and coinbase => height * 2 + expected.push_back(14); + + // amount & script + auto amountbytes = ParseHex("6400000000000000"); + expected.insert(expected.end(), amountbytes.begin(), amountbytes.end()); + expected.push_back(uint8_t(script.size())); + expected.insert(expected.end(), script.begin(), script.end()); + + secp256k1_context *ctx; + ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE); + secp256k1_multiset multiset; + secp256k1_multiset_init(ctx, &multiset); + secp256k1_multiset_add(ctx, &multiset, expected.data(), expected.size()); + + std::vector expectedhash(32); + secp256k1_multiset_finalize(ctx, expectedhash.data(), &multiset); + + secp256k1_context_destroy(ctx); + BOOST_ASSERT(uint256(expectedhash) == hash); +} + +BOOST_AUTO_TEST_CASE(utxo_commit_addcursor) { + + // Test adding a CCoinView Cursor to a CUtxoCommit + // This simulates the initial upgrade where the commitment stored in + // LevelDB must be generated from the existing UTXO set. + + const int count = 50000; + + // We use the pcoinviewdb provided by the test fixture's TestingSetup + CCoinsViewCache cache(pcoinsdbview); + cache.SetBestBlock(InsecureRand256()); + + // We will compare the commitment generated step-by-step, and the one + // created + // from cursor + CUtxoCommit commit_step, commit_cursor; + + LogPrintf("Preparing database\n"); + + for (int n = 0; n < count; n++) { + const COutPoint op = RandomOutpoint(); + const Coin c = RandomCoin(); + + if (c.GetTxOut().scriptPubKey.IsUnspendable()) { + continue; + } + + commit_step.Add(op, c); + cache.AddCoin(op, c, false); + if ((n + 1) % 5000000 == 0) { + LogPrintf("Flushing\n"); + BOOST_ASSERT(cache.Flush()); + } + } + + BOOST_ASSERT(cache.Flush()); + LogPrintf("Starting ECMH generation from cursor\n"); + + std::unique_ptr pcursor(pcoinsdbview->Cursor()); + commit_cursor.AddCoinView(pcursor.get()); + + BOOST_CHECK(commit_step == commit_cursor); + LogPrintf("ECMH generation from cursor done\n"); +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/utxocommit.h b/src/utxocommit.h new file mode 100644 --- /dev/null +++ b/src/utxocommit.h @@ -0,0 +1,75 @@ +// 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_UTXOCOMMIT_H +#define BITCOIN_UTXOCOMMIT_H + +#include "hash.h" +#include "secp256k1/include/secp256k1_multiset.h" +#include "streams.h" + +#include + +class Coin; +class COutPoint; +class CCoinsViewCursor; + +/** + * A Utxo Commitment + * + * This is maintained as 96-byte multiset value that uniquely defines a UTXO set + * + * It wraps the secp256k1 multiset + * + * Note that a CUtxoCommit allows "negative sets". That is + * + * CUtxoCommit set; // set is an empty set + * set.Remove(X); // set is empty set "minus" X + * set.Add(X); // set is an empty set + * + * This means a CUtxoCommit can both represent the total UTXO set, or a delta to + * the UTXO set +*/ +class CUtxoCommit { +private: + secp256k1_multiset multiset; + +public: + // Constructs empty CUtxoCommit + CUtxoCommit(); + + // Adds a TXO from multiset + void Add(const COutPoint &out, const Coin &element); + + // Adds another commitment to this one + void Add(const CUtxoCommit &other); + + // Removes a TXO from multiset + void Remove(const COutPoint &out, const Coin &element); + + void Clear(); + + uint256 GetHash() const; + + // Initializes from an existing UTXO set + bool AddCoinView(CCoinsViewCursor *cursor); + + // Comparison + friend bool operator==(const CUtxoCommit &a, const CUtxoCommit &b) { + return a.GetHash() == b.GetHash(); + } + friend bool operator!=(const CUtxoCommit &a, const CUtxoCommit &b) { + return a.GetHash() != b.GetHash(); + } + + // Serialization + template void Serialize(Stream &s) const { + s.write((char *)multiset.data, sizeof(multiset)); + } + template void Unserialize(Stream &s) { + s.read((char *)multiset.data, sizeof(multiset)); + } +}; + +#endif // MULTISET_H diff --git a/src/utxocommit.cpp b/src/utxocommit.cpp new file mode 100644 --- /dev/null +++ b/src/utxocommit.cpp @@ -0,0 +1,96 @@ +// Copyright (c) 2017 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "utxocommit.h" + +#include "coins.h" +#include "util.h" + +namespace { +// Lazy, thread-safe singleton that wraps the secp256k1_context used for the +// multisets +class CSecp256k1Context { +private: + secp256k1_context *context; + + CSecp256k1Context() { + context = secp256k1_context_create(SECP256K1_CONTEXT_NONE); + } + + ~CSecp256k1Context() { secp256k1_context_destroy(context); } + +public: + const static secp256k1_context *GetContext() { + static CSecp256k1Context instance; + return instance.context; + } + CSecp256k1Context(CSecp256k1Context const &) = delete; + void operator=(CSecp256k1Context const &) = delete; +}; +} + +// Constructs empty CUtxoCommit +CUtxoCommit::CUtxoCommit() { + secp256k1_multiset_init(CSecp256k1Context::GetContext(), &multiset); +} + +// Adds a TXO to multiset +void CUtxoCommit::Add(const COutPoint &out, const Coin &element) { + CDataStream txo(SER_NETWORK, PROTOCOL_VERSION); + txo << out << element; + secp256k1_multiset_add(CSecp256k1Context::GetContext(), &multiset, + (const uint8_t *)&txo[0], txo.size()); +} + +// Adds another commitment to this one +void CUtxoCommit::Add(const CUtxoCommit &other) { + secp256k1_multiset_combine(CSecp256k1Context::GetContext(), &this->multiset, + &other.multiset); +} + +// Removes a TXO from multiset +void CUtxoCommit::Remove(const COutPoint &out, const Coin &element) { + CDataStream txo(SER_NETWORK, PROTOCOL_VERSION); + txo << out << element; + secp256k1_multiset_remove(CSecp256k1Context::GetContext(), &multiset, + (const uint8_t *)&txo[0], txo.size()); +} + +void CUtxoCommit::Clear() { + secp256k1_multiset_init(CSecp256k1Context::GetContext(), &multiset); +} + +uint256 CUtxoCommit::GetHash() const { + std::vector hash(32); + secp256k1_multiset_finalize(CSecp256k1Context::GetContext(), hash.data(), + &multiset); + return uint256(hash); +} + +bool CUtxoCommit::AddCoinView(CCoinsViewCursor *pcursor) { + LogPrintf("Adding existing UTXO set to the UTXO commitment"); + + // TODO: Parallelize + int n = 0; + while (pcursor->Valid()) { + + COutPoint key; + Coin coin; + if (!pcursor->GetKey(key) || !pcursor->GetValue(coin)) { + return error("Failed to retrieve UTXO from cursor"); + } + + Add(key, coin); + + if ((n % 1000000) == 0) { + uint8_t c = *key.GetTxId().begin(); + LogPrintf("Generating UTXO commitment; progress %d\n", + uint32_t(c) * 100 / 256); + } + n++; + + pcursor->Next(); + } + return true; +}