wallet: return change from SelectionResult #25647

S3RK · 2022-07-20T07:54:57Z

Benefits:

more accurate waste calculation for knapsack. Waste calculation is now consistent with tx building code. Before we always assumed change for knapsack even when the solution is changeless4.
simpler tx building code. Only create change output when it's needed
makes it easier to correctly account for fees for CPFP inputs (should be done in a follow up)

In the first three commits we fix the code to accurately track selection target in SelectionResult::m_target
Then we introduce new variable min_change that represents the minimum viable change amount
Then we introduce SelectionResult::GetChange() which incapsulates dropping change for fee logic and uses correct values of SelectionResult::m_target
Then we use SelectionResult::GetChange() in both tx building and waste calculation code

This PR is a refactoring and shouldn't change the behaviour.
There is only one known small change (arguably a bug fix). Before we dropped change output if it's smaller than cost_of_change after paying change fees. This is incorrect as cost_of_change already includes change_fee.

DrahtBot · 2022-07-20T10:51:16Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#25685 (wallet: Faster transaction creation by removing pre-set-inputs fetching responsibility from Coin Selection by furszy)
#25273 (wallet: Pass through transaction locktime and preset input sequences and scripts to CreateTransaction by achow101)

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.

S3RK · 2022-07-21T07:32:49Z

Simulation results here https://github.com/S3RK/coin-selection-simulation/tree/25647-sim/results/25647

src/wallet/coinselection.h

src/wallet/spend.cpp

src/wallet/coinselection.cpp

src/wallet/spend.cpp

src/wallet/coinselection.cpp

Requires bitcoin#25647

achow101 · 2022-08-10T17:31:17Z

ACK e763496

murchandamus

ACK e763496

src/wallet/spend.cpp

src/wallet/coinselection.h

SelectionResult::m_target should be equal to actual selection target. Selection target is the sum of all recipient amounts plus non input fees. So we need to remove change_fee from the m_target. It's safe because change target is always greater than the change fee, so we can always cover fees if change output is created.

When we have preselected inputs the coin selection search target is reduced by the sum of (effective) values. This causes incorrect m_target value. Create separate instance of SelectionResult for all the preselected inputs and set the target equal to the sum of (effective) values. Target for preselected SelectionResult is equal to the delta for the search target. To get the final SelectionResult with accurate m_target we merge both SelectionResult instances.

S3RK · 2022-08-15T07:36:48Z

Added one commit c8cf08e and rebased on master again

furszy · 2022-08-16T20:53:42Z

src/wallet/coinselection.cpp

+    if (m_algo == SelectionAlgorithm::MANUAL) {
+        m_algo = other.m_algo;


for the current sources, this code block is a no-op.

the only time when we are entering here is when we merge a manual selection result with another manual selection result.

furszy · 2022-08-17T03:31:22Z

src/wallet/spend.cpp

+    // The smallest change amount should be:
+    // 1. at least equal to dust threshold
+    // 2. at least 1 sat greater than fees to spend it at m_discard_feerate
+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
+    const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size);
+    coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust);


hmm, this doesn't seems to be right:

