wallet: group outputs only once, decouple it from Coin Selection #25806

furszy · 2022-08-08T21:19:07Z

The idea originates from #24845 (comment).

Note:
For clarity, it's recommended to start reviewing from the end result to understand the structure of the flow.

GroupOutputs function rationale:

If "Avoid Partial Spends" is enabled, the function gathers outputs with the same script together inside a container. So Coin Selection can treats them as if them were just one possible input and either select them all or not select them.

How the Inputs Fetch + Selection process roughly works:

1. Fetch user’s manually selected inputs.
2. Fetch wallet available coins (walks through the entire wallet txes map) and insert them into a set of vectors (each vector store outputs from a single type).
3. Coin Selection Process:
   Call `AttemptSelection` 8 times. Each of them expands the coin eligibility filter (accepting a larger subset of coins in the calculation) until it founds a solutions or completely fails if no solutions gets founds after the 8 rounds.

   Each `AttemptSelection` call performs the following actions:
     - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and a combination of all of them):
       Call ‘ChooseSelectionResult’ providing the respective, filtered by type, coins vector. Which:
           I. Groups the outputs vector twice (one for positive only and a second one who includes the negative ones as well).
              - GroupOutputs walks-through the entire inputted coins vector one time at least, + more if we are avoiding partial spends, to generate a vector of OutputGroups.
           II. Then performs every coin selection algorithm using the recently created vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD.
           III. Then returns the best solution out of them.

We perform the general operation of gathering outputs, with the same script, into a single container inside:
Each coins selection attempt (8 times —> each coin eligibility filter), for each of the outputs vector who were filtered by type (plus another one joining all the outputs as well if needed), twice (one for the positive only outputs effective value and a second one for all of them).

So, in the worst case scenario where no solution is found after the 8 Coin Selection attempts, the GroupOutputs function is called 80 times (8 * 5 * 2).

Improvements:

This proposal streamlines the process so that the output groups, filtered by coin eligibility and type, are created in a single loop outside of the Coin Selection Process.

The new process is as follows:

1. Fetch user’s manually selected inputs.
2. Fetch wallet available coins.
3. Group outputs by each coin eligibility filter and each different output type found.
4. Coin Selection Process: 
   Call AttemptSelection 8 times. Each of them expands the coin eligibility filter (accepting different output groups) until it founds a solutions or completely fails if no solutions gets founds after the 8 rounds.
   
   Each ‘AttemptSelection’ call performs the following actions:
      - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and all of them):
          A. Call ‘ChooseSelectionResult’ providing the respective, filtered by type, output group. Which:
             I. Performs every coin selection algorithm using the provided vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD.
             II. Then returns the best solution out of them.

Extra Note:
The next steps after this PR will be to:

Merge AvailableCoins and GroupOutputs processes.
Skip entire coin selection rounds if no new coins are added into the subsequent round.
Remove global feerates from the OutputGroup class.
Remove secondary "grouped" tx creation from CreateTransactionInternal by running Coin Selection results over the aps grouped outputs vs non-aps ones.

DrahtBot · 2022-08-09T05:46:16Z

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	S3RK, theStack, achow101
Concept 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:

#26720 (wallet: coin selection, don't return results that exceed the max allowed weight by furszy)
#25982 (wallet: Guard against undefined behaviour by yancyribbens)
#25273 (wallet: Pass through transaction locktime and preset input sequences and scripts to CreateTransaction by achow101)
#24897 ([Draft / POC] Silent Payments by w0xlt)
#23475 (wallet: add config to prioritize a solution that doesn't create change in coin selection 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.

src/wallet/test/group_outputs_tests.cpp

src/wallet/coinselection.h

src/wallet/spend.cpp

src/wallet/test/group_outputs_tests.cpp

furszy · 2023-03-02T22:56:18Z

Thanks @S3RK for the review.

Updated per feedback (small diff), tackled the following points that made sense for me to include here:

Renamed OutputGroups to OutputGroupTypeMap to reflect what the struct really does and differentiate it from the inner struct.
Corrected the OutputGroups, now OutputGroupTypeMap, members comments.
And tackled @xekyo’s unneeded check.

I think that while we all agree that this work is functionality and structurally sound, we can move forward.
And tackle any new naming discussion in a follow-up work.

And not hide it inside the `OutputGroup::Insert` method. This method does not return anything if insertion fails. We can know before calling `Insert` whether the coin will be accepted or not.

furszy · 2023-03-03T21:36:09Z

