Optimize coin selection by dropping BnB upper limit #23367

S3RK · 2021-10-27T07:49:51Z

Requires #22019 and #22949

Removing upper bound allows to find more changeless solutions. Most of them would be terrible due to huge excess and hence waste, so another solution would be chosen. But in some cases excess higher than upper bound would be
economically optimal based on waste metric.

This change also makes transaction building and waste calculation consistent. Specifically it eliminates two sources of discrepancy:

for knapsack we used to always calculate waste as if they produce change (that's not always true)
change could be dropped to fees during tx building after waste is calculated

As a result we should see more changeless solutions which is good for: privacy, utxo set, total fees paid.

S3RK · 2021-10-27T07:52:56Z

Thanks @xekyo for the feedback on the original idea. cc @achow101

DrahtBot · 2021-10-27T14:39:10Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23810 (refactor: destroy all C-style casts; use modern C++ casts, enforce via -Wold-style-cast by PastaPastaPasta)
#23545 (scripted-diff: Use clang-tidy syntax for C++ named arguments by MarcoFalke)
#23534 (wallet: Allow negative effective value inputs when subtracting fee from outputs by achow101)
#23497 (Add src/node/ and src/wallet/ code to node:: and wallet:: namespaces by ryanofsky)
#23475 (wallet: add config to prioritize a solution that doesn't create change in coin selection by brunoerg)
#23202 (wallet: allow psbtbumpfee to work with txs with external inputs by achow101)
#23201 (wallet: Allow users to specify input weights when funding a transaction 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.

murchandamus · 2021-10-28T14:24:14Z

As discussed, @achow101 ran his simulation with this modification. It did find 10% more changeless solutions and an overall decrease in fee expenditure, but there were a few outcomes where the final input set that was used to fund transactions caused change output to be created that just exceeded the dust limit.

Edit: I see that you appear to always drop everything below min_change to fees, so we'd have to see how that changes the overall fee, and whether we might still need a limit for the overshoot of BnB inputs. Or perhaps whether we have to weight the excess differently than other types of costs that are less avoidable.

S3RK · 2021-10-29T07:00:33Z

Edit: I see that you appear to always drop everything below min_change to fees, so we'd have to see how that changes the overall fee, and whether we might still need a limit for the overshoot of BnB inputs.

Just to clarify, dropping to fees behaviour is not changed. I just moved it higher and passed the threshold to coin selection so waste calculation is based on the same tx structure as transaction building. What's new is that in case of BnB we will never created change now.

We already limit max absolute fee by DEFAULT_TRANSACTION_MAXFEE = COIN / 10. Maybe we can just lower the default?

I tend to think that whenever we have a solution with huge excess from BnB, we should get the same solution but with change instead of excess found by other selection algorithms. The problem is that SRD has min change of COIN/100/2, and knapsack is not deterministic AFAIK. Maybe need to try to prove this more formally? Or consider adding another algo in the mix that will deterministically produce a solution with change

achow101 · 2021-12-15T19:02:16Z

ISTM what this is really showing is that our calculation for the upper bound is incorrect. It's a bit overkill to remove the upper bound entirely; rather we should fix the calculation such that it finds the correct upper bound for what we are willing to throw away.

… from output

Removing upper bound allows to find more changeless solutions. Most of them would be terrible due to huge excess and hence waste, so another solution would be chosen. But in some cases excess higher than upper bound would be economically optimal based on waste metric.

achow101

IMO this PR should be broken up into multiple. There are a few commits which could stand alone and it would be nice to have them first. I think that the main "Return change from SelectionResult" commit (and some of the things that lead up to it) should be in its own PR, with this one building on top of that.

I have a few issues with the approach taken for GetChange - there is an inline comment for discussing that.

achow101 · 2021-12-20T20:22:47Z

src/wallet/spend.cpp

+
+    for (const CTxIn& txin : tx.vin) {
+        // if it's not in the wallet and corresponding UTXO is found than select as external output
+        const auto& outPoint = txin.prevout;


In 5f035ef "wallet: do not count wallet utxos as external"

nit: don't use camelCase

achow101 · 2021-12-20T20:30:20Z

src/wallet/test/coinselector_tests.cpp

        BOOST_CHECK(result10);
+        result10->ComputeAndSetWaste(coin_selection_params_bnb);


In ea7056b "test: verify waste for coinselection"

This doesn't compile

Suggested change

result10->ComputeAndSetWaste(coin_selection_params_bnb);

result10->ComputeAndSetWaste(coin_selection_params_bnb.m_cost_of_change);

achow101 · 2021-12-20T20:37:25Z

src/wallet/test/coinselector_tests.cpp

        BOOST_CHECK(result10);
+        result10->ComputeAndSetWaste(coin_selection_params_bnb);
+        BOOST_CHECK(result10->GetWaste() == -68 * 3); // - (long_term_fee * input) * 3coins


In ea7056b "test: verify waste for coinselection"

This fails.

achow101 · 2021-12-20T20:40:08Z

src/wallet/spend.h

 struct TxSize {
    int64_t vsize{-1};
    int64_t weight{-1};
 };

+int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* pwallet, const CCoinControl* coin_control = nullptr);
+int CalculateMaximumSignedInputSize(const CTxOut& txout, const COutPoint outpoint, const SigningProvider* pwallet, const CCoinControl* coin_control = nullptr);


In 803ae6e "wallet: unify max signature logic"

nit: Did these have to move?

achow101 · 2021-12-20T20:46:22Z

src/wallet/coinselection.h

@@ -32,9 +32,10 @@ class CInputCoin {
        effective_value = txout.nValue;
    }

-    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
+    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes, int input_weight) : CInputCoin(tx, i)


