Changeset View
Changeset View
Standalone View
Standalone View
src/test/merkle_tests.cpp
// Copyright (c) 2015-2016 The Bitcoin Core developers | // Copyright (c) 2015-2016 The Bitcoin Core developers | ||||
// Distributed under the MIT software license, see the accompanying | // Distributed under the MIT software license, see the accompanying | ||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | // file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
#include "consensus/merkle.h" | #include "consensus/merkle.h" | ||||
#include "test/test_bitcoin.h" | #include "test/test_bitcoin.h" | ||||
#include <boost/test/unit_test.hpp> | #include <boost/test/unit_test.hpp> | ||||
BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup) | 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. | // Older version of the merkle root computation code, for comparison. | ||||
static uint256 BlockBuildMerkleTree(const CBlock &block, bool *fMutated, | static uint256 BlockBuildMerkleTree(const CBlock &block, bool *fMutated, | ||||
std::vector<uint256> &vMerkleTree) { | std::vector<uint256> &vMerkleTree) { | ||||
vMerkleTree.clear(); | vMerkleTree.clear(); | ||||
// Safe upper bound for the number of total nodes. | // Safe upper bound for the number of total nodes. | ||||
vMerkleTree.reserve(block.vtx.size() * 2 + 16); | vMerkleTree.reserve(block.vtx.size() * 2 + 16); | ||||
for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); | for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); | ||||
it != block.vtx.end(); ++it) | it != block.vtx.end(); ++it) | ||||
▲ Show 20 Lines • Show All 136 Lines • Show Last 20 Lines |