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

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!

in src/test/fuzz/merkle.cpp:11 in 44298f0cb9 outdated

 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 <logging.h>

brunoerg commented at 9:40 am on May 11, 2025:

Why does it need logging.h?

kevkevinpal commented at 12:50 pm on May 11, 2025:

thanks!

removed in c5245d1

kevkevinpal force-pushed on May 11, 2025

in src/test/fuzz/merkle.cpp:46 in c5245d1a76 outdated

41+    const size_t num_txs = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 1000);
42+    std::vector<uint256> tx_hashes;
43+    tx_hashes.reserve(num_txs);
44+
45+    // Create a CBlock with fuzzed transactions
46+    CBlock block;

brunoerg commented at 4:50 pm on May 12, 2025:

Couldn’t you use ConsumeDeserializable to create a CBlock? I think it might simplify the way you’re creating the block and the transactions.

kevkevinpal commented at 4:02 pm on May 13, 2025:

I pushed f99fd0b which now uses ConsumeDeserializable

I haven’t used ConsumeDeserializable so I’m not 100% sure if I’m using it correctly.

kevkevinpal force-pushed on May 13, 2025

in src/test/fuzz/merkle.cpp:50 in f99fd0b87d outdated

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+        const auto mtx = ConsumeTransaction(fuzzed_data_provider, std::nullopt);

brunoerg commented at 5:06 pm on May 13, 2025:

f99fd0b87dcfaf84784ce423f78a950ad377b36b: Now that you’re using ConsumeDeserializable to create a CBlock, maybe you don’t to create the transactions using ConsumeTransaction anymore?

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

yea I tried doing that but then I was getting less coverage for some reason not sure if I just need to let the fuzzer run longer

Without ConsumeTransaction

0[#657589](/bitcoin-bitcoin/657589/) REDUCE cov: 813 ft: 3922 corp: 309/188Kb lim: 4096 exec/s: 8323 rss: 359Mb L: 941/3853 MS: 1 EraseBytes-

With ConsumeTransaction

0[#14901](/bitcoin-bitcoin/14901/)  REDUCE cov: 1461 ft: 8651 corp: 536/449Kb lim: 4096 exec/s: 3725 rss: 350Mb L: 677/4093 MS: 1 EraseBytes-

I can try running the fuzz test for a while and see if it adds cov

kevkevinpal commented at 2:13 pm on June 3, 2025:

ok I pushed and seems like the cirrus ci fuzzer had more coverage than my local machine did

[12:12:07.876] merkle [#156207](/bitcoin-bitcoin/156207/) DONE cov: 2645 ft: 12427 corp: 710/97Kb lim: 301 exec/s: 2560 rss: 212Mb

kevkevinpal force-pushed on May 16, 2025

kevkevinpal commented at 12:46 pm on May 16, 2025: contributor

I pushed caaed67 which does not include ConsumeTransaction but I am still trying to see if this will add more coverage compared to f99fd0b

kevkevinpal commented at 2:14 pm on June 3, 2025: contributor

I pushed caaed67 which does not include ConsumeTransaction but I am still trying to see if this will add more coverage compared to f99fd0b

Looks like the runner had significant coverage, should be good for review

[12:12:07.876] merkle [#156207](/bitcoin-bitcoin/156207/) DONE cov: 2645 ft: 12427 corp: 710/97Kb lim: 301 exec/s: 2560 rss: 212Mb

in src/test/fuzz/CMakeLists.txt:138 in caaed67232 outdated

134@@ -135,6 +135,7 @@ add_executable(fuzz
135   validation_load_mempool.cpp
136   vecdeque.cpp
137   versionbits.cpp
138+  merkle.cpp

marcofleon commented at 1:17 pm on June 6, 2025:

This should be before merkleblock.cpp.

kevkevinpal commented at 3:29 pm on June 6, 2025:

Thanks! That makes sense, updated in 95969bc

test: added fuzz coverage to consensus/merkle.cpp

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

95969bc58a

kevkevinpal force-pushed on Jun 6, 2025

marcofleon commented at 5:09 pm on June 6, 2025: contributor

ReACK 95969bc58ae0cd928e536d7cb8541de93e8c7205

Swtiched from ConsumeTransaction to ConsumeDeserializable since my last review. Coverage looks good!

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

Summary

Code Coverage & Benchmarks

Reviews