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

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.

<!--e57a25ab6845829454e8d69fc972939a-->

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

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage

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

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See 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.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

No conflicts as of last run.

Added milestone, because this is a fuzz blocker

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:

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

@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:

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 m_use_effective with True and the change is 0.

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

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

#28395#pullrequestreview-1651973742

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

Rebased

CI error seems unrelated:

2023-12-13T15:26:02.5983445Z 54/286 - rpc_signer.py failed, Duration: 3 s
2023-12-13T15:26:02.5983915Z 
2023-12-13T15:26:02.5984128Z stdout:
2023-12-13T15:26:02.5985467Z 2023-12-13T15:25:59.249000Z TestFramework (INFO): PRNG seed is: 6112864330657271854
2023-12-13T15:26:02.5986266Z 
2023-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
2023-12-13T15:26:02.5995453Z 
2023-12-13T15:26:02.5996137Z 2023-12-13T15:26:00.333000Z TestFramework (ERROR): Assertion failed
2023-12-13T15:26:02.5996821Z 
2023-12-13T15:26:02.5997101Z Traceback (most recent call last):
2023-12-13T15:26:02.5997578Z 
2023-12-13T15:26:02.5998332Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_framework.py", line 556, in start_nodes
2023-12-13T15:26:02.5999355Z 
2023-12-13T15:26:02.5999728Z     node.wait_for_rpc_connection()
2023-12-13T15:26:02.6000194Z 
2023-12-13T15:26:02.6001027Z   File "D:\a\bitcoin\bitcoin\test\functional\test_framework\test_node.py", line 249, in wait_for_rpc_connection
2023-12-13T15:26:02.6002062Z 
2023-12-13T15:26:02.6002391Z     raise FailedToStartError(self._node_msg(
2023-12-13T15:26:02.6002931Z 
2023-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

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

Most of them, but not all crashed on this:

[#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-
fuzz: ../../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

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

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

Yes, I'm addressing it.

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 change_spend_size randomly. Perhaps we could use CalculateMaximumSignedInputSize and the same approach in CreateTransactionInternal.

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

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

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();

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

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

assert(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.

@@ -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();

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.

Left a comment

@@ -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();

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

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.

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:

-    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)};
 

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

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

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.

Code ACK cd810075eddd

ACK cd810075eddd8b1a7139559b475b56126f70a93d

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

ACK cd810075eddd8b1a7139559b475b56126f70a93d