Coin Selection Algorithms for Cardano
Abstract
This article describes, in humanreadable terms, the coin selection algorithms used by Cardano Wallet and other parts of the Cardano ecosystem.
In the context of this article, coin selection refers to the process of choosing unspent coins from a wallet (or UTxO set) in order to pay money to one or more recipients.
Motivation: why is this CIP necessary?
This document was written to help people gain an understanding of the coin selection algorithms used in Cardano without having to read through and understand Cardano source code.
We aim to provide descriptions of algorithms that:
 don't require prior experience with any particular programming language;
 are understandable for people who are unfamiliar with coin selection;
 are precise enough for software engineers to be able to reimplement these algorithms in their preferred programming languages.
Where appropriate, we also provide mathematical descriptions, for added clarity.
Scope
Coin selection is a large, complex topic, with many difficult problems to solve. However, all software that performs coin selection must ultimately deal with at least the following pair of problems:
 How to generate a coin selection, by choosing unspent coins from a wallet (or UTxO set) in order to pay money to one or more recipients.
 How to adjust a coin selection in order to pay for a network fee, so that the coin selection can be published as a transaction on the blockchain.
This article concerns itself with the former problem of how to generate a coin selection.
Problems relating to network fees, and how to adjust coin selections to pay for such fees, are outside the scope of this article.
Background
This section introduces the fundamental concepts behind coin selection, provides a discussion of why coin selection is a nontrivial problem, and describes important goals of coin selection algorithms.
What is Coin Selection?
Coin selection is the process of choosing unspent coins from a wallet in order to pay money to one or more recipients.
Coin Selection in the Physical World
In the familiar world of physical money, our wallets hold value in the form of coins and banknotes.
When making a payment to someone, we typically select a combination of coins and banknotes from a wallet that, when added together, have enough value to cover the amount required.
Ideally, we'd always be able to select just enough to cover the exact amount. However, given that coins and banknotes have fixed values (and cannot be subdivided without destroying their value), it's often impossible to select the exact amount required. In such cases, we typically give the recipient more than the required amount, and then receive the excess value back as change.
:bulb: Example
Alice wishes to pay for her lunch.
The total price comes to €2.50 (2 euros and 50 cents). In her wallet, she has five oneeuro coins, and one teneuro note.
Note that there is no combination of coins (or notes) in her wallet that when added together give a total of €2.50, but there are several possible combinations that exceed the total.
To solve this problem, Alice selects one of these combinations: three oneeuro coins. She uses the coins to make the payment, and then receives one 50cent coin as change.
Coin Selection in Cardano
Similarly to how a physical wallet holds value in the form of unspent coins and banknotes, a Cardano wallet holds value in the form of unspent transaction outputs. An unspent transaction output is the result of a previous transaction that transferred money to the wallet, where the value has not yet been spent by another transaction. Each unspent transaction output has an associated coin value, and the total value of a wallet is the sum of these coin values. Collectively, the set of unspent transaction outputs is known as the UTxO set.
When using a Cardano wallet to make a payment, the wallet software must select a combination of unspent outputs from the wallet's UTxO set, so that the total value of selected outputs is enough to cover the target amount.
Just as with physical coins and notes, unspent outputs from the UTxO set cannot be subdivided, and must either be spent completely in a given transaction, or not be spent at all. Similarly to a transaction with physical money, the wallet software must select a combination of unspent outputs whose total value is greater than the target amount, and then arrange that change is paid back to the wallet.
Coin selection refers to the process of selecting a combination of unspent outputs from a wallet's UTxO set in order to make one or more payments, and computing the set of change to be paid back to the wallet.
Why is Coin Selection NonTrivial?
There are a number of issues which make the problem of coin selection more complicated than would initially appear.
The Transaction Size Limitation
Each transaction has a maximum size, as defined by the protocol. The size of a transaction increases as we add more inputs or outputs.
Therefore, there's a practical limit on the number of coins we can select for any given transaction.
The Problem of Dust
One simple strategy for selecting coins might be to mimic what we do when making a payment with coins and banknotes in the physical world. By giving the recipient an amount that's as close as possible to the amount they're expecting, we can minimize the amount of change they need to return to us.
However, trying to replicate this strategy with a UTxObased wallet has an undesirable effect: minimizing the total value of selected coins will also minimize the value of change returned to the wallet. When repeated over time, this strategy will tend to cause an accumulation of tiny outputs in the wallet's UTxO set known as dust.
Dust outputs are a problem, because even if the total value of dust in a wallet is more than enough to cover a given target amount, if we attempt to include that dust in a given transaction, we may run out of space (by reaching the transaction size limit) before we can cover the target amount.
For more information on dust avoidance, see Self Organisation in Coin Selection.
The Problem of Concurrency
One simple strategy for generating change might be to mimic what a shop assistant does when accepting a payment in the real world, which is to minimize the number of coins and banknotes that they return to the customer. This is beneficial for the shop, as it reduces the chances of them running out of change, and beneficial for the customer, as it reduces the amount of change that they have to carry around in their wallet.
Analogously, when generating change for a UTxObased wallet, we might be tempted to use the simple strategy of just creating a single change output with the exact excess value.
However, using this strategy has an undesirable effect: the repeated act of minimizing the number of change outputs will tend (over time) to reduce the number of entries in a wallet's UTxO set. This is bad for two reasons:

Having a small UTxO set limits the number of future payments that we can make in parallel.

The approach of coalescing all change into a single output is widely considered to have negative privacy implications.
Goals of Coin Selection Algorithms
In light of the issues described above, we'd ideally like for our coin selection algorithms to be able to:

limit, over the course of time, the amount of dust that accumulates in the UTxO set.

maintain, over the course of time, a UTxO set with useful outputs: that is, outputs that allow us to process future payments with a reasonably small number of inputs.
Specification
Structure
The Background section introduces the fundamental concepts behind coin selection, provides a discussion of why coin selection is a nontrivial problem, and describes the goals of coin selection algorithms.
The Interface section gives a description of the common interface unifying all coin selection algorithms used within Cardano Wallet, the standard parameter types, result types, and error types used by this interface, and a description of the properties that all conforming implementations are expected to satisfy.
The Algorithms section gives detailed descriptions of each of the individual coin selection algorithms used in Cardano Wallet, along with stepbystep descriptions of the computations involved.
The Reference Implementations section provides links to reference implementations of each algorithm in various languages.
Contents
 Abstract
 Motivation
 Specification
 Rationale: how does this CIP achieve its goals?
 Path to Active
 Copyright
Definitions
This section defines common terms that are used throughout this document.
Address
An address is a unique identifier that represents a payment recipient, a destination for a payment.
Addresses are typically owned (and generated) by individual wallets.
In general, coin selection algorithms are agnostic to the type of addresses used to identify payment recipients. Any address type may be used, so long as the set of possible addresses is totallyordered.
Coin Value
A coin value is a nonnegative integer value that represents a number of Lovelace.
One Ada is exactly equal to one million Lovelace.
Transaction
In a UTxObased blockchain, a transaction is a binding between inputs and outputs.
input #1 >+ +> output #1
\ /
input #2 >++
/ \
input #3 >+ +> output #2
Transaction Input
A transaction input is a unique reference to a single output from a previous transaction.
In general, coin selection algorithms are agnostic to the type of references used to identify outputs from previous transactions. Any type may be used, so long as the set of possible references is totallyordered, and so long as it is possible to determine the coin value associated with any given reference.
In the case of Cardano and other UTxObased blockchains, this reference generally consists of a pair of values (h, n), where:
 h is a unique identifier for an existing transaction t;
 n is a 0based integer index into the output list of transaction t.
Transaction Output
A transaction output consists of a pair of values (a, v), where:
 a is the address of a recipient.
 v is the coin value to pay to the recipient.
Spent Transaction Output
A spent transaction output is an output from an existing transaction that has already been referenced as an input within a later transaction on the blockchain.
In effect, the coin value associated with that transaction output has been spent, and cannot be reused.
Unspent Transaction Output
An unspent transaction output is an output from an existing transaction that has not yet been referenced as an input within a later transaction.
In effect, the coin value associated with that transaction output has not yet been spent, and is still available.
UTxO Set
A UTxO set is a set of unspent transaction outputs.
This term is commonly used in two ways:

To describe the complete set of all unspent transaction outputs within a blockchain.

To describe the subset of unspent transaction outputs associated with a wallet. The UTxO set of a wallet represents the total unspent value associated with that wallet.
From the point of view of a coin selection algorithm, each member of a UTxO set can be represented as a pair of the form (u, v), where:
 u is a unique reference to an unspent output from a previous transaction.
 v is the coin value associated with u.
