fuzz: coinselection, improve `min_viable_change`/`change_output

brunoerg commented at 6:48 pm on August 30, 2023: contributor

Instead of “randomly” fuzzing min_viable_change and change_output_size, and since they’re correlated, this PR changes the approach to fuzz them according to the logic in CreateTransactionInternal.

DrahtBot commented at 6:49 pm on August 30, 2023: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

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.

Conflicts

No conflicts as of last run.

DrahtBot added the label Tests on Aug 30, 2023

in src/wallet/test/fuzz/coinselection.cpp:105 in bb7b9e1f79 outdated

110     coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
111-    coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
112+    const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
113+    coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
114+    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
115+    coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);

murchandamus commented at 7:57 pm on August 30, 2023:

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. :thinking:

Approach ACK, will throw into my fuzzer for a while.

in src/wallet/test/fuzz/coinselection.cpp:82 in bb7b9e1f79 outdated

73@@ -74,6 +74,13 @@ static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmoun
74     return result;
75 }
76 
77+static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
78+{
79+    const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
80+    CScript script_change{GetScriptForDestination(tx_destination)};
81+    return CTxOut(0, script_change);
82+}

murchandamus commented at 8:01 pm on August 30, 2023:

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.

brunoerg commented at 4:32 pm on October 5, 2023:

Did you revisit it?

furszy commented at 7:28 pm on December 14, 2023:

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:

 0diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
 1--- a/src/wallet/test/fuzz/coinselection.cpp	(revision ccb25a1ddc1f79f432a6718604f01ed97dced15f)
 2+++ b/src/wallet/test/fuzz/coinselection.cpp	(date 1702581796902)
 3@@ -11,6 +11,7 @@
 4 #include <test/util/setup_common.h>
 5 #include <wallet/coinselection.h>
 6 
 7+#include <algorithm>
 8 #include <vector>
 9 
10 namespace wallet {
11@@ -74,13 +75,6 @@
12     return result;
13 }
14 
15-static CTxOut GetChangePrototypeTxout(FuzzedDataProvider& fuzzed_data_provider)
16-{
17-    const CTxDestination tx_destination{ConsumeTxDestination(fuzzed_data_provider)};
18-    CScript script_change{GetScriptForDestination(tx_destination)};
19-    return CTxOut(0, script_change);
20-}
21-
22 // Returns true if the result contains an error and the message is not empty
23 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
24 
25@@ -101,14 +95,16 @@
26     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
27     coin_params.m_long_term_feerate = long_term_fee_rate;
28     coin_params.m_effective_feerate = effective_fee_rate;
29-    auto change_prototype_txout{GetChangePrototypeTxout(fuzzed_data_provider)};
30-    coin_params.change_output_size = GetSerializeSize(change_prototype_txout);
31+    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
32     coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
33     coin_params.m_discard_feerate = discard_fee_rate;
34     coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
35     const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
36     coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
37-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
38+    // We only care about the change output size
39+    CScript change_out_script;
40+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
41+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
42     coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
43 
44     int next_locktime{0};

maflcko added this to the milestone 26.0 on Aug 31, 2023

maflcko commented at 8:00 am on August 31, 2023: member

Added milestone, because this is a fuzz blocker

murchandamus commented at 7:04 pm on September 1, 2023: contributor

I found a crash:

fuzz: ../../src/wallet/test/fuzz/coinselection.cpp:130: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0’ failed.

You can run the crash seed using:

0$ echo "FP93w8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8N3d1h3d4h3d3cUAjsTsTsTsTOOd3d3d5t3d3d3WHd3iHd3d3d3d///yZkblPEYAAB3d3d3d3cKJ3d3d////wAyd3d3d3c093d3d3d3dwonAAD/kiEA" | base64 -d > crash.input
1$ FUZZ=coinselection src/test/fuzz/fuzz crash.input

brunoerg commented at 6:46 pm on September 2, 2023: contributor

@murchandamus The crash happens because GetChange is returning exactly the cost_of_change, instead of 0.

In that crash the m_subtract_fee_outputs is True. So m_use_effective in GetChange is False.

See:

 0CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
 1{
 2    // change = SUM(inputs) - SUM(outputs) - fees
 3    // 1) With SFFO we don't pay any fees
 4    // 2) Otherwise we pay all the fees:
 5    //  - input fees are covered by GetSelectedEffectiveValue()
 6    //  - non_input_fee is included in m_target
 7    //  - change_fee
 8    const CAmount change = m_use_effective
 9                           ? GetSelectedEffectiveValue() - m_target - change_fee
10                           : GetSelectedValue() - m_target;
11
12    if (change < min_viable_change) {
13        return 0;
14    }
15
16    return change;
17}

I tested m_use_effective with True and the change is 0.

DrahtBot added the label CI failed on Sep 3, 2023

DrahtBot removed the label CI failed on Sep 5, 2023

DrahtBot added the label CI failed on Sep 5, 2023

DrahtBot removed the label CI failed on Sep 5, 2023

maflcko commented at 4:03 pm on October 5, 2023: member

Are you still working on this? What is the current status here?

furszy commented at 4:27 pm on October 5, 2023: member

Are you still working on this? What is the current status here?

#28395#pullrequestreview-1651973742

brunoerg commented at 4:31 pm on October 5, 2023: contributor

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.

maflcko removed this from the milestone 26.0 on Oct 5, 2023

maflcko commented at 4:36 pm on October 5, 2023: member

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.

brunoerg marked this as a draft on Oct 16, 2023

brunoerg commented at 6:14 pm on October 16, 2023: contributor

Draft while waiting for a fix in BnB

brunoerg force-pushed on Dec 13, 2023

brunoerg marked this as ready for review on Dec 13, 2023

brunoerg commented at 3:10 pm on December 13, 2023: contributor

Rebased

brunoerg commented at 4:57 pm on December 13, 2023: contributor

CI error seems unrelated:

 02023-12-13T15:26:02.5983445Z 54/286 - rpc_signer.py failed, Duration: 3 s
 12023-12-13T15:26:02.5983915Z 
 22023-12-13T15:26:02.5984128Z stdout:
 32023-12-13T15:26:02.5985467Z 2023-12-13T15:25:59.249000Z TestFramework (INFO): PRNG seed is: 6112864330657271854
 42023-12-13T15:26:02.5986266Z 
 52023-12-13T15:26:02.5994148Z 2023-12-13T15:25:59.249000Z TestFramework (INFO): Initializing test directory D:\a\_temp\test_runner_₿_🏃_20231213_151925\rpc_signer_229
 62023-12-13T15:26:02.5995453Z 
 72023-12-13T15:26:02.5996137Z 2023-12-13T15:26:00.333000Z TestFramework (ERROR): Assertion failed
 82023-12-13T15:26:02.5996821Z 
 92023-12-13T15:26:02.5997101Z Traceback (most recent call last):
102023-12-13T15:26:02.5997578Z 
112023-12-13T15:26:02.5998332Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_framework.py", line 556, in start_nodes
122023-12-13T15:26:02.5999355Z 
132023-12-13T15:26:02.5999728Z     node.wait_for_rpc_connection()
142023-12-13T15:26:02.6000194Z 
152023-12-13T15:26:02.6001027Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_node.py", line 249, in wait_for_rpc_connection
162023-12-13T15:26:02.6002062Z 
172023-12-13T15:26:02.6002391Z     raise FailedToStartError(self._node_msg(
182023-12-13T15:26:02.6002931Z 
192023-12-13T15:26:02.6005067Z test_framework.test_node.FailedToStartError: [node 1] bitcoind exited with status 1 during initialization. Error: Error parsing command line arguments: Invalid parameter -signer=py -3 D:\a\bitcoin\bitcoin\test\functional\mocks\signer.py

murchandamus commented at 3:09 am on December 14, 2023: contributor

Just kicked off 10×10h of fuzzing, will take a look tomorrow

murchandamus commented at 2:06 pm on December 14, 2023: contributor

Most of them, but not all crashed on this:

0[#626233](/bitcoin-bitcoin/626233/) REDUCE cov: 1289 ft: 13823 corp: 4183/16Mb lim: 66076 exec/s: 206 rss: 88Mb L: 157/65635 MS: 1 EraseBytes-
1fuzz: ../../src/wallet/test/fuzz/coinselection.cpp:131: void wallet::coinselection_fuzz_target(FuzzBufferType): Assertion `result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0' failed.

