-
Notifications
You must be signed in to change notification settings - Fork 37.7k
fuzz: coinselection, improve min_viable_change
/change_output_size
#28372
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
fuzz: coinselection, improve min_viable_change
/change_output_size
#28372
Conversation
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code CoverageFor detailed information about the code coverage, see the test coverage report. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. ConflictsNo conflicts as of last run. |
coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000); | ||
coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size); | ||
const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)}; | ||
coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee; | ||
const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)}; | ||
coin_params.min_viable_change = std::max(change_spend_fee + 1, dust); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I was pondering whether the input size being rolled randomly and the dust being only based on the output type could lead to min_viable_change
being smaller than cost_of_change - change_fee
, but this seems right to me now. 🤔
Approach ACK, will throw into my fuzzer for a while.
static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider) | ||
{ | ||
const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)}; | ||
CScript script_change{GetScriptForDestination(tx_destination)}; | ||
return CTxOut(0, script_change); | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This will narrow down the range of output sizes being fuzzed.
An alternative would perhaps be to randomly roll change output size and change input size, while calculating all the other derived values from those, but my gut says that there shouldn’t be all that much exciting happening anyway. Will revisit this question when I’ve fuzzed a bit.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Did you revisit it?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This will narrow down the range of output sizes being fuzzed.
Agree.
You don't need to create valid known destinations, we only care about the change output size. All yours:
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
--- a/src/wallet/test/fuzz/coinselection.cpp (revision ccb25a1ddc1f79f432a6718604f01ed97dced15f)
+++ b/src/wallet/test/fuzz/coinselection.cpp (date 1702581796902)
@@ -11,6 +11,7 @@
#include <test/util/setup_common.h>
#include <wallet/coinselection.h>
+#include <algorithm>
#include <vector>
namespace wallet {
@@ -74,13 +75,6 @@
return result;
}
-static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
-{
- const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
- CScript script_change{GetScriptForDestination(tx_destination)};
- return CTxOut(0, script_change);
-}
-
// Returns true if the result contains an error and the message is not empty
static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
@@ -101,14 +95,16 @@
coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
coin_params.m_long_term_feerate = long_term_fee_rate;
coin_params.m_effective_feerate = effective_fee_rate;
- auto change_prototype_txout{GetChangePrototypeTxout(fuzzed_data_provider)};
- coin_params.change_output_size = GetSerializeSize(change_prototype_txout);
+ coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
coin_params.m_discard_feerate = discard_fee_rate;
coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
- const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+ // We only care about the change output size
+ CScript change_out_script;
+ std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+ const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
int next_locktime{0};
Added milestone, because this is a fuzz blocker |
I found a crash:
You can run the crash seed using:
|
@murchandamus The crash happens because In that crash the See: CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
{
// change = SUM(inputs) - SUM(outputs) - fees
// 1) With SFFO we don't pay any fees
// 2) Otherwise we pay all the fees:
// - input fees are covered by GetSelectedEffectiveValue()
// - non_input_fee is included in m_target
// - change_fee
const CAmount change = m_use_effective
? GetSelectedEffectiveValue() - m_target - change_fee
: GetSelectedValue() - m_target;
if (change < min_viable_change) {
return 0;
}
return change;
} I tested |
Are you still working on this? What is the current status here? |
|
This is just an improvement in the logic and it's not an attempt to fix the crash since it's a real bug in BnB. |
Ok, removed milestone for now. Looks like this crashes in any case? #28372 (comment) So maybe mark as draft for now, while this is not yet ready for review. |
Draft while waiting for a fix in BnB |
bb7b9e1
to
ccb25a1
Compare
Rebased |
CI error seems unrelated:
|
Just kicked off 10×10h of fuzzing, will take a look tomorrow |
Most of them, but not all crashed on this:
I think we might have misdiagnosed the issue, when we thought it could only happen when SFFO is active |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think we might have misdiagnosed the issue, when we thought it could only happen when SFFO is active
@murchandamus. The code here has not fixed the issue I mentioned #28918 (comment).
Need to provide min_viable_change
to the BnB result GetChange()
function, not cost_of_change
. @brunoerg
Yes, I'm addressing it. |
Before pushing the changes, can verify them against the issue #28918 (comment). |
Also, I think it would be more appropriate if we don't set |
I think it would be fine to roll input and output sizes randomly as long as they remain greater than zero and all the related values are derived from them. E.g. it would be an issue if |
Got same crash with it. diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index b35bf34db3..5a3250bdd7 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
if (result_bnb) {
- assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
+ assert(result_bnb->GetChange(coin_params.min_viable_change, CAmount{0}) == 0);
assert(result_bnb->GetSelectedValue() >= target);
(void)result_bnb->GetShuffledInputVector();
(void)result_bnb->GetInputSet();
|
It seems to me that the check in line 131 is simply wrong:
The function definition is So, instead of passing @@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
if (result_bnb) {
- assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
+ assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
assert(result_bnb->GetSelectedValue() >= target);
(void)result_bnb->GetShuffledInputVector();
(void)result_bnb->GetInputSet(); |
Yeah, thats good. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Left a comment
static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider) | ||
{ | ||
const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)}; | ||
CScript script_change{GetScriptForDestination(tx_destination)}; | ||
return CTxOut(0, script_change); | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This will narrow down the range of output sizes being fuzzed.
Agree.
You don't need to create valid known destinations, we only care about the change output size. All yours:
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
--- a/src/wallet/test/fuzz/coinselection.cpp (revision ccb25a1ddc1f79f432a6718604f01ed97dced15f)
+++ b/src/wallet/test/fuzz/coinselection.cpp (date 1702581796902)
@@ -11,6 +11,7 @@
#include <test/util/setup_common.h>
#include <wallet/coinselection.h>
+#include <algorithm>
#include <vector>
namespace wallet {
@@ -74,13 +75,6 @@
return result;
}
-static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
-{
- const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
- CScript script_change{GetScriptForDestination(tx_destination)};
- return CTxOut(0, script_change);
-}
-
// Returns true if the result contains an error and the message is not empty
static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
@@ -101,14 +95,16 @@
coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
coin_params.m_long_term_feerate = long_term_fee_rate;
coin_params.m_effective_feerate = effective_fee_rate;
- auto change_prototype_txout{GetChangePrototypeTxout(fuzzed_data_provider)};
- coin_params.change_output_size = GetSerializeSize(change_prototype_txout);
+ coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
coin_params.m_discard_feerate = discard_fee_rate;
coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
- const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+ // We only care about the change output size
+ CScript change_out_script;
+ std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+ const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
int next_locktime{0};
Fuzzed for 1h with that change and got no new crash. |
Cool, I think the 0 came from the way we call |
Thanks, @furszy and @murchandamus. I will address the suggestions and leave it running for some time before pushing. Just an observation on @furszy's suggestion - I think it will cause - const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
+ // We only care about the change output size
+ CScript change_out_script;
+ std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
+ const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
|
I coded it on the fly. You can just push the opcodes manually if |
Change it to use same approach from `CreateTransactionInternal`.
ccb25a1
to
cd81007
Compare
Force-pushed addressing #28372 (comment) and #28372 (comment). Thanks @murchandamus and @furszy for the review! Left it running for 10h before pushing and did not crash. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Code ACK cd81007
ACK cd81007 Passes all my fuzzing crashes and no new crashes with some light additional fuzzing, code LGTM. |
ACK cd81007 |
Change it to use same approach from `CreateTransactionInternal`. Github-Pull: bitcoin#28372 Rebased-From: cd81007
Change it to use same approach from `CreateTransactionInternal`. Github-Pull: bitcoin#28372 Rebased-From: cd81007
Instead of "randomly" fuzzing
min_viable_change
andchange_output_size
, and since they're correlated, this PR changes the approach to fuzz them according to the logic inCreateTransactionInternal
.