Cardano Wallet unable to prioritise the selection of larger UTxOs when transaction space is limited.

Just checking...

[X] This is a cardano-wallet bug.
[X] I am using the latest cardano-wallet release.
[X] I am using the correct cardano-node version for that release of cardano-wallet.

Version

v2022-10-06 (git revision: 2130fe0acf19fa218cef8de4ef325ae9078e356e)

Platform

Linux cardano-relay-test 4.19.0-14-amd64 #1 SMP Debian 4.19.171-2 (2021-01-30) x86_64 GNU/Linux

Installation method

Binary from GitHub release page

Network configuration

mainnet, preview

Context

For large wallets with huge amount of addresses and small UTXOs it is often impossible to send TX despite it would be otherwise possible (if UTXOs could be hand picked).

For example in my case, I have a wallet with over 4000 UTXOs ranging from 1 ADA to 10 ADA and some (about 40) UTXOs with over 100ADA.

When I try to send 4000 ADA, cardano-wallet fails with:

{"code":"transaction_is_too_big","message":"I am not able to finalize the transaction because I need to select additional inputs and doing so will make the transaction too big. Try sending a smaller amount. I had already selected 114 inputs."}

Because it picks first 114 inputs - no idea by which order - that are some very small UTXOs that all together aren't even 4000 ADA and by that time the TX is already too large to fit the limits.

However, such TX could be easily constructed if cardano-wallet considered using some of the larger UTXOs that exist in it.

This makes it impossible in many cases to make TX at all. In other cases it results in unnecessarily bloated TXs that contain more UTXOs than they would otherwise have to, resulting in enormous network fees.

The algorithm should be smarter and cardano-wallet should allow user to specify explicitly which UTXOs they want to use for --tx-in so that they are free to improve the algorithm themselves, without having to modify the wallet's source code.

Description

Steps to Reproduce

Create a new wallet
Send 50 000 small UTXOs to it and 10 bigger UTXOs
Try to make a larger TX from that wallet, it will fail ...

Expected behavior

Be smarter when constructing the TX and chose more appropriate UTXOs. Or allow user to do that.

Actual behavior

Wrong UTXOs are picked resulting in failure.

Hi @benapetr

Many thanks for your bug report. Selecting an excessive number of small UTxOs is indeed a problem that would occur if your wallet's average UTxO size is much smaller than the payment you wish to make.

Could you try the workaround below and let me know if it works for you?

Suggested Workaround

First create one or more "re-balancing" transactions that adjust your wallet's UTxO distribution.

ℹ️ A "re-balancing" transaction is just a transaction where all inputs and outputs belong to the same wallet.

Example

Suppose that:

You wish to send 4000 ada to Alice.
The wallet is unable to select 4000 ada in a single transaction (because the resultant transaction would require too many inputs).

Try the following steps:

First attempt to create a transaction that pays 2000 ada to your own wallet.
If that doesn't work: create a transaction that pays 1000 ada to your own wallet.
If that doesn't work: create a transaction that pays 500 ada to your own wallet.
If that doesn't work: create a transaction that pays 250 ada to your own wallet.
If that doesn't work: create a transaction that pays 125 ada to your own wallet.
...
and so on.

Once you've succeeded in submitting a re-balancing transaction, then you can re-attempt to send 4000 ada to Alice.

If you're still unable to send 4000 ada to Alice, you may need to create further re-balancing transactions (again, following the process above).

After each re-balancing transaction, you can inspect the current UTxO distribution with:

After each re-balancing transaction, you should see an increase in the number of "larger" UTxOs within your wallet's UTxO distribution. The greater the number of "larger" UTxOs, the more likely it will be that the wallet selects them when building a transaction.

Historical Context

In the past, cardano-wallet had two algorithms for selecting UTxOs:

The wallet would first attempt to select UTxOs with Random-Improve, but fall back to Largest-First on failure.

However, with the introduction of multi-asset UTxOs (in the Mary era), a decision was taken to prioritise Random-Improve, and remove support for Largest-First, as:

there was not enough time to redesign Largest-First to support multi-asset UTxOs in time for the Mary release.
there is evidence to support the hypothesis that Random-Improve, when repeatedly applied over time, leads to healthier UTxO distributions.

Potential Future Improvements

Cardano Wallet already has support for a minimal selection strategy. (See PR 3161 and PR 3164). However, the minimal selection strategy is currently only supported by the balanceTransaction endpoint. In future, we could consider making this strategy available to more endpoints.
If there were enough demand for it, we could introduce a multi-asset version of the Largest-First algorithm. However, this would likely require research, design, implementation, and test work.

Hi @jonathanknowles thanks for the reply I will try this, but I don't think it will work, I will give you some more context so that you understand my current situation (the example I gave you is from preview network, but on mainnet the situation is much worse).

We are running a service called "vending machine" - it's a token distribution platform, where cardano-wallet helps us manage the UTXOs so that we don't have to end up working on low level (with CLI or microprotocols which would open space to bugs and security vulnerabilities). This service is processing thousands of reward withdrawals every day. You can see how large the wallet is - https://cardanoscan.io/stakeKey/stake1u89tnj258vkk4p9fnd226e7lulh3xh58mvl66uzarzgkrxq7xz24l we have over 70 000 addresses many thousands of UTXOs, virtually all of them with some native assets connected to them.

This is still working fine for us, the reward delivery model is actually quite well compatible with that way cardano-wallet manages UTXOs, but the problem is that someone accidentally sent over 260 000 ADA to one of our withdrawal addresses. And now we are kind of stuck in process of returning this amount back to them.

In your example of 4000 ADA it would probably work, I actually already solved similar issue in the past by sending few smaller batches to that person, but in this case - 260 000 is quite a large amount, so I don't think this can possibly work. But it all resides in one UTXO, inluding 1 native asset token (that we also intend to return to sender).

Now regarding your largest-first notice - I am wondering, what if we first tried to remove that native asset from the 260k+ ADA UTXO by sending only the asset out. If there was only ADA, would cardano-wallet actually pick it? Eg. send the token first and the remaining amount second?

Or is the only feasible solution to manually derive private key for the payment address and cherry pick this UTXO using cardano-cli?

Cardano Wallet already has support for a minimal selection strategy. (See PR 3161 and PR 3164). However, the minimal selection strategy is currently only supported by the balanceTransaction endpoint. In future, we could consider making this strategy available to more endpoints.

Update: The minimal selection strategy (fallback to selecting only 1x the output amount rather than 2x) should now have made its way to the constructTransaction endpoint as part of #3553 which is merged to master though yet-to-be released. We're also aiming getting the other endpoints (including /payments) to do the same by early next year.

cardano-foundation / cardano-wallet