merkle_tests.cpp
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 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 /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ 27 static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) { 28 if (pbranch) pbranch->clear(); 29 if (leaves.size() == 0) { 30 if (pmutated) *pmutated = false; 31 if (proot) *proot = uint256(); 32 return; 33 } 34 bool mutated = false; 35 // count is the number of leaves processed so far. 36 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 uint256 inner[32]; 43 // Which position in inner is a hash that depends on the matching leaf. 44 int matchlevel = -1; 45 // First process all leaves into 'inner' values. 46 while (count < leaves.size()) { 47 uint256 h = leaves[count]; 48 bool matchh = count == branchpos; 49 count++; 50 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 for (level = 0; !(count & ((uint32_t{1}) << level)); level++) { 55 if (pbranch) { 56 if (matchh) { 57 pbranch->push_back(inner[level]); 58 } else if (matchlevel == level) { 59 pbranch->push_back(h); 60 matchh = true; 61 } 62 } 63 mutated |= (inner[level] == h); 64 h = Hash(inner[level], h); 65 } 66 // Store the resulting hash at inner position level. 67 inner[level] = h; 68 if (matchh) { 69 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 while (!(count & ((uint32_t{1}) << level))) { 79 level++; 80 } 81 uint256 h = inner[level]; 82 bool matchh = matchlevel == level; 83 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 if (pbranch && matchh) { 88 pbranch->push_back(h); 89 } 90 h = Hash(h, h); 91 // Increment count to the value it would have if two entries at this 92 // level had existed. 93 count += ((uint32_t{1}) << level); 94 level++; 95 // And propagate the result upwards accordingly. 96 while (!(count & ((uint32_t{1}) << level))) { 97 if (pbranch) { 98 if (matchh) { 99 pbranch->push_back(inner[level]); 100 } else if (matchlevel == level) { 101 pbranch->push_back(h); 102 matchh = true; 103 } 104 } 105 h = Hash(inner[level], h); 106 level++; 107 } 108 } 109 // Return result. 110 if (pmutated) *pmutated = mutated; 111 if (proot) *proot = h; 112 } 113 114 static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) { 115 std::vector<uint256> ret; 116 MerkleComputation(leaves, nullptr, nullptr, position, &ret); 117 return ret; 118 } 119 120 static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position) 121 { 122 std::vector<uint256> leaves; 123 leaves.resize(block.vtx.size()); 124 for (size_t s = 0; s < block.vtx.size(); s++) { 125 leaves[s] = block.vtx[s]->GetHash(); 126 } 127 return ComputeMerkleBranch(leaves, position); 128 } 129 130 // Older version of the merkle root computation code, for comparison. 131 static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree) 132 { 133 vMerkleTree.clear(); 134 vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. 135 for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) 136 vMerkleTree.push_back((*it)->GetHash()); 137 int j = 0; 138 bool mutated = false; 139 for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) 140 { 141 for (int i = 0; i < nSize; i += 2) 142 { 143 int i2 = std::min(i+1, nSize-1); 144 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 vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2])); 149 } 150 j += nSize; 151 } 152 if (fMutated) { 153 *fMutated = mutated; 154 } 155 return (vMerkleTree.empty() ? uint256() : vMerkleTree.back()); 156 } 157 158 // Older version of the merkle branch computation code, for comparison. 159 static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex) 160 { 161 std::vector<uint256> vMerkleBranch; 162 int j = 0; 163 for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) 164 { 165 int i = std::min(nIndex^1, nSize-1); 166 vMerkleBranch.push_back(vMerkleTree[j+i]); 167 nIndex >>= 1; 168 j += nSize; 169 } 170 return vMerkleBranch; 171 } 172 173 static inline int ctz(uint32_t i) { 174 if (i == 0) return 0; 175 int j = 0; 176 while (!(i & 1)) { 177 j++; 178 i >>= 1; 179 } 180 return j; 181 } 182 183 BOOST_AUTO_TEST_CASE(merkle_test) 184 { 185 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 int ntx = (i <= 16) ? i : 17 + (InsecureRandRange(4000)); 188 // Try up to 3 mutations. 189 for (int mutate = 0; mutate <= 3; mutate++) { 190 int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first. 191 if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level). 192 int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication. 193 int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation. 194 if (duplicate2 >= ntx1) break; 195 int ntx2 = ntx1 + duplicate2; 196 int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation. 197 if (duplicate3 >= ntx2) break; 198 int ntx3 = ntx2 + duplicate3; 199 // Build a block with ntx different transactions. 200 CBlock block; 201 block.vtx.resize(ntx); 202 for (int j = 0; j < ntx; j++) { 203 CMutableTransaction mtx; 204 mtx.nLockTime = j; 205 block.vtx[j] = MakeTransactionRef(std::move(mtx)); 206 } 207 // Compute the root of the block before mutating it. 208 bool unmutatedMutated = false; 209 uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated); 210 BOOST_CHECK(unmutatedMutated == false); 211 // Optionally mutate by duplicating the last transactions, resulting in the same merkle root. 212 block.vtx.resize(ntx3); 213 for (int j = 0; j < duplicate1; j++) { 214 block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1]; 215 } 216 for (int j = 0; j < duplicate2; j++) { 217 block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2]; 218 } 219 for (int j = 0; j < duplicate3; j++) { 220 block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3]; 221 } 222 // Compute the merkle root and merkle tree using the old mechanism. 223 bool oldMutated = false; 224 std::vector<uint256> merkleTree; 225 uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree); 226 // Compute the merkle root using the new mechanism. 227 bool newMutated = false; 228 uint256 newRoot = BlockMerkleRoot(block, &newMutated); 229 BOOST_CHECK(oldRoot == newRoot); 230 BOOST_CHECK(newRoot == unmutatedRoot); 231 BOOST_CHECK((newRoot == uint256()) == (ntx == 0)); 232 BOOST_CHECK(oldMutated == newMutated); 233 BOOST_CHECK(newMutated == !!mutate); 234 // If no mutation was done (once for every ntx value), try up to 16 branches. 235 if (mutate == 0) { 236 for (int loop = 0; loop < std::min(ntx, 16); loop++) { 237 // If ntx <= 16, try all branches. Otherwise, try 16 random ones. 238 int mtx = loop; 239 if (ntx > 16) { 240 mtx = InsecureRandRange(ntx); 241 } 242 std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx); 243 std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx); 244 BOOST_CHECK(oldBranch == newBranch); 245 BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot); 246 } 247 } 248 } 249 } 250 } 251 252 253 BOOST_AUTO_TEST_CASE(merkle_test_empty_block) 254 { 255 bool mutated = false; 256 CBlock block; 257 uint256 root = BlockMerkleRoot(block, &mutated); 258 259 BOOST_CHECK_EQUAL(root.IsNull(), true); 260 BOOST_CHECK_EQUAL(mutated, false); 261 } 262 263 BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block) 264 { 265 bool mutated = false; 266 CBlock block; 267 268 block.vtx.resize(1); 269 CMutableTransaction mtx; 270 mtx.nLockTime = 0; 271 block.vtx[0] = MakeTransactionRef(std::move(mtx)); 272 uint256 root = BlockMerkleRoot(block, &mutated); 273 BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash()); 274 BOOST_CHECK_EQUAL(mutated, false); 275 } 276 277 BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block) 278 { 279 bool mutated; 280 CBlock block, blockWithRepeatedLastTx; 281 282 block.vtx.resize(3); 283 284 for (std::size_t pos = 0; pos < block.vtx.size(); pos++) { 285 CMutableTransaction mtx; 286 mtx.nLockTime = pos; 287 block.vtx[pos] = MakeTransactionRef(std::move(mtx)); 288 } 289 290 blockWithRepeatedLastTx = block; 291 blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back()); 292 293 uint256 rootofBlock = BlockMerkleRoot(block, &mutated); 294 BOOST_CHECK_EQUAL(mutated, false); 295 296 uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated); 297 BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx); 298 BOOST_CHECK_EQUAL(mutated, true); 299 } 300 301 BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree) 302 { 303 CBlock block, leftSubtreeBlock, rightSubtreeBlock; 304 305 block.vtx.resize(4); 306 std::size_t pos; 307 for (pos = 0; pos < block.vtx.size(); pos++) { 308 CMutableTransaction mtx; 309 mtx.nLockTime = pos; 310 block.vtx[pos] = MakeTransactionRef(std::move(mtx)); 311 } 312 313 for (pos = 0; pos < block.vtx.size() / 2; pos++) 314 leftSubtreeBlock.vtx.push_back(block.vtx[pos]); 315 316 for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++) 317 rightSubtreeBlock.vtx.push_back(block.vtx[pos]); 318 319 uint256 root = BlockMerkleRoot(block); 320 uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock); 321 uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock); 322 std::vector<uint256> leftRight; 323 leftRight.push_back(rootOfLeftSubtree); 324 leftRight.push_back(rootOfRightSubtree); 325 uint256 rootOfLR = ComputeMerkleRoot(leftRight); 326 327 BOOST_CHECK_EQUAL(root, rootOfLR); 328 } 329 330 BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness) 331 { 332 CBlock block; 333 334 block.vtx.resize(2); 335 for (std::size_t pos = 0; pos < block.vtx.size(); pos++) { 336 CMutableTransaction mtx; 337 mtx.nLockTime = pos; 338 block.vtx[pos] = MakeTransactionRef(std::move(mtx)); 339 } 340 341 uint256 blockWitness = BlockWitnessMerkleRoot(block); 342 343 std::vector<uint256> hashes; 344 hashes.resize(block.vtx.size()); 345 hashes[0].SetNull(); 346 hashes[1] = block.vtx[1]->GetHash(); 347 348 uint256 merkleRootofHashes = ComputeMerkleRoot(hashes); 349 350 BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness); 351 } 352 BOOST_AUTO_TEST_SUITE_END()