In general, coin selection algorithms are agnostic to the type of references used to identify unspent outputs from previous transactions. Any type may be used, so long as the set of possible references is totallyordered.
In practice however, the type of each unique reference u is equivalent to the type of a transaction input, as transaction inputs are simply references to unspent outputs from previous transactions.
Change Output
In the context of a wallet, a change output is a transaction output that transfers value back to the wallet, rather than to an external payment recipient. The address associated with a change output is generated by the wallet, and belongs to the wallet.
Change ouputs are necessary in a UTxObased blockchain, as the value associated with any given transaction input must be spent entirely by the transaction that includes it.
When selecting entries from a UTxO set to include as inputs in a transaction, a coin selection algorithm will generally not be able to select inputs that precisely match the total value of all payments to external recipients, and will therefore need to select more than is strictly required. To avoid the destruction of value, selection algorithms create change outputs to return the excess value back to the wallet.
Dust Output
A dust output is a transaction output with an associated coin value that is:
 small in comparison to payments typically made by the user of the wallet;
 small in comparison to the marginal fee associated with including it in a transaction.
Dust outputs are a problem, because even if the total value of dust in a wallet is more than enough to cover a given payment amount, if we attempt to include that dust in a given transaction, we may run out of space (by reaching the transaction size limit) before we can cover the target amount.
Interface
All coin selection algorithms used by Cardano Wallet implement a common interface.
At the most fundamental level, a coin selection algorithm is a mathematical function that when applied to a requested output set and an initial UTxO set, will produce a coin selection: the basis for a transaction in a UTxObased blockchain.
This section describes:
 the parameters accepted by all coin selection algorithms;
 the results they produce when successful;
 the error conditions that may occur on failure;
 the properties that apply to all coin selection algorithms: mathematical laws governing the relationships between parameters and results.
In this section, the terms coin selection algorithm and coin selection function will be used interchangeably.
Parameters
All coin selection functions accept the following parameters:

Requested Output Set
A list of payments to be made to recipient addresses, encoded as a list of transaction outputs.

Initial UTxO Set
A UTxO set from which the coin selection algorithm can select entries, to cover payments listed in the requested output set.
In the context of a wallet, this parameter would normally be assigned with the wallet's complete UTxO set, giving the coin selection algorithm access to the total value associated with that wallet.

Maximum Input Count
An upper bound on the number of UTxO entries that the coin selection algorithm is permitted to select from the initial UTxO set.
This parameter is necessary for blockchains that impose an upper limit on the size of transactions.
Results
All coin selection functions produce the following result values:

Coin Selection
A coin selection is the basis for a transaction in a UTxObased blockchain.
It is a record with three fields:

A set of inputs, equivalent to a subset of the initial UTxO set.
From the point of view of a wallet, this represents the value that has been selected from the wallet in order to cover the total payment value.

A set of outputs (see transaction output).
Represents the set of payments to be made to recipient addresses.

A set of change values (see change output), where each change value is simply a coin value.
From the point of view of a wallet, this represents the change to be returned to the wallet.


Remaining UTxO Set
The remaining UTxO set is a subset of the initial UTxO set.
It represents the set of values that remain after the coin selection algorithm has removed values to pay for entries in the requested output set.
In the context of a wallet, if a coin selection algorithm is applied to the wallet's complete UTxO set, then the remaining UTxO set represents the updated UTxO set of that wallet.
Properties
All coin selection algorithms satisfy a common set of properties: general rules that govern the relationship between the parameters supplied to coin selection functions and the results they are allowed to produce.
Coverage of Payments
This property states that the total value of inputs in the resulting coin selection result is sufficient to cover the total value of the requested output set.
In particular:
 vselected ≥ vrequested
Where:

vrequested
is the total value of the requested output set

vselected
is the total value of the inputs field of the coin selection result.
Correctness of Change
This property states that the correct amount of change was generated.
In particular:
 vselected = vrequested + vchange
Where:

vchange
is the total value of the change field of the coin selection result.

vrequested
is the total value of the requested output set

vselected
is the total value of the inputs field of the coin selection result.
Conservation of UTxO
This property states that every entry in the initial UTxO set is included in either the inputs set of the generated coin selection, or in the remaining UTxO set, but not both.

If a UTxO entry is selected by the coin selection algorithm, it is included in the coin selection inputs set.

