wallet: add config to prioritize a solution that doesn't create change in coin selection #23475

brunoerg · 2021-11-09T11:06:02Z

Based on #22009, Bitcoin Core execute all the coin selection algorithms and decide what solution will be used based on the waste metric. However, some users may prefer a solution that doesn't create change (privacy reason). This PR adds a config option to prioritize the BnB solution in send and fundrawtransaction.

DrahtBot · 2021-11-10T03:02:47Z

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

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)
#26129 (wallet, refactor: FundTransaction(): return out-params as util::Result structure by theStack)
#25806 (wallet: group outputs only once, decouple it 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.

lsilva01

Code Review ACK d3a434d
Perhaps a functional test for this new parameter can be added.

brunoerg · 2021-11-14T12:02:40Z

Code Review ACK d3a434d Perhaps a functional test for this new parameter can be added.

Functional test for it would be great, will work on it.

ghost · 2021-11-18T10:54:53Z

Concept ACK

achow101 · 2021-12-15T22:03:04Z

I don't think that this should be a startup option. The preferences for coin selection may be different per-wallet, or even on a per-transaction basis, so having it be global and apply to all wallets, all the time, seems incorrect. IMO the correct approach is to add the option to the options object used for send and fundrawtransaction.

brunoerg · 2021-12-17T10:50:43Z

Thanks, @achow101. I agree with you, the better approach would be add the option to the options object. Going to change it, thanks again.

brunoerg · 2022-01-06T12:32:47Z

force-pushed addressing comments from @achow101

Rspigler · 2022-01-06T21:56:14Z

ACK d6d6340

I see prioritize_no_change bool under the options argument for send as well as fundrawtransaction. Need to do more testing with spending different UTXOs. A GUI PR would be a good followup.

S3RK · 2022-01-10T09:02:02Z

Changeless txs are already somewhat prioritised since creating and spending a change increases waste metric. When you force a solution without change you forego a more economically efficient solution. The question is how much would you pay for the changeless tx? Current UX hides the price of privacy from user and could lead to confusion. May a better UX would be to specify the amount you would pay for the changeless tx (if possible).

This also conflicts with possible future improvements for BnB #23367

brunoerg · 2022-03-11T18:07:55Z

Force-pushed rebasing and addressing last @achow101's comment.

glozow · 2022-03-14T11:48:41Z

src/wallet/coincontrol.h

+    //! Prioritize a solution that doesn't generate change when selecting coins
+    bool m_prioritize_no_change = false;


Should this be in CoinSelectionParams instead?

It's in both I guess

murchandamus

Like @S3RK, I'm a bit worried that always using the result of one coin selection algorithm could have costly outcomes. Since BnB will only use UTXOs smaller than the target, we could see results such as using 50 inputs at 100 sat/vB, while there is a single UTXO that is greater than the target.

I would prefer if this option were guarded in some fashion, e.g. that its waste must be below 3× the waste of the best solution, or the option take a parameter to define a discount for the waste of BnB solutions.

Regarding the name, I prefer avoiding negations in variable, option or parameter names. What do you think about avoid_change or prefer_changeless?

luke-jr · 2022-04-26T01:57:24Z

src/bench/coin_selection.cpp

@@ -65,7 +65,7 @@ static void CoinSelection(benchmark::Bench& bench)
    const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34,
                                                    /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
                                                    /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
-                                                    /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
+                                                    /* tx_noinputs_size= */ 0, /* avoid_partial= */ false, /* prioritize no change */ false);


Suggested change

/* tx_noinputs_size= */ 0, /* avoid_partial= */ false, /* prioritize no change */ false);

/*tx_noinputs_size=*/0, /*avoid_partial=*/false, /*prioritise_no_change=*/false);

luke-jr · 2022-04-26T01:57:54Z

src/wallet/rpc/spend.cpp

