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