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

[benapetr]

Just checking...

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

Version

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

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

1. Create a new wallet
2. Send 50 000 small UTXOs to it and 10 bigger UTXOs
3. 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.

[jonathanknowles]

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:

• getWalletUTxOSnapshot
• getUTxOStatistics

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:

• Random-Improve
• Largest-First

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.

[benapetr]

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?

[Anviking]

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.

[HeinrichApfelmus]

@benapetr Is this issue still relevant to you? Please reopen if that is the case.

[benapetr]

yes, this is still relevant and still broken feature

[abailly]

@benapetr Would you be available for a chat to tell us more about how you are using the cardano-wallet, what are your pain points, how you mitigate those? The current Cardano-wallet has accumulated a lot of technical debt over the years and the team is currently working on a new version that will be much more fit for users with large number of UTxOs and addresses.
We would be interested in detailed feedback in order to ensure we can fix those issues with this new version.

[benapetr]

Hello, we are using cardano-wallet as one of backend components of vending machine - https://vm.adaseal.eu/about which is also used by TosiDrop platform and some other platforms. We are generating solid traffic on entire cardano blockchain with hundreds of thousands of transactions written to the chain using cardano-wallet. In the past we had wallets that bloated so much we had almost million addresses (we had to decommission them because they were too resource intensive to work with). Later cardano-wallet finally fixed that "bug" and made it so that wallet address pool doesn't grow indefinitely, but there are still some major issues, one of them is this inability to construct transaction even if it's technically possible.

To give you an example, this is one of current active wallets https://cardanoscan.io/stakeKey/stake1u8ffzkegp8h48mare3g3ntf3xmjce3jqptsdtj38ee3yh3c9t4uum it contains about 500 different asset types spread over hundreds of UTXOs (it used to be thousands but now we implemented more on-chain components that we are using in tandem with cardano-wallet, that are defragmenting the UTXO distribution manually in order to allow cardano-wallet to remain operational).

We often run into a problem where there is enough tokens to construct required TX, but cardano-wallet is either repeatedly unable to assemble such TX (because it tries UTXO seemingly completely randomly and after certain amount of attempts it just gives up), or else it manages to assemble the TX, but not very efficiently, resulting in a very large transaction.

We are already in a middle of implementation of our own drop-in replacement of cardano-wallet (written in C#) with compatible API that solves these issues, so this is not a "pressing issue" anymore, but it still is an issue that might be worth solving.

Simply said - the current algorithm for TX assembly only works under ideal conditions. In non-ideal conditions it collapses entirely, even if TX can be assembled.

And obviously it mostly affects transactions that contain many different native assets, not simple ada-only TXs, which are trivial to manage

[abailly]

@benapetr Thanks a lot for the detailed report.

We are already in a middle of implementation of our own drop-in replacement of cardano-wallet (written in C#) with compatible API that solves these issues, so this is not a "pressing issue" anymore, but it still is an issue that might be worth solving.

What's the time horizon for this replacement to happen?

[benapetr]

probably several months at least, we have a working read-only model with all cardano-wallet compatible APIs that can observe the chain, track UTXOs, and all asset movements, but there are some complications... not every aspect of Cardano blockchain is perfectly documented or obvious (especially various parameter changes across all sorts of hard-forks that change the way chain is meant to be processed) and also reading Haskell code and trying to understand how it works isn't exactly fun for most of programmers I know :P

also these other tools and scripts we made to defragment wallets and make it more manageable for cardano-wallet to keep working, made it so that this is really not a pressing issue anymore. It's just a scalability issue into the future and also defragmenting wallet costs ADA on fees, so it would be nice to have this solved, but not really a blocking issue right now.