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