wallet: return change from SelectionResult

S3RK commented at 7:54 am on July 20, 2022: contributor

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.

fanquake added the label Wallet on Jul 20, 2022

fanquake requested review from murchandamus on Jul 20, 2022

DrahtBot commented at 10:51 am on July 20, 2022: contributor

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 force-pushed on Jul 21, 2022

S3RK commented at 7:32 am on July 21, 2022: contributor

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

in src/wallet/coinselection.h:129 in ef71f05749 outdated

122@@ -123,6 +123,10 @@ struct CoinSelectionParams {
123     /** Mininmum change to target in Knapsack solver: select coins to cover the payment and
124      * at least this value of change. */
125     CAmount m_min_change_target{0};
126+    /** Minimum amount for creating a change output.
127+     * If change budget is smaller than min_change then we forgo creation of change output.
128+     */
129+    CAmount min_change{0};

murchandamus commented at 7:07 pm on July 28, 2022:

In commit “wallet: calculate and store min_change” (ef71f057495b0a152667857ab277c0e76e76ad76):

When I read min_change I think of the modifier of the target for the coin selection parameters. This seems to rather be the upper bound for dust. Perhaps we should use a different name here instead of the same term.

0    CAmount min_viable_change{0};

S3RK commented at 7:28 am on August 9, 2022:

done

in src/wallet/spend.cpp:753 in ef71f05749 outdated

744@@ -745,6 +745,13 @@ static BResult<CreatedTransactionResult> CreateTransactionInternal(
745     coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
746     coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee;
747 
748+    // The smallest change amount should be:
749+    // 1. at least equal to dust threshold
750+    // 2. at least 1 sat greater than fees to spend it at m_discard_feerate
751+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
752+    const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size);
753+    coin_selection_params.min_change = std::max(change_spend_fee + 1, dust);

murchandamus commented at 7:13 pm on July 28, 2022:

In commit “wallet: calculate and store min_change” (ef71f057495b0a152667857ab277c0e76e76ad76): Shouldn’t this be the same criteria we use for discarding the remainder? Also, I think the +1 should be added to either of the terms, so we can pull it out of the parens.

0    coin_selection_params.min_change = std::max(coin_selection_params.m_cost_of_change, dust) + 1;

S3RK commented at 7:24 am on August 9, 2022:

I’m not sure I understand the question about the remainder. I’ve tried to keep the existing behaviour unchanged.

We can totally add +1 to the dust threshold but that would be a change in behaviour. Are we sure we want to do it?

achow101 commented at 6:00 pm on August 9, 2022:

The changeless window is based on cost_of_change, not just change_spend_fee. So the minimum viable change should be cost_of_change + 1.

I agree that the + 1 should not be applied to the dust threshold. The existing behavior throws away change when it is < dust or <= cost of change. So that’s equivalent to < dust or < cost of change + 1.

murchandamus commented at 8:54 pm on August 9, 2022:

Err, yes. You’re right, the +1 should be on coin_selection_params.m_cost_of_change

S3RK commented at 4:59 pm on August 10, 2022:

No. cost_of_change = change_fee + change_spend_fee. When we compare change To min_viable_change the change_fee is already deducted.

Think about it from this perspective, you don’t want to create a change output that is less than what it takes to spend it.

S3RK commented at 5:03 pm on August 10, 2022:

You’re right though, that right now we drop change smaller than cost_of_change after deducting the change_fee. So the change_fee is deducted twice. Which I think is a bug. But I need to disclose this in the description.

UPD: oh.. I did disclose it already.. stupid me

achow101 commented at 5:22 pm on August 10, 2022:

Ah ok. That makes sense.

murchandamus commented at 7:22 pm on August 10, 2022:

Okay, convinced. That all sounds right. Thanks for explaining

in src/wallet/coinselection.cpp:512 in 83bf6ab231 outdated

501+    if (change_budget < min_change) {
502+        return 0;
503+    }
504+
505+    return change_budget;
506+}

murchandamus commented at 7:22 pm on July 28, 2022:

In commit “wallet: add SelectionResult::GetChange” (83bf6ab231af6db030cab876b169551f438c2499):

Naming-nit: My understanding was that change_budget refers to change_amount + change_fee, but in this function change_budget is actually just change?

 0CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
 1{
 2    // change = SUM(inputs) - SUM(outputs) - fees
 3    // 1) With SFFO we don't pay any fees
 4    // 2) Otherwise we pay all the fees:
 5    //  - input fees are covered by GetSelectedEffectiveValue()
 6    //  - non_input_fee is included in m_target
 7    //  - change_fee
 8    const CAmount change = m_use_effective
 9                                  ? GetSelectedEffectiveValue() - m_target - change_fee
10                                  : GetSelectedValue() - m_target;
11
12    if (change < min_viable_change) {
13        return 0;
14    }
15
16    return change;
17}

S3RK commented at 7:28 am on August 9, 2022:

done

in src/wallet/spend.cpp:917 in 64af431f32 outdated

817+            return _("Transaction change output index out of range");
818+        }
819+        txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
820+    } else {
821+        nChangePosInOut = -1;
822     }

