wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping #20040

achow101 · 2020-09-29T18:46:52Z

Even after #17458, we still deal with setting fees of an OutputGroup and filtering the OutputGroup outside of the struct. We currently make all of the OutputGroups in SelectCoins and then copy and modify them within each SelectCoinsMinConf scenario. This PR changes this to constructing the OutputGroups within the SelectCoinsMinConf so that the scenario can be taken into account during the group construction. Furthermore, setting of fees and filtering for effective value is moved into OutputGroup::Insert itself so that we don't add undesirable outputs to an OutputGroup rather than deleting them afterwards.

To facilitate fee calculation and effective value filtering during OutputGroup::Insert, OutputGroup now takes the feerates in its constructor and computes the fees and effective value for each output during Insert.

While removing OutputGroups in accordance with the CoinEligibilityFilter still requires creating the OutputGroups first, we can do that within the function that makes them - GroupOutputs.

OutputGroup will handle the fee and effective value computations inside of Insert. It now needs to take the effective feerate and long term feerates as arguments to its constructor.

Instead of filtering after the OutputGroups have been made, do it as they are being made.

DrahtBot · 2020-09-30T00:18:21Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

wallet: Increase OUTPUT_GROUP_MAX_ENTRIES to 100 #18418 (wallet: Increase OUTPUT_GROUP_MAX_ENTRIES to 100 by fjahr)
Add Single Random Draw as an additional coin selection algorithm #17526 (Use Single Random Draw In addition to knapsack as coin selection fallback by achow101)
gui: grey out used address in address book #17355 (gui: grey out used address in address book by za-kk)
Use effective values throughout coin selection #17331 (Use effective values throughout coin selection 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.

instagibbs · 2020-10-02T13:43:54Z

src/wallet/wallet.h

-    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_fee, size_t tx_noinputs_size) : use_bnb(use_bnb), change_output_size(change_output_size), change_spend_size(change_spend_size), effective_fee(effective_fee), tx_noinputs_size(tx_noinputs_size) {}
+    bool m_avoid_partial_spends = false;
+
+    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_fee, size_t tx_noinputs_size, bool avoid_partial) :


musing: this constructor only seems useful for tests

src/wallet/coinselection.cpp

src/wallet/wallet.cpp

Instead of hacking OutputGroup::m_ancestors to discourage the inclusion of partial groups via the eligibility filter, add a parameter to the eligibility filter that indicates whether we want to include the group. Then for those partial groups, don't return them in GroupOutputs if we indicate they aren't desired.

instagibbs · 2020-10-02T21:22:29Z

ACK f6b3052

fanquake · 2020-10-10T02:22:33Z

cc @xekyo

murchandamus · 2020-11-24T22:14:14Z

src/wallet/coinselection.cpp

@@ -302,6 +302,16 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group

 void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
    m_outputs.push_back(output);
+    CInputCoin& coin = m_outputs.back();
+    coin.m_fee = coin.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(coin.m_input_bytes);


I think I have asked this before, but why can m_input_bytes ever be below zero here? Perhaps it would be good to have a comment to explain that.

m_input_bytes is initialized to -1 to indicate that it hasn't been calculated yet.

But this is at the point where we calculate the effective value of UTXOs, so we need to know the size. Why would we want to mitigate a missing size here rather than throwing?

Since the intention is to not change behavior in this PR, I think I will leave this as is for now.

Additionally I don't think it is guaranteed that when we add a CInputCoin to an OutputGroup that we do know the size. It could be for a preset input or an input not in the wallet (there is a PR for that) where we add those coins to an OutputGroup and just don't use the effective value calculation. In those instances, the m_input_bytes may not be set.

A comment would still be a good idea :)

murchandamus · 2020-11-24T22:21:56Z

src/wallet/wallet.cpp

+                // This is for if each output gets it's own OutputGroup
+                OutputGroup coin(effective_feerate, long_term_feerate);
+                coin.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
+                if (coin.EligibleForSpending(filter)) groups.push_back(coin);


Wouldn't this mean that if you got a tiny and a large UTXO associated with the same address that you would potentially form a OutputGroup with just the large coin? Shouldn't the group rather be ineligible as a whole to avoid the partial spend?

This would make the wallet more vulnerable to dust attacks. An attacker could them lock out a user from their funds by sending dust to an already used address.

Yeah, I guess dust should get ignored altogether, but at higher fee rates this could in the worst-case even affect a small amount and a slightly larger amount, which should be prohibited by the partial spending restriction.

murchandamus · 2020-11-24T22:23:56Z

src/wallet/coinselection.cpp

+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
+    // Compute the effective value first
+    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
+    const CAmount ev = output.txout.nValue - coin_fee;


I think that this will result in the OutputGroup accepting uneconomic inputs in the case that the recipient is paying the fees. Should we perhaps rather filter by whether the UTXO are uneconomic, but just calculate with the value instead of the effective value for the case of the recipient paying the fees?

Given that the recipient paying the fees is typically used when sweeping the wallet, I don't think it really matters.

