An implementation of the Random-Improve coin selection algorithm.

Overview

The Random-Improve coin selection algorithm works in two phases, by first selecting UTxO entries at random to pay for each of the given outputs, and then attempting to improve upon each of the selections.

Phase 1: Random Selection

In this phase, the algorithm randomly selects a minimal set of UTxO entries to pay for each of the given outputs.

During this phase, the algorithm:

• processes outputs in descending order of coin value.
• maintains a remaining UTxO set, initially equal to the given UTxO set parameter.

For each output of value v, the algorithm randomly selects entries from the remaining UTxO set, until the total value of selected entries is greater than or equal to v. The selected entries are then associated with that output, and removed from the remaining UTxO set.

This phase ends when every output has been associated with a selection of UTxO entries.

However, if the remaining UTxO set is completely exhausted before all outputs can be processed, the algorithm terminates with an error.

Phase 2: Improvement

In this phase, the algorithm attempts to improve upon each of the UTxO selections made in the previous phase, by conservatively expanding the selection made for each output.

During this phase, the algorithm:

• processes outputs in ascending order of coin value.
• continues to maintain the remaining UTxO set produced by the previous phase.
• maintains an accumulated coin selection, which is initially empty.

For each output of value v, the algorithm:

1. Calculates a target range for the total value of inputs used to pay for that output, defined by the triplet:

   (minimum, ideal, maximum) = (v, 2v, 3v)

2. Attempts to improve upon the existing UTxO selection for that output, by repeatedly selecting additional entries at random from the remaining UTxO set, stopping when the selection can be improved upon no further.

   A selection with value v1 is considered to be an improvement over a selection with value v0 if all of the following conditions are satisfied:

   • Condition 1: we have moved closer to the ideal value:

     abs (ideal − v1) < abs (ideal − v0)

   • Condition 2: we have not exceeded the maximum value:

     v1 ≤ maximum

   • Condition 3: when counting cumulatively across all outputs considered so far, we have not selected more than the maximum number of UTxO entries specified by limit.
3. Creates a change value for the output, equal to the total value of the final UTxO selection for that output minus the value v of that output.

4. Updates the accumulated coin selection:

   • Adds the output to outputs.
   • Adds the improved UTxO selection to inputs.
   • Adds the change value to change.

This phase ends when every output has been processed, or when the remaining UTxO set has been exhausted, whichever occurs sooner.

Termination

When both phases are complete, the algorithm terminates.

The accumulated coin selection and remaining UTxO set are returned to the caller.

Failure Modes

The algorithm terminates with an error if:

1. The total value of the initial UTxO set (the amount of money available) is less than the total value of the output list (the amount of money required).

   See: InputValueInsufficientError.

2. The number of entries in the initial UTxO set is smaller than the number of requested outputs.

   Due to the nature of the algorithm, at least one UTxO entry is required for each output.

   See: InputCountInsufficientError.

3. Due to the particular distribution of values within the initial UTxO set, the algorithm depletes all entries from the UTxO set before it is able to pay for all requested outputs.

   See: InputsExhaustedError.

4. The number of UTxO entries needed to pay for the requested outputs would exceed the upper limit specified by limit.

   See: InputLimitExceededError.

Motivating Principles

There are several motivating principles behind the design of the algorithm.

Principle 1: Dust Management

The probability that random selection will choose dust entries from a UTxO set increases with the proportion of dust in the set.

Therefore, for a UTxO set with a large amount of dust, there's a high probability that a random subset will include a large amount of dust.

Principle 2: Change Management

Ideally, coin selection algorithms should, over time, create a UTxO set that has useful outputs: outputs that will allow us to process future payments with a minimum number of inputs.

If for each payment request of value v we create a change output of roughly the same value v, then we will end up with a distribution of change values that matches the typical value distribution of payment requests.

Principle 3: Performance Management

Searching the UTxO set for additional entries to improve our change outputs is only useful if the UTxO set contains entries that are sufficiently small enough. But it is precisely when the UTxO set contains many small entries that it is less likely for a randomly-chosen UTxO entry to push the total above the upper bound.

Since: 1.0.0