@@ -417,6 +417,7 @@ void FundTransaction(CWallet& wallet, CMutableTransaction& tx, CAmount& fee_out,
                {"change_type", UniValueType(UniValue::VSTR)},
                {"includeWatching", UniValueType(UniValue::VBOOL)},
                {"include_watching", UniValueType(UniValue::VBOOL)},
+                {"prioritize_no_change", UniValueType(UniValue::VBOOL)},


Suggested change

{"prioritize_no_change", UniValueType(UniValue::VBOOL)},

{"prioritise_no_change", UniValueType(UniValue::VBOOL)},

Correct spelling at least in the API :p

English is not my first language but I think both are correct, aren't they?

btw, I am gonna change it to avoid_change, looks better.

Prioritize is the north american spelling; prioritise is the british spelling.
I believe that in our docs we use the North American spelling

luke-jr · 2022-04-26T01:58:43Z

src/wallet/coinselection.h

        change_output_size(change_output_size),
        change_spend_size(change_spend_size),
        m_effective_feerate(effective_feerate),
        m_long_term_feerate(long_term_feerate),
        m_discard_feerate(discard_feerate),
        tx_noinputs_size(tx_noinputs_size),
-        m_avoid_partial_spends(avoid_partial)
+        m_avoid_partial_spends(avoid_partial),
+        m_prioritize_no_change(prioritize_no_change)


IMO would be nice to stop this long-constructor stuff and just assign it after creation.

luke-jr · 2022-04-26T02:00:28Z

src/wallet/test/coinselector_tests.cpp

@@ -167,7 +167,7 @@ inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>
    CoinSelectionParams coin_selection_params(/* change_output_size= */ 0,
                                              /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(0),
                                              /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
-                                              /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
+                                              /* tx_noinputs_size= */ 0, /* avoid_partial= */ false, /* prioritize_no_change */ false);


luke-jr · 2022-04-26T02:00:39Z

src/wallet/test/coinselector_tests.cpp

@@ -717,7 +717,7 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
        CoinSelectionParams cs_params(/* change_output_size= */ 34,
                                      /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
                                      /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
-                                      /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
+                                      /* tx_noinputs_size= */ 0, /* avoid_partial= */ false, /* prioritize_no_change */ false);


brunoerg · 2022-04-26T12:50:01Z

Regarding the name, I prefer avoiding negations in variable, option or parameter names. What do you think about avoid_change or prefer_changeless?

avoid_change is really good, I will adopt it.

Since BnB will only use UTXOs smaller than the target, we could see results such as using 50 inputs at 100 sat/vB, while there is a single UTXO that is greater than the target.

I understand your point, but if you are using avoid_change, it means you don't matter about the cost, you just want to avoid change even it costing much more, isn't it?

…e in coin selection

brunoerg · 2022-04-26T16:12:34Z

Force-pushed rebasing and addressing avoid_change as suggested by @xekyo

murchandamus · 2022-05-27T21:34:29Z

Some thoughts on two approaches I see here. I'll compare to the status quo and refer to the approaches as avoid_change and prefer_changeless.

status quo: use SelectionResult with the best waste score

Implementation: run all coin selection algorithms, prefer SelectionResult with lowest waste
Pro:
- waste score directly correlates with fee expenses for this transaction, likely produces least fees overall
- changeless solutions are usually cheaper than solutions that create change with similarly composed input sets and get automatically preferred
Contra:
- Will sometimes not use an available changeless solution

avoid_change: always use changeless solution if it exists

Implementation: run BnB first, if there is a solution, use that solution. Only run fallback if BnB didn't find a solution
Pro:
- probably increases overall count of changeless solutions
Contra:
- will occasionally spend a chunk more in fees when the BnB solution ends up being much worse than the least wasteful solution

prefer_changeless: use changeless solution if it's not too much worse than the best solution

Implementation: reduce waste score by a fixed or relative amount for changeless SelectionResults, e.g. reduce changeless solution's waste score by 5,000 ṩ, or reduce waste score of changeless solutions by 50%.
Pro:
- probably increases overall count of changeless solutions, but maybe not as much as avoid_change
- limits exposure to overpaying
Contra:
- may skip some unattractive changeless solutions

My questions are:

What will users think they're opting into when they activate an avoid_change or prefer_changeless option?
How does the option change the overall cost?
Preferring changeless solutions in general, may generally reduce the UTXO pool which actually could overall lower the frequency of changeless solutions. Would such an option actually increase or decrease changeless solutions? E.g. on wallet: increase BnB upper limit #24752, increasing the allowance for creating changeless solutions surprised us in that it reduced the overall count of changeless solutions.

Given that BnB doesn't always have a solution, the wallet will sometimes need to create change anyway, how much headway would we actually make with this change?

My suggestion for a next step would be that we simulate this branch with avoid_change set to true and false on a few different scenarios and see how the count of changeless transactions and overall costs are affected.

brunoerg · 2022-05-30T13:55:27Z

Thanks, @xekyo!

What will users think they're opting into when they activate an avoid_change or prefer_changeless option?

I see two scenarios:
Using avoid_change users would be saying: "Please, don't generate change even if it is expensive, this is the cost I am paying for privacy". In this case, I agree avoid_change is so much aggressive but I think anyone using this option should be aware of the pros and cons.

Using prefer_changeless users would be saying: "I prefer a changeless solution but only if this one is not so expensive compared to the other ones". It's less aggressive compared to the previous one and it would have similar effects.

Q: Only run fallback if BnB didn't find a solution: If user is using avoid_change should we run fallback if BnB didn't find a solution or should we skip it and return an error like: "It wasn't able to create a changeless solution"? Thinking about it, maybe changing the approach to prefer_changeless would be better. It's not a good experience for the user to have an avoid_change option which can generate a solution with change (users don't understand our algorithms and can open an issue relating a bug, for example).

