Use effective values throughout coin selection #17331

achow101 · 2019-10-31T18:59:06Z

Changes KnapsackSolver to use effective values instead of just the nominal txout value. Since fees are taken into account during the selection itself, we finally get rid of the CreateTransaction loop as well as a few other things that only were only necessary because of that loop.

This should not change coin selection behavior at all (except maybe remove weird edge cases that were caused by the loop). In order to keep behavior the same, KnapsackSolver will select outputs with a negative effective value (as it did before).

DrahtBot · 2019-10-31T19:22:26Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

Replace size/weight estimate tuple with struct for named fields #22042 (Replace size/weight estimate tuple with struct for named fields by instagibbs)
MOVEONLY: CWallet transaction code out of wallet.cpp/.h #21207 (MOVEONLY: CWallet transaction code out of wallet.cpp/.h by ryanofsky)
refactor: Make CWalletTx sync state type-safe #21206 (refactor: Make CWalletTx sync state type-safe by ryanofsky)
wallet, refactor: return out-params of CreateTransaction() as optional struct #20640 (wallet, refactor: return out-params of CreateTransaction() as optional struct by theStack)
gui: grey out used address in address book #17355 (gui: grey out used address in address book by za-kk)
Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs #17211 (Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs 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 · 2019-11-01T16:17:24Z

concept ACK, unifying to effective value should make 95% of my consternation with Core coin selection go away by making further improvements easier.

So with this change another idea is to have an opt-in Single Random Draw(SRD) which should be pretty drop-in after this which would allow more experimentation with less systemic risk.

laanwj · 2019-11-02T10:27:57Z

Concept ACK, thanks for making this code more understandable.

achow101 · 2019-11-13T00:10:01Z

I think there's a bug in here somewhere. I ran some simulations and it looks like there is a significant difference in some things (e.g. minimum change value) but it should be the same as master. I'm investigating that.

Edit: I think I fixed it. Requires #17458 now.

fjahr

Concept ACK

Will do another pass on the code once #17458 is merged.

src/wallet/coinselection.h

src/wallet/wallet.cpp

These booleans are no longer needed

Remove the CreateTransaction while loop. Removes variables that were only needed because of that loop. Also renames a few variables and moves their declarations to where they are used. Some subtractFeeFromOutputs handling is moved to after coin selection in order to reduce their amounts once the fee is known. If subtracting the fee reduces the change to dust, we will also now remove the change output

This was originally modified to use SelectCoinsMinConf in order to test both BnB and Knapsack at the same time. But since SelectCoins does both now, this is no longer necessary and we can revert back to actually testing SelectCoins.

Instead of hijacking the effective_feerate to use the correct value during coin selection, have OutputGroup be aware of whether we are subtracting the fee from the outputs and provide the correct value to use for selection. To do this, OutputGroup now takes CoinSelectionParams and has a new function GetSelectionAmount().

ryanofsky

I went through the new changes and everything looks good except for some questions and possible bugs in two commits changing the createtransaction loop:

2b445b7 Move output reductions for fee to after coin selection (4/11)
67fc8b7 Roll static tx fees into nValueToSelect instead of having it be separate (5/11)

Specific comments are above but in both commits, questions are mostly related to nFeeRet setting a few places

ryanofsky · 2021-05-19T19:01:09Z

src/wallet/wallet.cpp

+                CAmount nValueToSelect = nValue + not_input_fees;
+
+                // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the
+                // inputs that we found in the previous iteration.
+                if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) {
+                    nValueToSelect += std::max(CAmount(0), nFeeRet - not_input_fees);
+                }
+


In commit "Roll static tx fees into nValueToSelect instead of having it be separate" (67fc8b7)

This logic is not making sense to me. It wasn't this complicated before, and even though commits are reordered and nTargetValue is passed differently now I would expect these lines 2957-2964 to look like:

CAmount nValueToSelect = nValue; if (coin_selection_params.use_bnb) nValueToSelect += not_input_fees; if (nSubtractFeeFromAmount != 0) nValueToSelect += nFeeRet;

This would:

Avoid adding not_input_fees and then subtracting it

Avoid introducing unexplained std::max not_input_fees > nFeeRet corner case

