UTXO/Coin Selection

[MatthewLM]

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.

[peerchemist]

The primary use case of the coinlib is the mobile and web light wallet made in flutter, which is not capable of minting. Given this fact, it is useless to optimize UTXO selection for output age. Probably the best approach is the simplest one, with minor optimization like avoiding dust or avoiding change as secondary goals.

[MatthewLM]

Avoiding change can be done through the BnB algorithm ported from the C++ client.

If we use BnB but no solution is found, then we can use a fallback algorithm. To avoid dust we can adapt the idea of the "Random-Improve" algorithm: https://iohk.io/en/blog/posts/2018/07/03/self-organisation-in-coin-selection/

For this fallback, I suggest sorting outputs by address so that utxos of a given address are tried together before moving onto the next one. The sorting can be otherwise randomised. If the transaction size is too large, a largest-first sorting can be tried instead.

For additional privacy I think that after the payment value is met, we could randomly target a range of 1 + 1/sqrt(2) or 1 + sqrt(2) of the payment value so that the change is randomly either higher or lower than the payment value. This makes it harder to determine which output is the change. With a determined range selected, we can add outputs until the lower bound is met. If the upper bound is then exceeded, the smallest utxos can be removed until it falls below the upper bound. If we then fall below the lower bound again, we can continue to add further utxos and repeat the process until we run out of utxos or fall within the desired range.

This process of adding and removing utxos until we fall within range could be used to target the change-free range instead of BnB and would allow a single algorithm to cover the different approaches. It wouldn't try as many options as BnB however and could miss solutions.

[peerchemist]

For the start, it is probably the best to port the solution from the C++ client.

[MatthewLM]

The BnB can be ported. I wouldn't bother with Knapsack. The Random-Improve algorithm should be a reasonable fallback and I think the changes I propose can enhance it further for privacy.

[peerchemist]

Okay, make it so.

[MatthewLM]

OK, I will port BnB and then an adapted privacy-enhanced version of Random-Improve as a fallback. Ultimate fallback, in case of too many inputs, will be to use largest-first.