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"
16 #include <boost/assign/list_of.hpp>
17 #include <boost/test/unit_test.hpp>
19 class CPartialMerkleTreeTester
: public CPartialMerkleTree
22 // flip one bit in one of the hashes - this should break the authentication
24 unsigned int n
= insecure_randrange(vHash
.size());
25 int bit
= insecure_randrange(256);
26 *(vHash
[n
].begin() + (bit
>>3)) ^= 1<<(bit
&7);
30 BOOST_FIXTURE_TEST_SUITE(pmt_tests
, BasicTestingSetup
)
32 BOOST_AUTO_TEST_CASE(pmt_test1
)
34 seed_insecure_rand(false);
35 static const unsigned int nTxCounts
[] = {1, 4, 7, 17, 56, 100, 127, 256, 312, 513, 1000, 4095};
37 for (int i
= 0; i
< 12; i
++) {
38 unsigned int nTx
= nTxCounts
[i
];
40 // build a block with some dummy transactions
42 for (unsigned int j
=0; j
<nTx
; j
++) {
43 CMutableTransaction tx
;
44 tx
.nLockTime
= j
; // actual transaction data doesn't matter; just make the nLockTime's unique
45 block
.vtx
.push_back(MakeTransactionRef(std::move(tx
)));
48 // calculate actual merkle root and height
49 uint256 merkleRoot1
= BlockMerkleRoot(block
);
50 std::vector
<uint256
> vTxid(nTx
, uint256());
51 for (unsigned int j
=0; j
<nTx
; j
++)
52 vTxid
[j
] = block
.vtx
[j
]->GetHash();
53 int nHeight
= 1, nTx_
= nTx
;
59 // check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128
60 for (int att
= 1; att
< 15; att
++) {
61 // build random subset of txid's
62 std::vector
<bool> vMatch(nTx
, false);
63 std::vector
<uint256
> vMatchTxid1
;
64 for (unsigned int j
=0; j
<nTx
; j
++) {
65 bool fInclude
= insecure_randbits(att
/ 2) == 0;
68 vMatchTxid1
.push_back(vTxid
[j
]);
71 // build the partial merkle tree
72 CPartialMerkleTree
pmt1(vTxid
, vMatch
);
75 CDataStream
ss(SER_NETWORK
, PROTOCOL_VERSION
);
78 // verify CPartialMerkleTree's size guarantees
79 unsigned int n
= std::min
<unsigned int>(nTx
, 1 + vMatchTxid1
.size()*nHeight
);
80 BOOST_CHECK(ss
.size() <= 10 + (258*n
+7)/8);
82 // deserialize into a tester copy
83 CPartialMerkleTreeTester pmt2
;
86 // extract merkle root and matched txids from copy
87 std::vector
<uint256
> vMatchTxid2
;
88 std::vector
<unsigned int> vIndex
;
89 uint256 merkleRoot2
= pmt2
.ExtractMatches(vMatchTxid2
, vIndex
);
91 // check that it has the same merkle root as the original, and a valid one
92 BOOST_CHECK(merkleRoot1
== merkleRoot2
);
93 BOOST_CHECK(!merkleRoot2
.IsNull());
95 // check that it contains the matched transactions (in the same order!)
96 BOOST_CHECK(vMatchTxid1
== vMatchTxid2
);
98 // check that random bit flips break the authentication
99 for (int j
=0; j
<4; j
++) {
100 CPartialMerkleTreeTester
pmt3(pmt2
);
102 std::vector
<uint256
> vMatchTxid3
;
103 uint256 merkleRoot3
= pmt3
.ExtractMatches(vMatchTxid3
, vIndex
);
104 BOOST_CHECK(merkleRoot3
!= merkleRoot1
);
110 BOOST_AUTO_TEST_CASE(pmt_malleability
)
112 std::vector
<uint256
> vTxid
= boost::assign::list_of
113 (ArithToUint256(1))(ArithToUint256(2))
114 (ArithToUint256(3))(ArithToUint256(4))
115 (ArithToUint256(5))(ArithToUint256(6))
116 (ArithToUint256(7))(ArithToUint256(8))
117 (ArithToUint256(9))(ArithToUint256(10))
118 (ArithToUint256(9))(ArithToUint256(10));
119 std::vector
<bool> vMatch
= boost::assign::list_of(false)(false)(false)(false)(false)(false)(false)(false)(false)(true)(true)(false);
121 CPartialMerkleTree
tree(vTxid
, vMatch
);
122 std::vector
<unsigned int> vIndex
;
123 BOOST_CHECK(tree
.ExtractMatches(vTxid
, vIndex
).IsNull());
126 BOOST_AUTO_TEST_SUITE_END()