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