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