Optimize coin selection by dropping BnB upper limit

S3RK commented at 7:49 am on October 27, 2021: member

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 commented at 7:52 am on October 27, 2021: member

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

DrahtBot added the label Wallet on Oct 27, 2021

DrahtBot commented at 2:39 pm on October 27, 2021: 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:

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

S3RK force-pushed on Oct 28, 2021

Xekyo commented at 2:24 pm on October 28, 2021: member

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 commented at 7:00 am on October 29, 2021: member

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

S3RK force-pushed on Dec 1, 2021

S3RK force-pushed on Dec 2, 2021

S3RK force-pushed on Dec 8, 2021

DrahtBot added the label Needs rebase on Dec 13, 2021

wallet: do not count wallet utxos as external 5f035efcef

S3RK force-pushed on Dec 15, 2021

DrahtBot removed the label Needs rebase on Dec 15, 2021

achow101 commented at 7:02 pm on December 15, 2021: member

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.

wallet: don't add change_fee for knapsack target if subsctracting fee from output 77df739110

test: verify waste for coinselection ea7056bf51

wallet: unify max signature logic 803ae6e65a

wallet: fix SelectionResult target SRD 27158171fe

wallet: CInputCoin store weight 7d839eb13f

S3RK force-pushed on Dec 16, 2021

WIP. Add CInputCoint::m_isSegwit 3b7d2d7ecd

wallet: force no change for BnB. 1ea46b77cc

WIP. Return change from SelectionResult 6423998409

wallet: remove upper bound for BnB

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.

2dc0471378

S3RK force-pushed on Dec 16, 2021

in src/wallet/spend.cpp:1009 in 5f035efcef outdated

1008+    }
1009+    wallet.chain().findCoins(coins);
1010+
1011+    for (const CTxIn& txin : tx.vin) {
1012+        // if it's not in the wallet and corresponding UTXO is found than select as external output
1013+        const auto& outPoint = txin.prevout;

achow101 commented at 8:22 pm on December 20, 2021:

In 5f035efcef059922afb32bd2f75f32f6cd953984 “wallet: do not count wallet utxos as external”

nit: don’t use camelCase

in src/wallet/test/coinselector_tests.cpp:348 in ea7056bf51 outdated

342@@ -343,8 +343,10 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
343         coin_control.fAllowOtherInputs = true;
344         coin_control.Select(COutPoint(coins.at(0).tx->GetHash(), coins.at(0).i));
345         coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
346-        const auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
347+        auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
348         BOOST_CHECK(result10);
349+        result10->ComputeAndSetWaste(coin_selection_params_bnb);

achow101 commented at 8:30 pm on December 20, 2021:

In ea7056bf511f4b61f693dba4fc7691379ea21f36 “test: verify waste for coinselection”

This doesn’t compile

0        result10->ComputeAndSetWaste(coin_selection_params_bnb.m_cost_of_change);

in src/wallet/test/coinselector_tests.cpp:349 in ea7056bf51 outdated

342@@ -343,8 +343,10 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
343         coin_control.fAllowOtherInputs = true;
344         coin_control.Select(COutPoint(coins.at(0).tx->GetHash(), coins.at(0).i));
345         coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
346-        const auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
347+        auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
348         BOOST_CHECK(result10);
349+        result10->ComputeAndSetWaste(coin_selection_params_bnb);
350+        BOOST_CHECK(result10->GetWaste() == -68 * 3); // - (long_term_fee * input) * 3coins

achow101 commented at 8:37 pm on December 20, 2021:

In ea7056bf511f4b61f693dba4fc7691379ea21f36 “test: verify waste for coinselection”

This fails.

in src/wallet/spend.h:72 in 803ae6e65a outdated

70     int64_t vsize{-1};
71     int64_t weight{-1};
72 };
73 
74+int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* pwallet, const CCoinControl* coin_control = nullptr);
75+int CalculateMaximumSignedInputSize(const CTxOut& txout, const COutPoint outpoint, const SigningProvider* pwallet, const CCoinControl* coin_control = nullptr);

achow101 commented at 8:40 pm on December 20, 2021:

In 803ae6e65a94495b81158147a715f03f117dc700 “wallet: unify max signature logic”