Rebased due silent merge conflicts with #26889.
Ready to go now.

S3RK · 2023-03-06T09:08:11Z

utACK 1cfed6c (also reviewed the tests)

src/wallet/test/group_outputs_tests.cpp

src/wallet/coinselection.cpp

The following scenarios are covered: 1) 10 UTXO with the same script: partial spends is enabled --> outputs must not be grouped. 2) 10 UTXO with the same script: partial spends disabled --> outputs must be grouped. 3) 20 UTXO, 10 one from scriptA + 10 from scriptB: a) if partial spends is enabled --> outputs must not be grouped. b) if partial spends is not enabled --> 2 output groups expected (one per script). 3) Try to add a negative output (value - fee < 0): a) if "positive_only" is enabled --> negative output must be skipped. b) if "positive_only" is disabled --> negative output must be added. 4) Try to add a non-eligible UTXO (due not fulfilling the min depth target for "not mine" UTXOs) --> it must not be added to any group 5) Try to add a non-eligible UTXO (due not fulfilling the min depth target for "mine" UTXOs) --> it must not be added to any group 6) Surpass the 'OUTPUT_GROUP_MAX_ENTRIES' size and verify that a second partial group gets created.

Initial steps towards sharing COutput instances across all possible OutputGroups (instead of copying them time after time).

…sult Another step towards the single OutputGroups calculation goal

…td::vector No functional changes. Only cosmetic changes to simplify the follow-up commit.

The 'GroupOutputs()' function performs the same calculations for only-positive and mixed groups, the only difference is that when we look for only-positive groups, we discard negative utxos. So, instead of wasting resources calling GroupOutputs() for positive-only first, then call it again to include the negative ones in the result, we can execute GroupOutputs() only once, including in the response both group types (positive-only and mixed).

Optimizes coin selection by performing the "group outputs" procedure only once, outside the "attempt selection" process. Avoiding the repeated execution of the 'GroupOutputs' operation that occurs on each coin eligibility filters (up to 8 of them); then for every coin vector type plus one for all the coins together. This also let us not perform coin selection over coin eligibility filtered groups that don't add new elements. (because, if the previous round failed, and the subsequent one has the same coins, then this new round will fail again).

furszy · 2023-03-06T13:06:22Z

Updated per feedback, thanks S3RK 👌🏼.

Small diff, changes are in the last test scenario and the test commit message.

S3RK · 2023-03-06T19:43:03Z

ReACK 6a302d4
Thanks for addressing feedback

theStack

re-ACK 6a302d4 🥥

(verified via git range-diff 0bb90cab...6a302d40 that since my last ACK, most review comments by Murch and S3RK have been tackled, mostly trivial refactor + terminology/naming improvements and a minor unit test adaption)

achow101 · 2023-03-06T23:19:19Z

ACK 6a302d4

