Use effective values throughout coin selection

achow101 commented at 6:59 pm on October 31, 2019: member

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

fanquake added the label Wallet on Oct 31, 2019

DrahtBot commented at 7:22 pm on October 31, 2019: 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:

#22042 (Replace size/weight estimate tuple with struct for named fields by instagibbs)
#21207 (MOVEONLY: CWallet transaction code out of wallet.cpp/.h by ryanofsky)
#21206 (refactor: Make CWalletTx sync state type-safe by ryanofsky)
#20640 (wallet, refactor: return out-params of CreateTransaction() as optional struct by theStack)
#17355 (gui: grey out used address in address book by za-kk)
#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 commented at 4:17 pm on November 1, 2019: member

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 commented at 10:27 am on November 2, 2019: member

Concept ACK, thanks for making this code more understandable.

achow101 commented at 0:10 am on November 13, 2019: member

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.

achow101 force-pushed on Nov 13, 2019

DrahtBot added the label Needs rebase on Nov 22, 2019

achow101 force-pushed on Nov 22, 2019

DrahtBot removed the label Needs rebase on Nov 22, 2019

DrahtBot added the label Needs rebase on Dec 1, 2019

achow101 force-pushed on Dec 2, 2019

DrahtBot removed the label Needs rebase on Dec 2, 2019

in src/wallet/coinselection.h:102 in e8a280b98d outdated

 98@@ -99,7 +99,7 @@ struct OutputGroup
 99     OutputGroup GetPositiveOnlyGroup();
100 };
101 
102-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
103+bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);

fjahr commented at 1:58 pm on March 13, 2020:

rename target_value to actual_target here as well?

achow101 commented at 3:34 pm on March 13, 2020:

Done

in src/wallet/wallet.cpp:2663 in aee449e028 outdated

2657@@ -2653,9 +2658,10 @@ bool CWallet::CreateTransaction(interfaces::Chain::Lock& locked_chain, const std
2658 
2659                 // Never create dust outputs; if we would, just
2660                 // add the dust to the fee.
2661-                // When nChange is less than the cost of the change output,
2662-                // send it to fees (this means BnB was used)
2663-                if (IsDust(newTxOut, discard_rate) || nChange <= cost_of_change)
2664+                // When the selected_value is within the exact match range
2665+                // (nValue + not_input_fees + cost_of_change), don't make change.
2666+                WalletLogPrintf("%d %d %d %d %d\n", selected_eff, nValue, not_input_fees, cost_of_change, selected_value);

fjahr commented at 2:06 pm on March 13, 2020:

This looks like a debug print?

achow101 commented at 3:34 pm on March 13, 2020:

Removed

in src/wallet/wallet.cpp:3018 in cd2f48cd73 outdated

2877+                    int i = 0;
2878+                    bool fFirst = true;
2879+                    for (const auto& recipient : vecSend)
2880+                    {
2881+                        if (i == nChangePosInOut) {
2882+                            ++i;

fjahr commented at 2:22 pm on March 13, 2020:

Is this missing a continue here?

achow101 commented at 3:34 pm on March 13, 2020:

No. What this is doing is that we are skipping the index that is reserved for the change output. Doing continue would skip the current recipient which we definitely don’t want to do.

fjahr commented at 0:38 am on March 18, 2020:

Got it. I was irritated because of seeing in this case ++i was called twice in the loop.

fjahr commented at 2:25 pm on March 13, 2020: member

Concept ACK

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

achow101 force-pushed on Mar 13, 2020

DrahtBot added the label Needs rebase on Apr 17, 2020

achow101 force-pushed on Apr 19, 2020

DrahtBot removed the label Needs rebase on Apr 19, 2020

DrahtBot added the label Needs rebase on May 4, 2020

achow101 force-pushed on May 4, 2020

DrahtBot removed the label Needs rebase on May 4, 2020

in src/wallet/test/coinselector_tests.cpp:545 in d9c083ea53 outdated

541@@ -542,17 +542,18 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
542           for (int i = 0; i < RUN_TESTS; i++) {
543             // picking 50 from 100 coins doesn't depend on the shuffle,

fjahr commented at 4:09 pm on May 25, 2020:

Comment is outdated here, might be confusing even with the update below.

achow101 commented at 8:02 pm on May 26, 2020:

Done

in src/wallet/test/coinselector_tests.cpp:553 in d9c083ea53 outdated

550             BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
551 
552             int fails = 0;
553             for (int j = 0; j < RANDOM_REPEATS; j++)
554             {
555                 // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time

fjahr commented at 4:10 pm on May 25, 2020:

Should also be updated since it’s now 0.5.

achow101 commented at 8:02 pm on May 26, 2020:

Done

in src/wallet/wallet.cpp:2915 in 919abc311d outdated

2911@@ -2964,7 +2912,7 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransac
2912     reservedest.KeepDestination();
2913 
2914     WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Needed:%d Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
2915-              nFeeRet, nBytes, nFeeNeeded, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,
2916+              nFeeRet, nBytes, nFeeRet, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,

fjahr commented at 4:43 pm on May 25, 2020:

If “Needed” is always the same as “Fee” maybe just remove it from the log string?

achow101 commented at 8:02 pm on May 26, 2020:

Removed

in src/wallet/wallet.cpp:2843 in 919abc311d outdated

3002-                // need to subtract, we have no reason to reselect inputs
3003-                if (nSubtractFeeFromAmount > 0) {
3004-                    pick_new_inputs = false;
3005+                        if (recipient.fSubtractFeeFromAmount)
3006+                        {
3007+                            assert(nSubtractFeeFromAmount != 0);

fjahr commented at 5:04 pm on May 25, 2020:

Since we are already in an if branch that asserts the exact same thing, I think this assert is not necessary.

achow101 commented at 8:02 pm on May 26, 2020:

Removed

fjahr approved

fjahr commented at 7:20 pm on May 25, 2020: member

Code review ACK aec7fff512c61a84563801418ef56f3d97f4344b

Very nice improvements. I had a few more nit-ish comments if you are retouching anyway.

achow101 force-pushed on May 26, 2020

DrahtBot added the label Needs rebase on Jun 16, 2020

achow101 force-pushed on Jun 17, 2020

DrahtBot removed the label Needs rebase on Jun 17, 2020

DrahtBot added the label Needs rebase on Jul 30, 2020

achow101 force-pushed on Jul 30, 2020

DrahtBot removed the label Needs rebase on Jul 30, 2020

meshcollider commented at 1:01 am on August 2, 2020: contributor

Concept ACK. This looks okay to me so far with some review, but I am still getting my head around coin selection, so I want to review this a bit more before giving a review ack.

Also 0f8955ff1b2e99a4b56a3dad465833ec86ec05fd seems should just be squashed.

achow101 force-pushed on Aug 11, 2020

achow101 commented at 6:27 pm on August 11, 2020: member

Also 0f8955f seems should just be squashed.

Squashed. That commit is part of #17458, so comments about it should be left there.

achow101 force-pushed on Aug 17, 2020

instagibbs commented at 7:37 pm on September 28, 2020: member

https://travis-ci.org/github/bitcoin/bitcoin/jobs/718692541#L3326

Error, wallet loading race?

Will review again.

in src/wallet/wallet.cpp:2323 in 1a933ccea4 outdated

2341+    CAmount change_fee = coin_selection_params.effective_fee.GetFee(coin_selection_params.change_output_size);
2342+    CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + change_fee;
2343+
2344+    // Filter by the min conf specs and add to utxo_pool and calculate effective value
2345+    std::vector<OutputGroup> positive_groups;
2346+    std::vector<OutputGroup> all_groups;

instagibbs commented at 7:45 pm on September 28, 2020:

Leave a comment why this is here. Would be confusing for someone that doesn’t know the controversial history of our hoovering UTXO manager :)

achow101 commented at 9:29 pm on September 29, 2020:

Added a comment

in src/wallet/wallet.cpp:2338 in 833c1cf204 outdated

2334@@ -2335,13 +2335,12 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
2335         all_groups.push_back(group);
2336     }
2337 
2338-    if (coin_selection_params.use_bnb) {

instagibbs commented at 7:52 pm on September 28, 2020:

note to reviewers: this is removed next commit

in src/wallet/wallet.cpp:2766 in a99a7cb93e outdated

2777+            }
2778+            for (const auto& recipient : vecSend)
2779+            {
2780+                CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
2781+
2782+                // Include the fee cost for outputs. Note this is only used for BnB right now

instagibbs commented at 8:05 pm on September 28, 2020:

err. no?

achow101 commented at 9:30 pm on September 29, 2020:

Removed

in src/wallet/wallet.cpp:2780 in a99a7cb93e outdated

2822-                            error = _("Transaction amount too small");
2823-                        return false;
2824+                            error = _("The transaction amount is too small to send after the fee has been deducted");
2825                     }
2826-                    txNew.vout.push_back(txout);
2827+                    else

instagibbs commented at 8:07 pm on September 28, 2020:

let’s bracketize while we’re here.

achow101 commented at 9:30 pm on September 29, 2020:

Braketized where this was moved to.

in src/wallet/wallet.cpp:2775 in a99a7cb93e outdated

2814-                            if (txout.nValue < 0)
2815-                                error = _("The transaction amount is too small to pay the fee");
2816-                            else
2817-                                error = _("The transaction amount is too small to send after the fee has been deducted");
2818-                        }
2819+                        if (txout.nValue < 0)

instagibbs commented at 8:07 pm on September 28, 2020:

let’s bracketize while we’re here.

instagibbs commented at 8:33 pm on September 28, 2020:

Actually, this is impossible now since you moved the subtract from fee parts to later?

achow101 commented at 9:30 pm on September 29, 2020:

Yes. Moved this to the later part.

in src/wallet/wallet.cpp:2777 in a99a7cb93e outdated

2816-                            else
2817-                                error = _("The transaction amount is too small to send after the fee has been deducted");
2818-                        }
2819+                        if (txout.nValue < 0)
2820+                            error = _("The transaction amount is too small to pay the fee");
2821                         else

instagibbs commented at 8:07 pm on September 28, 2020:

let’s bracketize while we’re here.

achow101 commented at 9:30 pm on September 29, 2020:

Removed this else

in src/wallet/wallet.cpp:2792 in a99a7cb93e outdated

2847+            // Choose coins to use
2848+            CAmount selected_value = 0;
2849+            setCoins.clear();
2850+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
2851+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
2852+            // as lower-bound to allow BnB to do it's thing

instagibbs commented at 8:08 pm on September 28, 2020:

0            // as lower-bound to allow coin selection to do its thing

achow101 commented at 9:31 pm on September 29, 2020:

Done

in src/wallet/wallet.cpp:2808 in a99a7cb93e outdated

2876-                const CAmount nChange = nValueIn - nValueToSelect;
2877-                if (nChange > 0)
2878-                {
2879-                    // Fill a vout to ourself
2880-                    CTxOut newTxOut(nChange, scriptChange);
2881+            const CAmount nChange = selected_value - nValue;

instagibbs commented at 8:11 pm on September 28, 2020:

let’s please rename this to something like total_recipient_value, I find this name actually worse than previous

achow101 commented at 9:31 pm on September 29, 2020:

Done

in src/wallet/wallet.cpp:3003 in a99a7cb93e outdated

3034+                        nChangePosInOut = -1;
3035+                        nFeeRet += change_position->nValue;
3036+                        txNew.vout.erase(change_position);
3037                     }
3038                 }
3039+                // Reduce output values for subtractFeeFromAmount

instagibbs commented at 8:18 pm on September 28, 2020:

nit: make this an else if since they can’t both happen

achow101 commented at 9:31 pm on September 29, 2020:

Done

in src/wallet/wallet.cpp:2953 in a99a7cb93e outdated

2900+                // When nChange is less than the cost of the change output,
2901+                // send it to fees (this means BnB was used)
2902+                if (IsDust(newTxOut, discard_rate) || nChange <= cost_of_change)
2903+                {
2904+                    nChangePosInOut = -1;
2905+                    nFeeRet = nChange;

instagibbs commented at 8:19 pm on September 28, 2020:

this change from += to = looks correct, just kind of sneaky. Throw in an assert that it’s 0 before setting?

achow101 commented at 9:31 pm on September 29, 2020:

Done

in src/wallet/wallet.cpp:2773 in a99a7cb93e outdated

2805-                    }
2806 
2807-                    if (IsDust(txout, chain().relayDustFee()))
2808+                if (IsDust(txout, chain().relayDustFee()))
2809+                {
2810+                    if (recipient.fSubtractFeeFromAmount && nFeeRet > 0)

instagibbs commented at 8:35 pm on September 28, 2020:

It can only fire if you’ve already encountered the change position and discarded it based on discard_rate check. I think this check is supposed to be talking about when subtract from fee is being done earlier?

I think this whole section just becomes “Transaction amount too small” error?

achow101 commented at 9:31 pm on September 29, 2020:

Yes. Moved the subtract from fee checks to the part where that is actually being done.

in src/wallet/wallet.cpp:2878 in a99a7cb93e outdated

3035+                        nFeeRet += change_position->nValue;
3036+                        txNew.vout.erase(change_position);
3037                     }
3038                 }
3039+                // Reduce output values for subtractFeeFromAmount
3040+                if (nSubtractFeeFromAmount != 0) {

instagibbs commented at 8:35 pm on September 28, 2020:

doesn’t this section need to make sure we didn’t turn outputs into relay dust?

achow101 commented at 9:31 pm on September 29, 2020:

Added from above.

in src/wallet/wallet.cpp:2876 in 1ca165572a outdated

2819@@ -2815,9 +2820,9 @@ bool CWallet::CreateTransactionInternal(
2820 
2821                 // Never create dust outputs; if we would, just
2822                 // add the dust to the fee.
2823-                // When nChange is less than the cost of the change output,
2824-                // send it to fees (this means BnB was used)
2825-                if (IsDust(newTxOut, discard_rate) || nChange <= cost_of_change)
2826+                // When the selected_value is within the exact match range

instagibbs commented at 8:39 pm on September 28, 2020:

Not immediately obvious to me what this change is doing, explain? Also this should say selected_eff?

achow101 commented at 9:36 pm on September 29, 2020:

This is essentially doing what used_bnb did.

If the selected effective value is within the exact matching range that we use for BnB, then let the change go to fees.

instagibbs commented at 8:40 pm on September 28, 2020: member

imo we should target this getting into master just after 0.21 split to give it time to mature

achow101 force-pushed on Sep 29, 2020

achow101 commented at 9:37 pm on September 29, 2020: member

Rebased this onto #20040 as I think the refactor there makes this easier to understand. Also, there was a silent merge conflict with master.

achow101 force-pushed on Sep 30, 2020

achow101 force-pushed on Oct 2, 2020

achow101 force-pushed on Nov 2, 2020

achow101 force-pushed on Nov 10, 2020

DrahtBot added the label Needs rebase on Nov 17, 2020

achow101 force-pushed on Nov 17, 2020

DrahtBot removed the label Needs rebase on Nov 17, 2020

achow101 force-pushed on Nov 17, 2020

in src/bench/coin_selection.cpp:52 in f63d750fa8 outdated

53+        coins.emplace_back(wtx.get(), 0 /* iIn */, 6 * 24 /* nDepthIn */, true /* spendable */, true /* solvable */, true /* safe */);
54     }
55 
56     const CoinEligibilityFilter filter_standard(1, 6, 0);
57-    const CoinSelectionParams coin_selection_params(true, 34, 148, CFeeRate(0), 0);
58+    const CoinSelectionParams coin_selection_params(true, 34, 148, CFeeRate(0), 0, false);

Xekyo commented at 3:40 pm on December 4, 2020:

I see that this is setting a default false for avoidPartial. Did you consider setting it to true by default, and why didn’t you? (I’d have a few ideas, but I was curious what you considered.)

achow101 commented at 9:12 pm on December 8, 2020:

I had not considered enabling avoidpartial.

in src/wallet/wallet.cpp:2378 in 3693938681 outdated

2374+        CFeeRate effective_feerate{0};
2375+        if (!coin_selection_params.m_subtract_fee_outputs) {
2376+            effective_feerate = coin_selection_params.effective_fee;
2377+        }
2378+
2379+        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, eligibility_filter.max_ancestors, effective_feerate, long_term_feerate);

Xekyo commented at 3:48 pm on December 4, 2020:

I’m still confused by this approach, given that it may lead to spending uneconomic unspents due to the receiver paying the fees. I understand from the last PR I looked at, that this function is often used for sweeping wallets. To offer another perspective, I’m aware of multiple Bitcoin services that make their customers pay the transaction fees for withdrawals and in that case I would consider such a behavior potentially conflict inducing.

achow101 commented at 9:14 pm on December 8, 2020:

Given that this is how we currently handle subtracting the fee from outputs for BnB, I would prefer to preserve this behavior for now for all effective value things. We can revisit this in a followup.

in src/wallet/wallet.cpp:4218 in 3693938681 outdated

4216@@ -4217,15 +4217,16 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4217                     // high amount of fees.
4218                     if (it->second.m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {

Xekyo commented at 3:53 pm on December 4, 2020:

The “breaking consensus” part of the comment seems a bit spurious, given that OUTPUT_GROUP_MAX_ENTRIES appears to be set to ten, and 400,000 WU is the standardness limit, not even a consensus rule.

Frankly, anyone using -avoidpartialspends for privacy reasons would be severely confused if they reused addresses heavily enough to bump into this issue, but still…

in src/wallet/wallet.cpp:4221 in 3693938681 outdated

4216@@ -4217,15 +4217,16 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4217                     // high amount of fees.
4218                     if (it->second.m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {
4219                         groups.push_back(it->second);
4220-                        it->second = OutputGroup{};
4221+                        it->second = OutputGroup{effective_feerate, long_term_feerate};
4222                         full_groups.insert(dst);

Xekyo commented at 4:03 pm on December 4, 2020:

I find this hard to read. So you have a map, retrieve the coins with the same destination (i.e. invoice address), then read the value of the map by calling the “second” (presumably value) of an iterator item. If it’s full, it gets added to groups, but what is that in line 4220 then? Are you overwriting the element in the map with an empty output group as a shortcut to remove the final group and creating a new one for the remaining UTXOs with the same address?

Given that you’re calling it->second multiple times here, it would help readability to turn that into a named variable. Maybe also call gmap either group_map or even address_output_group_map.

achow101 commented at 9:17 pm on December 8, 2020:

Yes. The full group is added to the groups vector and the group in the map is reset to a fresh group for any further outputs to add for that destination.

in src/wallet/wallet.cpp:4226 in 3693938681 outdated

4223                     }
4224                     it->second.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4225                 } else {
4226-                    gmap[dst].Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4227+                    auto ins = gmap.emplace(dst, OutputGroup{effective_feerate, long_term_feerate});
4228+                    ins.first->second.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);

Xekyo commented at 4:09 pm on December 4, 2020:

I find it hard to wrap my head around all the possible outcomes for this functions due to the four levels of nested if’s followed by else branches.

Put the simpler cases to the top, i.e. starting with if (single_coin) { "add group" } then do the more complex cases. I think you can reduce this by at least two levels of nesting.

Also, how is this followed by another if(!single_coin) after all of that already?

achow101 commented at 1:21 am on December 9, 2020:

Done in the upstream pr.

in src/wallet/wallet.cpp:2364 in b573d8f548 outdated

2359@@ -2360,8 +2360,8 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
2360     setCoinsRet.clear();
2361     nValueRet = 0;
2362 
2363-    std::vector<OutputGroup> utxo_pool;
2364     if (coin_selection_params.use_bnb) {
2365+        std::vector<OutputGroup> utxo_pool;

Xekyo commented at 6:15 pm on December 4, 2020:

I don’t understand why the grouping has been moved into the scope of using BnB. Wouldn’t the groups be used for any unspent selection?

achow101 commented at 9:20 pm on December 8, 2020:

I’m not sure which commit this comment is for. The particular change is not present in the final diff.

in src/wallet/wallet.cpp:4222 in b573d8f548 outdated

4218@@ -4226,8 +4219,10 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4219                     ins.first->second.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4220                 }
4221             } else {
4222-                groups.emplace_back(effective_feerate, long_term_feerate);
4223-                groups.back().Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4224+                // This is for if each output gets it's own OutputGroup

Xekyo commented at 6:25 pm on December 4, 2020:

How about // Every OutputGroup has only one output

achow101 commented at 1:21 am on December 9, 2020:

Done

in src/wallet/wallet.cpp:4236 in b573d8f548 outdated

4232@@ -4238,7 +4233,8 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4233                 // Make this unattractive as we want coin selection to avoid it if possible
4234                 group.m_ancestors = max_ancestors - 1;
4235             }
4236-            groups.push_back(group);
4237+            // If the OutputGroup is not eligible, don't add it

Xekyo commented at 6:28 pm on December 4, 2020:

Negations are hard to read. How about: // Only add eligible OutputGroups or // Omit OutputGroups that are not eligible

achow101 commented at 1:21 am on December 9, 2020:

Done

in src/wallet/coinselection.cpp:304 in 2ad1a94f10 outdated

299@@ -300,16 +300,24 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
300 
301  ******************************************************************************/
302 
303-void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
304+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
305+    // Compute the effective value first
306+    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
307+    const CAmount ev = output.txout.nValue - coin_fee;

Xekyo commented at 6:34 pm on December 4, 2020:

How about a method GetEffectiveValue(const CFeeRate feerate) on CInputCoin?

achow101 commented at 1:22 am on December 9, 2020:

Meh. I think it’s fine for now.

in src/wallet/coinselection.cpp:312 in 2ad1a94f10 outdated

311+
312     m_outputs.push_back(output);
313     CInputCoin& coin = m_outputs.back();
314-    coin.m_fee = coin.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(coin.m_input_bytes);
315+
316+    coin.m_fee = coin_fee;

Xekyo commented at 6:58 pm on December 4, 2020:

When I see a method called Insert, I’d expect that the passed inputs end up in the corresponding datastructure.

This method does a lot more than just inserting, though. Maybe we can find a better name for the function, or split out the other responsibilities.

achow101 commented at 1:05 am on December 9, 2020:

I think Insert is a reasonable name for it. Everything that gets passed in ends up in the data structure.

in src/wallet/test/coinselector_tests.cpp:134 in 2ad1a94f10 outdated

126@@ -127,7 +127,7 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
127     static_groups.clear();
128     for (auto& coin : coins) {
129         static_groups.emplace_back();
130-        static_groups.back().Insert(coin.GetInputCoin(), coin.nDepth, coin.tx->m_amounts[CWalletTx::DEBIT].m_cached[ISMINE_SPENDABLE] && coin.tx->m_amounts[CWalletTx::DEBIT].m_value[ISMINE_SPENDABLE] == 1 /* HACK: we can't figure out the is_me flag so we use the conditions defined above; perhaps set safe to false for !fIsFromMe in add_coin() */, 0, 0);
131+        static_groups.back().Insert(coin.GetInputCoin(), coin.nDepth, coin.tx->m_amounts[CWalletTx::DEBIT].m_cached[ISMINE_SPENDABLE] && coin.tx->m_amounts[CWalletTx::DEBIT].m_value[ISMINE_SPENDABLE] == 1 /* HACK: we can't figure out the is_me flag so we use the conditions defined above; perhaps set safe to false for !fIsFromMe in add_coin() */, 0, 0, false);

Xekyo commented at 9:19 pm on December 7, 2020:

Maybe pull out

coin.tx->m_amounts[CWalletTx::DEBIT].m_cached[ISMINE_SPENDABLE] && coin.tx->m_amounts[CWalletTx::DEBIT].m_value[ISMINE_SPENDABLE] == 1

onto its own line and assign it to a variable?

achow101 commented at 1:06 am on December 9, 2020:

Prefer to leave it alone for now since we aren’t really making related changes here.

in src/wallet/wallet.cpp:4219 in 2ad1a94f10 outdated

4218                 // This is for if each output gets it's own OutputGroup
4219                 OutputGroup coin(effective_feerate, long_term_feerate);
4220-                coin.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4221-                if (coin.EligibleForSpending(filter)) groups.push_back(coin);
4222+                coin.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
4223+                if (positive_only && coin.effective_value <= 0) continue;

Xekyo commented at 9:22 pm on December 7, 2020:

You could have coins that are not spendable at high fees but also not dust. Then this would allow UTXO received to the same address to get spent separately (part of it now, at high fees, rest later at lower fees).

Xekyo commented at 9:26 pm on December 7, 2020:

I’m almost ready to ask for a flowchart for all the possible outcomes of avoid_partial, positive_only, and various fee rates ;)

achow101 commented at 10:21 pm on December 8, 2020:

Given that this is behavior that already exists, I think we should leave this for a followup as it also requires further discussion of what we want to do.

in src/wallet/wallet.cpp:4307 in 2ad1a94f10 outdated

4228@@ -4234,7 +4229,8 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4229                 group.m_ancestors = max_ancestors - 1;
4230             }
4231             // If the OutputGroup is not eligible, don't add it
4232-            if (group.EligibleForSpending(filter)) groups.push_back(group);
4233+            if (positive_only && group.effective_value <= 0) continue;

Xekyo commented at 9:23 pm on December 7, 2020:

AFAICT, this like can never trigger, because we are disallowing adding uneconomic UXTO above when positive_only is true.

achow101 commented at 1:07 am on December 9, 2020:

Meh. Belt-and-suspenders check.

in src/wallet/coinselection.h:90 in 2a5a779542 outdated

61@@ -62,9 +62,11 @@ struct CoinEligibilityFilter
62     const int conf_theirs;
63     const uint64_t max_ancestors;
64     const uint64_t max_descendants;
65+    const bool m_include_partial_groups{false}; //! Include partial destination groups when avoid_reuse and there are full groups

Xekyo commented at 9:30 pm on December 7, 2020:

The thing with the “full groups” still baffles me. Is it reasonable to expect overlap between someone interested in privacy enough to activate avoid_partial and someone that reuses addresses heavily enough that they stack up dozens of UTXOs, yet they still aren’t diligent enough to actually consolidate the large amount of UTXOs in one low feerate transaction?

I guess what I’m saying is… I don’t understand how all these special cases fit together to provide value. I’m wondering whether we are just adding complexity without a clear value-add.

achow101 commented at 10:26 pm on December 8, 2020:

I think it’s mostly as a belt-and-suspenders type of thing. Perhaps @kallewoof can shed some light on this.

kallewoof commented at 3:46 am on January 14, 2021:

I think the thought of use case here is: someone sends you money. Later on they track you by sending insignificant amounts to the same address. Two scenarios here:

You’ve already spent from that address once. If you spend from it again, they can associate the two transactions to you*.
You haven’t spent from it once. By giving your coin selection algorithm a bunch of UTXO:s to select from, the chances are it will pick up the other ones in unrelated spends, which, again, lets them associate multiple UTXO:s with the target, you. This second part is avoided by simply always picking all or none of the outputs associated with a given address.

(* this is avoided using the avoid reuse functionality, which ensures that UTXO:s associated with a given address are only included in transactions once, except when the user requests it)

in src/wallet/wallet.cpp:2364 in c314b098fe outdated

2365-        FeeCalculation feeCalc;
2366-        CCoinControl temp;
2367-        temp.m_confirm_target = 1008;
2368-        CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);
2369+    // Calculate the fees for things that aren't inputs
2370+    CAmount not_input_fees = coin_selection_params.effective_fee.GetFee(coin_selection_params.tx_noinputs_size);

