merkle_tests.cpp raw
1 // Copyright (c) 2015-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <consensus/merkle.h>
6 #include <test/util/common.h>
7 #include <test/util/random.h>
8 #include <test/util/setup_common.h>
9
10 #include <boost/test/unit_test.hpp>
11
12 BOOST_FIXTURE_TEST_SUITE(merkle_tests, BasicTestingSetup)
13
14 static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
15 uint256 hash = leaf;
16 for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
17 if (nIndex & 1) {
18 hash = Hash(*it, hash);
19 } else {
20 hash = Hash(hash, *it);
21 }
22 nIndex >>= 1;
23 }
24 return hash;
25 }
26
27 // Older version of the merkle root computation code, for comparison.
28 static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
29 {
30 vMerkleTree.clear();
31 vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
32 for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
33 vMerkleTree.push_back((*it)->GetHash().ToUint256());
34 int j = 0;
35 bool mutated = false;
36 for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
37 {
38 for (int i = 0; i < nSize; i += 2)
39 {
40 int i2 = std::min(i+1, nSize-1);
41 if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
42 // Two identical hashes at the end of the list at a particular level.
43 mutated = true;
44 }
45 vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
46 }
47 j += nSize;
48 }
49 if (fMutated) {
50 *fMutated = mutated;
51 }
52 return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
53 }
54
55 // Older version of the merkle branch computation code, for comparison.
56 static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
57 {
58 std::vector<uint256> vMerkleBranch;
59 int j = 0;
60 for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
61 {
62 int i = std::min(nIndex^1, nSize-1);
63 vMerkleBranch.push_back(vMerkleTree[j+i]);
64 nIndex >>= 1;
65 j += nSize;
66 }
67 return vMerkleBranch;
68 }
69
70 static inline int ctz(uint32_t i) {
71 if (i == 0) return 0;
72 int j = 0;
73 while (!(i & 1)) {
74 j++;
75 i >>= 1;
76 }
77 return j;
78 }
79
80 BOOST_AUTO_TEST_CASE(merkle_test)
81 {
82 for (int i = 0; i < 32; i++) {
83 // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
84 int ntx = (i <= 16) ? i : 17 + (m_rng.randrange(4000));
85 // Try up to 3 mutations.
86 for (int mutate = 0; mutate <= 3; mutate++) {
87 int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
88 if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
89 int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
90 int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
91 if (duplicate2 >= ntx1) break;
92 int ntx2 = ntx1 + duplicate2;
93 int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
94 if (duplicate3 >= ntx2) break;
95 int ntx3 = ntx2 + duplicate3;
96 // Build a block with ntx different transactions.
97 CBlock block;
98 block.vtx.resize(ntx);
99 for (int j = 0; j < ntx; j++) {
100 CMutableTransaction mtx;
101 mtx.nLockTime = j;
102 block.vtx[j] = MakeTransactionRef(std::move(mtx));
103 }
104 // Compute the root of the block before mutating it.
105 bool unmutatedMutated = false;
106 uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
107 BOOST_CHECK(unmutatedMutated == false);
108 // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
109 block.vtx.resize(ntx3);
110 for (int j = 0; j < duplicate1; j++) {
111 block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
112 }
113 for (int j = 0; j < duplicate2; j++) {
114 block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
115 }
116 for (int j = 0; j < duplicate3; j++) {
117 block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
118 }
119 // Compute the merkle root and merkle tree using the old mechanism.
120 bool oldMutated = false;
121 std::vector<uint256> merkleTree;
122 uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
123 // Compute the merkle root using the new mechanism.
124 bool newMutated = false;
125 uint256 newRoot = BlockMerkleRoot(block, &newMutated);
126 BOOST_CHECK(oldRoot == newRoot);
127 BOOST_CHECK(newRoot == unmutatedRoot);
128 BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
129 BOOST_CHECK(oldMutated == newMutated);
130 BOOST_CHECK(newMutated == !!mutate);
131 // If no mutation was done (once for every ntx value), try up to 16 branches.
132 if (mutate == 0) {
133 for (int loop = 0; loop < std::min(ntx, 16); loop++) {
134 // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
135 int mtx = loop;
136 if (ntx > 16) {
137 mtx = m_rng.randrange(ntx);
138 }
139 std::vector<uint256> newBranch = TransactionMerklePath(block, mtx);
140 std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
141 BOOST_CHECK(oldBranch == newBranch);
142 BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash().ToUint256(), newBranch, mtx) == oldRoot);
143 }
144 }
145 }
146 }
147 }
148
149
150 BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
151 {
152 bool mutated = false;
153 CBlock block;
154 uint256 root = BlockMerkleRoot(block, &mutated);
155
156 BOOST_CHECK_EQUAL(root.IsNull(), true);
157 BOOST_CHECK_EQUAL(mutated, false);
158
159 // Verify TransactionMerklePath handles empty block correctly
160 // This tests the early-return path in MerkleComputation
161 std::vector<uint256> merkle_path = TransactionMerklePath(block, 0);
162 BOOST_CHECK(merkle_path.empty());
163 }
164
165 BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
166 {
167 bool mutated = false;
168 CBlock block;
169
170 block.vtx.resize(1);
171 CMutableTransaction mtx;
172 mtx.nLockTime = 0;
173 block.vtx[0] = MakeTransactionRef(std::move(mtx));
174 uint256 root = BlockMerkleRoot(block, &mutated);
175 BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash().ToUint256());
176 BOOST_CHECK_EQUAL(mutated, false);
177 }
178
179 BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
180 {
181 bool mutated;
182 CBlock block, blockWithRepeatedLastTx;
183
184 block.vtx.resize(3);
185
186 for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
187 CMutableTransaction mtx;
188 mtx.nLockTime = pos;
189 block.vtx[pos] = MakeTransactionRef(std::move(mtx));
190 }
191
192 blockWithRepeatedLastTx = block;
193 blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
194
195 uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
196 BOOST_CHECK_EQUAL(mutated, false);
197
198 uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
199 BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
200 BOOST_CHECK_EQUAL(mutated, true);
201 }
202
203 BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
204 {
205 CBlock block, leftSubtreeBlock, rightSubtreeBlock;
206
207 block.vtx.resize(4);
208 std::size_t pos;
209 for (pos = 0; pos < block.vtx.size(); pos++) {
210 CMutableTransaction mtx;
211 mtx.nLockTime = pos;
212 block.vtx[pos] = MakeTransactionRef(std::move(mtx));
213 }
214
215 for (pos = 0; pos < block.vtx.size() / 2; pos++)
216 leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
217
218 for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
219 rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
220
221 uint256 root = BlockMerkleRoot(block);
222 uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
223 uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
224 std::vector<uint256> leftRight;
225 leftRight.push_back(rootOfLeftSubtree);
226 leftRight.push_back(rootOfRightSubtree);
227 uint256 rootOfLR = ComputeMerkleRoot(leftRight);
228
229 BOOST_CHECK_EQUAL(root, rootOfLR);
230 }
231
232 BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness)
233 {
234 CBlock block;
235
236 constexpr size_t vtx_count{3};
237 block.vtx.resize(vtx_count);
238 for (std::size_t pos = 0; pos < vtx_count; pos++) {
239 CMutableTransaction mtx;
240 mtx.nLockTime = pos;
241 block.vtx[pos] = MakeTransactionRef(std::move(mtx));
242 }
243
244 uint256 blockWitness = BlockWitnessMerkleRoot(block);
245
246 std::vector<uint256> hashes;
247 hashes.resize(vtx_count); // Odd count exercises leaf duplication in ComputeMerkleRoot (which can append one extra hash).
248 hashes[0] = uint256::ZERO; // The witness hash of the coinbase is 0.
249 for (size_t pos{1}; pos < vtx_count; ++pos) {
250 hashes[pos] = block.vtx[pos]->GetWitnessHash().ToUint256();
251 }
252
253 uint256 merkleRootofHashes = ComputeMerkleRoot(hashes);
254 BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness);
255 }
256 BOOST_AUTO_TEST_SUITE_END()
257