wallet: Target a pre-defined utxo set composition by adjusting change outputs

remyers commented at 4:45 pm on February 16, 2024: contributor

This PR is designed for the use case of a Lightning node that provides liquidity of predefined amounts via liquidity ads.

Coin selection is currently optimized to reduce the size of the utxo set and create change optimized for privacy. A liquidity provider instead needs to service multiple liquidity requests by spending confirmed utxos of known sizes.

Ideally most liquidity transactions would be funded by a single input or a small set of inputs optimized to reduce fees. To minimize the number of unconfirmed transactions, inputs should also be sized in a range where most transactions do not produce change. When change is created, it should be divided into outputs of the sizes needed so that the wallet’s utxo set converges towards an ideal utxo set specified by the user.

I am opening this PR as a draft to get feedback and suggestions on the concept and my implementation to address this use case.

The algorithm described below can be implemented externally via RPC calls or directly in the wallet.

Externally: use a new option to set the change target used for coin selection.
Wallet (opportunistic): a new configuration file defines the desired utxo set which the wallet uses to compute the change target used for coin selection and to split change outputs (if any).
Wallet (reactive/proactive): pre-select a large input to force coin selection to produce change when fees are below some specified threshold or the desired set of utxos falls below some threshold.

utxo targets file example:

 0{
 1    "buckets": [
 2        {
 3            "start_satoshis": 10000,
 4            "end_satoshis": 25000,
 5            "target_utxo_count": 150
 6        },
 7        {
 8            "start_satoshis": 50000,
 9            "end_satoshis": 75000,
10            "target_utxo_count": 50
11        },
12        {
13            "start_satoshis": 200000,
14            "end_satoshis": 250000,
15            "target_utxo_count": 20
16        },
17        {
18            "start_satoshis": 1000000,
19            "end_satoshis": 1400000,
20            "target_utxo_count": 5
21        }
22    ],
23    "bucket_refill_feerate": 30000
24}

The target_utxo_count for a bucket should be larger than the anticipated number of liquidity requests of bucket_start_satoshis within the expected confirmation time of a liquidity transaction.
The range from bucket_start_satoshis to bucket_end_satoshis should encompass expected fee variance.
The bucket_refill_feerate should be set to the expected median fee rate (?).
This file will be reloaded for every spend request to allow for on-the-fly updates

Algorithm steps

For each payment do the following:

Calculate the current capacity of each target bucket from the wallet’s utxo set.
- Include outputs from both confirmed and unconfirmed transactions in the wallet to calculate capacity.
Add our largest confirmed utxo as an input IF the capacity of the least full target bucket is below some threshold (eg. < 30% full) or less than some higher threshold (eg. < 70%) and fee rates are below the bucket_refill_feerate.
- When the largest confirmed utxo is from one of our target buckets, then we should refill our wallet with a utxo from cold storage.
Set the minimum change target m_min_change_target to a value from the target bucket with the lowest current capacity.
- Generate a random change target of the amount: current change_fee (the fee for creating an output) + a random value in the range: bucket_start_satoshis to bucket_end_satoshi - change_fee.
- Currently the change target is set by GenerateChangeTarget() in a hard coded range.
- This parameter is only used by the ‘knapsack’ and ‘coingrinder’ algorithms.
Call ‘SelectCoins()’ with the input from step 2 (if any) added to the preset_inputs parameter and with the minimum change target from step 3.
- The consolidatefeerate=0 configuration option should always be set so that utxos are not preemptively cosolidated. Coin selection sets the parameter m_long_term_feerate to the wallets consolidatefeerate.
- Ideally, only the ‘bnb’ and ‘cg’ coin selection algorithms should be used and the others disabled to optimize for low fees.
If the coin selection result includes a change output, then split the single change output amount into multiple outputs.
- Add the mimimum change target as an output first.
- If there is remaining value after paying the fee for a new output, then add a target from the next most empty target bucket.
- If there is not enough value to add a new output and fees, add remaining value to the last output added instead.

DrahtBot commented at 4:45 pm on February 16, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

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:

