1 // Copyright (c) 2012-2016 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.
5 #include "consensus/merkle.h"
6 #include "merkleblock.h"
10 #include "arith_uint256.h"
12 #include "test/test_bitcoin.h"
13 #include "test/test_random.h"
17 #include <boost/assign/list_of.hpp>
18 #include <boost/test/unit_test.hpp>
20 class CPartialMerkleTreeTester
: public CPartialMerkleTree
23 // flip one bit in one of the hashes - this should break the authentication
25 unsigned int n
= insecure_rand() % vHash
.size();
26 int bit
= insecure_rand() % 256;
27 *(vHash
[n
].begin() + (bit
>>3)) ^= 1<<(bit
&7);
31 BOOST_FIXTURE_TEST_SUITE(pmt_tests
, BasicTestingSetup
)
33 BOOST_AUTO_TEST_CASE(pmt_test1
)
35 seed_insecure_rand(false);
36 static const unsigned int nTxCounts
[] = {1, 4, 7, 17, 56, 100, 127, 256, 312, 513, 1000, 4095};
38 for (int i
= 0; i
< 12; i
++) {
39 unsigned int nTx
= nTxCounts
[i
];
41 // build a block with some dummy transactions
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
)));
49 // calculate actual merkle root and height
50 uint256 merkleRoot1
= BlockMerkleRoot(block
);
51 std::vector
<uint256
> vTxid(nTx
, uint256());
52 for (unsigned int j
=0; j
<nTx
; j
++)
53 vTxid
[j
] = block
.vtx
[j
]->GetHash();
54 int nHeight
= 1, nTx_
= nTx
;
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
<uint256
> vMatchTxid1
;
65 for (unsigned int j
=0; j
<nTx
; j
++) {
66 bool fInclude
= (insecure_rand() & ((1 << (att
/2)) - 1)) == 0;
69 vMatchTxid1
.push_back(vTxid
[j
]);
72 // build the partial merkle tree
73 CPartialMerkleTree
pmt1(vTxid
, vMatch
);
76 CDataStream
ss(SER_NETWORK
, PROTOCOL_VERSION
);
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);
83 // deserialize into a tester copy
84 CPartialMerkleTreeTester pmt2
;
87 // extract merkle root and matched txids from copy
88 std::vector
<uint256
> vMatchTxid2
;
89 std::vector
<unsigned int> vIndex
;
90 uint256 merkleRoot2
= pmt2
.ExtractMatches(vMatchTxid2
, vIndex
);
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());
96 // check that it contains the matched transactions (in the same order!)
97 BOOST_CHECK(vMatchTxid1
== vMatchTxid2
);
99 // check that random bit flips break the authentication
100 for (int j
=0; j
<4; j
++) {
101 CPartialMerkleTreeTester
pmt3(pmt2
);
103 std::vector
<uint256
> vMatchTxid3
;
104 uint256 merkleRoot3
= pmt3
.ExtractMatches(vMatchTxid3
, vIndex
);
105 BOOST_CHECK(merkleRoot3
!= merkleRoot1
);
111 BOOST_AUTO_TEST_CASE(pmt_malleability
)
113 std::vector
<uint256
> vTxid
= boost::assign::list_of
114 (ArithToUint256(1))(ArithToUint256(2))
115 (ArithToUint256(3))(ArithToUint256(4))
116 (ArithToUint256(5))(ArithToUint256(6))
117 (ArithToUint256(7))(ArithToUint256(8))
118 (ArithToUint256(9))(ArithToUint256(10))
119 (ArithToUint256(9))(ArithToUint256(10));
120 std::vector
<bool> vMatch
= boost::assign::list_of(false)(false)(false)(false)(false)(false)(false)(false)(false)(true)(true)(false);
122 CPartialMerkleTree
tree(vTxid
, vMatch
);
123 std::vector
<unsigned int> vIndex
;
124 BOOST_CHECK(tree
.ExtractMatches(vTxid
, vIndex
).IsNull());
127 BOOST_AUTO_TEST_SUITE_END()