wallet: increase BnB upper limit #24752

S3RK · 2022-04-04T07:58:11Z

Successor of #23367

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

DrahtBot · 2022-04-05T00:56:03Z

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.

src/wallet/coinselection.cpp

S3RK · 2022-04-07T16:55:08Z

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

murchandamus

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

murchandamus · 2022-05-09T18:54:41Z

src/wallet/spend.cpp

@@ -760,7 +760,8 @@ static bool CreateTransactionInternal(

    // vouts to the payees
    if (!coin_selection_params.m_subtract_fee_outputs) {
-        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)
+        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)


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.

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.

murchandamus · 2022-05-09T19:14:48Z

src/wallet/spend.cpp

@@ -27,25 +27,25 @@ using interfaces::FoundBlock;
 namespace wallet {
 static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100};

-int GetTxSpendSize(const CWallet& wallet, const CWalletTx& wtx, unsigned int out, bool use_max_sig)
+int GetTxSpendSize(const CWallet& wallet, const CWalletTx& wtx, unsigned int out, const CCoinControl* coin_control)


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

murchandamus · 2022-05-09T19:26:53Z

src/wallet/spend.cpp

-    // barely meets the target. Just use the lower bound change target instead of the randomly
-    // generated one, since SRD will result in a random change amount anyway; avoid making the
-    // target needlessly large.
-    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + CHANGE_LOWER;


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?

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

murchandamus · 2022-05-09T19:34:45Z

src/wallet/spend.cpp

+    if (!coin_selection_params.m_subtract_fee_outputs) {
+        target_with_change += coin_selection_params.m_change_fee;
+    }
+    if (auto knapsack_result{KnapsackSolver(all_groups, target_with_change, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {


Nice catch!

murchandamus · 2022-05-09T19:39:55Z

src/wallet/coinselection.h

+    /** Force no change even if more than enough inputs are selected */
+    bool m_force_no_change{false};


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.

Suggested change

/** Force no change even if more than enough inputs are selected */

bool m_force_no_change{false};

/** Do not allow change even if more than enough inputs are selected */

bool m_allow_change{true};

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

src/wallet/coinselection.h

murchandamus · 2022-05-09T20:11:31Z

src/wallet/spend.cpp

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


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

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.

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.

src/wallet/spend.cpp

murchandamus · 2022-05-09T20:18:11Z

src/wallet/spend.cpp

@@ -572,8 +585,8 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec
    if (!res) return std::nullopt;

    // Add preset inputs to result
-    res->AddInput(preset_inputs);
-    if (res->m_algo == SelectionAlgorithm::MANUAL) {
+    res->Merge(preselected);


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?

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

murchandamus · 2022-05-09T20:23:01Z

src/wallet/spend.cpp

    // 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)}) {
+    if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change + cost_of_extra_input)}) {


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.

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.

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

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.

🤔 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?

DrahtBot · 2022-05-17T12:06:21Z

🐙 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".}

murchandamus · 2022-05-27T20:53:49Z

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 · 2022-06-22T06:50:38Z

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 force-pushed the bnb_increase_upper_limit branch from 9dcc361 to de6ef81 Compare April 4, 2022 07:59

fanquake added the Wallet label Apr 4, 2022

S3RK force-pushed the bnb_increase_upper_limit branch from de6ef81 to f83127e Compare April 4, 2022 08:08

DrahtBot mentioned this pull request Apr 5, 2022

wallet: add tracepoints and algorithm information to coin selection #24644

Merged

S3RK force-pushed the bnb_increase_upper_limit branch from f83127e to 50831c9 Compare April 5, 2022 06:24

DrahtBot mentioned this pull request Apr 6, 2022

wallet, refactor: return out-params of CreateTransaction() as optional struct #20640

Merged

S3RK force-pushed the bnb_increase_upper_limit branch 2 times, most recently from 1561bfe to 3c106cc Compare April 7, 2022 06:58

fanquake reviewed Apr 7, 2022

View reviewed changes

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

This was referenced Apr 8, 2022

wallet: Improve AvailableCoins performance by reducing duplicated operations #24699

Merged

wallet: return error msg for "too-long-mempool-chain" #24845

Merged

S3RK mentioned this pull request Apr 19, 2022

test: coinselection edge cases #24580

Closed

S3RK marked this pull request as ready for review April 19, 2022 07:00

DrahtBot added the Needs rebase label Apr 26, 2022

S3RK added 5 commits April 28, 2022 09:10

wallet: more accurate tx_noinputs_size

27441c7

wallet: unify max signature logic

e4cfbe5

wallet: fix SelectionResult target SRD

9be2437

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

dcb9a0e

wallet: force no change for BnB.

e4c0838

S3RK force-pushed the bnb_increase_upper_limit branch from 3c106cc to 9e9c114 Compare April 28, 2022 07:28

DrahtBot removed the Needs rebase label Apr 28, 2022

This was referenced Apr 28, 2022

wallet: remove extra wtx lookup in 'AvailableCoins' + several code cleanups. #25005

Merged

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

Closed

S3RK force-pushed the bnb_increase_upper_limit branch from 9e9c114 to 070f9aa Compare May 2, 2022 06:08

S3RK added 2 commits May 2, 2022 08:21

WIP. Return change from SelectionResult

5ee8f6c

wallet: increase BnB upper bound

b009a99

S3RK force-pushed the bnb_increase_upper_limit branch from 070f9aa to b009a99 Compare May 2, 2022 06:21

DrahtBot mentioned this pull request May 8, 2022

Set effective_value when initializing a COutput #25083

Merged

murchandamus reviewed May 9, 2022

View reviewed changes

DrahtBot added the Needs rebase label May 17, 2022

S3RK closed this Jun 22, 2022

bitcoin locked and limited conversation to collaborators Jun 22, 2023

		/** Force no change even if more than enough inputs are selected */
		bool m_force_no_change{false};

wallet: increase BnB upper limit #24752

wallet: increase BnB upper limit #24752

Uh oh!

Conversation

S3RK commented Apr 4, 2022

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

Uh oh!

S3RK commented Apr 7, 2022

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!

murchandamus May 9, 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!

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!

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!

murchandamus May 10, 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!

DrahtBot commented May 17, 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!

S3RK commented Jun 22, 2022

Uh oh!

Uh oh!

DrahtBot commented Apr 5, 2022 •

edited

Loading

murchandamus May 9, 2022 •

edited

Loading

murchandamus May 10, 2022 •

edited

Loading

murchandamus commented May 27, 2022 •

edited

Loading