1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
// Copyright (c) 2015-2016 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include "consensus/merkle.h"
#include "test/test_bitcoin.h"
#include <boost/test/unit_test.hpp>
BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
// Older version of the merkle root computation code, for comparison.
static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
{
vMerkleTree.clear();
vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
vMerkleTree.push_back((*it)->GetHash());
int j = 0;
bool mutated = false;
for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
for (int i = 0; i < nSize; i += 2)
{
int i2 = std::min(i+1, nSize-1);
if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
// Two identical hashes at the end of the list at a particular level.
mutated = true;
}
vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(),
vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end()));
}
j += nSize;
}
if (fMutated) {
*fMutated = mutated;
}
return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
}
// Older version of the merkle branch computation code, for comparison.
static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
{
std::vector<uint256> vMerkleBranch;
int j = 0;
for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
int i = std::min(nIndex^1, nSize-1);
vMerkleBranch.push_back(vMerkleTree[j+i]);
nIndex >>= 1;
j += nSize;
}
return vMerkleBranch;
}
static inline int ctz(uint32_t i) {
if (i == 0) return 0;
int j = 0;
while (!(i & 1)) {
j++;
i >>= 1;
}
return j;
}
BOOST_AUTO_TEST_CASE(merkle_test)
{
for (int i = 0; i < 32; i++) {
// Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000);
// Try up to 3 mutations.
for (int mutate = 0; mutate <= 3; mutate++) {
int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
if (duplicate2 >= ntx1) break;
int ntx2 = ntx1 + duplicate2;
int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
if (duplicate3 >= ntx2) break;
int ntx3 = ntx2 + duplicate3;
// Build a block with ntx different transactions.
CBlock block;
block.vtx.resize(ntx);
for (int j = 0; j < ntx; j++) {
CMutableTransaction mtx;
mtx.nLockTime = j;
block.vtx[j] = MakeTransactionRef(std::move(mtx));
}
// Compute the root of the block before mutating it.
bool unmutatedMutated = false;
uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
BOOST_CHECK(unmutatedMutated == false);
// Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
block.vtx.resize(ntx3);
for (int j = 0; j < duplicate1; j++) {
block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
}
for (int j = 0; j < duplicate2; j++) {
block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
}
for (int j = 0; j < duplicate3; j++) {
block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
}
// Compute the merkle root and merkle tree using the old mechanism.
bool oldMutated = false;
std::vector<uint256> merkleTree;
uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
// Compute the merkle root using the new mechanism.
bool newMutated = false;
uint256 newRoot = BlockMerkleRoot(block, &newMutated);
BOOST_CHECK(oldRoot == newRoot);
BOOST_CHECK(newRoot == unmutatedRoot);
BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
BOOST_CHECK(oldMutated == newMutated);
BOOST_CHECK(newMutated == !!mutate);
// If no mutation was done (once for every ntx value), try up to 16 branches.
if (mutate == 0) {
for (int loop = 0; loop < std::min(ntx, 16); loop++) {
// If ntx <= 16, try all branches. Otherwise, try 16 random ones.
int mtx = loop;
if (ntx > 16) {
mtx = insecure_rand() % ntx;
}
std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
BOOST_CHECK(oldBranch == newBranch);
BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
}
}
}
}
}
BOOST_AUTO_TEST_SUITE_END()
|