The dust amount is taken from --> GetDustThreshold which receives the change output, serializes it and uses magic numbers to calculate the input vsize (it's a general minimum input vsize calculation for an output), then calls discard_fee.Get(vsize) with it to get the dust amount.

The change_spend_fee is taken from --> discard_fee.Get(change_spend_size) , where change_spend_size is the result of CalculateMaximumSignedInputSize(output) which is the real vsize calculation of a signed input that spends the change output (we don't hardcode numbers here, we create the input and sign it).

In other words:

The only difference between the dust and change_spend_fee variables is the vsize calculation (both are doing m_discard_fee.GetFee(vsize)), and:

for dust, vsize is calculated from hardcoded numbers to get the minimum theoretical possible size.

for change_spend_fee, vsize is calculated creating an input and dummy signing it.

So, dust will always be smaller than change_spend_fee right?

Extra note, had a great convo about this topic with @theStack. He mentioned that you might wanted to use wallet.chain().relayDustFee() instead of coin_selection_params.m_discard_feerate in the dust amount calculation?

What's implemented here matches the behavior in master. For this PR, I think this is correct.

However we should probably use m_long_term_feerate for calculating the change spend fee rather than the discard feerate. This would make it match how we calculate "future spends" for all of our inputs.

you might wanted to use wallet.chain().relayDustFee() instead of coin_selection_params.m_discard_feerate in the dust amount calculation?

I think discard feerate is correct here. It is the maximum of the longest term fee estimate and the dust relay fee. As the name suggests, it is the feerate that we are willing to discard at, so I think it makes sense to keep it as is.

you might wanted to use wallet.chain().relayDustFee() instead of coin_selection_params.m_discard_feerate in the dust amount calculation?

I think discard feerate is correct here. It is the maximum of the longest term fee estimate and the dust relay fee. As the name suggests, it is the feerate that we are willing to discard at, so I think it makes sense to keep it as is.

Isn't the point of setting the smallest change amount to "at least equal to dust threshold" to ensure that the created tx can enter our own mempool now, rather than somewhen in the future (considering that we run a node with a possibly customized -dustrelayfee=... option)? As an example, if one would set -dustrelayfee=... to a high value and discardfee=0, a tx with a change output could be created that is rejected from our mempool (due to being IsDust and therefore !IsStandardTx()) and thus can't be sent. That's why my assumption was that we want to call GetDustThreshold with the dustRelayFee instead:

- const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate); + const auto dust = GetDustThreshold(change_prototype_txout, wallet.chain.relayDustFee());

(Am I missing something?)

As an example, if one would set -dustrelayfee=... to a high value and discardfee=0, a tx with a change output could be created that is rejected from our mempool

Then the dustrelayfee is what m_discard_fee is set to. See GetDiscardRate in src/wallet/fees.cpp.

As an example, if one would set -dustrelayfee=... to a high value and discardfee=0, a tx with a change output could be created that is rejected from our mempool

Then the dustrelayfee is what m_discard_fee is set to. See GetDiscardRate in src/wallet/fees.cpp.

Oh right, I completely overlooked this following line of code, d'oh! 🤦‍♂️

bitcoin/src/wallet/fees.cpp

Line 91 in a8f6954

discard_rate = std::max(discard_rate, wallet.chain().relayDustFee());

I believe we should get rid of discard fee rate and replace it with dust relay fee rate and long term fee rate. For this PR I decide to stick to the current implementation to limit the scope. I'll open an issue to deprecate discard fee rate if there is none yet.

furszy

Code review ACK 4fef534

Great step forward, this area needs so much more love.

achow101 · 2022-08-17T21:51:21Z

ACK 4fef534

theStack · 2022-08-17T22:05:12Z

Concept ACK

w0xlt

Approach ACK.

w0xlt

ACK 4fef534

murchandamus

Sorry for the slow re-review. I don't think these two are blockers if they're issues at all, but I figured it might be good to bring them up.

murchandamus · 2022-08-22T12:41:49Z

src/wallet/coinselection.cpp

+    //  - change_fee
+    const CAmount change = m_use_effective
+                           ? GetSelectedEffectiveValue() - m_target - change_fee
+                           : GetSelectedValue() - m_target;


In “wallet: add SelectionResult::GetChange” (15e97a6):

If m_target includes the non_input_fee, but the recipient is supposed to pay for all fees, shouldn't SFFO branch here rather be GetSelectedValue() - (m_target - non_input_fee) or GetSelectedValue() - recipients_sum?

With SFFO non_input_fee is always set to 0. We can probably make this simpler and cleaner, let's discuss it on the wallet meeting or in some other place.

Ah okay, that explains it. Thanks

murchandamus · 2022-08-22T13:02:29Z

src/wallet/spend.cpp

    // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
    // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
    // permissive CoinEligibilityFilter.
    std::optional<SelectionResult> res = [&] {
        // Pre-selected inputs already cover the target amount.
-        if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue, SelectionAlgorithm::MANUAL));
+        if (value_to_select <= 0) return std::make_optional(SelectionResult(value_to_select, SelectionAlgorithm::MANUAL));


In “wallet: account for preselected inputs in target” (e3210a7):

This is a question about the commit message:
Sorry, if I'm being dense, but how was “deducting the effective values of the preselected inputs from m_target” leading to a different result than “creating a separate SelectionResult with the target set to the effective values of the preselected inputs and then starting the selection targeting the delta between that and the search target”?

It sounds to me that in both cases that would be m_target - effective_value_of_preselection under the hood? I assume there is a subtle difference here, but it's not obvious to me from the description. Is the difference that once we use m_target and “search target” is now composed differently? Please feel free to ignore if this has been covered elsewhere, and I just missed it.

