test: added fuzz coverage for consensus/merkle.cpp

kevkevinpal commented at 3:16 am on April 10, 2025: contributor

Summary

This adds a new fuzz target “merkle” which adds fuzz coverage to consensus/merkle.cpp

I can also add this to an existing fuzz target if that is preferable

Before: Screenshot 2025-04-09 at 10 12 54 PM

After: Screenshot 2025-04-11 at 4 20 41 PM

DrahtBot commented at 3:16 am on April 10, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32243.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	marcofleon

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

DrahtBot added the label Tests on Apr 10, 2025

DrahtBot added the label CI failed on Apr 10, 2025

DrahtBot commented at 4:25 am on April 10, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/40295372010

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

kevkevinpal force-pushed on Apr 10, 2025

kevkevinpal marked this as a draft on Apr 10, 2025

kevkevinpal commented at 6:41 pm on April 10, 2025: contributor

marking as draft, I want to resolve the lint failure and address other changes I want to make

kevkevinpal force-pushed on Apr 11, 2025

DrahtBot removed the label CI failed on Apr 11, 2025

kevkevinpal marked this as ready for review on Apr 12, 2025

in src/test/fuzz/merkle.cpp:43 in b4dfd362ef outdated

38+            prevout_hash_bytes.resize(32, 0); // Pad with zeros if needed
39+        }
40+        uint256 prevout_hash;
41+        memcpy(prevout_hash.begin(), prevout_hash_bytes.data(), 32);
42+        txin.prevout = COutPoint(Txid::FromUint256(prevout_hash), fuzzed_data_provider.ConsumeIntegral<uint32_t>());
43+        std::vector<unsigned char> script_sig_bytes = fuzzed_data_provider.ConsumeBytes<unsigned char>(40);

Christewart commented at 5:39 pm on April 13, 2025:

I’m new to the fuzzing test framework, but does this essentially build a fixed size 40 byte scriptSig?

It may be worth making this variable in size to test different weaknesses in the merkle tree.

Particularly if we can occasionally generate a 64 byte transaction, whose format you can read about here, you may be able to make some assertions on the mutated field below.

kevkevinpal commented at 3:11 pm on April 16, 2025:

Thanks for the review! I pushed cdd3ad0

Now I am using the MAX_SCRIPT_SIZE since that is what I see for the IsUnspendable function for CScript

kevkevinpal force-pushed on Apr 16, 2025

kevkevinpal commented at 3:16 pm on April 16, 2025: contributor

In cdd3ad0 we are now also fuzzing BlockWitnessMerkleRoot and BlockMerkleRoot so we are fuzzing everything in src/consensus/merkle.h

DrahtBot added the label CI failed on Apr 29, 2025

DrahtBot removed the label CI failed on May 2, 2025

in src/test/fuzz/merkle.cpp:103 in cdd3ad098c outdated

78+            assert(block_witness_merkle_root == uint256());
79+        }
80+    }
81+
82+    // Test TransactionMerklePath
83+    const uint32_t position = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, num_txs);

marcofleon commented at 2:57 pm on May 6, 2025:

This should be 0 to num_txs - 1 no? Just based on the coverage it seems the fuzzer is choosing num_txs which means matchh won’t be set to true here: https://github.com/bitcoin/bitcoin/blob/baa848b8d38187ce6b24a57cfadf1ea180209711/src/consensus/merkle.cpp#L111

kevkevinpal commented at 3:19 pm on May 7, 2025:

Yes that makes sense to me!

updated in 2c8a2b4

in src/test/fuzz/merkle.cpp:61 in cdd3ad098c outdated

56+        tx_hashes.push_back(block.vtx[i]->GetHash());
57+    }
58+
59+    // Test ComputeMerkleRoot
60+    bool mutated = fuzzed_data_provider.ConsumeBool();
61+    //bool mutated = false;

marcofleon commented at 3:19 pm on May 6, 2025:

Meant to remove this line?

kevkevinpal commented at 3:19 pm on May 7, 2025:

oops, thanks for the review!

updated in 2c8a2b4

marcofleon commented at 3:23 pm on May 6, 2025: contributor

Good stuff, nice to have new coverage.

I think it’d be worth it to add an oracle in the test where you reconstruct the merkle root with the path you get from TransactionMerklePath and verify that it matches the root from the earlier ComputeMerkleRoot call.

kevkevinpal force-pushed on May 7, 2025

kevkevinpal commented at 3:21 pm on May 7, 2025: contributor

Good stuff, nice to have new coverage.

I think it’d be worth it to add an oracle in the test where you reconstruct the merkle root with the path you get from TransactionMerklePath and verify that it matches the root from the earlier ComputeMerkleRoot call.

