diff options
Diffstat (limited to 'src/consensus')
| -rw-r--r-- | src/consensus/merkle.cpp | 114 | ||||
| -rw-r--r-- | src/consensus/merkle.h | 11 |
2 files changed, 1 insertions, 124 deletions
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<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* 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<uint256> hashes, bool* mutated) { bool mutation = false; @@ -149,24 +62,6 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) { return hashes[0]; } -std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) { - std::vector<uint256> ret; - MerkleComputation(leaves, nullptr, nullptr, position, &ret); - return ret; -} - -uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) { - uint256 hash = leaf; - for (std::vector<uint256>::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<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position) -{ - std::vector<uint256> 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 <primitives/block.h> #include <uint256.h> -uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated); -std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position); -uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& branch, uint32_t position); +uint256 ComputeMerkleRoot(std::vector<uint256> 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<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position); - #endif // BITCOIN_CONSENSUS_MERKLE_H |