improved pay coin selection

support for multiple exchanges and healing a previous selection

7 files changed, 478 insertions, 210 deletions

diff --git a/packages/taler-wallet-core/src/operations/backup/import.ts b/packages/taler-wallet-core/src/operations/backup/import.ts
index 416b068e4..2e33c2070 100644
--- a/packages/taler-wallet-core/src/operations/backup/import.ts
+++ b/packages/taler-wallet-core/src/operations/backup/import.ts
@@ -27,7 +27,6 @@ import {
   ExchangeUpdateStatus,
   ExchangeWireInfo,
   getTimestampNow,
-  PayCoinSelection,
   ProposalDownload,
   ProposalStatus,
   RefreshReason,
@@ -49,6 +48,7 @@ import {
   BackupRefundState,
   WalletBackupContentV1,
 } from "../../types/backupTypes";
+import { PayCoinSelection } from "../../util/coinSelection";
 import { j2s } from "../../util/helpers";
 import { checkDbInvariant, checkLogicInvariant } from "../../util/invariants";
 import { Logger } from "../../util/logging";
diff --git a/packages/taler-wallet-core/src/operations/deposits.ts b/packages/taler-wallet-core/src/operations/deposits.ts
index 50921a170..53f2529b2 100644
--- a/packages/taler-wallet-core/src/operations/deposits.ts
+++ b/packages/taler-wallet-core/src/operations/deposits.ts
@@ -37,6 +37,7 @@ import {
   codecForString,
   codecOptional,
 } from "../util/codec";
+import { selectPayCoins } from "../util/coinSelection";
 import { canonicalJson } from "../util/helpers";
 import { readSuccessResponseJsonOrThrow } from "../util/http";
 import { parsePaytoUri } from "../util/payto";
@@ -54,7 +55,7 @@ import {
   applyCoinSpend,
   extractContractData,
   generateDepositPermissions,
-  getCoinsForPayment,
+  getCandidatePayCoins,
   getEffectiveDepositAmount,
   getTotalPaymentCost,
 } from "./pay";
@@ -363,7 +364,26 @@ export async function createDepositGroup(
     "",
   );
 
-  const payCoinSel = await getCoinsForPayment(ws, contractData);
+  const candidates = await getCandidatePayCoins(ws, {
+    allowedAuditors: contractData.allowedAuditors,
+    allowedExchanges: contractData.allowedExchanges,
+    amount: contractData.amount,
+    maxDepositFee: contractData.maxDepositFee,
+    maxWireFee: contractData.maxWireFee,
+    timestamp: contractData.timestamp,
+    wireFeeAmortization: contractData.wireFeeAmortization,
+    wireMethod: contractData.wireMethod,
+  });
+
+  const payCoinSel = selectPayCoins({
+    candidates,
+    contractTermsAmount: contractData.amount,
+    depositFeeLimit: contractData.maxDepositFee,
+    wireFeeAmortization: contractData.wireFeeAmortization ?? 1,
+    wireFeeLimit: contractData.maxWireFee,
+    prevPayCoins: [],
+  });
+
 
   if (!payCoinSel) {
     throw Error("insufficient funds");
diff --git a/packages/taler-wallet-core/src/operations/pay.ts b/packages/taler-wallet-core/src/operations/pay.ts
index 3add9bbbf..cdacb2eba 100644
--- a/packages/taler-wallet-core/src/operations/pay.ts
+++ b/packages/taler-wallet-core/src/operations/pay.ts
@@ -34,7 +34,6 @@ import {
   WalletContractData,
   CoinRecord,
   DenominationRecord,
-  PayCoinSelection,
   AbortStatus,
   AllowedExchangeInfo,
   AllowedAuditorInfo,
@@ -55,7 +54,7 @@ import {
   PreparePayResultType,
   ConfirmPayResultType,
 } from "../types/walletTypes";
-import * as Amounts from "../util/amounts";
+import { Amounts } from "../util/amounts";
 import { AmountJson } from "../util/amounts";
 import { Logger } from "../util/logging";
 import { parsePayUri } from "../util/taleruri";
@@ -95,38 +94,13 @@ import {
   getRetryDuration,
 } from "../util/retries";
 import { TransactionHandle } from "../util/query";
+import { PayCoinSelection, CoinCandidateSelection, AvailableCoinInfo, selectPayCoins } from "../util/coinSelection";
 
 /**
  * Logger.
  */
 const logger = new Logger("pay.ts");
 
-/**
- * Structure to describe a coin that is available to be
- * used in a payment.
- */
-export interface AvailableCoinInfo {
-  /**
-   * Public key of the coin.
-   */
-  coinPub: string;
-
-  /**
-   * Coin's denomination public key.
-   */
-  denomPub: string;
-
-  /**
-   * Amount still remaining (typically the full amount,
-   * as coins are always refreshed after use.)
-   */
-  availableAmount: AmountJson;
-
-  /**
-   * Deposit fee for the coin.
-   */
-  feeDeposit: AmountJson;
-}
 
 /**
  * Compute the total cost of a payment to the customer.
@@ -212,104 +186,6 @@ export async function getEffectiveDepositAmount(
   return Amounts.sub(Amounts.sum(amt).amount, Amounts.sum(fees).amount).amount;
 }
 
-/**
- * Given a list of available coins, select coins to spend under the merchant's
- * constraints.
- *
- * This function is only exported for the sake of unit tests.
- */
-export function selectPayCoins(
-  acis: AvailableCoinInfo[],
-  contractTermsAmount: AmountJson,
-  customerWireFees: AmountJson,
-  depositFeeLimit: AmountJson,
-): PayCoinSelection | undefined {
-  if (acis.length === 0) {
-    return undefined;
-  }
-  const coinPubs: string[] = [];
-  const coinContributions: AmountJson[] = [];
-  // Sort by available amount (descending),  deposit fee (ascending) and
-  // denomPub (ascending) if deposit fee is the same
-  // (to guarantee deterministic results)
-  acis.sort(
-    (o1, o2) =>
-      -Amounts.cmp(o1.availableAmount, o2.availableAmount) ||
-      Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
-      strcmp(o1.denomPub, o2.denomPub),
-  );
-  const paymentAmount = Amounts.add(contractTermsAmount, customerWireFees)
-    .amount;
-  const currency = paymentAmount.currency;
-  let amountPayRemaining = paymentAmount;
-  let amountDepositFeeLimitRemaining = depositFeeLimit;
-  const customerDepositFees = Amounts.getZero(currency);
-  for (const aci of acis) {
-    // Don't use this coin if depositing it is more expensive than
-    // the amount it would give the merchant.
-    if (Amounts.cmp(aci.feeDeposit, aci.availableAmount) >= 0) {
-      continue;
-    }
-    if (amountPayRemaining.value === 0 && amountPayRemaining.fraction === 0) {
-      // We have spent enough!
-      break;
-    }
-
-    // How much does the user spend on deposit fees for this coin?
-    const depositFeeSpend = Amounts.sub(
-      aci.feeDeposit,
-      amountDepositFeeLimitRemaining,
-    ).amount;
-
-    if (Amounts.isZero(depositFeeSpend)) {
-      // Fees are still covered by the merchant.
-      amountDepositFeeLimitRemaining = Amounts.sub(
-        amountDepositFeeLimitRemaining,
-        aci.feeDeposit,
-      ).amount;
-    } else {
-      amountDepositFeeLimitRemaining = Amounts.getZero(currency);
-    }
-
-    let coinSpend: AmountJson;
-    const amountActualAvailable = Amounts.sub(
-      aci.availableAmount,
-      depositFeeSpend,
-    ).amount;
-
-    if (Amounts.cmp(amountActualAvailable, amountPayRemaining) > 0) {
-      // Partial spending, as the coin is worth more than the remaining
-      // amount to pay.
-      coinSpend = Amounts.add(amountPayRemaining, depositFeeSpend).amount;
-      // Make sure we contribute at least the deposit fee, otherwise
-      // contributing this coin would cause a loss for the merchant.
-      if (Amounts.cmp(coinSpend, aci.feeDeposit) < 0) {
-        coinSpend = aci.feeDeposit;
-      }
-      amountPayRemaining = Amounts.getZero(currency);
-    } else {
-      // Spend the full remaining amount on the coin
-      coinSpend = aci.availableAmount;
-      amountPayRemaining = Amounts.add(amountPayRemaining, depositFeeSpend)
-        .amount;
-      amountPayRemaining = Amounts.sub(amountPayRemaining, aci.availableAmount)
-        .amount;
-    }
-
-    coinPubs.push(aci.coinPub);
-    coinContributions.push(coinSpend);
-  }
-  if (Amounts.isZero(amountPayRemaining)) {
-    return {
-      paymentAmount: contractTermsAmount,
-      coinContributions,
-      coinPubs,
-      customerDepositFees,
-      customerWireFees,
-    };
-  }
-  return undefined;
-}
 
 export function isSpendableCoin(
   coin: CoinRecord,
@@ -329,6 +205,7 @@ export function isSpendableCoin(
 
 export interface CoinSelectionRequest {
   amount: AmountJson;
+
   allowedAuditors: AllowedAuditorInfo[];
   allowedExchanges: AllowedExchangeInfo[];
 
@@ -347,19 +224,23 @@ export interface CoinSelectionRequest {
 }
 
 /**
- * Select coins from the wallet's database that can be used
- * to pay for the given contract.
+ * Get candidate coins.  From these candidate coins,
+ * the actual contributions will be computed later.
  *
- * If payment is impossible, undefined is returned.
+ * The resulting candidate coin list is sorted deterministically.
+ *
+ * TODO: Exclude more coins:
+ * - when we already have a coin with more remaining amount than
+ *   the payment amount, coins with even higher amounts can be skipped.
  */
-export async function getCoinsForPayment(
+export async function getCandidatePayCoins(
   ws: InternalWalletState,
   req: CoinSelectionRequest,
-): Promise<PayCoinSelection | undefined> {
-  const remainingAmount = req.amount;
+): Promise<CoinCandidateSelection> {
+  const candidateCoins: AvailableCoinInfo[] = [];
+  const wireFeesPerExchange: Record<string, AmountJson> = {};
 
   const exchanges = await ws.db.iter(Stores.exchanges).toArray();
-
   for (const exchange of exchanges) {
     let isOkay = false;
     const exchangeDetails = exchange.details;
@@ -416,7 +297,6 @@ export async function getCoinsForPayment(
       throw Error("db inconsistent");
     }
     const currency = firstDenom.value.currency;
-    const acis: AvailableCoinInfo[] = [];
     for (const coin of coins) {
       const denom = await ws.db.get(Stores.denominations, [
         exchange.baseUrl,
@@ -434,11 +314,12 @@ export async function getCoinsForPayment(
       if (!isSpendableCoin(coin, denom)) {
         continue;
       }
-      acis.push({
+      candidateCoins.push({
         availableAmount: coin.currentAmount,
         coinPub: coin.coinPub,
         denomPub: coin.denomPub,
         feeDeposit: denom.feeDeposit,
+        exchangeBaseUrl: denom.exchangeBaseUrl,
       });
     }
 
@@ -449,32 +330,25 @@ export async function getCoinsForPayment(
         break;
       }
     }
-
-    let customerWireFee: AmountJson;
-
-    if (wireFee && req.wireFeeAmortization) {
-      const amortizedWireFee = Amounts.divide(wireFee, req.wireFeeAmortization);
-      if (Amounts.cmp(req.maxWireFee, amortizedWireFee) < 0) {
-        customerWireFee = amortizedWireFee;
-      } else {
-        customerWireFee = Amounts.getZero(currency);
-      }
-    } else {
-      customerWireFee = Amounts.getZero(currency);
-    }
-
-    // Try if paying using this exchange works
-    const res = selectPayCoins(
-      acis,
-      remainingAmount,
-      customerWireFee,
-      req.maxDepositFee,
-    );
-    if (res) {
-      return res;
+    if (wireFee) {
+      wireFeesPerExchange[exchange.baseUrl] = wireFee;
     }
   }
-  return undefined;
+
+  // Sort by available amount (descending),  deposit fee (ascending) and
+  // denomPub (ascending) if deposit fee is the same
+  // (to guarantee deterministic results)
+  candidateCoins.sort(
+    (o1, o2) =>
+      -Amounts.cmp(o1.availableAmount, o2.availableAmount) ||
+      Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
+      strcmp(o1.denomPub, o2.denomPub),
+  );
+
+  return {
+    candidateCoins,
+    wireFeesPerExchange,
+  };
 }
 
 export async function applyCoinSpend(
@@ -1009,13 +883,18 @@ async function storePayReplaySuccess(
  * We do this by going through the coin history provided by the exchange and
  * (1) verifying the signatures from the exchange
  * (2) adjusting the remaining coin value
- * (3) re-do coin selection.
+ * (3) re-do coin selection with the bad coin removed
  */
 async function handleInsufficientFunds(
   ws: InternalWalletState,
   proposalId: string,
   err: TalerErrorDetails,
 ): Promise<void> {
+  const proposal = await ws.db.get(Stores.purchases, proposalId);
+  if (!proposal) {
+    return;
+  }
+
   throw Error("payment re-denomination not implemented yet");
 }
 
@@ -1232,7 +1111,24 @@ export async function checkPaymentByProposalId(
 
   if (!purchase) {
     // If not already paid, check if we could pay for it.
-    const res = await getCoinsForPayment(ws, contractData);
+    const candidates = await getCandidatePayCoins(ws, {
+      allowedAuditors: contractData.allowedAuditors,
+      allowedExchanges: contractData.allowedExchanges,
+      amount: contractData.amount,
+      maxDepositFee: contractData.maxDepositFee,
+      maxWireFee: contractData.maxWireFee,
+      timestamp: contractData.timestamp,
+      wireFeeAmortization: contractData.wireFeeAmortization,
+      wireMethod: contractData.wireMethod,
+    });
+    const res = selectPayCoins({
+      candidates,
+      contractTermsAmount: contractData.amount,
+      depositFeeLimit: contractData.maxDepositFee,
+      wireFeeAmortization: contractData.wireFeeAmortization ?? 1,
+      wireFeeLimit: contractData.maxWireFee,
+      prevPayCoins: [],
+    });
 
     if (!res) {
       logger.info("not confirming payment, insufficient coins");
@@ -1434,12 +1330,34 @@ export async function confirmPay(
 
   logger.trace("confirmPay: purchase record does not exist yet");
 
-  const res = await getCoinsForPayment(ws, d.contractData);
+  const contractData = d.contractData;
+
+  const candidates = await getCandidatePayCoins(ws, {
+    allowedAuditors: contractData.allowedAuditors,
+    allowedExchanges: contractData.allowedExchanges,
+    amount: contractData.amount,
+    maxDepositFee: contractData.maxDepositFee,
+    maxWireFee: contractData.maxWireFee,
+    timestamp: contractData.timestamp,
+    wireFeeAmortization: contractData.wireFeeAmortization,
+    wireMethod: contractData.wireMethod,
+  });
+
+  const res = selectPayCoins({
+    candidates,
+    contractTermsAmount: contractData.amount,
+    depositFeeLimit: contractData.maxDepositFee,
+    wireFeeAmortization: contractData.wireFeeAmortization ?? 1,
+    wireFeeLimit: contractData.maxWireFee,
+    prevPayCoins: [],
+  });
 
   logger.trace("coin selection result", res);
 
   if (!res) {
     // Should not happen, since checkPay should be called first
+    // FIXME: Actually, this should be handled gracefully,
+    // and the status should be stored in the DB.
     logger.warn("not confirming payment, insufficient coins");
     throw Error("insufficient balance");
   }
diff --git a/packages/taler-wallet-core/src/types/dbTypes.ts b/packages/taler-wallet-core/src/types/dbTypes.ts
index 6c37971ad..689055df8 100644
--- a/packages/taler-wallet-core/src/types/dbTypes.ts
+++ b/packages/taler-wallet-core/src/types/dbTypes.ts
@@ -41,6 +41,7 @@ import { ReserveTransaction } from "./ReserveTransaction";
 import { Timestamp, Duration } from "../util/time";
 import { IDBKeyPath } from "@gnu-taler/idb-bridge";
 import { RetryInfo } from "../util/retries";
+import { PayCoinSelection } from "../util/coinSelection";
 
 export enum ReserveRecordStatus {
   /**
@@ -1138,36 +1139,6 @@ export interface WalletContractData {
   maxDepositFee: AmountJson;
 }
 
-/**
- * Result of selecting coins, contains the exchange, and selected
- * coins with their denomination.
- */
-export interface PayCoinSelection {
-  /**
-   * Amount requested by the merchant.
-   */
-  paymentAmount: AmountJson;
-
-  /**
-   * Public keys of the coins that were selected.
-   */
-  coinPubs: string[];
-
-  /**
-   * Amount that each coin contributes.
-   */
-  coinContributions: AmountJson[];
-
-  /**
-   * How much of the wire fees is the customer paying?
-   */
-  customerWireFees: AmountJson;
-
-  /**
-   * How much of the deposit fees is the customer paying?
-   */
-  customerDepositFees: AmountJson;
-}
 
 export enum AbortStatus {
   None = "none",
@@ -1210,6 +1181,16 @@ export interface PurchaseRecord {
 
   payCoinSelection: PayCoinSelection;
 
+  /**
+   * Pending removals from pay coin selection.
+   * 
+   * Used when a the pay coin selection needs to be changed
+   * because a coin became known as double-spent or invalid,
+   * but a new coin selection can't immediately be done, as
+   * there is not enough balance (e.g. when waiting for a refresh).
+   */
+  pendingRemovedCoinPubs?: string[];
+
   totalPayCost: AmountJson;
 
   /**
diff --git a/packages/taler-wallet-core/src/util/amounts.ts b/packages/taler-wallet-core/src/util/amounts.ts
index 801c3385e..7a242f41d 100644
--- a/packages/taler-wallet-core/src/util/amounts.ts
+++ b/packages/taler-wallet-core/src/util/amounts.ts
@@ -381,6 +381,25 @@ function mult(a: AmountJson, n: number): Result {
   return add(acc, x);
 }
 
+function max(a: AmountLike, b: AmountLike): AmountJson {
+  const cr = Amounts.cmp(a, b);
+  if (cr >= 0) {
+    return jsonifyAmount(a);
+  } else {
+    return jsonifyAmount(b);
+  }
+}
+
+function min(a: AmountLike, b: AmountLike): AmountJson {
+  const cr = Amounts.cmp(a, b);
+  if (cr >= 0) {
+    return jsonifyAmount(b);
+  } else {
+    return jsonifyAmount(a);
+  }
+}
+
+
 // Export all amount-related functions here for better IDE experience.
 export const Amounts = {
   stringify: stringify,
@@ -391,6 +410,8 @@ export const Amounts = {
   sum: sum,
   sub: sub,
   mult: mult,
+  max: max,
+  min: min,
   check: check,
   getZero: getZero,
   isZero: isZero,
diff --git a/packages/taler-wallet-core/src/wallet-test.ts b/packages/taler-wallet-core/src/util/coinSelection-test.ts
index 4b06accf2..3ac718aaf 100644
--- a/packages/taler-wallet-core/src/wallet-test.ts
+++ b/packages/taler-wallet-core/src/util/coinSelection-test.ts
@@ -1,24 +1,25 @@
 /*
- This file is part of TALER
- (C) 2017 Inria and GNUnet e.V.
+ This file is part of GNU Taler
+ (C) 2021 Taler Systems S.A.
 
- TALER is free software; you can redistribute it and/or modify it under the
+ GNU Taler is free software; you can redistribute it and/or modify it under the
  terms of the GNU General Public License as published by the Free Software
  Foundation; either version 3, or (at your option) any later version.
 
- TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
 
  You should have received a copy of the GNU General Public License along with
- TALER; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
  */
 
+/**
+ * Imports.
+ */
 import test from "ava";
-
-import { AmountJson } from "./util/amounts";
-import * as Amounts from "./util/amounts";
-import { selectPayCoins, AvailableCoinInfo } from "./operations/pay";
+import { AmountJson, Amounts } from "..";
+import { AvailableCoinInfo, selectPayCoins } from "./coinSelection";
 
 function a(x: string): AmountJson {
   const amt = Amounts.parse(x);
@@ -34,6 +35,7 @@ function fakeAci(current: string, feeDeposit: string): AvailableCoinInfo {
     coinPub: "foobar",
     denomPub: "foobar",
     feeDeposit: a(feeDeposit),
+    exchangeBaseUrl: "https://example.com/",
   };
 }
 
@@ -43,7 +45,17 @@ test("coin selection 1", (t) => {
     fakeAci("EUR:1.0", "EUR:0.0"),
   ];
 
-  const res = selectPayCoins(acis, a("EUR:2.0"), a("EUR:0"), a("EUR:0.1"));
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:2.0"),
+    depositFeeLimit: a("EUR:0.1"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
+
   if (!res) {
     t.fail();
     return;
@@ -59,7 +71,18 @@ test("coin selection 2", (t) => {
     // Merchant covers the fee, this one shouldn't be used
     fakeAci("EUR:1.0", "EUR:0.0"),
   ];
-  const res = selectPayCoins(acis, a("EUR:2.0"), a("EUR:0"), a("EUR:0.5"));
+
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:2.0"),
+    depositFeeLimit: a("EUR:0.5"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
+
   if (!res) {
     t.fail();
     return;
@@ -75,7 +98,18 @@ test("coin selection 3", (t) => {
     // this coin should be selected instead of previous one with fee
     fakeAci("EUR:1.0", "EUR:0.0"),
   ];
-  const res = selectPayCoins(acis, a("EUR:2.0"), a("EUR:0"), a("EUR:0.5"));
+
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:2.0"),
+    depositFeeLimit: a("EUR:0.5"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
+
   if (!res) {
     t.fail();
     return;
@@ -90,7 +124,18 @@ test("coin selection 4", (t) => {
     fakeAci("EUR:1.0", "EUR:0.5"),
     fakeAci("EUR:1.0", "EUR:0.5"),
   ];
-  const res = selectPayCoins(acis, a("EUR:2.0"), a("EUR:0"), a("EUR:0.5"));
+
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:2.0"),
+    depositFeeLimit: a("EUR:0.5"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
+
   if (!res) {
     t.fail();
     return;
@@ -105,7 +150,18 @@ test("coin selection 5", (t) => {
     fakeAci("EUR:1.0", "EUR:0.5"),
     fakeAci("EUR:1.0", "EUR:0.5"),
   ];
-  const res = selectPayCoins(acis, a("EUR:4.0"), a("EUR:0"), a("EUR:0.2"));
+
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:4.0"),
+    depositFeeLimit: a("EUR:0.2"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
+
   t.true(!res);
   t.pass();
 });
@@ -115,7 +171,16 @@ test("coin selection 6", (t) => {
     fakeAci("EUR:1.0", "EUR:0.5"),
     fakeAci("EUR:1.0", "EUR:0.5"),
   ];
-  const res = selectPayCoins(acis, a("EUR:2.0"), a("EUR:0"), a("EUR:0.2"));
+  const res = selectPayCoins({
+    candidates: {
+      candidateCoins: acis,
+      wireFeesPerExchange: {},
+    },
+    contractTermsAmount: a("EUR:2.0"),
+    depositFeeLimit: a("EUR:0.2"),
+    wireFeeLimit: a("EUR:0"),
+    wireFeeAmortization: 1,
+  });
   t.true(!res);
   t.pass();
 });
diff --git a/packages/taler-wallet-core/src/util/coinSelection.ts b/packages/taler-wallet-core/src/util/coinSelection.ts
new file mode 100644
index 000000000..d32ab6f3c
--- /dev/null
+++ b/packages/taler-wallet-core/src/util/coinSelection.ts
@@ -0,0 +1,263 @@
+/*
+ This file is part of GNU Taler
+ (C) 2021 Taler Systems S.A.
+
+ GNU Taler is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ */
+
+/**
+ * Selection of coins for payments.
+ *
+ * @author Florian Dold
+ */
+
+/**
+ * Imports.
+ */
+import { AmountJson, Amounts } from "./amounts";
+import { strcmp } from "./helpers";
+
+/**
+ * Result of selecting coins, contains the exchange, and selected
+ * coins with their denomination.
+ */
+export interface PayCoinSelection {
+  /**
+   * Amount requested by the merchant.
+   */
+  paymentAmount: AmountJson;
+
+  /**
+   * Public keys of the coins that were selected.
+   */
+  coinPubs: string[];
+
+  /**
+   * Amount that each coin contributes.
+   */
+  coinContributions: AmountJson[];
+
+  /**
+   * How much of the wire fees is the customer paying?
+   */
+  customerWireFees: AmountJson;
+
+  /**
+   * How much of the deposit fees is the customer paying?
+   */
+  customerDepositFees: AmountJson;
+}
+
+/**
+ * Structure to describe a coin that is available to be
+ * used in a payment.
+ */
+export interface AvailableCoinInfo {
+  /**
+   * Public key of the coin.
+   */
+  coinPub: string;
+
+  /**
+   * Coin's denomination public key.
+   */
+  denomPub: string;
+
+  /**
+   * Amount still remaining (typically the full amount,
+   * as coins are always refreshed after use.)
+   */
+  availableAmount: AmountJson;
+
+  /**
+   * Deposit fee for the coin.
+   */
+  feeDeposit: AmountJson;
+
+  exchangeBaseUrl: string;
+}
+
+type PreviousPayCoins = {
+  coinPub: string;
+  contribution: AmountJson;
+  feeDeposit: AmountJson;
+  exchangeBaseUrl: string;
+}[];
+
+export interface CoinCandidateSelection {
+  candidateCoins: AvailableCoinInfo[];
+  wireFeesPerExchange: Record<string, AmountJson>;
+}
+
+export interface SelectPayCoinRequest {
+  candidates: CoinCandidateSelection;
+  contractTermsAmount: AmountJson;
+  depositFeeLimit: AmountJson;
+  wireFeeLimit: AmountJson;
+  wireFeeAmortization: number;
+  prevPayCoins?: PreviousPayCoins;
+}
+
+/**
+ * Given a list of candidate coins, select coins to spend under the merchant's
+ * constraints.
+ *
+ * The prevPayCoins can be specified to "repair" a coin selection
+ * by adding additional coins, after a broken (e.g. double-spent) coin
+ * has been removed from the selection.
+ *
+ * This function is only exported for the sake of unit tests.
+ */
+export function selectPayCoins(
+  req: SelectPayCoinRequest,
+): PayCoinSelection | undefined {
+  const {
+    candidates,
+    contractTermsAmount,
+    depositFeeLimit,
+    wireFeeLimit,
+    wireFeeAmortization,
+  } = req;
+
+  if (candidates.candidateCoins.length === 0) {
+    return undefined;
+  }
+  const coinPubs: string[] = [];
+  const coinContributions: AmountJson[] = [];
+  const currency = contractTermsAmount.currency;
+  // Amount that still needs to be paid.
+  // May increase during the computation when fees need to be covered.
+  let amountPayRemaining = contractTermsAmount;
+  // Allowance given by the merchant towards wire fees
+  let amountWireFeeLimitRemaining = wireFeeLimit;
+  // Allowance given by the merchant towards deposit fees
+  // (and wire fees after wire fee limit is exhausted)
+  let amountDepositFeeLimitRemaining = depositFeeLimit;
+  let customerDepositFees = Amounts.getZero(currency);
+  let customerWireFees = Amounts.getZero(currency);
+
+  const wireFeeCoveredForExchange: Set<string> = new Set();
+
+  /**
+   * Account for the fees of spending a coin.
+   */
+  function tallyFees(exchangeBaseUrl: string, feeDeposit: AmountJson): void {
+    if (!wireFeeCoveredForExchange.has(exchangeBaseUrl)) {
+      const wf =
+        candidates.wireFeesPerExchange[exchangeBaseUrl] ??
+        Amounts.getZero(currency);
+      const wfForgiven = Amounts.min(amountWireFeeLimitRemaining, wf);
+      amountWireFeeLimitRemaining = Amounts.sub(
+        amountWireFeeLimitRemaining,
+        wfForgiven,
+      ).amount;
+      // The remaining, amortized amount needs to be paid by the
+      // wallet or covered by the deposit fee allowance.
+      let wfRemaining = Amounts.divide(
+        Amounts.sub(wf, wfForgiven).amount,
+        wireFeeAmortization,
+      );
+
+      // This is the amount forgiven via the deposit fee allowance.
+      const wfDepositForgiven = Amounts.min(
+        amountDepositFeeLimitRemaining,
+        wfRemaining,
+      );
+      amountDepositFeeLimitRemaining = Amounts.sub(
+        amountDepositFeeLimitRemaining,
+        wfDepositForgiven,
+      ).amount;
+
+      wfRemaining = Amounts.sub(wfRemaining, wfDepositForgiven).amount;
+      customerWireFees = Amounts.add(customerWireFees, wfRemaining).amount;
+      amountPayRemaining = Amounts.add(amountPayRemaining, wfRemaining).amount;
+      wireFeeCoveredForExchange.add(exchangeBaseUrl);
+    }
+
+    const dfForgiven = Amounts.min(feeDeposit, amountDepositFeeLimitRemaining);
+
+    amountDepositFeeLimitRemaining = Amounts.sub(
+      amountDepositFeeLimitRemaining,
+      dfForgiven,
+    ).amount;
+
+    // How much does the user spend on deposit fees for this coin?
+    const dfRemaining = Amounts.sub(feeDeposit, dfForgiven).amount;
+    customerDepositFees = Amounts.add(customerDepositFees, dfRemaining).amount;
+    amountPayRemaining = Amounts.add(amountPayRemaining, dfRemaining).amount;
+  }
+
+  const prevPayCoins = req.prevPayCoins ?? [];
+
+  // Look at existing pay coin selection and tally up
+  for (const prev of prevPayCoins) {
+    tallyFees(prev.exchangeBaseUrl, prev.feeDeposit);
+    amountPayRemaining = Amounts.sub(amountPayRemaining, prev.contribution)
+      .amount;
+
+    coinPubs.push(prev.coinPub);
+    coinContributions.push(prev.contribution);
+  }
+
+  const prevCoinPubs = new Set(prevPayCoins.map((x) => x.coinPub));
+
+  // Sort by available amount (descending),  deposit fee (ascending) and
+  // denomPub (ascending) if deposit fee is the same
+  // (to guarantee deterministic results)
+  const candidateCoins = [...candidates.candidateCoins].sort(
+    (o1, o2) =>
+      -Amounts.cmp(o1.availableAmount, o2.availableAmount) ||
+      Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
+      strcmp(o1.denomPub, o2.denomPub),
+  );
+
+  // FIXME:  Here, we should select coins in a smarter way.
+  // Instead of always spending the next-largest coin,
+  // we should try to find the smallest coin that covers the
+  // amount.
+
+  for (const aci of candidateCoins) {
+    // Don't use this coin if depositing it is more expensive than
+    // the amount it would give the merchant.
+    if (Amounts.cmp(aci.feeDeposit, aci.availableAmount) >= 0) {
+      continue;
+    }
+    if (Amounts.isZero(amountPayRemaining)) {
+      // We have spent enough!
+      break;
+    }
+
+    // The same coin can't contribute twice to the same payment,
+    // by a fundamental, intentional limitation of the protocol.
+    if (prevCoinPubs.has(aci.coinPub)) {
+      continue;
+    }
+
+    tallyFees(aci.exchangeBaseUrl, aci.feeDeposit);
+
+    const coinSpend = Amounts.min(amountPayRemaining, aci.availableAmount);
+    amountPayRemaining = Amounts.sub(amountPayRemaining, coinSpend).amount;
+    coinPubs.push(aci.coinPub);
+    coinContributions.push(coinSpend);
+  }
+
+  if (Amounts.isZero(amountPayRemaining)) {
+    return {
+      paymentAmount: contractTermsAmount,
+      coinContributions,
+      coinPubs,
+      customerDepositFees,
+      customerWireFees,
+    };
+  }
+  return undefined;
+}