aboutsummaryrefslogtreecommitdiff
path: root/src/test/merkle_tests.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/test/merkle_tests.cpp')
-rw-r--r--src/test/merkle_tests.cpp117
1 files changed, 117 insertions, 0 deletions
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<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;
+}
+
+/* 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;
+}
+
+static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
+ std::vector<uint256> ret;
+ MerkleComputation(leaves, nullptr, nullptr, position, &ret);
+ return ret;
+}
+
+static 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);
+}
+
// Older version of the merkle root computation code, for comparison.
static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
{