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:
01. Fetch user’s manually selected inputs.
12. 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).
23. Coin Selection Process:
3 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.
4
5 Each `AttemptSelection` call performs the following actions:
6 - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and a combination of all of them):
7 Call ‘ChooseSelectionResult’ providing the respective, filtered by type, coins vector. Which:
8 I. Groups the outputs vector twice (one for positive only and a second one who includes the negative ones as well).
9 - 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.
10 II. Then performs every coin selection algorithm using the recently created vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD.
11 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:
01. Fetch user’s manually selected inputs.
12. Fetch wallet available coins.
23. Group outputs by each coin eligibility filter and each different output type found.
34. Coin Selection Process:
4 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.
5
6 Each ‘AttemptSelection’ call performs the following actions:
7 - For each output type supported by the wallet (P2SH, P2PK, P2WPKH, P2WSH and all of them):
8 A. Call ‘ChooseSelectionResult’ providing the respective, filtered by type, output group. Which:
9 I. Performs every coin selection algorithm using the provided vector of OutputGroup: (1) BnB, (2) knapsack and (3) SRD.
10 II. Then returns the best solution out of them.
Extra Note: The next steps after this PR will be to:
- Merge
AvailableCoinsandGroupOutputsprocesses. - 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
CreateTransactionInternalby running Coin Selection results over the aps grouped outputs vs non-aps ones.
