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