Xekyo commented at 9:38 pm on December 7, 2020:

Shouldn’t this differ by whether non-input portion of transactions built by BnB vs by Knapsack or Random is expected to have a change output or not?

achow101 commented at 1:08 am on December 9, 2020:

We deal with the change fee later.

in src/wallet/wallet.cpp:2391 in c314b098fe outdated

2407-
2408+        // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
2409+        std::vector<OutputGroup> all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, long_term_feerate, eligibility_filter, false /* positive_only */);
2410         bnb_used = false;
2411-        return KnapsackSolver(nTargetValue, groups, setCoinsRet, nValueRet);
2412+        return KnapsackSolver(nTargetValue + not_input_fees, all_groups, setCoinsRet, nValueRet);

Xekyo commented at 2:06 am on December 8, 2020:

How is ensured that the KnapsackSolver retains a sufficient amount for a decently sized change output?

achow101 commented at 1:16 am on December 9, 2020:

The minimum change stuff is within KnapsackSolver itself.

ryanofsky commented at 11:41 am on May 6, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

Suggestion: It seems like if the later “Roll not_input_fees into nValueToSelect” commit was moved before this commit (without changing the value passed to KnapsackSolver), this commit on top of that one would be smaller and could reduce the confusion of nTargetValue meaning so many different things at different places.

achow101 commented at 6:07 pm on May 6, 2021:

I believe doing that would break the tests and change the behavior of KnapsackSolver. “Roll not_input_fees into nValueToSelect” does not change behavior.

in src/wallet/test/coinselector_tests.cpp:555 in 8aa8ef25bb outdated

