Line data Source code
1 : // Copyright (c) 2012-2013 The Bitcoin Core developers 2 : // Copyright (c) 2017-2021 The PIVX Core developers 3 : // Distributed under the MIT/X11 software license, see the accompanying 4 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 : 6 : #include "merkleblock.h" 7 : #include "serialize.h" 8 : #include "streams.h" 9 : #include "uint256.h" 10 : #include "version.h" 11 : #include "consensus/merkle.h" 12 : #include "test/test_pivx.h" 13 : 14 : #include <vector> 15 : 16 : #include <boost/test/unit_test.hpp> 17 : 18 : 19 0 : class CPartialMerkleTreeTester : public CPartialMerkleTree 20 : { 21 : public: 22 : // flip one bit in one of the hashes - this should break the authentication 23 672 : void Damage() { 24 672 : unsigned int n = InsecureRandRange(vHash.size()); 25 672 : int bit = InsecureRandBits(8); 26 672 : *(vHash[n].begin() + (bit>>3)) ^= 1<<(bit&7); 27 672 : } 28 : }; 29 : 30 : BOOST_FIXTURE_TEST_SUITE(pmt_tests, BasicTestingSetup) 31 : 32 2 : BOOST_AUTO_TEST_CASE(pmt_test1) 33 : { 34 1 : static const unsigned int nTxCounts[] = {1, 4, 7, 17, 56, 100, 127, 256, 312, 513, 1000, 4095}; 35 : 36 13 : for (int n = 0; n < 12; n++) { 37 12 : unsigned int nTx = nTxCounts[n]; 38 : 39 : // build a block with some dummy transactions 40 24 : CBlock block; 41 6500 : for (unsigned int j=0; j<nTx; j++) { 42 6488 : CMutableTransaction tx; 43 6488 : tx.nLockTime = InsecureRand32(); // actual transaction data doesn't matter; just make the nLockTime's unique 44 12976 : block.vtx.emplace_back(std::make_shared<const CTransaction>(tx)); 45 : } 46 : 47 : // calculate actual merkle root and height 48 12 : uint256 merkleRoot1 = BlockMerkleRoot(block); 49 24 : std::vector<uint256> vTxid(nTx, UINT256_ZERO); 50 6500 : for (unsigned int j=0; j<nTx; j++) 51 6488 : vTxid[j] = block.vtx[j]->GetHash(); 52 12 : int nHeight = 1, nTx_ = nTx; 53 91 : while (nTx_ > 1) { 54 79 : nTx_ = (nTx_+1)/2; 55 79 : nHeight++; 56 : } 57 : 58 : // check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128 59 180 : for (int att = 1; att < 15; att++) { 60 : // build random subset of txid's 61 336 : std::vector<bool> vMatch(nTx, false); 62 336 : std::vector<uint256> vMatchTxid1; 63 91000 : for (unsigned int j=0; j<nTx; j++) { 64 90832 : bool fInclude = InsecureRandBits(att / 2) == 0; 65 90832 : vMatch[j] = fInclude; 66 90832 : if (fInclude) 67 19354 : vMatchTxid1.push_back(vTxid[j]); 68 : } 69 : 70 : // build the partial merkle tree 71 336 : CPartialMerkleTree pmt1(vTxid, vMatch); 72 : 73 : // serialize 74 336 : CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); 75 168 : ss << pmt1; 76 : 77 : // verify CPartialMerkleTree's size guarantees 78 168 : unsigned int n = std::min<unsigned int>(nTx, 1 + vMatchTxid1.size()*nHeight); 79 336 : BOOST_CHECK(ss.size() <= 10 + (258*n+7)/8); 80 : 81 : // deserialize into a tester copy 82 336 : CPartialMerkleTreeTester pmt2; 83 168 : ss >> pmt2; 84 : 85 : // extract merkle root and matched txids from copy 86 336 : std::vector<uint256> vMatchTxid2; 87 168 : uint256 merkleRoot2 = pmt2.ExtractMatches(vMatchTxid2); 88 : 89 : // check that it has the same merkle root as the original, and a valid one 90 336 : BOOST_CHECK(merkleRoot1 == merkleRoot2); 91 518 : 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 840 : for (int j=0; j<4; j++) { 98 1344 : CPartialMerkleTreeTester pmt3(pmt2); 99 672 : pmt3.Damage(); 100 1344 : std::vector<uint256> vMatchTxid3; 101 672 : uint256 merkleRoot3 = pmt3.ExtractMatches(vMatchTxid3); 102 1344 : BOOST_CHECK(merkleRoot3 != merkleRoot1); 103 : } 104 : } 105 : } 106 1 : } 107 : 108 : BOOST_AUTO_TEST_SUITE_END()