CardanoSharp: The Process of UTxO selection

Cardano is a UTxO blockchain using an extended version of the model seen in Bitcoin and Litecoin. This makes it fundamentally different from account-based blockchains like Ethereum and Algorand, which track account balances rather than unspent transaction outputs.

So what is a UTxO anyway?

A UTxO, or Unspent Transaction Output, is a fundamental concept in many blockchain systems, including Cardano. In the context of the Cardano blockchain, a UTxO represents an amount of digital currency (like ADA, Cardano's native cryptocurrency) that has been received and is available to be spent in future transactions.

A UTxO is associated with a receiving address and can have native tokens in addition to ADA.

This is an example of a UTxO for address: addr_test1qzpmvykhq99xlfcccfft27rsntwg778mp37zf5dar75prtz6xzenalsrvktely96xvqtyv72syeycypeqn4fq42x4xnsl48ktw

The primary challenge arises during the construction of a transaction, where it is necessary to carefully select UTxOs as inputs to adequately cover the transaction's output requirements.

To address this, CardanoSharp offers a coin selection service. This service is adept at choosing the most suitable UTxOs for any given transaction, ensuring both efficiency and accuracy in the process for a given strategy.

Coin Selection

It is the process of methodically selecting the most appropriate UTxOs from a user's wallet to serve as inputs for a transaction on the Cardano blockchain. It is the process of ensuring that these UTxOs adequately cover the transaction value and the required fees, while also striving to prevent the creation of 'dust' and to optimize the wallet's UTxO management for future transactions.

Let's examine how to use the coin selection service in detail.

First, we need to retrieve all account UTxOs. For this, we will be using Cardanosharp Koios library to simplify the process.

// the stake address of the wallet
// derivation path: "m/1852'/1815'/0'/2/0"
var accountAddress = "stake_test1updrpve7lcpkt9uljzarxq9jx09gzvjvzqusf65s24r2nfczwgdg2";

// get an account client for Koios
var accountClient = RestService.For<IAccountClient>("https://preview.koios.rest/api/v1");

//get all available UTxOs for account
var response = await accountClient.GetAccountUtxos(new()
{
    StakeAddresses = new[] { accountAddress },
    Extended = true
});

// throw an exception if it's not a successful result
await response.EnsureSuccessStatusCodeAsync();

// koios account UTxOs
var aUtxos = response.Content;

Once we have a list of UTxOs from Koios, we need to prepare them to be used by the CardanoSharp coin selection service.

// convert koios utxo list to utxo models from CardanoSharp
var utxos = aUtxos
    .Where(u => !u.IsSpent)
    .Select(u => new Utxo
    {
        OutputAddress = u.Address,
        TxHash = u.TxHash,
        TxIndex = u.TxIndex,
        Balance = new Balance
        {
            Lovelaces = ulong.Parse(u.Value),
            Assets = u.AssetList.Select(al => new Asset()
            {
                Name = al.AssetName,
                PolicyId = al.PolicyId,
                Quantity = long.Parse(al.Quantity)
            }).ToList()
        }
    })
    .ToList();

Finally, let's build a simple transaction output to demonstrate the coin selection.

// second address in the wallet
// derivation path: "m/1852'/1815'/0'/0/1"
var receiver = new Address("addr_test1qzw3u57msm6ds6neg0na8guv2rqd8sse5v09k5vjcpzlu0j6xzenalsrvktely96xvqtyv72syeycypeqn4fq42x4xnsdya8t0");

// first address in the wallet
// derivation path: "m/1852'/1815'/0'/0/0"
var changeAddress = new Address("addr_test1qzpmvykhq99xlfcccfft27rsntwg778mp37zf5dar75prtz6xzenalsrvktely96xvqtyv72syeycypeqn4fq42x4xnsl48ktw");

// transaction output
// transferring 3 ADA
var transactionOutput = TransactionOutputBuilder.Create
    .SetAddress(receiver.GetBytes())
    .SetTransactionOutputValue(new TransactionOutputValue() { Coin = 3000000 })
    .SetOutputPurpose(OutputPurpose.Spend)
    .Build();

// initialise coin selection service with
// RandomImproveStrategy coin selection and 
// BasicChangeSelectionStrategy change strategy
var cs = new CoinSelectionService(new RandomImproveStrategy(), new BasicChangeSelectionStrategy());

// perform the selection using the transaction output as the criteria
var selection = cs.GetCoinSelection(new[] { transactionOutput }, utxos, changeAddress.ToString());

Let's examine the output of the selection service below:

The selection service has identified 2 UTxOs. One of the UTxOs has native tokens, which are then included in the change Output. Also, the balance of the total Lovelace has been adjusted to accommodate the required ADA in the transaction output.

The input collection and change outputs are expected to be added to the transaction body while building a transaction.

This would look like this:

// basic transfer transaction
var tbb = TransactionBodyBuilder
    .Create
    .AddOutput(transactionOutput)
    .SetFee(0);

// add all UTxOs inputs to the transaction
foreach (var input in selection.Inputs)
{
    tbb.AddInput(input);
}

// add all change outputs the transaction
foreach (var output in selection.ChangeOutputs)
{
    tbb.AddOutput(output);
}

// for demo purpose, mock witness
var witnesses = TransactionWitnessSetBuilder.Create.MockVKeyWitness(1);

// prepare transaction
var txBuilder = TransactionBuilder.Create.SetBody(tbb).SetWitnesses(witnesses);

// build transaction and calculate the fees
var tx = txBuilder.Build();
tx.CalculateAndSetFee();
tbb.RemoveFeeFromChange();

Below is the transaction body showing the 2 input UTxOs and the 2 outputs. One is the spent output, and the other is the change output. Notice how the change output has been adjusted to accommodate for the transaction fee.

Using this method will certainly simplify the process of creating transactions in Cardano.

I want to explore the strategies a little further so you have a good idea of the provided functionality out of the box.

Selection Strategies

The idea behind a good UTxO selection strategy is to balance transaction efficiency, cost and future wallet management.

The theory of a good selection strategy revolves around a few key ideas; here are three major points to consider:

• Transaction cost efficiency: since fees depend on the size of the transaction, selecting the right number of UTxO will keep costs at a minimum.

• Minimising future costs; a well-planned selection process can minimise future small transactions, thus reducing 'dust' UTxOs.

• Consolidating smaller UTxO; the strategy might consider including small 'dust' UTxOs so it can make future transactions more efficient. This will need to be carefully balanced against transaction costs.

CardanoSharp comes equipped with two strategies, RandomImproveStrategy and LargestFirstStrategy. Each strategy is trying to address certain needs and requirements. For instance, the LargestFirstStrategy would produce the most cost-efficient transaction by selecting the largest UTxOs to fulfill the transaction needs. However, RandomImproveStrategy is trying to randomise the UTxO selection and allow for the consolidation of smaller UTxO at random, thus improving future transaction costs.

Change Strategies

A change strategy is the second half of the selection equation. It focuses on future wallet management and UTxO fragmentation within the wallet.

A good strategy depends on the wallet's overall use case to begin with. For example, if the main purpose of the wallet is to hold ADA and small to no native tokens, then a simple change strategy is good enough. However, if the wallet will have few native tokens that are transferred not very often, then a strategy that will group tokens together in a UTxO with a small amount of ADA, leaving the majority of ADA in another UTxO, would be more effective for the purpose of the use case.

CardanoSharp comes with two strategies out of the box: BasicChangeSelectionStrategy and SingleTokenBundleStrategy.

These two strategies are trying to address the two use cases outlined above.

Closing thoughts

In this post, we discussed the automation of UTxO coin selection, using CardanoSharp and Koios services. This process is vital in any application that is going to build transaction for Cardano blockchains.

Also, we discussed the theory around the selection strategies and the objective it's trying to meet.

CardanoSharp aims to have a balanced implementation of the selection and change strategies.

However, you are not limited to them. You can implement your own to cover the specific use case of your application.

Here you will find the source code of the implementations provided by CardanoSharp https://github.com/CardanoSharp/cardanosharp-wallet/tree/main/CardanoSharp.Wallet%2FCIPs%2FCIP2