In 7d839eb "wallet: CInputCoin store weight"

Since the callers have to be changed to use TxSize anyways, why not just take a TxSize here rather than the two components individually?

achow101 · 2021-12-20T20:49:16Z

src/wallet/coinselection.h

    {
        m_input_bytes = input_bytes;
        m_input_weight = input_weight;
+        m_isSegwit = isSegwit;


In 3b7d2d7 "WIP. Add CInputCoint::m_isSegwit"

nit: snake_case is preferred.

achow101 · 2021-12-20T20:55:35Z

src/wallet/coinselection.cpp

+    // WU required to store input counter
+    // 1 vbyte for the default case already counted in non_input_size
+    int weight = (GetSizeOfCompactSize(m_selected_inputs.size()) - 1)*4;
+    bool hasWitnessInputs = false;


In 6423998 "WIP. Return change from SelectionResult"

nit: snake_case is preferred

achow101 · 2021-12-20T21:05:13Z

src/wallet/spend.cpp

@@ -492,6 +499,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec
         */
        preset_inputs.Insert(coin, 0, false, 0, 0, false);
    }
+    // TODO: value_to_select -= preset_inputs.GetSelectionAmount();


In 6423998 "WIP. Return change from SelectionResult"

This is currently unnecessary because in the loop above, the values of preset inputs are subtracted from value_to_select.

achow101 · 2021-12-20T21:07:38Z

src/wallet/spend.cpp

+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
+    // TODO: disambiguate between min_change and m_cost_of_change
+    if (dust > coin_selection_params.m_cost_of_change) coin_selection_params.m_cost_of_change = dust;


In 6423998 "WIP. Return change from SelectionResult"

Suggested change

const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);

// TODO: disambiguate between min_change and m_cost_of_change

if (dust > coin_selection_params.m_cost_of_change) coin_selection_params.m_cost_of_change = dust;

coin_selection_params.m_cost_of_change = std::max(GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate), coin_selection_params.m_cost_of_change);

achow101 · 2021-12-20T21:15:58Z

src/wallet/coinselection.cpp

+CAmount SelectionResult::GetChange(const CoinSelectionParams& coin_selection_params) const
+{
+    if (m_force_no_change) return 0;
+
+    CAmount change = GetSelectedValue() - m_target;
+    // TODO: rename var maybe?
+    if (!m_use_effective) { // opposite of m_subtract_fee_outputs
+        // m_target already includes not_input_fees
+        // but as they are payed by recipients we can add them back to our change
+        const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
+        change += not_input_fees;
+    } else {
+        const auto size = GetVirtualTransactionSize(GetInputsWeight(), 0, 0);
+        change -= coin_selection_params.m_effective_feerate.GetFee(size);
+    }
+    assert(change >= 0);
+
+    if (change <= coin_selection_params.m_cost_of_change) { // TODO: less or less_or_equal
+        change = 0;
+    }
+
+    return change;
+}


In 6423998 "WIP. Return change from SelectionResult"

I feel like all of the size calculation stuff in this function is unnecessary. We don't need GetChange to be exact down to the satoshi. Rather it just needs to be close enough to the real change (and essentially be whether there is going to be a change output) and its exact value can be adjusted later in CreateTransaction once we know the real size of the transaction. That adjustment doesn't need to account for dust because that should be taken care of here.

