text: // Copyright (c) 2015 The Lkcoinse Core developers
  // Copyright (c) 2015-2017 The Lkcoinse Unlimited developers
  // Distributed under the MIT software license, see the accompanying
  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  
  #include "consensus/merkle.h"
  #include "test/test_lkcoinse.h"
  #include "test/test_random.h"
  
  #include <boost/test/unit_test.hpp>
  
  BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
  
  // Older version of the merkle root computation code, for comparison.
  static uint256 BlockBuildMerkleTree(const CBlock &block, bool *fMutated, std::vector<uint256> &vMerkleTree)
  {
      vMerkleTree.clear();
      vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
      for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
          vMerkleTree.push_back((*it)->GetHash());
      int j = 0;
      bool mutated = false;
      for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
      {
          for (int i = 0; i < nSize; i += 2)
          {
              int i2 = std::min(i + 1, nSize - 1);
              if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j + i] == vMerkleTree[j + i2])
              {
                  // Two identical hashes at the end of the list at a particular level.
                  mutated = true;
              }
              vMerkleTree.push_back(Hash(vMerkleTree[j + i].begin(), vMerkleTree[j + i].end(),
                  vMerkleTree[j + i2].begin(), vMerkleTree[j + i2].end()));
          }
          j += nSize;
      }
      if (fMutated)
      {
          *fMutated = mutated;
      }
      return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
  }
  
  // Older version of the merkle branch computation code, for comparison.
  static std::vector<uint256> BlockGetMerkleBranch(const CBlock &block,
      const std::vector<uint256> &vMerkleTree,
      int nIndex)
  {
      std::vector<uint256> vMerkleBranch;
      int j = 0;
      for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
      {
          int i = std::min(nIndex ^ 1, nSize - 1);
          vMerkleBranch.push_back(vMerkleTree[j + i]);
          nIndex >>= 1;
          j += nSize;
      }
      return vMerkleBranch;
  }
  
  static inline int ctz(uint32_t i)
  {
      if (i == 0)
          return 0;
      int j = 0;
      while (!(i & 1))
      {
          j++;
          i >>= 1;
      }
      return j;
  }
  
  
  static uint256 ComputeRootFromCoinbaseProof(const uint256 &elem, const std::vector<uint256> &leaves)
  {
      uint256 running = elem;
      for (auto &hash : leaves)
      {
          uint256 result;
          CHash256().Write(running.begin(), 32).Write(hash.begin(), 32).Finalize(result.begin());
          running = result;
      }
      return running;
  }
  
  
  BOOST_AUTO_TEST_CASE(merkle_test)
  {
      // Test the merkle proof code exhaustively for element 0 (coinbase), since this is used when communicating
      // mining block headers to mining pools.
      unsigned int MAX_LEAVES = 100000;
      unsigned int MAX_TRIES = 20;
  
      std::vector<uint256> leafData;
      leafData.reserve(MAX_LEAVES);
  
      for (unsigned int i = 0; i < MAX_LEAVES; i++)
      {
          // add a random leaf
          uint256 temp;
          for (uint32_t j = 0; j < 32; j++)
              *(temp.begin() + j) = insecure_rand() & 255;
          leafData.push_back(temp);
      }
  
      for (unsigned int i = 0; i < MAX_TRIES; i++)
      {
          uint32_t size = insecure_rand() % MAX_LEAVES;
          std::vector<uint256> leaves = leafData;
          leaves.resize(size);
  
          uint256 root = ComputeMerkleRoot(leaves);
          std::vector<uint256> mklProof = ComputeMerkleBranch(leaves, 0);
  
          // Test 2 ways of doing it
          uint256 r1 = ComputeMerkleRootFromBranch(leaves[0], mklProof, 0);
          uint256 r2 = ComputeRootFromCoinbaseProof(leaves[0], mklProof);
  
          BOOST_CHECK(root == r1);
          BOOST_CHECK(root == r2);
      }
  
      for (int i = 0; i < 32; i++)
      {
          // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
          int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000);
          // Try up to 3 mutations.
          for (int mutate = 0; mutate <= 3; mutate++)
          {
              int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
              // Duplication of the entire tree results in a different root (it adds a level).
              if (duplicate1 >= ntx)
                  break;
              int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
              int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
              if (duplicate2 >= ntx1)
                  break;
              int ntx2 = ntx1 + duplicate2;
              int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
              if (duplicate3 >= ntx2)
                  break;
              int ntx3 = ntx2 + duplicate3;
              // Build a block with ntx different transactions.
              CBlock block;
              block.vtx.resize(ntx);
              for (int j = 0; j < ntx; j++)
              {
                  CMutableTransaction mtx;
                  mtx.nLockTime = j;
                  block.vtx[j] = MakeTransactionRef(std::move(mtx));
              }
              // Compute the root of the block before mutating it.
              bool unmutatedMutated = false;
              uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
              BOOST_CHECK(unmutatedMutated == false);
              // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
              block.vtx.resize(ntx3);
              for (int j = 0; j < duplicate1; j++)
              {
                  block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
              }
              for (int j = 0; j < duplicate2; j++)
              {
                  block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
              }
              for (int j = 0; j < duplicate3; j++)
              {
                  block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
              }
              // Compute the merkle root and merkle tree using the old mechanism.
              bool oldMutated = false;
              std::vector<uint256> merkleTree;
              uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
              // Compute the merkle root using the new mechanism.
              bool newMutated = false;
              uint256 newRoot = BlockMerkleRoot(block, &newMutated);
              BOOST_CHECK(oldRoot == newRoot);
              BOOST_CHECK(newRoot == unmutatedRoot);
              BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
              BOOST_CHECK(oldMutated == newMutated);
              BOOST_CHECK(newMutated == !!mutate);
              // If no mutation was done (once for every ntx value), try up to 16 branches.
              if (mutate == 0)
              {
                  for (int loop = 0; loop < std::min(ntx, 16); loop++)
                  {
                      // If ntx <= 16, try all branches. Otherise, try 16 random ones.
                      int mtx = loop;
                      if (ntx > 16)
                      {
                          mtx = insecure_rand() % ntx;
                      }
                      std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
                      std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
                      BOOST_CHECK(oldBranch == newBranch);
                      BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
                  }
              }
          }
      }
  }
  
  BOOST_AUTO_TEST_SUITE_END()
  