Make `Changeless` metric more useful when combined.

[evanlinjin]

@LLFourn mentioned in a private discussion:

... in theory the combined will be looser than each individual one in the sense that it will take more iterations to find the optimal solution for the combined one I think. (A,B) has to find an optimal solution for A but this will not necessarily be optimal for (A,B) so it has to keep looking.

I responded with:

Would you agree that combining another metric with Changeless is only useful if it tightens the bounds? Otherwise, we might as will do Iterator::filter on the BnbIter.

Relevant Context

• https://github.com/bitcoindevkit/coin-select/pull/13#discussion_r1452009375

[jp1ac4]

We have some situations where we only want solutions with change so I'm interested in the approach taken here and seeing how best to adapt it to our case.

[LLFourn]

Would you agree that combining another metric with Changeless is only useful if it tightens the bounds? Otherwise, we might as will do Iterator::filter on the BnbIter.

Can you explain more fully what you had in mind. And filter for what?

Tightness of bounds refers to how accurate the bounding function of a metric is. When you combine two metrics the bounding function necessarily becomes less accurate in the sense that the ordering on candidate solutions for the combined will be worse than each individual metric.

Maybe your question is whether it's right to do (A, B) or just do A and then pick the best B from the results. You will get slightly different results but I can't guess whether they will be better or worse. It'd depend on the metrics.

But FWIW I agree that the changeless metric is not very useful. It's always a mistake to add it atm so it probably shouldn't exist. lowest_fee will try and get you changeless or as close as possible. Wdyt?

We have some situations where we only want solutions with change so I'm interested in the approach taken here and seeing how best to adapt it to our case.

Interesting. So for this I'd say that the output's weight should just be added to the base transaction weight with the minimum value you'd accept for the change included in the Target along with the value for other outputs. In this case it's not really a "drain" since it's always there. Then use a change policy of "never add change" (we can add this). Then somehow we have to tell the metric not to worry about penalizing excess (being able discount excess is a useful feature I think ). Then when the selection is done you can just add the excess to the placeholder change output. Does that makes sense?

Note one might think a policy of "always add change" might be the way to go here but this will add change even when the excess value is below the relay limit for that output. You'd need a way of expressing "always add change with at least this value" and I think this will complicate things.

Out of interest why do you need this. I've actually seen another case in the ecosystem where they always add change but I thought it was a peculiar scenario.

@evanlinjin I'd wonder what you think as well.

[jp1ac4]

Does that makes sense?

Yep, that makes sense thanks. The approach we've taken for now is to create a new metric based on LowestFee, but with the score as None in case there is no drain according to the change policy, so that only selections with a change output are chosen. This modified metric uses the same bound function as LowestFee, which I guess means we may consider some branches that don't have selections with change, so we could also try to tighten this bound, but for now it seems fine.

Out of interest why do you need this. I've actually seen another case in the ecosystem where they always add change but I thought it was a peculiar scenario.

We use this for sweep-type transactions. For example, if we want to refresh the timelock on some UTXOs, we create a new transaction with these UTXOs as inputs and no outputs, and then get as much change as possible given the target feerate. The "must have change" condition ensures we return a selection with change rather than one with a lower score that would create a transaction with no outputs.

Another case is when we want to "cancel" a transaction using RBF, we create a replacement transaction that sends as much as possible to change at the target feerate and removes the outputs.

[LLFourn]

Does that makes sense?

Yep, that makes sense thanks. The approach we've taken for now is to create a new metric based on LowestFee, but with the score as None in case there is no drain according to the change policy, so that only selections with a change output are chosen. This modified metric uses the same bound function as LowestFee, which I guess means we may consider some branches that don't have selections with change, so we could also try to tighten this bound, but for now it seems fine.

Yeah sounds suboptimal but that will work :)

Out of interest why do you need this. I've actually seen another case in the ecosystem where they always add change but I thought it was a peculiar scenario.

We use this for sweep-type transactions. For example, if we want to refresh the timelock on some UTXOs, we create a new transaction with these UTXOs as inputs and no outputs, and then get as much change as possible given the target feerate. The "must have change" condition ensures we return a selection with change rather than one with a lower score that would create a transaction with no outputs.

In this case you won't use branch and bound because the set of coins you're going to spend is fixed right? You just select everything that needs to be updated, add a zero value output with the weight of your draining output, figure out the excess for the feerate and finally set the value of the draining output to the excess.

Another case is when we want to "cancel" a transaction using RBF, we create a replacement transaction that sends as much as possible to change at the target feerate and removes the outputs.

Why does it have to have a change output if you're just doing RBF?

[jp1ac4]

In this case you won't use branch and bound because the set of coins you're going to spend is fixed right?

That's right sorry, the coin selection is already done in this case and it's just a question of seeing if there's enough excess for change. For the RBF "cancel" transaction, we only need to select at least one of the inputs from the transaction to be replaced and so we do use coin selection in that case.

Why does it have to have a change output if you're just doing RBF?

This is for one particular use of RBF where we "cancel" the transaction by replacing it with another that has only a change output. This way, we keep all our funds from the first transaction except for the fee of the replacement transaction.