fuzz: add target for coinselection algorithms #24602

mzumsande commented at 11:39 AM on March 17, 2022: member

This adds a fuzz target for the coinselection algorithms by creating random OutputGroups and running all three coin selection algorithms for them. It does not fuzz higher-level wallet logic for selecting eligible coins (as in SelectCoins()), thought it probably would make sense to have a fuzz target for that too.

mzumsande force-pushed on Mar 17, 2022

fanquake added the label Tests on Mar 17, 2022

fanquake requested review from achow101 on Mar 17, 2022

fanquake requested review from Xekyo on Mar 17, 2022

mzumsande force-pushed on Mar 17, 2022

in src/wallet/test/fuzz/coinselection.cpp:83 in e21d0b9df8 outdated

  75 | +    GroupCoins(fuzzed_data_provider, group_pos, utxo_pool, coin_params, /*positive_only=*/true);
  76 | +    std::vector<OutputGroup> group_all;
  77 | +    GroupCoins(fuzzed_data_provider, group_all, utxo_pool, coin_params, /*positive_only=*/false);
  78 | +
  79 | +    // Run coinselection algorithms
  80 | +    const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change);

achow101 commented at 9:54 PM on March 21, 2022:

I think the waste should be computed for this result as well.

mzumsande commented at 10:22 PM on March 21, 2022:

The call was moved inside of SelectCoinsBnB() with #24530 so it is being computed already and wouldn't add coverage - or do you mean another explicit call from the fuzz test?

achow101 commented at 10:30 PM on March 21, 2022:

oh yeah, forgot about that.

glozow commented at 11:30 AM on March 22, 2022: member

Nice, concept ACK

in src/wallet/test/fuzz/coinselection.cpp:28 in e21d0b9df8 outdated

  23 | +    CInputCoin coin(MakeTransactionRef(tx), nInput);
  24 | +    coin.m_input_bytes = nInputBytes;
  25 | +    input_coins.push_back(coin);
  26 | +}
  27 | +
  28 | +// Randomly distribute coins to OutputGroups

vasild commented at 1:10 PM on March 22, 2022:

nit

// Randomly distribute coins to output_groups

mzumsande commented at 10:44 PM on March 22, 2022:

I meant this as "to instances of OutputGroup", not the name of the local variable. Changed it to that.

in src/wallet/test/fuzz/coinselection.cpp:64 in e21d0b9df8 outdated

  59 | +    coin_params.m_long_term_feerate = long_term_fee_rate;
  60 | +    coin_params.m_effective_feerate = effective_fee_rate;
  61 | +
  62 | +    // Create some coins
  63 | +    CAmount total_balance{0};
  64 | +    int nextLockTime{0};

vasild commented at 1:21 PM on March 22, 2022:

nit, here and all over the newly added coinselection.cpp:

Variable (including function arguments) and namespace names are all lowercase and may use _ to separate words (snake_case).

https://github.com/bitcoin/bitcoin/blame/f05cf59d91eb03857dd9bdcc77607764da0349d2/doc/developer-notes.md#L88-L89

    int next_lock_time{0};

mzumsande commented at 10:45 PM on March 22, 2022:

Thanks, cleaned it up everywhere.

in src/wallet/test/fuzz/coinselection.cpp:17 in e21d0b9df8 outdated

  12 | +
  13 | +#include <vector>
  14 | +
  15 | +namespace wallet {
  16 | +
  17 | +static void AddCoin(std::vector<CInputCoin>& input_coins, const CAmount& nValue, const int nInput, const int nInputBytes, const int lockTime)

vasild commented at 1:35 PM on March 22, 2022:

style:

input and inout parameters should be ordered first and output parameters should come last

https://github.com/bitcoin/bitcoin/blame/f05cf59d91eb03857dd9bdcc77607764da0349d2/doc/developer-notes.md#L1329-L1331

mzumsande commented at 10:46 PM on March 22, 2022:

Changed the order here and in GroupCoins().

in src/wallet/test/fuzz/coinselection.cpp:35 in e21d0b9df8 outdated

  30 | +{
  31 | +    auto output_group = OutputGroup(coin_params);
  32 | +    bool valid_outputgroup{false};
  33 | +    for (auto& coin : coins) {
  34 | +        output_group.Insert(coin, /*depth=*/0, /*from_me=*/true, /*ancestors=*/0, /*descendants=*/0, positive_only);
  35 | +        valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;

vasild commented at 3:25 PM on March 22, 2022:

Looking at the body of OutputGroup::Insert() I can't see how valid_outputgroup can become false. What do I miss?

mzumsande commented at 10:47 PM on March 22, 2022:

The problem I tried to address here is that OutputGroup::Insert() may not insert anything but just return if positive_only is true. In that case, we might have an empty OutputGroup with GetSelectionAmount() == 0 which would make SelectCoinsBnB() assert, so it cannot be submitted. I added a comment for this.

in src/wallet/test/fuzz/coinselection.cpp:75 in e21d0b9df8 outdated

  67 | +        const int nInput{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
  68 | +        const int nInputBytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(100, 10000)};
  69 | +        const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
  70 | +        AddCoin(utxo_pool, amount, nInput, nInputBytes, ++nextLockTime);
  71 | +        total_balance += amount;
  72 | +    }

vasild commented at 3:39 PM on March 22, 2022:

A few iterations of this could lead to total_balance being bigger than MAX_MONEY. Could this trigger some assert in the tested functions?

mzumsande commented at 10:48 PM on March 22, 2022:

Good catch! I'm actually not sure. But I added a break statement to the loop for this case, which (at least I hope!) can't happen in reality and therefore doesn't need fuzzing.

in src/wallet/test/fuzz/coinselection.cpp:43 in e21d0b9df8 outdated

  39 | +            valid_outputgroup = false;
  40 | +        }
  41 | +    }
  42 | +    if (valid_outputgroup) output_groups.push_back(output_group);
  43 | +    return;
  44 | +}

