wallet: Check max transaction weight in CoinSelection #25729

aureleoules · 2022-07-28T12:33:06Z

This PR is an attempt to fix #5782.

I have added 4 test scenarios, 3 of them provided here #5782 (comment) (slightly modified to use a segwit wallet).

Here are my benchmarks :

PR

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,466,341.00	681.97	0.6%	11,176,762.00	3,358,752.00	3.328	1,897,839.00	0.3%	0.02	`CoinSelection`

Master

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,526,029.00	655.30	0.5%	11,142,188.00	3,499,200.00	3.184	1,994,156.00	0.2%	0.02	`CoinSelection`

DrahtBot · 2022-07-28T15:56:25Z

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, w0xlt, furszy
Stale ACK	Xekyo

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:

#25806 (wallet: group outputs only once, decouple it from Coin Selection by furszy)

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.

achow101 · 2022-07-28T17:20:29Z

It shouldn't be necessary to pass an entire CMutableTransaction to SelectCoins. CoinSelectionParams already has the information about the sizes of the rest of the transaction, modulo the change output. So a calculation can be done with that information.

Additionally, depending on the algorithm used, there may or may not be a change output, so it's size will need to be accounted for in each size calculation.

aureleoules · 2022-07-28T18:38:37Z

Thank you for the feedback @achow101.
Sizes in the CoinSelectionParams appear to be in "bytes" and not in "weight", so I'm not sure how to use them as the multiplier of each field hasn't been taken into account, unless I'm mistaken.

Additionally, depending on the algorithm used, there may or may not be a change output, so it's size will need to be accounted for in each size calculation.

I'll look into that thanks.

achow101 · 2022-07-28T18:44:01Z

The size is always vsize, so multiplyging by WITNESS_SCALE_FACTOR is sufficient to convert to weight. There will be some rounding error, but vsize always rounds up, so weight calculated in that way will always be a slight overestimate.

aureleoules · 2022-07-28T21:40:45Z

I've removed the need for a dummy transaction.
Though I'm not sure how to include the change output in the size calculation yet.

src/wallet/spend.cpp

aureleoules · 2022-08-03T15:15:25Z

Pinging you @xekyo as you commented on the issue recently.

achow101 · 2022-11-18T17:11:19Z

No, it is correct as it is now. Converting vbytes to weight is always just multiply by WITNESS_SCALE_FACTOR. It doesn't matter what the script type is.

aureleoules · 2022-11-18T17:14:35Z

Okay great thank you!

src/wallet/coinselection.cpp

furszy

code review ACK 30b71d1, left few small comments.

src/wallet/spend.cpp

src/wallet/test/coinselector_tests.cpp

achow101 · 2022-11-23T19:08:48Z

ACK 30b71d1

Co-authored-by: Andrew Chow <github@achow101.com>

aureleoules · 2022-12-05T18:34:54Z

Rebased

achow101 · 2022-12-05T21:06:46Z

reACK c7c7ee9

w0xlt

ACK c7c7ee9

S3RK · 2022-12-06T07:45:27Z

src/wallet/coinselection.cpp

@@ -354,6 +355,10 @@ void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descend
    // descendants is the count as seen from the top ancestor, not the descendants as seen from the
    // coin itself; thus, this value is counted as the max, not the sum
    m_descendants = std::max(m_descendants, descendants);
+
+    if (output.input_bytes > 0) {
+        m_weight += output.input_bytes * WITNESS_SCALE_FACTOR;


While this is fine for the purposes of this PR, the weight here is not always precise due to rounding error of input_bytes.

Ideally, we would store the actual weight in COutput and just take it from there. I realise, this might be out of scope for this PR. But maybe we can add a warning in code for future devs and create an issue in this repo?

the weight here is not always precise due to rounding error of input_bytes

Could elaborate, since both COutput::input_bytes and WITNESS_SCALE_FACTOR are integer ?

1 virtual byte = 4 weight units. When computing vbytes from weight, if the weight is not divisible by 4, the vbytes is rounded up. For example, 6 WU is really 1.5 vbytes, but is rounded to 2 vbytes. Since input_bytes stores this rounded number, computing weight from it results in 8 WU rather than the correct value of 6.

furszy

diff ACK c7c7ee9

furszy · 2022-12-06T14:53:12Z

src/wallet/spend.cpp

@@ -888,7 +897,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
    }

    // Include the fees for things that aren't inputs, excluding the change output
-    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
+    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size);


could:

Suggested change

const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size);

const CAmount not_input_fees = coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

I would actually rather that not_input_fees is always calculated, and the SFFO handling is done for just the target. We really need to try to reduce the number of places that we have differences between normal and SFFO coin selection. Since not_input_fees is used elsewhere, having its value be dependent on SFFO results in a cascading effect that I think we should be avoiding.

But that can be done in a followup.

…ction