nit: Did these have to move?

in src/wallet/coinselection.h:35 in 7d839eb13f outdated

31@@ -32,9 +32,10 @@ class CInputCoin {
32         effective_value = txout.nValue;
33     }
34 
35-    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
36+    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes, int input_weight) : CInputCoin(tx, i)

achow101 commented at 8:46 pm on December 20, 2021:

In 7d839eb13f579e61b1048b756f84b07aadd05e75 “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?

in src/wallet/coinselection.h:38 in 7d839eb13f outdated

31@@ -32,9 +32,10 @@ class CInputCoin {
32         effective_value = txout.nValue;
33     }
34 
35-    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
36+    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes, int input_weight) : CInputCoin(tx, i)
37     {
38         m_input_bytes = input_bytes;
39+        m_input_weight = input_weight;

achow101 commented at 8:46 pm on December 20, 2021:

In 7d839eb13f579e61b1048b756f84b07aadd05e75 “wallet: CInputCoin store weight”

Perhaps store a TxSize instead of the two components?

in src/wallet/coinselection.h:39 in 3b7d2d7ecd outdated

31@@ -32,10 +32,11 @@ class CInputCoin {
32         effective_value = txout.nValue;
33     }
34 
35-    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes, int input_weight) : CInputCoin(tx, i)
36+    CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes, int input_weight, bool isSegwit) : CInputCoin(tx, i)
37     {
38         m_input_bytes = input_bytes;
39         m_input_weight = input_weight;
40+        m_isSegwit = isSegwit;

achow101 commented at 8:49 pm on December 20, 2021:

In 3b7d2d7ecd78f6c32c731293049a059f1da7cdc6 “WIP. Add CInputCoint::m_isSegwit”

nit: snake_case is preferred.

in src/wallet/coinselection.cpp:457 in 6423998409 outdated

452+CAmount SelectionResult::GetInputsWeight() const
453+{
454+    // WU required to store input counter
455+    // 1 vbyte for the default case already counted in non_input_size
456+    int weight = (GetSizeOfCompactSize(m_selected_inputs.size()) - 1)*4;
457+    bool hasWitnessInputs = false;

achow101 commented at 8:55 pm on December 20, 2021:

In 6423998409736be5728bb5826cfa89e1033ed816 “WIP. Return change from SelectionResult”

nit: snake_case is preferred

in src/wallet/spend.cpp:502 in 6423998409 outdated

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

achow101 commented at 9:05 pm on December 20, 2021:

In 6423998409736be5728bb5826cfa89e1033ed816 “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.

in src/wallet/spend.cpp:764 in 6423998409 outdated

755@@ -744,9 +756,17 @@ static bool CreateTransactionInternal(
756     coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
757     coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee;
758 
759+    // We want to drop the change to fees if:
760+    // 1. The change output would be dust
761+    // 2. The change is within the (almost) exact match window, i.e. it is less than or equal to the cost of the change output (cost_of_change)
762+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
763+    // TODO: disambiguate between min_change and m_cost_of_change
764+    if (dust > coin_selection_params.m_cost_of_change) coin_selection_params.m_cost_of_change = dust;

achow101 commented at 9:07 pm on December 20, 2021:

In 6423998409736be5728bb5826cfa89e1033ed816 “WIP. Return change from SelectionResult”

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

in src/wallet/coinselection.cpp:499 in 6423998409 outdated

494+    if (change <= coin_selection_params.m_cost_of_change) { // TODO: less or less_or_equal
495+        change = 0;
496+    }
497+
498+    return change;
499+}

achow101 commented at 9:15 pm on December 20, 2021:

In 6423998409736be5728bb5826cfa89e1033ed816 “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.

achow101 commented at 9:21 pm on December 20, 2021: member

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.

DrahtBot added the label Needs rebase on Jan 11, 2022

DrahtBot commented at 10:36 am on January 11, 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”.

S3RK commented at 7:36 am on March 30, 2022: member

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.

S3RK closed this on Mar 30, 2022

S3RK referenced this in commit 9fef32c78f on Jul 11, 2022

DrahtBot locked this on Jun 12, 2023

Optimize coin selection by dropping BnB upper limit #23367

Conflicts