I think we might have misdiagnosed the issue, when we thought it could only happen when SFFO is active

furszy commented at 2:11 pm on December 14, 2023: member

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

brunoerg commented at 2:11 pm on December 14, 2023: contributor

Need to provide min_viable_change to the BnB function, not cost_of_change. @brunoerg

Yes, I’m addressing it.

furszy commented at 2:22 pm on December 14, 2023: member

Yes, I’m addressing it.

Before pushing the changes, can verify them against the issue #28918 (comment).

brunoerg commented at 2:31 pm on December 14, 2023: contributor

Also, I think it would be more appropriate if we don’t set change_spend_size randomly. Perhaps we could use CalculateMaximumSignedInputSize and the same approach in CreateTransactionInternal.

murchandamus commented at 2:49 pm on December 14, 2023: contributor

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 cost_of_change or min_viable_change were independent of change_spend_size

brunoerg commented at 6:10 pm on December 14, 2023: contributor

Need to provide min_viable_change to the BnB result GetChange() function, not cost_of_change. @brunoerg

Got same crash with it.

 0diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
 1index b35bf34db3..5a3250bdd7 100644
 2--- a/src/wallet/test/fuzz/coinselection.cpp
 3+++ b/src/wallet/test/fuzz/coinselection.cpp
 4@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
 5     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
 6                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
 7     if (result_bnb) {
 8-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
 9+        assert(result_bnb->GetChange(coin_params.min_viable_change, CAmount{0}) == 0);
10         assert(result_bnb->GetSelectedValue() >= target);
11         (void)result_bnb->GetShuffledInputVector();
12         (void)result_bnb->GetInputSet();

0echo "//////////////////8AKH4pAAAsICkpAAAAAAgARSwLCwv//////////wsLCwsL                   
1Cwt+MPILCwsLCwsLCwsLCwEAAAsHCwsLTJV4CwsLCwsLCwsBAAALCwsLCwsLCwsL
2CwsA+f8nAAsLCwsLAf//JgImJtAB/w==" | base64 --decode > coinselection.crash

murchandamus commented at 6:41 pm on December 14, 2023: contributor

It seems to me that the check in line 131 is simply wrong:

0assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);

