Use effective values throughout coin selection #17331

rename target_value to actual_target here as well?

Done

This looks like a debug print?

Removed

Is this missing a continue here?

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.

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

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

Done

Should also be updated since it's now 0.5.

Done

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

Removed

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

Removed

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

Added a comment

note to reviewers: this is removed next commit

err. no?

Removed

let's bracketize while we're here.

Braketized where this was moved to.

let's bracketize while we're here.

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

Yes. Moved this to the later part.

let's bracketize while we're here.

Removed this else

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

Done

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

Done

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

Done

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

Done

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?

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

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

Added from above.

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

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.

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

I had not considered enabling avoidpartial.

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.

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.

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…

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.

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.

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?

Done in the upstream pr.

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?

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

How about // Every OutputGroup has only one output

Done

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

Done

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

Meh. I think it's fine for now.

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.

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

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?

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

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

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

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.

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

Meh. Belt-and-suspenders check.

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.

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

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:

1. You've already spent from that address once. If you spend from it again, they can associate the two transactions to you*.
2. 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)

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?

We deal with the change fee later.

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

The minimum change stuff is within KnapsackSolver itself.

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.

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

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

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.

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.

I've rewritten this comment.

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

Existing name, won't change for now.

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

Yes.

Yes.

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

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

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

            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.

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.

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

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.

695fbaa3a nicety if you retouch

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

Done

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

            CAmount selected_eff = 0; // selected effective value

Done

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

                // Cost of a change output = (size of output * this tx feerate) + (size of spending input * discard feerate)
                const 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);

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

tiny nit, since you're touching

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

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

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

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

Done

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?

Good idea, done.

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.

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.

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

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.

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?

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.

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?

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:

1. Calling KnapsackSolver with a higher nTargetvalue so it is forced to account for cost of final transaction outputs
2. 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
3. Refactoring code in SelectCoinsMinConf mostly not changing behavior, except to call KnapsackSolver with the higher target at the end.
4. 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

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.

Done

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

Oops, changed back.

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

Done

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.

Taking this as an opportunity to shill #21759 😛

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

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

Changed the comment.

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

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.

nit

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

Done

nit

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

Done

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

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.

If you retouch, this would be nice

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

Done

This is mostly to confirm my understanding - ?

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

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

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

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

Done

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

Done

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?

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.

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.

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?

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

Done

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

Done

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?

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.

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

Changed the rename to another commit.

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

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

Doesn't seem like it, removed.

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

🐮 says moo 🐷 says oink me says

            const int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);

Done

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

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.

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?

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.

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.

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

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.

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

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.

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

Split up the commit.

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.

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

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.

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

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.

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

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;

Fixed.

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

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.

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.

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

Done.

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.

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.

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.

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.

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.

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.

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

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 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:

nChangePosInOut = -1;
to_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

nChangePosInOut = -1;
nFeeRet += 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):

std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_position->nValue <= coin_selection_params.m_cost_of_change)
{
    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).

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 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 ___."

Updated the commit message to explain this more.

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

Renamed to coin_sel_params.

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

Done

nit

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

This comment was removed/rewritten.