…error messages 76dc547 gui: create tx, launch error dialog if backend throws runtime_error (furszy) f4d7947 wallet: coin selection, add duplicated inputs checks (furszy) 0aa065b wallet: return accurate error messages from Coin Selection (furszy) 7e8340a wallet: make SelectCoins flow return util::Result (furszy) e5e147f wallet: refactor eight consecutive 'AttemptSelection' calls into a loop (furszy) Pull request description: Work decoupled from #25806, which cleanup and improves the Coin Selection flow further. Adding the capability to propagate specific error messages from the Coin Selection process to the user. Instead of always returning the general "Insufficient funds" message which is not always accurate to what happened internally. Letting us instruct the user how to proceed under certain circumstances. The following error messages were added: 1) If the selection result exceeds the maximum transaction weight, we now will return: -> "The inputs size exceeds the maximum weight. Please try sending a smaller amount or manually consolidating your wallet's UTXOs". 2) If the user pre-selected inputs and disallowed the automatic coin selection process (no other inputs are allowed), we now will return: -> "The preselected coins total amount does not cover the transaction target. Please allow other inputs to be automatically selected or include more coins manually". 3) The double-counted preset inputs during Coin Selection error will now throw an "internal bug detected" message instead of crashing the node. The essence of this work comes from several comments: 1. bitcoin/bitcoin#26560 (comment) 2. bitcoin/bitcoin#25729 (comment) 3. bitcoin/bitcoin#25269 (review) 4. bitcoin/bitcoin#23144 (which is connected to #24845) ACKs for top commit: ishaanam: crACK 76dc547 achow101: ACK 76dc547 aureleoules: ACK 76dc547 theStack: ACK 76dc547 🌇 Tree-SHA512: 9de30792d7a5849cae77747aa978e70390b66ee9d082779a56088a024f82e725b0af050e6603aece0ac8229f6d73bc471ba97b4ab69dc7eddf419f5f56ae89a5

…ssages 76dc547 gui: create tx, launch error dialog if backend throws runtime_error (furszy) f4d7947 wallet: coin selection, add duplicated inputs checks (furszy) 0aa065b wallet: return accurate error messages from Coin Selection (furszy) 7e8340a wallet: make SelectCoins flow return util::Result (furszy) e5e147f wallet: refactor eight consecutive 'AttemptSelection' calls into a loop (furszy) Pull request description: Work decoupled from bitcoin#25806, which cleanup and improves the Coin Selection flow further. Adding the capability to propagate specific error messages from the Coin Selection process to the user. Instead of always returning the general "Insufficient funds" message which is not always accurate to what happened internally. Letting us instruct the user how to proceed under certain circumstances. The following error messages were added: 1) If the selection result exceeds the maximum transaction weight, we now will return: -> "The inputs size exceeds the maximum weight. Please try sending a smaller amount or manually consolidating your wallet's UTXOs". 2) If the user pre-selected inputs and disallowed the automatic coin selection process (no other inputs are allowed), we now will return: -> "The preselected coins total amount does not cover the transaction target. Please allow other inputs to be automatically selected or include more coins manually". 3) The double-counted preset inputs during Coin Selection error will now throw an "internal bug detected" message instead of crashing the node. The essence of this work comes from several comments: 1. bitcoin#26560 (comment) 2. bitcoin#25729 (comment) 3. bitcoin#25269 (review) 4. bitcoin#23144 (which is connected to bitcoin#24845) ACKs for top commit: ishaanam: crACK 76dc547 achow101: ACK 76dc547 aureleoules: ACK 76dc547 theStack: ACK 76dc547 🌇 Tree-SHA512: 9de30792d7a5849cae77747aa978e70390b66ee9d082779a56088a024f82e725b0af050e6603aece0ac8229f6d73bc471ba97b4ab69dc7eddf419f5f56ae89a5

…ults that exceed the max allowed weight 25ab147 refactor: coinselector_tests, unify wallet creation code (furszy) ba9431c test: coverage for bnb max weight (furszy) 5a2bc45 wallet: clean post coin selection max weight filter (furszy) 2d11258 coin selection: BnB, don't return selection if exceeds max allowed tx weight (furszy) d3a1c09 test: coin selection, add coverage for SRD (furszy) 9d9689e coin selection: heap-ify SRD, don't return selection if exceeds max tx weight (furszy) 6107ec2 coin selection: knapsack, select closest UTXO above target if result exceeds max tx size (furszy) 1284223 wallet: refactor coin selection algos to return util::Result (furszy) Pull request description: Coming from the following comment bitcoin/bitcoin#25729 (comment). The reason why we are adding hundreds of UTXO from different sources when the target amount is covered only by one of them is because only SRD returns a usable result. Context: In the test, we create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform Coin Selection to fund 49.5 BTC. As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the expectation here is to receive a selection result that only contain the big UTXO. Which is not happening for the following reason: Knapsack returns a result that exceeds the max allowed transaction size, when it should return the closest utxo above the target, so we fallback to SRD who selects coins randomly up until the target is met. So we end up with a selection result with lot more coins than what is needed. ACKs for top commit: S3RK: ACK 25ab147 achow101: ACK 25ab147 Xekyo: reACK 25ab147 theStack: Code-review ACK 25ab147 Tree-SHA512: 2425de4cc479b4db999b3b2e02eb522a2130a06379cca0418672a51c4076971a1d427191173820db76a0f85a8edfff100114e1c38fb3b5dc51598d07cabe1a60