murchandamus commented at 7:29 pm on July 28, 2022:

In commit “wallet: use GetChange() in tx building” (64af431f328de586b3e8769ec875a7cf9083b44e):

Style-nit: Inconsistent line breaking between if and brace.

S3RK commented at 7:24 am on August 9, 2022:

I think I fixed it

in src/wallet/coinselection.cpp:159 in 45ee9d3a73 outdated

155@@ -156,7 +156,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
156     for (const size_t& i : best_selection) {
157         result.AddInput(utxo_pool.at(i));
158     }
159-    result.ComputeAndSetWaste(CAmount{0});
160+    result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});

murchandamus commented at 8:09 pm on July 28, 2022:

In “wallet: use GetChange() when computing waste” (45ee9d3a737cc23babb9200c4d75d7dae4dc6700):

Shouldn’t the first value here be the maximum of cost_of_change and dust_threshold? I think that the former can be lower than the latter for feerates below discard_feerate.

S3RK commented at 7:41 am on August 9, 2022:

Technically yes, but it doesn’t matter in this case because BnB would never have change more than cost_of_change.

I’d say a better way to fix it is to use min_viable_change for the upper bound of BnB. But I don’t want to do expand the scope of this PR. Can we leave it for the follow up?

murchandamus commented at 7:35 pm on August 10, 2022:

Ah right, and since this call originates from SelectCoinsBnB(…) that’s sufficient of course.

Yeah, doing the BnB upper bound separately sounds fine to me.

in src/wallet/coinselection.cpp:409 in 45ee9d3a73 outdated

405@@ -406,9 +406,15 @@ CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
406     }
407 }
408 
409-void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
410+void SelectionResult::ComputeAndSetWaste(const CAmount min_change, const CAmount change_cost, const CAmount change_fee)

murchandamus commented at 8:18 pm on July 28, 2022:

In “wallet: use GetChange() when computing waste” (45ee9d3a737cc23babb9200c4d75d7dae4dc6700):

As suggested before, I’d prefer min_viable_change for this value here and below.

S3RK commented at 7:39 am on August 9, 2022:

done

DrahtBot added the label Needs rebase on Jul 28, 2022

murchandamus referenced this in commit ab80f3a8a1 on Jul 29, 2022

murchandamus referenced this in commit 5738e926e6 on Jul 29, 2022

S3RK force-pushed on Aug 9, 2022

DrahtBot removed the label Needs rebase on Aug 9, 2022

achow101 commented at 5:31 pm on August 10, 2022: member

ACK e763496caab2f9b9f9ba038f7a020caa56997c1b

in src/wallet/spend.cpp:499 in 98d5dd26ae outdated

