fuzz: split `coinselection` harness

brunoerg commented at 6:09 pm on February 14, 2025: contributor

This PR splits the coinselection fuzz harness into 3 targets (coinselection_bnb, coinselection_knapsack, coinselection_srd). The goal is to be able to fuzz each algorithm separately (to avoid performance issues) and also all of them together.

DrahtBot commented at 6:09 pm on February 14, 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/31870.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Stale ACK	zaidmstrr, marcofleon

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#31806 (fuzz: coinselection: cover SetBumpFeeDiscount by brunoerg)
#30080 (wallet: add coin selection parameter add_excess_to_recipient_position for changeless txs with excess that would be added to fees by remyers)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Tests on Feb 14, 2025

brunoerg marked this as ready for review on Feb 14, 2025

in src/wallet/test/fuzz/coinselection.cpp:223 in c6ab148559 outdated

220-{
221+enum class CoinSelectionAlgorithm {
222+    BNB,
223+    SRD,
224+    KNAPSACK,
225+    ALL

maflcko commented at 9:22 am on February 17, 2025:

nit: missing trailing comma.

Also, what is the point of combining them, when they are handled completely separate anyway?

brunoerg commented at 1:22 pm on February 17, 2025:

I just removed the ALL option. I don’t see anything that needs all of them combined.

in src/wallet/test/fuzz/coinselection.cpp:227 in c6ab148559 outdated

224+    KNAPSACK,
225+    ALL
226+};
227+
228+template<CoinSelectionAlgorithm Algorithm>
229+void FuzzCoinSelectionAlgorithm(const uint8_t* buffer, size_t size) {

maflcko commented at 9:22 am on February 17, 2025:

nit: please use std::span for new code

brunoerg commented at 1:20 pm on February 17, 2025:

Done

in src/wallet/test/fuzz/coinselection.cpp:289 in c6ab148559 outdated

302-    auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
303-    if (result_knapsack) {
304-        assert(result_knapsack->GetSelectedValue() >= target);
305-        assert(result_knapsack->GetWeight() <= max_selection_weight);
306-        result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
307-        (void)result_knapsack->GetShuffledInputVector();

maflcko commented at 9:28 am on February 17, 2025:

why remove this call?

brunoerg commented at 11:32 am on February 17, 2025:

There is no need to remove it, will put back. Probably missed it during the rework. Thanks.

brunoerg commented at 1:20 pm on February 17, 2025:

Done

brunoerg force-pushed on Feb 17, 2025

brunoerg commented at 1:23 pm on February 17, 2025: contributor

Force-pushed addressing #31870 (review), #31870 (review) and #31870 (review). Thanks, @maflcko.

in src/wallet/test/fuzz/coinselection.cpp:355 in aa27eeaaf3 outdated

350+FUZZ_TARGET(coinselection_srd) {
351+    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(std::span<const uint8_t>(buffer.data(), buffer.size()));
352+}
353+
354+FUZZ_TARGET(coinselection_knapsack) {
355+    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(std::span<const uint8_t>(buffer.data(), buffer.size()));

maflcko commented at 1:27 pm on February 17, 2025:

0    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);

nit: it is already a span,no?

brunoerg commented at 1:31 pm on February 17, 2025:

yes, done.

brunoerg force-pushed on Feb 17, 2025

DrahtBot added the label CI failed on Feb 17, 2025

DrahtBot removed the label CI failed on Feb 17, 2025

zaidmstrr commented at 8:32 pm on February 17, 2025: none

Hey, I’m reviewing this PR, as the description says that we can test each target separately, (coinselection_bnb, coinselection_knapsack, coinselection_srd) which is fine, but for the combined test I can’t find any fuzz target there like coinselection.

brunoerg commented at 8:37 pm on February 17, 2025: contributor

Hey, I’m reviewing this PR, as the description says that we can test each target separately, (coinselection_bnb, coinselection_knapsack, coinselection_srd) which is fine, but for the combined test I can’t find any fuzz target there like coinselection.

I just updated the description. I removed the coinselection target, so there are 3 ones.

zaidmstrr commented at 8:33 am on February 18, 2025: none

Tested ACK 9b293d0 The idea of fuzzing each algorithm independently seems good. I manually reviewed the new code changes with the previous ones to check for any missing statements. I also tested the code by manually inserting assert statements in between to check whether the desired behaviour was occurring or not.

marcofleon commented at 1:27 pm on February 21, 2025: contributor

Code review ACK 9b293d031c941dc6af0c4274e43388c57c702047

Knapsack is quite a bit slower than the other two, so separating them out is probably a good idea.

Coverage for the three targets: coinselection_bnb coinselection_srd coinselection_knapsack

in src/wallet/test/fuzz/coinselection.cpp:312 in 9b293d031c outdated

344+            (void)result_knapsack->GetShuffledInputVector();
345+            (void)result_knapsack->GetInputSet();
346+            // If the total balance is sufficient for the target and we are not using
347+            // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
348+            if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
349+                assert(result_knapsack);

maflcko commented at 2:05 pm on February 21, 2025:

why are you removing this check?

brunoerg commented at 2:54 pm on February 21, 2025:

Removing?

marcofleon commented at 2:59 pm on February 21, 2025:

Good catch. Took me a bit to see, but yeah this check should be outside of the inner if statement.

maflcko commented at 2:59 pm on February 21, 2025:

Previously the assert was exposed, now it is guarded by the same condition, making it dead code that the compiler will remove.

In other words: { if (a) assert(a); } is equivalent to { }.

brunoerg commented at 3:22 pm on February 21, 2025:

Ah, good catch! Gonna fix it, thanks.

brunoerg commented at 4:27 pm on February 21, 2025:

Done.

fuzz: split `coinselection` harness ba82240553

brunoerg force-pushed on Feb 21, 2025

brunoerg commented at 4:27 pm on February 21, 2025: contributor

Force-pushed addressing #31870 (review)

fuzz: split coinselection harness #31870

Code Coverage & Benchmarks

Reviews

Conflicts

fuzz: split `coinselection` harness #31870