Oh, I didn't realize that it was just used for that. Wouldn't it be much easier to implement that as a "send everything": no coin selection, just sum up everything, deduct fees and pay the recipient address that?

That's the most common use case I think, but not the only one.

It may be worth considering an explicit sweepwallet rpc since I don't think the expectations for "recipient pays fees" and "empty my wallets and send as much as you can" necessarily match. Although, maybe in both cases it would be appropriate not to use uneconomic UTXOs. ;)

murchandamus · 2020-11-30T21:31:05Z

Code Review ACK f6b3052

murchandamus · 2020-11-30T21:34:06Z

Disclaimer:
@achow101 has walked me throw the PR, I have reviewed it at least twice. I think that the concept makes sense, but I'm not familiar with the wallet code globally and my C++ is somewhat rusty.

achow101 · 2020-12-09T00:23:54Z

I've added a commit to rewrite GroupOutputs based on the comments left in downstream PR review (#17331 (comment))

murchandamus

Just reviewed 97256ca

It's much clearer, thank you also for the illustrative comments. Have a few naming suggestions.

src/wallet/wallet.cpp

Rewrite OutputGroups so that the logic is easier to follow and understand. There is a slight behavior change as OutputGroups will be grouped by scriptPubKey rather than CTxDestination as before. This should have no effect on users as all addresses are a CTxDestination. However by using scriptPubKeys, we can correctly group outputs which fall into the NoDestination case. But we also shouldn't have any NoDestination outputs.

murchandamus

Code review ACK: 5d45976

murchandamus · 2020-12-10T03:27:40Z

src/wallet/coinselection.cpp

+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
+    // Compute the effective value first
+    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
+    const CAmount ev = output.txout.nValue - coin_fee;


It may be worth considering an explicit sweepwallet rpc since I don't think the expectations for "recipient pays fees" and "empty my wallets and send as much as you can" necessarily match. Although, maybe in both cases it would be appropriate not to use uneconomic UTXOs. ;)

fjahr

Code review ACK 5d45976

Nice refactoring! I had a bunch of suggestions for small improvements but I don't consider them blocking for a merge.

One more comment: The behavior change in 416d74f could be noted a little more explicitly I think. Before this change, the OutputGroups are filled up and then filtered for positive-only later, sometimes then using groups that are not filled completely in coin selection. Now, since the non-positive coins are never inserted we will have full groups with only positive values. This will lead to different results in certain cases. I think this is an improvement and I don't see any issues arise from it but it wouldn't hurt to mention it in the commit message as it is in 5d45976.

fjahr · 2021-01-01T17:27:10Z

src/wallet/coinselection.h

    void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants);
    std::vector<CInputCoin>::iterator Discard(const CInputCoin& output);
    bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;

-    //! Update the OutputGroup's fee, long_term_fee, and effective_value based on the given feerates


in 99b399a

nit: Maybe add a similar comment to Insert that this updates the fees now if you retouch.

fjahr · 2021-01-01T17:36:00Z

src/wallet/coinselection.cpp

-void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
+    // Compute the effective value first
+    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);


in 416d74f

nit: I think you could skip both intermediary vars (coin_fee, ev) here and instead set the coin members here and use them in the following lines without hurting readability.

fjahr · 2021-01-01T17:44:25Z

src/wallet/wallet.h

@@ -841,7 +841,7 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
    bool IsSpentKey(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
    void SetSpentKeyState(WalletBatch& batch, const uint256& hash, unsigned int n, bool used, std::set<CTxDestination>& tx_destinations) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);

-    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin, const size_t max_ancestors, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter) const;
+    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin, const size_t max_ancestors, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const;


in 416d74f

nit: maybe make positive_only const as well?

fjahr · 2021-01-01T17:57:35Z

src/wallet/wallet.cpp

@@ -2489,8 +2489,8 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
-        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
-        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||


in f6b3052

Now since max_descendants and partial_groups are decoupled it could be discussed if it stays like this or if this coin selection step is split up into one which only tries with the old config (leaving out partial groups) and then one after that adds partial groups. But it can be left for a follow-up if that change is desired.

fjahr · 2021-01-01T18:10:12Z

src/wallet/wallet.cpp

-            CTxDestination dst;
-            CInputCoin input_coin = output.GetInputCoin();
+    if (separate_coins) {
+        // Single coin means no grouping. Each COutput gets its own OutputGroup.


in 5d45976

nit: update comment "Single coin" => "Separate coin"

fjahr · 2021-01-01T21:20:37Z

src/wallet/wallet.cpp

                continue;
            }
-            // If the OutputGroup is not eligible, don't add it
+
+            // Check the OutputGroup's eligibility. Only add the eligible ones.
            if (positive_only && group.effective_value <= 0) continue;


in 5d45976

same as above, I think this is not necessary since Insert takes care of this now.

fjahr · 2021-01-01T21:23:50Z

src/wallet/wallet.cpp