fanquake added the Wallet label Jul 28, 2022

aureleoules marked this pull request as draft July 28, 2022 13:34

aureleoules force-pushed the 2022-07-coin-selection-check-max-weight branch 5 times, most recently from 5123bd5 to 45b5a31 Compare July 28, 2022 15:37

This was referenced Jul 28, 2022

wallet: Faster transaction creation by removing pre-set-inputs fetching responsibility from Coin Selection #25685

Merged

wallet: simplify ListCoins implementation #25659

Merged

wallet: return change from SelectionResult #25647

Merged

aureleoules marked this pull request as ready for review July 28, 2022 17:06

This was referenced Jul 28, 2022

rpc: Filter inputs by type during CoinSelection #25183

Closed

refactor: improve complexity of removing preselected coins #24814

Closed

wallet: Improve AvailableCoins performance by reducing duplicated operations #24699

Merged

aureleoules force-pushed the 2022-07-coin-selection-check-max-weight branch from 45b5a31 to 627b715 Compare July 28, 2022 21:39

furszy reviewed Jul 28, 2022

View reviewed changes

src/wallet/spend.cpp Outdated Show resolved Hide resolved

aureleoules force-pushed the 2022-07-coin-selection-check-max-weight branch 6 times, most recently from e06a41f to 0741aaa Compare July 28, 2022 23:33

aureleoules marked this pull request as draft July 29, 2022 13:11

aureleoules marked this pull request as ready for review July 30, 2022 09:36

furszy reviewed Nov 19, 2022

View reviewed changes

src/wallet/coinselection.cpp Outdated Show resolved Hide resolved

aureleoules force-pushed the 2022-07-coin-selection-check-max-weight branch 2 times, most recently from 962bb57 to 30b71d1 Compare November 19, 2022 23:36

furszy approved these changes Nov 21, 2022

View reviewed changes

src/wallet/spend.cpp Show resolved Hide resolved

src/wallet/test/coinselector_tests.cpp Show resolved Hide resolved

fanquake requested a review from murchandamus November 23, 2022 22:01

This was referenced Nov 25, 2022

Wallet: estimate the size of signed inputs using descriptors #26567

Merged

wallet: bugfix, invalid CoinsResult cached total amount #26560

Merged

DrahtBot added the Needs rebase label Dec 5, 2022

aureleoules and others added 2 commits December 5, 2022 19:32

wallet: Check max tx weight in coin selector

6b563ca

Co-authored-by: Andrew Chow <github@achow101.com>

test: Check max transaction weight in CoinSelection

c7c7ee9

Co-authored-by: Andrew Chow <github@achow101.com>

aureleoules force-pushed the 2022-07-coin-selection-check-max-weight branch from 30b71d1 to c7c7ee9 Compare December 5, 2022 18:32

DrahtBot removed the Needs rebase label Dec 5, 2022

DrahtBot changed the title ~~wallet: Check max transaction weight in CoinSelection~~ wallet: Check max transaction weight in CoinSelection Dec 5, 2022

w0xlt approved these changes Dec 6, 2022

View reviewed changes

S3RK reviewed Dec 6, 2022

View reviewed changes

furszy approved these changes Dec 6, 2022

View reviewed changes

achow101 merged commit ef744c0 into bitcoin:master Dec 6, 2022

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Dec 6, 2022

Merge bitcoin#25729: wallet: Check max transaction weight in CoinSele…

7b7cd87

…ction

furszy mentioned this pull request Dec 8, 2022

wallet: Coin Selection, return accurate error messages #26661

Merged

furszy mentioned this pull request Dec 18, 2022

wallet: coin selection, don't return results that exceed the max allowed weight #26720

Merged

aureleoules deleted the 2022-07-coin-selection-check-max-weight branch January 12, 2023 11:51

bitcoin locked and limited conversation to collaborators Jan 12, 2024

	const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size);
	const CAmount not_input_fees = coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

wallet: Check max transaction weight in CoinSelection #25729

wallet: Check max transaction weight in CoinSelection #25729

Uh oh!

Conversation

aureleoules commented Jul 28, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR

Master

Uh oh!

DrahtBot commented Jul 28, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews

Conflicts

Uh oh!

achow101 commented Jul 28, 2022

Uh oh!

aureleoules commented Jul 28, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Jul 28, 2022

Uh oh!

aureleoules commented Jul 28, 2022

Uh oh!

Uh oh!

aureleoules commented Aug 3, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Nov 18, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aureleoules commented Nov 18, 2022

Uh oh!

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

achow101 commented Nov 23, 2022

Uh oh!

aureleoules commented Dec 5, 2022

Uh oh!

achow101 commented Dec 5, 2022

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

S3RK Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

w0xlt Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

achow101 Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

furszy Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

achow101 Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

aureleoules commented Jul 28, 2022 •

edited

Loading

DrahtBot commented Jul 28, 2022 •

edited

Loading

aureleoules commented Jul 28, 2022 •

edited

Loading

aureleoules commented Aug 3, 2022 •

edited

Loading

achow101 commented Nov 18, 2022 •

edited

Loading