Refactor OutputGroup effective value calculations and filtering to occur within the struct #17458

achow101 · 2019-11-13T00:06:15Z

Currently, the effective values and filtering for positive effective values is done outside of the OutputGroup. We should instead have functions in Outputgroup to do this and call those for each OutputGroup. So this PR does that.

This makes future changes for effective values in coin selection much easier.

DrahtBot · 2019-11-13T02:01:14Z

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

Conflicts

No conflicts as of last run.

instagibbs

Seems right. The remaining other location that sets effective_value is in SelectCoins for preset inputs.

I'd prefer that every setting was done under OutputGroup but that can be done later.

instagibbs · 2019-12-06T19:02:14Z

src/wallet/coinselection.cpp

@@ -299,7 +299,7 @@ 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);
    m_from_me &= from_me;
-    m_value += output.effective_value;


this only isn't a reachable "bug" because before this PR the values are the same, yes?

hmm actually no, this happens for any OutputGroup, which includes Bnb?

it isn't reachable because the values are the same as the outputs' effective values aren't ever actually to their effective values.

ah I see, it's being set externally in SelectCoinsMinConf. Ok, this set of changes makes it much easier to understand.

instagibbs · 2019-12-06T19:10:43Z

src/wallet/coinselection.h

@@ -36,6 +36,8 @@ class CInputCoin {
    COutPoint outpoint;
    CTxOut txout;
    CAmount effective_value;
+    CAmount m_fee;


This commit makes effective_value a bit ambiguous to the reader now that both short and long-range fees are being stored.

It makes everything easier to precompute and store these since they are used in multiple places.

I understand the motivation, my nitting is about naming since we're expanding the "scope" of what is being cached.

instagibbs · 2019-12-06T20:04:04Z

utACK 693cfa6

fjahr

Concept ACK

Good refactoring, code looks good too but please see my comment/question.

fjahr · 2020-03-09T15:02:50Z

src/wallet/coinselection.cpp

@@ -317,6 +318,8 @@ std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output)
    if (it == m_outputs.end()) return it;
    m_value -= output.txout.nValue;
    effective_value -= output.effective_value;
+    fee -= output.m_fee;
+    long_term_fee -= output.m_long_term_fee;


Should the reverse not also be added to the Insert method above?

Yes, but no. The OutputGroups are created (and Insert is called) before the fees are set. But Discard is called after the fees are set. So not incrementing fee and long_term_fee in Insert is safe because they are 0 at that time. I guess it still should for consistency.

Yeah, I think it would be better if it was added. Otherwise, bugs could be introduced if Insert is used differently in the future.

I've added it to insert.

fjahr

I had another pass and it looks good to me and works fine. But I would like to see the change in Insert() and GetPositiveOnlyGroup() can be simplified significantly, I think.

fjahr · 2020-05-23T19:29:37Z

src/wallet/coinselection.cpp

+    }
+}
+
+OutputGroup OutputGroup::GetPositiveOnlyGroup()


To me this method looks overly complicated and doesn't fit so well with the rest of the API. I would suggest simplifying it like this: fjahr@404e7f2

Tests passed for me with this change.

My understanding was that this was not safe and could result in undefined behavior because we are actively iterating through the vector while also modifying at the same time (Discard erases from the vector). So the safe way to do this is to use iterators.

You are right! I think this is still a bit of an improvement but only if you have to retouch fjahr@a438884

fjahr · 2020-05-23T19:35:07Z

src/wallet/coinselection.cpp

@@ -317,6 +318,8 @@ std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output)
    if (it == m_outputs.end()) return it;
    m_value -= output.txout.nValue;
    effective_value -= output.effective_value;
+    fee -= output.m_fee;
+    long_term_fee -= output.m_long_term_fee;


Yeah, I think it would be better if it was added. Otherwise, bugs could be introduced if Insert is used differently in the future.

instagibbs

reACK 6a6d19e

src/wallet/coinselection.h

src/wallet/wallet.cpp

achow101 · 2020-05-26T20:02:11Z

There seems to be a random sigabrt in the BnBExhaustion benchmark.

fjahr · 2020-06-14T12:22:13Z

ACK 6a6d19e

Tests run fine for me locally.

murchandamus · 2020-06-16T04:19:12Z

src/wallet/coinselection.cpp

