From 44b1896b9ec8af72aa0eb25e8c89a4cc0c841766 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Mon, 15 Mar 2021 13:43:53 +0100 Subject: improved pay coin selection support for multiple exchanges and healing a previous selection --- packages/taler-wallet-core/src/util/amounts.ts | 21 ++ .../src/util/coinSelection-test.ts | 186 +++++++++++++++ .../taler-wallet-core/src/util/coinSelection.ts | 263 +++++++++++++++++++++ 3 files changed, 470 insertions(+) create mode 100644 packages/taler-wallet-core/src/util/coinSelection-test.ts create mode 100644 packages/taler-wallet-core/src/util/coinSelection.ts (limited to 'packages/taler-wallet-core/src/util') 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 + */ + +/** + * 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 + */ + +/** + * 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; +} + +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 = 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; +} -- cgit v1.2.3