#29906 (Disable util::Result copying and assignment by ryanofsky)
#29700 (kernel, refactor: return error status on all fatal errors by ryanofsky)
#29523 (Wallet: Add max_tx_weight to transaction funding options (take 2) by ismaelsadeeq)
#29015 (kernel: Streamline util library by ryanofsky)
#28366 (Fix waste calculation in SelectionResult by murchandamus)
#28201 (Silent Payments: sending by josibake)
#26606 (wallet: Implement independent BDB parser by achow101)
#26596 (wallet: Migrate legacy wallets to descriptor wallets without requiring BDB by achow101)
#26022 (Add util::ResultPtr class by ryanofsky)
#25722 (refactor: Use util::Result class for wallet loading by ryanofsky)
#25665 (refactor: Add util::Result failure values, multiple error and warning messages by ryanofsky)

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.

DrahtBot added the label Wallet on Feb 16, 2024

remyers force-pushed on Feb 16, 2024

DrahtBot added the label CI failed on Feb 16, 2024

DrahtBot commented at 4:53 pm on February 16, 2024: contributor

🚧 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/21662752091

remyers force-pushed on Feb 16, 2024

DrahtBot removed the label CI failed on Feb 16, 2024

t-bast commented at 10:30 am on February 19, 2024: contributor

@murchandamus we’d love to get your feedback on this! I’ll try to summarize at a higher level what we’d like to achieve.

The bitcoind wallet currently tries to keep a somewhat “minimal” utxo set and actively consolidates user utxos, because it assumes that we receive transactions as much (or more) than we send transactions and wants outgoing transactions to be as cheap as possible. But that’s not true of liquidity service providers, who usually only receive funds when refilling the wallet from cold storage, and want to make sure they always have enough confirmed utxos to satisfy user demand efficiently. In such cases, the wallet operator has a good idea of what they’d like their utxo pool to look like (because they’re selling a limited sets of specific amounts), and would like bitcoind to try to maintain that utxo pool as much as possible, while optimizing mostly for transaction weight, especially when feerate is high (above a user-defined threshold, similar to consolidatefeerate but with the exact opposite semantics - when below that threshold, we want to actively create more utxos, not consolidate them).

We can think of this type of wallet as a slowly draining wallet: its total amount is linearly decreasing over time, and is occasionally topped-up from cold storage.

We’re not sure how to best achieve that. Our goal is to do it inside bitcoind (which is the source of truth for the wallet state), but with minimal changes to the coin selection code itself. We’d like this to be as much as possible done by simply pre-processing inputs to the coin selection algorithms and post-processing their outputs, which would make this:

easy to rebase on top of bitcoind releases if this work doesn’t make sense to be accepted into bitcoind
or as a user-configurable option if that PR can be merged to bitcoind

in src/wallet/spend.cpp:1228 in 85a049ddce outdated

1224@@ -1128,6 +1225,36 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
1225         available_coins = AvailableCoins(wallet, &coin_control, coin_selection_params.m_effective_feerate);
1226     }
1227 
1228+    // Load a json file that describes a target utxo set

t-bast commented at 3:17 pm on February 21, 2024:

Loading this file every time we fund a transaction doesn’t seem reasonable. I think we should start with a static file that needs a restart whenever the node operator wants to change values, and we can later decide how to make this more dynamic (if it’s even necessary).

remyers commented at 11:33 am on February 23, 2024:

That makes sense. I also think a static file could describe the buckets in a way that better adapts to a changing fee environment.

For example, rather than start_satoshis and end_satoshi we could define a bucket as:

0        "confirmation_target": 6,
1        "fee_rate_std": 10000, 
2        "buckets": [
3        {
4            "target_satoshis": 10000,
5            "target_utxo_count": 150
6        },

The range of values you want to spend should be “target_satoshis” + the fee to spend that input at a fee rate that will confirm in “confirmation_target” blocks. Because free rates vary, we randomize the current fee rate within a range +/- “fee_rate_std”.

To refill a bucket, compute the target_output as:

0target_feerate = current_feerate("confirmation_target") + random(-1 * "fee_rate_std", "fee_rate_std")
1target_output = "target_satoshis" + size_of_input * target_feerate

Ideally we would only need to restart when we add/remove buckets, change their counts or when fee variance changes dramatically.

in src/wallet/spend.cpp:846 in 85a049ddce outdated

841+}
842+
843+/** Returns a random change amount in the range of the most depleted Utxo bucket and sets `capacity`
844+ * to the capacity of that change target, if any.
845+ */
846+std::optional<CAmount> GenerateChangeTargetFromUtxoTargets(const std::vector<UtxoTarget>& utxo_targets, const CAmount change_fee, double& capacity, FastRandomContext& rng)

t-bast commented at 3:47 pm on February 21, 2024:

I’m not sure this is really what we want. I think this function should try to refill multiple buckets at once (when amounts allow it), not just the most depleted one:

Check which utxo buckets should be refilled:
- Initialize a to_refill list of (bucket, target_quantity)
- For each utxo bucket:
  - If the feerate is low (below a to-be-defined threshold) and the bucket is less than 70% full (or a to-be-defined threshold that could be configurable):
    - Add this bucket to to_refill with a target_quantity of target_utxo_count - current_utxo_count (when feerate is low, we’d like to refill as much as possible)
  - If the feerate is higher than our threshold and the bucket is less than 30% full (or a to-be-defined threshold that could be configurable), we refill less aggressively:
    - Add this bucket to to_refill with a target_quantity that we scale (somehow) based on feerate and how many utxos we’re missing
- Order to_refill by target_quantity, descending (we’ll want to refill the buckets that are missing the most utxos first)
Check the utxos that we have outside of our buckets: we ideally want to spend those utxos to refill our buckets. We have no guarantee that those are the ones that will be used by the coin selection, but we can use their total amount as the maximum amount of funds we allocate to refill our buckets. This part is a bit fuzzy for me right now, I’m not sure this is the best approach, it definitely deserves more thoughts.
- Iterate over those utxos and add their amount to obtain utxos_outside_buckets_total_amount
Compute the change target based on to_refill and utxos_outside_buckets_total_amount:
- Initialize change_target to 0
- Iterate over to_refill, and for each bucket that needs to be refilled:
  - Decide how much of the target_quantity we want to refill based on utxos_outside_buckets_total_amount and the current change_target
  - Add the corresponding amount to change_target
  - That step probably has a lot of issues as well and deserves more thought. If we have a lot of utxos outside of our buckets, we may end up targeting a very large change amount and thus create a huge transaction, which is generally undesirable, but maybe desirable when our buckets are close to being empty. Maybe it makes sense to bound the change_target to a (small) multiplier of the funding amount? Or have a very different behavior when the feerate is very low, because when that happens we may want to fully refill our buckets?

As you can see, this is still very early discussion on what the algorithm should look like. It feels like we’re still trying to understand the pitfalls we want to avoid we should try to write the algorithm in pseudo-code first in order to converge on an initial version (maybe to be detailed and discussed in a delving bitcoin post).

Also, when we don’t want to actively refill buckets, we should target a changeless transaction, I’m not sure that is done right now?

remyers commented at 4:30 pm on February 23, 2024:

I think it is unavoidable that refilling buckets cannibalizes utxos from other buckets unless there is a pool of utxos larger than the largest target bucket to pick from. The goal though is that in the long run the system wastes as little value from fees and over payment as possible in aggregate.

This is how I think the process as implemented currently (85a049d) should work:

Because we always set our minimum change value to be at least as large as one of our target buckets that is depleted, all of the wallet utxos are either in the range of one of our target buckets or larger than one of our target buckets.

A changeless BnB solution is found when:

there is a single utxo in the corresponding target bucket that does not overpay by too much in fees
a combination of multiple utxos smaller than the target bucket exist that do not overpay by too much in fees

A CoinGrinder solution is preferred when the cost of fees and over payment of the best BnB solution is more than the fees from using:

