[taler-wallet-core] branch master updated (a6b7fbaf -> 44b1896b)

[gnunet]

This is an automated email from the git hooks/post-receive script.

dold pushed a change to branch master
in repository wallet-core.

 discard a6b7fbaf improved pay coin selection
     new 44b1896b improved pay coin selection

This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version.  This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:

 * -- * -- B -- O -- O -- O   (a6b7fbaf)
            \
             N -- N -- N   refs/heads/master (44b1896b)

You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.

Any revisions marked "omit" are not gone; other references still
refer to them.  Any revisions marked "discard" are gone forever.

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 .../src/util/coinSelection-test.ts                 | 186 +++++++++++++++
 .../taler-wallet-core/src/util/coinSelection.ts    | 263 +++++++++++++++++++++
 2 files changed, 449 insertions(+)
 create mode 100644 packages/taler-wallet-core/src/util/coinSelection-test.ts
 create mode 100644 packages/taler-wallet-core/src/util/coinSelection.ts

diff --git a/packages/taler-wallet-core/src/util/coinSelection-test.ts 
b/packages/taler-wallet-core/src/util/coinSelection-test.ts
new file mode 100644
index 00000000..3ac718aa
--- /dev/null
+++ b/packages/taler-wallet-core/src/util/coinSelection-test.ts
@@ -0,0 +1,186 @@
+/*
+ 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/>
+ */
+
+/**
+ * Imports.
+ */
+import test from "ava";
+import { AmountJson, Amounts } from "..";
+import { AvailableCoinInfo, selectPayCoins } from "./coinSelection";
+
+function a(x: string): AmountJson {
+  const amt = Amounts.parse(x);
+  if (!amt) {
+    throw Error("invalid amount");
+  }
+  return amt;
+}
+
+function fakeAci(current: string, feeDeposit: string): AvailableCoinInfo {
+  return {
+    availableAmount: a(current),
+    coinPub: "foobar",
+    denomPub: "foobar",
+    feeDeposit: a(feeDeposit),
+    exchangeBaseUrl: "https://example.com/";,
+  };
+}
+
+test("coin selection 1", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.1"),
+    fakeAci("EUR:1.0", "EUR:0.0"),
+  ];
+
+  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;
+  }
+  t.true(res.coinPubs.length === 2);
+  t.pass();
+});
+
+test("coin selection 2", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.0"),
+    // Merchant covers the fee, this one shouldn't be used
+    fakeAci("EUR:1.0", "EUR:0.0"),
+  ];
+
+  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;
+  }
+  t.true(res.coinPubs.length === 2);
+  t.pass();
+});
+
+test("coin selection 3", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    // this coin should be selected instead of previous one with fee
+    fakeAci("EUR:1.0", "EUR:0.0"),
+  ];
+
+  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;
+  }
+  t.true(res.coinPubs.length === 2);
+  t.pass();
+});
+
+test("coin selection 4", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "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;
+  }
+  t.true(res.coinPubs.length === 3);
+  t.pass();
+});
+
+test("coin selection 5", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.5"),
+  ];
+
+  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();
+});
+
+test("coin selection 6", (t) => {
+  const acis: AvailableCoinInfo[] = [
+    fakeAci("EUR:1.0", "EUR:0.5"),
+    fakeAci("EUR:1.0", "EUR:0.5"),
+  ];
+  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 00000000..d32ab6f3
--- /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;
+}

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.