(Edited to clarify that I'm inquiring about the commit message.)

The newly added Merge function will add the m_targets of the two SelectionResults. In the event that value_to_select <= 0, using nTargetValue in this SelectionResult will add nTargetValueto them_targetstored in the preset inputsSelectionResult`. This is incorrect because the target was already met and we're actually just adding it twice.

Also note how all of the other SelectionResults returned by this function all use value_to_select.

m_target is not modified after construction, and nTargetValue is not modified at all in this function - it includes any value already selected by preset inputs.

Answering my own question after talking to S3RK out of band:

The correct m_target is needed to calculate the change in advance. Previously, the preselection approach was reducing m_target to reflect that some funds had already been picked, and now storing them in a SelectionResult and combining the two before calculating the change will be operating on basis of the correct m_target instead.

Ah thanks, @achow101, the case with the negative target makes it even clearer how this is better.

Small extra add to the topic in case you haven't seen it; the pre-set inputs workflow (this stuff) is being decoupled from the coin selection process in #25685. Which should make the flow clearer and less error-prone.

murchandamus · 2022-08-22T16:31:39Z

crACK 4fef534

fanquake added the Wallet label Jul 20, 2022

fanquake requested a review from murchandamus July 20, 2022 08:54

This was referenced Jul 20, 2022

wallet: Pass through transaction locktime and preset input sequences and scripts to CreateTransaction #25273

Merged

rpc: Filter inputs by type during CoinSelection #25183

Closed

wallet: avoid mixing different OutputTypes during coin selection #24584

Merged

S3RK force-pushed the coin_selection_get_change branch from f5e45c4 to 45ee9d3 Compare July 21, 2022 05:50

This was referenced Jul 21, 2022

refactor: Add util::Result failure values, multiple error and warning messages #25665

Open

refactor: Replace BResult with util::Result #25721

Merged

wallet: Check max transaction weight in CoinSelection #25729

Merged

murchandamus reviewed Jul 28, 2022

View reviewed changes

DrahtBot added the Needs rebase label Jul 28, 2022

murchandamus added a commit to murchandamus/bitcoin that referenced this pull request Jul 29, 2022

wallet: Prefer smaller change amount in tiebreaker

ab80f3a

Requires bitcoin#25647

murchandamus added a commit to murchandamus/bitcoin that referenced this pull request Jul 29, 2022

wallet: Prefer smaller change amount in tiebreaker

5738e92

Requires bitcoin#25647

murchandamus mentioned this pull request Jul 29, 2022

Use change amount as tiebreaker for SelectionResults #25742

Closed

S3RK mentioned this pull request Aug 8, 2022

wallet: Use GetSelectionAmount in ApproximateBestSubset #22686

Merged

S3RK force-pushed the coin_selection_get_change branch from 45ee9d3 to e763496 Compare August 9, 2022 07:40

DrahtBot removed the Needs rebase label Aug 9, 2022

This was referenced Aug 9, 2022

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

Merged

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

Merged

murchandamus reviewed Aug 10, 2022

View reviewed changes

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

src/wallet/coinselection.h Show resolved Hide resolved

S3RK added 7 commits August 15, 2022 09:34

wallet: ensure m_min_change_target always covers change fee

c8cf08e

wallet: add SelectionResult::Merge

f8e7963

wallet: calculate and store min_viable_change

72cad28

wallet: add SelectionResult::GetChange

15e97a6

wallet: use GetChange() in tx building

87e0ef9

wallet: use GetChange() when computing waste

4fef534

S3RK force-pushed the coin_selection_get_change branch from e87606d to 4fef534 Compare August 15, 2022 07:35

furszy reviewed Aug 17, 2022

View reviewed changes

furszy approved these changes Aug 17, 2022

View reviewed changes

w0xlt reviewed Aug 18, 2022

View reviewed changes

w0xlt approved these changes Aug 19, 2022

View reviewed changes

murchandamus reviewed Aug 22, 2022

View reviewed changes

achow101 merged commit 2bd9aa5 into bitcoin:master Aug 22, 2022

bitcoin locked and limited conversation to collaborators Aug 22, 2023

		if (m_algo == SelectionAlgorithm::MANUAL) {
		m_algo = other.m_algo;

wallet: return change from SelectionResult #25647

wallet: return change from SelectionResult #25647

Uh oh!

Conversation

S3RK commented Jul 20, 2022

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

S3RK commented Jul 21, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

achow101 commented Aug 10, 2022

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

S3RK commented Aug 15, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

furszy left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Aug 17, 2022

Uh oh!

theStack commented Aug 17, 2022

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

DrahtBot commented Jul 20, 2022 •

edited

Loading

furszy Aug 17, 2022 •

edited

Loading

furszy Aug 17, 2022 •

edited

Loading

murchandamus Aug 22, 2022 •

edited

Loading

achow101 Aug 22, 2022 •

edited

Loading