+    long_term_fee = 0;
+    effective_value = 0;
+    for (CInputCoin& coin : m_outputs) {
+        coin.m_fee = coin.m_input_bytes < 0 ? 0 : effective_feerate.GetFee(coin.m_input_bytes);


How would a UTXO's input size ever be smaller than 0? Shouldn't that be an exception?

m_input_bytes default is -1 to indicate it wasn't calculated.

I see thank you.

murchandamus · 2020-06-16T04:41:54Z

src/wallet/coinselection.h

@@ -93,6 +95,8 @@ struct OutputGroup
    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;
+    void SetFees(const CFeeRate effective_feerate, const CFeeRate long_term_feerate);
+    OutputGroup GetPositiveOnlyGroup();


My understanding from #17526 was that one instance of OutputGroup described a single UTXO with its ancestry, which seems consistent with the struct above.
It seems to me though, that the function GetPositiveOnlyGroup() operates on a set of OutputGroup in the above sense, though. Is that the case?

No, OutputGroup is a group of UTXOs that we want to consider together. It doesn't include ancestry. IIRC this is used for avoid reuse and for some privacy stuff.

I see, thanks. I wasn't thinking about the bundling of all utxos associated with one address.

maflcko · 2020-06-19T15:59:18Z

re-run ci

adamjonas · 2020-06-19T16:50:27Z

I thought it was a CI problem, but I'm able to reproduce the test failures from the last run.

wallet/test/coinselector_tests.cpp:176: error: in "coinselector_tests/bnb_search_test": check SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees) has failed
wallet/test/coinselector_tests.cpp:177: error: in "coinselector_tests/bnb_search_test": check equal_sets(selection, actual_selection) has failed
wallet/test/coinselector_tests.cpp:178: error: in "coinselector_tests/bnb_search_test": check value_ret == 5 * CENT has failed [2000000 != 5000000]
wallet/test/coinselector_tests.cpp:206: error: in "coinselector_tests/bnb_search_test": check equal_sets(selection, actual_selection) has failed
wallet/test/coinselector_tests.cpp:230: error: in "coinselector_tests/bnb_search_test": check SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees) has failed

achow101 · 2020-06-19T23:01:13Z

I'm unable to reproduce the test failures. After rebasing, I also can't get the random sigabrt I was getting.

src/wallet/coinselection.cpp

adamjonas · 2020-06-24T12:33:22Z

Confirming the test failures from 3ed30f4 are passing in 410c8b1.

OutputGroup::m_value is the true value, not the effective value, so use the true values of the outputs, not their effective values.

Instead of having callers set the fees, effective values, and filtering of outputs, do these within OutputGroups themselves as member functions. m_fee and m_long_term_fee is added to OutputGroup to track the fees of the OutputGroup.

instagibbs · 2020-08-13T01:57:13Z

reACK 9adc2f8

fanquake · 2020-08-13T02:05:20Z

@xekyo did you want to take another look here?

fjahr · 2020-08-13T14:35:58Z

re-ACK 9adc2f8

per git range-diff 4af01b37d40246cd1fdb54719855927e36a36b46..6a6d19e0e5d91673a0d361ffa732b6dc43890034 edec7f7c254294cd5c46ae5cf304353d458bb852..9adc2f80fc14f11ee2b1f989ee7be71b58481e6f

meshcollider

Light code review ACK 9adc2f8

I'll wait a bit longer for @xekyo but otherwise I'll merge this tomorrow

murchandamus · 2020-08-14T07:30:29Z

src/wallet/coinselection.cpp

+        fee += coin.m_fee;
+
+        coin.m_long_term_fee = coin.m_input_bytes < 0 ? 0 : long_term_feerate.GetFee(coin.m_input_bytes);
+        long_term_fee += coin.m_long_term_fee;


Actually, why is the long_term_fee tracked additionally to just the fee here? Is that just for calculating the waste metric?