My suggestion for a next step would be that we simulate this branch with avoid_change set to true and false on a few different scenarios and see how the count of changeless transactions and overall costs are affected.

Yeah, great, I am working on it!

murchandamus · 2022-05-31T14:20:14Z

That's a good point about not running other algorithms at all when BnB doesn't return a solution. I think that a prefer_changeless option would be less of a footgun and would have a better UX. Perhaps avoid_change would work better in a flow where the user reviews the final transaction before sending it.

ishaanam

I know that the author of this PR may implement prefer_changeless instead of avoid_change, but I think that my comments are applicable under either option.

ishaanam · 2022-07-03T12:20:40Z

src/wallet/spend.cpp

@@ -384,6 +384,10 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm
    // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
    std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, true /* positive_only */);
    if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
+        bnb_result->ComputeAndSetWaste(CAmount(0));


Is this line necessary? I think SelectCoinsBnB() already calls ComputeAndSetWaste() for this result.

ishaanam · 2022-07-03T12:22:16Z

src/wallet/rpc/spend.cpp

@@ -1241,6 +1248,11 @@ RPCHelpMan send()
            // be overridden by options.add_inputs.
            coin_control.m_add_inputs = rawTx.vin.size() == 0;
            SetOptionsInputWeights(options["inputs"], options);