Avoid changing behavior in the bnb && nSubtractFeeFromAmount case.

If it is actually desirable to change bnb behavior I think it should happen in a different commit. This commit is already doing multiple things and I think would be good to split, see Use effective values throughout coin selection #17331 (comment)

Let you drop or shorten the "Note that setting nValueToSelect is changed..." paragraph in commit description since it should be obvious this only changes bnb

I had done it this way so that a future commit which has to remove this special case would not need to modify any lines, just drop the code. This code is required at this commit because nFeeRet itself includes not_input_fees, so KnapsackSolver would always be trying to choose more coins than it actually needs. However in the next commit, this is just dropped directly because it is no longer needed once KnapsackSolver uses effective value.

ryanofsky · 2021-05-19T19:16:07Z

src/wallet/wallet.cpp

                        assert(change_and_fee < nFeeRet);
-                        nFeeRet = orig_fee;


In commit "Roll static tx fees into nValueToSelect instead of having it be separate" (67fc8b7)

I could be thinking about this wrong, but this change seems backwards. It matches the description which says "use the changeless nFeeRet when iterating for KnapsackSolver. This is because we include
the change fee when doing KnapsackSolver, so nFeeRet on furtheriterations won't include the change fee."

But isn't this the opposite of what we want? If KnapSackSolver is going to find a solution requiring a change output, shouldn't nFeeRet be set to the full cost of a transaction including the change output (orig_fee)? Not the cost of the smaller transaction without a change output.

It's because we are including the change fee during SelectCoinsMinConf. So using the fee that includes the change fee results in us targeting a slightly higher value than we actually need. This is also moot because we stop the looping behavior in the next two commits that have KnapsackSolver use effective values.

ryanofsky · 2021-05-19T19:24:22Z

src/wallet/wallet.cpp

-                        continue;
+                        // Since we use effective values now, it should not be possible to reach this situation where the change value was not
+                        // enough to cover the fees
+                        error = _("Cannot reduce change to cover transaction fees");


In commit "Have KnapsackSolver actually use effective values" (a07552b)

Would be good to change the error to "Bug: Cannot reduce change to cover transaction fees" or "Unexpected condition: Cannot reduce change to cover transaction fees" or just use CHECK_NONFATAL(false) or assert(false), so it is clearer this shouldn't happen, or if it does happen it's a bug and not the user doing something wrong.

Following your suggested diff, this error condition was removed and I haven't quite figured out the correct place to reintroduce it.

In commit "Have KnapsackSolver actually use effective values" (01dc8eb)

Following your suggested diff, this error condition was removed and I haven't quite figured out the correct place to reintroduce it.

Not important, but I think the updated equivalent after 01dc8eb would be:

--- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -3004,10 +3004,9 @@ bool CWallet::CreateTransactionInternal( error = _("Signing transaction failed"); return false; } - nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes); + CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes); // Subtract fee from the change output if not subtrating it from recipient outputs - CAmount fee_needed = nFeeRet; if (nSubtractFeeFromAmount == 0) { change_position->nValue -= fee_needed; } @@ -3071,6 +3070,10 @@ bool CWallet::CreateTransactionInternal( nFeeRet = fee_needed; break; // The fee has been deducted from the recipients, nothing left to do here } + CHECK_NONFATAL(!coin_selection_params.use_bnb); + CHECK_NONFATAL(nFeeRet == 0); + CHECK_NONFATAL(fee_needed != 0); + nFeeRet = fee_needed; } // Give up if change keypool ran out and change is required

achow101 · 2021-05-19T19:44:25Z

I've updated this to include @ryanofsky's suggested changes.

ryanofsky · 2021-05-19T20:01:39Z

Thanks for following up, and I'll take a look at the updates. I still don't get c += std::max(0, a-b); instead of c += a; c =- b;, but I can see basically the new things I've been confused by are temporary and removed later commits so not worth perfecting or putting too much effort into.

ryanofsky

Code review ACK 51a3ac2. Looks good to go!

ryanofsky · 2021-05-21T18:56:05Z

src/wallet/wallet.cpp