If I understand that right, at this point the output group is already being cast into the context of the current transaction (i.e. the fee is specific to the transaction we are building). Since the waste metric is only dependent on the current fee rate and the long term fee rate (if that's still the same from when we discussed two years ago), perhaps it would be better to calculate the waste here instead of carrying around the long term fee to calculate the waste later. Might be better to do that in separate PR later, though, even if you agree. ;)

Indeed, I think it would be better to track the waste. I will do that in a followup as it is a slightly larger change which touches the actual coin selection algorithms.

…s and filtering to occur within the struct 9adc2f8 Refactor OutputGroups to handle effective values, fees, and filtering (Andrew Chow) 7d07e86 Use real value when calculating OutputGroup value (Andrew Chow) Pull request description: Currently, the effective values and filtering for positive effective values is done outside of the OutputGroup. We should instead have functions in Outputgroup to do this and call those for each OutputGroup. So this PR does that. This makes future changes for effective values in coin selection much easier. ACKs for top commit: instagibbs: reACK 9adc2f8 fjahr: re-ACK 9adc2f8 meshcollider: Light code review ACK 9adc2f8 Tree-SHA512: 7445c94b7295b45bcd83a6f8a5c8f6961a89453fcc856335192d4b4a66aec7724513616b04e5111588ab208c89b311055399d6279cd9c4ce452aefb85f04b64a

…ng eligibility on grouping 5d45976 Rewrite OutputGroups to be clearer and to use scriptPubKeys (Andrew Chow) f6b3052 Explicitly filter out partial groups when we don't want them (Andrew Chow) 416d74f Move OutputGroup positive only filtering into Insert (Andrew Chow) d895e98 Move EligibleForSpending into GroupOutputs (Andrew Chow) 99b399a Move fee setting of OutputGroup to Insert (Andrew Chow) 6148a8a Move GroupOutputs into SelectCoinsMinConf (Andrew Chow) 2acad03 Remove OutputGroup non-default constructors (Andrew Chow) Pull request description: 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 `OutputGroup`s in `SelectCoins` and then copy and modify them within each `SelectCoinsMinConf` scenario. This PR changes this to constructing the `OutputGroup`s 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 `OutputGroup`s in accordance with the `CoinEligibilityFilter` still requires creating the `OutputGroup`s first, we can do that within the function that makes them - `GroupOutput`s. ACKs for top commit: Xekyo: Code review ACK: 5d45976 fjahr: Code review ACK 5d45976 meshcollider: Light utACK 5d45976 Tree-SHA512: 35965b6d49a87f4ebb366ec4f00aafaaf78e9282481ae2c9682b515a3a9f2cbcd3cd6e202fee29489d48fe7f3a7cede4270796f5e72bbaff76da647138fb3059

Summary: OutputGroup::m_value is the true value, not the effective value, so use the true values of the outputs, not their effective values. This is a backport of [[bitcoin/bitcoin#17458 | core#17458]] [1/2] bitcoin/bitcoin@9adc2f8 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D10088

Summary: Instead of having callers set the fees, effective values, and filtering of outputs, do these within OutputGroups themselves as member functions. m_fee and m_long_term_fee is added to OutputGroup to track the fees of the OutputGroup. This is a backport of [[bitcoin/bitcoin#17458 | core#17458]] [2/2] bitcoin/bitcoin@9adc2f8 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Subscribers: Detetivepro1 Differential Revision: https://reviews.bitcoinabc.org/D10089

fanquake added the Wallet label Nov 13, 2019

achow101 mentioned this pull request Nov 13, 2019

Use effective values throughout coin selection #17331

Merged

DrahtBot added the Needs rebase label Nov 22, 2019

achow101 force-pushed the cleanup-outputgroups branch from 625e494 to 693cfa6 Compare November 22, 2019 21:24

DrahtBot removed the Needs rebase label Nov 22, 2019

instagibbs reviewed Dec 6, 2019

View reviewed changes

DrahtBot mentioned this pull request Feb 11, 2020

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

Merged

fjahr reviewed Mar 9, 2020

View reviewed changes

fjahr suggested changes May 23, 2020

View reviewed changes

achow101 force-pushed the cleanup-outputgroups branch from 693cfa6 to 6a6d19e Compare May 26, 2020 18:29

instagibbs approved these changes May 26, 2020

View reviewed changes

src/wallet/coinselection.h Show resolved Hide resolved

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

murchandamus reviewed Jun 16, 2020

View reviewed changes

maflcko closed this Jun 19, 2020

maflcko reopened this Jun 19, 2020

achow101 force-pushed the cleanup-outputgroups branch from 6a6d19e to 3ed30f4 Compare June 19, 2020 23:00

maflcko reviewed Jun 20, 2020

View reviewed changes

src/wallet/coinselection.cpp Show resolved Hide resolved

achow101 force-pushed the cleanup-outputgroups branch from 3ed30f4 to 410c8b1 Compare June 22, 2020 20:24

Use real value when calculating OutputGroup value

7d07e86

OutputGroup::m_value is the true value, not the effective value, so use the true values of the outputs, not their effective values.

achow101 force-pushed the cleanup-outputgroups branch from 410c8b1 to 97f6acd Compare July 30, 2020 17:05

achow101 force-pushed the cleanup-outputgroups branch from 97f6acd to 9adc2f8 Compare August 11, 2020 18:26

meshcollider reviewed Aug 13, 2020

View reviewed changes

murchandamus reviewed Aug 14, 2020

View reviewed changes

meshcollider merged commit f269165 into bitcoin:master Aug 14, 2020

achow101 mentioned this pull request Sep 29, 2020

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

Merged

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

Refactor OutputGroup effective value calculations and filtering to occur within the struct #17458

Refactor OutputGroup effective value calculations and filtering to occur within the struct #17458

Uh oh!

Conversation

achow101 commented Nov 13, 2019

Uh oh!

DrahtBot commented Nov 13, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

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

instagibbs commented Dec 6, 2019

Uh oh!

fjahr left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 Mar 9, 2020 • 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!

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!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

achow101 commented May 26, 2020

Uh oh!

fjahr commented Jun 14, 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!

maflcko commented Jun 19, 2020

Uh oh!

adamjonas commented Jun 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Jun 19, 2020

DrahtBot commented Nov 13, 2019 •

edited

Loading

achow101 Mar 9, 2020 •

edited

Loading

adamjonas commented Jun 19, 2020 •

edited

Loading

meshcollider left a comment •

edited

Loading

murchandamus Aug 14, 2020 •

edited

Loading