src/test/merkle_tests.cpp

   1 // Copyright (c) 2015-2016 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 "test/test_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<CTransactionRef>::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 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] = MakeTransactionRef(std::move(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()