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 // 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_LeftSubtreeRightSubtree) 198 { 199 CBlock block, leftSubtreeBlock, rightSubtreeBlock; 200 201 block.vtx.resize(4); 202 std::size_t pos; 203 for (pos = 0; pos < block.vtx.size(); pos++) { 204 CMutableTransaction mtx; 205 mtx.nLockTime = pos; 206 block.vtx[pos] = MakeTransactionRef(std::move(mtx)); 207 } 208 209 for (pos = 0; pos < block.vtx.size() / 2; pos++) 210 leftSubtreeBlock.vtx.push_back(block.vtx[pos]); 211 212 for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++) 213 rightSubtreeBlock.vtx.push_back(block.vtx[pos]); 214 215 uint256 root = BlockMerkleRoot(block); 216 uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock); 217 uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock); 218 std::vector<uint256> leftRight; 219 leftRight.push_back(rootOfLeftSubtree); 220 leftRight.push_back(rootOfRightSubtree); 221 uint256 rootOfLR = ComputeMerkleRoot(leftRight); 222 223 BOOST_CHECK_EQUAL(root, rootOfLR); 224 } 225 226 BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness) 227 { 228 CBlock block; 229 230 block.vtx.resize(2); 231 for (std::size_t pos = 0; pos < block.vtx.size(); pos++) { 232 CMutableTransaction mtx; 233 mtx.nLockTime = pos; 234 block.vtx[pos] = MakeTransactionRef(std::move(mtx)); 235 } 236 237 uint256 blockWitness = BlockWitnessMerkleRoot(block); 238 239 std::vector<uint256> hashes; 240 hashes.resize(block.vtx.size()); 241 hashes[0].SetNull(); 242 hashes[1] = block.vtx[1]->GetHash(); 243 244 uint256 merkleRootofHashes = ComputeMerkleRoot(hashes); 245 246 BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness); 247 } 248 BOOST_AUTO_TEST_SUITE_END()