move helpers to util

1 files changed, 1233 insertions, 0 deletions

diff --git a/packages/taler-wallet-core/src/coinSelection.ts b/packages/taler-wallet-core/src/coinSelection.ts
new file mode 100644
index 000000000..f0b435b54
--- /dev/null
+++ b/packages/taler-wallet-core/src/coinSelection.ts
@@ -0,0 +1,1233 @@
+/*
+ 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 { GlobalIDB } from "@gnu-taler/idb-bridge";
+import {
+  AbsoluteTime,
+  AccountRestriction,
+  AgeCommitmentProof,
+  AgeRestriction,
+  AllowedAuditorInfo,
+  AllowedExchangeInfo,
+  AmountJson,
+  AmountLike,
+  Amounts,
+  AmountString,
+  checkDbInvariant,
+  checkLogicInvariant,
+  CoinPublicKeyString,
+  CoinStatus,
+  DenominationInfo,
+  DenominationPubKey,
+  DenomSelectionState,
+  Duration,
+  ForcedCoinSel,
+  ForcedDenomSel,
+  InternationalizedString,
+  j2s,
+  Logger,
+  parsePaytoUri,
+  PayCoinSelection,
+  PayMerchantInsufficientBalanceDetails,
+  PayPeerInsufficientBalanceDetails,
+  strcmp,
+  TalerProtocolTimestamp,
+  UnblindedSignature,
+} from "@gnu-taler/taler-util";
+import {
+  getMerchantPaymentBalanceDetails,
+  getPeerPaymentBalanceDetailsInTx,
+} from "./balance.js";
+import { getAutoRefreshExecuteThreshold } from "./common.js";
+import { DenominationRecord, WalletDbReadOnlyTransaction } from "./db.js";
+import { isWithdrawableDenom } from "./denominations.js";
+import { getExchangeWireDetailsInTx } from "./exchanges.js";
+import { InternalWalletState } from "./wallet.js";
+
+const logger = new Logger("coinSelection.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.
+   *
+   * FIXME: We should only need the denomPubHash here, if at all.
+   */
+  denomPub: DenominationPubKey;
+
+  /**
+   * Full value of the coin.
+   */
+  value: AmountJson;
+
+  /**
+   * 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;
+
+  maxAge: number;
+  ageCommitmentProof?: AgeCommitmentProof;
+}
+
+export 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;
+  requiredMinimumAge?: number;
+}
+
+export interface CoinSelectionTally {
+  /**
+   * Amount that still needs to be paid.
+   * May increase during the computation when fees need to be covered.
+   */
+  amountPayRemaining: AmountJson;
+
+  /**
+   * Allowance given by the merchant towards wire fees
+   */
+  amountWireFeeLimitRemaining: AmountJson;
+
+  /**
+   * Allowance given by the merchant towards deposit fees
+   * (and wire fees after wire fee limit is exhausted)
+   */
+  amountDepositFeeLimitRemaining: AmountJson;
+
+  customerDepositFees: AmountJson;
+
+  customerWireFees: AmountJson;
+
+  wireFeeCoveredForExchange: Set<string>;
+
+  lastDepositFee: AmountJson;
+}
+
+/**
+ * Account for the fees of spending a coin.
+ */
+function tallyFees(
+  tally: Readonly<CoinSelectionTally>,
+  wireFeesPerExchange: Record<string, AmountJson>,
+  wireFeeAmortization: number,
+  exchangeBaseUrl: string,
+  feeDeposit: AmountJson,
+): CoinSelectionTally {
+  const currency = tally.amountPayRemaining.currency;
+  let amountWireFeeLimitRemaining = tally.amountWireFeeLimitRemaining;
+  let amountDepositFeeLimitRemaining = tally.amountDepositFeeLimitRemaining;
+  let customerDepositFees = tally.customerDepositFees;
+  let customerWireFees = tally.customerWireFees;
+  let amountPayRemaining = tally.amountPayRemaining;
+  const wireFeeCoveredForExchange = new Set(tally.wireFeeCoveredForExchange);
+
+  if (!tally.wireFeeCoveredForExchange.has(exchangeBaseUrl)) {
+    const wf =
+      wireFeesPerExchange[exchangeBaseUrl] ?? Amounts.zeroOfCurrency(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;
+
+  return {
+    amountDepositFeeLimitRemaining,
+    amountPayRemaining,
+    amountWireFeeLimitRemaining,
+    customerDepositFees,
+    customerWireFees,
+    wireFeeCoveredForExchange,
+    lastDepositFee: feeDeposit,
+  };
+}
+
+export type SelectPayCoinsResult =
+  | {
+      type: "failure";
+      insufficientBalanceDetails: PayMerchantInsufficientBalanceDetails;
+    }
+  | { type: "success"; coinSel: PayCoinSelection };
+
+/**
+ * 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 async function selectPayCoinsNew(
+  ws: InternalWalletState,
+  req: SelectPayCoinRequestNg,
+): Promise<SelectPayCoinsResult> {
+  const {
+    contractTermsAmount,
+    depositFeeLimit,
+    wireFeeLimit,
+    wireFeeAmortization,
+  } = req;
+
+  // FIXME: Why don't we do this in a transaction?
+  const [candidateDenoms, wireFeesPerExchange] =
+    await selectPayMerchantCandidates(ws, req);
+
+  const coinPubs: string[] = [];
+  const coinContributions: AmountJson[] = [];
+  const currency = contractTermsAmount.currency;
+
+  let tally: CoinSelectionTally = {
+    amountPayRemaining: contractTermsAmount,
+    amountWireFeeLimitRemaining: wireFeeLimit,
+    amountDepositFeeLimitRemaining: depositFeeLimit,
+    customerDepositFees: Amounts.zeroOfCurrency(currency),
+    customerWireFees: Amounts.zeroOfCurrency(currency),
+    wireFeeCoveredForExchange: new Set(),
+    lastDepositFee: Amounts.zeroOfCurrency(currency),
+  };
+
+  const prevPayCoins = req.prevPayCoins ?? [];
+
+  // Look at existing pay coin selection and tally up
+  for (const prev of prevPayCoins) {
+    tally = tallyFees(
+      tally,
+      wireFeesPerExchange,
+      wireFeeAmortization,
+      prev.exchangeBaseUrl,
+      prev.feeDeposit,
+    );
+    tally.amountPayRemaining = Amounts.sub(
+      tally.amountPayRemaining,
+      prev.contribution,
+    ).amount;
+
+    coinPubs.push(prev.coinPub);
+    coinContributions.push(prev.contribution);
+  }
+
+  let selectedDenom: SelResult | undefined;
+  if (req.forcedSelection) {
+    selectedDenom = selectForced(req, candidateDenoms);
+  } else {
+    // 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.
+    selectedDenom = selectGreedy(
+      req,
+      candidateDenoms,
+      wireFeesPerExchange,
+      tally,
+    );
+  }
+
+  if (!selectedDenom) {
+    const details = await getMerchantPaymentBalanceDetails(ws, {
+      acceptedAuditors: req.auditors,
+      acceptedExchanges: req.exchanges,
+      acceptedWireMethods: [req.wireMethod],
+      currency: Amounts.currencyOf(req.contractTermsAmount),
+      minAge: req.requiredMinimumAge ?? 0,
+    });
+    let feeGapEstimate: AmountJson;
+    if (
+      Amounts.cmp(
+        details.balanceMerchantDepositable,
+        req.contractTermsAmount,
+      ) >= 0
+    ) {
+      // FIXME: We can probably give a better estimate.
+      feeGapEstimate = Amounts.add(
+        tally.amountPayRemaining,
+        tally.lastDepositFee,
+      ).amount;
+    } else {
+      feeGapEstimate = Amounts.zeroOfAmount(req.contractTermsAmount);
+    }
+    return {
+      type: "failure",
+      insufficientBalanceDetails: {
+        amountRequested: Amounts.stringify(req.contractTermsAmount),
+        balanceAgeAcceptable: Amounts.stringify(details.balanceAgeAcceptable),
+        balanceAvailable: Amounts.stringify(details.balanceAvailable),
+        balanceMaterial: Amounts.stringify(details.balanceMaterial),
+        balanceMerchantAcceptable: Amounts.stringify(
+          details.balanceMerchantAcceptable,
+        ),
+        balanceMerchantDepositable: Amounts.stringify(
+          details.balanceMerchantDepositable,
+        ),
+        feeGapEstimate: Amounts.stringify(feeGapEstimate),
+      },
+    };
+  }
+
+  const finalSel = selectedDenom;
+
+  logger.trace(`coin selection request ${j2s(req)}`);
+  logger.trace(`selected coins (via denoms) for payment: ${j2s(finalSel)}`);
+
+  await ws.db.runReadOnlyTx(["coins", "denominations"], async (tx) => {
+    for (const dph of Object.keys(finalSel)) {
+      const selInfo = finalSel[dph];
+      const numRequested = selInfo.contributions.length;
+      const query = [
+        selInfo.exchangeBaseUrl,
+        selInfo.denomPubHash,
+        selInfo.maxAge,
+        CoinStatus.Fresh,
+      ];
+      logger.trace(`query: ${j2s(query)}`);
+      const coins =
+        await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll(
+          query,
+          numRequested,
+        );
+      if (coins.length != numRequested) {
+        throw Error(
+          `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`,
+        );
+      }
+      coinPubs.push(...coins.map((x) => x.coinPub));
+      coinContributions.push(...selInfo.contributions);
+    }
+  });
+
+  return {
+    type: "success",
+    coinSel: {
+      paymentAmount: Amounts.stringify(contractTermsAmount),
+      coinContributions: coinContributions.map((x) => Amounts.stringify(x)),
+      coinPubs,
+      customerDepositFees: Amounts.stringify(tally.customerDepositFees),
+      customerWireFees: Amounts.stringify(tally.customerWireFees),
+    },
+  };
+}
+
+function makeAvailabilityKey(
+  exchangeBaseUrl: string,
+  denomPubHash: string,
+  maxAge: number,
+): string {
+  return `${denomPubHash};${maxAge};${exchangeBaseUrl}`;
+}
+
+/**
+ * Selection result.
+ */
+interface SelResult {
+  /**
+   * Map from an availability key
+   * to an array of contributions.
+   */
+  [avKey: string]: {
+    exchangeBaseUrl: string;
+    denomPubHash: string;
+    expireWithdraw: TalerProtocolTimestamp;
+    expireDeposit: TalerProtocolTimestamp;
+    maxAge: number;
+    contributions: AmountJson[];
+  };
+}
+
+export function testing_selectGreedy(
+  ...args: Parameters<typeof selectGreedy>
+): ReturnType<typeof selectGreedy> {
+  return selectGreedy(...args);
+}
+
+function selectGreedy(
+  req: SelectPayCoinRequestNg,
+  candidateDenoms: AvailableDenom[],
+  wireFeesPerExchange: Record<string, AmountJson>,
+  tally: CoinSelectionTally,
+): SelResult | undefined {
+  const { wireFeeAmortization } = req;
+  const selectedDenom: SelResult = {};
+  for (const denom of candidateDenoms) {
+    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++
+    ) {
+      tally = tallyFees(
+        tally,
+        wireFeesPerExchange,
+        wireFeeAmortization,
+        denom.exchangeBaseUrl,
+        Amounts.parseOrThrow(denom.feeDeposit),
+      );
+
+      const coinSpend = Amounts.max(
+        Amounts.min(tally.amountPayRemaining, denom.value),
+        denom.feeDeposit,
+      );
+
+      tally.amountPayRemaining = Amounts.sub(
+        tally.amountPayRemaining,
+        coinSpend,
+      ).amount;
+
+      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,
+          expireDeposit: denom.stampExpireDeposit,
+          expireWithdraw: denom.stampExpireWithdraw,
+        };
+      }
+      sd.contributions.push(...contributions);
+      selectedDenom[avKey] = sd;
+    }
+  }
+  return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined;
+}
+
+function selectForced(
+  req: SelectPayCoinRequestNg,
+  candidateDenoms: AvailableDenom[],
+): SelResult | undefined {
+  const selectedDenom: SelResult = {};
+
+  const forcedSelection = req.forcedSelection;
+  checkLogicInvariant(!!forcedSelection);
+
+  for (const forcedCoin of forcedSelection.coins) {
+    let found = false;
+    for (const aci of candidateDenoms) {
+      if (aci.numAvailable <= 0) {
+        continue;
+      }
+      if (Amounts.cmp(aci.value, forcedCoin.value) === 0) {
+        aci.numAvailable--;
+        const avKey = makeAvailabilityKey(
+          aci.exchangeBaseUrl,
+          aci.denomPubHash,
+          aci.maxAge,
+        );
+        let sd = selectedDenom[avKey];
+        if (!sd) {
+          sd = {
+            contributions: [],
+            denomPubHash: aci.denomPubHash,
+            exchangeBaseUrl: aci.exchangeBaseUrl,
+            maxAge: aci.maxAge,
+            expireDeposit: aci.stampExpireDeposit,
+            expireWithdraw: aci.stampExpireWithdraw,
+          };
+        }
+        sd.contributions.push(Amounts.parseOrThrow(forcedCoin.value));
+        selectedDenom[avKey] = sd;
+        found = true;
+        break;
+      }
+    }
+    if (!found) {
+      throw Error("can't find coin for forced coin selection");
+    }
+  }
+
+  return selectedDenom;
+}
+
+export function checkAccountRestriction(
+  paytoUri: string,
+  restrictions: AccountRestriction[],
+): { ok: boolean; hint?: string; hintI18n?: InternationalizedString } {
+  for (const myRestriction of restrictions) {
+    switch (myRestriction.type) {
+      case "deny":
+        return { ok: false };
+      case "regex":
+        const regex = new RegExp(myRestriction.payto_regex);
+        if (!regex.test(paytoUri)) {
+          return {
+            ok: false,
+            hint: myRestriction.human_hint,
+            hintI18n: myRestriction.human_hint_i18n,
+          };
+        }
+    }
+  }
+  return {
+    ok: true,
+  };
+}
+
+export interface SelectPayCoinRequestNg {
+  exchanges: AllowedExchangeInfo[];
+  auditors: AllowedAuditorInfo[];
+  wireMethod: string;
+  contractTermsAmount: AmountJson;
+  depositFeeLimit: AmountJson;
+  wireFeeLimit: AmountJson;
+  wireFeeAmortization: number;
+  prevPayCoins?: PreviousPayCoins;
+  requiredMinimumAge?: number;
+  forcedSelection?: ForcedCoinSel;
+
+  /**
+   * Deposit payto URI, in case we already know the account that
+   * will be deposited into.
+   *
+   * That is typically the case when the wallet does a deposit to
+   * return funds to the user's own bank account.
+   */
+  depositPaytoUri?: string;
+}
+
+export type AvailableDenom = DenominationInfo & {
+  maxAge: number;
+  numAvailable: number;
+};
+
+async function selectPayMerchantCandidates(
+  ws: InternalWalletState,
+  req: SelectPayCoinRequestNg,
+): Promise<[AvailableDenom[], Record<string, AmountJson>]> {
+  return await ws.db.runReadOnlyTx(
+    ["exchanges", "exchangeDetails", "denominations", "coinAvailability"],
+    async (tx) => {
+      // FIXME: Use the existing helper (from balance.ts) to
+      // get acceptable exchanges.
+      const denoms: AvailableDenom[] = [];
+      const exchanges = await tx.exchanges.iter().toArray();
+      const wfPerExchange: Record<string, AmountJson> = {};
+      loopExchange: for (const exchange of exchanges) {
+        const exchangeDetails = await getExchangeWireDetailsInTx(
+          tx,
+          exchange.baseUrl,
+        );
+        // 1.- exchange has same currency
+        if (exchangeDetails?.currency !== req.contractTermsAmount.currency) {
+          continue;
+        }
+        let wireMethodFee: string | undefined;
+        // 2.- exchange supports wire method
+        loopWireAccount: for (const acc of exchangeDetails.wireInfo.accounts) {
+          const pp = parsePaytoUri(acc.payto_uri);
+          checkLogicInvariant(!!pp);
+          if (pp.targetType !== req.wireMethod) {
+            continue;
+          }
+          const wireFeeStr = exchangeDetails.wireInfo.feesForType[
+            req.wireMethod
+          ]?.find((x) => {
+            return AbsoluteTime.isBetween(
+              AbsoluteTime.now(),
+              AbsoluteTime.fromProtocolTimestamp(x.startStamp),
+              AbsoluteTime.fromProtocolTimestamp(x.endStamp),
+            );
+          })?.wireFee;
+          let debitAccountCheckOk = false;
+          if (req.depositPaytoUri) {
+            // FIXME: We should somehow propagate the hint here!
+            const checkResult = checkAccountRestriction(
+              req.depositPaytoUri,
+              acc.debit_restrictions,
+            );
+            if (checkResult.ok) {
+              debitAccountCheckOk = true;
+            }
+          } else {
+            debitAccountCheckOk = true;
+          }
+
+          if (wireFeeStr) {
+            wireMethodFee = wireFeeStr;
+            break loopWireAccount;
+          }
+        }
+        if (!wireMethodFee) {
+          continue;
+        }
+        wfPerExchange[exchange.baseUrl] = Amounts.parseOrThrow(wireMethodFee);
+
+        // 3.- exchange is trusted in the exchange list or auditor list
+        let accepted = false;
+        for (const allowedExchange of req.exchanges) {
+          if (allowedExchange.exchangePub === exchangeDetails.masterPublicKey) {
+            accepted = true;
+            break;
+          }
+        }
+        for (const allowedAuditor of req.auditors) {
+          for (const providedAuditor of exchangeDetails.auditors) {
+            if (allowedAuditor.auditorPub === providedAuditor.auditor_pub) {
+              accepted = true;
+              break;
+            }
+          }
+        }
+        if (!accepted) {
+          continue;
+        }
+        // 4.- filter coins restricted by age
+        let ageLower = 0;
+        let ageUpper = AgeRestriction.AGE_UNRESTRICTED;
+        if (req.requiredMinimumAge) {
+          ageLower = req.requiredMinimumAge;
+        }
+        const myExchangeCoins =
+          await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll(
+            GlobalIDB.KeyRange.bound(
+              [exchangeDetails.exchangeBaseUrl, ageLower, 1],
+              [
+                exchangeDetails.exchangeBaseUrl,
+                ageUpper,
+                Number.MAX_SAFE_INTEGER,
+              ],
+            ),
+          );
+        // 5.- save denoms with how many coins are available
+        // FIXME: Check that the individual denomination is audited!
+        // FIXME: Should we exclude denominations that are
+        // not spendable anymore?
+        for (const coinAvail of myExchangeCoins) {
+          const denom = await tx.denominations.get([
+            coinAvail.exchangeBaseUrl,
+            coinAvail.denomPubHash,
+          ]);
+          checkDbInvariant(!!denom);
+          if (denom.isRevoked || !denom.isOffered) {
+            continue;
+          }
+          denoms.push({
+            ...DenominationRecord.toDenomInfo(denom),
+            numAvailable: coinAvail.freshCoinCount ?? 0,
+            maxAge: coinAvail.maxAge,
+          });
+        }
+      }
+      logger.info(`available denoms ${j2s(denoms)}`);
+      // Sort by available amount (descending),  deposit fee (ascending) and
+      // denomPub (ascending) if deposit fee is the same
+      // (to guarantee deterministic results)
+      denoms.sort(
+        (o1, o2) =>
+          -Amounts.cmp(o1.value, o2.value) ||
+          Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
+          strcmp(o1.denomPubHash, o2.denomPubHash),
+      );
+      return [denoms, wfPerExchange];
+    },
+  );
+}
+
+/**
+ * Get a list of denominations (with repetitions possible)
+ * whose total value is as close as possible to the available
+ * amount, but never larger.
+ */
+export function selectWithdrawalDenominations(
+  amountAvailable: AmountJson,
+  denoms: DenominationRecord[],
+  denomselAllowLate: boolean = false,
+): DenomSelectionState {
+  let remaining = Amounts.copy(amountAvailable);
+
+  const selectedDenoms: {
+    count: number;
+    denomPubHash: string;
+  }[] = [];
+
+  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
+  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);
+
+  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
+  denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value));
+
+  for (const d of denoms) {
+    const cost = Amounts.add(d.value, d.fees.feeWithdraw).amount;
+    const res = Amounts.divmod(remaining, cost);
+    const count = res.quotient;
+    remaining = Amounts.sub(remaining, Amounts.mult(cost, count).amount).amount;
+    if (count > 0) {
+      totalCoinValue = Amounts.add(
+        totalCoinValue,
+        Amounts.mult(d.value, count).amount,
+      ).amount;
+      totalWithdrawCost = Amounts.add(
+        totalWithdrawCost,
+        Amounts.mult(cost, count).amount,
+      ).amount;
+      selectedDenoms.push({
+        count,
+        denomPubHash: d.denomPubHash,
+      });
+    }
+
+    if (Amounts.isZero(remaining)) {
+      break;
+    }
+  }
+
+  if (logger.shouldLogTrace()) {
+    logger.trace(
+      `selected withdrawal denoms for ${Amounts.stringify(totalCoinValue)}`,
+    );
+    for (const sd of selectedDenoms) {
+      logger.trace(`denom_pub_hash=${sd.denomPubHash}, count=${sd.count}`);
+    }
+    logger.trace("(end of withdrawal denom list)");
+  }
+
+  return {
+    selectedDenoms,
+    totalCoinValue: Amounts.stringify(totalCoinValue),
+    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
+  };
+}
+
+export function selectForcedWithdrawalDenominations(
+  amountAvailable: AmountJson,
+  denoms: DenominationRecord[],
+  forcedDenomSel: ForcedDenomSel,
+  denomselAllowLate: boolean,
+): DenomSelectionState {
+  const selectedDenoms: {
+    count: number;
+    denomPubHash: string;
+  }[] = [];
+
+  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
+  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);
+
+  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
+  denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value));
+
+  for (const fds of forcedDenomSel.denoms) {
+    const count = fds.count;
+    const denom = denoms.find((x) => {
+      return Amounts.cmp(x.value, fds.value) == 0;
+    });
+    if (!denom) {
+      throw Error(
+        `unable to find denom for forced selection (value ${fds.value})`,
+      );
+    }
+    const cost = Amounts.add(denom.value, denom.fees.feeWithdraw).amount;
+    totalCoinValue = Amounts.add(
+      totalCoinValue,
+      Amounts.mult(denom.value, count).amount,
+    ).amount;
+    totalWithdrawCost = Amounts.add(
+      totalWithdrawCost,
+      Amounts.mult(cost, count).amount,
+    ).amount;
+    selectedDenoms.push({
+      count,
+      denomPubHash: denom.denomPubHash,
+    });
+  }
+
+  return {
+    selectedDenoms,
+    totalCoinValue: Amounts.stringify(totalCoinValue),
+    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
+  };
+}
+
+export interface CoinInfo {
+  id: string;
+  value: AmountJson;
+  denomDeposit: AmountJson;
+  denomWithdraw: AmountJson;
+  denomRefresh: AmountJson;
+  totalAvailable: number | undefined;
+  exchangeWire: AmountJson | undefined;
+  exchangePurse: AmountJson | undefined;
+  duration: Duration;
+  exchangeBaseUrl: string;
+  maxAge: number;
+}
+
+export interface SelectedPeerCoin {
+  coinPub: string;
+  coinPriv: string;
+  contribution: AmountString;
+  denomPubHash: string;
+  denomSig: UnblindedSignature;
+  ageCommitmentProof: AgeCommitmentProof | undefined;
+}
+
+export interface PeerCoinSelectionDetails {
+  exchangeBaseUrl: string;
+
+  /**
+   * Info of Coins that were selected.
+   */
+  coins: SelectedPeerCoin[];
+
+  /**
+   * How much of the deposit fees is the customer paying?
+   */
+  depositFees: AmountJson;
+
+  maxExpirationDate: TalerProtocolTimestamp;
+}
+
+export type SelectPeerCoinsResult =
+  | { type: "success"; result: PeerCoinSelectionDetails }
+  | {
+      type: "failure";
+      insufficientBalanceDetails: PayPeerInsufficientBalanceDetails;
+    };
+
+export interface PeerCoinRepair {
+  exchangeBaseUrl: string;
+  coinPubs: CoinPublicKeyString[];
+  contribs: AmountJson[];
+}
+
+export interface PeerCoinSelectionRequest {
+  instructedAmount: AmountJson;
+
+  /**
+   * Instruct the coin selection to repair this coin
+   * selection instead of selecting completely new coins.
+   */
+  repair?: PeerCoinRepair;
+}
+
+/**
+ * Get coin availability information for a certain exchange.
+ */
+async function selectPayPeerCandidatesForExchange(
+  ws: InternalWalletState,
+  tx: WalletDbReadOnlyTransaction<["coinAvailability", "denominations"]>,
+  exchangeBaseUrl: string,
+): Promise<AvailableDenom[]> {
+  const denoms: AvailableDenom[] = [];
+
+  let ageLower = 0;
+  let ageUpper = AgeRestriction.AGE_UNRESTRICTED;
+  const myExchangeCoins =
+    await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll(
+      GlobalIDB.KeyRange.bound(
+        [exchangeBaseUrl, ageLower, 1],
+        [exchangeBaseUrl, ageUpper, Number.MAX_SAFE_INTEGER],
+      ),
+    );
+
+  for (const coinAvail of myExchangeCoins) {
+    const denom = await tx.denominations.get([
+      coinAvail.exchangeBaseUrl,
+      coinAvail.denomPubHash,
+    ]);
+    checkDbInvariant(!!denom);
+    if (denom.isRevoked || !denom.isOffered) {
+      continue;
+    }
+    denoms.push({
+      ...DenominationRecord.toDenomInfo(denom),
+      numAvailable: coinAvail.freshCoinCount ?? 0,
+      maxAge: coinAvail.maxAge,
+    });
+  }
+  // Sort by available amount (descending),  deposit fee (ascending) and
+  // denomPub (ascending) if deposit fee is the same
+  // (to guarantee deterministic results)
+  denoms.sort(
+    (o1, o2) =>
+      -Amounts.cmp(o1.value, o2.value) ||
+      Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
+      strcmp(o1.denomPubHash, o2.denomPubHash),
+  );
+
+  return denoms;
+}
+
+interface PeerCoinSelectionTally {
+  amountAcc: AmountJson;
+  depositFeesAcc: AmountJson;
+  lastDepositFee: AmountJson;
+}
+
+/**
+ * exporting for testing
+ */
+export function testing_greedySelectPeer(
+  ...args: Parameters<typeof greedySelectPeer>
+): ReturnType<typeof greedySelectPeer> {
+  return greedySelectPeer(...args);
+}
+
+function greedySelectPeer(
+  candidates: AvailableDenom[],
+  instructedAmount: AmountLike,
+  tally: PeerCoinSelectionTally,
+): SelResult | undefined {
+  const selectedDenom: SelResult = {};
+  for (const denom of candidates) {
+    const contributions: AmountJson[] = [];
+    for (
+      let i = 0;
+      i < denom.numAvailable &&
+      Amounts.cmp(tally.amountAcc, instructedAmount) < 0;
+      i++
+    ) {
+      const amountPayRemaining = Amounts.sub(
+        instructedAmount,
+        tally.amountAcc,
+      ).amount;
+      // Maximum amount the coin could effectively contribute.
+      const maxCoinContrib = Amounts.sub(denom.value, denom.feeDeposit).amount;
+
+      const coinSpend = Amounts.min(
+        Amounts.add(amountPayRemaining, denom.feeDeposit).amount,
+        maxCoinContrib,
+      );
+
+      tally.amountAcc = Amounts.add(tally.amountAcc, coinSpend).amount;
+      tally.amountAcc = Amounts.sub(tally.amountAcc, denom.feeDeposit).amount;
+
+      tally.depositFeesAcc = Amounts.add(
+        tally.depositFeesAcc,
+        denom.feeDeposit,
+      ).amount;
+
+      tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit);
+
+      contributions.push(coinSpend);
+    }
+    if (contributions.length > 0) {
+      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,
+          expireDeposit: denom.stampExpireDeposit,
+          expireWithdraw: denom.stampExpireWithdraw,
+        };
+      }
+      sd.contributions.push(...contributions);
+      selectedDenom[avKey] = sd;
+    }
+    if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) {
+      break;
+    }
+  }
+
+  if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) {
+    return selectedDenom;
+  }
+  return undefined;
+}
+
+export async function selectPeerCoins(
+  ws: InternalWalletState,
+  req: PeerCoinSelectionRequest,
+): Promise<SelectPeerCoinsResult> {
+  const instructedAmount = req.instructedAmount;
+  if (Amounts.isZero(instructedAmount)) {
+    // Other parts of the code assume that we have at least
+    // one coin to spend.
+    throw new Error("amount of zero not allowed");
+  }
+  return await ws.db.runReadWriteTx(
+    [
+      "exchanges",
+      "contractTerms",
+      "coins",
+      "coinAvailability",
+      "denominations",
+      "refreshGroups",
+      "peerPushDebit",
+    ],
+    async (tx) => {
+      const exchanges = await tx.exchanges.iter().toArray();
+      const exchangeFeeGap: { [url: string]: AmountJson } = {};
+      const currency = Amounts.currencyOf(instructedAmount);
+      for (const exch of exchanges) {
+        if (exch.detailsPointer?.currency !== currency) {
+          continue;
+        }
+        const candidates = await selectPayPeerCandidatesForExchange(
+          ws,
+          tx,
+          exch.baseUrl,
+        );
+        const tally: PeerCoinSelectionTally = {
+          amountAcc: Amounts.zeroOfCurrency(currency),
+          depositFeesAcc: Amounts.zeroOfCurrency(currency),
+          lastDepositFee: Amounts.zeroOfCurrency(currency),
+        };
+        const resCoins: {
+          coinPub: string;
+          coinPriv: string;
+          contribution: AmountString;
+          denomPubHash: string;
+          denomSig: UnblindedSignature;
+          ageCommitmentProof: AgeCommitmentProof | undefined;
+        }[] = [];
+
+        if (req.repair && req.repair.exchangeBaseUrl === exch.baseUrl) {
+          for (let i = 0; i < req.repair.coinPubs.length; i++) {
+            const contrib = req.repair.contribs[i];
+            const coin = await tx.coins.get(req.repair.coinPubs[i]);
+            if (!coin) {
+              throw Error("repair not possible, coin not found");
+            }
+            const denom = await ws.getDenomInfo(
+              ws,
+              tx,
+              coin.exchangeBaseUrl,
+              coin.denomPubHash,
+            );
+            checkDbInvariant(!!denom);
+            resCoins.push({
+              coinPriv: coin.coinPriv,
+              coinPub: coin.coinPub,
+              contribution: Amounts.stringify(contrib),
+              denomPubHash: coin.denomPubHash,
+              denomSig: coin.denomSig,
+              ageCommitmentProof: coin.ageCommitmentProof,
+            });
+            const depositFee = Amounts.parseOrThrow(denom.feeDeposit);
+            tally.lastDepositFee = depositFee;
+            tally.amountAcc = Amounts.add(
+              tally.amountAcc,
+              Amounts.sub(contrib, depositFee).amount,
+            ).amount;
+            tally.depositFeesAcc = Amounts.add(
+              tally.depositFeesAcc,
+              depositFee,
+            ).amount;
+          }
+        }
+
+        const selectedDenom = greedySelectPeer(
+          candidates,
+          instructedAmount,
+          tally,
+        );
+
+        if (selectedDenom) {
+          let minAutorefreshExecuteThreshold = TalerProtocolTimestamp.never();
+          for (const dph of Object.keys(selectedDenom)) {
+            const selInfo = selectedDenom[dph];
+            // Compute earliest time that a selected denom
+            // would have its coins auto-refreshed.
+            minAutorefreshExecuteThreshold = TalerProtocolTimestamp.min(
+              minAutorefreshExecuteThreshold,
+              AbsoluteTime.toProtocolTimestamp(
+                getAutoRefreshExecuteThreshold({
+                  stampExpireDeposit: selInfo.expireDeposit,
+                  stampExpireWithdraw: selInfo.expireWithdraw,
+                }),
+              ),
+            );
+            const numRequested = selInfo.contributions.length;
+            const query = [
+              selInfo.exchangeBaseUrl,
+              selInfo.denomPubHash,
+              selInfo.maxAge,
+              CoinStatus.Fresh,
+            ];
+            logger.info(`query: ${j2s(query)}`);
+            const coins =
+              await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll(
+                query,
+                numRequested,
+              );
+            if (coins.length != numRequested) {
+              throw Error(
+                `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`,
+              );
+            }
+            for (let i = 0; i < selInfo.contributions.length; i++) {
+              resCoins.push({
+                coinPriv: coins[i].coinPriv,
+                coinPub: coins[i].coinPub,
+                contribution: Amounts.stringify(selInfo.contributions[i]),
+                ageCommitmentProof: coins[i].ageCommitmentProof,
+                denomPubHash: selInfo.denomPubHash,
+                denomSig: coins[i].denomSig,
+              });
+            }
+          }
+
+          const res: PeerCoinSelectionDetails = {
+            exchangeBaseUrl: exch.baseUrl,
+            coins: resCoins,
+            depositFees: tally.depositFeesAcc,
+            maxExpirationDate: minAutorefreshExecuteThreshold,
+          };
+          return { type: "success", result: res };
+        }
+
+        const diff = Amounts.sub(instructedAmount, tally.amountAcc).amount;
+        exchangeFeeGap[exch.baseUrl] = Amounts.add(
+          tally.lastDepositFee,
+          diff,
+        ).amount;
+
+        continue;
+      }
+
+      // We were unable to select coins.
+      // Now we need to produce error details.
+
+      const infoGeneral = await getPeerPaymentBalanceDetailsInTx(ws, tx, {
+        currency,
+      });
+
+      const perExchange: PayPeerInsufficientBalanceDetails["perExchange"] = {};
+
+      let maxFeeGapEstimate = Amounts.zeroOfCurrency(currency);
+
+      for (const exch of exchanges) {
+        if (exch.detailsPointer?.currency !== currency) {
+          continue;
+        }
+        const infoExchange = await getPeerPaymentBalanceDetailsInTx(ws, tx, {
+          currency,
+          restrictExchangeTo: exch.baseUrl,
+        });
+        let gap =
+          exchangeFeeGap[exch.baseUrl] ?? Amounts.zeroOfCurrency(currency);
+        if (Amounts.cmp(infoExchange.balanceMaterial, instructedAmount) < 0) {
+          // Show fee gap only if we should've been able to pay with the material amount
+          gap = Amounts.zeroOfCurrency(currency);
+        }
+        perExchange[exch.baseUrl] = {
+          balanceAvailable: Amounts.stringify(infoExchange.balanceAvailable),
+          balanceMaterial: Amounts.stringify(infoExchange.balanceMaterial),
+          feeGapEstimate: Amounts.stringify(gap),
+        };
+
+        maxFeeGapEstimate = Amounts.max(maxFeeGapEstimate, gap);
+      }
+
+      const errDetails: PayPeerInsufficientBalanceDetails = {
+        amountRequested: Amounts.stringify(instructedAmount),
+        balanceAvailable: Amounts.stringify(infoGeneral.balanceAvailable),
+        balanceMaterial: Amounts.stringify(infoGeneral.balanceMaterial),
+        feeGapEstimate: Amounts.stringify(maxFeeGapEstimate),
+        perExchange,
+      };
+
+      return { type: "failure", insufficientBalanceDetails: errDetails };
+    },
+  );
+}