Line data    Source code

       1             : // Copyright (c) 2015 The Bitcoin Core developers
       2             : // Copyright (c) 2019-2020 The PIVX Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include "consensus/merkle.h"
       7             : #include "test/test_pivx.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          93 : static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
      15             : {
      16          93 :     vMerkleTree.clear();
      17          93 :     vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
      18      120214 :     for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
      19      120121 :         vMerkleTree.push_back((*it)->GetHash());
      20          93 :     int j = 0;
      21          93 :     bool mutated = false;
      22         856 :     for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
      23             :     {
      24      121045 :         for (int i = 0; i < nSize; i += 2)
      25             :         {
      26      120282 :             int i2 = std::min(i+1, nSize-1);
      27      120282 :             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      120282 :             vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(),
      32      120282 :                                        vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end()));
      33             :         }
      34         763 :         j += nSize;
      35             :     }
      36          93 :     if (fMutated) {
      37          93 :         *fMutated = mutated;
      38             :     }
      39          93 :     return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
      40             : }
      41             : 
      42             : // Older version of the merkle branch computation code, for comparison.
      43         376 : static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
      44             : {
      45         376 :     std::vector<uint256> vMerkleBranch;
      46         376 :     int j = 0;
      47        3478 :     for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
      48             :     {
      49        3102 :         int i = std::min(nIndex^1, nSize-1);
      50        3102 :         vMerkleBranch.push_back(vMerkleTree[j+i]);
      51        3102 :         nIndex >>= 1;
      52        3102 :         j += nSize;
      53             :     }
      54         376 :     return vMerkleBranch;
      55             : }
      56             : 
      57         143 : static inline int ctz(uint32_t i) {
      58         143 :     if (i == 0) return 0;
      59             :     int j = 0;
      60         380 :     while (!(i & 1)) {
      61         237 :         j++;
      62         237 :         i >>= 1;
      63             :     }
      64             :     return j;
      65             : }
      66             : 
      67           2 : BOOST_AUTO_TEST_CASE(merkle_test)
      68             : {
      69          33 :     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          47 :         int ntx = (i <= 16) ? i : 17 + (InsecureRandRange(4000));
      72             :         // Try up to 3 mutations.
      73         125 :         for (int mutate = 0; mutate <= 3; mutate++) {
      74         186 :             int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
      75         109 :             if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
      76         103 :             int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
      77         149 :             int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
      78         103 :             if (duplicate2 >= ntx1) break;
      79          97 :             int ntx2 = ntx1 + duplicate2;
      80         117 :             int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation.
      81          97 :             if (duplicate3 >= ntx2) break;
      82          93 :             int ntx3 = ntx2 + duplicate3;
      83             :             // Build a block with ntx different transactions.
      84          93 :             CBlock block;
      85          93 :             block.vtx.resize(ntx);
      86      119219 :             for (int j = 0; j < ntx; j++) {
      87      119126 :                 CMutableTransaction mtx;
      88      119126 :                 mtx.nLockTime = j;
      89      119126 :                 block.vtx[j] = std::make_shared<const CTransaction>(mtx);
      90             :             }
      91             :             // Compute the root of the block before mutating it.
      92          93 :             bool unmutatedMutated = false;
      93          93 :             uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
      94         186 :             BOOST_CHECK(unmutatedMutated == false);
      95             :             // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
      96          93 :             block.vtx.resize(ntx3);
      97         252 :             for (int j = 0; j < duplicate1; j++) {
      98         159 :                 block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
      99             :             }
     100         381 :             for (int j = 0; j < duplicate2; j++) {
     101         288 :                 block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
     102             :             }
     103         641 :             for (int j = 0; j < duplicate3; j++) {
     104         548 :                 block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
     105             :             }
     106             :             // Compute the merkle root and merkle tree using the old mechanism.
     107          93 :             bool oldMutated = false;
     108         186 :             std::vector<uint256> merkleTree;
     109          93 :             uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
     110             :             // Compute the merkle root using the new mechanism.
     111          93 :             bool newMutated = false;
     112          93 :             uint256 newRoot = BlockMerkleRoot(block, &newMutated);
     113         186 :             BOOST_CHECK(oldRoot == newRoot);
     114         186 :             BOOST_CHECK(newRoot == unmutatedRoot);
     115         279 :             BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
     116         186 :             BOOST_CHECK(oldMutated == newMutated);
     117         186 :             BOOST_CHECK(newMutated == !!mutate);
     118             :             // If no mutation was done (once for every ntx value), try up to 16 branches.
     119          93 :             if (mutate == 0) {
     120         662 :                 for (int loop = 0; loop < std::min(ntx, 16); loop++) {
     121             :                     // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
     122         376 :                     int mtx = loop;
     123         376 :                     if (ntx > 16) {
     124         240 :                         mtx = InsecureRandRange(ntx);
     125             :                     }
     126         752 :                     std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
     127         752 :                     std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
     128         752 :                     BOOST_CHECK(oldBranch == newBranch);
     129         752 :                     BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
     130             :                 }
     131             :             }
     132             :         }
     133             :     }
     134           1 : }
     135             : 
     136             : BOOST_AUTO_TEST_SUITE_END()