If a UTxO entry is not selected by the coin selection algorithm, it is included in the remaining UTxO set.
The following laws hold:
 Uinitial ⊃ Uremaining
 Uinitial ⊇ Uselected
And:
 Uremaining ∩ Uselected = ∅
 Uremaining ⋃ Uselected = Uinitial
Where:

Uinitial
is the initial UTxO set.

Uremaining
is the remaining UTxO set.

Uselected
is the value of the inputs field of the coin selection result.
Conservation of Outputs
This property states that the requested output set is conserved in the coin selection result.
In particular, the outputs field of the coin selection result should be equal to the requested output set.
Failure Modes
There are a number of ways in which a coin selection algorithm can fail:

UTxO Balance Insufficient
This failure occurs when the total value of the entries within the initial UTxO set (the amount of money available) is less than the the total value of all entries in the requested output set (the amount of money required).

UTxO Not Fragmented Enough
This failure occurs when the number of entries in the initial UTxO set is smaller than the number of entries in the requested output set, for algorithms that impose the restriction that a single UTxO entry can only be used to pay for at most one output.

UTxO Fully Depleted
This failure occurs if the algorithm depletes all entries from the initial UTxO set before it is able to pay for all outputs in the requested output set.
This can happen even if the total value of entries within the initial UTxO set is greater than the total value of all entries in the requested output set, due to various restrictions that coin selection algorithms impose on themselves when selecting UTxO entries.

Maximum Input Count Exceeded
This failure occurs when another input must be selected by the algorithm in order to continue making progress, but doing so will increase the size of the resulting selection beyond an acceptable limit, specified by the maximum input count parameter.
Algorithms
This section describes the coin selection algorithms used by Cardano Wallet, along with stepbystep descriptions of the computations involved.
All algorithms implement a common interface, as described in the Interface section.
There are two main algorithms used by Cardano Wallet:
In general, Cardano Wallet gives priority to the RandomImprove algorithm, as experimental evidence shows that it performs better at minimising dust and maintaining a UTxO set with useful outputs. (See Self Organisation in Coin Selection for more details.)
However, in rare cases, the RandomImprove algorithm may fail to produce a result. In such cases, Cardano Wallet will fall back to the LargestFirst algorithm.
LargestFirst
The LargestFirst coin selection algorithm considers UTxO set entries in descending order of value, from largest to smallest.
When applied to a set of requested outputs, the algorithm repeatedly selects entries from the initial UTxO set until the total value of selected entries is greater than or equal to the total value of requested outputs.
The name of the algorithm is taken from the idea that the largest UTxO entry is always selected first. Specifically:
A given UTxO entry u1 with value v1 can be selected if and only if there is no other unselected entry u2 with value v2 where v2 > v1.
State
At all stages of processing, the algorithm maintains the following pieces of state:

Available UTxO List
This is initially equal to the initial UTxO set, sorted into descending order of coin value.
The head of the list is always the remaining UTxO entry with the largest coin value.
Entries are incrementally removed from the head of the list as the algorithm proceeds, until enough value has been selected.

Selected UTxO Set
This is initially equal to the empty set.
Computation
The algorithm proceeds according to the following sequence of steps:

Step 1
If the available UTxO list is empty:
 Terminate with a UTxO Balance Insufficient error.
If the available UTxO list is not empty:
 Remove an UTxO entry from the head of the available UTxO list and add it to the selected UTxO set.

Step 2
Compare the total size nselected of the selected UTxO set with the maximum input count nmax.

If nselected > nmax then:
 Terminate with a Maximum Input Count Exceeded error.

If nselected ≤ nmax then:
 Go to step 3.


Step 3
Compare the total value vselected of the selected UTxO set to the total value vrequested of the requested output set:
 If vselected < vrequested then go to step 1.
 If vselected ≥ vrequested then go to step 4.

Step 4
Return a coin selection result where:

The inputs set is equal to the selected UTxO set.

The outputs set is equal to the requested output set.

If vselected > vrequested then:
 The change set contains just a single coin of value (vselected − vrequested).

If vselected = vrequested then:
 The change set is empty.

RandomImprove
The RandomImprove coin selection algorithm works in two phases:

In the first phase, the algorithm iterates through each of the requested outputs in descending order of coin value, from largest to smallest. For each output, the algorithm repeatedly selects entries at random from the initial UTxO set, until each requested output has been associated with a set of UTxO entries whose total value is enough to pay for that ouput.