Thank you for the review!

In 2c8a2b4 I added a helper function ComputeMerkleRootFromPath to help rebuild the root so then I could compare the responses from TransactionMerklePath, BlockMerkleRoot and also ComputeMerkleRoot

let me know if that looks good of if there is anything you’d like to change!

kevkevinpal force-pushed on May 7, 2025

DrahtBot added the label CI failed on May 7, 2025

DrahtBot commented at 3:23 pm on May 7, 2025: contributor

🚧 At least one of the CI tasks failed. Task lint: https://github.com/bitcoin/bitcoin/runs/41809311683 LLM reason (✨ experimental): The CI failure is caused by a lint error, specifically due to the use of quote syntax includes instead of bracket syntax.

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

in src/test/fuzz/merkle.cpp:103 in 2c8a2b459e outdated

 98+            assert(block_witness_merkle_root == uint256());
 99+        }
100+    }
101+
102+    // Test TransactionMerklePath
103+    const uint32_t position = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, num_txs - 1);

brunoerg commented at 6:16 pm on May 7, 2025:

/ci_container_base/src/test/fuzz/merkle.cpp:103:96: runtime error: unsigned integer overflow: 0 - 1 cannot be represented in type 'size_t' (aka 'unsigned long')

. num_txs can be zero, so it’s causing the overflow here.

kevkevinpal commented at 6:22 pm on May 7, 2025:

ahh that makes sense, I can revert it back to what I had previously

kevkevinpal commented at 6:23 pm on May 7, 2025:

changed back to just num_txs in 7c80dcd

brunoerg commented at 7:10 pm on May 7, 2025:

changed back to just num_txs in 7c80dcd

I think that using just num_txs is not correct since it’s a position, you could add something like num_txs > 0 ? num_txs - 1 : 0.

kevkevinpal commented at 7:17 pm on May 7, 2025:

that works with me! updated in 0fe4e7d

kevkevinpal force-pushed on May 7, 2025

DrahtBot removed the label CI failed on May 8, 2025

in src/test/fuzz/merkle.cpp:64 in 0fe4e7d186 outdated

59+            prevout_hash_bytes.resize(32, 0); // Pad with zeros if needed
60+        }
61+        uint256 prevout_hash;
62+        memcpy(prevout_hash.begin(), prevout_hash_bytes.data(), 32);
63+        txin.prevout = COutPoint(Txid::FromUint256(prevout_hash), fuzzed_data_provider.ConsumeIntegral<uint32_t>());
64+        std::vector<unsigned char> script_sig_bytes = fuzzed_data_provider.ConsumeBytes<unsigned char>(MAX_SCRIPT_SIZE);

marcofleon commented at 2:55 pm on May 8, 2025:

I think it would be better to consume from a range here and below. MAX_SCRIPT_SIZE is large (10000) so the fuzzer ends up consuming the remaining bytes in the data provider at this line.

edit: This is what was actually causing the lack of coverage for matchh it seems, as position is always 0 later in the test. I’m not sure how long it would take for the provider to have enough bytes… but still, I think ~~ConsumeIntegralInRange~~ ConsumeRandomLengthByteVector makes sense here in place of ConsumeBytes.

kevkevinpal commented at 8:16 pm on May 8, 2025:

Good catch! You’re right it doesnt make sense to always have the MAX_SCRIPT_SIZE we should instead use in that range

updated in 0fc30f2

brunoerg commented at 8:33 pm on May 8, 2025:

Why not using ConsumeScript to create the scriptPubKey and scriptSig?

kevkevinpal commented at 8:56 pm on May 8, 2025:

Would using ConsumeTransaction make sense and just pushing that transaction into the block?

kevkevinpal commented at 8:57 pm on May 8, 2025:

I used ConsumeTransaction in 44298f0

let me know if that looks good or if you would prefer to use ConsumeScript

brunoerg commented at 3:13 pm on May 9, 2025:

ConsumeTransaction is fine.

kevkevinpal force-pushed on May 8, 2025

test: added fuzz coverage to consensus/merkle.cpp

This adds a new fuzz target merkle which adds fuzz coverage to
consensus/merkle.cpp

44298f0cb9

kevkevinpal force-pushed on May 8, 2025

marcofleon commented at 2:20 pm on May 9, 2025: contributor

ACK 44298f0cb9c3de42b1c0f464c0d7b2779aa4c3b7

Using ConsumeTransaction works, and makes sense. Here’s the coverage. Everything lgtm!

test: added fuzz coverage for consensus/merkle.cpp #32243

Summary

Code Coverage & Benchmarks

Reviews