summaryrefslogtreecommitdiff
path: root/packages/taler-wallet-core/src/util
diff options
context:
space:
mode:
authorFlorian Dold <florian@dold.me>2021-03-15 13:43:53 +0100
committerFlorian Dold <florian@dold.me>2021-03-15 13:44:25 +0100
commit44b1896b9ec8af72aa0eb25e8c89a4cc0c841766 (patch)
tree5a1b60cfd7334a64bb9cf6e465b3d62ee9dacde0 /packages/taler-wallet-core/src/util
parentfb3da3a28d6ed6a16ca7d0fa8ec775de51c7df6b (diff)
downloadwallet-core-44b1896b9ec8af72aa0eb25e8c89a4cc0c841766.tar.gz
wallet-core-44b1896b9ec8af72aa0eb25e8c89a4cc0c841766.tar.bz2
wallet-core-44b1896b9ec8af72aa0eb25e8c89a4cc0c841766.zip
improved pay coin selection
support for multiple exchanges and healing a previous selection
Diffstat (limited to 'packages/taler-wallet-core/src/util')
-rw-r--r--packages/taler-wallet-core/src/util/amounts.ts21
-rw-r--r--packages/taler-wallet-core/src/util/coinSelection-test.ts186
-rw-r--r--packages/taler-wallet-core/src/util/coinSelection.ts263
3 files changed, 470 insertions, 0 deletions
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/util/coinSelection-test.ts b/packages/taler-wallet-core/src/util/coinSelection-test.ts
new file mode 100644
index 000000000..3ac718aaf
--- /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 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;
+}