Branch data Line data Source code
# 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/setup_common.h>
# 7 : :
# 8 : : #include <boost/test/unit_test.hpp>
# 9 : :
# 10 : : BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
# 11 : :
# 12 : 752 : static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
# 13 : 752 : uint256 hash = leaf;
# 14 [ + + ]: 6860 : for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
# 15 [ + + ]: 6108 : if (nIndex & 1) {
# 16 : 2754 : hash = Hash(*it, hash);
# 17 : 3354 : } else {
# 18 : 3354 : hash = Hash(hash, *it);
# 19 : 3354 : }
# 20 : 6108 : nIndex >>= 1;
# 21 : 6108 : }
# 22 : 752 : return hash;
# 23 : 752 : }
# 24 : :
# 25 : : /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
# 26 : 752 : static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
# 27 [ + - ]: 752 : if (pbranch) pbranch->clear();
# 28 [ - + ]: 752 : if (leaves.size() == 0) {
# 29 [ # # ]: 0 : if (pmutated) *pmutated = false;
# 30 [ # # ]: 0 : if (proot) *proot = uint256();
# 31 : 0 : return;
# 32 : 0 : }
# 33 : 752 : bool mutated = false;
# 34 : : // count is the number of leaves processed so far.
# 35 : 752 : uint32_t count = 0;
# 36 : : // inner is an array of eagerly computed subtree hashes, indexed by tree
# 37 : : // level (0 being the leaves).
# 38 : : // For example, when count is 25 (11001 in binary), inner[4] is the hash of
# 39 : : // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
# 40 : : // the last leaf. The other inner entries are undefined.
# 41 : 752 : uint256 inner[32];
# 42 : : // Which position in inner is a hash that depends on the matching leaf.
# 43 : 752 : int matchlevel = -1;
# 44 : : // First process all leaves into 'inner' values.
# 45 [ + + ]: 745024 : while (count < leaves.size()) {
# 46 : 744272 : uint256 h = leaves[count];
# 47 : 744272 : bool matchh = count == branchpos;
# 48 : 744272 : count++;
# 49 : 744272 : int level;
# 50 : : // For each of the lower bits in count that are 0, do 1 step. Each
# 51 : : // corresponds to an inner value that existed before processing the
# 52 : : // current leaf, and each needs a hash to combine it.
# 53 [ + + ]: 1485128 : for (level = 0; !(count & (((uint32_t)1) << level)); level++) {
# 54 [ + - ]: 740856 : if (pbranch) {
# 55 [ + + ]: 740856 : if (matchh) {
# 56 : 2452 : pbranch->push_back(inner[level]);
# 57 [ + + ]: 738404 : } else if (matchlevel == level) {
# 58 : 2550 : pbranch->push_back(h);
# 59 : 2550 : matchh = true;
# 60 : 2550 : }
# 61 : 740856 : }
# 62 : 740856 : mutated |= (inner[level] == h);
# 63 : 740856 : CHash256().Write(inner[level]).Write(h).Finalize(h);
# 64 : 740856 : }
# 65 : : // Store the resulting hash at inner position level.
# 66 : 744272 : inner[level] = h;
# 67 [ + + ]: 744272 : if (matchh) {
# 68 : 3302 : matchlevel = level;
# 69 : 3302 : }
# 70 : 744272 : }
# 71 : : // Do a final 'sweep' over the rightmost branch of the tree to process
# 72 : : // odd levels, and reduce everything to a single top value.
# 73 : : // Level is the level (counted from the bottom) up to which we've sweeped.
# 74 : 752 : int level = 0;
# 75 : : // As long as bit number level in count is zero, skip it. It means there
# 76 : : // is nothing left at this level.
# 77 [ + + ]: 1472 : while (!(count & (((uint32_t)1) << level))) {
# 78 : 720 : level++;
# 79 : 720 : }
# 80 : 752 : uint256 h = inner[level];
# 81 : 752 : bool matchh = matchlevel == level;
# 82 [ + + ]: 3476 : while (count != (((uint32_t)1) << level)) {
# 83 : : // If we reach this point, h is an inner value that is not the top.
# 84 : : // We combine it with itself (Bitcoin's special rule for odd levels in
# 85 : : // the tree) to produce a higher level one.
# 86 [ + - ][ + + ]: 2724 : if (pbranch && matchh) {
# 87 : 152 : pbranch->push_back(h);
# 88 : 152 : }
# 89 : 2724 : CHash256().Write(h).Write(h).Finalize(h);
# 90 : : // Increment count to the value it would have if two entries at this
# 91 : : // level had existed.
# 92 : 2724 : count += (((uint32_t)1) << level);
# 93 : 2724 : level++;
# 94 : : // And propagate the result upwards accordingly.
# 95 [ + + ]: 5388 : while (!(count & (((uint32_t)1) << level))) {
# 96 [ + - ]: 2664 : if (pbranch) {
# 97 [ + + ]: 2664 : if (matchh) {
# 98 : 302 : pbranch->push_back(inner[level]);
# 99 [ + + ]: 2362 : } else if (matchlevel == level) {
# 100 : 652 : pbranch->push_back(h);
# 101 : 652 : matchh = true;
# 102 : 652 : }
# 103 : 2664 : }
# 104 : 2664 : CHash256().Write(inner[level]).Write(h).Finalize(h);
# 105 : 2664 : level++;
# 106 : 2664 : }
# 107 : 2724 : }
# 108 : : // Return result.
# 109 [ - + ]: 752 : if (pmutated) *pmutated = mutated;
# 110 [ - + ]: 752 : if (proot) *proot = h;
# 111 : 752 : }
# 112 : :
# 113 : 752 : static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
# 114 : 752 : std::vector<uint256> ret;
# 115 : 752 : MerkleComputation(leaves, nullptr, nullptr, position, &ret);
# 116 : 752 : return ret;
# 117 : 752 : }
# 118 : :
# 119 : : static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
# 120 : 752 : {
# 121 : 752 : std::vector<uint256> leaves;
# 122 : 752 : leaves.resize(block.vtx.size());
# 123 [ + + ]: 745024 : for (size_t s = 0; s < block.vtx.size(); s++) {
# 124 : 744272 : leaves[s] = block.vtx[s]->GetHash();
# 125 : 744272 : }
# 126 : 752 : return ComputeMerkleBranch(leaves, position);
# 127 : 752 : }
# 128 : :
# 129 : : // Older version of the merkle root computation code, for comparison.
# 130 : : static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
# 131 : 184 : {
# 132 : 184 : vMerkleTree.clear();
# 133 : 184 : vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
# 134 [ + + ]: 189754 : for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
# 135 : 189570 : vMerkleTree.push_back((*it)->GetHash());
# 136 : 184 : int j = 0;
# 137 : 184 : bool mutated = false;
# 138 [ + + ]: 1672 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
# 139 : 1488 : {
# 140 [ + + ]: 191344 : for (int i = 0; i < nSize; i += 2)
# 141 : 189856 : {
# 142 : 189856 : int i2 = std::min(i+1, nSize-1);
# 143 [ + + ][ + + ]: 189856 : if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
# [ + + ]
# 144 : : // Two identical hashes at the end of the list at a particular level.
# 145 : 222 : mutated = true;
# 146 : 222 : }
# 147 : 189856 : vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
# 148 : 189856 : }
# 149 : 1488 : j += nSize;
# 150 : 1488 : }
# 151 [ + - ]: 184 : if (fMutated) {
# 152 : 184 : *fMutated = mutated;
# 153 : 184 : }
# 154 [ - + ]: 184 : return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
# 155 : 184 : }
# 156 : :
# 157 : : // Older version of the merkle branch computation code, for comparison.
# 158 : : static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
# 159 : 752 : {
# 160 : 752 : std::vector<uint256> vMerkleBranch;
# 161 : 752 : int j = 0;
# 162 [ + + ]: 6860 : for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
# 163 : 6108 : {
# 164 : 6108 : int i = std::min(nIndex^1, nSize-1);
# 165 : 6108 : vMerkleBranch.push_back(vMerkleTree[j+i]);
# 166 : 6108 : nIndex >>= 1;
# 167 : 6108 : j += nSize;
# 168 : 6108 : }
# 169 : 752 : return vMerkleBranch;
# 170 : 752 : }
# 171 : :
# 172 : 286 : static inline int ctz(uint32_t i) {
# 173 [ - + ]: 286 : if (i == 0) return 0;
# 174 : 286 : int j = 0;
# 175 [ + + ]: 808 : while (!(i & 1)) {
# 176 : 522 : j++;
# 177 : 522 : i >>= 1;
# 178 : 522 : }
# 179 : 286 : return j;
# 180 : 286 : }
# 181 : :
# 182 : : BOOST_AUTO_TEST_CASE(merkle_test)
# 183 : 2 : {
# 184 [ + + ]: 66 : for (int i = 0; i < 32; i++) {
# 185 : : // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
# 186 [ + + ]: 64 : int ntx = (i <= 16) ? i : 17 + (InsecureRandRange(4000));
# 187 : : // Try up to 3 mutations.
# 188 [ + + ]: 248 : for (int mutate = 0; mutate <= 3; mutate++) {
# 189 [ + + ]: 218 : int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
# 190 [ + + ]: 218 : if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
# 191 : 206 : int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
# 192 [ + + ]: 206 : int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
# 193 [ + + ]: 206 : if (duplicate2 >= ntx1) break;
# 194 : 194 : int ntx2 = ntx1 + duplicate2;
# 195 [ + + ]: 194 : int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
# 196 [ + + ]: 194 : if (duplicate3 >= ntx2) break;
# 197 : 184 : int ntx3 = ntx2 + duplicate3;
# 198 : : // Build a block with ntx different transactions.
# 199 : 184 : CBlock block;
# 200 : 184 : block.vtx.resize(ntx);
# 201 [ + + ]: 185864 : for (int j = 0; j < ntx; j++) {
# 202 : 185680 : CMutableTransaction mtx;
# 203 : 185680 : mtx.nLockTime = j;
# 204 : 185680 : block.vtx[j] = MakeTransactionRef(std::move(mtx));
# 205 : 185680 : }
# 206 : : // Compute the root of the block before mutating it.
# 207 : 184 : bool unmutatedMutated = false;
# 208 : 184 : uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
# 209 : 184 : BOOST_CHECK(unmutatedMutated == false);
# 210 : : // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
# 211 : 184 : block.vtx.resize(ntx3);
# 212 [ + + ]: 474 : for (int j = 0; j < duplicate1; j++) {
# 213 : 290 : block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
# 214 : 290 : }
# 215 [ + + ]: 1104 : for (int j = 0; j < duplicate2; j++) {
# 216 : 920 : block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
# 217 : 920 : }
# 218 [ + + ]: 2864 : for (int j = 0; j < duplicate3; j++) {
# 219 : 2680 : block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
# 220 : 2680 : }
# 221 : : // Compute the merkle root and merkle tree using the old mechanism.
# 222 : 184 : bool oldMutated = false;
# 223 : 184 : std::vector<uint256> merkleTree;
# 224 : 184 : uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
# 225 : : // Compute the merkle root using the new mechanism.
# 226 : 184 : bool newMutated = false;
# 227 : 184 : uint256 newRoot = BlockMerkleRoot(block, &newMutated);
# 228 : 184 : BOOST_CHECK(oldRoot == newRoot);
# 229 : 184 : BOOST_CHECK(newRoot == unmutatedRoot);
# 230 : 184 : BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
# 231 : 184 : BOOST_CHECK(oldMutated == newMutated);
# 232 : 184 : BOOST_CHECK(newMutated == !!mutate);
# 233 : : // If no mutation was done (once for every ntx value), try up to 16 branches.
# 234 [ + + ]: 184 : if (mutate == 0) {
# 235 [ + + ]: 814 : for (int loop = 0; loop < std::min(ntx, 16); loop++) {
# 236 : : // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
# 237 : 752 : int mtx = loop;
# 238 [ + + ]: 752 : if (ntx > 16) {
# 239 : 480 : mtx = InsecureRandRange(ntx);
# 240 : 480 : }
# 241 : 752 : std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
# 242 : 752 : std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
# 243 : 752 : BOOST_CHECK(oldBranch == newBranch);
# 244 : 752 : BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
# 245 : 752 : }
# 246 : 62 : }
# 247 : 184 : }
# 248 : 64 : }
# 249 : 2 : }
# 250 : :
# 251 : :
# 252 : : BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
# 253 : 2 : {
# 254 : 2 : bool mutated = false;
# 255 : 2 : CBlock block;
# 256 : 2 : uint256 root = BlockMerkleRoot(block, &mutated);
# 257 : :
# 258 : 2 : BOOST_CHECK_EQUAL(root.IsNull(), true);
# 259 : 2 : BOOST_CHECK_EQUAL(mutated, false);
# 260 : 2 : }
# 261 : :
# 262 : : BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
# 263 : 2 : {
# 264 : 2 : bool mutated = false;
# 265 : 2 : CBlock block;
# 266 : :
# 267 : 2 : block.vtx.resize(1);
# 268 : 2 : CMutableTransaction mtx;
# 269 : 2 : mtx.nLockTime = 0;
# 270 : 2 : block.vtx[0] = MakeTransactionRef(std::move(mtx));
# 271 : 2 : uint256 root = BlockMerkleRoot(block, &mutated);
# 272 : 2 : BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash());
# 273 : 2 : BOOST_CHECK_EQUAL(mutated, false);
# 274 : 2 : }
# 275 : :
# 276 : : BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
# 277 : 2 : {
# 278 : 2 : bool mutated;
# 279 : 2 : CBlock block, blockWithRepeatedLastTx;
# 280 : :
# 281 : 2 : block.vtx.resize(3);
# 282 : :
# 283 [ + + ]: 8 : for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
# 284 : 6 : CMutableTransaction mtx;
# 285 : 6 : mtx.nLockTime = pos;
# 286 : 6 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
# 287 : 6 : }
# 288 : :
# 289 : 2 : blockWithRepeatedLastTx = block;
# 290 : 2 : blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
# 291 : :
# 292 : 2 : uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
# 293 : 2 : BOOST_CHECK_EQUAL(mutated, false);
# 294 : :
# 295 : 2 : uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
# 296 : 2 : BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
# 297 : 2 : BOOST_CHECK_EQUAL(mutated, true);
# 298 : 2 : }
# 299 : :
# 300 : : BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
# 301 : 2 : {
# 302 : 2 : CBlock block, leftSubtreeBlock, rightSubtreeBlock;
# 303 : :
# 304 : 2 : block.vtx.resize(4);
# 305 : 2 : std::size_t pos;
# 306 [ + + ]: 10 : for (pos = 0; pos < block.vtx.size(); pos++) {
# 307 : 8 : CMutableTransaction mtx;
# 308 : 8 : mtx.nLockTime = pos;
# 309 : 8 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
# 310 : 8 : }
# 311 : :
# 312 [ + + ]: 6 : for (pos = 0; pos < block.vtx.size() / 2; pos++)
# 313 : 4 : leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
# 314 : :
# 315 [ + + ]: 6 : for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
# 316 : 4 : rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
# 317 : :
# 318 : 2 : uint256 root = BlockMerkleRoot(block);
# 319 : 2 : uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
# 320 : 2 : uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
# 321 : 2 : std::vector<uint256> leftRight;
# 322 : 2 : leftRight.push_back(rootOfLeftSubtree);
# 323 : 2 : leftRight.push_back(rootOfRightSubtree);
# 324 : 2 : uint256 rootOfLR = ComputeMerkleRoot(leftRight);
# 325 : :
# 326 : 2 : BOOST_CHECK_EQUAL(root, rootOfLR);
# 327 : 2 : }
# 328 : :
# 329 : : BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness)
# 330 : 2 : {
# 331 : 2 : CBlock block;
# 332 : :
# 333 : 2 : block.vtx.resize(2);
# 334 [ + + ]: 6 : for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
# 335 : 4 : CMutableTransaction mtx;
# 336 : 4 : mtx.nLockTime = pos;
# 337 : 4 : block.vtx[pos] = MakeTransactionRef(std::move(mtx));
# 338 : 4 : }
# 339 : :
# 340 : 2 : uint256 blockWitness = BlockWitnessMerkleRoot(block);
# 341 : :
# 342 : 2 : std::vector<uint256> hashes;
# 343 : 2 : hashes.resize(block.vtx.size());
# 344 : 2 : hashes[0].SetNull();
# 345 : 2 : hashes[1] = block.vtx[1]->GetHash();
# 346 : :
# 347 : 2 : uint256 merkleRootofHashes = ComputeMerkleRoot(hashes);
# 348 : :
# 349 : 2 : BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness);
# 350 : 2 : }
# 351 : : BOOST_AUTO_TEST_SUITE_END()
|
