Coin selection for liquidity providers

coin-selection-lsp.md

Coin selection for liquidity providers

Bitcoin Core's coin selection algorithms optimizes mostly for the following metrics:

• keep a low utxo count by consolidating regularly
• avoid creating a change output
• when a change output is needed, use an amount equivalent to the payment (for privacy)

This doesn't match what liquidity providers need. Liquidity providers need to:

• keep a large enough utxo pool
• keep a diversity of utxo amounts that matches what we're selling
• use as few inputs as possible when funding transactions
• avoid creating change outputs most of the time

We'll need to either tweak the existing coin selection algorithms to match those goals, or write our own coin selection algorithm. Ideally this will take the form of a branch on top of Bitcoin Core's release branches, that is easy to rebase from one release to the other. Even more ideally this code would be accepted into Bitcoin Core.

Parameters to the algorithm

Utxo set target

We'd like to configure our Bitcoin Core node with a description of our ideal utxo set, which consists of buckets of specific amounts. This would probably be an array of the following form:

[
    {
        "bucket_start_satoshis": 10000,
        "bucket_end_satoshis": 25000,
        "target_utxo_count": 150,
    },
    {
        "bucket_start_satoshis": 50000,
        "bucket_end_satoshis": 75000,
        "target_utxo_count": 50,
    },
    {
        "bucket_start_satoshis": 200000,
        "bucket_end_satoshis": 250000,
        "target_utxo_count": 20,
    },
    {
        "bucket_start_satoshis": 1000000,
        "bucket_end_satoshis": 1400000,
        "target_utxo_count": 5,
    }
]

Bitcoin Core should try to make our utxo set converge towards that ideal utxo set. That ideal utxo set is crafted by the node operator to ensure that most funding attempts require few inputs for its expected business operations.

Bucket refill feerate

Since one of the goals of the coin selection algorithm is to produce transactions that don't have any change output, the buckets will gradually empty themselves. There should be two mechanisms to refill the utxo buckets:

• opportunistic refill
• low-feerate active refill

Whenever we're unable to produce a transaction that doesn't have a change output, we should opportunistically create change outputs that refill the most depleted buckets (even if that means adding more inputs).

If the current mempool feerate is below a configured threshold (bucket_refill_feerate), we should actively create change outputs to refill depleted buckets (note that it's perfectly fine, and even beneficial to create multiple change outputs in one single transaction).

Otherwise, when we're running too low on utxos in some buckets (with a threshold to be defined), we should force the creation of change outputs, regardless of the current feerate.

We probably don't need an algorithm that finds an optimal solution in terms of fees, since this is a long term game, where creating new change outputs may cost us more now, but save us some money later.

Passing those parameters

The parameters from the previous section should be persistent, but it would be nice to be able to update them without having to restart bitcoind. Not sure how that would work though (maybe bitcoind could regularly read from a configuration file?).

Algorithm steps

For each payment do the following:

1. 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.
2. 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 targets buckets, then we should refill our wallet with a UTXO from cold storage.
3. Set the minimum change target wallet::CoinSelectionParams::m_min_change_target to a value from the target bucket with the lowest current capacity.
   • Generate a random change target from the current change_fee plus a random value in the range [bucket_start_satoshis, 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.
4. Call 'SelectCoins()' with the input from step 2 (if any) as a preset_inputs parameter and the minimum change target from step 4.
   • The consolidatefeerate=0 configuration option should always be set so that UTXOs are not preemptively cosolidated. Coin selection sets the parameter wallet::CoinSelectionParams::m_long_term_feerate to the wallets consolidatefeerate.
   • Only the 'bnb' and 'cg' coin selection algorithms should be used.
5. If 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.

UTXO target json file:

• The target_utxo_count for a bucket should be larger than the anticipated number of requests to spend bucket_start_satoshis within the expected confirmation time of a splice.
• 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.
• The target json file will be reloaded for every spend request to allow for on-the-fly updates