504-    if (!coin_selection_params.m_subtract_fee_outputs) {
505-        target_with_change += coin_selection_params.m_change_fee;
506-    }
507-    if (auto knapsack_result{KnapsackSolver(all_groups, target_with_change, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
508+    std::vector<OutputGroup> all_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, /*positive_only=*/false);
509+    if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {

murchandamus commented at 8:01 pm on August 10, 2022:

Just a headscratcher: In the commit message of “wallet: accurate SelectionResult::m_target” (98d5dd26aec30ec63b555afc844281a4a04bd0fb) you write:

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.

It’s not clear to me why the change target is always greater than change fee. Are you just alluding to the minimum change being more than the change fee even beyond 1,000 s/vB, or does the change fee actually get added anywhere that I’m missing?

S3RK commented at 8:00 am on August 11, 2022:

Good catch. Indeed what I meant is that m_change_target is at least CHANGE_LOWER which in most cases should be bigger than change_fee, but at high enough fee rate it doesn’t hold.

Maybe we can ensure that m_change_target is at least change_fee by making CHANGE_LOWER dynamic and equal to max(50000, change_fee). @Xekyo @achow101 wdyt?

furszy commented at 2:06 pm on August 11, 2022:

Hmm, isn’t m_change_target an unused field right now?

S3RK commented at 6:07 am on August 12, 2022:

@furszy #25825

S3RK commented at 7:36 am on August 15, 2022:

I’ve added c8cf08ea743e430c2bf3fe46439594257b0937e5 to address this. Please review

in src/wallet/coinselection.h:129 in 84f871db7b outdated

122@@ -123,6 +123,10 @@ struct CoinSelectionParams {
123     /** Mininmum change to target in Knapsack solver: select coins to cover the payment and
124      * at least this value of change. */
125     CAmount m_min_change_target{0};
126+    /** Minimum amount for creating a change output.
127+     * If change budget is smaller than min_change then we forgo creation of change output.
128+     */
129+    CAmount min_viable_change{0};

murchandamus commented at 8:49 pm on August 10, 2022:

Nit: In wallet: calculate and store min_change (84f871db7bc2e74c5b9ebdd4690a9eb5c79ef334) the change introduces now min_viable_change but the commit message still says min_change.

S3RK commented at 8:01 am on August 11, 2022:

ack. I’ll fix it on the next push

S3RK commented at 7:35 am on August 15, 2022:

done

murchandamus commented at 8:58 pm on August 10, 2022: contributor

ACK e763496caab2f9b9f9ba038f7a020caa56997c1b

wallet: ensure m_min_change_target always covers change fee c8cf08ea74

wallet: accurate SelectionResult::m_target

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.

06f558e4e2

wallet: add SelectionResult::Merge f8e796348b

wallet: account for preselected inputs in target

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.

e3210a7225

wallet: calculate and store min_viable_change 72cad28da0

wallet: add SelectionResult::GetChange 15e97a6886

wallet: use GetChange() in tx building 87e0ef9031

wallet: use GetChange() when computing waste 4fef534428

S3RK force-pushed on Aug 15, 2022

S3RK commented at 7:36 am on August 15, 2022: contributor

Added one commit c8cf08ea743e430c2bf3fe46439594257b0937e5 and rebased on master again

in src/wallet/coinselection.cpp:441 in f8e796348b outdated

432@@ -433,6 +433,16 @@ void SelectionResult::AddInput(const OutputGroup& group)
433     m_use_effective = !group.m_subtract_fee_outputs;
434 }
435 
436+void SelectionResult::Merge(const SelectionResult& other)
437+{
438+    m_target += other.m_target;
439+    m_use_effective |= other.m_use_effective;
440+    if (m_algo == SelectionAlgorithm::MANUAL) {
441+        m_algo = other.m_algo;

furszy commented at 8:53 pm on August 16, 2022:

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.

in src/wallet/spend.cpp:863 in 72cad28da0 outdated

854@@ -855,6 +855,13 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
855 
856     coin_selection_params.m_min_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), coin_selection_params.m_change_fee, rng_fast);
857 
858+    // The smallest change amount should be:
859+    // 1. at least equal to dust threshold
860+    // 2. at least 1 sat greater than fees to spend it at m_discard_feerate
861+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
862+    const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size);
863+    coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust);

furszy commented at 3:31 am on August 17, 2022:

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?

furszy commented at 3:37 am on August 17, 2022:

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?

achow101 commented at 3:57 am on August 17, 2022:

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.

theStack commented at 11:03 am on August 17, 2022:

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:

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

(Am I missing something?)

achow101 commented at 2:42 pm on August 17, 2022:

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.

theStack commented at 10:03 pm on August 17, 2022:

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! 🤦‍♂️

https://github.com/bitcoin/bitcoin/blob/a8f69541ad53a76d5f69044ba829069d225a4af1/src/wallet/fees.cpp#L91

S3RK commented at 6:13 am on August 22, 2022:

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 approved

furszy commented at 7:10 pm on August 17, 2022: member

Code review ACK 4fef5344

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

achow101 commented at 9:51 pm on August 17, 2022: member

ACK 4fef5344288e454460b80db0316294e1ec1ad8ad

theStack commented at 10:05 pm on August 17, 2022: contributor

Concept ACK

w0xlt commented at 0:41 am on August 18, 2022: contributor

Approach ACK.

w0xlt approved

w0xlt commented at 4:28 pm on August 19, 2022: contributor

ACK https://github.com/bitcoin/bitcoin/pull/25647/commits/4fef5344288e454460b80db0316294e1ec1ad8ad

in src/wallet/coinselection.cpp:499 in 15e97a6886 outdated

494+    //  - input fees are covered by GetSelectedEffectiveValue()
495+    //  - non_input_fee is included in m_target
496+    //  - change_fee
497+    const CAmount change = m_use_effective
498+                           ? GetSelectedEffectiveValue() - m_target - change_fee
499+                           : GetSelectedValue() - m_target;

murchandamus commented at 12:41 pm on August 22, 2022:

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

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?

S3RK commented at 4:20 pm on August 22, 2022:

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.

murchandamus commented at 4:27 pm on August 22, 2022:

Ah okay, that explains it. Thanks

in src/wallet/spend.cpp:618 in e3210a7225 outdated

614     // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
615     // permissive CoinEligibilityFilter.
616     std::optional<SelectionResult> res = [&] {
617         // Pre-selected inputs already cover the target amount.
618-        if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue, SelectionAlgorithm::MANUAL));
619+        if (value_to_select <= 0) return std::make_optional(SelectionResult(value_to_select, SelectionAlgorithm::MANUAL));

murchandamus commented at 1:02 pm on August 22, 2022:

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

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.)

achow101 commented at 4:25 pm on August 22, 2022:

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.

murchandamus commented at 4:30 pm on August 22, 2022:

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.

murchandamus commented at 4:34 pm on August 22, 2022:

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

furszy commented at 4:42 pm on August 22, 2022:

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 commented at 1:10 pm on August 22, 2022: contributor

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 commented at 4:31 pm on August 22, 2022: contributor

crACK 4fef5344288e454460b80db0316294e1ec1ad8ad

achow101 merged this on Aug 22, 2022

achow101 closed this on Aug 22, 2022

bitcoin locked this on Aug 22, 2023

wallet: return change from SelectionResult #25647

Conflicts