a single larger utxo with change outputs
a combination of multiple smaller utxos and change outputs

The largest wallet utxo will hold the residual value after initially refilling the buckets from cold storage. This residual funding utxo will be used as a single input when:

this utxo is available and CoinGrinder selects it to refill buckets opportunistically
fees are low, or buckets are severely depleted, we force this input to be selected to refill buckets.

When a large residual value utxo is used to refill all buckets via change outputs, another large residual utxo may also be created. That residual value utxo can not be used again until the tx that uses it confirms. This seems like an area that can be optimized. Perhaps a separate automatic refill transaction that confirms quickly makes more sense than using it for opportunistic bucket refills.

Eventually the largest utxo in the wallet will be in the range of the target buckets. The utxo set will then no longer be able to refill buckets without also depleting other buckets. This should be a signal to refill the wallet from cold storage.

remyers commented at 1:10 pm on February 28, 2024:

Also, when we don’t want to actively refill buckets, we should target a changeless transaction, I’m not sure that is done right now?

The current system should always prefer changeless transactions unless, for example, an exact match with more inputs and no change is more wasteful than selecting fewer inputs that generate a change output.

in src/wallet/spend.cpp:861 in 85a049ddce outdated

856+        capacity = double(target_iter->current_utxo_count) / target_iter->target_utxo_count;
857+    }
858+    return change_target;
859+}
860+
861+std::list<CTxOut> SplitChangeFromUtxoTargets(CAmount change_amount, std::vector<UtxoTarget> utxo_targets, CAmount change_target, const CAmount change_fee, FastRandomContext& rng, CScript script_change)

t-bast commented at 3:52 pm on February 21, 2024:

I’m wondering whether we should use a fully deterministic algorithm to split the change into buckets, I’m afraid this is exactly the kind of algorithm that may end up in a loop where one funding attempt does something, and the next one undoes it. It feels like adding randomization may be the simple way to avoid this? But maybe it’s too early in the algorithm design phase to decide.

remyers commented at 10:04 am on February 26, 2024:

I agree that there’s a risk that one funding operation adds an extra input from an existing bucket and then creates a change output to refill that same bucket, for example. My intuition though is that we can’t optimize too far into the future.

Even if an input is cannibalized from a bucket, it will be “reforged” into a new utxo that hopefully has a value that is more likely to be selected by BnB as a single input to a future changeless funding transaction. The current scheme randomizes new change outputs and skews them based on the current fee rate to try to optimize for future changeless single input transactions.

Can we do better with some ideas from memory caching? Maybe use the frequency that a particular amount is requested for funding to influence whether it is used as an extra input or as the size of a new change output?

t-bast commented at 3:55 pm on February 21, 2024: contributor

I really like the fact that it consists mostly of a pre-processing step before coin selection runs, followed by a post-processing step on the output of coin selection.

Should we also tweak which coin selection algorithms are run depending on whether we’re trying to refill buckets (and how aggressive we’d like to be) or not? Some of them may not be well suited for that?

remyers commented at 11:01 am on February 23, 2024: contributor

Should we also tweak which coin selection algorithms are run depending on whether we’re trying to refill buckets (and how aggressive we’d like to be) or not? Some of them may not be well suited for that?

Yes, I think we should only run BnB and Coingrinder. Currently SRD and Knapsack are fallbacks that could win when BnB and CoinGrinder have higher waste metrics. When consolidatefeerate=0 then longTermFeeRate=0 and the waste metric used to compare the results of the different algorithms should be based on how much we overshoot the target value + how much it costs to add more inputs.

0waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)

If one of the algorithms can find a solution with less overshoot than the cost of adding more (small value) inputs, then it seems like they would win. Coingrinder should always find a solution with the least input weight.

When fees are high, I think we should not care if we overshoot our target. We should always prefer a changeless BnB solution over one with change. When we have to produce change, we would prefer the Coingrinder solution with minimal input weight. We will allocate change to outputs sized to favor BnB in the future.

