Bitcoin Core  24.99.0
P2P Digital Currency
pmt_tests.cpp
Go to the documentation of this file.
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>
10 #include <uint256.h>
11 #include <version.h>
12 
13 #include <vector>
14 
15 #include <boost/test/unit_test.hpp>
16 
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 
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++) {
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
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 
Definition: block.h:69
std::vector< CTransactionRef > vtx
Definition: block.h:72
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:55
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
extract the matching txid's represented by this partial merkle tree and their respective indices with...
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:64
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:186
bool IsNull() const
Definition: uint256.h:34
256-bit opaque blob.
Definition: uint256.h:119
BOOST_AUTO_TEST_SUITE_END()
unsigned int nHeight
uint256 BlockMerkleRoot(const CBlock &block, bool *mutated)
Definition: merkle.cpp:65
#define BOOST_CHECK(expr)
Definition: object.cpp:17
BOOST_AUTO_TEST_CASE(pmt_test1)
Definition: pmt_tests.cpp:30
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:422
static uint64_t InsecureRandRange(uint64_t range)
Definition: setup_common.h:77
static uint64_t InsecureRandBits(int bits)
Definition: setup_common.h:76
Basic testing setup.
Definition: setup_common.h:85
A mutable version of CTransaction.
Definition: transaction.h:380