[coinselection] Increase SRD target by change_fee #27846

pull murchandamus wants to merge 2 commits into bitcoin:master from murchandamus:2023-06-fix-srd-target changing 5 files +10 −7

murchandamus commented at 6:14 PM on June 9, 2023: contributor

I discovered via fuzzing of another coin selection approach that at extremely high feerates SRD may find input sets that lead to transactions without change outputs. This is an unintended outcome since SRD is meant to always produce a transaction with a change output—we use other algorithms to specifically search for changeless solutions.

The issue occurs when the flat allowance of 50,000 ṩ for change is insufficient to pay for the creation of a change output with a non-dust amount, at and above 1,613 ṩ/vB. Increasing the change budget by change_fee makes SRD behave as expected at any feerates.

Note: The intermittent failures of test/functional/interface_usdt_mempool.py are a known issue: https://github.com/bitcoin/bitcoin/issues/27380
DrahtBot commented at 6:14 PM on June 9, 2023: contributor


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



Reviews

See the guideline for information on the review process.

Type Reviewers

ACK achow101, S3RK

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.



Conflicts

Reviewers, this pull request conflicts with the following ones:
- #27877 (wallet: Add CoinGrinder coin selection algorithm by Xekyo)
- #27585 (fuzz: improve coinselection by brunoerg)
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
DrahtBot added the label CI failed on Jun 9, 2023
DrahtBot removed the label CI failed on Jun 13, 2023
achow101 commented at 6:44 PM on June 14, 2023: member

Could we add a (fuzz) test that checks for this?
murchandamus commented at 8:57 PM on June 14, 2023: contributor

Could we add a (fuzz) test that checks for this?

I added an assert that SRD’s budget for change is always bigger than change_fee plus the dust amount for a P2WPKH output. This assert failed within seconds for the old code, but is fine with the new code.
murchandamus force-pushed on Jun 14, 2023
in src/wallet/test/fuzz/coinselection.cpp:95 in a92efa9422 outdated
```
  89 | @@ -90,8 +90,11 @@ FUZZ_TARGET(coinselection)
  90 |      // Run coinselection algorithms
  91 |      const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change, MAX_STANDARD_TX_WEIGHT);
  92 |  
  93 | -    auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
  94 | -    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
  95 | +    auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
  96 | +    if (result_srd) {
  97 | +        assert(result_srd->GetChange(CAmount{294}, coin_params.m_change_fee) > 0); // Shows that SRD always selects enough for a non-dust P2WPKH change output
```
S3RK commented at 8:16 AM on June 19, 2023:

Why 294?

S3RK commented at 8:21 AM on June 19, 2023:

Answering myself. Dust limit for P2WPKH is 294 = (67 vbytes for input + 31 vbytes for output) * 3sat/vb

S3RK commented at 8:23 AM on June 19, 2023:

But why use P2WPKH in particular, when change_output_size is a random int for 10 to 1000

achow101 commented at 5:21 PM on June 19, 2023:

This parameter is the minimum viable change, which for this test, I think makes sense to actually be as high as possible, rather than dependent on the change output itself. The new behavior is that SRD will never make a change output that is smaller than CHANGE_LOWER, so I think it would make sense to set this to CHANGE_LOWER.

murchandamus commented at 8:18 PM on June 21, 2023:

@S3RK: Yeah, you got it right. @achow101: Followed your suggestion and updated the minimum to CHANGE_LOWER.
S3RK commented at 8:19 AM on June 19, 2023: contributor

Approach ACK.

That's a straightforward fix for the bug.
murchandamus force-pushed on Jun 21, 2023

Type	Reviewers
ACK	achow101, S3RK

[bug] Increase SRD target by change_fee

I discovered via fuzzing of another coin selection approach that at
extremely high feerates SRD may find input sets that lead to
transactions without change outputs. This is an unintended outcome since
SRD is meant to always produce a transaction with a change output—we use
other algorithms to specifically search for changeless solutions.

The issue occures when the flat allowance of 50,000 ṩ for change is
insufficient to pay for the creation of a change output with a non-dust
amount, at and above 1,613 ṩ/vB. Increasing the change budget by
change_fees makes SRD behave as expected at any feerates.

941b8c6539

[fuzz] Show that SRD budgets for non-dust change

Adding this assert to the fuzz test without increasing the change target
by the change_fee resulted in a crash within a few seconds.

1771daa815

murchandamus force-pushed on Jun 21, 2023
murchandamus commented at 8:20 PM on June 21, 2023: contributor

Rebase: Increased minimum value of change to CHANGE_LOWER as discussed above, and signed commits.
achow101 commented at 8:40 PM on June 21, 2023: member

ACK 1771daa815ec014276cfcb30c934b0eaff4d72bf
S3RK commented at 6:52 AM on June 22, 2023: contributor

ACK 1771daa815ec014276cfcb30c934b0eaff4d72bf
achow101 merged this on Jun 23, 2023
achow101 closed this on Jun 23, 2023
sidhujag referenced this in commit 7b1ed7d1fa on Jun 25, 2023
luke-jr referenced this in commit ac26196314 on Aug 16, 2023
luke-jr referenced this in commit c4717a5a6c on Aug 16, 2023
murchandamus deleted the branch on Aug 25, 2023
bitcoin locked this on Aug 24, 2024

Contributors

Linked (view graph)

#27380 Intermittent failures in interface_usdt_mempool.py

[coinselection] Increase SRD target by change_fee #27846

Reviews

Conflicts