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