LCOV - code coverage report
Current view: top level - src - merkleblock.cpp (source / functions) Hit Total Coverage
Test: total_coverage.info Lines: 96 106 90.6 %
Date: 2020-09-26 01:30:44 Functions: 12 12 100.0 %

          Line data    Source code
       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2019 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include <merkleblock.h>
       7             : 
       8             : #include <hash.h>
       9             : #include <consensus/consensus.h>
      10             : 
      11             : 
      12         186 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
      13             : {
      14         186 :     std::vector<unsigned char> ret((bits.size() + 7) / 8);
      15       76673 :     for (unsigned int p = 0; p < bits.size(); p++) {
      16       76487 :         ret[p / 8] |= bits[p] << (p % 8);
      17             :     }
      18             :     return ret;
      19         186 : }
      20             : 
      21         184 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
      22             : {
      23         184 :     std::vector<bool> ret(bytes.size() * 8);
      24       77504 :     for (unsigned int p = 0; p < ret.size(); p++) {
      25       77320 :         ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
      26             :     }
      27             :     return ret;
      28         184 : }
      29             : 
      30          60 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
      31          30 : {
      32          30 :     header = block.GetBlockHeader();
      33             : 
      34          30 :     std::vector<bool> vMatch;
      35          30 :     std::vector<uint256> vHashes;
      36             : 
      37          30 :     vMatch.reserve(block.vtx.size());
      38          30 :     vHashes.reserve(block.vtx.size());
      39             : 
      40         150 :     for (unsigned int i = 0; i < block.vtx.size(); i++)
      41             :     {
      42         120 :         const uint256& hash = block.vtx[i]->GetHash();
      43         120 :         if (txids && txids->count(hash)) {
      44          19 :             vMatch.push_back(true);
      45         120 :         } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
      46          23 :             vMatch.push_back(true);
      47          23 :             vMatchedTxn.emplace_back(i, hash);
      48             :         } else {
      49          78 :             vMatch.push_back(false);
      50             :         }
      51         120 :         vHashes.push_back(hash);
      52             :     }
      53             : 
      54          30 :     txn = CPartialMerkleTree(vHashes, vMatch);
      55          60 : }
      56             : 
      57      143848 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
      58             :     //we can never have zero txs in a merkle block, we always need the coinbase tx
      59             :     //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
      60      143848 :     assert(vTxid.size() != 0);
      61      143848 :     if (height == 0) {
      62             :         // hash at height 0 is the txids themself
      63       90964 :         return vTxid[pos];
      64             :     } else {
      65             :         // calculate left hash
      66       52884 :         uint256 left = CalcHash(height-1, pos*2, vTxid), right;
      67             :         // calculate right hash if not beyond the end of the array - copy left hash otherwise
      68       52884 :         if (pos*2+1 < CalcTreeWidth(height-1))
      69       52635 :             right = CalcHash(height-1, pos*2+1, vTxid);
      70             :         else
      71         249 :             right = left;
      72             :         // combine subhashes
      73       52884 :         return Hash(left, right);
      74       52884 :     }
      75      143848 : }
      76             : 
      77       76586 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
      78             :     // determine whether this node is the parent of at least one matched txid
      79       76586 :     bool fParentOfMatch = false;
      80      939092 :     for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
      81      862506 :         fParentOfMatch |= vMatch[p];
      82             :     // store as flag bit
      83       76586 :     vBits.push_back(fParentOfMatch);
      84       76586 :     if (height==0 || !fParentOfMatch) {
      85             :         // if at height 0, or nothing interesting below, store hash and stop
      86       38329 :         vHash.push_back(CalcHash(height, pos, vTxid));
      87       38329 :     } else {
      88             :         // otherwise, don't store any hash, but descend into the subtrees
      89       38257 :         TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
      90       38257 :         if (pos*2+1 < CalcTreeWidth(height-1))
      91       38130 :             TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
      92             :     }
      93       76586 : }
      94             : 
      95      382263 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
      96      382263 :     if (nBitsUsed >= vBits.size()) {
      97             :         // overflowed the bits array - failure
      98           0 :         fBad = true;
      99           0 :         return uint256();
     100             :     }
     101      382263 :     bool fParentOfMatch = vBits[nBitsUsed++];
     102      382263 :     if (height==0 || !fParentOfMatch) {
     103             :         // if at height 0, or nothing interesting below, use stored hash and do not descend
     104      191285 :         if (nHashUsed >= vHash.size()) {
     105             :             // overflowed the hash array - failure
     106           0 :             fBad = true;
     107           0 :             return uint256();
     108             :         }
     109      191285 :         const uint256 &hash = vHash[nHashUsed++];
     110      191285 :         if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
     111       95598 :             vMatch.push_back(hash);
     112       95598 :             vnIndex.push_back(pos);
     113       95598 :         }
     114      191285 :         return hash;
     115             :     } else {
     116             :         // otherwise, descend into the subtrees to extract matched txids and hashes
     117      190978 :         uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
     118      190978 :         if (pos*2+1 < CalcTreeWidth(height-1)) {
     119      190417 :             right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
     120      190417 :             if (right == left) {
     121             :                 // The left and right branches should never be identical, as the transaction
     122             :                 // hashes covered by them must each be unique.
     123           1 :                 fBad = true;
     124           1 :             }
     125             :         } else {
     126         561 :             right = left;
     127             :         }
     128             :         // and combine them before returning
     129      190978 :         return Hash(left, right);
     130      190978 :     }
     131      382263 : }
     132             : 
     133         398 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
     134             :     // reset state
     135         199 :     vBits.clear();
     136         199 :     vHash.clear();
     137             : 
     138             :     // calculate height of tree
     139             :     int nHeight = 0;
     140        1367 :     while (CalcTreeWidth(nHeight) > 1)
     141        1168 :         nHeight++;
     142             : 
     143             :     // traverse the partial tree
     144         199 :     TraverseAndBuild(nHeight, 0, vTxid, vMatch);
     145         398 : }
     146             : 
     147         274 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
     148             : 
     149         868 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
     150         868 :     vMatch.clear();
     151             :     // An empty set will not work
     152         868 :     if (nTransactions == 0)
     153           0 :         return uint256();
     154             :     // check for excessively high numbers of transactions
     155         868 :     if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT)
     156           0 :         return uint256();
     157             :     // there can never be more hashes provided than one for every txid
     158         868 :     if (vHash.size() > nTransactions)
     159           0 :         return uint256();
     160             :     // there must be at least one bit per node in the partial tree, and at least one node per hash
     161         868 :     if (vBits.size() < vHash.size())
     162           0 :         return uint256();
     163             :     // calculate height of tree
     164             :     int nHeight = 0;
     165        6457 :     while (CalcTreeWidth(nHeight) > 1)
     166        5589 :         nHeight++;
     167             :     // traverse the partial tree
     168         868 :     unsigned int nBitsUsed = 0, nHashUsed = 0;
     169         868 :     uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
     170             :     // verify that no problems occurred during the tree traversal
     171         868 :     if (fBad)
     172           1 :         return uint256();
     173             :     // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
     174         867 :     if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
     175           0 :         return uint256();
     176             :     // verify that all hashes were consumed
     177         867 :     if (nHashUsed != vHash.size())
     178           0 :         return uint256();
     179         867 :     return hashMerkleRoot;
     180         868 : }

Generated by: LCOV version 1.15