[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[taler-wallet-core] 01/01: improved pay coin selection
|
From: |
gnunet |
|
Subject: |
[taler-wallet-core] 01/01: improved pay coin selection |
|
Date: |
Mon, 15 Mar 2021 13:44:30 +0100 |
This is an automated email from the git hooks/post-receive script.
dold pushed a commit to branch master
in repository wallet-core.
commit 44b1896b9ec8af72aa0eb25e8c89a4cc0c841766
Author: Florian Dold <florian@dold.me>
AuthorDate: Mon Mar 15 13:43:53 2021 +0100
improved pay coin selection
support for multiple exchanges and healing a previous selection
---
.../src/operations/backup/import.ts | 2 +-
.../taler-wallet-core/src/operations/deposits.ts | 24 +-
packages/taler-wallet-core/src/operations/pay.ts | 242 +++++++------------
packages/taler-wallet-core/src/types/dbTypes.ts | 41 +---
packages/taler-wallet-core/src/util/amounts.ts | 21 ++
.../{wallet-test.ts => util/coinSelection-test.ts} | 95 ++++++--
.../taler-wallet-core/src/util/coinSelection.ts | 263 +++++++++++++++++++++
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 416b068e..2e33c207 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 50921a17..53f2529b 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 3add9bbb..cdacb2eb 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 6c37971a..689055df 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 801c3385..7a242f41 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
similarity index 54%
rename from packages/taler-wallet-core/src/wallet-test.ts
rename to packages/taler-wallet-core/src/util/coinSelection-test.ts
index 4b06accf..3ac718aa 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 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.