The function definition is CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

0@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
1     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
2                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
3     if (result_bnb) {
4-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
5+        assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
6         assert(result_bnb->GetSelectedValue() >= target);
7         (void)result_bnb->GetShuffledInputVector();
8         (void)result_bnb->GetInputSet();

furszy commented at 7:04 pm on December 14, 2023: member

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

Yeah, thats good. It is because cost_of_change, the BnB upper bound, includes change_fee while min_viable_change does not.

furszy commented at 7:29 pm on December 14, 2023: member

Left a comment

murchandamus commented at 8:42 pm on December 14, 2023: contributor

0@@ -128,7 +128,7 @@ FUZZ_TARGET(coinselection)
1     auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
2                       SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
3     if (result_bnb) {
4-        assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
5+        assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
6         assert(result_bnb->GetSelectedValue() >= target);
7         (void)result_bnb->GetShuffledInputVector();
8         (void)result_bnb->GetInputSet();

Fuzzed for 1h with that change and got no new crash.

brunoerg commented at 9:18 pm on December 14, 2023: contributor

So, instead of passing coin_params.m_cost_of_change and 0, we should be passing coin_params.min_viable_change and coin_params.m_change_fee. Just fixing one or the other was insufficient, but when I replace both all my fuzz crashes pass.

Cool, I think the 0 came from the way we call ComputeAndSetWaste internally in SelectCoinsBnB.

brunoerg commented at 9:19 pm on December 14, 2023: contributor

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 stack-buffer-overflow:

0-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
1+    // We only care about the change output size
2+    CScript change_out_script;
3+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
4+    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
5

furszy commented at 9:46 pm on December 14, 2023: member

Just an observation on @furszy’s suggestion - I think it will cause stack-buffer-overflow:

0-    const auto dust{GetDustThreshold(change_prototype_txout, coin_params.m_discard_feerate)};
1+    // We only care about the change output size
2+    CScript change_out_script;
3+    std::fill_n(change_out_script.begin(), coin_params.change_output_size, OP_TRUE);
4+    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 std::fill_n() doesn’t work or correct it in some way. The rationale is to not construct only known destinations as you are doing here. Coin selection doesn’t care about them, it just uses the script size.

fuzz: coinselection, improve `min_viable_change`/`change_output_size`

Change it to use same approach from
`CreateTransactionInternal`.

cd810075ed

brunoerg force-pushed on Dec 15, 2023

brunoerg commented at 9:30 am on December 15, 2023: contributor

Force-pushed addressing #28372 (comment) and #28372 (review). Thanks @murchandamus and @furszy for the review!

Left it running for 10h before pushing and did not crash.

furszy approved

furszy commented at 1:14 pm on December 15, 2023: member

Code ACK cd810075eddd

murchandamus commented at 1:33 pm on December 19, 2023: contributor

ACK cd810075eddd8b1a7139559b475b56126f70a93d

Passes all my fuzzing crashes and no new crashes with some light additional fuzzing, code LGTM.

achow101 commented at 0:38 am on December 21, 2023: member

ACK cd810075eddd8b1a7139559b475b56126f70a93d

achow101 merged this on Dec 21, 2023

achow101 closed this on Dec 21, 2023

luke-jr referenced this in commit 462f2be2ca on Mar 15, 2024

luke-jr referenced this in commit 51251355eb on Mar 18, 2024

bitcoin locked this on Dec 20, 2024

fuzz: coinselection, improve min_viable_change/change_output_size #28372

Code Coverage

Reviews

Conflicts

fuzz: coinselection, improve `min_viable_change`/`change_output_size` #28372