Coin Selection

[alessandrokonrad]

I've been thinking about coin selection recently. I looked at other coin selection algorithms and specificially CIP-2. None of these take multi assets into consideration and some other contraints like execution unit costs (having a lot of unnecessary assets in the inputs could easily exceed plutus script cost limits).

I took some of the ideas of Random Improve, because I think it's a good algorithm, but it simply needs to be adjusted for multiassets. Also the core principles are:

• keep it simple
• universally applicable to all kind of transaction types
• low complexity and fast calculation
• keep the amount of assets in inputs as small as possible
• good utxo distribution over time

1. Random sampling:

a) Loop through all assets and ada in the outputs and randomly select inputs (inputs that contain the asset) until at least the target amount is reached.

b) If the target amount for the next asset is already reached through the selection of previous assets, don't look further (this helps with not overadding too many inputs).

2. Improvement phase

a) Our goal is to find better inputs. We consider something as better if:

• we get closer to an ideal ADA amount (twice the target amount) => less utxo fractions overtime and better for covering fees and change outputs min ada requirements

• we get closer to an ideal amount for all assets (here also twice the target amount for each asset). We model this through vectors, where the dimension represents the amount of assets and the coordinate the quantity (e.g. x = [1,1,5], target = [2,4,8]). Then we normalize these vectors and take the euclidean distance. The closer the distance to 0 the better. (We do not want to do this when we interact with plutus scripts, then these weights are simply 0)

• we have less assets in our inputs (when we interact with plutus scripts we put even more weight on this)

• we never go below the least required amount for ada and all assets (put a very high weight, so this never happens)

  We can model this through a cost function, where we apply weights to each criteria described above. Basically we try to punish the coin selection and try to find the best input set were it gets least punished:

   cost = 100000 * has_least_required_amount + w_1 * ideal_ada + w_2 * ideal_assets + w_3 * asset_len
  

  w_n ∈ ℤ
  has_least_required_amount ∈ {0,1}
  ideal_ada, ideal_assets, asset_len ∈ [0,1]

b) We have 3 actions we can take to make improvements to our currently selected input set:

• Replace: We replace a random utxo from our selected input set with a random utxo from the remaining set
• Append: Append a utxo from the remaining set to the selected input set
• Remove: Remove a random utxo from the selected input set

c) Loop for n iterations (n = 100 currently) and do:

• Take an action and compare our previous state s_prev with our new state state s_new. If cost(s_new) < cost(s_prev) we apply s_new as our new input set.
• In each iteration we try out different actions until one applies and then we go into the next iteration. If no applies we also go into the next iteration.

d) After the improvement iterations we get our final input set.

[fermatspace]

Did you look at the implementation of the off-chain code handling that IOG provides in the Constraints module? Or do you see the above problems with that implementation as well?

[alessandrokonrad]

The Contraints module helps you to build the tx in the way you need it. Lucid allows you to do exactly the same. So yeah this is covered as well. Basically any kind of transaction should be possible regardless of what you add and the coin selection should be able to find the right inputs.

[nicolasayotte]

You can run a one-pass filter on the utxos to split off those that have the assets you are looking for, those that contain only Ada, and those that contain Ada and assets your are not looking for.

I also distinguish between utxos that have only the asset I am looking for.

Within those filtered results, you can run your Random Sampling in this order:

Asset(s)

1. Random sample through utxos with only the required asset as needed
2. Random sample through utxos with the required assed and other assets as needed

Ada

1. Random sample (or even largest-first) through the utxos with only ada as needed
2. Random sample through all utxos that have not been chosen yet

No improvement step because you are guaranteed to be done as every pick is an improvement...

Important Note: Do not forget to increase the target quantity of Ada within the utxos selection loop to account for the carry necessary to send back the change output. The change output might contain a large number of random assets and the Ada necessary to send it back in change is NOT Ada that can be counted towards your coin selection target.

[nicolasayotte]

More opinonated take : At the last step where you need to scrounge for Ada within a bunch of utxos with assets you do not need, I actually do a weighted sorting where the weight is

weight = Ada / (1 + Number of Assets ^ 2)

and pick from those in order from the largest to the smallest so as to minimize my grabbing random junk. But I admit this is might be a matter of (even more) debate.

[mateusap1]

Was this ever implemented? I would love to have a utils function in Lucid to do random improve coin selection for me, right now it looks like Nami is not really doing it by default with .getUTxOs

[gavinharris-dev]

I wonder if this proposal could work with Lucid: cardano-foundation/CIPs#785

There is a sample implementation in CardanoSharp (C# library)

Implementation Code Example

An implementation example for all 3 core functions involved in the Optimized Random Improve selection can be found in this fork of the CardanoSharp Library here:

Aggregator Function - https://github.com/Orion-Crypto/cardanosharp-wallet/blob/optimized-coin-selection-example/CardanoSharp.Wallet/CIPs/CIP2/CoinSelectionService.cs
Select Inputs Function - https://github.com/Orion-Crypto/cardanosharp-wallet/blob/optimized-coin-selection-example/CardanoSharp.Wallet/CIPs/CIP2/CoinSelectionStrategies/OptimizedRandomImproveStrategy.cs
Change Selection Function - https://github.com/Orion-Crypto/cardanosharp-wallet/blob/optimized-coin-selection-example/CardanoSharp.Wallet/CIPs/CIP2/ChangeCreationStrategies/MultiSplitChangeSelectionStrategy.cs