1  // Copyright (c) 2012-2022 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 <merkleblock.h>
  7  #include <serialize.h>
  8  #include <streams.h>
  9  #include <test/util/random.h>
 10  #include <test/util/setup_common.h>
 11  #include <uint256.h>
 12  
 13  #include <vector>
 14  
 15  #include <boost/test/unit_test.hpp>
 16  
 17  class CPartialMerkleTreeTester : public CPartialMerkleTree
 18  {
 19  public:
 20      // flip one bit in one of the hashes - this should break the authentication
 21      void Damage() {
 22          unsigned int n = InsecureRandRange(vHash.size());
 23          int bit = InsecureRandBits(8);
 24          *(vHash[n].begin() + (bit>>3)) ^= 1<<(bit&7);
 25      }
 26  };
 27  
 28  BOOST_FIXTURE_TEST_SUITE(pmt_tests, BasicTestingSetup)
 29  
 30  BOOST_AUTO_TEST_CASE(pmt_test1)
 31  {
 32      static const unsigned int nTxCounts[] = {1, 4, 7, 17, 56, 100, 127, 256, 312, 513, 1000, 4095};
 33  
 34      for (int i = 0; i < 12; i++) {
 35          unsigned int nTx = nTxCounts[i];
 36  
 37          // build a block with some dummy transactions
 38          CBlock block;
 39          for (unsigned int j=0; j<nTx; j++) {
 40              CMutableTransaction tx;
 41              tx.nLockTime = j; // actual transaction data doesn't matter; just make the nLockTime's unique
 42              block.vtx.push_back(MakeTransactionRef(std::move(tx)));
 43          }
 44  
 45          // calculate actual merkle root and height
 46          uint256 merkleRoot1 = BlockMerkleRoot(block);
 47          std::vector<uint256> vTxid(nTx, uint256());
 48          for (unsigned int j=0; j<nTx; j++)
 49              vTxid[j] = block.vtx[j]->GetHash();
 50          int nHeight = 1, nTx_ = nTx;
 51          while (nTx_ > 1) {
 52              nTx_ = (nTx_+1)/2;
 53              nHeight++;
 54          }
 55  
 56          // check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128
 57          for (int att = 1; att < 15; att++) {
 58              // build random subset of txid's
 59              std::vector<bool> vMatch(nTx, false);
 60              std::vector<uint256> vMatchTxid1;
 61              for (unsigned int j=0; j<nTx; j++) {
 62                  bool fInclude = InsecureRandBits(att / 2) == 0;
 63                  vMatch[j] = fInclude;
 64                  if (fInclude)
 65                      vMatchTxid1.push_back(vTxid[j]);
 66              }
 67  
 68              // build the partial merkle tree
 69              CPartialMerkleTree pmt1(vTxid, vMatch);
 70  
 71              // serialize
 72              DataStream ss{};
 73              ss << pmt1;
 74  
 75              // verify CPartialMerkleTree's size guarantees
 76              unsigned int n = std::min<unsigned int>(nTx, 1 + vMatchTxid1.size()*nHeight);
 77              BOOST_CHECK(ss.size() <= 10 + (258*n+7)/8);
 78  
 79              // deserialize into a tester copy
 80              CPartialMerkleTreeTester pmt2;
 81              ss >> pmt2;
 82  
 83              // extract merkle root and matched txids from copy
 84              std::vector<uint256> vMatchTxid2;
 85              std::vector<unsigned int> vIndex;
 86              uint256 merkleRoot2 = pmt2.ExtractMatches(vMatchTxid2, vIndex);
 87  
 88              // check that it has the same merkle root as the original, and a valid one
 89              BOOST_CHECK(merkleRoot1 == merkleRoot2);
 90              BOOST_CHECK(!merkleRoot2.IsNull());
 91  
 92              // check that it contains the matched transactions (in the same order!)
 93              BOOST_CHECK(vMatchTxid1 == vMatchTxid2);
 94  
 95              // check that random bit flips break the authentication
 96              for (int j=0; j<4; j++) {
 97                  CPartialMerkleTreeTester pmt3(pmt2);
 98                  pmt3.Damage();
 99                  std::vector<uint256> vMatchTxid3;
100                  uint256 merkleRoot3 = pmt3.ExtractMatches(vMatchTxid3, vIndex);
101                  BOOST_CHECK(merkleRoot3 != merkleRoot1);
102              }
103          }
104      }
105  }
106  
107  BOOST_AUTO_TEST_CASE(pmt_malleability)
108  {
109      std::vector<uint256> vTxid{
110          uint256{1}, uint256{2},
111          uint256{3}, uint256{4},
112          uint256{5}, uint256{6},
113          uint256{7}, uint256{8},
114          uint256{9}, uint256{10},
115          uint256{9}, uint256{10},
116      };
117      std::vector<bool> vMatch = {false, false, false, false, false, false, false, false, false, true, true, false};
118  
119      CPartialMerkleTree tree(vTxid, vMatch);
120      std::vector<unsigned int> vIndex;
121      BOOST_CHECK(tree.ExtractMatches(vTxid, vIndex).IsNull());
122  }
123  
124  BOOST_AUTO_TEST_SUITE_END()