merkle.cpp raw

   1  // Copyright (c) 2025-present 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  uint256 ComputeMerkleRootFromPath(const CBlock& block, uint32_t position, const std::vector<uint256>& merkle_path) {
  18      if (position >= block.vtx.size()) {
  19          throw std::out_of_range("Position out of range");
  20      }
  21  
  22      uint256 current_hash = block.vtx[position]->GetHash().ToUint256();
  23  
  24      for (const uint256& sibling : merkle_path) {
  25          if (position % 2 == 0) {
  26              current_hash = Hash(current_hash, sibling);
  27          } else {
  28              current_hash = Hash(sibling, current_hash);
  29          }
  30          position = position / 2;
  31      }
  32  
  33      return current_hash;
  34  }
  35  
  36  FUZZ_TARGET(merkle)
  37  {
  38      FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
  39  
  40      const bool with_witness = fuzzed_data_provider.ConsumeBool();
  41      std::optional<CBlock> block {ConsumeDeserializable<CBlock>(fuzzed_data_provider, with_witness ? TX_WITH_WITNESS : TX_NO_WITNESS)};
  42      if (!block){
  43          return;
  44      }
  45      const size_t num_txs = block->vtx.size();
  46      std::vector<uint256> tx_hashes;
  47      tx_hashes.reserve(num_txs);
  48  
  49      for (size_t i = 0; i < num_txs; ++i) {
  50          tx_hashes.push_back(block->vtx[i]->GetHash().ToUint256());
  51      }
  52  
  53      // Test ComputeMerkleRoot
  54      bool mutated = fuzzed_data_provider.ConsumeBool(); // output param, initial value shouldn't matter
  55      const uint256 merkle_root = ComputeMerkleRoot(tx_hashes, fuzzed_data_provider.ConsumeBool() ? &mutated : nullptr);
  56  
  57      // Basic sanity checks for ComputeMerkleRoot
  58      if (tx_hashes.size() == 1) {
  59          assert(merkle_root == tx_hashes[0]);
  60      }
  61  
  62  
  63      const uint256 block_merkle_root = BlockMerkleRoot(*block, &mutated);
  64      if (tx_hashes.size() == 1) {
  65          assert(block_merkle_root == tx_hashes[0]);
  66      }
  67  
  68      if (!block->vtx.empty()){
  69          const uint256 block_witness_merkle_root = BlockWitnessMerkleRoot(*block);
  70          if (tx_hashes.size() == 1) {
  71              assert(block_witness_merkle_root == uint256());
  72          }
  73      }
  74  
  75      // Test TransactionMerklePath
  76      const uint32_t position = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, num_txs > 0 ? num_txs - 1 : 0);
  77      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      if (tx_hashes.size() > 1) {
  81          uint256 merkle_root_from_merkle_path = ComputeMerkleRootFromPath(*block, position, merkle_path);
  82          assert(merkle_root_from_merkle_path == merkle_root);
  83          assert(merkle_root_from_merkle_path == block_merkle_root);
  84      }
  85  
  86      // Basic sanity checks for TransactionMerklePath
  87      assert(merkle_path.size() <= 32); // Maximum depth of a Merkle tree with 2^32 leaves
  88      if (num_txs == 1 || num_txs == 0) {
  89          assert(merkle_path.empty()); // Single transaction has no path
  90      }
  91  
  92  }
  93