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