|
| 1 | +// Copyright (c) 2015 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/test_bitcoin.h" |
| 7 | +#include "random.h" |
| 8 | + |
| 9 | +#include <boost/test/unit_test.hpp> |
| 10 | + |
| 11 | +BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup) |
| 12 | + |
| 13 | +// Older version of the merkle root computation code, for comparison. |
| 14 | +static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree) |
| 15 | +{ |
| 16 | + vMerkleTree.clear(); |
| 17 | + vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. |
| 18 | + for (std::vector<CTransaction>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it) |
| 19 | + vMerkleTree.push_back(it->GetHash()); |
| 20 | + int j = 0; |
| 21 | + bool mutated = false; |
| 22 | + for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) |
| 23 | + { |
| 24 | + for (int i = 0; i < nSize; i += 2) |
| 25 | + { |
| 26 | + int i2 = std::min(i+1, nSize-1); |
| 27 | + if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) { |
| 28 | + // Two identical hashes at the end of the list at a particular level. |
| 29 | + mutated = true; |
| 30 | + } |
| 31 | + vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(), |
| 32 | + vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end())); |
| 33 | + } |
| 34 | + j += nSize; |
| 35 | + } |
| 36 | + if (fMutated) { |
| 37 | + *fMutated = mutated; |
| 38 | + } |
| 39 | + return (vMerkleTree.empty() ? uint256() : vMerkleTree.back()); |
| 40 | +} |
| 41 | + |
| 42 | +// Older version of the merkle branch computation code, for comparison. |
| 43 | +static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex) |
| 44 | +{ |
| 45 | + std::vector<uint256> vMerkleBranch; |
| 46 | + int j = 0; |
| 47 | + for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) |
| 48 | + { |
| 49 | + int i = std::min(nIndex^1, nSize-1); |
| 50 | + vMerkleBranch.push_back(vMerkleTree[j+i]); |
| 51 | + nIndex >>= 1; |
| 52 | + j += nSize; |
| 53 | + } |
| 54 | + return vMerkleBranch; |
| 55 | +} |
| 56 | + |
| 57 | +static inline int ctz(uint32_t i) { |
| 58 | + if (i == 0) return 0; |
| 59 | + int j = 0; |
| 60 | + while (!(i & 1)) { |
| 61 | + j++; |
| 62 | + i >>= 1; |
| 63 | + } |
| 64 | + return j; |
| 65 | +} |
| 66 | + |
| 67 | +BOOST_AUTO_TEST_CASE(merkle_test) |
| 68 | +{ |
| 69 | + for (int i = 0; i < 32; i++) { |
| 70 | + // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes. |
| 71 | + int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000); |
| 72 | + // Try up to 3 mutations. |
| 73 | + for (int mutate = 0; mutate <= 3; mutate++) { |
| 74 | + int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first. |
| 75 | + if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level). |
| 76 | + int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication. |
| 77 | + int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation. |
| 78 | + if (duplicate2 >= ntx1) break; |
| 79 | + int ntx2 = ntx1 + duplicate2; |
| 80 | + int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation. |
| 81 | + if (duplicate3 >= ntx2) break; |
| 82 | + int ntx3 = ntx2 + duplicate3; |
| 83 | + // Build a block with ntx different transactions. |
| 84 | + CBlock block; |
| 85 | + block.vtx.resize(ntx); |
| 86 | + for (int j = 0; j < ntx; j++) { |
| 87 | + CMutableTransaction mtx; |
| 88 | + mtx.nLockTime = j; |
| 89 | + block.vtx[j] = mtx; |
| 90 | + } |
| 91 | + // Compute the root of the block before mutating it. |
| 92 | + bool unmutatedMutated = false; |
| 93 | + uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated); |
| 94 | + BOOST_CHECK(unmutatedMutated == false); |
| 95 | + // Optionally mutate by duplicating the last transactions, resulting in the same merkle root. |
| 96 | + block.vtx.resize(ntx3); |
| 97 | + for (int j = 0; j < duplicate1; j++) { |
| 98 | + block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1]; |
| 99 | + } |
| 100 | + for (int j = 0; j < duplicate2; j++) { |
| 101 | + block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2]; |
| 102 | + } |
| 103 | + for (int j = 0; j < duplicate3; j++) { |
| 104 | + block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3]; |
| 105 | + } |
| 106 | + // Compute the merkle root and merkle tree using the old mechanism. |
| 107 | + bool oldMutated = false; |
| 108 | + std::vector<uint256> merkleTree; |
| 109 | + uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree); |
| 110 | + // Compute the merkle root using the new mechanism. |
| 111 | + bool newMutated = false; |
| 112 | + uint256 newRoot = BlockMerkleRoot(block, &newMutated); |
| 113 | + BOOST_CHECK(oldRoot == newRoot); |
| 114 | + BOOST_CHECK(newRoot == unmutatedRoot); |
| 115 | + BOOST_CHECK((newRoot == uint256()) == (ntx == 0)); |
| 116 | + BOOST_CHECK(oldMutated == newMutated); |
| 117 | + BOOST_CHECK(newMutated == !!mutate); |
| 118 | + // If no mutation was done (once for every ntx value), try up to 16 branches. |
| 119 | + if (mutate == 0) { |
| 120 | + for (int loop = 0; loop < std::min(ntx, 16); loop++) { |
| 121 | + // If ntx <= 16, try all branches. Otherise, try 16 random ones. |
| 122 | + int mtx = loop; |
| 123 | + if (ntx > 16) { |
| 124 | + mtx = insecure_rand() % ntx; |
| 125 | + } |
| 126 | + std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx); |
| 127 | + std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx); |
| 128 | + BOOST_CHECK(oldBranch == newBranch); |
| 129 | + BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx].GetHash(), newBranch, mtx) == oldRoot); |
| 130 | + } |
| 131 | + } |
| 132 | + } |
| 133 | + } |
| 134 | +} |
| 135 | + |
| 136 | +BOOST_AUTO_TEST_SUITE_END() |
0 commit comments