Branch data Line data Source code
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 : 376 : static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
15 : 376 : uint256 hash = leaf;
16 [ + + ]: 3494 : for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
17 [ + + ]: 3118 : if (nIndex & 1) {
18 : 1400 : hash = Hash(*it, hash);
19 : : } else {
20 : 1718 : hash = Hash(hash, *it);
21 : : }
22 : 3118 : nIndex >>= 1;
23 : : }
24 : 376 : return hash;
25 : : }
26 : :
27 : : // Older version of the merkle root computation code, for comparison.
28 : 90 : static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
29 : : {
30 [ - + ]: 90 : vMerkleTree.clear();
31 [ - + ]: 90 : vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
32 [ + + ]: 117708 : for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
33 : 117618 : vMerkleTree.push_back((*it)->GetHash().ToUint256());
34 : 90 : int j = 0;
35 : 90 : bool mutated = false;
36 [ - + + + ]: 832 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
37 : : {
38 [ + + ]: 118500 : for (int i = 0; i < nSize; i += 2)
39 : : {
40 [ + + ]: 117758 : int i2 = std::min(i+1, nSize-1);
41 [ + + + + : 117758 : 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 : 117758 : vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
46 : : }
47 : 742 : j += nSize;
48 : : }
49 [ + - ]: 90 : if (fMutated) {
50 : 90 : *fMutated = mutated;
51 : : }
52 [ - + ]: 90 : return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
53 : : }
54 : :
55 : : // Older version of the merkle branch computation code, for comparison.
56 : 376 : static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
57 : : {
58 : 376 : std::vector<uint256> vMerkleBranch;
59 : 376 : int j = 0;
60 [ - + + + ]: 3494 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
61 : : {
62 [ + + ]: 3118 : int i = std::min(nIndex^1, nSize-1);
63 [ + - ]: 3118 : vMerkleBranch.push_back(vMerkleTree[j+i]);
64 : 3118 : nIndex >>= 1;
65 : 3118 : j += nSize;
66 : : }
67 : 376 : return vMerkleBranch;
68 : 0 : }
69 : :
70 : 140 : static inline int ctz(uint32_t i) {
71 : 140 : if (i == 0) return 0;
72 : : int j = 0;
73 [ + + + + : 438 : while (!(i & 1)) {
+ + ]
74 : 298 : j++;
75 : 298 : i >>= 1;
76 : : }
77 : : return j;
78 : : }
79 : :
80 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
81 : : {
82 [ + + ]: 33 : 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 [ + + ]: 32 : int ntx = (i <= 16) ? i : 17 + (m_rng.randrange(4000));
85 : : // Try up to 3 mutations.
86 [ + + ]: 122 : for (int mutate = 0; mutate <= 3; mutate++) {
87 [ + + + - ]: 184 : int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
88 [ + + ]: 108 : if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
89 : 102 : int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
90 [ + + + - ]: 147 : int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
91 [ + + ]: 102 : if (duplicate2 >= ntx1) break;
92 : 95 : int ntx2 = ntx1 + duplicate2;
93 [ + + + - ]: 146 : int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
94 [ + + ]: 95 : if (duplicate3 >= ntx2) break;
95 : 90 : int ntx3 = ntx2 + duplicate3;
96 : : // Build a block with ntx different transactions.
97 : 90 : CBlock block;
98 [ + - ]: 90 : block.vtx.resize(ntx);
99 [ + + ]: 116432 : for (int j = 0; j < ntx; j++) {
100 [ + - ]: 116342 : CMutableTransaction mtx;
101 : 116342 : mtx.nLockTime = j;
102 [ + - - + ]: 232684 : block.vtx[j] = MakeTransactionRef(std::move(mtx));
103 : 116342 : }
104 : : // Compute the root of the block before mutating it.
105 : 90 : bool unmutatedMutated = false;
106 [ + - ]: 90 : uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
107 [ + - + - : 180 : BOOST_CHECK(unmutatedMutated == false);
+ - ]
108 : : // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
109 [ + - ]: 90 : block.vtx.resize(ntx3);
110 [ + + ]: 286 : for (int j = 0; j < duplicate1; j++) {
111 : 196 : block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
112 : : }
113 [ + + ]: 518 : for (int j = 0; j < duplicate2; j++) {
114 : 428 : block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
115 : : }
116 [ + + ]: 742 : for (int j = 0; j < duplicate3; j++) {
117 : 652 : block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
118 : : }
119 : : // Compute the merkle root and merkle tree using the old mechanism.
120 : 90 : bool oldMutated = false;
121 : 90 : std::vector<uint256> merkleTree;
122 [ + - ]: 90 : uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
123 : : // Compute the merkle root using the new mechanism.
124 : 90 : bool newMutated = false;
125 [ + - ]: 90 : uint256 newRoot = BlockMerkleRoot(block, &newMutated);
126 [ + - - + : 180 : BOOST_CHECK(oldRoot == newRoot);
+ - + - ]
127 [ + - - + : 180 : BOOST_CHECK(newRoot == unmutatedRoot);
+ - + - ]
128 [ + - + - : 270 : BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
+ - + - ]
129 [ + - + - : 180 : BOOST_CHECK(oldMutated == newMutated);
+ - ]
130 [ + - + - : 180 : BOOST_CHECK(newMutated == !!mutate);
+ + ]
131 : : // If no mutation was done (once for every ntx value), try up to 16 branches.
132 [ + + ]: 90 : if (mutate == 0) {
133 [ + + + + ]: 559 : for (int loop = 0; loop < std::min(ntx, 16); loop++) {
134 : : // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
135 : 376 : int mtx = loop;
136 [ + + ]: 376 : if (ntx > 16) {
137 : 240 : mtx = m_rng.randrange(ntx);
138 : : }
139 [ + - ]: 376 : std::vector<uint256> newBranch = TransactionMerklePath(block, mtx);
140 [ + - ]: 376 : std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
141 [ + - + - : 752 : BOOST_CHECK(oldBranch == newBranch);
+ - ]
142 [ + - + - : 1128 : BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash().ToUint256(), newBranch, mtx) == oldRoot);
+ - ]
143 : 376 : }
144 : : }
145 : 90 : }
146 : : }
147 : 1 : }
148 : :
149 : :
150 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
151 : : {
152 : 1 : bool mutated = false;
153 : 1 : CBlock block;
154 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block, &mutated);
155 : :
156 [ + - + - ]: 2 : BOOST_CHECK_EQUAL(root.IsNull(), true);
157 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
158 : :
159 : : // Verify TransactionMerklePath handles empty block correctly
160 : : // This tests the early-return path in MerkleComputation
161 [ + - ]: 1 : std::vector<uint256> merkle_path = TransactionMerklePath(block, 0);
162 [ + - + - ]: 2 : BOOST_CHECK(merkle_path.empty());
163 : 1 : }
164 : :
165 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
166 : : {
167 : 1 : bool mutated = false;
168 : 1 : CBlock block;
169 : :
170 [ + - ]: 1 : block.vtx.resize(1);
171 [ + - ]: 1 : CMutableTransaction mtx;
172 : 1 : mtx.nLockTime = 0;
173 [ + - - + ]: 2 : block.vtx[0] = MakeTransactionRef(std::move(mtx));
174 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block, &mutated);
175 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash().ToUint256());
176 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
177 : 1 : }
178 : :
179 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
180 : : {
181 : 1 : bool mutated;
182 : 1 : CBlock block, blockWithRepeatedLastTx;
183 : :
184 [ + - ]: 1 : block.vtx.resize(3);
185 : :
186 [ - + + + ]: 4 : for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
187 [ + - ]: 3 : CMutableTransaction mtx;
188 : 3 : mtx.nLockTime = pos;
189 [ + - - + ]: 6 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
190 : 3 : }
191 : :
192 [ + - ]: 1 : blockWithRepeatedLastTx = block;
193 [ + - ]: 1 : blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
194 : :
195 [ + - ]: 1 : uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
196 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, false);
197 : :
198 [ + - ]: 1 : uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
199 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
200 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(mutated, true);
201 : 1 : }
202 : :
203 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_mutated_return_value)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
204 : : {
205 : : // CVE-2012-2459 construction: [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] produce the same root.
206 : 1 : const std::vector leaves{uint256{1}, uint256{2}, uint256{3}, uint256{4}, uint256{5}, uint256{6}};
207 [ + - ]: 1 : auto mutated_leaves{leaves};
208 [ + - ]: 1 : mutated_leaves.insert(mutated_leaves.end(), leaves.end() - 2, leaves.end()); // repeat last two elements
209 : :
210 : 1 : bool mutated{true};
211 [ + - + - ]: 1 : const uint256 unmutated_root{ComputeMerkleRoot(leaves, &mutated)};
212 [ + - + - : 2 : BOOST_CHECK(!mutated);
+ - ]
213 [ + - + - : 1 : BOOST_CHECK_EQUAL(unmutated_root, ComputeMerkleRoot(mutated_leaves, &mutated));
+ - + - ]
214 [ + - + - : 2 : BOOST_CHECK( mutated);
+ - ]
215 : :
216 [ + - ]: 1 : const std::vector nontrailing_duplicate_leaves{uint256{1}, uint256{1}, uint256{3}, uint256{4}};
217 : 1 : mutated = false;
218 [ + - + - ]: 1 : const uint256 nontrailing_duplicate_root{ComputeMerkleRoot(nontrailing_duplicate_leaves, &mutated)};
219 [ + - + - : 3 : BOOST_CHECK(nontrailing_duplicate_root == ComputeMerkleRoot(nontrailing_duplicate_leaves));
+ - + - +
- ]
220 [ + - + - ]: 2 : BOOST_CHECK(mutated);
221 : 1 : }
222 : :
223 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
224 : : {
225 : 1 : CBlock block, leftSubtreeBlock, rightSubtreeBlock;
226 : :
227 [ + - ]: 1 : block.vtx.resize(4);
228 : : std::size_t pos;
229 [ - + + + ]: 5 : for (pos = 0; pos < block.vtx.size(); pos++) {
230 [ + - ]: 4 : CMutableTransaction mtx;
231 : 4 : mtx.nLockTime = pos;
232 [ + - - + ]: 8 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
233 : 4 : }
234 : :
235 [ - + + + ]: 3 : for (pos = 0; pos < block.vtx.size() / 2; pos++)
236 [ + - ]: 2 : leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
237 : :
238 [ - + + + ]: 3 : for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
239 [ + - ]: 2 : rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
240 : :
241 [ + - ]: 1 : uint256 root = BlockMerkleRoot(block);
242 [ + - ]: 1 : uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
243 [ + - ]: 1 : uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
244 : 1 : std::vector<uint256> leftRight;
245 [ + - ]: 1 : leftRight.push_back(rootOfLeftSubtree);
246 [ + - ]: 1 : leftRight.push_back(rootOfRightSubtree);
247 [ + - + - ]: 1 : uint256 rootOfLR = ComputeMerkleRoot(leftRight);
248 : :
249 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(root, rootOfLR);
250 : 1 : }
251 : :
252 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
253 : : {
254 : 1 : CBlock block;
255 : :
256 : 1 : constexpr size_t vtx_count{3};
257 [ + - ]: 1 : block.vtx.resize(vtx_count);
258 [ + + ]: 4 : for (std::size_t pos = 0; pos < vtx_count; pos++) {
259 [ + - ]: 3 : CMutableTransaction mtx;
260 : 3 : mtx.nLockTime = pos;
261 [ + - - + ]: 6 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
262 : 3 : }
263 : :
264 [ + - ]: 1 : uint256 blockWitness = BlockWitnessMerkleRoot(block);
265 : :
266 : 1 : std::vector<uint256> hashes;
267 [ + - ]: 1 : hashes.resize(vtx_count); // Odd count exercises leaf duplication in ComputeMerkleRoot (which can append one extra hash).
268 : 1 : hashes[0] = uint256::ZERO; // The witness hash of the coinbase is 0.
269 [ + + ]: 3 : for (size_t pos{1}; pos < vtx_count; ++pos) {
270 : 2 : hashes[pos] = block.vtx[pos]->GetWitnessHash().ToUint256();
271 : : }
272 : :
273 [ + - + - ]: 1 : uint256 merkleRootofHashes = ComputeMerkleRoot(hashes);
274 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness);
275 : 1 : }
276 : : BOOST_AUTO_TEST_SUITE_END()
|
