Page MenuHomePhabricator
Differential D5120 Diff 15929 src/test/merkle_tests.cpp

Changeset View

Standalone View

View Options

src/test/merkle_tests.cpp

Show All 31 Lines
/** /**
* This implements a constant-space merkle root/path calculator, limited to 2^32 * This implements a constant-space merkle root/path calculator, limited to 2^32
* leaves. * leaves.
*/ */
static void MerkleComputation(const std::vector<uint256> &leaves, static void MerkleComputation(const std::vector<uint256> &leaves,
uint256 *proot, bool *pmutated, uint256 *proot, bool *pmutated,
uint32_t branchpos, uint32_t branchpos,
std::vector<uint256> *pbranch) { std::vector<uint256> *pbranch) {
if (pbranch) pbranch->clear(); if (pbranch) {
pbranch->clear();
}
if (leaves.size() == 0) { if (leaves.size() == 0) {
if (pmutated) *pmutated = false; if (pmutated) {
if (proot) *proot = uint256(); *pmutated = false;
}
if (proot) {
*proot = uint256();
}
return; return;
} }
bool mutated = false; bool mutated = false;
// count is the number of leaves processed so far. // count is the number of leaves processed so far.
uint32_t count = 0; uint32_t count = 0;
// inner is an array of eagerly computed subtree hashes, indexed by tree // inner is an array of eagerly computed subtree hashes, indexed by tree
// level (0 being the leaves). // level (0 being the leaves).
// For example, when count is 25 (11001 in binary), inner[4] is the hash of // For example, when count is 25 (11001 in binary), inner[4] is the hash of
▲ Show 20 Lines • Show All 71 Lines • ▼ Show 20 Lines while (count != (((uint32_t)1) << level)) {
CHash256() CHash256()
.Write(inner[level].begin(), 32) .Write(inner[level].begin(), 32)
.Write(h.begin(), 32) .Write(h.begin(), 32)
.Finalize(h.begin()); .Finalize(h.begin());
level++; level++;
} }
} }
// Return result. // Return result.
if (pmutated) *pmutated = mutated; if (pmutated) {
if (proot) *proot = h; *pmutated = mutated;
}
if (proot) {
*proot = h;
}
} }
static std::vector<uint256> static std::vector<uint256>
ComputeMerkleBranch(const std::vector<uint256> &leaves, uint32_t position) { ComputeMerkleBranch(const std::vector<uint256> &leaves, uint32_t position) {
std::vector<uint256> ret; std::vector<uint256> ret;
MerkleComputation(leaves, nullptr, nullptr, position, &ret); MerkleComputation(leaves, nullptr, nullptr, position, &ret);
return ret; return ret;
} }
Show All 10 Lines
// 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) {
vMerkleTree.push_back((*it)->GetId()); vMerkleTree.push_back((*it)->GetId());
}
int j = 0; int j = 0;
bool mutated = false; bool mutated = false;
for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) { for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) {
for (int i = 0; i < nSize; i += 2) { for (int i = 0; i < nSize; i += 2) {
int i2 = std::min(i + 1, nSize - 1); int i2 = std::min(i + 1, nSize - 1);
if (i2 == i + 1 && i2 + 1 == nSize && if (i2 == i + 1 && i2 + 1 == nSize &&
vMerkleTree[j + i] == vMerkleTree[j + i2]) { vMerkleTree[j + i] == vMerkleTree[j + i2]) {
// Two identical hashes at the end of the list at a particular // Two identical hashes at the end of the list at a particular
Show All 23 Lines for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) {
vMerkleBranch.push_back(vMerkleTree[j + i]); vMerkleBranch.push_back(vMerkleTree[j + i]);
nIndex >>= 1; nIndex >>= 1;
j += nSize; j += nSize;
} }
return vMerkleBranch; return vMerkleBranch;
} }
static inline int ctz(uint32_t i) { static inline int ctz(uint32_t i) {
if (i == 0) return 0; if (i == 0) {
return 0;
}
int j = 0; int j = 0;
while (!(i & 1)) { while (!(i & 1)) {
j++; j++;
i >>= 1; i >>= 1;
} }
return j; return j;
} }
Show All 11 Lines for (int i = 0; i < 32; i++) {
// (it adds a level). // (it adds a level).
break; break;
} }
// The resulting number of transactions after the first duplication. // The resulting number of transactions after the first duplication.
int ntx1 = ntx + duplicate1; int ntx1 = ntx + duplicate1;
// Likewise for the second mutation. // Likewise for the second mutation.
int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0;
if (duplicate2 >= ntx1) break; if (duplicate2 >= ntx1) {
break;
}
int ntx2 = ntx1 + duplicate2; int ntx2 = ntx1 + duplicate2;
// And for the third mutation. // And for the third mutation.
int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0;
if (duplicate3 >= ntx2) break; if (duplicate3 >= ntx2) {
break;
}
int ntx3 = ntx2 + duplicate3; int ntx3 = ntx2 + duplicate3;
// Build a block with ntx different transactions. // Build a block with ntx different transactions.
CBlock block; CBlock block;
block.vtx.resize(ntx); block.vtx.resize(ntx);
for (int j = 0; j < ntx; j++) { for (int j = 0; j < ntx; j++) {
CMutableTransaction mtx; CMutableTransaction mtx;
mtx.nLockTime = j; mtx.nLockTime = j;
block.vtx[j] = MakeTransactionRef(std::move(mtx)); block.vtx[j] = MakeTransactionRef(std::move(mtx));
▲ Show 20 Lines • Show All 55 Lines • Show Last 20 Lines