LCOV - code coverage report
Current view: top level - src - merkleblock.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 0 112 0.0 %
Date: 2023-11-06 23:13:05 Functions: 0 9 0.0 %
Branches: 0 104 0.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2                 :            : // Copyright (c) 2009-2020 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                 :          0 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
      13                 :            : {
      14         [ #  # ]:          0 :     std::vector<unsigned char> ret((bits.size() + 7) / 8);
      15         [ #  # ]:          0 :     for (unsigned int p = 0; p < bits.size(); p++) {
      16         [ #  # ]:          0 :         ret[p / 8] |= bits[p] << (p % 8);
      17                 :          0 :     }
      18                 :          0 :     return ret;
      19         [ #  # ]:          0 : }
      20                 :            : 
      21                 :          0 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
      22                 :            : {
      23         [ #  # ]:          0 :     std::vector<bool> ret(bytes.size() * 8);
      24         [ #  # ]:          0 :     for (unsigned int p = 0; p < ret.size(); p++) {
      25         [ #  # ]:          0 :         ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
      26                 :          0 :     }
      27                 :          0 :     return ret;
      28         [ #  # ]:          0 : }
      29                 :            : 
      30                 :          0 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
      31                 :            : {
      32         [ #  # ]:          0 :     header = block.GetBlockHeader();
      33                 :            : 
      34                 :          0 :     std::vector<bool> vMatch;
      35                 :          0 :     std::vector<uint256> vHashes;
      36                 :            : 
      37         [ #  # ]:          0 :     vMatch.reserve(block.vtx.size());
      38         [ #  # ]:          0 :     vHashes.reserve(block.vtx.size());
      39                 :            : 
      40         [ #  # ]:          0 :     for (unsigned int i = 0; i < block.vtx.size(); i++)
      41                 :            :     {
      42         [ #  # ]:          0 :         const uint256& hash = block.vtx[i]->GetHash();
      43 [ #  # ][ #  # ]:          0 :         if (txids && txids->count(hash)) {
                 [ #  # ]
      44         [ #  # ]:          0 :             vMatch.push_back(true);
      45 [ #  # ][ #  # ]:          0 :         } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
                 [ #  # ]
      46         [ #  # ]:          0 :             vMatch.push_back(true);
      47         [ #  # ]:          0 :             vMatchedTxn.emplace_back(i, hash);
      48                 :          0 :         } else {
      49         [ #  # ]:          0 :             vMatch.push_back(false);
      50                 :            :         }
      51         [ #  # ]:          0 :         vHashes.push_back(hash);
      52                 :          0 :     }
      53                 :            : 
      54         [ #  # ]:          0 :     txn = CPartialMerkleTree(vHashes, vMatch);
      55                 :          0 : }
      56                 :            : 
      57                 :          0 : 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         [ #  # ]:          0 :     assert(vTxid.size() != 0);
      61         [ #  # ]:          0 :     if (height == 0) {
      62                 :            :         // hash at height 0 is the txids themselves
      63                 :          0 :         return vTxid[pos];
      64                 :            :     } else {
      65                 :            :         // calculate left hash
      66                 :          0 :         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         [ #  # ]:          0 :         if (pos*2+1 < CalcTreeWidth(height-1))
      69                 :          0 :             right = CalcHash(height-1, pos*2+1, vTxid);
      70                 :            :         else
      71                 :          0 :             right = left;
      72                 :            :         // combine subhashes
      73                 :          0 :         return Hash(left, right);
      74                 :            :     }
      75                 :          0 : }
      76                 :            : 
      77                 :          0 : 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                 :          0 :     bool fParentOfMatch = false;
      80 [ #  # ][ #  # ]:          0 :     for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
      81                 :          0 :         fParentOfMatch |= vMatch[p];
      82                 :            :     // store as flag bit
      83                 :          0 :     vBits.push_back(fParentOfMatch);
      84 [ #  # ][ #  # ]:          0 :     if (height==0 || !fParentOfMatch) {
      85                 :            :         // if at height 0, or nothing interesting below, store hash and stop
      86                 :          0 :         vHash.push_back(CalcHash(height, pos, vTxid));
      87                 :          0 :     } else {
      88                 :            :         // otherwise, don't store any hash, but descend into the subtrees
      89                 :          0 :         TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
      90         [ #  # ]:          0 :         if (pos*2+1 < CalcTreeWidth(height-1))
      91                 :          0 :             TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
      92                 :            :     }
      93                 :          0 : }
      94                 :            : 
      95                 :          0 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
      96         [ #  # ]:          0 :     if (nBitsUsed >= vBits.size()) {
      97                 :            :         // overflowed the bits array - failure
      98                 :          0 :         fBad = true;
      99                 :          0 :         return uint256();
     100                 :            :     }
     101                 :          0 :     bool fParentOfMatch = vBits[nBitsUsed++];
     102 [ #  # ][ #  # ]:          0 :     if (height==0 || !fParentOfMatch) {
     103                 :            :         // if at height 0, or nothing interesting below, use stored hash and do not descend
     104         [ #  # ]:          0 :         if (nHashUsed >= vHash.size()) {
     105                 :            :             // overflowed the hash array - failure
     106                 :          0 :             fBad = true;
     107                 :          0 :             return uint256();
     108                 :            :         }
     109                 :          0 :         const uint256 &hash = vHash[nHashUsed++];
     110 [ #  # ][ #  # ]:          0 :         if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
     111                 :          0 :             vMatch.push_back(hash);
     112                 :          0 :             vnIndex.push_back(pos);
     113                 :          0 :         }
     114                 :          0 :         return hash;
     115                 :            :     } else {
     116                 :            :         // otherwise, descend into the subtrees to extract matched txids and hashes
     117                 :          0 :         uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
     118         [ #  # ]:          0 :         if (pos*2+1 < CalcTreeWidth(height-1)) {
     119                 :          0 :             right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
     120         [ #  # ]:          0 :             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                 :          0 :                 fBad = true;
     124                 :          0 :             }
     125                 :          0 :         } else {
     126                 :          0 :             right = left;
     127                 :            :         }
     128                 :            :         // and combine them before returning
     129                 :          0 :         return Hash(left, right);
     130                 :            :     }
     131                 :          0 : }
     132                 :            : 
     133                 :          0 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
     134                 :            :     // reset state
     135                 :          0 :     vBits.clear();
     136                 :          0 :     vHash.clear();
     137                 :            : 
     138                 :            :     // calculate height of tree
     139                 :          0 :     int nHeight = 0;
     140 [ #  # ][ #  # ]:          0 :     while (CalcTreeWidth(nHeight) > 1)
     141                 :          0 :         nHeight++;
     142                 :            : 
     143                 :            :     // traverse the partial tree
     144         [ #  # ]:          0 :     TraverseAndBuild(nHeight, 0, vTxid, vMatch);
     145                 :          0 : }
     146                 :            : 
     147                 :          0 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
     148                 :            : 
     149                 :          0 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
     150                 :          0 :     vMatch.clear();
     151                 :            :     // An empty set will not work
     152         [ #  # ]:          0 :     if (nTransactions == 0)
     153                 :          0 :         return uint256();
     154                 :            :     // check for excessively high numbers of transactions
     155         [ #  # ]:          0 :     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         [ #  # ]:          0 :     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         [ #  # ]:          0 :     if (vBits.size() < vHash.size())
     162                 :          0 :         return uint256();
     163                 :            :     // calculate height of tree
     164                 :          0 :     int nHeight = 0;
     165         [ #  # ]:          0 :     while (CalcTreeWidth(nHeight) > 1)
     166                 :          0 :         nHeight++;
     167                 :            :     // traverse the partial tree
     168                 :          0 :     unsigned int nBitsUsed = 0, nHashUsed = 0;
     169                 :          0 :     uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
     170                 :            :     // verify that no problems occurred during the tree traversal
     171         [ #  # ]:          0 :     if (fBad)
     172                 :          0 :         return uint256();
     173                 :            :     // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
     174         [ #  # ]:          0 :     if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
     175                 :          0 :         return uint256();
     176                 :            :     // verify that all hashes were consumed
     177         [ #  # ]:          0 :     if (nHashUsed != vHash.size())
     178                 :          0 :         return uint256();
     179                 :          0 :     return hashMerkleRoot;
     180                 :          0 : }

Generated by: LCOV version 1.14