From 4defdfab94504018f822dc34a313ad26cedc8255 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 12 May 2018 11:48:41 -0700 Subject: [MOVEONLY] Move unused Merkle branch code to tests --- src/consensus/merkle.cpp | 114 -------------------------------------------- src/consensus/merkle.h | 11 +---- src/test/merkle_tests.cpp | 117 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 118 insertions(+), 124 deletions(-) (limited to 'src') diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp index a23dd00144..07cd109cc1 100644 --- a/src/consensus/merkle.cpp +++ b/src/consensus/merkle.cpp @@ -42,93 +42,6 @@ root. */ -/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ -static void MerkleComputation(const std::vector& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector* pbranch) { - if (pbranch) pbranch->clear(); - if (leaves.size() == 0) { - if (pmutated) *pmutated = false; - if (proot) *proot = uint256(); - return; - } - bool mutated = false; - // count is the number of leaves processed so far. - uint32_t count = 0; - // inner is an array of eagerly computed subtree hashes, indexed by tree - // level (0 being the leaves). - // For example, when count is 25 (11001 in binary), inner[4] is the hash of - // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to - // the last leaf. The other inner entries are undefined. - uint256 inner[32]; - // Which position in inner is a hash that depends on the matching leaf. - int matchlevel = -1; - // First process all leaves into 'inner' values. - while (count < leaves.size()) { - uint256 h = leaves[count]; - bool matchh = count == branchpos; - count++; - int level; - // For each of the lower bits in count that are 0, do 1 step. Each - // corresponds to an inner value that existed before processing the - // current leaf, and each needs a hash to combine it. - for (level = 0; !(count & (((uint32_t)1) << level)); level++) { - if (pbranch) { - if (matchh) { - pbranch->push_back(inner[level]); - } else if (matchlevel == level) { - pbranch->push_back(h); - matchh = true; - } - } - mutated |= (inner[level] == h); - CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); - } - // Store the resulting hash at inner position level. - inner[level] = h; - if (matchh) { - matchlevel = level; - } - } - // Do a final 'sweep' over the rightmost branch of the tree to process - // odd levels, and reduce everything to a single top value. - // Level is the level (counted from the bottom) up to which we've sweeped. - int level = 0; - // As long as bit number level in count is zero, skip it. It means there - // is nothing left at this level. - while (!(count & (((uint32_t)1) << level))) { - level++; - } - uint256 h = inner[level]; - bool matchh = matchlevel == level; - while (count != (((uint32_t)1) << level)) { - // If we reach this point, h is an inner value that is not the top. - // We combine it with itself (Bitcoin's special rule for odd levels in - // the tree) to produce a higher level one. - if (pbranch && matchh) { - pbranch->push_back(h); - } - CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); - // Increment count to the value it would have if two entries at this - // level had existed. - count += (((uint32_t)1) << level); - level++; - // And propagate the result upwards accordingly. - while (!(count & (((uint32_t)1) << level))) { - if (pbranch) { - if (matchh) { - pbranch->push_back(inner[level]); - } else if (matchlevel == level) { - pbranch->push_back(h); - matchh = true; - } - } - CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); - level++; - } - } - // Return result. - if (pmutated) *pmutated = mutated; - if (proot) *proot = h; -} uint256 ComputeMerkleRoot(std::vector hashes, bool* mutated) { bool mutation = false; @@ -149,24 +62,6 @@ uint256 ComputeMerkleRoot(std::vector hashes, bool* mutated) { return hashes[0]; } -std::vector ComputeMerkleBranch(const std::vector& leaves, uint32_t position) { - std::vector ret; - MerkleComputation(leaves, nullptr, nullptr, position, &ret); - return ret; -} - -uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector& vMerkleBranch, uint32_t nIndex) { - uint256 hash = leaf; - for (std::vector::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) { - if (nIndex & 1) { - hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash)); - } else { - hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it)); - } - nIndex >>= 1; - } - return hash; -} uint256 BlockMerkleRoot(const CBlock& block, bool* mutated) { @@ -189,12 +84,3 @@ uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated) return ComputeMerkleRoot(std::move(leaves), mutated); } -std::vector BlockMerkleBranch(const CBlock& block, uint32_t position) -{ - std::vector leaves; - leaves.resize(block.vtx.size()); - for (size_t s = 0; s < block.vtx.size(); s++) { - leaves[s] = block.vtx[s]->GetHash(); - } - return ComputeMerkleBranch(leaves, position); -} diff --git a/src/consensus/merkle.h b/src/consensus/merkle.h index f2559d458e..01d75b1329 100644 --- a/src/consensus/merkle.h +++ b/src/consensus/merkle.h @@ -12,9 +12,7 @@ #include #include -uint256 ComputeMerkleRoot(std::vector hashes, bool* mutated); -std::vector ComputeMerkleBranch(const std::vector& leaves, uint32_t position); -uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector& branch, uint32_t position); +uint256 ComputeMerkleRoot(std::vector hashes, bool* mutated = nullptr); /* * Compute the Merkle root of the transactions in a block. @@ -28,11 +26,4 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = nullptr); */ uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated = nullptr); -/* - * Compute the Merkle branch for the tree of transactions in a block, for a - * given position. - * This can be verified using ComputeMerkleRootFromBranch. - */ -std::vector BlockMerkleBranch(const CBlock& block, uint32_t position); - #endif // BITCOIN_CONSENSUS_MERKLE_H diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 72a2672352..259e45dacf 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -9,6 +9,123 @@ BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup) +static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector& vMerkleBranch, uint32_t nIndex) { + uint256 hash = leaf; + for (std::vector::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) { + if (nIndex & 1) { + hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash)); + } else { + hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it)); + } + nIndex >>= 1; + } + return hash; +} + +/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ +static void MerkleComputation(const std::vector& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector* pbranch) { + if (pbranch) pbranch->clear(); + if (leaves.size() == 0) { + if (pmutated) *pmutated = false; + if (proot) *proot = uint256(); + return; + } + bool mutated = false; + // count is the number of leaves processed so far. + uint32_t count = 0; + // inner is an array of eagerly computed subtree hashes, indexed by tree + // level (0 being the leaves). + // For example, when count is 25 (11001 in binary), inner[4] is the hash of + // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to + // the last leaf. The other inner entries are undefined. + uint256 inner[32]; + // Which position in inner is a hash that depends on the matching leaf. + int matchlevel = -1; + // First process all leaves into 'inner' values. + while (count < leaves.size()) { + uint256 h = leaves[count]; + bool matchh = count == branchpos; + count++; + int level; + // For each of the lower bits in count that are 0, do 1 step. Each + // corresponds to an inner value that existed before processing the + // current leaf, and each needs a hash to combine it. + for (level = 0; !(count & (((uint32_t)1) << level)); level++) { + if (pbranch) { + if (matchh) { + pbranch->push_back(inner[level]); + } else if (matchlevel == level) { + pbranch->push_back(h); + matchh = true; + } + } + mutated |= (inner[level] == h); + CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); + } + // Store the resulting hash at inner position level. + inner[level] = h; + if (matchh) { + matchlevel = level; + } + } + // Do a final 'sweep' over the rightmost branch of the tree to process + // odd levels, and reduce everything to a single top value. + // Level is the level (counted from the bottom) up to which we've sweeped. + int level = 0; + // As long as bit number level in count is zero, skip it. It means there + // is nothing left at this level. + while (!(count & (((uint32_t)1) << level))) { + level++; + } + uint256 h = inner[level]; + bool matchh = matchlevel == level; + while (count != (((uint32_t)1) << level)) { + // If we reach this point, h is an inner value that is not the top. + // We combine it with itself (Bitcoin's special rule for odd levels in + // the tree) to produce a higher level one. + if (pbranch && matchh) { + pbranch->push_back(h); + } + CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); + // Increment count to the value it would have if two entries at this + // level had existed. + count += (((uint32_t)1) << level); + level++; + // And propagate the result upwards accordingly. + while (!(count & (((uint32_t)1) << level))) { + if (pbranch) { + if (matchh) { + pbranch->push_back(inner[level]); + } else if (matchlevel == level) { + pbranch->push_back(h); + matchh = true; + } + } + CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); + level++; + } + } + // Return result. + if (pmutated) *pmutated = mutated; + if (proot) *proot = h; +} + +static std::vector ComputeMerkleBranch(const std::vector& leaves, uint32_t position) { + std::vector ret; + MerkleComputation(leaves, nullptr, nullptr, position, &ret); + return ret; +} + +static std::vector BlockMerkleBranch(const CBlock& block, uint32_t position) +{ + std::vector leaves; + leaves.resize(block.vtx.size()); + for (size_t s = 0; s < block.vtx.size(); s++) { + leaves[s] = block.vtx[s]->GetHash(); + } + return ComputeMerkleBranch(leaves, position); +} + // Older version of the merkle root computation code, for comparison. static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector& vMerkleTree) { -- cgit v1.2.3