commit e69d25477800eb11eabdd7acafdbe4ce188e9e97
parent b13a53c32576ebffdd9fa21496d2d175bdc3b1d9
Author: Florian Dold <dold@taler.net>
Date: Mon, 10 Aug 2026 02:15:26 +0200
wallet-core: implement DD91 coin selection
Diffstat:
2 files changed, 722 insertions(+), 71 deletions(-)
diff --git a/packages/taler-wallet-core/src/coinSelection.test.ts b/packages/taler-wallet-core/src/coinSelection.test.ts
@@ -115,9 +115,9 @@ test("p2p: should select 3 coins", (t) => {
denomPubHash: "hash0",
maxAge: 32,
contributions: [
+ Amounts.parseOrThrow("LOCAL:0.3"),
Amounts.parseOrThrow("LOCAL:10"),
Amounts.parseOrThrow("LOCAL:10"),
- Amounts.parseOrThrow("LOCAL:0.3"),
],
},
});
@@ -511,18 +511,321 @@ test("overpay when remaining < depositFee", (t) => {
exchangeMasterPub: "123",
denomPubHash: "hash0",
maxAge: 32,
- contributions: [Amounts.parseOrThrow("LOCAL:1.1")],
+ contributions: [Amounts.parseOrThrow("LOCAL:2")],
+ },
+ "hash1;32;http://exchange.localhost/": {
+ exchangeBaseUrl: "http://exchange.localhost/",
+ exchangeMasterPub: "123",
+ denomPubHash: "hash1",
+ maxAge: 32,
+ contributions: [Amounts.parseOrThrow("LOCAL:0.1")],
+ },
+ });
+});
+
+test("DD91 removes redundant small coins after ascending selection", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:6"),
+ });
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:8" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 4,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(coins, {
+ "hash0;32;http://exchange.localhost/": {
+ exchangeBaseUrl: "http://exchange.localhost/",
+ exchangeMasterPub: "123",
+ denomPubHash: "hash0",
+ maxAge: 32,
+ contributions: [Amounts.parseOrThrow("LOCAL:6")],
+ },
+ });
+});
+
+test("DD91 pruning remains exact when selected values exceed the amount limit", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:4503599627370496"),
+ });
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:4503599627370496" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:2251799813685248" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(Object.keys(coins ?? {}), [
+ "hash0;32;http://exchange.localhost/",
+ ]);
+});
+
+test("DD91 prefers the denomination that expires first", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:1"),
+ });
+ const candidates = createCandidates([
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]);
+ candidates[0].stampExpireDeposit = AbsoluteTime.toProtocolTimestamp(
+ AbsoluteTime.addDuration(
+ AbsoluteTime.now(),
+ Duration.fromSpec({ hours: 2 }),
+ ),
+ );
+ candidates[1].stampExpireDeposit = inTheDistantFuture;
+
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ candidates,
+ tally,
+ );
+
+ assert.deepStrictEqual(Object.keys(coins ?? {}), [
+ "hash1;32;http://exchange.localhost/",
+ ]);
+});
+
+test("DD91 replaces small coins when that avoids customer fees", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:3.7"),
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.1");
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:4" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 4,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(coins, {
+ "hash0;32;http://exchange.localhost/": {
+ exchangeBaseUrl: "http://exchange.localhost/",
+ exchangeMasterPub: "123",
+ denomPubHash: "hash0",
+ maxAge: 32,
+ contributions: [Amounts.parseOrThrow("LOCAL:3.7")],
},
+ });
+ assert.deepStrictEqual(
+ tally.customerDepositFees,
+ Amounts.parseOrThrow("LOCAL:0"),
+ );
+ assert.deepStrictEqual(
+ tally.totalDepositFees,
+ Amounts.parseOrThrow("LOCAL:0.1"),
+ );
+});
+
+test("DD91 prunes coins made redundant by lower fees", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:3.8"),
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.1");
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:4" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 4,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:0.1" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(coins, {
+ "hash0;32;http://exchange.localhost/": {
+ exchangeBaseUrl: "http://exchange.localhost/",
+ exchangeMasterPub: "123",
+ denomPubHash: "hash0",
+ maxAge: 32,
+ contributions: [Amounts.parseOrThrow("LOCAL:3.8")],
+ },
+ });
+});
+
+test("DD91 keeps spending an overabundant small denomination", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:3.7"),
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.1");
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:4" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 21,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(coins, {
"hash1;32;http://exchange.localhost/": {
exchangeBaseUrl: "http://exchange.localhost/",
exchangeMasterPub: "123",
denomPubHash: "hash1",
maxAge: 32,
- contributions: [Amounts.parseOrThrow("LOCAL:1")],
+ contributions: [
+ Amounts.parseOrThrow("LOCAL:1"),
+ Amounts.parseOrThrow("LOCAL:1"),
+ Amounts.parseOrThrow("LOCAL:1"),
+ Amounts.parseOrThrow("LOCAL:1"),
+ ],
},
});
});
+test("DD91 still optimizes at exactly the 5*F_D balance threshold", (t) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:3.7"),
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.1");
+ const coins = testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ createCandidates([
+ {
+ amount: "LOCAL:4" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 20,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]),
+ tally,
+ );
+
+ assert.deepStrictEqual(Object.keys(coins ?? {}), [
+ "hash0;32;http://exchange.localhost/",
+ ]);
+ assert.deepStrictEqual(
+ tally.customerDepositFees,
+ Amounts.parseOrThrow("LOCAL:0"),
+ );
+});
+
+test("DD91 selection is independent of candidate input order", (t) => {
+ const candidates = createCandidates([
+ {
+ amount: "LOCAL:4" as AmountString,
+ numAvailable: 1,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ {
+ amount: "LOCAL:1" as AmountString,
+ numAvailable: 4,
+ depositFee: "LOCAL:0.1" as AmountString,
+ fromExchange: "http://exchange.localhost/",
+ fromMasterPub: "123",
+ },
+ ]);
+ const select = (orderedCandidates: AvailableCoinsOfDenom[]) => {
+ const tally = emptyTallyForPeerPayment({
+ instructedAmount: Amounts.parseOrThrow("LOCAL:3.7"),
+ });
+ tally.amountDepositFeeLimitRemaining = Amounts.parseOrThrow("LOCAL:0.1");
+ return testing_selectGreedy(
+ { wireFeesPerExchange: {} },
+ orderedCandidates,
+ tally,
+ );
+ };
+
+ assert.deepStrictEqual(select(candidates), select([...candidates].reverse()));
+});
+
test("prefer exact denom", (t) => {
const instructedAmount = Amounts.parseOrThrow("LOCAL:2");
const tally = emptyTallyForPeerPayment({
diff --git a/packages/taler-wallet-core/src/coinSelection.ts b/packages/taler-wallet-core/src/coinSelection.ts
@@ -779,93 +779,441 @@ function selectGreedyDefault(
candidateDenoms: AvailableCoinsOfDenom[],
tally: CoinSelectionTally,
): SelResult | undefined {
- const selectedDenom: SelResult = {};
+ const baseTally = cloneTally(tally);
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(
+ const candidates = candidateDenoms
+ .filter((denom) => {
+ const meta = getCandidateSelectionMeta(denom);
+ return denom.numAvailable > 0 && meta.depositFee <= meta.value;
+ })
+ .sort(compareCandidateDenoms);
+ const selection: MutableCoinSelection = {
+ coins: [],
+ selectedCountByDenom: new Map(),
+ totals: {
+ value: 0n,
+ depositFees: 0n,
+ wireFees: 0n,
+ exchangeCoinCount: new Map(),
+ },
+ };
+
+ // DD91 pass 1: add the smallest, earliest-expiring coins until the
+ // selection covers the payment and the fees not covered by the merchant.
+ addCoins: for (const denom of candidates) {
+ for (let i = 0; i < denom.numAvailable; i++) {
+ addSelectedCoin(selection, denom, req, baseTally);
+ if (selectionIsSufficient(selection.totals, baseTally)) {
+ break addCoins;
+ }
+ }
+ }
+ if (!selectionIsSufficient(selection.totals, baseTally)) {
+ return undefined;
+ }
+
+ pruneSelection(selection, req, baseTally);
+
+ reduceSelectionFees(selection, candidates, req, baseTally);
+ // Lower fees can leave another coin redundant even though replacements
+ // preserve the total denomination value.
+ pruneSelection(selection, req, baseTally);
+
+ const finalCoins = selection.coins
+ .filter((coin) => coin.selected)
+ .sort((a, b) => compareCandidateDenoms(a.denom, b.denom));
+ checkLogicInvariant(
+ finalCoins.length > 0 || Amounts.isZero(tally.amountPayRemaining),
+ );
+
+ // Account for all fees before assigning the change to the smallest coin.
+ // The selection is irreducible after pass 2, so the excess is smaller than
+ // that coin's value.
+ for (const coin of finalCoins) {
+ tallyFees(
+ tally,
+ req.wireFeesPerExchange,
+ coin.denom.exchangeBaseUrl,
+ Amounts.parseOrThrow(coin.denom.feeDeposit),
+ );
+ }
+ const excess = amountFromUnits(
+ currency,
+ selection.totals.value - amountToUnits(tally.amountPayRemaining),
+ );
+ if (finalCoins.length > 0) {
+ checkLogicInvariant(Amounts.cmp(excess, finalCoins[0].denom.value) < 0);
+ }
+ const selectedDenom: SelResult = {};
+ for (let i = 0; i < finalCoins.length; i++) {
+ const denom = finalCoins[i].denom;
+ const contribution =
+ i === 0
+ ? Amounts.sub(denom.value, excess).amount
+ : Amounts.parseOrThrow(denom.value);
+ applyContributions(selectedDenom, [contribution], denom);
+ tally.amountPayRemaining = Amounts.sub(
tally.amountPayRemaining,
- req.wireFeesPerExchange[denom.exchangeBaseUrl] ??
- Amounts.zeroOfCurrency(currency),
- denom.feeDeposit,
+ contribution,
).amount;
- if (denom.numAvailable <= 0) {
+ }
+ checkLogicInvariant(Amounts.isZero(tally.amountPayRemaining));
+ return selectedDenom;
+}
+
+interface SelectedCandidateCoin {
+ denom: AvailableCoinsOfDenom;
+ selected: boolean;
+}
+
+interface SelectionTotals {
+ value: bigint;
+ depositFees: bigint;
+ wireFees: bigint;
+ exchangeCoinCount: Map<string, number>;
+}
+
+interface MutableCoinSelection {
+ coins: SelectedCandidateCoin[];
+ selectedCountByDenom: Map<AvailableCoinsOfDenom, number>;
+ totals: SelectionTotals;
+}
+
+interface CandidateSelectionMeta {
+ value: bigint;
+ depositFee: bigint;
+ expireDeposit: AbsoluteTime;
+}
+
+const candidateSelectionMeta = new WeakMap<
+ AvailableCoinsOfDenom,
+ CandidateSelectionMeta
+>();
+
+function getCandidateSelectionMeta(
+ denom: AvailableCoinsOfDenom,
+): CandidateSelectionMeta {
+ let meta = candidateSelectionMeta.get(denom);
+ if (!meta) {
+ meta = {
+ value: amountToUnits(denom.value),
+ depositFee: amountToUnits(denom.feeDeposit),
+ expireDeposit: AbsoluteTime.fromProtocolTimestamp(
+ denom.stampExpireDeposit,
+ ),
+ };
+ candidateSelectionMeta.set(denom, meta);
+ }
+ return meta;
+}
+
+function compareBigInt(left: bigint, right: bigint): number {
+ return left < right ? -1 : left > right ? 1 : 0;
+}
+
+/**
+ * DD91 pass 2: consider removals from largest to smallest. Walking the
+ * ascending selection backwards also removes later-expiring coins first
+ * within one denomination.
+ */
+function pruneSelection(
+ selection: MutableCoinSelection,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ for (let i = selection.coins.length - 1; i >= 0; i--) {
+ const coin = selection.coins[i];
+ if (!coin.selected) {
continue;
}
- if (Amounts.cmp(denom.value, tally.amountPayRemaining) < 0) {
- break;
+ removeSelectedCoin(selection, coin, req, baseTally);
+ if (!selectionIsSufficient(selection.totals, baseTally)) {
+ restoreSelectedCoin(selection, coin, req, baseTally);
}
- if (Amounts.cmp(denom.value, maxCost) > 0) {
- continue;
+ }
+}
+
+function compareCandidateDenoms(
+ left: AvailableCoinsOfDenom,
+ right: AvailableCoinsOfDenom,
+): number {
+ const leftMeta = getCandidateSelectionMeta(left);
+ const rightMeta = getCandidateSelectionMeta(right);
+ return (
+ compareBigInt(leftMeta.value, rightMeta.value) ||
+ AbsoluteTime.cmp(leftMeta.expireDeposit, rightMeta.expireDeposit) ||
+ compareBigInt(leftMeta.depositFee, rightMeta.depositFee) ||
+ strcmp(left.exchangeBaseUrl, right.exchangeBaseUrl) ||
+ strcmp(left.denomPubHash, right.denomPubHash) ||
+ left.maxAge - right.maxAge
+ );
+}
+
+function selectionCustomerFees(
+ totals: SelectionTotals,
+ baseTally: CoinSelectionTally,
+): bigint {
+ const fees = totals.depositFees + totals.wireFees;
+ const allowance = amountToUnits(baseTally.amountDepositFeeLimitRemaining);
+ return fees > allowance ? fees - allowance : 0n;
+}
+
+function selectionIsSufficient(
+ totals: SelectionTotals,
+ baseTally: CoinSelectionTally,
+): boolean {
+ const required =
+ amountToUnits(baseTally.amountPayRemaining) +
+ selectionCustomerFees(totals, baseTally);
+ return totals.value >= required;
+}
+
+function addSelectionTotals(
+ totals: SelectionTotals,
+ denom: AvailableCoinsOfDenom,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ const meta = getCandidateSelectionMeta(denom);
+ totals.value += meta.value;
+ totals.depositFees += meta.depositFee;
+ const oldCount = totals.exchangeCoinCount.get(denom.exchangeBaseUrl) ?? 0;
+ if (
+ oldCount === 0 &&
+ !baseTally.wireFeeCoveredForExchange.has(denom.exchangeBaseUrl)
+ ) {
+ const wireFee = req.wireFeesPerExchange[denom.exchangeBaseUrl];
+ totals.wireFees += wireFee ? amountToUnits(wireFee) : 0n;
+ }
+ totals.exchangeCoinCount.set(denom.exchangeBaseUrl, oldCount + 1);
+}
+
+function removeSelectionTotals(
+ totals: SelectionTotals,
+ denom: AvailableCoinsOfDenom,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ const meta = getCandidateSelectionMeta(denom);
+ totals.value -= meta.value;
+ totals.depositFees -= meta.depositFee;
+ const oldCount = totals.exchangeCoinCount.get(denom.exchangeBaseUrl) ?? 0;
+ checkLogicInvariant(oldCount > 0);
+ if (oldCount === 1) {
+ totals.exchangeCoinCount.delete(denom.exchangeBaseUrl);
+ if (!baseTally.wireFeeCoveredForExchange.has(denom.exchangeBaseUrl)) {
+ const wireFee = req.wireFeesPerExchange[denom.exchangeBaseUrl];
+ totals.wireFees -= wireFee ? amountToUnits(wireFee) : 0n;
}
- 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;
+ } else {
+ totals.exchangeCoinCount.set(denom.exchangeBaseUrl, oldCount - 1);
+ }
+}
+
+function addSelectedCoin(
+ selection: MutableCoinSelection,
+ denom: AvailableCoinsOfDenom,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): SelectedCandidateCoin {
+ const coin = { denom, selected: false };
+ selection.coins.push(coin);
+ restoreSelectedCoin(selection, coin, req, baseTally);
+ return coin;
+}
+
+function restoreSelectedCoin(
+ selection: MutableCoinSelection,
+ coin: SelectedCandidateCoin,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ checkLogicInvariant(!coin.selected);
+ coin.selected = true;
+ selection.selectedCountByDenom.set(
+ coin.denom,
+ (selection.selectedCountByDenom.get(coin.denom) ?? 0) + 1,
+ );
+ addSelectionTotals(selection.totals, coin.denom, req, baseTally);
+}
+
+function removeSelectedCoin(
+ selection: MutableCoinSelection,
+ coin: SelectedCandidateCoin,
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ checkLogicInvariant(coin.selected);
+ coin.selected = false;
+ const oldCount = selection.selectedCountByDenom.get(coin.denom) ?? 0;
+ checkLogicInvariant(oldCount > 0);
+ if (oldCount === 1) {
+ selection.selectedCountByDenom.delete(coin.denom);
+ } else {
+ selection.selectedCountByDenom.set(coin.denom, oldCount - 1);
+ }
+ removeSelectionTotals(selection.totals, coin.denom, req, baseTally);
+}
+
+function denominationFactor(
+ larger: AvailableCoinsOfDenom,
+ smaller: AvailableCoinsOfDenom,
+ exact: boolean,
+): number | undefined {
+ const largerUnits = getCandidateSelectionMeta(larger).value;
+ const smallerUnits = getCandidateSelectionMeta(smaller).value;
+ if (smallerUnits === 0n) {
+ return undefined;
+ }
+ const quotient = largerUnits / smallerUnits;
+ const hasRemainder = largerUnits % smallerUnits !== 0n;
+ const factor = quotient + (hasRemainder ? 1n : 0n);
+ if ((exact && hasRemainder) || factor > BigInt(Number.MAX_SAFE_INTEGER)) {
+ return undefined;
+ }
+ return Number(factor);
+}
+
+const amountFractionalBaseBigInt = 100_000_000n;
+
+function amountToUnits(amount: AmountJson | string): bigint {
+ const parsed = Amounts.parseOrThrow(amount);
+ return (
+ BigInt(parsed.value) * amountFractionalBaseBigInt + BigInt(parsed.fraction)
+ );
+}
+
+function amountFromUnits(currency: string, units: bigint): AmountJson {
+ checkLogicInvariant(units >= 0n);
+ const value = Number(units / amountFractionalBaseBigInt);
+ checkLogicInvariant(Number.isSafeInteger(value));
+ return {
+ currency,
+ value,
+ fraction: Number(units % amountFractionalBaseBigInt),
+ };
+}
+
+/**
+ * DD91 pass 3: replace exact groups of small coins with a larger coin when
+ * this lowers the customer's fees and the wallet does not have an excess of
+ * that small denomination.
+ */
+function reduceSelectionFees(
+ selection: MutableCoinSelection,
+ candidates: AvailableCoinsOfDenom[],
+ req: SelectGreedyRequest,
+ baseTally: CoinSelectionTally,
+): void {
+ if (selectionCustomerFees(selection.totals, baseTally) === 0n) {
+ return;
+ }
+
+ const groups: AvailableCoinsOfDenom[][] = [];
+ for (const candidate of candidates) {
+ const last = groups[groups.length - 1];
+ if (
+ !last ||
+ getCandidateSelectionMeta(last[0]).value !==
+ getCandidateSelectionMeta(candidate).value
+ ) {
+ groups.push([candidate]);
+ } else {
+ last.push(candidate);
}
}
- // Otherwise use smallest coins first.
- for (let i = 0; i < candidateDenoms.length; i++) {
- const denom = candidateDenoms[candidateDenoms.length - i - 1];
- const contributions: AmountJson[] = [];
+ const selectedCoinsByValue = new Map<bigint, SelectedCandidateCoin[]>();
+ for (const coin of selection.coins) {
+ if (!coin.selected) {
+ continue;
+ }
+ const value = getCandidateSelectionMeta(coin.denom).value;
+ const coins = selectedCoinsByValue.get(value) ?? [];
+ coins.push(coin);
+ selectedCoinsByValue.set(value, coins);
+ }
- // 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) {
+ // An excess in any non-largest denomination means that reducing coin
+ // count would work against DD91's primary goal of draining small coins.
+ for (let i = 0; i + 1 < groups.length; i++) {
+ const factor = denominationFactor(groups[i + 1][0], groups[i][0], false);
+ if (factor === undefined || factor < 2) {
continue;
}
+ const numAvailable = groups[i].reduce(
+ (sum, candidate) => sum + candidate.numAvailable,
+ 0,
+ );
+ if (numAvailable > 5 * factor) {
+ return;
+ }
+ }
+ for (let smallIndex = 0; smallIndex + 1 < groups.length; smallIndex++) {
+ const smallGroup = groups[smallIndex];
+ const smallValue = getCandidateSelectionMeta(smallGroup[0]).value;
+ const selectedSmallCoins = selectedCoinsByValue.get(smallValue) ?? [];
+ selectedSmallCoins.sort((a, b) => compareCandidateDenoms(b.denom, a.denom));
for (
- let j = 0;
- j < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining);
- j++
+ let largeIndex = smallIndex + 1;
+ largeIndex < groups.length;
+ largeIndex++
) {
- // Save the allowance *before* tallying.
- const depositFeeAllowance = tally.amountDepositFeeLimitRemaining;
-
- tallyFees(
- tally,
- req.wireFeesPerExchange,
- denom.exchangeBaseUrl,
- Amounts.parseOrThrow(denom.feeDeposit),
- );
-
- const coinSpend = Amounts.max(
- Amounts.min(tally.amountPayRemaining, denom.value),
- // Underflow saturates to zero
- Amounts.sub(denom.feeDeposit, depositFeeAllowance).amount,
- );
-
- tally.amountPayRemaining = Amounts.sub(
- tally.amountPayRemaining,
- coinSpend,
- ).amount;
+ const largeGroup = groups[largeIndex];
+ const factor = denominationFactor(largeGroup[0], smallGroup[0], true);
+ if (factor === undefined || factor < 2) {
+ continue;
+ }
- contributions.push(coinSpend);
+ while (selectedSmallCoins.length >= factor) {
+ const smallCoins = selectedSmallCoins.slice(0, factor);
+
+ let replacementMade = false;
+ for (const largeDenom of largeGroup) {
+ const numSelected =
+ selection.selectedCountByDenom.get(largeDenom) ?? 0;
+ if (numSelected >= largeDenom.numAvailable) {
+ continue;
+ }
+ const feesBefore = selectionCustomerFees(selection.totals, baseTally);
+ for (const coin of smallCoins) {
+ removeSelectedCoin(selection, coin, req, baseTally);
+ }
+ const replacement = addSelectedCoin(
+ selection,
+ largeDenom,
+ req,
+ baseTally,
+ );
+ const feesAfter = selectionCustomerFees(selection.totals, baseTally);
+ if (
+ feesAfter < feesBefore &&
+ selectionIsSufficient(selection.totals, baseTally)
+ ) {
+ replacementMade = true;
+ selectedSmallCoins.splice(0, factor);
+ const largeValue = getCandidateSelectionMeta(largeDenom).value;
+ const selectedLargeCoins =
+ selectedCoinsByValue.get(largeValue) ?? [];
+ selectedLargeCoins.push(replacement);
+ selectedCoinsByValue.set(largeValue, selectedLargeCoins);
+ break;
+ }
+ removeSelectedCoin(selection, replacement, req, baseTally);
+ for (const coin of smallCoins) {
+ restoreSelectedCoin(selection, coin, req, baseTally);
+ }
+ }
+ if (!replacementMade) {
+ break;
+ }
+ if (selectionCustomerFees(selection.totals, baseTally) === 0n) {
+ return;
+ }
+ }
}
-
- applyContributions(selectedDenom, contributions, denom);
}
- return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined;
}
function selectForced(
