taler-typescript-core

commit bfde4170fe757a22725264ba8b9a9eda0003e215
parent d254fbd2a8ea1f4274b285a506bac68c45ed2418
Author: Florian Dold <dold@taler.net>
Date:   Thu, 20 Aug 2026 19:06:50 +0200

wallet-core: document greedy denomination selection

Diffstat:
M
packages/taler-wallet-core/src/denomSelection.ts
 | 
12
+++++++++---
M
packages/taler-wallet-core/src/withdraw.test.ts
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 70 insertions(+), 3 deletions(-)
diff --git a/packages/taler-wallet-core/src/denomSelection.ts b/packages/taler-wallet-core/src/denomSelection.ts
@@ -60,9 +60,15 @@ export class UnverifiedDenomError extends Error {
 }
 
 /**
- * Get a list of denominations (with repetitions possible)
- * whose total value is as close as possible to the available
- * amount, but never larger.
+ * Greedily select a list of denominations (with repetitions possible) whose
+ * total withdrawal cost does not exceed the available amount.
+ *
+ * This is deterministic best-effort selection, not a closest-fit or
+ * fee-optimal algorithm.  It consumes as many coins as possible in the
+ * caller-supplied descending denomination order before considering the next
+ * denomination.  Thus a smaller-denomination combination can sometimes yield
+ * more coin value or leave a smaller remainder.  Exact bounded optimization
+ * is deliberately deferred until its resource policy is specified.
  *
  * Throws if any of the denoms is invalid.
  *
diff --git a/packages/taler-wallet-core/src/withdraw.test.ts b/packages/taler-wallet-core/src/withdraw.test.ts
@@ -435,3 +435,64 @@ test("withdrawal selection bug repro", (t) => {
 
   assert.ok(Amounts.cmp(res.totalWithdrawCost, amount) <= 0);
 });
+
+test("withdrawal denomination selection is documented greedy best effort", () => {
+  const now = AbsoluteTime.now();
+  const stampStart = timestampProtocolToDb(
+    AbsoluteTime.toProtocolTimestamp(
+      AbsoluteTime.subtractDuraction(now, Duration.fromSpec({ minutes: 1 })),
+    ),
+  );
+  const stampExpireWithdraw = timestampProtocolToDb(
+    AbsoluteTime.toProtocolTimestamp(
+      AbsoluteTime.addDuration(now, Duration.fromSpec({ hours: 1 })),
+    ),
+  );
+  const stampExpireDeposit = timestampProtocolToDb(
+    AbsoluteTime.toProtocolTimestamp(
+      AbsoluteTime.addDuration(now, Duration.fromSpec({ hours: 2 })),
+    ),
+  );
+  const zero = "KUDOS:0" as AmountString;
+  const makeDenom = (
+    denomPubHash: string,
+    value: AmountString,
+    feeWithdraw: AmountString,
+  ): WalletDenomination =>
+    ({
+      denomPubHash,
+      value,
+      currency: "KUDOS",
+      fees: {
+        feeWithdraw,
+        feeDeposit: zero,
+        feeRefresh: zero,
+        feeRefund: zero,
+      },
+      verificationStatus: DenominationVerificationStatus.VerifiedGood,
+      isOffered: true,
+      isRevoked: false,
+      isLost: false,
+      stampStart,
+      stampExpireWithdraw,
+      stampExpireDeposit,
+      denomPub: { cipher: DenomKeyType.Rsa, age_mask: 0 },
+    }) as WalletDenomination;
+
+  const selection = selectWithdrawalDenominations(
+    Amounts.parseOrThrow("KUDOS:15"),
+    [
+      makeDenom("cost-eleven", "KUDOS:10", "KUDOS:1"),
+      makeDenom("cost-five", "KUDOS:5", zero),
+    ],
+  );
+
+  // Greedy takes the first cost-11 denomination and leaves four, even though
+  // three cost-5 denominations would fit exactly.  This pins the consciously
+  // deferred approximation so it cannot again be mistaken for closest-fit.
+  assert.deepStrictEqual(selection.selectedDenoms, [
+    { denomPubHash: "cost-eleven", count: 1 },
+  ]);
+  assert.strictEqual(selection.totalWithdrawCost, "KUDOS:11");
+  assert.strictEqual(selection.totalCoinValue, "KUDOS:10");
+});