Page MenuHomePhabricator
Differential D1846 Diff 5318 src/consensus/merkle.cpp

Changeset View

Standalone View

View Options

src/consensus/merkle.cpp

Show All 36 Lines/* WARNING! If you're reading this because you're learning about crypto
valid) versions of the same block. We defend against this by detecting valid) versions of the same block. We defend against this by detecting
the case where we would hash two identical hashes at the end of the list the case where we would hash two identical hashes at the end of the list
together, and treating that identically to the block having an invalid together, and treating that identically to the block having an invalid
merkle root. Assuming no double-SHA256 collisions, this will detect all merkle root. Assuming no double-SHA256 collisions, this will detect all
known ways of changing the transactions without affecting the merkle known ways of changing the transactions without affecting the merkle
root. root.
*/ */
/* This implements a constant-space merkle root/path calculator, limited to 2^32 uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool *mutated) {
* leaves. */ bool mutation = false;
static void MerkleComputation(const std::vector<uint256> &leaves, while (hashes.size() > 1) {
uint256 *proot, bool *pmutated, if (mutated) {
uint32_t branchpos, for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
std::vector<uint256> *pbranch) { if (hashes[pos] == hashes[pos + 1]) mutation = true;
if (pbranch) pbranch->clear(); }
if (leaves.size() == 0) { }
if (pmutated) *pmutated = false; if (hashes.size() & 1) {
if (proot) *proot = uint256(); hashes.push_back(hashes.back());
return; }
} SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
bool mutated = false; hashes.resize(hashes.size() / 2);
// count is the number of leaves processed so far. }
uint32_t count = 0; if (mutated) *mutated = mutation;
// inner is an array of eagerly computed subtree hashes, indexed by tree if (hashes.size() == 0) return uint256();
// level (0 being the leaves). return hashes[0];
// 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(const std::vector<uint256> &leaves, bool *mutated) {
uint256 hash;
MerkleComputation(leaves, &hash, mutated, -1, nullptr);
return hash;
}
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) { uint256 BlockMerkleRoot(const CBlock &block, bool *mutated) {
std::vector<uint256> leaves; std::vector<uint256> leaves;
leaves.resize(block.vtx.size()); leaves.resize(block.vtx.size());
for (size_t s = 0; s < block.vtx.size(); s++) { for (size_t s = 0; s < block.vtx.size(); s++) {
leaves[s] = block.vtx[s]->GetId(); leaves[s] = block.vtx[s]->GetId();
} }
return ComputeMerkleRoot(leaves, 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]->GetId();
}
return ComputeMerkleBranch(leaves, position);
} }