When fees are low, I think we will want to create more change to refill our target buckets, but still not favor more exact matches that use more inputs.

S3RK commented at 8:37 am on February 26, 2024: contributor

I think we should consider a pluggable architecture for coin selection algorithms.

It’s clear that there are multiple personas using the bitcoin core wallet, e.g. merchant, customer, lightning wallets. They have different and conflicting needs. So we either will have to have a complicated code and configuration surface to reconcile them or make our code extendable.

The interface of coin selection is pretty well defined, so it seems like it is a good fit for extensibility. The coin selection plug-in could receive utxo_pool and target amount as inputs (plus maybe some additional info), and return selected utxo’s as result. @remyers @t-bast would something like this work in your case?

remyers commented at 9:16 am on February 26, 2024: contributor

I think we should consider a pluggable architecture for coin selection algorithms.

That’s an interesting suggestion. So far in our case I don’t see a need to use a different coin selection algorithm, though I do think there might be value in having the ability to selectively disable SRD and knapsack. The current scheme proposed in this PR is more of a wrapper around the existing coin selection system.

I can not rule out the possibility that there might exist a superior custom coin selection algorithm for this use case. If someone were to propose a different algorithm then that would certainly help motivate a pluggable coin selection architecture.

yancyribbens commented at 6:40 pm on February 28, 2024: contributor

Is the bitcoin core reference implementation the right place to try these customization/personas?

remyers commented at 2:25 pm on March 1, 2024: contributor

Is the bitcoin core reference implementation the right place to try these customization/personas?

That’s a fair question - I think it depends on how widely useful this kind of customization/persona is for different wallet users.

Even if it’s not deemed general enough for more than a draft PR, comments will help improve the implementation in a fork and could feed back less invasive ideas to core. For example, just having a way to specify the minimum_change used by cs could be useful.

DrahtBot commented at 2:27 pm on March 22, 2024: contributor

🚧 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/22979879322

DrahtBot added the label CI failed on Mar 22, 2024

wallet: Add change_target parameter to coin control

Add a coin control parameter to optionally force a particular change target for coin selection algorithms that result in a change output.

ea2fb83ccc

wallet: Define utxo set targets to replenish when spends have change

Add a config option to load a json file that defines a set of utxo target buckets with a value range and count. When the current utxo set for the wallet does not match or exceed the counts for the value ranges of the buckets, opportunistically split the change output produced by coin selection (if any) into additional outputs.

Target buckets will be refilled from most to least depleted. The value of a new output to refill a target bucket will be randomly selected from its value range.

Once all buckets are full the change output will not be further split.

83b1f5d25e

wallet: Refill utxo target buckets proactively

When utxo targets are specified and a utxo target bucket is depleted, or fees are low, produce excess change that can be split to replenish the utxo target set. This is accomplished by including a large valued utxo as an input to coin selection.

1641736156

Compute utxo targets using unconfirmed outputs e31706a957

Add max_excess coin selection parameter

When considering a transaction without change, the max_excess amount is how much extra value can be added to the target value and not be counted as waste.

e41d853bda

Add coin control rpc option "disable_algos" 6764afb95e

Add new pre-coinselection using utxotargets and feerate estimates 0d752b592d

remyers force-pushed on Apr 15, 2024

Replace max_excess with add_excess_to_recipient_position

- When this is added to a funding RPC call then the waste for changeless BnB txs will be added to the selected recipient output position instead of added to fees.

2efadb1b47

DrahtBot added the label Needs rebase on Apr 30, 2024

DrahtBot commented at 6:27 pm on April 30, 2024: contributor

🐙 This pull request conflicts with the target branch and needs rebase.

Saraeutsza commented at 12:34 pm on May 12, 2024: none

remyers:2024-05-bnb-excess

remyers commented at 9:25 am on May 13, 2024: contributor

Replaced by simpler #30080

remyers closed this on May 13, 2024

wallet: Target a pre-defined utxo set composition by adjusting change outputs #29442

utxo targets file example:

Algorithm steps

Code Coverage

Reviews

Conflicts