553 
554             int fails = 0;
555             for (int j = 0; j < RANDOM_REPEATS; j++)
556             {
557-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
558+                // selecting 0.5 from 100 identical coins depends on the shuffle; this test will fail 1% of the time

Xekyo commented at 2:10 am on December 8, 2020:

Why does this fail at all? Couldn’t we just test that selected the right count of inputs and the right input amount?

achow101 commented at 1:19 am on December 9, 2020:

Because we prefer BnB if it works, the test would previously always use BnB because the coins were always 1 * COIN. This change (and other similar changes to use a 0.5) ensures that we cannot exactly match the target with the given coins so the KnapsackSolver is always used.

glozow commented at 7:32 pm on April 1, 2021:

I think @Xekyo was referring to the “this test will fail 1% of the time” part? I was confused as well. Since you’re touching the comment maybe elaborate on it too? This test is checking that the knapsack solver has some randomness and picks different coins on different invocations, but even such, we have a 1/100 chance of picking the exact same coins, so this test fails 1% of the time.

achow101 commented at 0:13 am on April 2, 2021:

I’ve rewritten this comment.

in src/wallet/wallet.cpp:2824 in 9008dbf6a5 outdated

2789@@ -2792,215 +2790,167 @@ bool CWallet::CreateTransactionInternal(
2790             CFeeRate discard_rate = GetDiscardRate(*this);
2791 
2792             // Get the fee rate to use effective values in coin selection
2793-            CFeeRate nFeeRateNeeded = GetMinimumFeeRate(*this, coin_control, &feeCalc);
2794+            coin_selection_params.effective_fee = GetMinimumFeeRate(*this, coin_control, &feeCalc);

Xekyo commented at 2:15 am on December 8, 2020:

effective_feerate, since it’s a feerate not a fee.

achow101 commented at 10:26 pm on December 8, 2020:

Existing name, won’t change for now.

in src/wallet/wallet.cpp:2916 in 9008dbf6a5 outdated

2852+            // Choose coins to use
2853+            CAmount input_sum = 0;
2854+            setCoins.clear();
2855+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
2856+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
2857+            // as lower-bound to allow coin selection to do its thing

Xekyo commented at 2:21 am on December 8, 2020:

I assume this is to handle foreign change addresses that are opaque due to P2SH?

achow101 commented at 0:17 am on December 9, 2020:

Yes.

achow101 commented at 1:20 am on December 9, 2020:

Yes.

in src/wallet/wallet.cpp:2898 in 16c1017083 outdated

2861@@ -2857,9 +2862,9 @@ bool CWallet::CreateTransactionInternal(
2862 
2863                 // Never create dust outputs; if we would, just
2864                 // add the dust to the fee.
2865-                // When nChange is less than the cost of the change output,
2866-                // send it to fees (this means BnB was used)
2867-                if (IsDust(newTxOut, discard_rate) || nChange <= cost_of_change)
2868+                // When the selected_eff is within the exact match range
2869+                // (nValue + not_input_fees + cost_of_change), don't make change.
2870+                if (IsDust(newTxOut, discard_rate) || selected_eff <= nValue + not_input_fees + cost_of_change)

Xekyo commented at 2:24 am on December 8, 2020:

Didn’t we just call the first two of that triplet actual_target?

achow101 commented at 1:20 am on December 9, 2020:

I believe we discussed changing this, but I decided to leave that for a followup refactor that cleans up this whole function.

Xekyo commented at 2:26 am on December 8, 2020: member

I went over this a bit quickly, especially the “CreateTransaction loop refactor”. I figured I’d leave you my comments and will go over again when you have replied.

achow101 force-pushed on Dec 9, 2020

achow101 force-pushed on Jan 13, 2021

DrahtBot added the label Needs rebase on Feb 1, 2021

achow101 force-pushed on Feb 1, 2021

DrahtBot removed the label Needs rebase on Feb 1, 2021

in src/wallet/wallet.cpp:2459 in ac86704d0f outdated

2433-            if (coin_selection_params.use_bnb) {
2434-                value_to_select -= coin.effective_value;
2435-            } else {
2436-                value_to_select -= coin.txout.nValue;
2437-            }
2438+            coin.effective_value = coin.txout.nValue - (coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.effective_fee.GetFee(coin.m_input_bytes));

jonatack commented at 4:02 pm on February 4, 2021:

7865b70b60 I assume I’m confused but would have thought it would be this way around

0            coin.effective_value = coin.txout.nValue - (coin_selection_params.m_subtract_fee_outputs ? coin_selection_params.effective_fee.GetFee(coin.m_input_bytes) : 0);

It seems one of these two versions should fail but src/test/test_bitcoin -t coinselector_tests passes with both.

achow101 commented at 6:47 pm on February 5, 2021:

When we are subtracting the fee from an output, we set the effective value to its real value.

The test to use is usually test/functional/rpc_fundrawtransaction.py.

jonatack commented at 6:53 pm on February 6, 2021:

Thanks @achow101. Re-checked and wallet_bumpfee.py and rpc_psbt.py both fail with the wrong version.

in src/wallet/coinselection.cpp:55 in ac86704d0f outdated

47@@ -48,28 +48,25 @@ struct {
48  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
49  *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
50  *        values are their effective values.
51- * @param const CAmount& target_value This is the value that we want to select. It is the lower
52+ * @param const CAmount& actual_target This is the value that we want to select. It is the lower
53  *        bound of the range.
54  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
55- *        This plus target_value is the upper bound of the range.
56+ *        This plus actual_target is the upper bound of the range.

jonatack commented at 4:42 pm on February 4, 2021:

695fbaa3 Not saying it needs to be addressed in this pull but keep in mind that CAmount is a cheaply copied type that should be passed by value for “in” params.

Also not directly related but ISTM the Doxygen part of the comments should be in the header file declaration.

in src/wallet/wallet.cpp:2888 in ac86704d0f outdated

2893-                            error = _("Transaction amount too small");
2894-                        return false;
2895-                    }
2896-                    txNew.vout.push_back(txout);
2897-                }
2898+            if (!SelectCoins(vAvailableCoins, nValue + not_input_fees, setCoins, input_sum, coin_control, coin_selection_params))

jonatack commented at 4:51 pm on February 4, 2021:

695fbaa3a nicety if you retouch

0            if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValue + not_input_fees, setCoins, input_sum, coin_control, coin_selection_params))

achow101 commented at 0:18 am on April 2, 2021:

Done

in src/wallet/wallet.cpp:2894 in ac86704d0f outdated

2928-                        }
2929-                    }
2930-                } else {
2931-                    bnb_used = false;
2932-                }
2933+            CAmount selected_eff = 0;

jonatack commented at 6:11 pm on February 4, 2021:

bc963a3c I’d find this helpful, if this is what the naming means

0            CAmount selected_eff = 0; // selected effective value

achow101 commented at 0:18 am on April 2, 2021:

Done

jonatack commented at 6:15 pm on February 4, 2021: member

Non-expert-I’m-learning-here-review at ac86704d0f8724d5b7155e5d905294e795381f75, looks good after a couple of hours (the diff is hard to parse in places) but I need to look more at commit “Remove CreateTransaction while loop and some related variables” and at the subtractFeeFromOutputs logic. At each commit the changes build cleanly and the coinselector_tests pass.

laanwj added this to the "Blockers" column in a project

MarcoFalke commented at 10:37 am on February 19, 2021: member

Even though this is in high-prio, reviewers might want to review #21083 first.

Only #21083 should be backported, and it should be merged first for the backport to go smoothly. #19229 (comment)

laanwj removed this from the "Blockers" column in a project

DrahtBot added the label Needs rebase on Mar 8, 2021

achow101 force-pushed on Mar 10, 2021

DrahtBot removed the label Needs rebase on Mar 10, 2021

DrahtBot added the label Needs rebase on Mar 17, 2021

glozow commented at 9:13 pm on March 17, 2021: member

Concept ACK, planning to review more closely after rebase

achow101 force-pushed on Mar 17, 2021

DrahtBot removed the label Needs rebase on Mar 17, 2021

in src/wallet/wallet.cpp:2905 in 8e2385fbb4 outdated

2985 
2986-                    // Never create dust outputs; if we would, just
2987-                    // add the dust to the fee.
2988-                    // The nChange when BnB is used is always going to go to fees.
2989-                    if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || bnb_used)
2990+                CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);

glozow commented at 7:22 pm on April 1, 2021:

Can be const. Also, this code was not immediately obvious to me, so I think a comment (and shorter lines) would be nice.

0                // Cost of a change output = (size of output * this tx feerate) + (size of spending input * discard feerate)
1                const CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) 
2                      + coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);

achow101 commented at 0:26 am on April 2, 2021:

Added a comment. Also did the same split that was done in SelectCoinsMinConf.

in src/wallet/test/coinselector_tests.cpp:548 in 8e2385fbb4 outdated

546+            // picking 50.5 from 100 coins doesn't depend on the shuffle,
547             // but does depend on randomness in the stochastic approximation code
548-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
549-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
550+            // Use 50.5 to be sure that BnB doesn't match
551+            BOOST_CHECK(testWallet.SelectCoinsMinConf(50.5 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params));

glozow commented at 7:27 pm on April 1, 2021:

tiny nit, since you’re touching

0            BOOST_CHECK(testWallet.SelectCoinsMinConf(50.5 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));

achow101 commented at 0:27 am on April 2, 2021:

This space is to make it line up with the line below, but it doesn’t really matter. Done.

in src/wallet/wallet.cpp:2886 in 8e2385fbb4 outdated

2914-                    // Include the fee cost for outputs. Note this is only used for BnB right now
2915-                    if (!coin_selection_params.m_subtract_fee_outputs) {
2916-                        coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
2917-                    }
2918+            // Calculate the fees for things that aren't inputs
2919+            CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

glozow commented at 7:37 pm on April 1, 2021:

const all the things 😝 especially since this is the part of the fee that doesn’t change.

0            const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

achow101 commented at 0:27 am on April 2, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:547 in 8e2385fbb4 outdated

541@@ -548,19 +542,20 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
542 
543           // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
544           for (int i = 0; i < RUN_TESTS; i++) {
545-            // picking 50 from 100 coins doesn't depend on the shuffle,
546+            // picking 50.5 from 100 coins doesn't depend on the shuffle,
547             // but does depend on randomness in the stochastic approximation code
548-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
549-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
550+            // Use 50.5 to be sure that BnB doesn't match

glozow commented at 8:05 pm on April 1, 2021:

In a493cbcb26: it seems a little hacky to use 50.5 to make it use the knapsack solver, why not just call KnapsackSolver directly since that’s what you’re testing?

achow101 commented at 0:27 am on April 2, 2021:

Good idea, done.

achow101 force-pushed on Apr 2, 2021

laanwj added this to the "Blockers" column in a project

in src/wallet/wallet.cpp:2465 in 4ac1adda99 outdated

2465-            if (coin_selection_params.use_bnb) {
2466-                value_to_select -= coin.effective_value;
2467-            } else {
2468-                value_to_select -= coin.txout.nValue;
2469-            }
2470+            coin.effective_value = coin.txout.nValue - (coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.m_effective_feerate.GetFee(coin.m_input_bytes));

Xekyo commented at 4:41 pm on April 9, 2021:

I think this approach muddles two concerns. We should generally filter inputs that have a negative effective feerate, even when we do not pay for the fees, but the recipient does.

Xekyo commented at 11:39 pm on April 22, 2021:

I think it may be good if CInputCoin kept track of both nValue and n_effective_value separately. In the case of recipient paying for the tx, we could use effective value for filtering, but nValue to determine whether sufficient funds have been selected.

Xekyo commented at 11:41 pm on April 22, 2021:

Then also, effective_value wouldn’t need to be instantiated with nValue which I thought was pretty surprising.

achow101 commented at 7:29 pm on April 23, 2021:

This particular section is for pre-selected inputs, so we don’t filter here. However I do agree that changing the effective_feerate depending on whether we are subtracting the fee from the outputs doesn’t quite make sense. So I’ve changed this back to subtract the correct value from value_to_select based on coin_selection_params.m_subtract_fee_outputs.

Then also, effective_value wouldn’t need to be instantiated with nValue which I thought was pretty surprising.

I don’t think that is necessarily true.

in src/wallet/coinselection.cpp:230 in 453c00c8ea outdated

229@@ -230,14 +230,14 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
230     Shuffle(groups.begin(), groups.end(), FastRandomContext());
231 
232     for (const OutputGroup& group : groups) {
233-        if (group.m_value == nTargetValue) {
234+        if (group.effective_value == nTargetValue) {

Xekyo commented at 5:29 pm on April 9, 2021:

Since OutputGroup only exist ephemerally within the context of a specific coinselection, and the outputgroup knows the current feerate, would it perhaps make sense to make the calculation of an OutputGroup’s effective value a member function of that struct?

achow101 commented at 7:30 pm on April 23, 2021:

would it perhaps make sense to make the calculation of an OutputGroup’s effective value a member function of that struct?

I don’t think so.

However I have changed OutputGroup to have a member function which returns either m_value or effective_value depending on the coin selection parameters which OutputGroup now has a copy of.

Xekyo commented at 5:33 pm on April 30, 2021:

The output_group interpreting the context of the coin selection seems odd. Wouldn’t it make more sense to apply the coin selection parameter at the place that retrieves either effective_value or m_value?

ryanofsky commented at 11:22 pm on May 5, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

I’m trying to understand how/whether this commit changes behavior. It might be helpful to say in the commit message. It seems like this commit is definitely changing behavior of the KnapsackSolver, because now it is solving based on cost of the finally created transaction instead of ignoring that cost and requiring CreateTransactionInternal to work around and call KnapsackSolver twice. But the overall behavior is the same because of the fact that CreateTransactionInternal loops? (And the second loop is unnecessary now?)

Again a commit description would be helpful. It seems like this commit is doing a few things:

Calling KnapsackSolver with a higher nTargetvalue so it is forced to account for cost of final transaction outputs
Changin KnapsackSolver to internally use group.effective_value instead of group.m_value so it is forced to account for cost of final transaction inputs
Refactoring code in SelectCoinsMinConf mostly not changing behavior, except to call KnapsackSolver with the higher target at the end.
Tweaking SelectCoinsMinConf caller SelectCoins in the case where there are preselected coins, to stop having a special case for use_bnb, now that both bnb and knapsack paths use effective value

achow101 commented at 5:26 pm on May 6, 2021:

The way I view it is that the OutputGroup is responsible for telling the coin selection algorithm what the value for that OutputGroup is for the selection. The algo itself does not care about whether it should be effective_value or m_value except when it totals up the amount selected for nValueRet. So this change makes OutputGroup aware of which value it should be giving to the coin selection algorithm. Furthermore, OutputGroups already have to know about certain coin selection parameters in order to determine its fee, long term fee, effective value, and whether to contain dust.

achow101 commented at 8:06 pm on May 6, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:586 in d6d2a00363 outdated

581@@ -580,10 +582,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
582             int fails = 0;
583             for (int j = 0; j < RANDOM_REPEATS; j++)
584             {
585-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
586-                // run the test RANDOM_REPEATS times and only complain if all of them fail
587-                BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
588-                BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
589+                BOOST_CHECK(KnapsackSolver(90*COIN, GroupCoins(vCoins), setCoinsRet, nValueRet));
590+                BOOST_CHECK(KnapsackSolver(90*COIN, GroupCoins(vCoins), setCoinsRet2, nValueRet));

glozow commented at 5:42 pm on April 9, 2021:

You’ve changed these from 90*CENT to 90*COIN?

achow101 commented at 6:47 pm on April 23, 2021:

Oops, changed back.

in src/wallet/test/coinselector_tests.cpp:560 in d6d2a00363 outdated

561             {
562-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
563-                // run the test RANDOM_REPEATS times and only complain if all of them fail
564-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
565-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
566+                // Tests that the KnapsackSolver KnapsackSolver becomes a random selector with identical coins.

Xekyo commented at 5:46 pm on April 9, 2021:

Nit: not identical, but equivalent: “// Test that KnapsackSolver selects randomly from equivalent coins (same value and same input size).”

achow101 commented at 6:48 pm on April 23, 2021:

Done

in src/wallet/wallet.cpp:2501 in 7dd34c0929 outdated

2508+        SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params) ||
2509+        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) ||
2510+        (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)) ||
2511+        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) ||
2512+        (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)) ||
2513+        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params));

