Copyright | © 2018-2020 IOHK |
---|---|

License | Apache-2.0 |

Safe Haskell | None |

Language | Haskell2010 |

This module contains an implementation of the **Random-Improve** coin
selection algorithm.

## Synopsis

- randomImprove :: (Ord i, Ord o, MonadRandom m) => CoinSelectionAlgorithm i o m

# Documentation

randomImprove :: (Ord i, Ord o, MonadRandom m) => CoinSelectionAlgorithm i o m Source #

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

**. The selected entries are then associated with that output, and removed from the**

*v**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:

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

*minimum*,*ideal*,*maximum*) = (*v*,*2v*,*3v*)**Attempts to**for that output, by repeatedly selecting additional entries at random from the*improve*upon the*existing UTxO selection**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`

.

**Creates a**for the output, equal to the total value of the*change value**final UTxO selection*for that output minus the value*v*of that output.**Updates the**:*accumulated coin selection*

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:

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*).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.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`

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

**, then we will end up with a distribution of change values that matches the typical value distribution of payment requests.**

*v*### 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*