diff options
| -rw-r--r-- | packages/taler-wallet-core/src/operations/backup/import.ts | 2 | ||||
| -rw-r--r-- | packages/taler-wallet-core/src/operations/deposits.ts | 24 | ||||
| -rw-r--r-- | packages/taler-wallet-core/src/operations/pay.ts | 242 | ||||
| -rw-r--r-- | packages/taler-wallet-core/src/types/dbTypes.ts | 41 | ||||
| -rw-r--r-- | packages/taler-wallet-core/src/util/amounts.ts | 21 | ||||
| -rw-r--r-- | packages/taler-wallet-core/src/util/coinSelection-test.ts (renamed from packages/taler-wallet-core/src/wallet-test.ts) | 95 | ||||
| -rw-r--r-- | packages/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 416b068e4..2e33c2070 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 50921a170..53f2529b2 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 3add9bbbf..cdacb2eba 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 6c37971ad..689055df8 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 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/wallet-test.ts b/packages/taler-wallet-core/src/util/coinSelection-test.ts index 4b06accf2..3ac718aaf 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 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; +} |