coinselection
#27585
This PR:
CreateCoins.EligibleForSpendingAddInputs: get result of each algorithm (srd, knapsack and bnb), call CreateCoins and add into them.GetShuffledInputVector and GetInputSet using the result of each algorithm (srd, knapsack and bnb).Merge: Call SRD with the new utxos and, if successful, try to merge with the previous SRD result.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | furszy, murchandamus, achow101 |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
No conflicts as of last run.
124+ return std::make_shared<COutput>(output);
125+ });
126+
127+ if (result_srd) result_srd->AddInputs(utxos_set, subtract_fee_outputs);
128+ if (result_knapsack) result_knapsack->AddInputs(utxos_set, subtract_fee_outputs);
129+ if (result_bnb) result_bnb->AddInputs(utxos_set, subtract_fee_outputs);
If CreateCoins generates a coin that is already inside any of the results, AddInputs will throw a runtime error, which the fuzzing framework will detect as a failure when it is not. It is part of the class boundaries.
Same apply for the fuzz Merge function commit.
If CreateCoins generates a coin that is already inside any of the results, AddInputs will throw a runtime error, which the fuzzing framework will detect as a failure when it is not. It is part of the class boundaries.
Yes, that’s why it calls CreateCoins twice and with different “utxos pool”. Is there any risk yet?
next_locktime which ensures that all UTXOs receive a different hash even when the fuzzer provided the same data for them.
So, nvm. A comment wouldn’t hurt but nothing serious.
50+ CAmount total_balance{0};
51+ int next_locktime{0};
52+ LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
53+ {
54+ const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
55+ const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(100, 10000)};
Let’s allow the lower bound of what’s possible:
0 const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
121+ }
122
123 auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
124- if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
125+ if (result_srd) {
126+ result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
It’s not clear to me why the ComputeAndSetWaste() is called with these parameters. The first should be min_viable_change which should be bigger than change_fee but not really related to cost_of_change. I guess that’s fine for this test. It’s also not clear to me, though why the change_fee is set to 0 here. Wouldn’t it be better to have it derive from the current coin_params?
coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
Not sure if it adds interesting test coverage here, but I could see some ComputeAndSetWaste() come to different conclusions occasionally when a fee is considered.
I didn’t touch ComputeAndSetWaste parameters value, perhaps who did it copied (?) from: https://github.com/bitcoin/bitcoin/blob/34ac3f438a268e83af6cd11e2981e5bc07f699c9/src/wallet/coinselection.cpp#L179
I’m going to change it to make it more “realistic”/robust.
I’m pretty new to fuzz testing, so I am not sure whether we want to have all these additional calls for each selection result. It seems to me that if we wanted to test the behavior of SelectionResult, it might make more sense to separately fuzz that instead of fuzzing that in the context of running all the different coin selection algorithms, since it might lower the number of executions we get on fuzzing coin selection.
OTOH, it’s great to get fuzzing coverage for these codepaths.
Code changes look good to me.
Tentative ACK d5282a45bd452844dc815181825e3dd46133ac51, except that I’d be curious to hear what others think about expanding the responsibility of this fuzz target vs adding a second fuzz target for testing SelectionResult.
124+ }
125
126 auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
127- if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
128+ if (result_srd) {
129+ result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
min_viable_change is smaller than m_change_fee as mentioned above, also see https://github.com/bitcoin/bitcoin/pull/27846
ACK 2d739a425c92e2dd409c45273e8e376d39ead1cc
My concern about the min_viable_change and change_fee causing issues did not substantiate after some light fuzzing. Since it does not seem to cause crashes, having independent values for the two parameters may be better. Thanks for adding more coverage.
123+ CreateCoins(fuzzed_data_provider, utxos, coin_params);
124+ std::transform(utxos.begin(), utxos.end(),
125+ std::inserter(utxos_set, utxos_set.begin()),
126+ [](const COutput& output) {
127+ return std::make_shared<COutput>(output);
128+ });
std::vector<COutput> to std::vector<std::shared_ptr<COutput>>
100@@ -101,16 +101,23 @@ FUZZ_TARGET(coinselection)
101
102 // Run coinselection algorithms
103 auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change, MAX_STANDARD_TX_WEIGHT);
104+ if (result_bnb) {
105+ (void)result_bnb->GetShuffledInputVector();
106+ }
GetChange() is always 0?
ComputeSetAndWaste which checks change. Any unexpected action regarding it would affect the assertion - assert(best_waste == result.GetWaste());.
I think that it worth. One of fuzzing goals is to assert expected behavior externally. Black-box style. So if the internal implementation changes by mistake (or if there is a way to by-pass the expected behavior that we aren’t aware of), the fuzzer catches it.
Also, the internal BnB ComputeSetAndWaste call checks that the final selection is within a certain range: target <= value < target + change cost. It is indirectly checking GetChange() result but I don’t think that we should rely on that. If change_cost is also 0, the GetChange result doesn’t really matter, the same code will be executed in both branches of the ComputeAndSetWaste function.
144+ std::vector<OutputGroup> new_group_pos;
145+ GroupCoins(fuzzed_data_provider, utxos, coin_params, /*positive_only=*/true, new_group_pos);
146+ auto new_srd = SelectCoinsSRD(new_group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
147+ if (new_srd && result_srd) {
148+ new_srd->Merge(result_srd.value());
149+ }
In d72c0926:
Should check the Merge outcome. e.g. the result target and weight need to be the sum of the two merged targets and weights. Moreover, if one result uses the effective value and the other one not, the use_effective field must be updated.
Left few comments. I think that we could go further in few places and check that the called functions are actually doing what they suppose to be doing.
For instance, all valid results must have a target below the sum of the selected inputs amounts. Also, waste on results with more difference between target and inputs sum should be greater than results with closer diff between target and inputs sum.
Force-pushed:
Addressed:
Also, I added support for GetSelectedValue(), asserting that its value is always greater or equal than target in a valid result.
147+ const CAmount old_target{new_srd->GetTarget()};
148+ const int old_weight{new_srd->GetWeight()};
149+ new_srd->Merge(result_srd.value());
150+ assert(new_srd->GetTarget() == old_target + result_srd->GetTarget());
151+ assert(new_srd->GetWeight() == old_weight + result_srd->GetWeight());
152+ }
Could also check the resulting inputs size and the use_effective_fee field.
Also, we only use of the Merge function in the sources to combine a MANUAL selection with one of the automatic selections. We never combine two srd solutions.
126+ utxos_set.insert(std::make_shared<COutput>(utxo));
127+ }
128+
129+ if (result_srd) result_srd->AddInputs(utxos_set, subtract_fee_outputs);
130+ if (result_knapsack) result_knapsack->AddInputs(utxos_set, subtract_fee_outputs);
131+ if (result_bnb) result_bnb->AddInputs(utxos_set, subtract_fee_outputs);
76@@ -77,7 +77,7 @@ FUZZ_TARGET(coinselection)
77 const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
78 const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
79 const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
80- const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
81+ const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(50000, MAX_MONEY)};
1000. but the reason is to make it more realistic. e.g. do we really use it for 1 sat?
Force-pushed:
Merge: now it checks the input set and it tries to merge every solution with a “manual” one.AddInputs to check the total weight.154@@ -144,6 +155,21 @@ FUZZ_TARGET(coinselection)
155 assert(result->GetWeight() > weight);
156 }
157 }
158+
159+ std::vector<COutput> manual_utxos;
160+ CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_utxos, coin_params)};
161+ if (manual_balance <= 0) return;
162+ for (auto& result : results) {
163+ if (!result) break;
continue?
126+ std::set<std::shared_ptr<COutput>> utxos_set;
127+ for (const auto& utxo : utxos) {
128+ utxos_set.insert(std::make_shared<COutput>(utxo));
129+ }
130+ for (auto& result : results) {
131+ if (!result) break;
continue?
129+ }
130+ for (auto& result : results) {
131+ if (!result) break;
132+ const auto weight{result->GetWeight()};
133+ result->AddInputs(utxos_set, subtract_fee_outputs);
134+ assert(result->GetWeight() > weight);
154@@ -144,6 +155,21 @@ FUZZ_TARGET(coinselection)
155 assert(result->GetWeight() > weight);
156 }
157 }
158+
159+ std::vector<COutput> manual_utxos;
160+ CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_utxos, coin_params)};
161+ if (manual_balance <= 0) return;
159+ std::vector<COutput> manual_utxos;
160+ CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_utxos, coin_params)};
161+ if (manual_balance <= 0) return;
162+ for (auto& result : results) {
163+ if (!result) break;
164+ auto manual_selection{ManualSelection(manual_utxos, manual_balance, coin_params.m_subtract_fee_outputs)};
164+ auto manual_selection{ManualSelection(manual_utxos, manual_balance, coin_params.m_subtract_fee_outputs)};
165+ const CAmount old_target{result->GetTarget()};
166+ const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
167+ const int old_weight{result->GetWeight()};
168+ result->Merge(manual_selection);
169+ assert(result->GetInputSet().size() > input_set.size());
0assert(result->GetInputSet().size() == input_set.size() + manual_utxos.size());
117@@ -118,6 +118,22 @@ FUZZ_TARGET(coinselection)
118 if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
119 assert(result_knapsack);
120 }
121+
122+ std::vector<COutput> utxos;
123+ std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb};
124+ CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params)};
125+ if (new_total_balance > 0) {
126+ std::set<std::shared_ptr<COutput>> utxos_set;
70+ SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
71+ std::set<std::shared_ptr<COutput>> utxos_set;
72+ for (const auto& utxo : utxos) {
73+ utxos_set.insert(std::make_shared<COutput>(utxo));
74+ }
75+ result.AddInputs(utxos_set, subtract_fee_outputs);
Nit:
0 std::set<std::shared_ptr<COutput>> utxo_pool;
1 for (const auto& utxo : utxos) {
2 utxo_pool.insert(std::make_shared<COutput>(utxo));
3 }
4 result.AddInputs(utxo_pool, subtract_fee_outputs);
154@@ -144,6 +155,21 @@ FUZZ_TARGET(coinselection)
155 assert(result->GetWeight() > weight);
156 }
157 }
158+
159+ std::vector<COutput> manual_utxos;
manual_inputs.
87@@ -88,7 +88,7 @@ FUZZ_TARGET(coinselection)
88 const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
89 const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
90 const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
91- const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
While we don’t broadcast transactions with outputs of that amount (except OP_RETURN maybe), if it doesn’t break anywhere, a target of 1 ṩ should maybe be legal for coin selection?
IIRC, Bitcoin Core permits 294 ṩ for P2WPKH outputs, so it should at least not be bigger than that.
assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
Ah, my bad, I thought this target referred to the sum of recipient outputs, but it’s actually recipient_sum + not_input_fees.
Is it possible that this then would need to be at least as large as the cost for the header + change output? 1000 ṩ might not be enough for every feerate then.
I got a crash after 130k attempts when I tried to lower the target to 1 ṩ. Gonna fuzz with the 1000 ṩ tonight, will revisit tomorrow.
The fuzz test crashed for me after 7.4M attempts:
fuzz: ../../src/wallet/test/fuzz/coinselection.cpp:120: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.`
You should be able to replicate the issue with:
0$ echo "MP3//////wT/LzMBEABL////////Wv///yWyEABLAADoQP//PP//CAAAPQAAAAAAAAAAPQEAAAAA AAAA/V12+w==" | base64 -d > crash.input
1$ FUZZ=coinselection src/test/fuzz/fuzz crash.input
I don’t think that an absolute value will work. My guess is that the crash may be caused by m_cost_of_change being generated randomly independent from m_change_fee. Usually, cost_of_change cannot ever be smaller than m_change_fee, so if it happens to be smaller here, it may interfere with the change calculation?
I attempted to calculate cost_of_change instead from m_change_fee + input_size×LTFRE, leaving the fuzz input consumption unchanged. It made the test pass:
0@@ -97,9 +97,9 @@ FUZZ_TARGET(coinselection)
1 coin_params.m_long_term_feerate = long_term_fee_rate;
2 coin_params.m_effective_feerate = effective_fee_rate;
3 coin_params.min_viable_change = min_viable_change;
4- coin_params.m_cost_of_change = cost_of_change;
5 coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
6 coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
7+ coin_params.m_cost_of_change = coin_params.m_change_fee + long_term_fee_rate.GetFee(58);
I’m about 2.1M runs in, and no issues so far. :smile:
I don’t think that an absolute value will work. My guess is that the crash may be caused by m_cost_of_change being generated randomly independent from m_change_fee. Usually, cost_of_change cannot ever be smaller than m_change_fee, so if it happens to be smaller here, it may interfere with the change calculation?
Bingo, I think so!
Also, in long_term_fee_rate.GetFee(58) why 58?
That was loosely inspired by the vsize of a P2TR input (rounded up).
I’m just seeing that we are calculating the cost_of_change actually with the discard_feerate rather than the LTFRE, though:
src/wallet/spend.cpp: coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee;
You could then also make the change_spend_size or change_input_size a random variable in the range 41…1000. Inputs cannot ever be smaller than 41 vB (32+4+4+1).
cost_of_change according to spend.cpp, it avoids any issue with low targets.
Code changes look good to me, crACK d501e1a2283d82b833260bf3372512d616a62a4c
Started some fuzzing, will let you know if it finds anything.
My fuzzer has performed over 10M runs without uncovering an issue.
ACK https://github.com/bitcoin/bitcoin/commit/d501e1a2283d82b833260bf3372512d616a62a4c
44@@ -45,6 +45,37 @@ static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vect
45 if (valid_outputgroup) output_groups.push_back(output_group);
46 }
47
48+static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params)
49+{
50+ // Create some coins
51+ CAmount total_balance{0};
52+ int next_locktime{0};
Need to make next_locktime a global variable (or receive it as ref here).
This variable prevents CreateCoins from generating duplicated transaction hashes (look at AddCoin()). If the variable is reset on every CreateCoins call, as is now, could be the case where the same coins are created twice.
Which will cause a runtime_error in AddInputs() and Merge() calls (see SelectionResult::InsertInputs()).
Move coins creation for a specific function. It
allows us to use it in other parts of the code.
122+ CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
123+ if (new_total_balance > 0) {
124+ std::set<std::shared_ptr<COutput>> utxo_pool;
125+ for (const auto& utxo : utxos) {
126+ utxo_pool.insert(std::make_shared<COutput>(utxo));
127+ }
In 562a577d0:
nit: this variable shadows another utxo_pool declared above.
Also, if you want to go further, probably could get rid of this extra loops by making CreateCoins create a set of shared pointers.
83@@ -84,7 +84,8 @@ FUZZ_TARGET(coinselection)
84
85 const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
86 const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
87- const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
88+ // Discard feerate must be at least dust relay feerate
89+ const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(3000, COIN)};
In 5f0237f2:
nit: could you take the dust relay feerate from somewhere instead of hardcoding it?
Code review ACK 5f0237f2
As an extra small nit, I would merge the GetInputSet and GetShuffledInputSet commits into one (ec82d1c3a523a9b28adf66f840e239f4adead37a, 4531ab1aee85a6801e0de00816b3764b8462771c) as they are basically doing the same. But, not a big deal if you don’t do it anyway.
Instead of using `cost_of_change` for `min_viable_change`
and `change_cost`, and 0 for `change_fee`, use values from
`coin_params`. The previous values don't generate any effects
that is relevant for that context.
The valid results should have a target below the sum of
the selected inputs amounts. Also, it increases the
minimum value for target to make it more realistic.
`m_cost_of_change` must not be generated randomly
independent from m_change_fee. This commit changes
it to set it up according to `wallet/spend`.
DUST_RELAY_TX_FEE instead of hardcoding the value and squashed GetInputSet and GetShuffledInputSet commits.
This crashes:
0fuzz: wallet/test/fuzz/coinselection.cpp:121: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.
0ACwnYWEAAAABAAABAAAgAAAAAI8AAAABAAABIAAAAACPAQAAAQAAAQB6AAAAAAAAAAAAAQAAAQAA
1jwAAAAEAAAE=
This crashes:
Yea. OSS-Fuzz has this this now as well https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=61790:
0Crash Type: ASSERT
1Crash Address:
2Crash State:
3 result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0
4 wallet::coinselection_fuzz_target
5 std::__1::__function::__func<void