It also seems like it is not necessary to calculate the change on the fly like this. Rather the coin selection algorithms should already know what the change is based on their parameters when they selected. While we don't know the fees exactly due to rolling them into the target, we do know how much was selected and what the input fees should be, so we can calculate the change in the SelectCoins* functions and just set it in SelectionResult.

DrahtBot · 2022-01-11T10:36:57Z

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

S3RK · 2022-03-30T07:36:38Z

This approach drops huge amounts to fees in the cases introduced in #24580. In the short-term I'll work on just increasing the boundary for BnB search to improve efficiency of coin selection.

DrahtBot added the Wallet label Oct 27, 2021

S3RK force-pushed the bnb_drop_upper_limit branch from 6546386 to 3f5fdfe Compare October 28, 2021 07:43

DrahtBot mentioned this pull request Oct 29, 2021

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

Merged

This was referenced Nov 10, 2021

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

Closed

Add src/node/ and src/wallet/ code to node:: and wallet:: namespaces #23497

Merged

This was referenced Nov 18, 2021

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

Closed

scripted-diff: Use clang-tidy syntax for C++ named arguments #23545

Closed

DrahtBot mentioned this pull request Nov 30, 2021

Make CFeeRate work with uint64_t sizes #23633

Closed

S3RK force-pushed the bnb_drop_upper_limit branch 2 times, most recently from 56591f6 to 26f86fd Compare December 2, 2021 07:51

This was referenced Dec 2, 2021

MOVEONLY: Move wallet backup and encryption RPCs out of rpcwallet #23647

Closed

Split up rpcwallet #23667

Merged

S3RK force-pushed the bnb_drop_upper_limit branch from ccbd009 to 6a798dc Compare December 8, 2021 08:34

DrahtBot added the Needs rebase label Dec 13, 2021

wallet: do not count wallet utxos as external

5f035ef

S3RK force-pushed the bnb_drop_upper_limit branch from 2d68643 to 71e3635 Compare December 15, 2021 09:18

DrahtBot removed the Needs rebase label Dec 15, 2021

S3RK added 4 commits December 16, 2021 09:01

wallet: don't add change_fee for knapsack target if subsctracting fee…

77df739

… from output

test: verify waste for coinselection

ea7056b

wallet: unify max signature logic

803ae6e

wallet: fix SelectionResult target SRD

2715817

wallet: CInputCoin store weight

7d839eb

S3RK force-pushed the bnb_drop_upper_limit branch from 71e3635 to df9918c Compare December 16, 2021 08:09

S3RK added 4 commits December 16, 2021 10:46

WIP. Add CInputCoint::m_isSegwit

3b7d2d7

wallet: force no change for BnB.

1ea46b7

WIP. Return change from SelectionResult

6423998

S3RK force-pushed the bnb_drop_upper_limit branch from df9918c to 2dc0471 Compare December 16, 2021 09:46

DrahtBot mentioned this pull request Dec 18, 2021

docs: avoid C-style casts; use modern C++ casts #23810

Merged

achow101 reviewed Dec 20, 2021

View reviewed changes

DrahtBot added the Needs rebase label Jan 11, 2022

S3RK mentioned this pull request Mar 24, 2022

test: coinselection edge cases #24580

Closed

S3RK closed this Mar 30, 2022

S3RK mentioned this pull request Apr 4, 2022

wallet: increase BnB upper limit #24752

Closed

S3RK referenced this pull request in S3RK/bitcoin Jul 11, 2022

WIP. Use GetChange in tx building

9fef32c

bitcoin locked and limited conversation to collaborators Jun 12, 2023

		BOOST_CHECK(result10);
		result10->ComputeAndSetWaste(coin_selection_params_bnb);

Optimize coin selection by dropping BnB upper limit #23367

Optimize coin selection by dropping BnB upper limit #23367

Uh oh!

Conversation

S3RK commented Oct 27, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

S3RK commented Oct 27, 2021

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

murchandamus commented Oct 28, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

S3RK commented Oct 29, 2021

Uh oh!

achow101 commented Dec 15, 2021

Uh oh!

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

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

DrahtBot commented Jan 11, 2022

Uh oh!

S3RK commented Mar 30, 2022

Uh oh!

Uh oh!

S3RK commented Oct 27, 2021 •

edited

Loading

DrahtBot commented Oct 27, 2021 •

edited

Loading

murchandamus commented Oct 28, 2021 •

edited

Loading