DD 91: Wallet Coin Selection

18.91. DD 91: Wallet Coin Selection#

18.91.1. Summary#

This design document discusses the coin selection algorithm(s) used by the wallet during payments.

18.91.2. Motivation#

The current algorithm (as of 2026-01) is not properly specified and known to lead to lots of small coins in the wallet, eventually causing major performance regressions.

18.91.3. Requirements#

  • Computationally cheap

  • Minimize number of (small) coins in the wallet

  • Prefer coins closer to expiry

  • Minimize fees

18.91.4. Proposed Solution#

18.91.4.1. Grothoff coin selection#

  1. Only consider coins/denominations that are eligible (exchange, age restriction, etc.).

  2. In ascending denomination order, add coins until we are at or above the total amount. If multiple coins of the same denomination are available, start with the ones that expire first. [now we have for sure >= total amount]

  3. In descending denomination order, remove coins that would cause the total to remain at or above the total amount. If removing the smallest coin in the selection would cause us to fall below the total amount, obtain change for that coin. [now we have for sure == total amount]

  4. If total fees exceed what would be paid by the merchant and we do not have an imbalanced wallet with > 5*F_D coins per denomination D on average (except the largest denomination) [where “D” is the factor in the amount of a coin of denomination D and the next larger denomination D+1], then in ascending denomination order see if we can replace the selection of multiple small coins with larger coins to reduce deposit fees (like using 2 cents instead of 2x 1 cent, or 4 cents instead of 4x 1 cent [F_D=2], or if denominations are not powers of 2 also 3x 1 cent for 3 cents (F_D=3)). Stop early if the total fees fall below what the merchant pays.

This way we have:

  • linear coin selection cost

  • spent old coins first

  • minimize small coins: reduce storage, ensure fast selection (few coins to choose from)

  • reasonably minimize deposit fees (if possible)

  • avoid getting change unnecessarily

Disadvantages:

  • does not strictly minimize number of fresh coins in refresh (but spends old coins faster)

  • does not handle multiple exchanges yet

18.91.5. Discussion / Q&A#

(This should be filled in with results from discussions on mailing lists / personal communication.)