+
+            if (options.exists("avoid_change")) {


I think this can be removed from send() because it is already run in FundTransaction().

Hmm, interesting! Gonna check it

DrahtBot · 2023-03-07T01:10:38Z

🐙 This pull request conflicts with the target branch and needs rebase.

brunoerg · 2023-03-23T20:27:31Z

Closing for now as I haven't been working on it for a while

fanquake added the Wallet label Nov 9, 2021

brunoerg force-pushed the 2021-11-coinselection-option branch from 7ed827a to d3a434d Compare November 9, 2021 12:20

DrahtBot mentioned this pull request Nov 10, 2021

Optimize coin selection by dropping BnB upper limit #23367

Closed

brunoerg marked this pull request as ready for review November 10, 2021 10:29

DrahtBot mentioned this pull request Nov 10, 2021

wallet: Introduce SelectionResult for encapsulating a coin selection solution #22019

Merged

brunoerg mentioned this pull request Nov 10, 2021

wallet, coin selection: config option to prioritize 'no change' when possible #23372

Closed

lsilva01 reviewed Nov 13, 2021

View reviewed changes

brunoerg force-pushed the 2021-11-coinselection-option branch from d3a434d to 83e33d5 Compare November 18, 2021 10:49

DrahtBot mentioned this pull request Dec 6, 2021

wallet: Allow negative effective value inputs when subtracting fee from outputs #23534

Closed

DrahtBot added the Needs rebase label Dec 9, 2021

brunoerg marked this pull request as draft January 4, 2022 12:04

brunoerg force-pushed the 2021-11-coinselection-option branch 2 times, most recently from 6428e61 to a0da26c Compare January 5, 2022 12:44

DrahtBot removed the Needs rebase label Jan 5, 2022

brunoerg force-pushed the 2021-11-coinselection-option branch from a0da26c to d6d6340 Compare January 5, 2022 14:29

brunoerg marked this pull request as ready for review January 5, 2022 17:42

Rspigler mentioned this pull request Jan 6, 2022

prioritize_no_change GUI option bitcoin-core/gui#520

Open

DrahtBot removed the Needs rebase label Mar 11, 2022

glozow reviewed Mar 14, 2022

View reviewed changes

DrahtBot mentioned this pull request Mar 14, 2022

wallet: Use single FastRandomContext when creating a wallet tx #24560

Merged

nina1234 approved these changes Mar 18, 2022

View reviewed changes

murchandamus reviewed Mar 21, 2022

View reviewed changes

DrahtBot added the Needs rebase label Mar 23, 2022

luke-jr suggested changes Apr 26, 2022

View reviewed changes

wallet: add config to prioritize a solution that doesn't create chang…

97190d1

…e in coin selection

brunoerg force-pushed the 2021-11-coinselection-option branch from 5768c9f to 97190d1 Compare April 26, 2022 16:11

DrahtBot removed the Needs rebase label Apr 26, 2022

This was referenced Apr 28, 2022

[Draft / POC] Silent Payments #24897

Closed

wallet: increase BnB upper limit #24752

Closed

DrahtBot mentioned this pull request Jun 4, 2022

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

Merged

ishaanam reviewed Jul 3, 2022

View reviewed changes

DrahtBot mentioned this pull request Jul 18, 2022

rpc: Filter inputs by type during CoinSelection #25183

Closed

DrahtBot mentioned this pull request Aug 9, 2022

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

Merged

DrahtBot mentioned this pull request Sep 20, 2022

wallet, refactor: FundTransaction(): return out-params as util::Result structure #26129

Closed

DrahtBot mentioned this pull request Dec 8, 2022

wallet: Coin Selection, return accurate error messages #26661

Merged

DrahtBot mentioned this pull request Dec 19, 2022

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

Merged

DrahtBot added the Needs rebase label Mar 7, 2023

brunoerg closed this Mar 23, 2023

bitcoin locked and limited conversation to collaborators Mar 22, 2024

		//! Prioritize a solution that doesn't generate change when selecting coins
		bool m_prioritize_no_change = false;

	/* tx_noinputs_size= / 0, / avoid_partial= / false, / prioritize no change */ false);
	/tx_noinputs_size=/0, /avoid_partial=/false, /prioritise_no_change=/false);

	{"prioritize_no_change", UniValueType(UniValue::VBOOL)},
	{"prioritise_no_change", UniValueType(UniValue::VBOOL)},

wallet: add config to prioritize a solution that doesn't create change in coin selection #23475

wallet: add config to prioritize a solution that doesn't create change in coin selection #23475

Uh oh!

Conversation

brunoerg commented Nov 9, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Nov 10, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

lsilva01 left a comment

Choose a reason for hiding this comment

Uh oh!

brunoerg commented Nov 14, 2021

Uh oh!

ghost commented Nov 18, 2021

Uh oh!

achow101 commented Dec 15, 2021

Uh oh!

brunoerg commented Dec 17, 2021

Uh oh!

brunoerg commented Jan 6, 2022

Uh oh!

Rspigler commented Jan 6, 2022

Uh oh!

S3RK commented Jan 10, 2022

Uh oh!

brunoerg commented Mar 11, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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!

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!

brunoerg commented Apr 26, 2022

Uh oh!

brunoerg commented Apr 26, 2022

Uh oh!

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

Uh oh!

Uh oh!

brunoerg commented May 30, 2022

Uh oh!

murchandamus commented May 31, 2022

Uh oh!

ishaanam 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!

DrahtBot commented Mar 7, 2023

Uh oh!

brunoerg commented Mar 23, 2023

Uh oh!

Uh oh!

brunoerg commented Nov 9, 2021 •

edited

Loading

DrahtBot commented Nov 10, 2021 •

edited

Loading

murchandamus commented May 27, 2022 •

edited

Loading