Branch data     Line data    Source code

       1                 :             : // Copyright (c) 2025 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 <test/fuzz/fuzz.h>
       7                 :             : #include <test/fuzz/FuzzedDataProvider.h>
       8                 :             : #include <test/fuzz/util.h>
       9                 :             : #include <test/util/str.h>
      10                 :             : #include <util/strencodings.h>
      11                 :             : #include <hash.h>
      12                 :             : 
      13                 :             : #include <cassert>
      14                 :             : #include <cstdint>
      15                 :             : #include <vector>
      16                 :             : 
      17                 :         148 : uint256 ComputeMerkleRootFromPath(const CBlock& block, uint32_t position, const std::vector<uint256>& merkle_path) {
      18         [ -  + ]:         148 :     if (position >= block.vtx.size()) {
      19         [ #  # ]:           0 :         throw std::out_of_range("Position out of range");
      20                 :             :     }
      21                 :             : 
      22                 :         148 :     uint256 current_hash = block.vtx[position]->GetHash();
      23                 :             : 
      24         [ +  + ]:         944 :     for (const uint256& sibling : merkle_path) {
      25         [ +  + ]:         796 :         if (position % 2 == 0) {
      26                 :         600 :             current_hash = Hash(current_hash, sibling);
      27                 :             :         } else {
      28                 :         196 :             current_hash = Hash(sibling, current_hash);
      29                 :             :         }
      30                 :         796 :         position = position / 2;
      31                 :             :     }
      32                 :             : 
      33                 :         148 :     return current_hash;
      34                 :             : }
      35                 :             : 
      36         [ +  - ]:         959 : FUZZ_TARGET(merkle)
      37                 :             : {
      38                 :         513 :     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
      39                 :             : 
      40                 :         513 :     const bool with_witness = fuzzed_data_provider.ConsumeBool();
      41         [ +  + ]:         728 :     std::optional<CBlock> block {ConsumeDeserializable<CBlock>(fuzzed_data_provider, with_witness ? TX_WITH_WITNESS : TX_NO_WITNESS)};
      42         [ +  + ]:         513 :     if (!block){
      43                 :         337 :         return;
      44                 :             :     }
      45         [ +  - ]:         176 :     const size_t num_txs = block->vtx.size();
      46                 :         176 :     std::vector<uint256> tx_hashes;
      47         [ +  - ]:         176 :     tx_hashes.reserve(num_txs);
      48                 :             : 
      49         [ +  + ]:      378773 :     for (size_t i = 0; i < num_txs; ++i) {
      50         [ +  - ]:      378597 :         tx_hashes.push_back(block->vtx[i]->GetHash());
      51                 :             :     }
      52                 :             : 
      53                 :             :     // Test ComputeMerkleRoot
      54                 :         176 :     bool mutated = fuzzed_data_provider.ConsumeBool();
      55   [ +  -  +  - ]:         176 :     const uint256 merkle_root = ComputeMerkleRoot(tx_hashes, &mutated);
      56                 :             : 
      57                 :             :     // Basic sanity checks for ComputeMerkleRoot
      58         [ +  + ]:         176 :     if (tx_hashes.size() == 1) {
      59         [ -  + ]:          25 :         assert(merkle_root == tx_hashes[0]);
      60                 :             :     }
      61                 :             : 
      62                 :             : 
      63         [ +  - ]:         176 :     const uint256 block_merkle_root = BlockMerkleRoot(*block, &mutated);
      64         [ +  + ]:         176 :     if (tx_hashes.size() == 1) {
      65         [ -  + ]:          25 :         assert(block_merkle_root == tx_hashes[0]);
      66                 :             :     }
      67                 :             : 
      68         [ +  + ]:         176 :     if (!block->vtx.empty()){
      69         [ +  - ]:         173 :         const uint256 block_witness_merkle_root = BlockWitnessMerkleRoot(*block, &mutated);
      70         [ +  + ]:         173 :         if (tx_hashes.size() == 1) {
      71         [ -  + ]:          25 :             assert(block_witness_merkle_root == uint256());
      72                 :             :         }
      73                 :             :     }
      74                 :             : 
      75                 :             :     // Test TransactionMerklePath
      76         [ +  + ]:         176 :     const uint32_t position = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, num_txs > 0 ? num_txs - 1 : 0);
      77         [ +  - ]:         176 :     std::vector<uint256> merkle_path = TransactionMerklePath(*block, position);
      78                 :             : 
      79                 :             :     // Check that the root we compute from TransactionMerklePath equals the same merkle_root and block_merkle_root
      80         [ +  + ]:         176 :     if (tx_hashes.size() > 1) {
      81         [ +  - ]:         148 :         uint256 merkle_root_from_merkle_path = ComputeMerkleRootFromPath(*block, position, merkle_path);
      82         [ -  + ]:         148 :         assert(merkle_root_from_merkle_path == merkle_root);
      83         [ -  + ]:         148 :         assert(merkle_root_from_merkle_path == block_merkle_root);
      84                 :             :     }
      85                 :             : 
      86                 :             :     // Basic sanity checks for TransactionMerklePath
      87         [ -  + ]:         176 :     assert(merkle_path.size() <= 32); // Maximum depth of a Merkle tree with 2^32 leaves
      88         [ +  + ]:         176 :     if (num_txs == 1 || num_txs == 0) {
      89         [ -  + ]:          28 :         assert(merkle_path.empty()); // Single transaction has no path
      90                 :             :     }
      91                 :             : 
      92                 :         513 : }