vasild commented at 4:59 PM on March 22, 2022:

This return; is unnecessary.

mzumsande commented at 10:49 PM on March 22, 2022:

Removed it.

mzumsande force-pushed on Mar 22, 2022

mzumsande commented at 10:50 PM on March 22, 2022: member

Thanks for the review! I addressed the comments by @vasild and rebased on master.

MarcoFalke added the label Needs rebase on Mar 25, 2022

DrahtBot removed the label Needs rebase on Mar 25, 2022

mzumsande force-pushed on Mar 27, 2022

mzumsande commented at 4:57 PM on March 27, 2022: member

Needs rebase?

Definitely. Rebased after #24091 and #24494 were merged.

vasild approved

vasild commented at 2:04 PM on March 29, 2022: member

ACK 591c108ec82aca71a8b9b420c2465d5d32bf9abc

Thanks for the explanations. I tried running this for a while and did not see any failures. Also tried disabling the LIMITED_WHILE in the code to be sure that it does not brick with empty group_pos and group_all.

in src/wallet/test/fuzz/coinselection.cpp:17 in 591c108ec8 outdated

  12 | +
  13 | +#include <vector>
  14 | +
  15 | +namespace wallet {
  16 | +
  17 | +static void AddCoin(const CAmount& value, const int n_input, const int n_input_bytes, const int locktime, std::vector<COutput>& coins)

vasild commented at 2:10 PM on March 29, 2022:

nit: const int function parameters make little sense and are sometimes confusing.

https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#f16-for-in-parameters-pass-cheaply-copied-types-by-value-and-others-by-reference-to-const

mzumsande commented at 3:19 PM on March 30, 2022:

done, thanks

in src/wallet/test/fuzz/coinselection.cpp:50 in 591c108ec8 outdated

  45 | +FUZZ_TARGET(coinselection)
  46 | +{
  47 | +    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
  48 | +    std::vector<COutput> utxo_pool;
  49 | +
  50 | +    const CFeeRate long_term_fee_rate{CFeeRate(ConsumeMoney(fuzzed_data_provider, /*max=*/COIN))};

MarcoFalke commented at 5:48 PM on March 29, 2022:

nit: One constructor should be sufficient.

    const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};

mzumsande commented at 3:20 PM on March 30, 2022:

Yes, copy/paste mistake, corrected.

in src/wallet/test/fuzz/coinselection.cpp:57 in 591c108ec8 outdated

  52 | +    const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
  53 | +    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
  54 | +    const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
  55 | +
  56 | +    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
  57 | +    auto coin_params = CoinSelectionParams(fast_random_context);

MarcoFalke commented at 5:51 PM on March 29, 2022:

nit: No auto and no =.

    CoinSelectionParams coin_params{fast_random_context};

mzumsande commented at 3:20 PM on March 30, 2022:

changed.

MarcoFalke approved

MarcoFalke commented at 5:53 PM on March 29, 2022: member

Concept ACK

fuzz: add target for coinselection

This creates random OutputGroups and runs the
existing coinselection algorithms for them.

21520b9551

mzumsande force-pushed on Mar 30, 2022

mzumsande commented at 3:21 PM on March 30, 2022: member

Pushed an update addressing feedback.

vasild approved

vasild commented at 2:17 PM on March 31, 2022: member

ACK 21520b95515676d45145df624f430cdd39db7515

MarcoFalke added the label Wallet on Mar 31, 2022

MarcoFalke assigned achow101 on Mar 31, 2022

achow101 commented at 4:58 PM on March 31, 2022: member

ACK 21520b95515676d45145df624f430cdd39db7515

achow101 merged this on Mar 31, 2022

achow101 closed this on Mar 31, 2022

mzumsande deleted the branch on Apr 6, 2022

DrahtBot locked this on Apr 6, 2023