+                // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the
+                // inputs that we found in the previous iteration.
+                if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) {
+                    nValueToSelect += std::max(CAmount(0), nFeeRet - not_input_fees);


In commit "Roll static tx fees into nValueToSelect instead of having it be separate" (bf26e01)

Just want to record some notes about this commit since there is so much going on. IMO, this could be split up an made more clear, but probably not worth it since it won't affect the end results. This commit is doing a few things:

For the BnB case, it is adding not_input_fees as the value to select in CreateTransactionInternal line 2957 instead of in SelectCoinsBnB line 73. This is not a change in behavior, just the value being added in a different place so BnB and knapsack can share the same effective value logic later.

For the non-BnB knapsack case, not_input_fees is immediately subtracted again on line 2962 from the value to select, to undo the just mentioned line 2957 change, and try to avoid changing knapsack behavior. But the undo subtraction does not happen and there is a change in behavior if subtract fee from recipients is enable. The undo subtraction also does not happen because of std::max if not_fee_inputs is greater than nFeeRet, which will be true the first time Knapsack is called after BnB fails. In both of these cases it's unclear if the change in behavior is intentional, but maybe knapsack will be more likely to succeed with these changes. Also it won't matter anyway after the later commit switching knapsack to use effective values.

For the BnB case, nFeeRet is no longer added to the value to select on line 2936. The shouldn't be a change in behavior because nFeeRet should always be 0 in this case. For the non-BnB case, nFeeRet is just added later on line 2962 instead. It looks like a change in behavior because again the std::max skips the addition when not_fee_inputs is greater than nFeeRet, but I believe that can't happen unless nFeeRet is 0, in which case adding wouldn't have any effect anyway. So I think there is no change in behavior. Also this logic is going away when knapsack switches to effective values, so it shouldn't matter long run.

On line 2422, change output cost is added to knapsack target value. This is a change in behavior and seems to not really be tied to the other changes in this commit. The way I understand it, it could temporarily result in knapsack targeting too high because nFeeRet will also include the cost of the change output, so change output cost is considered twice as expensive for targetting. But this is again fixed later with the knapsack switch to effective values. (In general, targeting cost of change output makes sense for knapsack but not bnb because bnb solutions should not have change and knapsack solutions should.)

instagibbs

review ACK 51a3ac2

Large sections of "pure refactors" which probably aren't(most places I questioned where also questioned by russel), however the resulting code is much simpler to understand imo, and this is a band aid pull long-overdue.

instagibbs · 2021-05-24T02:04:32Z

src/wallet/wallet.h

@@ -621,6 +621,10 @@ struct CoinSelectionParams
    size_t change_output_size = 0;
    /** Size of the input to spend a change output in virtual bytes. */
    size_t change_spend_size = 0;
+    /** Cost of creating the change output. */


not in love with these names since they're both costs, but only one says "cost"

instagibbs · 2021-05-24T02:18:37Z

src/wallet/wallet.cpp

+                // 1. The change output would be dust
+                // 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)
+                CAmount change_amount = change_position->nValue;
+                if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change)


bnb_used becomes change_amount <= coin_selection_params.m_cost_of_change, need to make sure this is not a behavior change overall

the logic itself is fine to me, whether or not it's a change in behavior overall in this commit

instagibbs · 2021-05-24T02:32:32Z

src/wallet/wallet.cpp


                // Dummy fill vin for maximum size estimation
                //
                for (const auto& coin : setCoins) {
                    txNew.vin.push_back(CTxIn(coin.outpoint,CScript()));
                }

+                // Calculate the transaction fee
                tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
                nBytes = tx_sizes.first;


not your fault, but I find this tuple poorly/non-documented. Had to read the actual source to figure out what it is

instagibbs · 2021-05-24T03:04:23Z

src/wallet/wallet.cpp

