commit f678df93fee97ed75d4c974681f72538cff09716
parent 949f9fb291e0f71d431f865c453475ca39b35480
Author: Florian Dold <florian@dold.me>
Date: Fri, 20 Mar 2026 13:37:35 +0100
add DD91: wallet coin selection
Diffstat:
2 files changed, 68 insertions(+), 0 deletions(-)
diff --git a/design-documents/091-wallet-coin-selection.rst b/design-documents/091-wallet-coin-selection.rst
@@ -0,0 +1,67 @@
+DD 91: Wallet Coin Selection
+############################
+
+Summary
+=======
+
+This design document discusses the coin selection algorithm(s) used by the
+wallet during payments.
+
+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.
+
+Requirements
+============
+
+* Computationally cheap
+* Minimize number of (small) coins in the wallet
+* Prefer coins closer to expiry
+* Minimize fees
+
+Proposed Solution
+=================
+
+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
+
+Discussion / Q&A
+================
+
+(This should be filled in with results from discussions on mailing lists / personal communication.)
diff --git a/design-documents/index.rst b/design-documents/index.rst
@@ -102,4 +102,5 @@ Design documents that start with "XX" are considered deprecated.
088-wallet-withdraw
089-merchant-2fa
090-branding
+ 091-wallet-coin-selection
999-template