In the second phase, the algorithm attempts to expand each existing UTxO selection with additional values taken at random from the initial UTxO set, to the point where the total value of each selection is as close as possible to twice the value of its associated output.
After the above phases are complete, for each output of value voutput and accompanying UTxO selection of value vselection, the algorithm generates a single change output of value vchange, where:
vchange = vselection − voutput
Since the goal of the second phase was to expand each selection to the point where its total value is approximately twice the value of its associated output, this corresponds to a change output whose target value is approximately equal to the value of the output itself:
vchange = vselection − voutput
vchange ≈ 2voutput − voutput
vchange ≈ voutput
Cardinality
The RandomImprove algorithm imposes the following cardinality restriction:
 Each entry from the initial UTxO set is used to pay for at most one output from the requested output set.
As a result of this restriction, the algorithm will fail with a UTxO Not Fragmented Enough error if the number of entries in the initial UTxO set is smaller than the number of entries in the requested output set.
State
At all stages of processing, the algorithm maintains the following pieces of state:

Available UTxO Set
This is initially equal to the initial UTxO set.

Accumulated Coin Selection
The accumulated coin selection is a coin selection where all fields are initially equal to the empty set.
Computation
The algorithm proceeds in two phases.
 Phase 1: Random Selection
In this phase, the algorithm iterates through each of the requested outputs in descending order of coin value, from largest to smallest.
For each output of value v, the algorithm repeatedly selects entries at random from the available 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 available UTxO set.
This phase ends when every output has been associated with a selection of UTxO entries.
 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 in order to generate improved change values.
During this phase, the algorithm:

processes outputs in ascending order of coin value.

continues to select values from the available UTxO set.

incrementally populates the accumulated coin selection.
For each output of value v, the algorithm:

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)

Attempts to improve upon the existing UTxO selection for that output, by repeatedly selecting additional entries at random from the available 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 Maximum Input Count.


Creates a change value for the output, equal to the total value of the improved UTxO selection for that output minus the value v of that output.

Updates the accumulated coin selection:
 Adds the output to the outputs field;
 Adds the improved UTxO selection to the inputs field;
 Adds the change value to the change values field.
This phase ends when every output has been processed, or when the available UTxO set has been exhausted, whichever occurs sooner.
Termination
When both phases are complete, the algorithm terminates.
The accumulated coin selection is returned to the caller as the coin selection result.
The available UTxO set is returned to the caller as the remaining UTxO set result.
Rationale
LargestFirst

RandomImprove
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.
Over time, selecting entries randomly in this way will tend to limit the amount of dust that accumulates in the UTxO set.
Principle 2: Change Management
As mentioned in the Goals section, it is desirable that coin selection algorithms, over time, are able to create UTxO sets that have useful outputs: outputs that will allow us to process future payments with a reasonably small 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.
:bulb: Example
Alice often buys bread and other similar items that cost around €1.00 each.
When she instructs her wallet software to make a payment for around €1.00, the software attempts to select a set of unspent transaction outputs with a total value of around €2.00.
As she frequently makes payments for similar amounts, transactions created by her wallet will also frequently produce change coins of around €1.00 in value.
Over time, her wallet will selforganize to contain multiple coins of around €1.00, which are useful for the kinds of payments that Alice frequently makes.
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 randomlychosen UTxO entry to push the total above the upper bound.
External Resources
Self Organisation in Coin Selection
Title Self Organisation in Coin Selection Author Edsko de Vries Year 2018 Location https://iohk.io/en/blog/posts/2018/07/03/selforganisationincoinselection/ This article introduces the RandomImprove coin selection algorithm, invented by Edsko de Vries.
It describes the three principles of selforganisation that inform the algorithm's design, and provides experimental evidence to demonstrate the algorithm's effectiveness at maintaining healthy UTxO sets over time.
Path to Active
Acceptance Criteria
 There exists one or more reference implementations with appropriate testing illustrating the various properties of coinselection stated in this document.
Implementation Plan
Reference Implementations
LargestFirst
Reference implementations of the LargestFirst algorithm are available in the following languages:
Language  Documentation  Source 

Haskell  Documentation  Source 
RandomImprove
Reference implementations of the RandomImprove algorithm are available in the following languages:
Language  Documentation  Source 

Haskell  Documentation  Source 
Copyright
This CIP is licensed under CCBY4.0.