Cardano Omnibus - UTXO Management

The UTxO has many interesting properties. However it comes with its challenges too. For one it is more difficult to manage UTxOs wallet to the scale of an exchange or a dApp. Handling UTxO even for smaller wallets already has its challenges. We want to provide specification and reference implementation on how to handle large amounts of UTxO, from the input selection to the output selection.

Indeed the Output selection has been totally left out of the many different papers out there. The simple cases have been resolved, how to do input selections in order to optimize the cost and the security of a wallet. Here we wish to explore solutions on how to continuously reorganise UTxO into sizable chunks to provide an easier and more optimized transaction system.

Example: if you have a wallet with millions of UTxOs, each holding a value of 1 ada. Technically your spending capacity is worth millions of Ada. Yet the limitation of the transaction size will make it impossible for you to do any transaction for all these assets. Now you can claim this is possible to do via multiple transactions. And you would be correct. But then you have wasted your fees. Because in Cardano, the most expensive part of the transaction is not necessarily the inputs and the outputs, it's the constant fee of 0.155381 Ada. Instead we want to build transactions to, at the same time, do the requested spending and perform the UTxO re-grouping. We claim this is cheaper and more efficient than any wallet implementation out there.

Since there is no readily available solution for this, many wallets implement their own ad-hoc solutions which can often lead to, for example, wallets with many NFTs being unable to send ADA anymore. Exchanges also run into this problem often causing downtime in exchanges and they try and manually fix their wallet. 

As this is an open R&D problem, it is hard to predict how long it will take. Beyond the implementation itself, we plan to also contribute to the CIP discussion about input selections and properly document how we got to the final solution(s). We believe we can complete this in the first half of 2022

The previous work done in Byron by IOG no longer works well because Cardano now supports multi-asset and smart contracts, but it may be useful to look at to understand what the deliverable of this proposal will look like:

- Input Selection CIP: https://github.com/input-output-hk/cardano-coin-selection
- Input Selection library: https://input-output-hk.github.io/cardano-coin-selection/haddock/cardano-coin-selection-1.0.1/Cardano-CoinSelection.html
- Coin selection algorithm research: https://iohk.io/en/blog/posts/2018/07/03/self-organisation-in-coin-selection/

If you want to refer to the work that was done for this in Byron (doesn't work well anymore because Cardano sup