Xekyo commented at 5:57 pm on April 9, 2021:

This single boolean statement appears to encode the entire eligibility back-off strategy for coin selection. It’s very repetitive, since the only thing that changes are the eligibility filters.

You could define all variants of the eligibility filter, comment there how they’re motivated, then make a single lambda call using that list. Since res is not const, you could split it into two blocks, where the second block is generally conditional on the user generally permittting unconfirmed change outputs for the latter six strategies.

glozow commented at 11:35 pm on April 22, 2021:

Taking this as an opportunity to shill #21759 😛

achow101 commented at 4:41 pm on April 23, 2021:

I’ll leave this to #21759 to clean up.

in src/wallet/test/coinselector_tests.cpp:554 in 4ac1adda99 outdated

555             {
556-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
557-                // run the test RANDOM_REPEATS times and only complain if all of them fail
558-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
559-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
560+                // Tests that the KnapsackSolver KnapsackSolver becomes a random selector with identical coins.

fjahr commented at 10:29 pm on April 21, 2021:

0                // Tests that the KnapsackSolver becomes a random selector with identical coins.

achow101 commented at 6:46 pm on April 23, 2021:

Changed the comment.

in src/wallet/wallet.cpp:2990 in 23c85ae91e outdated

3111+                // eventually allow a fallback fee
3112+                error = _("Fee estimation failed. Fallbackfee is disabled. Wait a few blocks or enable -fallbackfee.");
3113+                return false;
3114+            }
3115+            if (nFeeRet < fee_needed) {
3116+                nFeeRet = fee_needed;

fjahr commented at 11:02 pm on April 21, 2021:

Hm, shouldn’t this be nFeeRet = fee_needed - nFeeRet; in case there is already a small dust output in nFeeRet?

achow101 commented at 6:46 pm on April 23, 2021:

No, nFeeRet needs to be the total amount in fees, and whatever small change that is being burned as fees is part of that. Furthermore, if this line is reached and we are not subtracting fee from the outputs, then we won’t have selected enough value to even cover the fees, and that would be a problem. If we are subtracting the fee from the outputs, then it is possible that we end up overpaying on the fees since the amount that we use for that calculation will include the small change being thrown away.

So I have added an else to give an error if we reach this line without a change output, and changed the subtract fee from outputs calculation to not include nChange.

All of this fee calculation stuff probably could be cleaned up (and overhauled) but I would prefer to do that in a followup.

in src/wallet/wallet.cpp:2413 in 4ac1adda99 outdated

2427+    // Cost of change is the cost of creating the change output + cost of spending the change output in the future.
2428+    // For creating the change output now, we use the effective feerate.
2429+    // For spending the change output in the future, we use the discard feerate for now.
2430+    // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate)
2431+    CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
2432+    CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;

fjahr commented at 11:10 pm on April 21, 2021:

nit

0    const CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
1    const CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;

achow101 commented at 6:46 pm on April 23, 2021:

Done

in src/wallet/wallet.cpp:2913 in 4ac1adda99 outdated

2986+                // Cost of change is the cost of creating the change output + cost of spending the change output in the future.
2987+                // For creating the change output now, we use the effective feerate.
2988+                // For spending the change output in the future, we use the discard feerate for now.
2989+                // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate)
2990+                CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
2991+                CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;

fjahr commented at 11:16 pm on April 21, 2021:

nit

0                const CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
1                const CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;

achow101 commented at 6:46 pm on April 23, 2021:

Done

in src/wallet/wallet.cpp:2958 in 4ac1adda99 outdated

3107+            if (nBytes < 0) {
3108+                error = _("Signing transaction failed");
3109+                return false;
3110+            }
3111 
3112+            CAmount fee_needed = GetMinimumFee(*this, nBytes, coin_control, &feeCalc);

fjahr commented at 11:18 pm on April 21, 2021:

nit: could be moved below this if to where it is used

achow101 commented at 6:46 pm on April 23, 2021:

This is actually in the correct spot because the if below is to handle fee estimation failure. However this line is actually incorrect because we’re supposed to be using the coin_selection_params.m_effective_feerate that we had retrieved at the top of the function. Changed it to be using that.

fjahr commented at 0:05 am on April 22, 2021: member

Looks good! Feel free to ignore my nits but I think the nFeeRet thing should be looked at.

in src/wallet/wallet.cpp:2900 in 4ac1adda99 outdated

2971-                    bnb_used = false;
2972-                }
2973+            CAmount selected_eff = 0; // selected effective value
2974+            for (const CInputCoin& coin : setCoins) {
2975+                selected_eff += coin.effective_value;
2976+            }

glozow commented at 10:43 pm on April 22, 2021:

If you retouch, this would be nice

0            // Total effective value of selected coins
1            const CAmount selected_eff = std::accumulate(setCoins.cbegin(), setCoins.cend(), 0,
2                [](CAmount sum, const auto& coin) { return sum + coin.effective_value; });

achow101 commented at 6:47 pm on April 23, 2021:

Done

in src/wallet/wallet.cpp:2949 in 4ac1adda99 outdated

2992+
2993+                // Never create dust outputs; if we would, just
2994+                // add the dust to the fee.
2995+                // When the selected_eff is within the exact match range
2996+                // (nValue + not_input_fees + cost_of_change), don't make change.
2997+                if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || selected_eff <= nValue + not_input_fees + cost_of_change)

glozow commented at 11:25 pm on April 22, 2021:

This is mostly to confirm my understanding - ?

0                // There are two cases in which we drop the change to fees:
1                // 1. The change output would be dust.
2                // 2. We found an "exact match," i.e. the difference between the total effective value of the selected
3                // coins and nTargetValue is less than or equal to the cost of the change output.
4                if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) ||
5                    selected_eff - (nValue + not_input_fees) <= cost_of_change)

achow101 commented at 6:47 pm on April 23, 2021:

Yes, that is correct. I’ve changed the comment to be similar.

glozow commented at 11:25 pm on April 22, 2021: member

Code Review ACK 4ac1adda9914d845aaea5804af4801ffec53c701

in src/wallet/coinselection.cpp:52 in da9adea998 outdated

48@@ -49,28 +49,25 @@ struct {
49  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
50  *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
51  *        values are their effective values.
52- * @param const CAmount& target_value This is the value that we want to select. It is the lower
53+ * @param const CAmount& actual_target This is the value that we want to select. It is the lower

Xekyo commented at 0:16 am on April 23, 2021:

Perhaps consider calling this selection_target or something else that ties it more strongly to the context.

Xekyo commented at 0:19 am on April 23, 2021:

Although in that case nTargetValue should perhaps also be renamed to something like selection_target_with_minchange?

achow101 commented at 6:48 pm on April 23, 2021:

Done

achow101 force-pushed on Apr 23, 2021

in src/wallet/coinselection.h:159 in 326db920e2 outdated

121     bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
122+    CAmount GetSelectionAmount() const;
123 };
124 
125-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
126+bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& actual_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);

fjahr commented at 3:29 pm on April 24, 2021:

nit: In the implementation it’s now selection_target instead of actual_target.

achow101 commented at 6:11 pm on April 29, 2021:

Done

fjahr commented at 3:49 pm on April 24, 2021: member

Code review ACK 326db920e24736581d0eb2ce555771c57101dc1b

in src/wallet/coinselection.h:147 in 326db920e2 outdated

103@@ -79,21 +104,20 @@ struct OutputGroup
104     size_t m_descendants{0};
105     CAmount effective_value{0};
106     CAmount fee{0};
107-    CFeeRate m_effective_feerate{0};
108     CAmount long_term_fee{0};
109-    CFeeRate m_long_term_feerate{0};
110+    CoinSelectionParams m_cs_params;

glozow commented at 2:26 pm on April 29, 2021:

hm, not sure how I feel about having a CoinSelectionParams in every single OutputGroup… could it just have a GetSelectionAmount(subtract_fee_outputs) or something?

achow101 commented at 6:09 pm on April 29, 2021:

Currently neither of the actual coin selection functions (which are the ones that call GetSelectionAmount are aware of subtract fee from outputs. I decided to go this route of including CoinSelectionParams in the OutputGroups because it reduces the number of parameters that we need to pass to both GroupOutputs and the OutputGroup constructor. Since the CoinSelectionParams contain the effective feerate and the long term feerate, it also makes it so that the OutputGroup does not need to track those feerates separately.

glozow commented at 7:02 pm on April 29, 2021:

But now every single COutputGroup has a copy of CoinSelectionParams (and afaik this would be the same across all COuputGroups for a coin selection). That’s a lot of extra space just for 2 feerates.

It also seems like an API violation for the groups of UTXOs to have so much extra information about coin selection (e.g. the size of change output spend). I still think callers could provide those as arguments in group.Insert(), group.GetSelectionAmount(), etc.

achow101 commented at 7:27 pm on April 29, 2021:

Making it a const CoinSelectionParams& would avoid having so many copies.

Of the 8 parameters in CoinSelectionParams, it’s an even split between the ones relevant to OutputGroups and GroupOutputs. 4 of them (m_effective_feerate, m_long_term_feerate, m_subtract_fee_outputs, and m_avoid_partial_spends) are used by GroupOutputs. I don’t think it’s that much of a layer violation. Alternatively, we can still pass in CoinSelectionParams and just copy out the parameters that we care about?

glozow commented at 8:30 pm on April 29, 2021:

Alternatively, we can still pass in CoinSelectionParams and just copy out the parameters that we care about?

This sounds like a better option to me

achow101 commented at 0:40 am on April 30, 2021:

Done

DrahtBot added the label Needs rebase on Apr 29, 2021

achow101 force-pushed on Apr 29, 2021

DrahtBot removed the label Needs rebase on Apr 29, 2021

achow101 force-pushed on Apr 30, 2021

in src/wallet/wallet.cpp:2401 in 37c717952f outdated

2403-        // When subtracting the fee from the outputs, we want the effective feerate to be 0
2404-        CFeeRate effective_feerate{0};
2405-        if (!coin_selection_params.m_subtract_fee_outputs) {
2406-            effective_feerate = coin_selection_params.m_effective_feerate;
2407-        }
2408+    // Calculate the fees for things that aren't inputs

Xekyo commented at 5:34 pm on April 30, 2021:

This could be clarified to indicate that the change output is also not included.

achow101 commented at 8:05 pm on May 6, 2021:

Done

in src/wallet/wallet.cpp:2976 in 0fb20f9c82 outdated

2972@@ -2991,10 +2973,21 @@ bool CWallet::CreateTransactionInternal(
2973                     // Fill a vout to ourself
2974                     CTxOut newTxOut(nChange, scriptChange);
2975 
2976+                    CAmount cost_of_change = 0;

Xekyo commented at 5:42 pm on April 30, 2021:

This commit’s subject indicates only that it’s removing bnb_used and use_bnb.

This update in the change creation seems to stem from doing both BnB and KS every pass. Is it possible that this part should have been in the previous commit?

achow101 commented at 8:06 pm on May 6, 2021:

No, this is supposed to be here. However it is also related to “Properly determine whether we are in the exact match range to make change”, so I’ve moved that commit to be before “Remove use_bnb and bnb_used” and combined this change with it.

in src/wallet/coinselection.cpp:52 in 5a7a8e0820 outdated

48@@ -49,28 +49,25 @@ struct {
49  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
50  *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
51  *        values are their effective values.
52- * @param const CAmount& target_value This is the value that we want to select. It is the lower
53+ * @param const CAmount& selection_target This is the value that we want to select. It is the lower

Xekyo commented at 5:48 pm on April 30, 2021:

Optional: Please mention renaming to selection_target in commit message or split into separate commit.

achow101 commented at 8:06 pm on May 6, 2021:

Changed the rename to another commit.

in src/wallet/wallet.cpp:2932 in bcaee1c0ef outdated

3002+                return false;
3003+            }
3004 
3005-                const CAmount nChange = nValueIn - nValueToSelect;
3006-                if (nChange > 0)
3007+            const CAmount nChange = input_sum - nValue;

Xekyo commented at 5:54 pm on April 30, 2021:

I was just staring at this and was wondering why nChange = input_sum - nValue until I realized that input_sum is the sum of the effective values of the inputs. That could perhaps be clarified in a comment or the variable name (e.g. inputs_effective_value).

achow101 commented at 7:55 pm on May 6, 2021:

It isn’t the sum of effective values. It is a the actual sum of input values. In this case, nChange is a bit of a misnomer as it also includes the fee that is to be paid.

in src/wallet/wallet.cpp:2888 in 041e39561a outdated

2898 
2899-                CAmount nValueToSelect = nValue;
2900-                if (nSubtractFeeFromAmount == 0)
2901-                    nValueToSelect += nFeeRet;
2902+            txNew.vin.clear();
2903+            txNew.vout.clear();

glozow commented at 1:36 pm on May 3, 2021:

In Remove CreateTransaction while loop and some related variables Are these needed anymore? txNew is created within CreateTransactionInternal() and iiuc there’s no loop iteration for it to be mutated in

achow101 commented at 8:03 pm on May 6, 2021:

Doesn’t seem like it, removed.

in src/wallet/coinselection.h:161 in 041e39561a outdated

155-        m_effective_feerate(effective_feerate),
156-        m_long_term_feerate(long_term_feerate)
157+    OutputGroup(const CoinSelectionParams& params) :
158+        m_effective_feerate(params.m_effective_feerate),
159+        m_long_term_feerate(params.m_long_term_feerate),
160+        m_subtract_fee_outputs(params.m_subtract_fee_outputs)

glozow commented at 1:50 pm on May 3, 2021:

Thanks for accepting the suggestion, I like this a lot better than OutputGroup keeping a copy of params :)

in src/wallet/wallet.cpp:2917 in 041e39561a outdated

2932-                        assert(nSubtractFeeFromAmount != 0);
2933-                        txout.nValue -= nFeeRet / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient
2934+            // Choose coins to use
2935+            CAmount input_sum = 0;
2936+            setCoins.clear();
2937+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);

glozow commented at 2:04 pm on May 3, 2021:

🐮 says moo 🐷 says oink me says

0            const int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);

achow101 commented at 8:03 pm on May 6, 2021:

Done

glozow commented at 2:08 pm on May 3, 2021: member

