From eece63fa72566068cb2a1bf85c95a72a5ba59bc9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 17 Nov 2015 17:35:44 +0100 Subject: Switch blocks to a constant-space Merkle root/branch algorithm. This switches the Merkle tree logic for blocks to one that runs in constant (small) space. The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations: * Verifies that the old code and new code agree for the Merkle root. * Verifies that the old code and new code agree for the Merkle branch. * Verifies that the computed Merkle branch is valid. * Verifies that mutations don't change the Merkle root. * Verifies that mutations are correctly detected. --- src/test/merkle_tests.cpp | 136 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 136 insertions(+) create mode 100644 src/test/merkle_tests.cpp (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp new file mode 100644 index 000000000..1e31f2e67 --- /dev/null +++ b/src/test/merkle_tests.cpp @@ -0,0 +1,136 @@ +// Copyright (c) 2015 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "consensus/merkle.h" +#include "test/test_bitcoin.h" +#include "random.h" + +#include + +BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup) + +// Older version of the merkle root computation code, for comparison. +static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector& vMerkleTree) +{ + vMerkleTree.clear(); + vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. + for (std::vector::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) + vMerkleTree.push_back(it->GetHash()); + int j = 0; + bool mutated = false; + for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) + { + for (int i = 0; i < nSize; i += 2) + { + int i2 = std::min(i+1, nSize-1); + if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) { + // Two identical hashes at the end of the list at a particular level. + mutated = true; + } + vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(), + vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end())); + } + j += nSize; + } + if (fMutated) { + *fMutated = mutated; + } + return (vMerkleTree.empty() ? uint256() : vMerkleTree.back()); +} + +// Older version of the merkle branch computation code, for comparison. +static std::vector BlockGetMerkleBranch(const CBlock& block, const std::vector& vMerkleTree, int nIndex) +{ + std::vector vMerkleBranch; + int j = 0; + for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) + { + int i = std::min(nIndex^1, nSize-1); + vMerkleBranch.push_back(vMerkleTree[j+i]); + nIndex >>= 1; + j += nSize; + } + return vMerkleBranch; +} + +static inline int ctz(uint32_t i) { + if (i == 0) return 0; + int j = 0; + while (!(i & 1)) { + j++; + i >>= 1; + } + return j; +} + +BOOST_AUTO_TEST_CASE(merkle_test) +{ + for (int i = 0; i < 32; i++) { + // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes. + int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000); + // Try up to 3 mutations. + for (int mutate = 0; mutate <= 3; mutate++) { + int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first. + if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level). + int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication. + int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation. + if (duplicate2 >= ntx1) break; + int ntx2 = ntx1 + duplicate2; + int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation. + if (duplicate3 >= ntx2) break; + int ntx3 = ntx2 + duplicate3; + // Build a block with ntx different transactions. + CBlock block; + block.vtx.resize(ntx); + for (int j = 0; j < ntx; j++) { + CMutableTransaction mtx; + mtx.nLockTime = j; + block.vtx[j] = mtx; + } + // Compute the root of the block before mutating it. + bool unmutatedMutated = false; + uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated); + BOOST_CHECK(unmutatedMutated == false); + // Optionally mutate by duplicating the last transactions, resulting in the same merkle root. + block.vtx.resize(ntx3); + for (int j = 0; j < duplicate1; j++) { + block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1]; + } + for (int j = 0; j < duplicate2; j++) { + block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2]; + } + for (int j = 0; j < duplicate3; j++) { + block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3]; + } + // Compute the merkle root and merkle tree using the old mechanism. + bool oldMutated = false; + std::vector merkleTree; + uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree); + // Compute the merkle root using the new mechanism. + bool newMutated = false; + uint256 newRoot = BlockMerkleRoot(block, &newMutated); + BOOST_CHECK(oldRoot == newRoot); + BOOST_CHECK(newRoot == unmutatedRoot); + BOOST_CHECK((newRoot == uint256()) == (ntx == 0)); + BOOST_CHECK(oldMutated == newMutated); + BOOST_CHECK(newMutated == !!mutate); + // If no mutation was done (once for every ntx value), try up to 16 branches. + if (mutate == 0) { + for (int loop = 0; loop < std::min(ntx, 16); loop++) { + // If ntx <= 16, try all branches. Otherise, try 16 random ones. + int mtx = loop; + if (ntx > 16) { + mtx = insecure_rand() % ntx; + } + std::vector newBranch = BlockMerkleBranch(block, mtx); + std::vector oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx); + BOOST_CHECK(oldBranch == newBranch); + BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx].GetHash(), newBranch, mtx) == oldRoot); + } + } + } + } +} + +BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From 9d263bd17c2bdd5ba9e31bd5fb110c332eb80691 Mon Sep 17 00:00:00 2001 From: Chris Wheeler Date: Sun, 17 Jan 2016 11:03:56 +0000 Subject: Typo fixes in comments --- src/test/merkle_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 1e31f2e67..b40ab848d 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -77,7 +77,7 @@ BOOST_AUTO_TEST_CASE(merkle_test) int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation. if (duplicate2 >= ntx1) break; int ntx2 = ntx1 + duplicate2; - int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation. + int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation. if (duplicate3 >= ntx2) break; int ntx3 = ntx2 + duplicate3; // Build a block with ntx different transactions. -- cgit v1.2.3 From 5eaaa83ac1f5eb525f93e2808fafd73f5ed97013 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Thu, 13 Oct 2016 16:19:20 +0200 Subject: Kill insecure_random and associated global state There are only a few uses of `insecure_random` outside the tests. This PR replaces uses of insecure_random (and its accompanying global state) in the core code with an FastRandomContext that is automatically seeded on creation. This is meant to be used for inner loops. The FastRandomContext can be in the outer scope, or the class itself, then rand32() is used inside the loop. Useful e.g. for pushing addresses in CNode or the fee rounding, or randomization for coin selection. As a context is created per purpose, thus it gets rid of cross-thread unprotected shared usage of a single set of globals, this should also get rid of the potential race conditions. - I'd say TxMempool::check is not called enough to warrant using a special fast random context, this is switched to GetRand() (open for discussion...) - The use of `insecure_rand` in ConnectThroughProxy has been replaced by an atomic integer counter. The only goal here is to have a different credentials pair for each connection to go on a different Tor circuit, it does not need to be random nor unpredictable. - To avoid having a FastRandomContext on every CNode, the context is passed into PushAddress as appropriate. There remains an insecure_random for test usage in `test_random.h`. --- src/test/merkle_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index b40ab848d..66ca381ea 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -4,7 +4,7 @@ #include "consensus/merkle.h" #include "test/test_bitcoin.h" -#include "random.h" +#include "test_random.h" #include -- cgit v1.2.3 From fa8278e845b6a80164e13a39f917a101fe14b10d Mon Sep 17 00:00:00 2001 From: MarcoFalke Date: Mon, 7 Nov 2016 15:04:57 +0100 Subject: test: Fix test_random includes --- src/test/merkle_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 66ca381ea..706d30f48 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -4,7 +4,7 @@ #include "consensus/merkle.h" #include "test/test_bitcoin.h" -#include "test_random.h" +#include "test/test_random.h" #include -- cgit v1.2.3 From 1662b437b33b7ec5a1723f6ae6187d3bdd06f593 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 10 Nov 2016 17:26:00 -0800 Subject: Make CBlock::vtx a vector of shared_ptr --- src/test/merkle_tests.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 706d30f48..8aea571e1 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -15,8 +15,8 @@ static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::ve { vMerkleTree.clear(); vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. - for (std::vector::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) - vMerkleTree.push_back(it->GetHash()); + for (std::vector>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) + vMerkleTree.push_back((*it)->GetHash()); int j = 0; bool mutated = false; for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) @@ -86,7 +86,7 @@ BOOST_AUTO_TEST_CASE(merkle_test) for (int j = 0; j < ntx; j++) { CMutableTransaction mtx; mtx.nLockTime = j; - block.vtx[j] = mtx; + block.vtx[j] = std::make_shared(mtx); } // Compute the root of the block before mutating it. bool unmutatedMutated = false; @@ -126,7 +126,7 @@ BOOST_AUTO_TEST_CASE(merkle_test) std::vector newBranch = BlockMerkleBranch(block, mtx); std::vector oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx); BOOST_CHECK(oldBranch == newBranch); - BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx].GetHash(), newBranch, mtx) == oldRoot); + BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot); } } } -- cgit v1.2.3 From b4e4ba475a5679e09f279aaf2a83dcf93c632bdb Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 10 Nov 2016 17:34:17 -0800 Subject: Introduce convenience type CTransactionRef --- src/test/merkle_tests.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 8aea571e1..55e6852a1 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -15,7 +15,7 @@ static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::ve { vMerkleTree.clear(); vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. - for (std::vector>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) + for (std::vector::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) vMerkleTree.push_back((*it)->GetHash()); int j = 0; bool mutated = false; @@ -86,7 +86,7 @@ BOOST_AUTO_TEST_CASE(merkle_test) for (int j = 0; j < ntx; j++) { CMutableTransaction mtx; mtx.nLockTime = j; - block.vtx[j] = std::make_shared(mtx); + block.vtx[j] = MakeTransactionRef(std::move(mtx)); } // Compute the root of the block before mutating it. bool unmutatedMutated = false; -- cgit v1.2.3 From 27765b6403cece54320374b37afb01a0cfe571c3 Mon Sep 17 00:00:00 2001 From: isle2983 Date: Sat, 31 Dec 2016 11:01:21 -0700 Subject: Increment MIT Licence copyright header year on files modified in 2016 Edited via: $ contrib/devtools/copyright_header.py update . --- src/test/merkle_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/test/merkle_tests.cpp') diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 55e6852a1..af02d67f7 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2015 The Bitcoin Core developers +// Copyright (c) 2015-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -- cgit v1.2.3