[Wallet] Coinselection algorithm produces too many small coins

[callebtc]

The current coinselection algorithm favors large coins first since it assumes that their anon set is small. However, over a long period, this leads to wallets with an ever increasing number of tokens since they tend to be broken down. We need to find a good balance between efficiency and other objectives, such as getting rid of large coins if possible.

One option would be adding a heuristic threshold for the selection of large coins (i.e., favor selection of coins with a amount if the amount is > 2^14).

[sj-fisher]

Thanks for flagging this as a "good first issue", I've been looking for some way to make a small contribution to this interesting project.

I think our (conflicting) objectives for wallet management are:

• Keep transaction messages small by limiting the number of proofs we need to include.
• Keep our wallet small by limiting the number of proofs we need to store. (A single wallet probably has negligible size even on the smallest device, but a hypothetical server-based backup could have large numbers of wallets to store.)
• Help keep the mint database small(er) by limiting the number of proofs we ask it to create.
• Keep the anonymity set for our transactions as large as possible by preferring "common" coin sizes.

Did I miss anything?

If we're really worried about anonymity set size for larger coins, the wallet could be anti-social (bloating the mint database) and split such coins as soon as it receives them. If we don't do that, does that mean we're not that bothered about it but we'll take low-cost steps to spend in an anonymity set-friendly way because it doesn't hurt and might help a bit?

Could/should the mint track coin sizes which have very small anonymity sets and try to dynamically phase in or out the use of "large" denominations as demand changes? For example, when generating a new keyset, cap the maximum coin size at something that would have been reasonably commonly issued across the set of mint requests during the lifespan of the previous keyset?

Is it actually a good idea from an anonymity set perspective to spend large coins ASAP? If these coins have a low but non-zero rate of issuance, the longer we hold our large coin, the more other coins of this size are likely to come into existence and the larger the anonymity set grows. (If my thinking is correct here, the anonymity set grows as coins of a particular denomination and keyset are issued. Those coins being spent doesn't shrink the anonymity set, unless there's only ever one such coin in circulation at any time.)

Without having done any simulations or anything like that (yet), my current inclination is to implement coin selection so that:

• If we can pay exactly with a subset of the coins on hand, we do that.
• Otherwise, if we have any coins larger than the required amount, we split the smallest of those coins.
• Otherwise, we use the current algorithm - sort by descending order of size, and pick the shortest initial subset of those coins which exceeds the required amount.

I am assuming that in the absence of the serious constraints relevant for on-chain wallet UTXO management, we don't want anything which is too complex in cashu. The above feels reasonably tractable - only paying with an exact subset is non-trivial, and I think branch and bound (see e.g. https://blog.summerofbitcoin.org/coin-selection-for-dummies-2/) will address it relatively easily. (It's also possible that the fact all coins are powers of two helps; we can compare the binary representation of the desired amount against the available coins and see if we can make up any shortfalls on the naive match by using "spare" lower value tokens, e.g. we need an 8 and don't have one, but we have two spare 4s. I'd have to try implementing this to see if it's simpler than branch and bound.)

[sj-fisher]

I've written some prototype code which finds a subset of the wallet's coins adding to a specific value if possible. The "use the binary representation and then try to compensate for missing coins" trick seems to work well and isn't complex (it's about 25 lines of code) so branch and bound is probably unnecessarily complex here.

[sj-fisher]

I've now done some basic simulation on this. Obviously I had to make up some hopefully plausible models of the distribution of deposits and spends to/from a wallet, but I think what I've come up with is reasonably realistic.

I've attached a simple Python program which simulates the existing coin selection algorithm and the one I described above on some random wallet deposit/spend sequences. For want of better names, I am calling the existing algorithm "largest first" and the one above "PESS" (for "Prefer Exact or Smallest Single (coin)").

After 50000 simulated deposit/spend sequences, I got:

               Wallet size percentiles             Coins created percentiles
               [   0%,   25%,   50%,   75%,  100%] [   0%,   25%,   50%,   75%,  100%]
Largest first: [    1,   118,   169,   222,   432] [  119,   448,   759,  1064,  1449]
PESS:          [    1,    21,    29,    37,    96] [   69,   282,   469,   653,   934]

The wallet sizes show the distribution of the number of individual coins (regardless of size) in our wallet at the end of the test sequences. In the worst test sequence with PESS we had 96 coins left in our wallet, whereas largest first had 432 coins. That's obviously an extreme, but PESS is performing much better at lower percentiles as well.

The coins created percentiles track the amount of bloat in the mint database by recording the number of coins created (whether retained in our wallet or given to someone else). I believe coin creation adds a record to the mint database but coin destruction doesn't (because the mint still has to remember the coin has been spent), so coin destruction is not tracked - if I have the wrong end of the stick here, these results will not be meaningful. Assuming for the moment I'm correct, with largest first the worst test sequence created 1449 coins in total, whereas with PESS the worst case was 934 coins created, and again the performance is better at lower percentiles too.

I've tried to comment the test code fairly well so I hope it's clear if anyone would like to take a look. find_exact_subset() implements the algorithm for finding the exact subset of coins in a wallet adding to a specific amount. find_exact_subset() and spend_pess() are effectively the code that (rewritten to work with real wallets, of course) needs to be migrated into wallet.py's _select_proofs_to_send() function to implement this.

I will look at implementing this in cashu properly in the near future, but I'll wait a little bit in case anyone has any comments first.

simulation.py.gz

[sj-fisher]

I have had a go at implementing this in cashu, including adding some tests. You can see the code on my issue-301-wip branch.

However, I am getting a failure on a single test:

E       assert 162 == 182
E        +  where 162 = <cashu.wallet.wallet.Wallet object at 0x7f7380013cd0>.balance

tests/test_wallet_restore.py:364: AssertionError

Everything else passes. I don't really understand what is happening in this test with the restore_promises_from_to(0, 50) call so I'm finding it hard to debug. Can anyone offer any advice please? For example, where does the correct value of 182 come from?

Any other comments would be welcome too. I plan to squash the change to a single commit on a new branch before submitting a pull request, so please don't worry too much about the individual commits on the branch. You can see the whole diff here.

[sj-fisher]

I have rebased this to the latest main and the code can be found on my issue-301-wip-2 branch.

The test failure above is still present - I would appreciate some advice on this please.

All the other tests pass except test_split_race_condition, which I think is somewhat expected (https://github.com/cashubtc/nutshell/issues/505).