…m Coin Selection 6a302d4 wallet: single output groups filtering and grouping process (furszy) bd91ed1 wallet: unify outputs grouping process (furszy) 5596200 test: coinselector_tests refactor, use CoinsResult instead of plain std::vector (furszy) 34f54a0 wallet: decouple outputs grouping process from each ChooseSelectionResult (furszy) 461f082 refactor: make OutputGroup::m_outputs field a vector of shared_ptr (furszy) d8e749b test: wallet, add coverage for outputs grouping process (furszy) 06ec8f9 wallet: make OutputGroup "positive_only" filter explicit (furszy) Pull request description: The idea originates from bitcoin#24845 (comment). Note: For clarity, it's recommended to start reviewing from the end result to understand the structure of the flow. #### GroupOutputs function rationale: If "Avoid Partial Spends" is enabled, the function gathers outputs with the same script together inside a container. So Coin Selection can treats them as if them were just one possible input and either select them all or not select them. #### How the Inputs Fetch + Selection process roughly works: ``` 1. Fetch user’s manually selected inputs. 2. Fetch wallet available coins (walks through the entire wallet txes map) and insert them into a set of vectors (each vector store outputs from a single type). 3. Coin Selection Process: Call `AttemptSelection` 8 times. Each of them expands the coin eligibility filter (accepting a larger subset of coins in the calculation) until it founds a solutions or completely fails if no solutions gets founds after the 8 rounds. Each `AttemptSelection` call performs the following actions: - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and a combination of all of them): Call ‘ChooseSelectionResult’ providing the respective, filtered by type, coins vector. Which: I. Groups the outputs vector twice (one for positive only and a second one who includes the negative ones as well). - GroupOutputs walks-through the entire inputted coins vector one time at least, + more if we are avoiding partial spends, to generate a vector of OutputGroups. II. Then performs every coin selection algorithm using the recently created vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD. III. Then returns the best solution out of them. ``` We perform the general operation of gathering outputs, with the same script, into a single container inside: Each coins selection attempt (8 times —> each coin eligibility filter), for each of the outputs vector who were filtered by type (plus another one joining all the outputs as well if needed), twice (one for the positive only outputs effective value and a second one for all of them). So, in the worst case scenario where no solution is found after the 8 Coin Selection attempts, the `GroupOutputs` function is called 80 times (8 * 5 * 2). #### Improvements: This proposal streamlines the process so that the output groups, filtered by coin eligibility and type, are created in a single loop outside of the Coin Selection Process. The new process is as follows: ``` 1. Fetch user’s manually selected inputs. 2. Fetch wallet available coins. 3. Group outputs by each coin eligibility filter and each different output type found. 4. Coin Selection Process: Call AttemptSelection 8 times. Each of them expands the coin eligibility filter (accepting different output groups) until it founds a solutions or completely fails if no solutions gets founds after the 8 rounds. Each ‘AttemptSelection’ call performs the following actions: - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and all of them): A. Call ‘ChooseSelectionResult’ providing the respective, filtered by type, output group. Which: I. Performs every coin selection algorithm using the provided vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD. II. Then returns the best solution out of them. ``` Extra Note: The next steps after this PR will be to: 1) Merge `AvailableCoins` and `GroupOutputs` processes. 2) Skip entire coin selection rounds if no new coins are added into the subsequent round. 3) Remove global feerates from the OutputGroup class. 4) Remove secondary "grouped" tx creation from `CreateTransactionInternal` by running Coin Selection results over the aps grouped outputs vs non-aps ones. ACKs for top commit: S3RK: ReACK 6a302d4 achow101: ACK 6a302d4 theStack: re-ACK 6a302d4 🥥 Tree-SHA512: dff849063be328e7d9c358ec80239a6db2cd6131963b511b83699b95b337d3106263507eaba0119eaac63e6ac21c6c42d187ae23d79d9220b90c323d44b01d24

475c20a wallet: remove coin control arg from AutomaticCoinSelection (furszy) 8a55831 wallet: remove unused methods (furszy) 8471967 wallet: GroupOutput, remove unneeded "spendable" check (furszy) a9aa041 wallet: OutputGroup, remove unused effective_feerate member (furszy) 99034b2 wallet: APS, don't create empty groups (furszy) 805f399 wallet: do not make two COutputs, use shared_ptr (furszy) Pull request description: Few small findings post-#25806 and extra cleanups, nothing biggie. ACKs for top commit: S3RK: Code review ACK 475c20a Xekyo: utACK 475c20a achow101: ACK 475c20a Tree-SHA512: df45efebd6e2e4ecac619d6ecef794979c328a2d6ef532e25124d0dc1c72b55ccf13498f61fb65958b907bfba6a72ed569bf34eb5fbe35419632fe0406e78798

475c20a wallet: remove coin control arg from AutomaticCoinSelection (furszy) 8a55831 wallet: remove unused methods (furszy) 8471967 wallet: GroupOutput, remove unneeded "spendable" check (furszy) a9aa041 wallet: OutputGroup, remove unused effective_feerate member (furszy) 99034b2 wallet: APS, don't create empty groups (furszy) 805f399 wallet: do not make two COutputs, use shared_ptr (furszy) Pull request description: Few small findings post-bitcoin#25806 and extra cleanups, nothing biggie. ACKs for top commit: S3RK: Code review ACK 475c20a Xekyo: utACK 475c20a achow101: ACK 475c20a Tree-SHA512: df45efebd6e2e4ecac619d6ecef794979c328a2d6ef532e25124d0dc1c72b55ccf13498f61fb65958b907bfba6a72ed569bf34eb5fbe35419632fe0406e78798

murchandamus

Post merge ACK 6a302d4

murchandamus · 2023-04-10T16:54:06Z

src/wallet/test/fuzz/coinselection.cpp

