Open alessandrokonrad opened 2 years ago
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?
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.
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)
Ada
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.
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.
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
I wonder if this proposal could work with Lucid: https://github.com/cardano-foundation/CIPs/pull/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
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:
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 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:
c) Loop for n iterations (n = 100 currently) and do:
d) After the improvement iterations we get our final input set.