reACK https://github.com/bitcoin/bitcoin/pull/17331/commits/041e39561ae708712d89a3f49fd4130ec2989071 via range-diff 4ac1add...041e395 and reviewing the new changes in the last commit - I appreciate the cleanup

A few small comments that don’t need to be addressed here

in src/wallet/wallet.cpp:3039 in 041e39561a outdated

3222-                nFeeRet = nFeeNeeded;
3223-                coin_selection_params.use_bnb = false;
3224-                continue;
3225             }
3226 
3227             // Give up if change keypool ran out and change is required

glozow commented at 11:31 pm on May 3, 2021:

Is this block still needed? Seems like it exists to prevent further iterations

achow101 commented at 8:05 pm on May 6, 2021:

It is needed, but the change stuff could be consolidated to not need it. I think that cleaning this up could be done a followup.

in src/wallet/wallet.cpp:2908 in bcaee1c0ef outdated

2906+            txNew.vout.clear();
2907 
2908-                // vouts to the payees
2909+            // vouts to the payees
2910+            if (!coin_selection_params.m_subtract_fee_outputs) {
2911+                coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size)

Xekyo commented at 1:45 am on May 4, 2021:

Isn’t that just 10.75 vB?

Probably out of scope for this PR, but what do you think about these calculations using weight units in the future?

achow101 commented at 5:33 pm on May 6, 2021:

Yes, I rounded up.

We should be using weights everywhere rather than vB, but fee estimation and many other things still use vB which makes it harder to use weights.

Xekyo commented at 3:37 am on May 4, 2021: member

tACK 041e39561ae708712d89a3f49fd4130ec2989071 with some nits

Xekyo commented at 3:40 am on May 4, 2021: member

I keep making the same mistake of reviewing this commit by commit, when half the code that gets changed around actually disappears midway through the PR. Feel free to ignore these irrelevant bits. :sweat:

in src/wallet/coinselection.cpp:239 in 37c717952f outdated

236             nValueRet += group.m_value;
237             return true;
238-        } else if (group.m_value < nTargetValue + MIN_CHANGE) {
239+        } else if (group.effective_value < nTargetValue + MIN_CHANGE) {
240             applicable_groups.push_back(group);
241             nTotalLower += group.m_value;

ryanofsky commented at 10:08 am on May 6, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

Is it right to use m_value instead of effective value here? If nTargetValue and nBest here are to switched effective value instead of actual value, and these are compared against nTotalLower, shouldn’t nTotalLower be an effective value too? Assuming this code is correct, I think it would be useful to add a comment to this function explaining how it uses effective values vs literal values, now that this function is taking effective values into account.

achow101 commented at 8:07 pm on May 6, 2021:

That is correct, this should be using effective_value. Fixed.

in src/wallet/coinselection.cpp:273 in 37c717952f outdated

269@@ -270,7 +270,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
270     // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
271     //                                   or the next bigger coin is closer), return the bigger coin
272     if (lowest_larger &&
273-        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
274+        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->effective_value <= nBest)) {

ryanofsky commented at 10:19 am on May 6, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

Is KnapsackSolver solver a legacy function that is likely to be removed at some point? If not, it would be good in the future for it to have some direct test coverage (I assume it already has some indirect coverage at a higher level) where it is called directly with some basic input and checked to see it gives expected output. More comprehensive tests would take more effort and probably not worth the cost, but if there were a basic test before this commit, that had to be updated as part of this commit, this commit would be easier to understand and have confidence in.

achow101 commented at 5:40 pm on May 6, 2021:

There is some direct coverage, and some calls to SelectCoinsMinConf in the coin selector tests are changed to KnapsackSolver in future commits.

in src/wallet/wallet.cpp:2404 in 37c717952f outdated

2407-        }
2408+    // Calculate the fees for things that aren't inputs
2409+    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
2410 
2411-        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */);
2412+    // Get the feerate for effective value.

ryanofsky commented at 10:52 am on May 6, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

Now there are two effective rate variables used in the code below: effective_feerate and coin_selection_params.m_effective_feerate, and I’m confused about why each one is used different places. Can the new variable at least have a distinct name to be clear about it’s purpose? Maybe outputgroup_effective_feerate because this feerate just seems to be literally inserted in all the outputgroups and not used right away.

Again a high-level comment explaining how this function is using effective feerates would be pretty helpful, since apparently it was ignoring them previously.

achow101 commented at 5:46 pm on May 6, 2021:

effective_feerate is used to calculate the effective value. It’s value is either 0 or coin_selection_params.m_effective_feerate, depending on whether we are subtracting the fee from the outputs. This is a bit of a hack to make sure that when we are subtracting the fee from the outputs, the selection algos use the real value rather than the effective value. However, this is all moot because the last commit in this PR removes this behavior. Instead OutputGroup will know about coin_selection_params.m_subtract_fee_outputs and return either m_value or m_effective_value depending on that parameter.

in src/wallet/wallet.cpp:2424 in 37c717952f outdated

2434+        return SelectCoinsBnB(positive_groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees);
2435     } else {
2436-        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */);
2437-
2438+        // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
2439+        std::vector<OutputGroup> all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */);

ryanofsky commented at 10:58 am on May 6, 2021:

In commit “Have KnapsackSolver actually use effective values” (37c717952f6b0719392bfdddcafbf1a2db1de7ca)

So much code is just moving and being tweaked and not changing substantively. I think this commit would be easier to understand split into two parts:

1 - Refactoring only change, adding new change_fee variable, adding new comments, moving the code that needs to move. 2 - Behavior change using effective values, which should be simpler to understand with less code being moved around and cleaned up.

achow101 commented at 8:07 pm on May 6, 2021:

Split up the commit.

ryanofsky commented at 12:14 pm on May 6, 2021: member

Would be curious about the nTotalLower question below, but other than that if this PR is close to merge (I see at least 3 acks above) I don’t want to delay this, so ignore my suggestions unless they are actually worth implementing.

Started review (will update list below with progress).

37c717952f6b0719392bfdddcafbf1a2db1de7ca Have KnapsackSolver actually use effective values (1/8)
b8d0eecd8e792d9b71c898aa7780336c695377d9 Do both BnB and Knapsack coin selection in SelectCoinsMinConf (2/8)
0fb20f9c8220df6c13381117000316f3f0915c75 Remove use_bnb and bnb_used (3/8)
5a7a8e08200071ea6f7072642e70e2a243efbfef Roll not_input_fees into nValueToSelect instead of having it be separate (4/8)
bcaee1c0efe80e03ffb7fb19d3e6bbfc18d823cd Remove CreateTransaction while loop and some related variables (5/8)
c1637366f5e500eb24ea3531bf8e1292d2e77686 Properly determine whether we are in the exact match range to make change (6/8)
d3b141721078d5e97be47ac89abe47adc0c1aa8c Change SelectCoins_test to actually test SelectCoins (7/8)
041e39561ae708712d89a3f49fd4130ec2989071 Have OutputGroup determine the value to use (8/8)

achow101 force-pushed on May 6, 2021

achow101 commented at 8:08 pm on May 6, 2021: member

I’ve done a bit of commit reorganization but the final diff should not be very different.

Also, it seems that “Have KnapsackSolver actually use effective values” breaks wallet_bumpfee.py, but “Remove CreateTransaction while loop and some related variables” fixes it. I’m not sure if it is necessary to investigate the failure so that the test passes throughout.

meshcollider commented at 11:42 am on May 7, 2021: contributor

I am absolutely no expert on coin selection and I dread this code, but from what I understand, this PR looks good. I’m glad it also has more experienced eyes like those of Russ and Murch.

Light utACK d4c6e8d57f7326a3f7e762cc5e473977843fd5c7

in src/wallet/wallet.cpp:3006 in 3c7ea2233e outdated

3005+                        // Cost of change is the cost of creating the change output + cost of spending the change output in the future.
3006+                        // For creating the change output now, we use the effective feerate.
3007+                        // For spending the change output in the future, we use the discard feerate for now.
3008+                        // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate)
3009+                        const CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
3010+                        cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;

ryanofsky commented at 7:35 pm on May 7, 2021:

In commit “Determine whether we are in the exact match range to make change” (3c7ea2233ed1bf1075a9ee19071381298b021f74)

Note: “Cost of change” comments and code here duplicates code in SelectCoinsMinConf (grep “Cost of change is the cost”) so might be good to dedup later with a cost of change function.

achow101 commented at 6:57 am on May 8, 2021:

I’ve deduplicated this code by adding m_cost_of_change to CoinSelectionParams.

in src/wallet/wallet.cpp:3011 in 3c7ea2233e outdated

3010+                        cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee;
3011+                    }
3012+
3013+                    // We want to drop the change to fees if:
3014+                    // 1. The change output would be dust
3015+                    // 2. The "change" is within the (almost) exact match window, i.e. the difference between the selected effective value

ryanofsky commented at 7:41 pm on May 7, 2021:

In commit “Determine whether we are in the exact match range to make change” (3c7ea2233ed1bf1075a9ee19071381298b021f74)

I don’t understand “change” in quotes here. Is this referring to the nChange = nValueIn - nValueToSelect variable, which is not really the final change but a combination of change and fees? It would be good to clarify what is meant in this comment either way. Could also rename “nChange” to “surplus” or “change_plus_fees” or “inputs_minus_outputs” or something to make the old name less misleading in a new commit.

achow101 commented at 8:38 pm on May 7, 2021:

Yes, I put it in quotes because it’s really change + fees.

in src/wallet/wallet.cpp:3013 in 3c7ea2233e outdated

3012+
3013+                    // We want to drop the change to fees if:
3014+                    // 1. The change output would be dust
3015+                    // 2. The "change" is within the (almost) exact match window, i.e. the difference between the selected effective value
3016+                    //    and the selection target (nValue + not_input_fees) is less than or equal to the cost of the change output (cost_of_change)
3017+                    if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || selected_eff <= nValue + not_input_fees + cost_of_change)

ryanofsky commented at 7:49 pm on May 7, 2021:

In commit “Determine whether we are in the exact match range to make change” (3c7ea2233ed1bf1075a9ee19071381298b021f74)

Note: I would have expected just || nChange <= cost_of_change as the second condition, but IIUC, this wouldn’t work because nChange isn’t really the change value but the (change + fees) value. So this is instead estimating the change output value as ((value of inputs minus effective fees) minus (value of outputs minus effective fees)), and then seeing if that change output value would be worth the cost of the output & spend.

achow101 commented at 7:16 am on May 8, 2021:

I’ve moved this to be after fee reduction, so it makes more sense now with just comparing to the cost of change directly.

in src/wallet/wallet.cpp:2957 in 6bd07ddff8 outdated

2952@@ -2956,6 +2953,9 @@ bool CWallet::CreateTransactionInternal(
2953                     txNew.vout.push_back(txout);
2954                 }
2955 
2956+                // Calculate the fees for things that aren't inputs, excluding the change output
2957+                const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

ryanofsky commented at 8:09 pm on May 7, 2021:

In commit “Roll not_input_fees into nValueToSelect instead of having it be separate” (6bd07ddff8c092ac57fc72e47510c73864ac7acc)

Not necessarily relevant to this commit, but there is a big block of code above that just seems to be filling the coin_selection_params struct. It could be good for a future cleanup to move that code into a function to be able to shrink this function and declare coin_selection_params as const

ryanofsky commented at 8:15 pm on May 7, 2021: member

Mostly finished in progress review (will update list below). First few commits are 😍 really nicely done. But the “CreateTransaction while loop” commit is breaking my brain, and I am going to stop and go running to see if more oxygen will help. Or less oxygen will help. Or less oxygen minus the discard rate plus the subtract from recipient change position is good.

Again, one thing that might clarify that commit could be to do the minor code cleanups like adding consts, renaming variables nValueIn/input_sum nFeeNeeded/fee_needed in separate commits. But the main thing I am not conceptually understanding about the new code is how it now is possible to decide whether or not to drop the change output /before/ handing fSubtractFeeFromAmount. How could you know whether dropping the output is economical before knowing how big the output will be? Anyway, I assume I’m just missing things and will try again.

c1c2164ae19e5c919f90a6e9931124d4000a51e7 Move some calculations to common code in SelectCoinsMinConf (1/10)
33eb3fcf63928f8852b9ec8623632c60c361ebac Have KnapsackSolver actually use effective values (2/10)
83fddb7ecb5e56b25021ca4a7099a811bbeb224d Do both BnB and Knapsack coin selection in SelectCoinsMinConf (3/10)
6e5ca674770bfbce6eaa333191e8a3f9da4cac91 scripted-diff: rename actual_target to selection_target (4/10)
6bd07ddff8c092ac57fc72e47510c73864ac7acc Roll not_input_fees into nValueToSelect instead of having it be separate (5/10)
3c7ea2233ed1bf1075a9ee19071381298b021f74 Determine whether we are in the exact match range to make change (6/10)
df5870c6d34697e3a0d66937b1bb7e70ae196679 Remove use_bnb and bnb_used (7/10)
69991df82f00e7b1a415c85e930645458dcf6266 Remove CreateTransaction while loop and some related variables (8/10)
0082b6bdf6d912b09001525cddbb6cbacea13e34 Change SelectCoins_test to actually test SelectCoins (9/10)
d4c6e8d57f7326a3f7e762cc5e473977843fd5c7 Have OutputGroup determine the value to use (10/10)

SomethingUseful commented at 9:59 pm on May 7, 2021: none

we were running this PR as bitcoin-0.21.0-patch. We upgraded to 0.21.1 and after few days were having failed transactions again so we had to roll back to this patch version again.

achow101 force-pushed on May 8, 2021

achow101 commented at 7:04 am on May 8, 2021: member

But the main thing I am not conceptually understanding about the new code is how it now is possible to decide whether or not to drop the change output /before/ handing fSubtractFeeFromAmount. How could you know whether dropping the output is economical before knowing how big the output will be? Anyway, I assume I’m just missing things and will try again.

That is indeed an issue. I’ve reworked this behavior. Now we will always try to make a change output, and then reduce it’s value to deal with the transaction fees. This should be easier to understand as all of fee setting is consolidated in a single chunk of code.

I’ve also done another bit of commit reorganization to try to reduce the number of commits that fail tests.

achow101 force-pushed on May 8, 2021

in src/wallet/wallet.cpp:2985 in 79ef774476 outdated

2981@@ -2982,15 +2982,15 @@ bool CWallet::CreateTransactionInternal(
2982                     bnb_used = false;
2983                 }
2984 
2985-                const CAmount nChange = nValueIn - nValueToSelect;
2986-                if (nChange > 0)
2987+                const CAmount change_and_fee = nValueIn - nValueToSelect;

ryanofsky commented at 5:51 pm on May 11, 2021:

In commit “scripted-diff: rename some variables” (79ef77447615067e30ee476343ca8816559869a3)

This commit doesn’t compile

wallet/wallet.cpp:2997:36: error: use of undeclared identifier ’nChange’ nFeeRet += nChange;

achow101 commented at 9:34 pm on May 12, 2021:

Fixed.