@@ -29,8 +29,10 @@ static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vect
    auto output_group = OutputGroup(coin_params);
    bool valid_outputgroup{false};
    for (auto& coin : coins) {
-        output_group.Insert(coin, /*ancestors=*/0, /*descendants=*/0, positive_only);
-        // If positive_only was specified, nothing may have been inserted, leading to an empty output group
+        if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {


Suggested change

if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {

if (!positive_only || (coin.GetEffectiveValue() > 0)) {

fanquake added the Wallet label Aug 8, 2022

furszy mentioned this pull request Aug 9, 2022

wallet: Check max transaction weight in CoinSelection #25729

Merged

DrahtBot added the Needs rebase label Aug 17, 2022

furszy changed the title ~~wallet: single outputs grouping calculation~~ wallet: single group outputs calculation, decouple it from Coin Selection Sep 6, 2022

furszy changed the title ~~wallet: single group outputs calculation, decouple it from Coin Selection~~ wallet: single group outputs calculation, decoupled from Coin Selection Sep 6, 2022

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from 27eac5e to bbac1ad Compare October 27, 2022 22:40

furszy changed the title ~~wallet: single group outputs calculation, decoupled from Coin Selection~~ wallet: group outputs only once, decouple it from Coin Selection Oct 27, 2022

DrahtBot removed the Needs rebase label Oct 27, 2022

This was referenced Oct 28, 2022

clang-tidy: fixup named argument comments #26238

Merged

wallet: Guard against undefined behaviour #25982

Closed

refactor: use braced init for integer literals instead of c style casts #23829

Merged

DrahtBot mentioned this pull request Nov 4, 2022

Bump unconfirmed ancestor transactions to target feerate #26152

Merged

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from bbac1ad to ae41a8b Compare November 16, 2022 16:01

aureleoules reviewed Nov 16, 2022

View reviewed changes

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from ae41a8b to 9e97767 Compare November 17, 2022 14:18

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from 0bb90ca to ae0dd2b Compare March 2, 2023 22:54

wallet: make OutputGroup "positive_only" filter explicit

06ec8f9

And not hide it inside the `OutputGroup::Insert` method. This method does not return anything if insertion fails. We can know before calling `Insert` whether the coin will be accepted or not.

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from ae0dd2b to 1cfed6c Compare March 3, 2023 21:34

S3RK reviewed Mar 6, 2023

View reviewed changes

src/wallet/test/group_outputs_tests.cpp Outdated Show resolved Hide resolved

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

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

furszy added 6 commits March 6, 2023 09:45

refactor: make OutputGroup::m_outputs field a vector of shared_ptr

461f082

Initial steps towards sharing COutput instances across all possible OutputGroups (instead of copying them time after time).

wallet: decouple outputs grouping process from each ChooseSelectionRe…

34f54a0

…sult Another step towards the single OutputGroups calculation goal

test: coinselector_tests refactor, use CoinsResult instead of plain s…

5596200

…td::vector No functional changes. Only cosmetic changes to simplify the follow-up commit.

DrahtBot requested review from achow101 and theStack March 6, 2023 12:50

furszy force-pushed the 2022_wallet_single_outputs_grouping_process branch from 1cfed6c to 6a302d4 Compare March 6, 2023 13:03

theStack approved these changes Mar 6, 2023

View reviewed changes

achow101 merged commit 4ea3a8b into bitcoin:master Mar 6, 2023

furszy mentioned this pull request Mar 8, 2023

wallet: 25806 follow-up #27227

Merged

furszy mentioned this pull request Apr 3, 2023

Mark "too-long-mempool-chain error msg" completed NYDIG/bitcoin-task-bounty#32

Merged

murchandamus reviewed Apr 10, 2023

View reviewed changes

furszy deleted the 2022_wallet_single_outputs_grouping_process branch May 27, 2023 01:47

bitcoin locked and limited conversation to collaborators May 26, 2024

	if (!positive_only \|\| (positive_only && coin.GetEffectiveValue() > 0)) {
	if (!positive_only \|\| (coin.GetEffectiveValue() > 0)) {

wallet: group outputs only once, decouple it from Coin Selection #25806

wallet: group outputs only once, decouple it from Coin Selection #25806

Uh oh!

Conversation

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

Uh oh!

GroupOutputs function rationale:

How the Inputs Fetch + Selection process roughly works:

Improvements:

Uh oh!

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

Uh oh!

Reviews

Conflicts

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

furszy commented Mar 2, 2023

Uh oh!

furszy commented Mar 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

S3RK commented Mar 6, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

furszy commented Mar 6, 2023

Uh oh!

S3RK commented Mar 6, 2023

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Mar 6, 2023

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

murchandamus Apr 10, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

furszy commented Aug 8, 2022 •

edited

Loading

DrahtBot commented Aug 9, 2022 •

edited

Loading

furszy commented Mar 3, 2023 •

edited

Loading