+
+                // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the
+                // inputs that we found in the previous iteration.
+                if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) {


this section doesn't seem straight forward but it promptly vanishes so whatever

meshcollider

Re-review in progress ...

re-light-utACK 51a3ac2

meshcollider · 2021-05-25T12:21:40Z

src/wallet/wallet.cpp

+            // Get size of spending the change output
+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
+            // as lower-bound to allow BnB to do it's thing


Behavior might have recently changed in bitcoin#17331 (it is not clear) but not noticed because there is no test coverage. This adds test coverage for current subtract from recipient behavior without changing it.

Behavior might have recently changed in bitcoin#17331 (it is not clear) but not noticed because there is no test coverage. This adds test coverage for current subtract from recipient behavior without changing it. Co-authored-by: Andrew Chow <achow101-github@achow101.com>

96c2c95 scripted-diff: Rename SelectCoinsMinConf to AttemptSelection (Andrew Chow) b583f73 Move vin filling to before final fee setting (Andrew Chow) d39cac0 Set m_subtract_fee_outputs during recipients vector loop (Andrew Chow) 364e069 Move variable initializations to where they are used (Andrew Chow) 32ab430 Move recipients vector checks to beginning of CreateTransaction (Andrew Chow) cd1d6d3 Rename nSubtractFeeFromAmount in CreateTransaction (Andrew Chow) dac21c7 Rename nValue and nValueToSelect (Andrew Chow) d2aee3b Remove extraneous scope in CreateTransactionInternal (Andrew Chow) b299596 Move cs_wallet lock in CreateTransactionInternal to top of function (Andrew Chow) Pull request description: #17331 did some refactors and cleanup of `CreateTransactionInternal` to make it easier to understand, however it is still a bit convoluted even though it doesn't have to be. This PR does additional cleanup and refactoring to `CreateTransactionInternal` so that it is easier to understand. Some unnecessary code was removed, some variables moved around to where they matter, and several indents removed. ACKs for top commit: glozow: reACK 96c2c95 ryanofsky: Code review ACK 96c2c95 also acked previously (was reverted). meshcollider: re-utACK 96c2c95 Tree-SHA512: 3dba67ed436968a07bfd82d435d566ad74e116c6e50ac9baed7144a46ad5c0f630b1ba59d91e8e8972ac2af559d7c0576f0560f09684d2ab20fad6689902866f

Behavior might have recently changed in bitcoin#17331 (it is not clear) but not noticed because there is no test coverage. This adds test coverage for current subtract from recipient behavior without changing it. Co-authored-by: Andrew Chow <achow101-github@achow101.com>

…ehavior fe6dc76 wallet test: Add test for subtract fee from recipient behavior (Russell Yanofsky) 2565478 wallet test refactor: add CreateSyncedWallet function (Russell Yanofsky) Pull request description: This adds test coverage for wallet subtract from recipient behavior without changing it. Behavior seems to have changed recently in a minor way in #17331 without being noticed. ACKs for top commit: achow101: ACK fe6dc76 glozow: ACK fe6dc76 promag: Code review ACK fe6dc76. Tree-SHA512: e00c5dfe467e4ccef5edb0dd4fff6c53f35a37828a4327bea2e166751e5ef971d519ffca7b8f735b12912bb4a547980626356bc1855981005aed1a6c2a57be0b

This removes a lot of the craziness that was added during the 0.21 rebase 240f03f (Bitcoin PR #17290) as well as a lot of other upstream craziness. It's a very positive change but will probably be a bear to review. There are two places where I (purposely) nontrivially changed the logic beyond what the upstream PR did: 1. When setting the change output positions, I used a uniform distribution for all change outputs and also obeyed the user's `change_position` choice. The old code was non-uniform and had a bug where it would offset the change position. For non-policy assets, I do not create zero-sized change since we would just remove them later. For the policy asset, I do sometimes create zero-sized change since the upstream logic expects it to exist. 2. Rather than "reblinding whenever something changes" we blind once for size/fee estimation purposes and then again at the end after all potential adjustments have been made. The resulting code should be closer to upstream. We should really redo this code though because our use of the `BlindDetails` structure is very confusing and stateful. 3. We consider whether or not we're using CT/CA when estimating the size of change outpust. This is because we now use branch and bound far more often (yay!) which selects coins such that there will be no change output. This is implemented however by adding a change output then dumping it to fees ... meaning that if we dramatically overestimate the size of a change out then we'll end up dramatically dumping too many coins to fees. There are another couple small things, which I apologize for .. this PR took me 2 hours to get compiling and 11 hours to get working(!!) and some things got away from me. One fun thing is that I changed CWallet::SelectCoinsMinConf to gate an addition on coin_selection_params.m_subtract_fee_outputs ... this is actually an upstream bug that I'll file whenever I get around to producing a test that triggers it. (A bit hard as I have to gin up a scenario where branch-and-bound fails to hit this codepath.) Also, in test/functional/wallet_bumpfee.py I had to change the feerate required to force selection to add another input from 500 to 800. I don't know why and I don't care to figure it out.

fanquake added the Wallet label Oct 31, 2019

achow101 force-pushed the effective-value branch from 968248a to a1dac94 Compare November 13, 2019 06:55

achow101 mentioned this pull request Nov 19, 2019

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

Merged

Sjors mentioned this pull request Nov 20, 2019

High level road map for coin selection changes #12605

Closed

DrahtBot added the Needs rebase label Nov 22, 2019

achow101 force-pushed the effective-value branch from a1dac94 to 75b29f6 Compare November 22, 2019 21:37

DrahtBot removed the Needs rebase label Nov 22, 2019

achow101 mentioned this pull request Nov 25, 2019

wallet: fix when sufficient preset inputs and subtractFeeFromOutputs #17568

Merged

DrahtBot added the Needs rebase label Dec 1, 2019

achow101 force-pushed the effective-value branch 2 times, most recently from dcfa6ef to aee449e Compare December 2, 2019 15:13

DrahtBot removed the Needs rebase label Dec 2, 2019

DrahtBot mentioned this pull request Feb 20, 2020

Replace current benchmarking framework with nanobench #18011

Merged

This was referenced Mar 6, 2020

wallet: error if an explicit fee rate was given but the needed fee rate differed #18275

Merged

rpc/wallet: initialize nFeeRequired to avoid using garbage value on failure #18274

Merged

fjahr reviewed Mar 13, 2020

View reviewed changes

src/wallet/coinselection.h 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 effective-value branch 2 times, most recently from 4da370c to ebe0c80 Compare March 13, 2020 16:03

achow101 added 4 commits May 19, 2021 14:37

Remove use_bnb and bnb_used

6f0d518

These booleans are no longer needed

Change SelectCoins_test to actually test SelectCoins

6d6d278

This was originally modified to use SelectCoinsMinConf in order to test both BnB and Knapsack at the same time. But since SelectCoins does both now, this is no longer necessary and we can revert back to actually testing SelectCoins.

achow101 force-pushed the effective-value branch from 57590fb to 51a3ac2 Compare May 19, 2021 19:42

ryanofsky reviewed May 19, 2021

View reviewed changes

This was referenced May 20, 2021

wallet: Cleanup and refactor CreateTransactionInternal #22008

Merged

wallet: Decide which coin selection solution to use based on waste metric #22009

Merged

ryanofsky approved these changes May 21, 2021

View reviewed changes

instagibbs approved these changes May 24, 2021

View reviewed changes

DrahtBot mentioned this pull request May 24, 2021

Replace size/weight estimate tuple with struct for named fields #22042

Merged

meshcollider reviewed May 25, 2021

View reviewed changes

meshcollider merged commit 6b25481 into bitcoin:master May 25, 2021

ryanofsky mentioned this pull request Jun 4, 2021

wallet test: Add test for subtract fee from recipient behavior #22155

Merged

achow101 mentioned this pull request Jan 28, 2022

Deprecate SubtractFeeFromOutputs #24142

Closed

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

Use effective values throughout coin selection #17331

Use effective values throughout coin selection #17331

Uh oh!

Conversation

achow101 commented Oct 31, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

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

Uh oh!

Uh oh!

laanwj commented Nov 2, 2019

Uh oh!

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

Uh oh!

Uh oh!

fjahr left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

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

ryanofsky May 24, 2021 • 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!

achow101 commented May 19, 2021

Uh oh!

ryanofsky commented May 19, 2021

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

instagibbs left a comment • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

meshcollider left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

achow101 commented Oct 31, 2019 •

edited

Loading

DrahtBot commented Oct 31, 2019 •

edited

Loading

instagibbs commented Nov 1, 2019 •

edited

Loading

achow101 commented Nov 13, 2019 •

edited

Loading

ryanofsky May 24, 2021 •

edited

Loading

instagibbs left a comment •

edited

Loading