UTXO/Coin Selection

One or more algorithms can be produced to select UTXOs when given a list of UTXO values and ages to help with transaction construction. A class could be created called CoinSelector that can construct a transaction from a UTXO set and desired outputs.

What should this algorithm optimize for? Should it contain options for the optimisation process, or should there be multiple sub-classes with different optimization algorithms?

• Speed and simplicity?
• Minimise the output age?
• Avoid change? Such as with the "Branch and Bound" algo.
• Aim to avoid dusty change with a minimum target change size (subject to balance)?
• Aim to make destination and change outputs ambiguous for privacy?
• Try to use as few different addresses as possible from UTXOs for privacy?

Tasks

• Update Input class to include int? get signedSize to determine what the size shall be when fully signed. This shall be null when the size is unknown.
• Add InputCandidate class with details of UTXO to be added including the unsigned input and value of the output. Only accept input types that have a known size to spend including TaprootKeyInput so that the fee can be correctly determined and coins selected accordingly.
• Create CoinSelection class that takes the version, locktime, InputCandidate objects, change Program, minimum change value, feeperkb and recipient outputs for a transaction. This shall provide the total input amount, total output amount, required fee and change value (0 if cannot reach minimum value and change is absent, or negative if there is a shortfall). This will also provide a transaction getter that will provide the transaction with inputs added or throw InsufficientFunds if the input value is insufficient. The change output will be added to a random output location. The class will also provide the signedSize.
• Create a .largestFirst() factory constructor which will select from InputCandidate objects taking the largest first.
• Create a .privateRandomImprove() factory constructor which will select coins according to a modified "Random Improve" algorithm (https://iohk.io/en/blog/posts/2018/07/03/self-organisation-in-coin-selection/). Details are given below.
• Create a .branchAndBound() factory constructor which will attempt to find a selection according to the Branch and Bound algorithm found in the C++ client. SolutionNotFound shall be thrown when there is no solution found for an algorithm.
• Create a .optimal() factory constructor which will try branchAndBound first and then privateRandomImprove, followed by .largestFirst() until a valid solution is found.

Private Random Improve

A target value shall be set for the total recipient value times 2, such that the change is near to the recipient value. It shall be determined if the total input value minus fee should be above or below the target on a 50/50 basis.

UTXOs will be randomised with inputs for identical programs being grouped together. UTXOs will be added from this list until the target plus fee is exceeded.

Once the input value minus fee exceeds the target, two things may happen. If the amount should be under the target, remove the last output and add to a discard list. If the amount is above target*0.75 then return, else go back to adding further outputs.

If the amount should be above the target, return if the amount is under target*1.5, else remove the last output to the discard list and continue to add further outputs.

If there are no more outputs left, it shall return provided that the required amount is met. Otherwise it shall add outputs from the discard list until the required amount is met.

Start with the existing CoinSelection, InputCandidate, and largestFirst entry points to understand how fees, signed sizes, change, and selected inputs are represented. Compare the requested privateRandomImprove and branchAndBound behavior with the linked Random Improve article and C++ client algorithm. Done means the three factory constructors and optimal fallback are implemented, including the specified failure conditions, with coverage for valid and insufficient selections.