MACS: A new approach to multi-asset coin selection

A research paper exploring how the MACS algorithm enhances UTxO-based blockchain coin selection

Innovation as well as continuous research are key to advancing the utility, reach, and efficacy of blockchains, and the Cardano Foundation strongly believes not only in aiding but indeed in contributing to blockchain research. The publication of our research paper “MACS: A Multi-Asset Coin Selection Algorithm for UTxO-based Blockchains”—first presented at the 2023 IEEE International Conference on Blockchain—focuses on the benefits and enhanced capabilities of using the multi-asset coin selection (MACS) algorithm.

Coin selection, a term referring to the process whereby a wallet chooses which of its unspent transaction outputs (UTxOs) it spends in a particular transaction, remains a pain point for many users: Different wallet software may use various coin selection algorithms, which can influence speed, privacy, and transaction fees. Continually optimizing the algorithms used in this process ensures the enduring strength and efficacy of the technology. Better coin selection algorithms are needed to improve the way blockchain functions, including in terms of user experience. Therefore, the MACS paper constitutes an advancement of the technology underpinning the blockchain.

UTxO vs. account-based blockchains

To fully comprehend the impact of the MACS algorithm, understanding how ledgers function proves crucial. To begin with, blockchain encompasses two primary ledger classes: UTxO-based ledgers, exemplified by Bitcoin, and account-based ledgers, such as in Ethereum.

In UTxO-based ledgers, the blockchain’s state is stored within these UTxOs. Blockchain transactions in this type of ledger involve consuming specific UTxOs and creating new ones. To calculate the user’s total tokens, the wallet software must calculate the balance by summing up all UTxOs linked to that user.

Account-based ledgers, on the other hand, assign each user a dedicated account. In this system, transactions primarily increase or decrease the balance in a user’s account by transferring tokens to other users. As a result, the user wallet software shows account balances without the need to calculate them.

While account-based ledgers appear simpler, calculating balances by summing tokens in the user’s UTxOs offers distinct advantages. Specifically, the UTxO-based ledgers produce more predictable results and facilitate parallel transaction processing.

The research results

The MACS paper examined a number of areas and results, namely the:

formulation of an optimization problem that aims to jointly minimize transaction fees and the UTxO pool size, as well as preserve user privacy;
introduction of a priority score for UTxOs which involves the value, age, and number of linked UTxOs;
comparison of the performance of MACS with other algorithms.

So far, MACS has been tested exclusively in simulations. As outlined in the paper, they show promising behavior, which should serve as the basis for more in-depth future research. Crucially, it also represents one step towards improved coin selection algorithms.

The present research results already highlight MACS’s usefulness to enhance UTxO-based blockchains in several important ways, including optimizing transactions for cost, speed, and privacy, as well as ultimately boosting the user experience. With further improvement iterations, we believe MACS has the potential for broad adoption in UTxO-based blockchains.

Moving forward, it will be critical to test MACS with real-world data to fully optimize the algorithm. After concluding such testing and optimization, the algorithm could hold the potential for various wallet implementations. In fact, additional testing and research will show the full capabilities of MACS.

The Cardano Foundation encourages everyone to read the paper in full and for free.

Manvir Schneider