in src/wallet/wallet.cpp:2418 in 19ccc6401c outdated

2415         // The knapsack solver currently does not use effective values, so we give GroupOutputs feerates of 0 so it sets the effective values to be the same as the real value.
2416         std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */);
2417 
2418         bnb_used = false;
2419-        return KnapsackSolver(nTargetValue, groups, setCoinsRet, nValueRet);
2420+        return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, groups, setCoinsRet, nValueRet);

ryanofsky commented at 6:38 pm on May 11, 2021:

In commit “Roll not_input_fees into nValueToSelect instead of having it be separate” (19ccc6401c8d854815727522949242d3ad343c73)

What’s the reason for adding m_change_fee here? Can there be a code comment saying why the selection amount + change cost sum is used as target for knapsack but not bnb, and maybe a commit message note saying whether commit is intended to change behavior. I notice in earlier versions of the PR, adding this was part of a different “Do both BnB and Knapsack coin selection in SelectCoinsMinConf” commit, but I’m actually not sure how this change fit in that commit either:

b8d0eecd8e792d9b71c898aa7780336c695377d9 Apr 29 Do both BnB and Knapsack, adds change fee 83fddb7ecb5e56b25021ca4a7099a811bbeb224d May 6 Do both BnB and Knapsack, adds change fee d516f82b187a19b9943957eb56eed93664050ed2 May 8 Do both BnB and Knapsack, change fee already added

ryanofsky commented at 6:45 pm on May 13, 2021:

In commit “Roll not_input_fees into nValueToSelect instead of having it be separate” (534917d11c12a713b39708290f51f495f370a66d)

Thanks for new code comments, very helpful. IIUC. I’m still a little surprised to see this change here in this commit, instead of in it’s own commit or in the “Have KnapsackSolver actually use effective values” commit. Everything else in this commit is not a change in behavior, but this one change passing a higher target to KnapsackSolver is a change in behavior? If this is the case, it would be nice to split this up into two commits, or alternately say how the two different parts of this change are dependent in the commit message.

I’m also curious about tradeoffs with the new behavior. This is probably just my ignorance, but I don’t know if it is strictly better to target the change cost, or if there are there expected cases where targeting no-change cost would be better. Would be nice to be able to understand more of this background thinking from the code comment or commit message.

achow101 commented at 7:19 pm on May 13, 2021:

Our assumption is that KnapsackSolver will always find a result that has change as BnB will find any that do not have change. I’ve updated the commit message.

ryanofsky commented at 8:01 pm on May 13, 2021:

In commit “Roll static tx fees into nValueToSelect instead of having it be separate” (a8b689bf239df610627337531b3722711a571068)

Thanks for new commit message. Just will say what my understanding is:

1 - The first change in this commit rolling BnB not_input_fees into nTargetValue is not a change in behavior, just a pure refactoring 2 - The second change in this commit rolling knapsack change cost into nTargetValue is a change in behavior that should result better coin selection 3 - Neither of the two changes is dependent on the other, they’re just related thematically

Could be nice to mention these things in the commit message, but it’s already pretty good and I’m just writing in case I need to be reminded later or need to be corrected if I’m wrong.

Also if the code comment here said there’s is no downside to assuming there will be a change output since the bnb call above would find a changeless solution, I would personally like that and find it helpful, but I could also see it being too verbose / basic for other readers so :shrug:

in src/wallet/coinselection.cpp:340 in 282ee37b64 outdated

335@@ -336,3 +336,8 @@ bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_f
336         && m_ancestors <= eligibility_filter.max_ancestors
337         && m_descendants <= eligibility_filter.max_descendants;
338 }
339+
340+CAmount OutputGroup::GetSelectionAmount() const

ryanofsky commented at 10:06 pm on May 11, 2021:

In commit “Have OutputGroup determine the value to use” (282ee37b64d581dc22e2e9743d442f9acd67b4b3)

I think it’s a minor bug (or at least an unmentioned change in behavior) that there are still two effective_value member uses when all other uses are switched to selection amounts. This commit and final code would be easier to understand if all output group effective value uses were replaced with selection amounts. The two uses I think should be updated are:

https://github.com/bitcoin/bitcoin/blob/282ee37b64d581dc22e2e9743d442f9acd67b4b3/src/wallet/wallet.cpp#L4248 https://github.com/bitcoin/bitcoin/blob/282ee37b64d581dc22e2e9743d442f9acd67b4b3/src/wallet/wallet.cpp#L4307

It would be more understandable to consistently use not effective values for subtract-from-recipients, instead of having effective values leak in for them now in these corner cases.

achow101 commented at 9:34 pm on May 12, 2021:

Done.

in src/wallet/wallet.cpp:3061 in 6f36603f64 outdated

3020-                        if (nFeeRet >= fee_needed_with_change + minimum_value_for_change) {
3021-                            pick_new_inputs = false;
3022-                            nFeeRet = fee_needed_with_change;
3023-                            continue;
3024-                        }
3025-                    }

ryanofsky commented at 10:44 pm on May 11, 2021:

In commit “Move output reductions for fee to after coin selection” (6f36603f64246c8cd274a532df222ab0414d651b)

I’m really confused by this block of removed code, which was introduced in #10712 https://github.com/bitcoin/bitcoin/pull/10712/commits/0f402b9263b0579b29aa0f841fc64ad58d3efba6 (and which I apparently reviewed years ago). I don’t understand how the code was functioning when it added, or why it is safe to remove now. It seems like when the code was added, it would never trigger because if the selected coins were ever high enough to merit adding a change output, nChangePosInOut would already not be -1 and the new condition would never trigger:

https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2683 https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2766

I guess it seems safe to drop this code, but it would be nice to understand what it’s doing while it’s here.

achow101 commented at 9:11 pm on May 12, 2021:

This code is needed because of the looping behavior. As we are removing that loop, it is no longer needed.

As for why this was needed, suppose in one iteration of the loop, we choose a lot of small inputs. This will require a higher transaction fee. If those inputs are not enough to cover the fee that they need, we iterate again. In the next iteration, we find that with the increased target, we need only a few large inputs. This thus requires a lower transaction fee than the previous iteration. Since in this second iteration we have selected enough inputs to cover the transaction, we would exit the loop. But because we have used the previous iteration to set the fee, we are actually overpaying the fees for this input set. So this code was added to add a change output and reduce the fee to just the necessary amount in this scenario.

ryanofsky commented at 10:01 pm on May 12, 2021:

re: #17331 (review)

As for why this was needed, suppose in one iteration of the loop, we choose a lot of small inputs. […]

Sorry, I understood why change output boosting is needed. The code I was asking about was the code from 0f402b9263b0579b29aa0f841fc64ad58d3efba6 in #10712 and now removed here which tried to add a change output late in the loop. I don’t see any case it would trigger because the change output would already be added earlier in the loop.

https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2683 https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2766

This is all after coin selection.

achow101 commented at 10:09 pm on May 12, 2021:

It’s change boosting but in the case where we don’t have change.

It’s the same scenario as change boosting, but instead of having selected more than enough to cover the fees from the previous iteration, we have selected exactly enough to cover those fees. But in this second iteration, there are fewer inputs, so fewer fees, so we need to add a change output because there is no existing change to boost.

ryanofsky commented at 5:53 pm on May 13, 2021:

It’s change boosting but in the case where we don’t have change.

It’s the same scenario as change boosting, but instead of having selected more than enough to cover the fees from the previous iteration, we have selected exactly enough to cover those fees. But in this second iteration, there are fewer inputs, so fewer fees, so we need to add a change output because there is no existing change to boost.

I keep linking to line 2683: https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2683

Because in every case where the code below it (line 2766) would seemingly need to add a change output, it seems like this line would already have added it. This line happens after selecting coins in the same iteration of the while loop. My only understanding (which makes no sense) is that the code is selecting coins, seeing if a change output needs to be added, then adding it on line 2683. Then seeing if a change output needs to be added again on line 2766, but this code can never trigger because the change output should be already added.

If the code added in 0f402b9263b0579b29aa0f841fc64ad58d3efba6 is just nonsense that doesn’t do anything, then it should be safe to drop. And it could be safe to drop anyway. Everything else in this PR looks good, just these CreateTransactionInternal changes are still pretty opaque to me.

achow101 commented at 6:34 pm on May 13, 2021:

I think the key thing in understanding this code is that nChange (now named change_and_fee) was actually supposed to just be the change. nValueToSelect includes the nFeeRet from the previous iteration. So we could have nChange == 0 if we select exactly enough to cover the recipient amount + previous nFeeRet. That would cause this code to trigger.

ryanofsky commented at 7:35 pm on May 13, 2021:

Oh, wow. I guess I was looking at the new code first where nChange means input exceeding originally requested output, or change+fees. But in the current code as long as nValueToSelect still contains fees, then nChange will just be pure change:

https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2620 https://github.com/bitcoin/bitcoin/blob/0f402b9263b0579b29aa0f841fc64ad58d3efba6/src/wallet/wallet.cpp#L2664

So nChange could be 0 even if the final fee turned out to be a significantly less than the originally estimated fee, and the change output would not be added on the first pass.

I guess now the thing I don’t understand is why commit “Move output reductions for fee to after coin selection” (234f85c44042d6566b7cf7e1bf1b969b2e38f903) is safe before commit “Remove CreateTransaction while loop and some related variables” (1f2cf3cf180a5928171729ce92324952cb172d9f) because it seems like the change output could still be missing until after the nValueToSelect += nFeeRet; line is dropped or no longer doing anything, resulting either in excessive fees paid again or just a failure (forgot details of the part below already….)

achow101 commented at 8:26 pm on May 13, 2021:

Indeed, this commit fails the tests and doesn’t quite work. However in the end, it all does work. I have tried to fix it, but it seems like it will end up just adding a bunch of code that gets removed in a later commit. I don’t think there’s a way to reorder commits to make this work.

in src/wallet/wallet.cpp:3044 in 6f36603f64 outdated

3091+                        {
3092+                            nChangePosInOut = -1;
3093+                            nFeeRet += change_position->nValue;
3094+                            // We need to reduce the amount to subtract from the recipients so they don't overpay
3095+                            // as dropping the change accounts for some fees.
3096+                            to_reduce = change_position->nValue;

ryanofsky commented at 2:06 am on May 12, 2021:

In commit “Move output reductions for fee to after coin selection” (6f36603f64246c8cd274a532df222ab0414d651b)

It seems like in subtract-fee-from-recipients case when change output is too small to be economical it would make more sense to send the savings back to recipients, instead of paying extra in fees. So I would expect this to say something like:

0nChangePosInOut = -1;
1to_reduce -= change_position->nValue;

(EDIT: Suggestion above originally had an extra line “nFeeRet -= change_position->nValue;” that wasn’t right. Simple example to think about would be a $5 subtract-from-recipient transaction with $5.25 input, and a $1 fee, and no change output. nFeeRet should stay $1 in this case, and to_reduce should be $0.75 so output value is $5 - $0.75 = $4.25)

But if you did want to send the dust change amount to the miner instead of recipient, I’d expect this to just say

0nChangePosInOut = -1;
1nFeeRet += change_position->nValue;

without changing to_reduce at all. Saying “to_reduce = change_position->nValue” seems like a bug and makes me wonder if there is test coverage for this stuff.

Also, this dust checking code is identical between the subtract and non-subtract branches and could be factored out or moved above (could also be a later cleanup):

0std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
1if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_position->nValue <= coin_selection_params.m_cost_of_change)
2{
3    nChangePosInOut = -1;

~~Also the to_reduce variable seems unnecessary, just a local duplicate of nFeeRet~~ (EDIT: This was wrong, to_reduce is different from the fee).

achow101 commented at 9:35 pm on May 12, 2021:

Yes, there is a bug here. Removed changing nFeeRet and fixed the to_reduce calculation.

Indeed, this is supposed to be a discount to the recipients, so it was supposed to be -=. Because this will cause to_reduce and nFeeRet to deviate, it is necessary for to_reduce to exist. Otherwise nFeeRet will misreport the actual transaction fee for this transaction.

in src/wallet/wallet.cpp:2932 in 6f36603f64 outdated

2931@@ -2935,33 +2932,14 @@ bool CWallet::CreateTransactionInternal(
2932                 {
2933                     CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
2934 
2935-                    if (recipient.fSubtractFeeFromAmount)

ryanofsky commented at 6:37 pm on May 12, 2021:

In commit “Move output reductions for fee to after coin selection” (6f36603f64246c8cd274a532df222ab0414d651b)

Now that SelectCoins accounts for the transaction fees, it is now possible to reduce the outputs to deal with the transaction fees after the SelectCoins.

This commit message seems incorrect, or at least it is hard to understand. As far as I can see in 6f36603f64246c8cd274a532df222ab0414d651b SelectCoins is not actually accounting for transaction fees yet, that happens later in commit “Have KnapsackSolver actually use effective values” (fe760f2411c3486f0f370e2f0ff3c834e9e0cd23). But anyway even before this commit, the recipient output reduction would only take place after SelectCoins because it would happen after the first loop iteration https://github.com/bitcoin/bitcoin/blob/d9ae6ec8929e739187740baab206daa55cde61d1/src/wallet/wallet.cpp#L3085-L3089

It seems like a commit description more closely matching the change might be:

“Simplify CreateTransactionInternal without changing behavior. Avoid need for second pick_new_inputs = false loop iteration in the subtract-fee-from-amount case, by moving the subtract-fee-from-amount implementation later in the while loop where it is possible to calculate and subtract the needed fee within a single iteration, instead of calculating the fee the first iteration, and then subtracting the fee the second iteration. Also, avoid the need for a second pick_new_inputs = false loop iteration in a different and rarer case where nSubtractFeeFromAmount == 0 and an extra loop iteration was introduced to add a missing change output to avoid paying excessive fees. This case was added in #10712 https://github.com/bitcoin/bitcoin/pull/10712/commits/0f402b9263b0579b29aa0f841fc64ad58d3efba6, but is no longer needed because ___.”

achow101 commented at 9:36 pm on May 12, 2021:

Updated the commit message to explain this more.

ryanofsky commented at 8:16 pm on May 12, 2021: member

Coming close to a good understanding of this PR after staring too much at this. Left some questions and feedbacks.

79ef77447615067e30ee476343ca8816559869a3 scripted-diff: rename some variables (1/11)
2b9bcef9a0b7dd9ecb9290fbf274429060e39e95 Move some calculations to common code in SelectCoinsMinConf (2/11)
770924c57336486fe80ffff4b421084bd5efddbd Make cost_of_change part of CoinSelectionParams (3/11)
19ccc6401c8d854815727522949242d3ad343c73 Roll not_input_fees into nValueToSelect instead of having it be separate (4/11)
6f36603f64246c8cd274a532df222ab0414d651b Move output reductions for fee to after coin selection (5/11)
fe760f2411c3486f0f370e2f0ff3c834e9e0cd23 Have KnapsackSolver actually use effective values (6/11)
d516f82b187a19b9943957eb56eed93664050ed2 Do both BnB and Knapsack coin selection in SelectCoinsMinConf (7/11)
9c994b6e5211ff0b52977de8182017b16ab6a6ad Remove use_bnb and bnb_used (8/11)
502931bb11409f7d5f91ec13bcdcf4317e8cde77 Remove CreateTransaction while loop and some related variables (9/11)
14db25c17e5d1eaf1e7182f5667308a0fae1fa4b Change SelectCoins_test to actually test SelectCoins (10/11)
282ee37b64d581dc22e2e9743d442f9acd67b4b3 Have OutputGroup determine the value to use (11/11)

achow101 force-pushed on May 12, 2021

ryanofsky commented at 6:57 pm on May 13, 2021: member

This is all looks good, safe, and correct to me except the two CreateTransactionInternal commits which I probably just am not understanding well enough. Would ACK everything else though.

7220a78ce64d65cf5f3cfd073f3556efec82671d scripted-diff: rename some variables (1/11)
f3605e9f89b236bfc7f3d5d9d137e4ba55069577 Move some calculations to common code in SelectCoinsMinConf (2/11)
f52c9ded0c426cec4cf084704e2ddf3895205735 Make cost_of_change part of CoinSelectionParams (3/11)
534917d11c12a713b39708290f51f495f370a66d Roll not_input_fees into nValueToSelect instead of having it be separate (4/11)
234f85c44042d6566b7cf7e1bf1b969b2e38f903 Move output reductions for fee to after coin selection (5/11)
b5f646d02defdc9e29ee33070fffa64a58d18e8a Have KnapsackSolver actually use effective values (6/11)
759419f94ec7a88010995bbf8b575fafefdfb29b Do both BnB and Knapsack coin selection in SelectCoinsMinConf (7/11)
4be8193b35839f12d7a42601f2c2a3e27f079b07 Remove use_bnb and bnb_used (8/11)
1f2cf3cf180a5928171729ce92324952cb172d9f Remove CreateTransaction while loop and some related variables (9/11)
35d358d52b9123836a80967219b6e372a8ee8e11 Change SelectCoins_test to actually test SelectCoins (10/11)
ff62a22aea843ad5ad4ccbbdbd1337f07590cc42 Have OutputGroup determine the value to use (11/11)

achow101 force-pushed on May 13, 2021

scripted-diff: rename some variables

actual_target -> selection_target
nChange -> change_and_fee

-BEGIN VERIFY SCRIPT-
sed -i -e 's/actual_target/selection_target/g' src/wallet/coinselection.cpp
sed -i -e '2801,3691s/nChange /change_and_fee /g' src/wallet/wallet.cpp
sed -i -e '2801,3691s/nChange,/change_and_fee,/g' src/wallet/wallet.cpp
sed -i -e '2801,3691s/nChange;/change_and_fee;/g' src/wallet/wallet.cpp
-END VERIFY SCRIPT-

1bf4a62cb6

Move some calculations to common code in SelectCoinsMinConf

To prepare for KnapsackSolver to use effective values, these
calculations are moved out of the BnB if block to allow for them to be
shared with KnapsackSolver in the future.

af5867c896

Make cost_of_change part of CoinSelectionParams d97d25d950

achow101 commented at 8:50 pm on May 13, 2021: member

Rebased for a silent merge conflict.

achow101 force-pushed on May 13, 2021

achow101 force-pushed on May 14, 2021

achow101 commented at 6:38 pm on May 14, 2021: member

Since the fee deduction logic was still a bit confusing, I’ve slightly reworked it again. The latest change should be much easier to comprehend. There was a minor commit reordering too which allows all of the commits to pass the tests too. This should be the final major revision to this PR.

in src/wallet/wallet.cpp:4246 in 57590fba00 outdated

4242@@ -4250,12 +4243,12 @@ bool CWalletTx::IsImmatureCoinBase() const
4243     return GetBlocksToMaturity() > 0;
4244 }
4245 
4246-std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, bool separate_coins, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const
4247+std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, const CoinSelectionParams& cs_params, const CoinEligibilityFilter& filter, bool positive_only) const

fjahr commented at 9:43 pm on May 15, 2021:

nit: I would prefer if we could reserve cs_ for the typical use in mutex names.

achow101 commented at 7:42 pm on May 19, 2021:

Renamed to coin_sel_params.

in src/wallet/wallet.cpp:2944 in 57590fba00 outdated

3012-                            return false;
3013-                        }
3014+            const CAmount change_and_fee = input_sum - nValue;
3015+            assert(change_and_fee >= 0);
3016+            // Fill a vout to ourself
3017+            CTxOut newTxOut(change_and_fee, scriptChange);

