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

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30080.

Reviews

See the guideline for information on the review process.
A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #31870 (fuzz: split coinselection harness by brunoerg)

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.

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/24823503231}

From CI:

291/305 - 
rpc_help.py
 failed, Duration: 1 s
stdout:
2024-05-10T15:06:20.992000Z TestFramework (INFO): PRNG seed is: 4539310303736745094
2024-05-10T15:06:20.998000Z TestFramework (INFO): Initializing test directory /ci_container_base/ci/scratch/test_runner/test_runner_₿_🏃_20240510_150004/rpc_help_7
2024-05-10T15:06:21.349000Z TestFramework (ERROR): Assertion failed
Traceback (most recent call last):
  File "/ci_container_base/ci/scratch/build/bitcoin-i686-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 132, in main
    self.run_test()
  File "/ci_container_base/ci/scratch/build/bitcoin-i686-pc-linux-gnu/test/functional/rpc_help.py", line 54, in run_test
    self.test_client_conversion_table()
  File "/ci_container_base/ci/scratch/build/bitcoin-i686-pc-linux-gnu/test/functional/rpc_help.py", line 72, in test_client_conversion_table
    raise AssertionError("RPC client conversion table ({}) and RPC server named arguments mismatch!\n{}".format(
AssertionError: RPC client conversion table (/ci_container_base/ci/scratch/build/bitcoin-i686-pc-linux-gnu/src/rpc/client.cpp) and RPC server named arguments mismatch!
{('walletcreatefundedpsbt', 3, 'add_excess_to_recipient_position'), ('fundrawtransaction', 1, 'add_excess_to_recipient_position'), ('walletcreatefundedpsbt', 3, 'disable_algos'), ('send', 4, 'add_excess_to_recipient_position')}
2024-05-10T15:06:21.401000Z TestFramework (INFO): Stopping nodes
2024-05-10T15:06:21.503000Z TestFramework (WARNING): Not cleaning up dir /ci_container_base/ci/scratch/test_runner/test_runner_₿_🏃_20240510_150004/rpc_help_7
2024-05-10T15:06:21.503000Z TestFramework (ERROR): Test failed. Test logging available at /ci_container_base/ci/scratch/test_runner/test_runner_₿_🏃_20240510_150004/rpc_help_7/test_framework.log
2024-05-10T15:06:21.503000Z TestFramework (ERROR): 
2024-05-10T15:06:21.503000Z TestFramework (ERROR): Hint: Call /ci_container_base/ci/scratch/build/bitcoin-i686-pc-linux-gnu/test/functional/combine_logs.py '/ci_container_base/ci/scratch/test_runner/test_runner_₿_🏃_20240510_150004/rpc_help_7' to consolidate all logs
2024-05-10T15:06:21.503000Z TestFramework (ERROR): 
2024-05-10T15:06:21.503000Z TestFramework (ERROR): If this failure happened unexpectedly or intermittently, please file a bug and provide a link or upload of the combined log.
2024-05-10T15:06:21.504000Z TestFramework (ERROR): https://github.com/bitcoin/bitcoin/issues
2024-05-10T15:06:21.504000Z TestFramework (ERROR): 

Here are my initial thoughts on each of the options individually

change_target
IIUC you want a specific min value for the change UTXO. Would a following alternative work? You provide your change address in the list of recipients with desired min amount and specify it as change UTXO using change_positionparameter. The downside compared to a new option is that we always have a change output. Not sure if that's a problem in your case.

disable_algos
This makes sense, and could be a first step to pluggable coin selection in core. But it should be in settings, not in RPC parameters. I doubt many users need to change it at runtime and so it's better to keep the RPC parameters to a minimum.

add_excess_to_recipient_position
This options seems like a compromise that makes nobody happy. From your perspective you're okay to overfund a channel, but you have no control by how much, since excess is not configurable. From the perspective of users not doing splicing, this option is not useful at all.

It seems like what you really want is to search for a changeless solution in a given target range. And then if failed to fallback to a solution with change.

Thanks for the feedback! I agree that it is worth considering how to make these parameters more useful for general users.

change_target IIUC you want a specific min value for the change UTXO. Would a following alternative work? You provide your change address in the list of recipients with desired min amount and specify it as change UTXO using change_positionparameter. The downside compared to a new option is that we always have a change output. Not sure if that's a problem in your case.

Always having a change output would be a problem because we always prefer a changeless tx if the excess is not too large. But when that is not possible the change should be large enough to potentially spend later as a changeless tx.

A possible alternative would be to add a setting for CHANGE_LOWER rather than always use the hard coded value of 50,000 sats. It is probably not necessary for my use case to set the change_target every time we fund a tx; we can just make sure it is always above the minimum value we want for all of our UTXOs.

disable_algos This makes sense, and could be a first step to pluggable coin selection in core. But it should be in settings, not in RPC parameters. I doubt many users need to change it at runtime and so it's better to keep the RPC parameters to a minimum.

I agree that generally it's too in the weeds for most users. I'll move it to settings.

add_excess_to_recipient_position This options seems like a compromise that makes nobody happy. From your perspective you're okay to overfund a channel, but you have no control by how much, since excess is not configurable. From the perspective of users not doing splicing, this option is not useful at all.

Good point. The maximum excess currently built into BnB is cost_of_change, defined as the cost to create and spend a change output. This is an arbitrary value to use if you are happy to add some amount of excess to a changeless spend output. It would be better to also have a max_excess parameter that defaults to cost_of_change if not otherwise defined.

It seems like what you really want is to search for a changeless solution in a given target range. And then if failed to fallback to a solution with change.

Exactly! I believe that is how CS works now. If no set of inputs are found with excess in the range from zero to cost_of_change then BnB will fail and CS will fallback to a solution with change. But adding a new max_excess parameter would make it explicit what that range is.

From the perspective of not over complicating the coin selection options, do you think it would be better to have two new options: add_excess_to_recipient_position and max_excess, OR just add max_excess and always default to add the excess to the first spending target?

I changed disable_algos to enable_algos in 3154f83. This was suggested by @t-bast because it won't cause problems for existing users when new cs algorithms are added. I believe I have the simplest and safest solution for initializing the m_enable_algos std::bitset to all true, but there are a few other ways to do it.

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/25171023419}

May want to first do a PR to fix the related issue 26466 or resolve that issue if it has been fixed. ht @willcl-ark

It's not entirely clear to me why BnB should care about whether the excess is going to the recipient or not. I don't think that should change the algorithm at all, so the changes to SelectCoinsBnB seem unnecessary.

Additionally, this implementation modifies the target, and I think that's rather dangerous to do. I think the obvious way to implement this feature is to just detect when the fee paid is greater than the fee needed, and send the excess to the recipient specified, just as we already do when there are change outputs. That would also really shrink the diff.

I think the obvious way to implement this feature is to just detect when the fee paid is greater than the fee needed, and send the excess to the recipient specified, just as we already do when there are change outputs.

Thanks for the feedback. I agree and think for our use we can even do that diff outside of bitcoind. I'll update the PR.

It's not entirely clear to me why BnB should care about whether the excess is going to the recipient or not. I don't think that should change the algorithm at all, so the changes to SelectCoinsBnB seem unnecessary.

Imagine this scenario:

• target is 100
• max_excess is 30
• UTXOs: [20, 20, 20, 20, 20, 120]
• fee to spend an input: 4
• minimum spendable: 10

Input set A: [20,20,20,20,20]
Input set B: [120]

Current BnB computes waste as:
Input set A: 20 (best)
Input set B: 24

This PR with max_excess = 30 computes waste as:
Input set A: 20
Input set B: 4 (best)

In both cases, CG would select input set B and compute waste as something like 8 (1 input, 1 output). Current CS would choose the Knapsack solution(waste = 8 < 20). After this PR CS should select the BnB solution (waste = 4 < 8).

A sender that retains excess would prefer the less costly BnB solution using input set A.

This PR allows a sender to find an optimal solution using CS when excess value is retained by the sender.

Another approach would be to not change BnB at all, but instead modify CS to detect that the best solution has a change output amount (and fee) that is less than our specified max_excess and modify the final tx to add the change output amount (and fee) to the target output.

Needs rebase, if still relevant.

This PR looks interesting from the idea that throw away change can go to a different party instead of just throwing away to fees. At first glance though, it seems like the implementation is confusing. For example, I don't understand what max_excess is needed for.

From the commit message:

If set, excess from changeless spends can not exceed the lesser of this amount and the current cost_of_change, otherwise just use cost_of_change by default

This doesn't explain why this parameter is needed. I'm not saying it's not, just that more explanation would be helpful.

This doesn't explain why this parameter is needed. I'm not saying it's not, just that more explanation would be helpful.

You would want to set max_excess to something larger than cost_of_change if you want the utxos in your wallet to all be greater than max_excess.

For example, in the case of a Lightning node that is selling liquidity, you might know the smallest utxo you might sell is 10,000 sats + spend fees, so you could set max_excess to something like 15,000 sats. Now when you select a utxo to add inbound liquidity via a splice transaction, you won't create change of less than 15,000 sats and if you end up with excess value up to that amount you won't create any change output at all. Does that make sense?

I now believe we can achieve equivalent behavior without changing the wallet by just using it to find the best funding utxo, and if there is change we can (when appropriate) build the actual tx with the change amount added to the recipient output position before submitting the transaction.

I'll close this PR for now because this doesn't seem generally useful outside of Lightning liquidity providers that want to optimizing their UTXO set management, and a good alternative way of doing it exists.

I now believe we can achieve equivalent behavior without changing the wallet by just using it to find the best funding utxo, and if there is change we can (when appropriate) build the actual tx with the change amount added to the recipient output position before submitting the transaction.

Yes, that's a good idea.

I'll close this PR for now because this doesn't seem generally useful outside of Lightning liquidity providers that want to optimizing their UTXO set management, and a good alternative way of doing it exists.

I don't know that this idea applies only to Lightning, I can envision some other creative use cases other than just increasing the transaction priority by adding to fees. However, for it to be useful you'd need to be in position to take advantage some large number of aggregate transaction for the change amounts to be worthwhile and there's also the issue of aggregating amounts greater than the dust limit.