091-wallet-coin-selection.rst (2430B)
1 DD 91: Wallet Coin Selection 2 ############################ 3 4 Summary 5 ======= 6 7 This design document discusses the coin selection algorithm(s) used by the 8 wallet during payments. 9 10 Motivation 11 ========== 12 13 The current algorithm (as of 2026-01) is not properly specified and known to 14 lead to lots of small coins in the wallet, eventually causing major performance 15 regressions. 16 17 Requirements 18 ============ 19 20 * Computationally cheap 21 * Minimize number of (small) coins in the wallet 22 * Prefer coins closer to expiry 23 * Minimize fees 24 25 Proposed Solution 26 ================= 27 28 Grothoff coin selection 29 ^^^^^^^^^^^^^^^^^^^^^^^ 30 31 1. Only consider coins/denominations that are eligible (exchange, age 32 restriction, etc.). 33 2. In ascending denomination order, add coins until we are at or above the 34 total amount. If multiple coins of the same denomination are available, 35 start with the ones that expire first. [now we have for sure >= total 36 amount] 37 3. In descending denomination order, remove coins that would cause the total to 38 remain at or above the total amount. If removing the smallest coin in the 39 selection would cause us to fall below the total amount, obtain change for 40 that coin. [now we have for sure == total amount] 41 4. If total fees exceed what would be paid by the merchant *and* we do not have 42 an imbalanced wallet with > 5*F_D coins per denomination D on average 43 (except the largest denomination) [where "D" is the factor in the amount of 44 a coin of denomination D and the next larger denomination D+1], then in 45 ascending denomination order see if we can replace the selection of multiple 46 small coins with larger coins to reduce deposit fees (like using 2 cents 47 instead of 2x 1 cent, or 4 cents instead of 4x 1 cent [F_D=2], or if 48 denominations are not powers of 2 also 3x 1 cent for 3 cents (F_D=3)). Stop 49 early if the total fees fall below what the merchant pays. 50 51 This way we have: 52 53 * linear coin selection cost 54 * spent old coins first 55 * minimize small coins: reduce storage, ensure fast selection (few coins to choose from) 56 * reasonably minimize deposit fees (if possible) 57 * avoid getting change unnecessarily 58 59 Disadvantages: 60 61 * does not strictly minimize number of fresh coins in refresh (but spends old coins faster) 62 * does not handle multiple exchanges yet 63 64 Discussion / Q&A 65 ================ 66 67 (This should be filled in with results from discussions on mailing lists / personal communication.)