fjahr commented at 11:41 pm on May 15, 2021:

I think this could use a comment on why it’s ok that we might add a dust change here.

achow101 commented at 7:42 pm on May 19, 2021:

Done

in src/wallet/wallet.cpp:2982 in 57590fba00 outdated

3050+                std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
3051+                change_position->nValue -= nFeeRet;
3052+
3053+                if (change_position->nValue < 0) {
3054+                    // Maybe the change value was just enough to cover the fee if we did not have change in this transaction
3055+                    // Let's try dropping the change, recalculating the fee, and comparing the new fee to change_and_Fee

fjahr commented at 12:07 pm on May 16, 2021:

nit

0                    // Let's try dropping the change, recalculating the fee, and comparing the new fee to change_and_fee

achow101 commented at 7:42 pm on May 19, 2021:

This comment was removed/rewritten.

in src/wallet/wallet.cpp:2977 in 57590fba00 outdated

3045+
3046+            nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
3047+            // Try to reduce change to include necessary fee
3048+            if (nSubtractFeeFromAmount == 0) {
3049+                assert(nChangePosInOut != -1);
3050+                std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;

fjahr commented at 1:10 pm on May 16, 2021:

I think you could use position here instead of getting the iterator again. Same below in the else block.

achow101 commented at 7:43 pm on May 19, 2021:

I’m not sure how safe it is to use an iterator after modifying the vector with an insert afterwards. But because insert returns an iterator pointing to the inserted element, I’ve changed this so that change_position is set by the insert.

fjahr commented at 3:32 pm on May 16, 2021: member

Code review ACK 57590fba000c875ebc680b27ce37ceb99c7433fb

Did a fresh review of all the changes. There is room for follow-ups of course but I think this is a good step forward. So feel free to ignore my comments unless you have to retouch.

in src/wallet/wallet.cpp:3003 in 2b445b7c13 outdated

3009-                } else {
3010-                    bnb_used = false;
3011                 }
3012 
3013-                const CAmount change_and_fee = nValueIn - nValueToSelect;
3014-                if (change_and_fee > 0)

ryanofsky commented at 3:53 pm on May 18, 2021:

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

Reminder / note to anyone looking at this: this commit is easier to review ignoring whitespace.

in src/wallet/wallet.cpp:3106 in 2b445b7c13 outdated

3155-
3156-                // Include more fee and try again.
3157-                nFeeRet = nFeeNeeded;
3158-                coin_selection_params.use_bnb = false;
3159-                continue;
3160+                assert(false); // It shouldn't be possible to reach this

ryanofsky commented at 6:52 pm on May 18, 2021:

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

EDIT: Never mind this suggestion, later loop removing commit makes this better.

~~Minor style suggestion. Would be a little clearer to replace~~

0if (nSubtractFeeFromAmount == 0) {
1    ...
2} else if (nSubtractFeeFromAmount != 0) {
3    ...
4} else {
5    assert(false); // It shouldn't be possible to reach this
6}

~~with~~

0if (nSubtractFeeFromAmount == 0) {
1    ...
2} else {
3   assert (nSubtractFeeFromAmount != 0);
4   ...
5}

in src/wallet/wallet.cpp:3056 in 2b445b7c13 outdated

3086+                // Reduce output values for subtractFeeFromAmount
3087+                else if (nSubtractFeeFromAmount != 0) {
3088+                    int i = 0;
3089+                    bool fFirst = true;
3090+                    CAmount to_reduce = nFeeRet;
3091+                    if (nChangePosInOut != -1) {

ryanofsky commented at 6:57 pm on May 18, 2021:

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

This condition should always be true so this could be an assert

in src/wallet/wallet.cpp:3027 in 2b445b7c13 outdated

3042+                        tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
3043+                        nBytes = tx_sizes.first;
3044+                        nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
3045+                        if (nFeeRet <= change_and_fee) {
3046+                            // Dropping the change value puts us exactly at the value, so we can exit now
3047+                            break;

ryanofsky commented at 7:04 pm on May 18, 2021:

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

It seems like this should say:

0if (nFeeRet <= change_and_fee) {
1   nFeeRet = change_and_fee;
2   break;
3}

to handle the nFeeRet <= change_and_fee case and more accurately return the amount of fee paid without the change output.

in src/wallet/wallet.cpp:3024 in 2b445b7c13 outdated

3039+                        nChangePosInOut = -1;
3040+                        txNew.vout.erase(change_position);
3041+
3042+                        tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
3043+                        nBytes = tx_sizes.first;
3044+                        nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);

ryanofsky commented at 7:12 pm on May 18, 2021:

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

Just a code simplifcation suggestion, but it seems like instead of introducing an orig_fee variable and reducing nFeeRet and then reassigning nFeeRet back to orig_fee, it would be simpler to drop orig_fee and just say:

0CAmount required_fee = coin_selection_params.m_effective_feerate.GetFee(nBytes);
1if (required_fee < change_and_fee) {
2   nFeeRet = required_fee; // or maybe = change_and_fee, see other comment below
3   break;
4}

ryanofsky commented at 7:56 pm on May 18, 2021: member

Thanks for updates, new changes & comments so far seem very helpful. I am still grinding through the new changes but posting some initial comments for now and will keep at this.

1bf4a62cb61bd4b91d9cd4e379fea2b914786342 scripted-diff: rename some variables (1/11)
af5867c89688b06173b295b7c32a42845ea455da Move some calculations to common code in SelectCoinsMinConf (2/11)
d97d25d95006725e705635530b27643363d6b2a4 Make cost_of_change part of CoinSelectionParams (3/11)
2b445b7c1336506d43874a7ee31f85f511cd3114 Move output reductions for fee to after coin selection (4/11)
67fc8b7be1d5fbdb199d6e995434431a7282d446 Roll static tx fees into nValueToSelect instead of having it be separate (5/11)
a07552b94fe05651970e53813ae67606692d6f19 Have KnapsackSolver actually use effective values (6/11)
9428105a7af6a769e5dda53df97304c3ff2587de Do both BnB and Knapsack coin selection in SelectCoinsMinConf (7/11)
960ef2c01fcb00f718f2faaac2fd2ee94efd17c5 Remove use_bnb and bnb_used (8/11)
e30a30bcf0945acef0cc33a8c275e5ecdefa0c1f Remove CreateTransaction while loop and some related variables (9/11)
c42cf62b61b4602d10d94b31a48d8495af6b0b3e Change SelectCoins_test to actually test SelectCoins (10/11)
57590fba000c875ebc680b27ce37ceb99c7433fb Have OutputGroup determine the value to use (11/11)

ryanofsky commented at 1:31 pm on May 19, 2021: member

In commit “Move output reductions for fee to after coin selection” (2b445b7c1336506d43874a7ee31f85f511cd3114)

I was experimenting with some of the simplifications I suggested earlier and make the following changes on top of 2b445b7c1336506d43874a7ee31f85f511cd3114 to remove duplicate logic and make the code shorter. I think it’s more readable, but obviously that’s subjective.

  0diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
  1index fcf6fd00d7c..33c866d1186 100644
  2--- a/src/wallet/wallet.cpp
  3+++ b/src/wallet/wallet.cpp
  4@@ -3007,71 +3007,42 @@ bool CWallet::CreateTransactionInternal(
  5 
  6                 nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
  7                 // Try to reduce change to include necessary fee
  8+
  9+                assert(nChangePosInOut != -1);
 10+                std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
 11+
 12+                // Subtract fee from the change output if not subtracting it from recipient outputs
 13+                CAmount fee_needed = nFeeRet;
 14                 if (nSubtractFeeFromAmount == 0) {
 15-                    assert(nChangePosInOut != -1);
 16-                    std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
 17-                    change_position->nValue -= nFeeRet;
 18-
 19-                    if (change_position->nValue < 0) {
 20-                        CAmount orig_fee = nFeeRet;
 21-                        // Maybe the change value was just enough to cover the fee if we did not have change in this transaction
 22-                        // Let's try dropping the change, recalculating the fee, and comparing the new fee to change_and_Fee
 23-                        nChangePosInOut = -1;
 24-                        txNew.vout.erase(change_position);
 25-
 26-                        tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
 27-                        nBytes = tx_sizes.first;
 28-                        nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 29-                        if (nFeeRet <= change_and_fee) {
 30-                            // Dropping the change value puts us exactly at the value, so we can exit now
 31-                            break;
 32-                        }
 33-
 34-                        // The change value was not enough to cover the fees, even after dropping the change
 35-                        // We set nFeeRet back to its original value (the one that includes the change output) and try selecting again
 36-                        assert(change_and_fee < nFeeRet);
 37-                        nFeeRet = orig_fee;
 38-                        continue;
 39-                    }
 40-
 41-                    // The change value was enough to cover the fees. We may want to drop it to fees if it is too small,
 42-                    // or try selecting again if we don't meet the minimum change requirement
 43-
 44-                    // We want to drop the change to fees if:
 45-                    // 1. The change output would be dust
 46-                    // 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)
 47-                    if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_position->nValue <= coin_selection_params.m_cost_of_change)
 48-                    {
 49-                        nFeeRet += change_position->nValue;
 50-                        nChangePosInOut = -1;
 51-                        txNew.vout.erase(change_position);
 52-                    }
 53-                    break; // Fee requirements were met
 54+                    change_position->nValue -= fee_needed;
 55                 }
 56+
 57+                // We want to drop the change output if:
 58+                // 1. The change output would be dust
 59+                // 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)
 60+                CAmount change_amount = change_position->nValue;
 61+                if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change) {
 62+                    nChangePosInOut = -1;
 63+                    txNew.vout.erase(change_position);
 64+                    change_amount = 0;
 65+
 66+                    // Because we have dropped this change, our tx size and required fee will be different. So let's recalculate those.
 67+                    tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
 68+                    nBytes = tx_sizes.first;
 69+                    fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 70+                }
 71+
 72+                // Break if fee is covered and no need to loop or subtract from recipients.
 73+                if (fee_needed <= change_and_fee - change_amount) {
 74+                    nFeeRet = change_and_fee - change_amount;
 75+                    break;
 76+                }
 77+
 78                 // Reduce output values for subtractFeeFromAmount
 79-                else if (nSubtractFeeFromAmount != 0) {
 80+                if (nSubtractFeeFromAmount != 0) {
 81+                    CAmount to_reduce = fee_needed + change_amount - change_and_fee;
 82                     int i = 0;
 83                     bool fFirst = true;
 84-                    CAmount to_reduce = nFeeRet;
 85-                    if (nChangePosInOut != -1) {
 86-                        // Although we aren't going to reduce this change output to handle the transaction fees,
 87-                        // we still want to check if we would drop it to fees
 88-                        std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
 89-                        if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_position->nValue <= coin_selection_params.m_cost_of_change)
 90-                        {
 91-                            nChangePosInOut = -1;
 92-                            txNew.vout.erase(change_position);
 93-
 94-                            // Because we have dropped this change, our tx size and required fee will be different. So let's recalculate those.
 95-                            tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
 96-                            nBytes = tx_sizes.first;
 97-                            to_reduce = nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 98-
 99-                            // Furthermore, because we have dropped the change value, that will be part of the fee.
100-                            // We give this back to the recipients as a discount to the amount that is being reduced from them.
101-                            to_reduce -= change_and_fee;
102-                        }
103-                    }
104                     for (const auto& recipient : vecSend)
105                     {
106                         if (i == nChangePosInOut) {
107@@ -3101,9 +3072,9 @@ bool CWallet::CreateTransactionInternal(
108                         }
109                         ++i;
110                     }
111+                    nFeeRet = fee_needed;
112                     break; // The fee has been deducted from the recipients, nothing left to do here
113                 }
114-                assert(false); // It shouldn't be possible to reach this
115             }
116 
117             // Give up if change keypool ran out and change is required

Move output reductions for fee to after coin selection

Simplifies CreateTransactionInternal without changing behavior. Removes
the pick_new_inputs variable by moving the subtract fee from amount
implementation to later in the loop to where it is possible to calculate
the fee for the transaction. This allows the fee to be subtracted from
the outputs within a single iteration, instead of calculating the fee in
the first iteration, and subtracting the fee in the second.

This also removes another scenario where a second iteration of the loop
finds a smaller input set (and thus smaller fees than the first
iteration) with no change and so a third iteration of the loop is done in order to make
a change output that contains the excess fees.

To handle these cases, we always create a change output which contains
the difference between selected input values and the recipient amounts.
Once the transaction fee is calculated, the change output is reduced (in
the normal case) or the recipient amounts are reduced (in the subtract
fee from amount case). All of this is done in a single iteration of the
loop.

cc3f14b27c

Roll static tx fees into nValueToSelect instead of having it be separate

The fees for transaction overhead and recipient outputs are now included
in nTargetValue instead of being a separate parameter. For the coin
selection algorithms, it doesn't matter that these are separate as in
either case, the algorithm needs to select enough to cover these fees.

Note that setting nValueToSelect is changed as it now includes
not_input_fees. Without the change to how nValueToSelect is increased
for KnapsackSolver, this would result in overpaying fees. The change to
increase by the difference between nFeeRet and not_input_fees allows
this to have the same behavior as previously.

Additionally, because we assume that KnapsackSolver will always find a
solution that requires change (we assume that BnB always finds a
non-change solution), we also include the fee for the change output in
KnapsackSolver's target. As part of this, we also use the changeless
nFeeRet when iterating for KnapsackSolver. This is because we include
the change fee when doing KnapsackSolver, so nFeeRet on further
iterations won't include the change fee.

bf26e018de

Have KnapsackSolver actually use effective values

Although the CreateTransaction loop currently remains, it should be
largely unused. KnapsackSolver will now account for transaction fees
when doing its selection.

In the previous commit, SelectCoinsMinConf was refactored to have some
calculations become shared for KnapsackSolver and SelectCoinsBnB. In
this commit, KnapsackSolver will now use the not_input_fees and
effective_feerate so that it include the fee for non-input things
(excluding a change output) so that the algorithm will select enough to
cover those fees. This is necessary for selecting on effective values.

Additionally, the OutputGroups
created for KnapsackSolver will actually have their effective values
calculated and set, and KnapsackSolver will do its selection on those
effective values.

Lastly, SelectCoins is modified to use the same value for preselected
inputs for BnB and KnapsackSolver. While it will still use the real
value when subtracting the fee from outputs, this behavior will be
the same regardless of the algo used for selecting additional inputs.

01dc8ebda5

Do both BnB and Knapsack coin selection in SelectCoinsMinConf

Instead of switching which algorithm to use based on use_bnb, just run
both in SelectCoinsMinConf. If BnB fails, do Knapsack.

de26eb0e1f

Remove use_bnb and bnb_used

These booleans are no longer needed

6f0d5189af

Remove CreateTransaction while loop and some related variables

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

9d3bd74ab4

Change SelectCoins_test to actually test SelectCoins

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.

6d6d278475

Have OutputGroup determine the value to use

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().

51a3ac242c

in src/wallet/wallet.cpp:2956 in 67fc8b7be1 outdated

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

ryanofsky commented at 7:01 pm on May 19, 2021:

In commit “Roll static tx fees into nValueToSelect instead of having it be separate” (67fc8b7be1d5fbdb199d6e995434431a7282d446)

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:

0CAmount nValueToSelect = nValue;
1if (coin_selection_params.use_bnb) nValueToSelect += not_input_fees;
2if (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 #17331 (review)
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

achow101 commented at 7:48 pm on May 19, 2021:

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.

in src/wallet/wallet.cpp:3033 in 67fc8b7be1 outdated

3031@@ -3027,10 +3032,8 @@ bool CWallet::CreateTransactionInternal(
3032                             break;
3033                         }
3034 
3035-                        // The change value was not enough to cover the fees, even after dropping the change
3036-                        // We set nFeeRet back to its original value (the one that includes the change output) and try selecting again
3037+                        // The change value was not enough to cover the fees, even after dropping the change. Try selecting again.
3038                         assert(change_and_fee < nFeeRet);
3039-                        nFeeRet = orig_fee;

ryanofsky commented at 7:16 pm on May 19, 2021:

In commit “Roll static tx fees into nValueToSelect instead of having it be separate” (67fc8b7be1d5fbdb199d6e995434431a7282d446)

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.

achow101 commented at 7:51 pm on May 19, 2021:

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.

in src/wallet/wallet.cpp:3029 in a07552b94f outdated

3023@@ -3032,9 +3024,10 @@ bool CWallet::CreateTransactionInternal(
3024                             break;
3025                         }
3026 
3027-                        // The change value was not enough to cover the fees, even after dropping the change. Try selecting again.
3028-                        assert(change_and_fee < nFeeRet);
3029-                        continue;
3030+                        // Since we use effective values now, it should not be possible to reach this situation where the change value was not
3031+                        // enough to cover the fees
3032+                        error = _("Cannot reduce change to cover transaction fees");

ryanofsky commented at 7:24 pm on May 19, 2021:

In commit “Have KnapsackSolver actually use effective values” (a07552b94fe05651970e53813ae67606692d6f19)

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.

achow101 commented at 7:52 pm on May 19, 2021:

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

ryanofsky commented at 8:25 pm on May 24, 2021:

In commit “Have KnapsackSolver actually use effective values” (01dc8ebda50a382d45d3d169b2c3f3965869dcae)

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 01dc8ebda50a382d45d3d169b2c3f3965869dcae would be:

 0--- a/src/wallet/wallet.cpp
 1+++ b/src/wallet/wallet.cpp
 2@@ -3004,10 +3004,9 @@ bool CWallet::CreateTransactionInternal(
 3                     error = _("Signing transaction failed");
 4                     return false;
 5                 }
 6-                nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 7+                CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 8 
 9                 // Subtract fee from the change output if not subtrating it from recipient outputs
10-                CAmount fee_needed = nFeeRet;
11                 if (nSubtractFeeFromAmount == 0) {
12                     change_position->nValue -= fee_needed;
13                 }
14@@ -3071,6 +3070,10 @@ bool CWallet::CreateTransactionInternal(
15                     nFeeRet = fee_needed;
16                     break; // The fee has been deducted from the recipients, nothing left to do here
17                 }
18+                CHECK_NONFATAL(!coin_selection_params.use_bnb);
19+                CHECK_NONFATAL(nFeeRet == 0);
20+                CHECK_NONFATAL(fee_needed != 0);
21+                nFeeRet = fee_needed;
22             }
23 
24             // Give up if change keypool ran out and change is required

achow101 force-pushed on May 19, 2021

ryanofsky commented at 7:43 pm on May 19, 2021: member

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

2b445b7c1336506d43874a7ee31f85f511cd3114 Move output reductions for fee to after coin selection (4/11)
67fc8b7be1d5fbdb199d6e995434431a7282d446 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

achow101 commented at 7:44 pm on May 19, 2021: member

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

ryanofsky commented at 8:01 pm on May 19, 2021: member

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.

in src/wallet/wallet.cpp:2962 in bf26e018de outdated

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

ryanofsky commented at 6:56 pm on May 21, 2021:

In commit “Roll static tx fees into nValueToSelect instead of having it be separate” (bf26e018de33216d6f0ed0d6ff822b93536f7cc1)

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

ryanofsky approved

ryanofsky commented at 7:02 pm on May 21, 2021: member

Code review ACK 51a3ac242c92e69b59df26f8f9e287b31e5c3b0f. Looks good to go!

1bf4a62cb61bd4b91d9cd4e379fea2b914786342 scripted-diff: rename some variables (1/11)
af5867c89688b06173b295b7c32a42845ea455da Move some calculations to common code in SelectCoinsMinConf (2/11)
d97d25d95006725e705635530b27643363d6b2a4 Make cost_of_change part of CoinSelectionParams (3/11)
cc3f14b27c06b7a0da1472f5c7100c3f0b76fd98 Move output reductions for fee to after coin selection (4/11)
bf26e018de33216d6f0ed0d6ff822b93536f7cc1 Roll static tx fees into nValueToSelect instead of having it be separate (5/11)
01dc8ebda50a382d45d3d169b2c3f3965869dcae Have KnapsackSolver actually use effective values (6/11)
de26eb0e1fa2b6f03c58ba104d00f7a8ffead39c Do both BnB and Knapsack coin selection in SelectCoinsMinConf (7/11)
6f0d5189af4c881fe8b97a0c28ce1ffa33480715 Remove use_bnb and bnb_used (8/11)
9d3bd74ab4430532d6e53eef8cf77ad999044b14 Remove CreateTransaction while loop and some related variables (9/11)
6d6d2784759878ef0c4ac128d12aac68add1edca Change SelectCoins_test to actually test SelectCoins (10/11)
51a3ac242c92e69b59df26f8f9e287b31e5c3b0f Have OutputGroup determine the value to use (11/11)

in src/wallet/wallet.h:624 in d97d25d950 outdated

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

instagibbs commented at 2:04 am on May 24, 2021:

not in love with these names since they’re both costs, but only one says “cost”

in src/wallet/wallet.cpp:3021 in cc3f14b27c outdated

3133-                    }
3134+                // We want to drop the change to fees if:
3135+                // 1. The change output would be dust
3136+                // 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)
3137+                CAmount change_amount = change_position->nValue;
3138+                if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change)

