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