This article describes, inhuman-readable terms, the coin selectionalgorithms used byCardanoWallet and other parts ofthe Cardano ecosystem.
In the context of this article,coin selection refers to the process ofchoosingunspent coins from a wallet (orUTxO set) in order topay money to one or more recipients.
This document was written to help people gain an understanding of the coinselection algorithms used in Cardanowithout having to read through andunderstand Cardano source code.
We aim to provide descriptions of algorithms that:
Where appropriate, we also provide mathematical descriptions, for added clarity.
Coin selection is a large, complex topic, with many difficult problems tosolve. However, all software that performs coin selection must ultimately dealwith at least the following pair of problems:
This article concerns itself with theformer problem ofhow to generate acoin selection.
Problems relating to network fees, and how to adjust coin selections to pay forsuch fees, are outside the scope of this article.
This section introduces the fundamental concepts behind coin selection,provides a discussion of why coin selection is a non-trivial problem, anddescribes important goals of coin selection algorithms.
Coin selection is the process of choosing unspent coins from a wallet in orderto pay money to one or more recipients.
In the familiar world ofphysical money, our wallets hold value in the formofcoins and banknotes.
When making a payment to someone, we typically select a combination of coinsand banknotes from a wallet that, when added together, have enough value tocover the amount required.
Ideally, we'd always be able to selectjust enough to cover the exact amount.However, given that coins and banknotes have fixed values (and cannot besubdivided without destroying their value), it's often impossible to select theexact amount required. In such cases, we typically give the recipientmorethan the required amount, and then receive the excess value back aschange.
: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 hasfiveone-euro coins, andoneten-euro note.
Note that there isno combination of coins (or notes) in her wallet thatwhen added together give a total of €2.50, but thereare several possiblecombinations thatexceed the total.
To solve this problem, Alice selectsone of these combinations:threeone-euro coins. She uses the coins to make the payment, and then receivesone 50-cent coin as change.
Similarly to how a physical wallet holds value in the form ofunspent coinsand banknotes, a Cardano wallet holds value in the form ofunspenttransaction outputs. Anunspent transactionoutput is the result of a previous transactionthat transferred money to the wallet, where the value has not yet been spent byanother transaction. Each unspent transaction output has an associatedcoinvalue, and the total value of a wallet is thesum of these coinvalues. Collectively, the set of unspent transaction outputs is known as theUTxO set.
When using a Cardano wallet to make a payment, the wallet software must selecta combination of unspent outputs from the wallet'sUTxO set, sothat 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 setcannot be subdivided, and must either be spent completely in a giventransaction, or not be spent at all. Similarly to a transaction with physicalmoney, the wallet software must select a combination of unspent outputs whosetotal value isgreater than the target amount, and then arrange thatchangeis paid back to the wallet.
Coin selection refers to the process of selecting a combination of unspentoutputs from a wallet'sUTxO set in order to make one or morepayments, and computing the set of change to be paid back to the wallet.
There are a number of issues which make the problem of coin selection morecomplicated than would initially appear.
Eachtransaction has amaximum size, as defined by theprotocol. The size of a transaction increases as we add moreinputs oroutputs.
Therefore, there's a practical limit on the number of coins we can select forany given transaction.
One simple strategy forselecting coins might be to mimic what we do whenmaking a payment with coins and banknotes in the physical world. By giving therecipient 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 UTxO-based wallet has anundesirable effect: minimizing the total value of selected coins will alsominimize the value of change returned to the wallet. When repeated over time,this strategy will tend to cause an accumulation of tiny outputs in thewallet'sUTxO set known asdust.
Dust outputs are a problem, because even if the total value of dust in a walletis more than enough to cover a given target amount, if we attempt to includethat dust in a given transaction, we may run out of space (by reaching thetransaction size limit) before we can coverthe target amount.
For more information on dust avoidance, seeSelf Organisation in CoinSelection.
One simple strategy forgenerating change might be to mimic what a shopassistant does when accepting a payment in the real world, which is to minimizethenumber of coins and banknotes that they return to the customer. This isbeneficial for the shop, as it reduces the chances of them running out ofchange, and beneficial for the customer, as it reduces the amount of changethat they have to carry around in their wallet.
Analogously, when generating change for a UTxO-based wallet, we might betempted to use the simple strategy of just creating a singlechangeoutput with the exact excess value.
However, using this strategy has an undesirable effect: the repeated act ofminimizing the number of change outputs will tend (over time) to reduce thenumber of entries in a wallet'sUTxO set. This is bad for tworeasons:
Having a smallUTxO set limits the number of future paymentsthat we can make in parallel.
The approach of coalescing all change into a single output is widelyconsidered to have negative privacy implications.
In light of the issues described above, we'd ideally like for our coin selectionalgorithms to be able to:
limit, over the course of time, the amount ofdust thataccumulates in theUTxO set.
maintain, over the course of time, aUTxO set withusefuloutputs: that is, outputs that allow us to process future payments with areasonably small number ofinputs.
TheBackground section introduces the fundamental conceptsbehind coin selection, provides a discussion of why coin selection isa non-trivial problem, and describes the goals of coin selection algorithms.
TheInterface section gives a description of the common interfaceunifying all coin selection algorithms used within Cardano Wallet, the standardparameter types, result types, and error types used by this interface, and adescription of the properties that all conforming implementations are expectedto satisfy.
TheAlgorithms section gives detailed descriptions of each ofthe individual coin selection algorithms used in Cardano Wallet, along withstep-by-step descriptions of the computations involved.
TheReference Implementations section provideslinks to reference implementations of each algorithm in various languages.
This section defines common terms that are used throughout this document.
Anaddress is a unique identifier that represents a payment recipient, adestination for a payment.
Addresses are typically owned (and generated) by individual wallets.
In general, coin selection algorithms are agnostic to the type of addressesused to identify payment recipients. Any address type may be used, so long asthe set of possible addresses is totally-ordered.
Acoin value is a non-negative integer value that represents a number ofLovelace.
OneAda isexactly equalto one million Lovelace.
In aUTxO-based blockchain, atransaction is a binding betweeninputs andoutputs.
input #1 >---+ +---> output #1 \ /input #2 >-----+------+ / \input #3 >---+ +---> output #2Atransaction input is aunique reference to a singleoutput from a previous transaction.
In general, coin selection algorithms are agnostic to the type of referencesused to identify outputs from previous transactions. Any type may be used, solong as the set of possible references is totally-ordered, and so long as it ispossible to determine thecoin value associated with any givenreference.
In the case of Cardano and other UTxO-based blockchains, this referencegenerally consists of a pair of values (h,n), where:
Atransaction output consists of a pair of values (a,v), where:
Aspent transaction output is anoutput from anexistingtransaction that has already been referenced as aninput within a later transaction on the blockchain.
In effect, thecoin value associated with that transactionoutput has beenspent, and cannot be reused.
Anunspent transaction output is anoutput from anexistingtransaction that has not yet been referenced as aninput within a later transaction.
In effect, thecoin value associated with that transactionoutput hasnot yet been spent, and is still available.
AUTxO set is a set ofunspent transactionoutputs.
This term is commonly used in two ways:
To describe thecomplete set of all unspent transaction outputs within ablockchain.
To describe thesubset of unspent transaction outputs associated withawallet. The UTxO set of a wallet represents the total unspent valueassociated with that wallet.
From the point of view of a coin selection algorithm, each member of a UTxO setcan be represented as a pair of the form (u,v), where:
In general, coin selection algorithms are agnostic to the type of referencesused to identify unspent outputs from previous transactions. Any type may beused, so long as the set of possible references is totally-ordered.
In practice however, the type of each unique referenceu is equivalentto the type of atransaction input, as transaction inputsare simply references to unspent outputs from previous transactions.
In the context of a wallet, achange output is atransactionoutput that transfers valueback to the wallet, ratherthan to an external payment recipient. Theaddress associated witha change output is generated by the wallet, and belongs to the wallet.
Change ouputs are necessary in a UTxO-based blockchain, as the value associatedwith any giventransaction input must be spententirelyby the transaction that includes it.
When selecting entries from aUTxO set to include as inputs in atransaction, a coin selection algorithm will generally not be able to selectinputs that precisely match the total value of all payments to externalrecipients, and will therefore need to select more than is strictly required.To avoid the destruction of value, selection algorithms createchange outputsto return the excess value back to the wallet.
Adust output is atransaction output with anassociatedcoin value that is:
Dust outputs are a problem, because even if the total value of dust in a walletis more than enough to cover a given payment amount, if we attempt to includethat dust in a given transaction, we may run out of space (by reaching thetransaction size limit) before we can coverthe target amount.
All coin selection algorithms used by Cardano Wallet implement acommon interface.
At the most fundamental level, a coin selection algorithm is amathematicalfunction that when applied to arequested outputset and aninitial UTxO set,will produce acoin selection: the basis for atransaction in a UTxO-based blockchain.
This section describes:
In this section, the termscoin selection algorithm andcoin selectionfunction will be used interchangeably.
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 oftransaction outputs.
Initial UTxO Set
AUTxO set from which the coin selection algorithm can selectentries, to cover payments listed in therequested outputset.
In the context of a wallet, this parameter would normally be assigned withthe wallet's completeUTxO set, giving the coin selectionalgorithm access to the total value associated with that wallet.
Maximum Input Count
Anupper bound on the number of UTxO entries that the coin selectionalgorithm is permitted to select from theinitial UTxOset.
This parameter is necessary for blockchains that impose an upper limit onthe size of transactions.
All coin selection functions produce the following result values:
Coin Selection
Acoin selection is the basis for atransaction in aUTxO-based blockchain.
It is a record with three fields:
A set ofinputs, equivalent to a subset of theinitial UTxO set.
From the point of view of awallet, this represents the value thathas been selected from the wallet in order to cover the total paymentvalue.
A set ofoutputs (seetransaction output).
Represents the set of payments to be made to recipient addresses.
A set ofchange values (seechange output),where each change value is simply acoin value.
From the point of view of awallet, this represents the change to bereturned to the wallet.
Remaining UTxO Set
Theremaining UTxO set is a subset of theinitial UTxOset.
It represents the set of values that remain after the coin selectionalgorithm has removed values to pay for entries in therequested outputset.
In the context of awallet, if a coin selection algorithm is applied tothe wallet'scomplete UTxO set, then theremaining UTxO set representstheupdated UTxO set of that wallet.
All coin selection algorithms satisfy a common set ofproperties: generalrules that govern the relationship between theparameters supplied to coinselection functions and theresults they are allowed to produce.
This property states that the total value ofinputs in the resultingcoinselection result is sufficient tocover the total value oftherequested output set.
In particular:
Where:
vrequested
is the total value of therequested output set
vselected
is the total value of theinputs field of thecoinselection result.
This property states that the correct amount ofchange was generated.
In particular:
Where:
vchange
is the total value of thechange field of thecoinselection result.
vrequested
is the total value of therequested output set
vselected
is the total value of theinputs field of thecoinselection result.
This property states that every entry in theinitial UTxOset is included ineither the inputs set of the generatedcoin selection,or in theremaining UTxOset, butnot both.
If a UTxO entryis selected by the coin selection algorithm, it isincluded in thecoin selection inputs set.
If a UTxO entry isnot selected by the coin selection algorithm, it isincluded in theremaining UTxO set.
The following laws hold:
And:
Where:
Uinitial
is theinitial UTxO set.
Uremaining
is theremaining UTxO set.
Uselected
is the value of theinputs field of thecoin selectionresult.
This property states that therequested output setisconserved in thecoin selection result.
In particular, theoutputs field of thecoin selectionresult should beequal to therequested output set.
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 theinitialUTxO set (the amount of moneyavailable) islessthan the the total value of all entries in therequested outputset (the amount of moneyrequired).
UTxO Not Fragmented Enough
This failure occurs when thenumber of entries in theinitial UTxOset issmaller than the number of entries in therequested output set, for algorithms that imposethe restriction that a single UTxO entry can only be used to pay foratmost one output.
UTxO Fully Depleted
This failure occurs if the algorithm depletes all entries from theinitialUTxO setbefore it is able to pay for all outputs intherequested output set.
This can happeneven if the total value of entries within theinitialUTxO set isgreater than the total value of allentries in therequested output set, due tovarious restrictions that coin selection algorithms impose on themselveswhen selecting UTxO entries.
Maximum Input Count Exceeded
This failure occurs when another input must be selected by the algorithm inorder to continue making progress, but doing so will increase the size ofthe resulting selection beyond an acceptable limit, specified by themaximum input count parameter.
This section describes the coin selection algorithms used by Cardano Wallet,along with step-by-step descriptions of the computations involved.
All algorithms implement acommon interface, as described in theInterface section.
There are two main algorithms used by Cardano Wallet:
In general, Cardano Wallet givespriority to theRandom-Improve algorithm, as experimental evidence showsthat it performs better atminimising dust and maintaining a UTxO setwithuseful outputs. (SeeSelf Organisation in CoinSelection for more details.)
However, in rare cases, theRandom-Improve algorithm mayfail to produce a result. In such cases, Cardano Wallet will fall back to theLargest-First algorithm.
TheLargest-First coin selection algorithm considers UTxO set entriesindescending order of value, from largest to smallest.
When applied to a set ofrequested outputs, thealgorithm repeatedly selects entries from theinitial UTxOset until the total value of selected entries isgreaterthan or equal to the total value of requested outputs.
The name of the algorithm is taken from the idea that thelargest UTxOentry is always selectedfirst. Specifically:
A given UTxO entryu1 withvaluev1 can be selected if and only if there is no otherunselected entryu2 with valuev2 wherev2 >v1.
At all stages of processing, the algorithm maintains the following pieces ofstate:
Available UTxO List
This is initially equal to theinitial UTxO set,sorted intodescending order of coin value.
Thehead of the list is always the remaining UTxO entry with thelargestcoin value.
Entries are incrementally removed from thehead of the list as thealgorithm proceeds, until enough value has been selected.
Selected UTxO Set
This is initially equal to the empty set.
The algorithm proceeds according to the following sequence of steps:
Step 1
If theavailable UTxO list isempty:
If theavailable UTxO list isnot empty:
Step 2
Compare the total sizenselected of theselected UTxOset with themaximum inputcountnmax.
Ifnselected >nmax then:
Ifnselected ≤nmax then:
Step 3
Compare the total valuevselected of theselected UTxOset to the total valuevrequested oftherequested output set:
Step 4
Return acoin selection result where:
Theinputs set is equal to theselected UTxOset.
Theoutputs set is equal to therequested outputset.
Ifvselected >vrequested then:
Ifvselected =vrequested then:
TheRandom-Improve coin selection algorithm works intwo phases:
In thefirst phase, the algorithm iterates through each of therequested outputs indescending order of coinvalue, fromlargest tosmallest. For each output, the algorithmrepeatedly selects entriesat random from theinitial UTxOset, until each requested output has been associatedwith a set of UTxO entries whosetotal value is enough to pay for thatouput.
In thesecond phase, the algorithm attempts toexpand eachexisting UTxO selection withadditional values taken at random from theinitial UTxO set, to the point where the total valueof each selection is as close as possible totwice the value of itsassociated output.
After the above phases are complete, for each output of valuevoutput and accompanying UTxO selection of valuevselection, the algorithm generates asingle change outputof valuevchange, where:
vchange=vselection−voutput
Since the goal of the second phase was to expand each selection to the pointwhere its total value isapproximately twice the value of its associatedoutput, this corresponds to a change output whose target value isapproximately equal to the value of the output itself:
vchange=vselection−voutput
vchange≈ 2voutput−voutput
vchange≈voutput
The Random-Improve algorithm imposes the following cardinality restriction:
As a result of this restriction, the algorithm will fail with aUTxO NotFragmented Enough error if the number of entriesin theinitial UTxO set issmaller than the number ofentries in therequested output set.
At all stages of processing, the algorithm maintains the following pieces ofstate:
Available UTxO Set
This is initially equal to theinitial UTxO set.
Accumulated Coin Selection
The accumulated coin selection is acoin selection whereall fields are initially equal to theempty set.
The algorithm proceeds in two phases.
In this phase, the algorithm iterates through each of therequestedoutputs in descending order of coin value, fromlargest to smallest.
For each output of valuev, the algorithm repeatedly selects entries atrandom from theavailable UTxO set, until thetotalvalue of selected entries is greater than or equal tov. The selectedentries are thenassociated with that output, andremoved from theavailable UTxO set.
This phase ends whenevery output has been associated with a selection ofUTxO entries.
In this phase, the algorithm attempts to improve upon each of the UTxOselections made in the previous phase, by conservatively expanding theselection made for each output in order to generate improved changevalues.
During this phase, the algorithm:
processes outputs inascending order of coin value.
continues to select values from theavailable UTxOset.
incrementally populates theaccumulated coin selection.
For each output of valuev, the algorithm:
Calculates atarget range for the total value of inputs used topay 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 theavailableUTxO set, stopping when the selection can beimproved upon no further.
A selection with valuev1 is considered to be animprovement over a selection with valuev0 ifallof the following conditions are satisfied:
Condition 1: we have moved closer to theideal value:
abs (ideal −v1) <abs (ideal −v0)
Condition 2: we have not exceeded themaximum value:
v1 ≤maximum
Condition 3: when counting cumulatively across all outputsconsidered so far, we have not selected more than themaximum numberof UTxO entries specified byMaximum InputCount.
Creates achange value for the output, equal to the total valueof theimproved UTxO selection for that output minus the valuevof that output.
Updates theaccumulated coinselection:
This phase ends when every output has been processed,or when theavailable UTxO set has been exhausted, whichever occurssooner.
When both phases are complete, the algorithm terminates.
Theaccumulated coin selection is returnedto the caller as thecoin selection result.
Theavailable UTxO set is returned to the caller as theremaining UTxO set result.
-
There are several motivating principles behind the design of the algorithm.
The probability that random selection will choose dust entries from a UTxOsetincreases with the proportion of dust in the set.
Therefore, for a UTxO set with a large amount of dust, there's a highprobability that a random subset will include a large amount of dust.
Over time, selecting entries randomly in this way will tend tolimit theamount of dust that accumulates in the UTxO set.
As mentioned in theGoals section, it isdesirable that coin selection algorithms, over time, are able to create UTxOsets that haveuseful outputs: outputs that will allow us to process futurepayments with areasonably small number of inputs.
If for each payment request of valuev we create a change output ofroughly the same valuev, then we will end up with a distribution ofchange values that matches the typical value distribution of paymentrequests.
: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 outputswith a total value of around €2.00.
As she frequently makes payments for similar amounts, transactions created byher wallet will also frequently produce change coins of around €1.00 in value.
Over time, her wallet will self-organize to contain multiple coins of around€1.00, which are useful for the kinds of payments that Alice frequently makes.
Searching the UTxO set for additional entries toimprove our change outputsisonly useful if the UTxO set contains entries that are sufficientlysmall enough. But it is precisely when the UTxO set contains many smallentries that it is less likely for a randomly-chosen UTxO entry to push thetotal above the upper bound.
Title Self Organisation in Coin Selection Author Edsko de Vries Year 2018 Location https://iohk.io/en/blog/posts/2018/07/03/self-organisation-in-coin-selection/ This article introduces theRandom-Improve coin selectionalgorithm, invented byEdsko de Vries.
It describes the three principles of self-organisation that inform thealgorithm's design, and provides experimental evidence to demonstrate thealgorithm's effectiveness at maintaining healthy UTxO sets over time.
Reference implementations of theLargest-First algorithm areavailable in the following languages:
| Language | Documentation | Source |
|---|---|---|
| Haskell | Documentation | Source |
Reference implementations of theRandom-Improve algorithmare available in the following languages:
| Language | Documentation | Source |
|---|---|---|
| Haskell | Documentation | Source |
This CIP is licensed underCC-BY-4.0.