instagibbs commented at 2:18 am on May 24, 2021:

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

in src/wallet/wallet.cpp:3004 in cc3f14b27c outdated

3067                     txNew.vin.push_back(CTxIn(coin.outpoint,CScript()));
3068                 }
3069 
3070+                // Calculate the transaction fee
3071                 tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
3072                 nBytes = tx_sizes.first;

instagibbs commented at 2:32 am on May 24, 2021:

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

in src/wallet/wallet.cpp:2961 in bf26e018de outdated

2956+                const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
2957+                CAmount nValueToSelect = nValue + not_input_fees;
2958+
2959+                // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the
2960+                // inputs that we found in the previous iteration.
2961+                if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) {

instagibbs commented at 3:04 am on May 24, 2021:

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

instagibbs approved

instagibbs commented at 3:29 am on May 24, 2021: member

review ACK https://github.com/bitcoin/bitcoin/pull/17331/commits/51a3ac242c92e69b59df26f8f9e287b31e5c3b0f

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.

in src/wallet/wallet.cpp:2884 in d97d25d950 outdated

2877@@ -2885,6 +2878,16 @@ bool CWallet::CreateTransactionInternal(
2878             CTxOut change_prototype_txout(0, scriptChange);
2879             coin_selection_params.change_output_size = GetSerializeSize(change_prototype_txout);
2880 
2881+            // Get size of spending the change output
2882+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
2883+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
2884+            // as lower-bound to allow BnB to do it's thing

meshcollider commented at 12:21 pm on May 25, 2021:

nit: its

meshcollider commented at 1:04 pm on May 25, 2021: contributor

Re-review in progress …

1bf4a62cb61bd4b91d9cd4e379fea2b914786342 scripted-diff: rename some variables
af5867c89688b06173b295b7c32a42845ea455da Move some calculations to common code in SelectCoinsMinConf
d97d25d95006725e705635530b27643363d6b2a4 Make cost_of_change part of CoinSelectionParams
cc3f14b27c06b7a0da1472f5c7100c3f0b76fd98 Move output reductions for fee to after coin selection
bf26e018de33216d6f0ed0d6ff822b93536f7cc1 Roll static tx fees into nValueToSelect instead of having it be separate
01dc8ebda50a382d45d3d169b2c3f3965869dcae Have KnapsackSolver actually use effective values
de26eb0e1fa2b6f03c58ba104d00f7a8ffead39c Do both BnB and Knapsack coin selection in SelectCoinsMinConf
6f0d5189af4c881fe8b97a0c28ce1ffa33480715 Remove use_bnb and bnb_used
9d3bd74ab4430532d6e53eef8cf77ad999044b14 Remove CreateTransaction while loop and some related variables
6d6d2784759878ef0c4ac128d12aac68add1edca Change SelectCoins_test to actually test SelectCoins
51a3ac242c92e69b59df26f8f9e287b31e5c3b0f Have OutputGroup determine the value to use

re-light-utACK 51a3ac242c92e69b59df26f8f9e287b31e5c3b0f

meshcollider merged this on May 25, 2021

meshcollider closed this on May 25, 2021

laanwj removed this from the "Blockers" column in a project

ryanofsky referenced this in commit e459d013d7 on Jun 4, 2021

ryanofsky referenced this in commit e65102cc96 on Jun 8, 2021

ryanofsky referenced this in commit 36c1c98475 on Jun 8, 2021

meshcollider referenced this in commit 58f8b156ed on Jun 9, 2021

ryanofsky referenced this in commit 6071dd2cfa on Jun 10, 2021

ryanofsky referenced this in commit 764ccec4b4 on Jun 10, 2021

ryanofsky referenced this in commit fb7ba37a0c on Jun 10, 2021

ryanofsky referenced this in commit 496af352ed on Jun 12, 2021

ryanofsky referenced this in commit 68f7985762 on Jun 12, 2021

ryanofsky referenced this in commit fe6dc76b7c on Jul 14, 2021

MarcoFalke referenced this in commit 7075a52b67 on Jul 27, 2021

gwillen referenced this in commit 8b34c974c3 on Jun 1, 2022

DrahtBot locked this on Aug 16, 2022

Use effective values throughout coin selection #17331

Conflicts