+        size_t ancestors, descendants;
+        chain().getTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
+        CInputCoin input_coin = output.GetInputCoin();
+        CScript spk = input_coin.txout.scriptPubKey;


in 5d45976

nit: spk seems to be only used in the line below so I would drop it.

fjahr · 2021-01-01T21:30:23Z

src/bench/coin_selection.cpp

@@ -42,21 +42,19 @@ static void CoinSelection(benchmark::Bench& bench)
    }
    addCoin(3 * COIN, wallet, wtxs);

-    // Create groups
-    std::vector<OutputGroup> groups;
+    // Create coins


in 6148a8a

nit: This comment isn't that helpful, I would suggest something like "Prepare coins in a format that can be passed to SelectCoinsMinConf()"

fjahr · 2021-01-01T21:33:57Z

src/wallet/wallet.cpp

@@ -2381,6 +2381,8 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
        temp.m_confirm_target = 1008;
        CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);

+        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, eligibility_filter.max_ancestors);


in 6148a8a

This line seems to be the same in both if-else blocks so it could be moved to the beginning of the function before the if

Ah, never mind, it becomes necessary later when the positive_only param is added

fjahr · 2021-01-01T21:38:19Z

src/wallet/coinselection.cpp

@@ -302,6 +302,16 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group

 void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
    m_outputs.push_back(output);
+    CInputCoin& coin = m_outputs.back();
+    coin.m_fee = coin.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(coin.m_input_bytes);


A comment would still be a good idea :)

achow101 · 2021-01-28T19:14:23Z

@fjahr Since this now has two ACKs, I'm going to leave this as-is for now.

meshcollider

Light utACK 5d45976

Nice cleanup thanks Andrew!

… spending eligibility on grouping

achow101 added 4 commits September 29, 2020 14:25

Remove OutputGroup non-default constructors

2acad03

Move GroupOutputs into SelectCoinsMinConf

6148a8a

Move fee setting of OutputGroup to Insert

99b399a

OutputGroup will handle the fee and effective value computations inside of Insert. It now needs to take the effective feerate and long term feerates as arguments to its constructor.

Move EligibleForSpending into GroupOutputs

d895e98

Instead of filtering after the OutputGroups have been made, do it as they are being made.

achow101 changed the title ~~wallet: Refactor OutputGroups to handle fees and spending eligibility on insert~~ wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping Sep 29, 2020

achow101 force-pushed the inner-groupoutputs branch 2 times, most recently from 98cb8a1 to 4b15eae Compare September 29, 2020 20:07

meshcollider added the Wallet label Sep 29, 2020

achow101 mentioned this pull request Sep 29, 2020

Use effective values throughout coin selection #17331

Merged

This was referenced Sep 30, 2020

wallet: Increase OUTPUT_GROUP_MAX_ENTRIES to 100 #18418

Merged

Add Single Random Draw as an additional coin selection algorithm #17526

Merged

gui: grey out used address in address book #17355

Closed

achow101 force-pushed the inner-groupoutputs branch 2 times, most recently from 4d86d14 to d4b8b8d Compare October 2, 2020 00:48

instagibbs reviewed Oct 2, 2020

View reviewed changes

achow101 added 2 commits October 2, 2020 12:35

Move OutputGroup positive only filtering into Insert

416d74f

achow101 force-pushed the inner-groupoutputs branch from d4b8b8d to f6b3052 Compare October 2, 2020 17:45

apoelstra mentioned this pull request Nov 14, 2020

Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs #17211

Merged

murchandamus reviewed Nov 24, 2020

View reviewed changes

achow101 mentioned this pull request Dec 8, 2020

Coin selection algorithm not working as expected resulting in more fees #20598

Closed

murchandamus reviewed Dec 10, 2020

View reviewed changes

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

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

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

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

achow101 force-pushed the inner-groupoutputs branch from 97256ca to 5d45976 Compare December 10, 2020 01:21

murchandamus reviewed Dec 10, 2020

View reviewed changes

fjahr reviewed Jan 1, 2021

View reviewed changes

fanquake requested review from meshcollider and instagibbs January 29, 2021 07:56

meshcollider reviewed Feb 1, 2021

View reviewed changes

meshcollider merged commit 7dc4807 into bitcoin:master Feb 1, 2021

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Feb 2, 2021

Merge bitcoin#20040: wallet: Refactor OutputGroups to handle fees and…

d9c59c9

… spending eligibility on grouping

bitcoin locked as resolved and limited conversation to collaborators Aug 16, 2022

wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping #20040

wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping #20040

Uh oh!

Conversation

achow101 commented Sep 29, 2020

Uh oh!

DrahtBot commented Sep 30, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

instagibbs commented Oct 2, 2020

Uh oh!

fanquake commented Oct 10, 2020

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!

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 commented Nov 30, 2020

Uh oh!

murchandamus commented Nov 30, 2020

Uh oh!

achow101 commented Dec 9, 2020

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

DrahtBot commented Sep 30, 2020 •

edited

Loading

fjahr Jan 1, 2021 •

edited

Loading