commit c08a5c8214e8f97a89d277bf11c6495a94190567
parent 8f10278107a4e314333b4dd87d2c50ec3a30015f
Author: Florian Dold <florian@dold.me>
Date: Thu, 12 Mar 2026 19:00:12 +0100
wallet-core: improve coin selection
Diffstat:
2 files changed, 133 insertions(+), 31 deletions(-)
diff --git a/packages/taler-wallet-core/src/coinSelection.test.ts b/packages/taler-wallet-core/src/coinSelection.test.ts
@@ -150,7 +150,6 @@ test("pay: select one coin to pay with fee", (t) => {
customerDepositFees: zero,
customerWireFees: zero,
wireFeeCoveredForExchange: new Set<string>(),
- lastDepositFee: zero,
totalDepositFees: zero,
} satisfies CoinSelectionTally;
const coins = testing_selectGreedy(
@@ -184,7 +183,6 @@ test("pay: select one coin to pay with fee", (t) => {
customerDepositFees: Amounts.parse("LOCAL:0.1"),
customerWireFees: Amounts.parse("LOCAL:0.1"),
wireFeeCoveredForExchange: new Set(["http://exchange.localhost/"]),
- lastDepositFee: Amounts.parse("LOCAL:0.1"),
totalDepositFees: Amounts.parse("LOCAL:0.1"),
});
});
@@ -504,13 +502,62 @@ test("overpay when remaining < depositFee", (t) => {
exchangeBaseUrl: "http://exchange.localhost/",
denomPubHash: "hash0",
maxAge: 32,
- contributions: [Amounts.parseOrThrow("LOCAL:2")],
+ contributions: [Amounts.parseOrThrow("LOCAL:1.1")],
+ },
+ "hash1;32;http://exchange.localhost/": {
+ exchangeBaseUrl: "http://exchange.localhost/",
+ denomPubHash: "hash1",
+ maxAge: 32,
+ contributions: [Amounts.parseOrThrow("LOCAL:1")],
+ },
+ });
+});
+
+test("prefer exact denom", (t) => {
+ const instructedAmount = Amounts.parseOrThrow("LOCAL:2");
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount,
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.5");
+
+ const coins = testing_selectGreedy(
+ {
+ wireFeesPerExchange: {},
},
+ createCandidates([
+ {
+ amount: "LOCAL:3" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.2" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:2" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.2" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.2" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ t.assert(coins != null);
+
+ t.deepEqual(coins, {
"hash1;32;http://exchange.localhost/": {
exchangeBaseUrl: "http://exchange.localhost/",
denomPubHash: "hash1",
maxAge: 32,
- contributions: [Amounts.parseOrThrow("LOCAL:0.1")],
+ contributions: [Amounts.parseOrThrow("LOCAL:2")],
},
});
});
diff --git a/packages/taler-wallet-core/src/coinSelection.ts b/packages/taler-wallet-core/src/coinSelection.ts
@@ -103,8 +103,17 @@ export interface CoinSelectionTally {
customerWireFees: AmountJson;
wireFeeCoveredForExchange: Set<string>;
+}
- lastDepositFee: AmountJson;
+function cloneTally(tally: CoinSelectionTally): CoinSelectionTally {
+ return {
+ amountDepositFeeLimitRemaining: tally.amountDepositFeeLimitRemaining,
+ amountPayRemaining: tally.amountPayRemaining,
+ customerDepositFees: tally.customerDepositFees,
+ customerWireFees: tally.customerWireFees,
+ totalDepositFees: tally.totalDepositFees,
+ wireFeeCoveredForExchange: new Set(tally.wireFeeCoveredForExchange),
+ };
}
/**
@@ -165,7 +174,6 @@ function tallyFees(
tally.amountPayRemaining,
dfRemaining,
).amount;
- tally.lastDepositFee = feeDeposit;
tally.totalDepositFees = Amounts.add(
tally.totalDepositFees,
feeDeposit,
@@ -246,7 +254,6 @@ async function internalSelectPayCoins(
customerWireFees: Amounts.zeroOfCurrency(currency),
totalDepositFees: Amounts.zeroOfCurrency(currency),
wireFeeCoveredForExchange: new Set(),
- lastDepositFee: Amounts.zeroOfCurrency(currency),
};
await maybeRepairCoinSelection(
@@ -725,26 +732,92 @@ export interface SelectGreedyRequest {
wireFeesPerExchange: Record<string, AmountJson>;
}
+function applyContributions(
+ selectedDenom: SelResult,
+ contributions: AmountJson[],
+ denom: AvailableCoinsOfDenom,
+): void {
+ if (contributions.length) {
+ const avKey = makeAvailabilityKey(
+ denom.exchangeBaseUrl,
+ denom.denomPubHash,
+ denom.maxAge,
+ );
+ let sd = selectedDenom[avKey];
+ if (!sd) {
+ sd = {
+ contributions: [],
+ denomPubHash: denom.denomPubHash,
+ exchangeBaseUrl: denom.exchangeBaseUrl,
+ maxAge: denom.maxAge,
+ };
+ }
+ sd.contributions.push(...contributions);
+ selectedDenom[avKey] = sd;
+ }
+}
+
function selectGreedy(
req: SelectGreedyRequest,
candidateDenoms: AvailableCoinsOfDenom[],
tally: CoinSelectionTally,
): SelResult | undefined {
const selectedDenom: SelResult = {};
- for (const denom of candidateDenoms) {
+ const currency = Amounts.currencyOf(tally.amountPayRemaining);
+ // Optimization: If we have a coin that exactly fits, use it.
+ for (let i = 0; i < candidateDenoms.length; i++) {
+ const denom = candidateDenoms[i];
+ const maxCost = Amounts.add(
+ tally.amountPayRemaining,
+ req.wireFeesPerExchange[denom.exchangeBaseUrl] ??
+ Amounts.zeroOfCurrency(currency),
+ denom.feeDeposit,
+ ).amount;
+ if (Amounts.cmp(denom.value, tally.amountPayRemaining) < 0) {
+ break;
+ }
+ if (Amounts.cmp(denom.value, maxCost) > 0) {
+ continue;
+ }
+ const testTally = cloneTally(tally);
+ tallyFees(
+ testTally,
+ req.wireFeesPerExchange,
+ denom.exchangeBaseUrl,
+ Amounts.parseOrThrow(denom.feeDeposit),
+ );
+ if (Amounts.cmp(testTally.amountPayRemaining, denom.value) == 0) {
+ // This time, don't modify testTally but the real tally.
+ tallyFees(
+ tally,
+ req.wireFeesPerExchange,
+ denom.exchangeBaseUrl,
+ Amounts.parseOrThrow(denom.feeDeposit),
+ );
+ applyContributions(
+ selectedDenom,
+ [Amounts.parseOrThrow(denom.value)],
+ denom,
+ );
+ return selectedDenom;
+ }
+ }
+
+ // Otherwise use smallest coins first.
+ for (let i = 0; i < candidateDenoms.length; i++) {
+ const denom = candidateDenoms[candidateDenoms.length - i - 1];
const contributions: AmountJson[] = [];
// Don't use this coin if depositing it is more expensive than
// the amount it would give the merchant.
if (Amounts.cmp(denom.feeDeposit, denom.value) > 0) {
- tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit);
continue;
}
for (
- let i = 0;
- i < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining);
- i++
+ let j = 0;
+ j < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining);
+ j++
) {
// Save the allowance *before* tallying.
const depositFeeAllowance = tally.amountDepositFeeLimitRemaining;
@@ -770,24 +843,7 @@ function selectGreedy(
contributions.push(coinSpend);
}
- if (contributions.length) {
- const avKey = makeAvailabilityKey(
- denom.exchangeBaseUrl,
- denom.denomPubHash,
- denom.maxAge,
- );
- let sd = selectedDenom[avKey];
- if (!sd) {
- sd = {
- contributions: [],
- denomPubHash: denom.denomPubHash,
- exchangeBaseUrl: denom.exchangeBaseUrl,
- maxAge: denom.maxAge,
- };
- }
- sd.contributions.push(...contributions);
- selectedDenom[avKey] = sd;
- }
+ applyContributions(selectedDenom, contributions, denom);
}
return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined;
}
@@ -1230,7 +1286,6 @@ export function emptyTallyForPeerPayment(
return {
amountPayRemaining: instructedAmount,
customerDepositFees: zero,
- lastDepositFee: zero,
amountDepositFeeLimitRemaining: req.feesCoveredByCounterparty
? instructedAmount
: zero,
