src/test/pmt_tests.cpp

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