Branch data Line data Source code
1 : : // Copyright (c) 2015-2020 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/random.h>
7 : : #include <test/util/setup_common.h>
8 : :
9 : : #include <boost/test/unit_test.hpp>
10 : :
11 : : BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
12 : :
13 : 376 : static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
14 : 376 : uint256 hash = leaf;
15 [ + + ]: 3462 : for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
16 [ + + ]: 3086 : if (nIndex & 1) {
17 : 1416 : hash = Hash(*it, hash);
18 : : } else {
19 : 1670 : hash = Hash(hash, *it);
20 : : }
21 : 3086 : nIndex >>= 1;
22 : : }
23 : 376 : return hash;
24 : : }
25 : :
26 : : /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
27 : 376 : static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
28 [ + - - + ]: 376 : if (pbranch) pbranch->clear();
29 [ - + ]: 376 : if (leaves.size() == 0) {
30 [ # # ]: 0 : if (pmutated) *pmutated = false;
31 [ # # ]: 0 : if (proot) *proot = uint256();
32 : 0 : return;
33 : : }
34 : 376 : bool mutated = false;
35 : : // count is the number of leaves processed so far.
36 : 376 : uint32_t count = 0;
37 : : // inner is an array of eagerly computed subtree hashes, indexed by tree
38 : : // level (0 being the leaves).
39 : : // For example, when count is 25 (11001 in binary), inner[4] is the hash of
40 : : // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
41 : : // the last leaf. The other inner entries are undefined.
42 : 376 : uint256 inner[32];
43 : : // Which position in inner is a hash that depends on the matching leaf.
44 : 376 : int matchlevel = -1;
45 : : // First process all leaves into 'inner' values.
46 [ + + ]: 454688 : while (count < leaves.size()) {
47 : 454312 : uint256 h = leaves[count];
48 : 454312 : bool matchh = count == branchpos;
49 : 454312 : count++;
50 : 454312 : int level;
51 : : // For each of the lower bits in count that are 0, do 1 step. Each
52 : : // corresponds to an inner value that existed before processing the
53 : : // current leaf, and each needs a hash to combine it.
54 [ + + ]: 906884 : for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
55 [ + - ]: 452572 : if (pbranch) {
56 [ + + ]: 452572 : if (matchh) {
57 : 1253 : pbranch->push_back(inner[level]);
58 [ + + ]: 451319 : } else if (matchlevel == level) {
59 : 1288 : pbranch->push_back(h);
60 : 1288 : matchh = true;
61 : : }
62 : : }
63 : 452572 : mutated |= (inner[level] == h);
64 : 452572 : h = Hash(inner[level], h);
65 : : }
66 : : // Store the resulting hash at inner position level.
67 : 454312 : inner[level] = h;
68 [ + + ]: 454312 : if (matchh) {
69 : 1664 : matchlevel = level;
70 : : }
71 : : }
72 : : // Do a final 'sweep' over the rightmost branch of the tree to process
73 : : // odd levels, and reduce everything to a single top value.
74 : : // Level is the level (counted from the bottom) up to which we've sweeped.
75 : : int level = 0;
76 : : // As long as bit number level in count is zero, skip it. It means there
77 : : // is nothing left at this level.
78 [ + + ]: 720 : while (!(count & ((uint32_t{1}) << level))) {
79 : 344 : level++;
80 : : }
81 : 376 : uint256 h = inner[level];
82 : 376 : bool matchh = matchlevel == level;
83 [ + + ]: 1754 : while (count != ((uint32_t{1}) << level)) {
84 : : // If we reach this point, h is an inner value that is not the top.
85 : : // We combine it with itself (Bitcoin's special rule for odd levels in
86 : : // the tree) to produce a higher level one.
87 [ + + ]: 1378 : if (pbranch && matchh) {
88 : 54 : pbranch->push_back(h);
89 : : }
90 : 1378 : h = Hash(h, h);
91 : : // Increment count to the value it would have if two entries at this
92 : : // level had existed.
93 : 1378 : count += ((uint32_t{1}) << level);
94 : 1378 : level++;
95 : : // And propagate the result upwards accordingly.
96 [ + + ]: 2742 : while (!(count & ((uint32_t{1}) << level))) {
97 [ + - ]: 1364 : if (pbranch) {
98 [ + + ]: 1364 : if (matchh) {
99 : 163 : pbranch->push_back(inner[level]);
100 [ + + ]: 1201 : } else if (matchlevel == level) {
101 : 328 : pbranch->push_back(h);
102 : 328 : matchh = true;
103 : : }
104 : : }
105 : 1364 : h = Hash(inner[level], h);
106 : 1364 : level++;
107 : : }
108 : : }
109 : : // Return result.
110 [ - + ]: 376 : if (pmutated) *pmutated = mutated;
111 [ - + ]: 376 : if (proot) *proot = h;
112 : : }
113 : :
114 : 376 : static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
115 : 376 : std::vector<uint256> ret;
116 [ + - ]: 376 : MerkleComputation(leaves, nullptr, nullptr, position, &ret);
117 : 376 : return ret;
118 : 0 : }
119 : :
120 : 376 : static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
121 : : {
122 : 376 : std::vector<uint256> leaves;
123 [ + - ]: 376 : leaves.resize(block.vtx.size());
124 [ + + ]: 454688 : for (size_t s = 0; s < block.vtx.size(); s++) {
125 : 454312 : leaves[s] = block.vtx[s]->GetHash();
126 : : }
127 [ + - ]: 376 : return ComputeMerkleBranch(leaves, position);
128 : 376 : }
129 : :
130 : : // Older version of the merkle root computation code, for comparison.
131 : 92 : static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
132 : : {
133 [ - + ]: 92 : vMerkleTree.clear();
134 : 92 : vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
135 [ + + ]: 114445 : for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
136 : 114353 : vMerkleTree.push_back((*it)->GetHash());
137 : 92 : int j = 0;
138 : 92 : bool mutated = false;
139 [ + + ]: 843 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
140 : : {
141 [ + + ]: 115251 : for (int i = 0; i < nSize; i += 2)
142 : : {
143 [ + + ]: 114500 : int i2 = std::min(i+1, nSize-1);
144 [ + + + + : 114500 : if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
+ + ]
145 : : // Two identical hashes at the end of the list at a particular level.
146 : : mutated = true;
147 : : }
148 : 114500 : vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
149 : : }
150 : 751 : j += nSize;
151 : : }
152 [ + - ]: 92 : if (fMutated) {
153 : 92 : *fMutated = mutated;
154 : : }
155 [ - + ]: 92 : return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
156 : : }
157 : :
158 : : // Older version of the merkle branch computation code, for comparison.
159 : 376 : static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
160 : : {
161 : 376 : std::vector<uint256> vMerkleBranch;
162 : 376 : int j = 0;
163 [ + + ]: 3462 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
164 : : {
165 [ + + ]: 3086 : int i = std::min(nIndex^1, nSize-1);
166 [ + - ]: 3086 : vMerkleBranch.push_back(vMerkleTree[j+i]);
167 : 3086 : nIndex >>= 1;
168 : 3086 : j += nSize;
169 : : }
170 : 376 : return vMerkleBranch;
171 : 0 : }
172 : :
173 : 143 : static inline int ctz(uint32_t i) {
174 : 143 : if (i == 0) return 0;
175 : : int j = 0;
176 [ + + + + : 384 : while (!(i & 1)) {
+ + ]
177 : 241 : j++;
178 : 241 : i >>= 1;
179 : : }
180 : : return j;
181 : : }
182 : :
183 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
184 : : {
185 [ + + ]: 33 : for (int i = 0; i < 32; i++) {
186 : : // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
187 [ + + ]: 47 : int ntx = (i <= 16) ? i : 17 + (InsecureRandRange(4000));
188 : : // Try up to 3 mutations.
189 [ + + ]: 124 : for (int mutate = 0; mutate <= 3; mutate++) {
190 [ + + + - ]: 186 : int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
191 [ + + ]: 109 : if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
192 : 103 : int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
193 [ + + + - ]: 149 : int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
194 [ + + ]: 103 : if (duplicate2 >= ntx1) break;
195 : 97 : int ntx2 = ntx1 + duplicate2;
196 [ + + + - ]: 149 : int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
197 [ + + ]: 97 : if (duplicate3 >= ntx2) break;
198 : 92 : int ntx3 = ntx2 + duplicate3;
199 : : // Build a block with ntx different transactions.
200 : 92 : CBlock block;
201 [ + - ]: 92 : block.vtx.resize(ntx);
202 [ + + ]: 113350 : for (int j = 0; j < ntx; j++) {
203 [ + - ]: 113258 : CMutableTransaction mtx;
204 : 113258 : mtx.nLockTime = j;
205 [ + - - + ]: 226516 : block.vtx[j] = MakeTransactionRef(std::move(mtx));
206 : 113258 : }
207 : : // Compute the root of the block before mutating it.
208 : 92 : bool unmutatedMutated = false;
209 [ + - ]: 92 : uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
210 [ + - + - : 184 : BOOST_CHECK(unmutatedMutated == false);
+ - ]
211 : : // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
212 [ + - ]: 92 : block.vtx.resize(ntx3);
213 [ + + ]: 367 : for (int j = 0; j < duplicate1; j++) {
214 : 275 : block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
215 : : }
216 [ + + ]: 488 : for (int j = 0; j < duplicate2; j++) {
217 : 396 : block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
218 : : }
219 [ + + ]: 516 : for (int j = 0; j < duplicate3; j++) {
220 : 424 : block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
221 : : }
222 : : // Compute the merkle root and merkle tree using the old mechanism.
223 : 92 : bool oldMutated = false;
224 : 92 : std::vector<uint256> merkleTree;
225 [ + - ]: 92 : uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
226 : : // Compute the merkle root using the new mechanism.
227 : 92 : bool newMutated = false;
228 [ + - ]: 92 : uint256 newRoot = BlockMerkleRoot(block, &newMutated);
229 [ + - + - : 184 : BOOST_CHECK(oldRoot == newRoot);
+ - ]
230 [ + - + - : 184 : BOOST_CHECK(newRoot == unmutatedRoot);
+ - ]
231 [ + - + - : 184 : BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
+ - ]
232 [ + - + - : 184 : BOOST_CHECK(oldMutated == newMutated);
+ - ]
233 [ + - + - : 184 : BOOST_CHECK(newMutated == !!mutate);
+ + ]
234 : : // If no mutation was done (once for every ntx value), try up to 16 branches.
235 [ + + ]: 92 : if (mutate == 0) {
236 [ + + + + ]: 559 : for (int loop = 0; loop < std::min(ntx, 16); loop++) {
237 : : // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
238 : 376 : int mtx = loop;
239 [ + + ]: 376 : if (ntx > 16) {
240 : 240 : mtx = InsecureRandRange(ntx);
241 : : }
242 [ + - ]: 376 : std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
243 [ + - ]: 376 : std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
244 [ + - + - : 752 : BOOST_CHECK(oldBranch == newBranch);
+ - ]
245 [ + - + - : 752 : BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
+ - ]
246 : 376 : }
247 : : }
248 : 92 : }
249 : : }
250 : 1 : }
251 : :
252 : :
253 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
254 : : {
255 : 1 : bool mutated = false;
256 : 1 : CBlock block;
257 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block, &mutated);
258 : :
259 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(root.IsNull(), true);
260 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
261 : 1 : }
262 : :
263 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
264 : : {
265 : 1 : bool mutated = false;
266 : 1 : CBlock block;
267 : :
268 [ + - ]: 1 : block.vtx.resize(1);
269 [ + - ]: 1 : CMutableTransaction mtx;
270 : 1 : mtx.nLockTime = 0;
271 [ + - - + ]: 2 : block.vtx[0] = MakeTransactionRef(std::move(mtx));
272 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block, &mutated);
273 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash());
274 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
275 : 1 : }
276 : :
277 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
278 : : {
279 : 1 : bool mutated;
280 : 1 : CBlock block, blockWithRepeatedLastTx;
281 : :
282 [ + - ]: 1 : block.vtx.resize(3);
283 : :
284 [ + + ]: 4 : for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
285 [ + - ]: 3 : CMutableTransaction mtx;
286 : 3 : mtx.nLockTime = pos;
287 [ + - - + ]: 6 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
288 : 3 : }
289 : :
290 [ + - ]: 1 : blockWithRepeatedLastTx = block;
291 [ + - ]: 1 : blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
292 : :
293 [ + - ]: 1 : uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
294 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
295 : :
296 [ + - ]: 1 : uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
297 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
298 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, true);
299 : 1 : }
300 : :
301 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
302 : : {
303 : 1 : CBlock block, leftSubtreeBlock, rightSubtreeBlock;
304 : :
305 [ + - ]: 1 : block.vtx.resize(4);
306 : : std::size_t pos;
307 [ + + ]: 5 : for (pos = 0; pos < block.vtx.size(); pos++) {
308 [ + - ]: 4 : CMutableTransaction mtx;
309 : 4 : mtx.nLockTime = pos;
310 [ + - - + ]: 8 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
311 : 4 : }
312 : :
313 [ + + ]: 3 : for (pos = 0; pos < block.vtx.size() / 2; pos++)
314 [ + - ]: 2 : leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
315 : :
316 [ + + ]: 3 : for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
317 [ + - ]: 2 : rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
318 : :
319 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block);
320 [ + - ]: 1 : uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
321 [ + - ]: 1 : uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
322 : 1 : std::vector<uint256> leftRight;
323 [ + - ]: 1 : leftRight.push_back(rootOfLeftSubtree);
324 [ + - ]: 1 : leftRight.push_back(rootOfRightSubtree);
325 [ + - + - ]: 1 : uint256 rootOfLR = ComputeMerkleRoot(leftRight);
326 : :
327 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(root, rootOfLR);
328 : 1 : }
329 : :
330 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
331 : : {
332 : 1 : CBlock block;
333 : :
334 [ + - ]: 1 : block.vtx.resize(2);
335 [ + + ]: 3 : for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
336 [ + - ]: 2 : CMutableTransaction mtx;
337 : 2 : mtx.nLockTime = pos;
338 [ + - - + ]: 4 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
339 : 2 : }
340 : :
341 [ + - ]: 1 : uint256 blockWitness = BlockWitnessMerkleRoot(block);
342 : :
343 : 1 : std::vector<uint256> hashes;
344 [ + - ]: 1 : hashes.resize(block.vtx.size());
345 : 1 : hashes[0].SetNull();
346 [ + - ]: 1 : hashes[1] = block.vtx[1]->GetHash();
347 : :
348 [ + - + - ]: 1 : uint256 merkleRootofHashes = ComputeMerkleRoot(hashes);
349 : :
350 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness);
351 : 1 : }
352 : : BOOST_AUTO_TEST_SUITE_END()
|
