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

brunoerg commented at 11:06 am on November 9, 2021: contributor

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.

fanquake added the label Wallet on Nov 9, 2021

brunoerg force-pushed on Nov 9, 2021

DrahtBot commented at 3:02 am on November 10, 2021: 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:

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

brunoerg marked this as ready for review on Nov 10, 2021

lsilva01 commented at 4:15 pm on November 13, 2021: contributor

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

brunoerg commented at 12:02 pm on November 14, 2021: contributor

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.

brunoerg force-pushed on Nov 18, 2021

ghost commented at 10:54 am on November 18, 2021: none

Concept ACK

DrahtBot added the label Needs rebase on Dec 9, 2021

achow101 commented at 10:03 pm on December 15, 2021: member

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 commented at 10:50 am on December 17, 2021: contributor

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 marked this as a draft on Jan 4, 2022

brunoerg force-pushed on Jan 5, 2022

DrahtBot removed the label Needs rebase on Jan 5, 2022

brunoerg force-pushed on Jan 5, 2022

brunoerg marked this as ready for review on Jan 5, 2022

brunoerg commented at 12:32 pm on January 6, 2022: contributor

force-pushed addressing comments from @achow101

Rspigler commented at 9:56 pm on January 6, 2022: contributor

ACK d6d634094744569d99b35bbb20f295ecdfda32bc

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 commented at 9:02 am on January 10, 2022: contributor

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

Rspigler commented at 4:47 am on January 12, 2022: contributor

So something like the maxapsfee?

How does this conflict with BnB improvements?

S3RK commented at 7:56 am on January 12, 2022: contributor

So something like the maxapsfee?

Not sure what maxapsfee means, but I was thinking about a config parameter that would decrease waste metric for changeless solutions by the specified amount.

How does this conflict with BnB improvements?

There is an idea to drop BnB upper limit. This means there will be always be a BnB solution however terrible it is. Combined with the proposed configuration parameter a user could end up with a changeless tx that drop horrendous amounts to fees.

Rspigler commented at 1:04 am on January 13, 2022: contributor

maxapsfee is a config option that specifies the maximum amount of extra fees a user is willing to pay to avoid partial spends

brunoerg commented at 8:54 pm on January 17, 2022: contributor

Hi, @S3RK. Thanks for the comments, I didn’t review #23367 yet, hope to do it soon.

When you force a solution without change you forego a more economically efficient solution. Yes, this is the purpose of this config, sometimes users don’t want the more economically efficient solution, but that one that may provide a little bit more privacy (e.g. not generating change).

Combined with the proposed configuration parameter a user could end up with a changeless tx that drop horrendous amounts to fees.

Interesting. Interesting. As I said before, I haven’t checked this PR yet. But I think this config option can verify that the BnB solution is not generating horrible amounts of fees. Basically, if we have a ‘decent’ BnB solution, prioritize it.

DrahtBot added the label Needs rebase on Jan 25, 2022

brunoerg force-pushed on Mar 10, 2022

DrahtBot removed the label Needs rebase on Mar 10, 2022

in src/dummywallet.cpp:53 in b6269b012f outdated

49@@ -50,7 +50,7 @@ void DummyWalletInit::AddWalletOptions(ArgsManager& argsman) const
50         "-flushwallet",
51         "-privdb",
52         "-walletrejectlongchains",
53-        "-unsafesqlitesync",
54+        "-unsafesqlitesync"

achow101 commented at 3:00 pm on March 11, 2022:

In b6269b012fe2cad261f94480711c09ebbf47c7fa “wallet: add config to prioritize a solution that doesn’t create change in coin selection”

This change is unrelated.

brunoerg commented at 6:07 pm on March 11, 2022:

Just removed it, thanks!

achow101 requested review from murchandamus on Mar 11, 2022

DrahtBot added the label Needs rebase on Mar 11, 2022

brunoerg force-pushed on Mar 11, 2022

brunoerg commented at 6:07 pm on March 11, 2022: contributor

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

DrahtBot removed the label Needs rebase on Mar 11, 2022

in src/wallet/coincontrol.h:57 in 5768c9fa90 outdated

52@@ -53,6 +53,8 @@ class CCoinControl
53     bool m_avoid_partial_spends = DEFAULT_AVOIDPARTIALSPENDS;
54     //! Forbids inclusion of dirty (previously used) addresses
55     bool m_avoid_address_reuse = false;
56+    //! Prioritize a solution that doesn't generate change when selecting coins
57+    bool m_prioritize_no_change = false;

glozow commented at 11:48 am on March 14, 2022:

Should this be in CoinSelectionParams instead?

brunoerg commented at 10:14 pm on March 14, 2022:

It’s in both I guess

nina1234 approved

murchandamus commented at 11:39 pm on March 21, 2022: contributor

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?

DrahtBot added the label Needs rebase on Mar 23, 2022

in src/bench/coin_selection.cpp:68 in 5768c9fa90 outdated

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

luke-jr commented at 1:57 am on April 26, 2022:

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

in src/wallet/rpc/spend.cpp:420 in 5768c9fa90 outdated

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

luke-jr commented at 1:57 am on April 26, 2022:

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

Correct spelling at least in the API :p

brunoerg commented at 12:20 pm on April 26, 2022:

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

brunoerg commented at 1:00 pm on April 26, 2022:

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

Rspigler commented at 6:26 pm on April 26, 2022:

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

in src/wallet/coinselection.h:115 in 5768c9fa90 outdated

112         m_long_term_feerate(long_term_feerate),
113         m_discard_feerate(discard_feerate),
114         tx_noinputs_size(tx_noinputs_size),
115-        m_avoid_partial_spends(avoid_partial)
116+        m_avoid_partial_spends(avoid_partial),
117+        m_prioritize_no_change(prioritize_no_change)

luke-jr commented at 1:58 am on April 26, 2022:

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

in src/wallet/test/coinselector_tests.cpp:170 in 5768c9fa90 outdated

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

luke-jr commented at 2:00 am on April 26, 2022:

as above

in src/wallet/test/coinselector_tests.cpp:720 in 5768c9fa90 outdated

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

luke-jr commented at 2:00 am on April 26, 2022:

as above

luke-jr changes_requested

brunoerg commented at 12:50 pm on April 26, 2022: contributor

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?

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

brunoerg force-pushed on Apr 26, 2022

brunoerg commented at 4:12 pm on April 26, 2022: contributor

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

DrahtBot removed the label Needs rebase on Apr 26, 2022

murchandamus commented at 9:34 pm on May 27, 2022: contributor

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 #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 commented at 1:55 pm on May 30, 2022: contributor

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 commented at 2:20 pm on May 31, 2022: contributor

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.

in src/wallet/spend.cpp:387 in 97190d172e

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

ishaanam commented at 12:20 pm on July 3, 2022:

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

in src/wallet/rpc/spend.cpp:1252 in 97190d172e

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

ishaanam commented at 12:22 pm on July 3, 2022:

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

brunoerg commented at 4:24 pm on July 5, 2022:

Hmm, interesting! Gonna check it

ishaanam commented at 12:34 pm on July 3, 2022: contributor

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.

DrahtBot added the label Needs rebase on Mar 7, 2023

DrahtBot commented at 1:10 am on March 7, 2023: contributor

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

brunoerg commented at 8:27 pm on March 23, 2023: contributor

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

brunoerg closed this on Mar 23, 2023

bitcoin locked this on Mar 22, 2024

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

Conflicts