wallet: increase BnB upper limit

S3RK commented at 7:58 am on April 4, 2022: member

Successor of #23367

Increasing upper bound helps to find more changeless solutions. This improves coin selection in the cases introduced in #24580.

S3RK force-pushed on Apr 4, 2022

fanquake added the label Wallet on Apr 4, 2022

S3RK force-pushed on Apr 4, 2022

DrahtBot commented at 0:56 am on April 5, 2022: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#25005 (wallet: remove extra wtx lookup in ‘AvailableCoins’ + several code cleanups. by furszy)
#24845 (wallet: createTransaction, return proper error description for “too-long-mempool-chain” + introduce generic Result classes by furszy)
#24699 (wallet: Improve AvailableCoins performance by reducing duplicated operations by achow101)
#23475 (wallet: add config to prioritize a solution that doesn’t create change in coin selection by brunoerg)
#20640 (wallet, refactor: return out-params of CreateTransaction() as optional struct by theStack)

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 Apr 5, 2022

S3RK force-pushed on Apr 7, 2022

in src/wallet/coinselection.cpp:67 in 3c106cc578 outdated

61@@ -62,9 +62,9 @@ struct {
62 
63 static const size_t TOTAL_TRIES = 100000;
64 
65-std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
66+std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& upper_bound)
67 {
68-    SelectionResult result(selection_target);
69+    SelectionResult result(selection_target, /* force_no_change=*/ true);

fanquake commented at 10:26 am on April 7, 2022:

0    SelectionResult result(selection_target, /*force_no_change=*/true);

Anywhere you are adding/touching named args, please use the style from the developer docs.

S3RK commented at 4:51 pm on April 7, 2022:

Sure, will fix that

S3RK commented at 7:29 am on April 28, 2022:

fixed

S3RK commented at 4:55 pm on April 7, 2022: member

@achow101 take a look. I reworked my BnB optimization and all the tests pass now. I think the next step would be to do simulations and see how this affects coin selection at large (but locally it fixes some of the edge cases found in #24580)

S3RK marked this as ready for review on Apr 19, 2022

DrahtBot added the label Needs rebase on Apr 26, 2022

wallet: more accurate tx_noinputs_size 27441c7253

wallet: unify max signature logic e4cfbe5e7b

wallet: fix SelectionResult target SRD 9be243779e

wallet: don't add change_fee to target if subsctracting fee from output dcb9a0e53a

wallet: force no change for BnB. e4c0838479

S3RK force-pushed on Apr 28, 2022

DrahtBot removed the label Needs rebase on Apr 28, 2022

S3RK force-pushed on May 2, 2022

WIP. Return change from SelectionResult 5ee8f6c23e

wallet: increase BnB upper bound b009a99839

S3RK force-pushed on May 2, 2022

in src/wallet/spend.cpp:763 in 27441c7253 outdated

759@@ -760,7 +760,8 @@ static bool CreateTransactionInternal(
760 
761     // vouts to the payees
762     if (!coin_selection_params.m_subtract_fee_outputs) {
763-        coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size)
764+        coin_selection_params.tx_noinputs_size = 10; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 witness overhead (dummy, flag, stack size)

Xekyo commented at 6:54 pm on May 9, 2022:

Note for reviewers/myself: It should be 10 vB for non-segwit transactions, and 42 WU for segwit transactions (as the witness adds the two fields marker and flag that don’t scale with the count of inputs. So, this is correct for non-segwit transactions, but would be short for a segwit transaction.

S3RK commented at 6:25 am on May 10, 2022:

For clarity. The size required to store output counter added below. So in case of <253 outputs tx_noinputs_size will be 11vB for both segwit and non-segwit txs. This overshoots the target a bit for non-segwit, but this is much better than selecting not enough coins.

in src/wallet/spend.cpp:30 in e4cfbe5e7b outdated

26@@ -27,25 +27,25 @@ using interfaces::FoundBlock;
27 namespace wallet {
28 static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100};
29 
30-int GetTxSpendSize(const CWallet& wallet, const CWalletTx& wtx, unsigned int out, bool use_max_sig)
31+int GetTxSpendSize(const CWallet& wallet, const CWalletTx& wtx, unsigned int out, const CCoinControl* coin_control)

Xekyo commented at 7:14 pm on May 9, 2022:

Note to other reviewers: it wasn’t obvious to me at first why this replacement is possible, but I found that use_max_sig is directly calculated from CCoinControl values. Perhaps this could be mentioned in the commit message.

./src/wallet/wallet.cpp: const bool use_max_sig = coin_control && (coin_control->fAllowWatchOnly || coin_control->IsExternalSelected(txin.prevout));

S3RK commented at 7:03 am on May 10, 2022:

Will do

in src/wallet/spend.cpp:405 in 9be243779e outdated

397@@ -398,11 +398,8 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm
398         results.push_back(*knapsack_result);
399     }
400 
401-    // Include change for SRD as we want to avoid making really small change if the selection just
402-    // barely meets the target. Just use the lower bound change target instead of the randomly
403-    // generated one, since SRD will result in a random change amount anyway; avoid making the
404-    // target needlessly large.
405-    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + CHANGE_LOWER;

Xekyo commented at 7:26 pm on May 9, 2022:

I see how this is just a refactor, and doesn’t change the result, but it’s not clear to me why it’s being done. Could you add a sentence of motivation to the commit message?

S3RK commented at 7:03 am on May 10, 2022:

Will do. The reason is to have the correct value (without CHANGE_LOWER) for SelectionResult.m_target

in src/wallet/spend.cpp:399 in dcb9a0e53a outdated

397-                                            coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
398+    // So we need to include that for KnapsackSolver and SRD as well, as we are expecting to create a change output.
399+    if (!coin_selection_params.m_subtract_fee_outputs) {
400+        target_with_change += coin_selection_params.m_change_fee;
401+    }
402+    if (auto knapsack_result{KnapsackSolver(all_groups, target_with_change, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {

Xekyo commented at 7:34 pm on May 9, 2022:

Nice catch!

in src/wallet/coinselection.h:262 in e4c0838479 outdated

257@@ -258,15 +258,17 @@ struct SelectionResult
258     bool m_use_effective{false};
259     /** The computed waste */
260     std::optional<CAmount> m_waste;
261+    /** Force no change even if more than enough inputs are selected */
262+    bool m_force_no_change{false};

Xekyo commented at 7:39 pm on May 9, 2022:

force_no_change = false feels like a potential brain twister. Perhaps it would be better to call this allow_change and invert the boolean values.

0    /** Do not allow change even if more than enough inputs are selected */
1    bool m_allow_change{true};

S3RK commented at 7:05 am on May 10, 2022:

meh.. I’m ambivalent about this. What do others think?

in src/wallet/coinselection.cpp:67 in e4c0838479 outdated

63@@ -64,7 +64,7 @@ static const size_t TOTAL_TRIES = 100000;
64 
65 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
66 {
67-    SelectionResult result(selection_target, SelectionAlgorithm::BNB);
68+    SelectionResult result(selection_target, SelectionAlgorithm::BNB, /*force_no_change=*/true);

Xekyo commented at 7:41 pm on May 9, 2022:

See below

0    SelectionResult result(selection_target, SelectionAlgorithm::BNB, /*allow_change=*/false);

in src/wallet/coinselection.h:271 in e4c0838479 outdated

268     const SelectionAlgorithm m_algo;
269 
270-    explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
271-        : m_target(target), m_algo(algo) {}
272+    explicit SelectionResult(const CAmount target, SelectionAlgorithm algo, const bool force_no_change = false)
273+        : m_target(target), m_algo(algo), m_force_no_change(force_no_change) {}

Xekyo commented at 7:43 pm on May 9, 2022:

see above

0    explicit SelectionResult(const CAmount target, SelectionAlgorithm algo, const bool allow_change = true)
1        : m_target(target), m_algo(algo), m_allow_change(allow_change) {}

in src/wallet/coinselection.cpp:453 in 5ee8f6c23e outdated

449@@ -439,7 +450,18 @@ void SelectionResult::Clear()
450 void SelectionResult::AddInput(const OutputGroup& group)
451 {
452     util::insert(m_selected_inputs, group.m_outputs);
453-    m_use_effective = !group.m_subtract_fee_outputs;
454+    m_use_effective = m_use_effective || !group.m_subtract_fee_outputs;

Xekyo commented at 7:49 pm on May 9, 2022:

I don’t understand what’s going on here. I’m actually now wondering why we need m_use_effective in the first place if it’s just the negation of m_subtract_fee_outputs on the group.

in src/wallet/coinselection.cpp:465 in 5ee8f6c23e outdated

461+    m_force_no_change |= other.m_force_no_change;
462+    if (m_algo == SelectionAlgorithm::MANUAL) {
463+        m_algo = other.m_algo;
464+    }
465+    util::insert(m_selected_inputs, other.m_selected_inputs);
466 }

Xekyo commented at 7:54 pm on May 9, 2022:

This feels like it should be mentioned in the commit message and should perhaps be a separate commit than “Return change from SelectionResult”. I see that this might be useful to construct input sets with a specific UTXO included, but I have a hard time following how it fits into the bigger picture.

S3RK commented at 7:07 am on May 10, 2022:

I’ll work on splitting this into a separate commit

in src/wallet/coinselection.cpp:520 in 5ee8f6c23e outdated

515+    if (change <= min_change) { // TODO: less or less_or_equal
516+        change = 0;
517+    }
518+
519+    return change;
520+}

Xekyo commented at 7:59 pm on May 9, 2022:

Nice! :heart: I was also thinking about us returning the change value in the SelectionResult in the context of automatic CPFP for unconfirmed inputs when the parent transaction has a lower feerate and we need to add fees for that. This is great!

in src/wallet/coinselection.h:258 in 5ee8f6c23e outdated

253@@ -254,6 +254,10 @@ struct SelectionResult
254 private:
255     /** Set of inputs selected by the algorithm to use in the transaction */
256     std::set<COutput> m_selected_inputs;
257+    /** The target the algorithm selected for. Note that this may not be equal to the recipient amount as it can include non-input fees */
258+    CAmount m_target;

Xekyo commented at 8:05 pm on May 9, 2022:

I wish we had canonical terms to consistently disambiguate the selection target and the recipient output total, especially because it additionally sometimes includes cost of change and a minimum change.

What do you all think about something along the lines of:

recipients_total: sum of recipient output values (excluding change)
selection_target: the value the coin selection needs to raise to pay for the payload including change for algorithms that allow change

Do we need another term for selection_target without change?

S3RK commented at 7:08 am on May 10, 2022:

+1 to the terms. I don’t think we need another one for selection_target without change. Currently we know in most cases whether we need change or not. BnB - always no change, Knapsack and SRD always change, unless sffo.

Xekyo commented at 1:40 pm on May 10, 2022:

Good, although Knapsack can actually produce results without change, but it takes care of the change amount internally.

in src/wallet/coinselection.h:260 in 5ee8f6c23e outdated

253@@ -254,6 +254,10 @@ struct SelectionResult
254 private:
255     /** Set of inputs selected by the algorithm to use in the transaction */
256     std::set<COutput> m_selected_inputs;
257+    /** The target the algorithm selected for. Note that this may not be equal to the recipient amount as it can include non-input fees */
258+    CAmount m_target;
259+    /** The algorithm used to produce this result */
260+    SelectionAlgorithm m_algo;

Xekyo commented at 8:08 pm on May 9, 2022:

I think we got something like this via #24644 now.

S3RK commented at 6:29 am on May 10, 2022:

Yes, I just made it non const to allow merging two SelectionResults

in src/wallet/spend.cpp:437 in 5ee8f6c23e outdated

433@@ -434,9 +434,17 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec
434              */
435             preset_inputs.Insert(out, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false);
436         }
437+        if (preset_inputs.GetSelectionAmount() < nTargetValue) return std::nullopt;

Xekyo commented at 8:11 pm on May 9, 2022:

Wasn’t this what we introduced SelectionResult.Merge(…) above for?

S3RK commented at 7:10 am on May 10, 2022:

Not sure what did you mean by this. This is the case when the selected inputs are not enough and we just return null value. There’s no merging going on.

Xekyo commented at 1:41 pm on May 10, 2022:

Right, but if the preset inputs are less than the target, wouldn’t we be supposed to select additional inputs and build a transaction? I thought that’s what you introduced the merge for.

in src/wallet/spend.cpp:439 in 5ee8f6c23e outdated

433@@ -434,9 +434,17 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec
434              */
435             preset_inputs.Insert(out, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false);
436         }
437+        if (preset_inputs.GetSelectionAmount() < nTargetValue) return std::nullopt;
438+
439+        if (preset_inputs.GetSelectionAmount() > nTargetValue + coin_selection_params.m_cost_of_change) {

Xekyo commented at 8:13 pm on May 9, 2022:

Would this perhaps still need to check whether the remainder is greater than the dust threshold?

S3RK commented at 7:01 am on May 10, 2022:

I don’t think so, because m_cost_of_change is higher than dust

Xekyo commented at 1:43 pm on May 10, 2022:

Ah right, because it includes the cost of future spending.

in src/wallet/spend.cpp:588 in 5ee8f6c23e outdated

584@@ -572,8 +585,8 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec
585     if (!res) return std::nullopt;
586 
587     // Add preset inputs to result
588-    res->AddInput(preset_inputs);
589-    if (res->m_algo == SelectionAlgorithm::MANUAL) {
590+    res->Merge(preselected);

Xekyo commented at 8:18 pm on May 9, 2022:

I have the impression that this commit makes changes to how coin selection works with preselected inputs and in addition introduces that SelectionResult returns change. While both changes look worthwhile to me, it would be easier to follow if they were separate commits if not separate PRs. Am I missing some special reason why doing all of this at once is advantageous?

S3RK commented at 7:13 am on May 10, 2022:

I intended this to not change the behavior. The reason why we need Merge is to correctly track SelectionResult::m_target. Right now in case with preselected inputs m_target will be reduced by the amount of preselected inputs and this leads to incorrect result in SelectionResult::GetChange

I’ll split the commits and try to explain better why this is needed

in src/wallet/spend.cpp:388 in b009a99839

381@@ -382,9 +382,10 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm
382     // Vector of results. We will choose the best one based on waste.
383     std::vector<SelectionResult> results;
384 
385+    const auto cost_of_extra_input = coin_selection_params.m_effective_feerate.GetFee(DUMMY_NESTED_P2WPKH_INPUT_SIZE);
386     // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
387     std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, true /* positive_only */);
388-    if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
389+    if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change + cost_of_extra_input)}) {

Xekyo commented at 8:23 pm on May 9, 2022:

That’s an interesting upper bound. Much better than just completely unbounded, but definitely gives some room for bigger excess amounts than before. Is this still a WIP-value to give you more wiggle room or is this what you finally identified as the appropriate upper bound? Curious about your thought process here.

S3RK commented at 6:56 am on May 10, 2022:

To fix inefficiencies identified #24580 we need to increase upper limit by the opportunity cost of spending one extra input. We don’t know what type that one extra input would be.

The range of possible values is from the cost of p2tr (57.5vb) to the cost of p2pkh (148vb). The chosen value is in the middle of that range.

If you have only p2pkh inputs in your wallet: the new upper bound is lower than optimal, but still better than current bound as it extends the set of possible BnB solutions.
If you have only p2tr inputs: the new bound is higher than optimal, but also better than current bound. Same reasoning applies here as for the BnB without upper limit. We produce more BnB solutions and later choose what solution is economically more efficient. But unlike BnB without upper limit we don’t risk dropping ridiculous amounts to fees.

An alternative way to pick the value would be to examine available UTXOs and take an average input size or something like this. This is more complicated and I’m not sure if it makes a meaningful difference.

S3RK commented at 7:17 am on May 10, 2022:

I should probably add a comment to the code once we agree on the value

Xekyo commented at 1:49 pm on May 10, 2022:

Perhaps it should just use the default output type, that way it will automatically upgrade as wallets progress to P2TR eventually. The current default seems like a reasonable choice at this time.

:thinking: Having the bound definitely feels a lot better than unbounded. A whole input’s fee still feels like a lot of additional fees. It’s obviously only the worst case, but I’m curious to see how that fares in simulations. Do you need to make more logic changes or do you think I could take it for a spin on a few different scenarios?

Xekyo commented at 8:24 pm on May 9, 2022: member

Very exciting changes in this PR. It feels like there are still some moving parts, see my comments on the various sections.

DrahtBot commented at 12:06 pm on May 17, 2022: member

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

Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a “draft”.

DrahtBot added the label Needs rebase on May 17, 2022

Xekyo commented at 8:53 pm on May 27, 2022: member

Update: I did some simulations for this branch. The results were that

the cost increased when the BnB window was relaxed
the number of changeless solutions was reduced

FWIU, @S3RK had a similar result with his simulations so far. There was a bug discovered in how the waste is calculated for Knapsack in some instances, but I don’t expect this bug to impact the overall trend.

More experiments to follow, and it may be interesting to explore the opposite, i.e. see whether reducing the window size in which BnB produces solutions improves results instead.

S3RK commented at 6:50 am on June 22, 2022: member

The results were that

the cost increased when the BnB window was relaxed

the number of changeless solutions was reduced

I don’t think this is the correct interpretation of the data. e.g. for bustabit-tiny-hot-wallet_2019-2020-per-day

total cost remained the same.
- average balance: baseline - 14.6401 vs branch - 14.6396
- average total fees: baseline - 0.4950 vs branch - 0.4954
- average total cost: baseline - 0.4958 vs branch - 0.4963
the number of changeless solutions very slightly increased (~ +3% but we see more knapsack solutions and it’s not clear if the difference is significant or due to randomness)
- average for baseline - 1668.2 vs branch - 1721.6

I see similar picture for bustabit-tiny-hot-wallet_peak-and-tail and for my own simulations.

Overall it’s not clear whether increasing the upper limit is beneficial. I’m closing this now and will send refactoring PRs separately.

S3RK closed this on Jun 22, 2022

DrahtBot locked this on Jun 22, 2023

wallet: increase BnB upper limit #24752

Conflicts