Make it easier for the UTxO selection algorithm to split up unrelated assets.

[jonathanknowles]

Summary

This PR adjusts the UTxO selection algorithm so that when selecting for a given non-ada asset under the optimal selection strategy, we no longer prioritise the selection of UTxOs with fewer numbers of unique assets.

(In contrast, when selecting for ada, we preserve the existing behaviour of always prioritising the selection of pure-ada UTxOs over UTxOs with other assets.)

Motivation

This PR assumes the desirability of the following properties:

• assets that are frequently spent together should, over time, become bundled together within the UTxO set.
• assets that are frequently spent separately should, over time, become located separately within the UTxO set.

One intuitive reason for this is that if a user commonly attempts to create transactions that spend some asset a, then we would like to reduce the (amortised) probability that the user is also forced to spend assets that are unrelated to the transaction, assets that can only be returned as change (which increases the amortised size and cost of transactions).

Furthermore, for a given pair of assets a and b, if the user shifts their spending pattern from one where a and b are typically spent together to a pattern where a and b are typically spent separately, then we ideally want the UTxO selection algorithm, when repeatedly applied over time, to cause the UTxO set to evolve away from a distribution where a and b are typically bundled together toward a distribution where a and b are usually separate.

By removing the bias toward selecting smaller UTxOs over larger UTxOs, we make the following evolutionary changes equally easy:

• Evolution type 1: separation of assets Evolving from a distribution where assets a and b are typically bundled together to a distribution where a and b are usually separate.
• Evolution type 2: colocation of assets Evolving from a distribution where assets a and b are usually separate to a distribution where a and b are typically bundled together.

Without this PR, the former type of evolution is more difficult than the latter, for no good reason.

Context

When the multi-asset UTxO selection algorithm was first written, there was no explicit choice of selection strategy. In order to maximise the chance that a given selection would not exceed transaction size and cost limits, the algorithm used the following fixed strategy when selecting for a given asset a:

1. First, attempt to find a UTxO that contain a and no other assets.
2. Then attempt to find a UTxO that contains a and just one another asset.
3. Finally, attempt to find a UTxO that contains a and any number of additional assets.

However, since then:

1. the UTxO selection algorithm was upgraded to accept a SelectionStrategy parameter, with two possibilities:
   • SelectionStrategyOptimal: attempt to select around twice the minimum possible amount of each asset from the UTxO set, making it possible to generate change outputs that are roughly the same sizes and shapes as the user-specified outputs.
   • SelectionStrategyMinimal: attempt to only select just enough of each asset from the available UTxO set to meet the minimum amount, terminating selection as soon as the minimum amount of each asset has been covered.
2. the balanceTx function was upgraded to use SelectionStrategyOptimal by default, and then fall back to SelectionStrategyMinimal in the event that the optimal strategy fails.

Given that we always have the safe option of falling back to the minimal strategy, it's no longer necessary to artificially constrain the optimal strategy so that it prioritises the selection of UTxOs with fewer assets.

[jonathanknowles]

Closing after discussion with the HAL team.