View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0011099 | Taler | wallet-core | public | 2026-02-17 22:58 | 2026-03-12 19:43 |
| Reporter | Florian Dold | Assigned To | Florian Dold | ||
| Priority | normal | Severity | tweak | Reproducibility | have not tried |
| Status | assigned | Resolution | open | ||
| Product Version | git (master) | ||||
| Target Version | 1.5 | ||||
| Summary | 0011099: coin selection should minimize small coins [3h] | ||||
| Description | According to experiments by one of Mikolai's student's, the current coin selection results in a large number of small coins that aren't spent. We should try to spend small coins earlier. | ||||
| Tags | No tags attached. | ||||
|
|
I have an algorithm to propose. 3 passes: (0) Only consider coins/denominations that are eligible (exchange, age restriction, etc.). (1) 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] (2) 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] (3) 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) * ??? |
|
|
Sounds reasonable, I guess how we should proceed is: * Immediately implement a simplified version of this algorithm that does (0)+(1) partially (2) * That's already done, adjusting tests for differing amounts right now * Flesh out the above algorithm in a DD * Implement the full algorithm (with low prio in 1.5, possibly later) |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2026-02-17 22:58 | Florian Dold | New Issue | |
| 2026-02-19 18:46 | Christian Grothoff | Severity | minor => tweak |
| 2026-02-19 18:46 | Christian Grothoff | Status | new => confirmed |
| 2026-02-19 18:46 | Christian Grothoff | Product Version | => git (master) |
| 2026-02-19 18:46 | Christian Grothoff | Target Version | => 1.8 |
| 2026-03-12 14:52 | Florian Dold | Target Version | 1.8 => 1.5 |
| 2026-03-12 14:52 | Florian Dold | Summary | coin selection should minimize small coins => coin selection should minimize small coins [3h] |
| 2026-03-12 15:15 | Florian Dold | Assigned To | => Florian Dold |
| 2026-03-12 15:15 | Florian Dold | Status | confirmed => assigned |
| 2026-03-12 18:36 | Christian Grothoff | Note Added: 0028119 | |
| 2026-03-12 19:43 | Florian Dold | Note Added: 0028122 |
