From 612b85c18fc17af412d08e075e1fddaa67aa7bf0 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Wed, 21 Feb 2024 13:01:23 +0100 Subject: move helpers to util --- packages/taler-wallet-core/src/coinSelection.ts | 1233 +++++++++++++++++++++++ 1 file changed, 1233 insertions(+) create mode 100644 packages/taler-wallet-core/src/coinSelection.ts (limited to 'packages/taler-wallet-core/src/coinSelection.ts') diff --git a/packages/taler-wallet-core/src/coinSelection.ts b/packages/taler-wallet-core/src/coinSelection.ts new file mode 100644 index 000000000..f0b435b54 --- /dev/null +++ b/packages/taler-wallet-core/src/coinSelection.ts @@ -0,0 +1,1233 @@ +/* + 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 { GlobalIDB } from "@gnu-taler/idb-bridge"; +import { + AbsoluteTime, + AccountRestriction, + AgeCommitmentProof, + AgeRestriction, + AllowedAuditorInfo, + AllowedExchangeInfo, + AmountJson, + AmountLike, + Amounts, + AmountString, + checkDbInvariant, + checkLogicInvariant, + CoinPublicKeyString, + CoinStatus, + DenominationInfo, + DenominationPubKey, + DenomSelectionState, + Duration, + ForcedCoinSel, + ForcedDenomSel, + InternationalizedString, + j2s, + Logger, + parsePaytoUri, + PayCoinSelection, + PayMerchantInsufficientBalanceDetails, + PayPeerInsufficientBalanceDetails, + strcmp, + TalerProtocolTimestamp, + UnblindedSignature, +} from "@gnu-taler/taler-util"; +import { + getMerchantPaymentBalanceDetails, + getPeerPaymentBalanceDetailsInTx, +} from "./balance.js"; +import { getAutoRefreshExecuteThreshold } from "./common.js"; +import { DenominationRecord, WalletDbReadOnlyTransaction } from "./db.js"; +import { isWithdrawableDenom } from "./denominations.js"; +import { getExchangeWireDetailsInTx } from "./exchanges.js"; +import { InternalWalletState } from "./wallet.js"; + +const logger = new Logger("coinSelection.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. + * + * FIXME: We should only need the denomPubHash here, if at all. + */ + denomPub: DenominationPubKey; + + /** + * Full value of the coin. + */ + value: AmountJson; + + /** + * 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; + + maxAge: number; + ageCommitmentProof?: AgeCommitmentProof; +} + +export 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; + requiredMinimumAge?: number; +} + +export interface CoinSelectionTally { + /** + * Amount that still needs to be paid. + * May increase during the computation when fees need to be covered. + */ + amountPayRemaining: AmountJson; + + /** + * Allowance given by the merchant towards wire fees + */ + amountWireFeeLimitRemaining: AmountJson; + + /** + * Allowance given by the merchant towards deposit fees + * (and wire fees after wire fee limit is exhausted) + */ + amountDepositFeeLimitRemaining: AmountJson; + + customerDepositFees: AmountJson; + + customerWireFees: AmountJson; + + wireFeeCoveredForExchange: Set; + + lastDepositFee: AmountJson; +} + +/** + * Account for the fees of spending a coin. + */ +function tallyFees( + tally: Readonly, + wireFeesPerExchange: Record, + wireFeeAmortization: number, + exchangeBaseUrl: string, + feeDeposit: AmountJson, +): CoinSelectionTally { + const currency = tally.amountPayRemaining.currency; + let amountWireFeeLimitRemaining = tally.amountWireFeeLimitRemaining; + let amountDepositFeeLimitRemaining = tally.amountDepositFeeLimitRemaining; + let customerDepositFees = tally.customerDepositFees; + let customerWireFees = tally.customerWireFees; + let amountPayRemaining = tally.amountPayRemaining; + const wireFeeCoveredForExchange = new Set(tally.wireFeeCoveredForExchange); + + if (!tally.wireFeeCoveredForExchange.has(exchangeBaseUrl)) { + const wf = + wireFeesPerExchange[exchangeBaseUrl] ?? Amounts.zeroOfCurrency(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; + + return { + amountDepositFeeLimitRemaining, + amountPayRemaining, + amountWireFeeLimitRemaining, + customerDepositFees, + customerWireFees, + wireFeeCoveredForExchange, + lastDepositFee: feeDeposit, + }; +} + +export type SelectPayCoinsResult = + | { + type: "failure"; + insufficientBalanceDetails: PayMerchantInsufficientBalanceDetails; + } + | { type: "success"; coinSel: PayCoinSelection }; + +/** + * 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 async function selectPayCoinsNew( + ws: InternalWalletState, + req: SelectPayCoinRequestNg, +): Promise { + const { + contractTermsAmount, + depositFeeLimit, + wireFeeLimit, + wireFeeAmortization, + } = req; + + // FIXME: Why don't we do this in a transaction? + const [candidateDenoms, wireFeesPerExchange] = + await selectPayMerchantCandidates(ws, req); + + const coinPubs: string[] = []; + const coinContributions: AmountJson[] = []; + const currency = contractTermsAmount.currency; + + let tally: CoinSelectionTally = { + amountPayRemaining: contractTermsAmount, + amountWireFeeLimitRemaining: wireFeeLimit, + amountDepositFeeLimitRemaining: depositFeeLimit, + customerDepositFees: Amounts.zeroOfCurrency(currency), + customerWireFees: Amounts.zeroOfCurrency(currency), + wireFeeCoveredForExchange: new Set(), + lastDepositFee: Amounts.zeroOfCurrency(currency), + }; + + const prevPayCoins = req.prevPayCoins ?? []; + + // Look at existing pay coin selection and tally up + for (const prev of prevPayCoins) { + tally = tallyFees( + tally, + wireFeesPerExchange, + wireFeeAmortization, + prev.exchangeBaseUrl, + prev.feeDeposit, + ); + tally.amountPayRemaining = Amounts.sub( + tally.amountPayRemaining, + prev.contribution, + ).amount; + + coinPubs.push(prev.coinPub); + coinContributions.push(prev.contribution); + } + + let selectedDenom: SelResult | undefined; + if (req.forcedSelection) { + selectedDenom = selectForced(req, candidateDenoms); + } else { + // 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. + selectedDenom = selectGreedy( + req, + candidateDenoms, + wireFeesPerExchange, + tally, + ); + } + + if (!selectedDenom) { + const details = await getMerchantPaymentBalanceDetails(ws, { + acceptedAuditors: req.auditors, + acceptedExchanges: req.exchanges, + acceptedWireMethods: [req.wireMethod], + currency: Amounts.currencyOf(req.contractTermsAmount), + minAge: req.requiredMinimumAge ?? 0, + }); + let feeGapEstimate: AmountJson; + if ( + Amounts.cmp( + details.balanceMerchantDepositable, + req.contractTermsAmount, + ) >= 0 + ) { + // FIXME: We can probably give a better estimate. + feeGapEstimate = Amounts.add( + tally.amountPayRemaining, + tally.lastDepositFee, + ).amount; + } else { + feeGapEstimate = Amounts.zeroOfAmount(req.contractTermsAmount); + } + return { + type: "failure", + insufficientBalanceDetails: { + amountRequested: Amounts.stringify(req.contractTermsAmount), + balanceAgeAcceptable: Amounts.stringify(details.balanceAgeAcceptable), + balanceAvailable: Amounts.stringify(details.balanceAvailable), + balanceMaterial: Amounts.stringify(details.balanceMaterial), + balanceMerchantAcceptable: Amounts.stringify( + details.balanceMerchantAcceptable, + ), + balanceMerchantDepositable: Amounts.stringify( + details.balanceMerchantDepositable, + ), + feeGapEstimate: Amounts.stringify(feeGapEstimate), + }, + }; + } + + const finalSel = selectedDenom; + + logger.trace(`coin selection request ${j2s(req)}`); + logger.trace(`selected coins (via denoms) for payment: ${j2s(finalSel)}`); + + await ws.db.runReadOnlyTx(["coins", "denominations"], async (tx) => { + for (const dph of Object.keys(finalSel)) { + const selInfo = finalSel[dph]; + const numRequested = selInfo.contributions.length; + const query = [ + selInfo.exchangeBaseUrl, + selInfo.denomPubHash, + selInfo.maxAge, + CoinStatus.Fresh, + ]; + logger.trace(`query: ${j2s(query)}`); + const coins = + await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll( + query, + numRequested, + ); + if (coins.length != numRequested) { + throw Error( + `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`, + ); + } + coinPubs.push(...coins.map((x) => x.coinPub)); + coinContributions.push(...selInfo.contributions); + } + }); + + return { + type: "success", + coinSel: { + paymentAmount: Amounts.stringify(contractTermsAmount), + coinContributions: coinContributions.map((x) => Amounts.stringify(x)), + coinPubs, + customerDepositFees: Amounts.stringify(tally.customerDepositFees), + customerWireFees: Amounts.stringify(tally.customerWireFees), + }, + }; +} + +function makeAvailabilityKey( + exchangeBaseUrl: string, + denomPubHash: string, + maxAge: number, +): string { + return `${denomPubHash};${maxAge};${exchangeBaseUrl}`; +} + +/** + * Selection result. + */ +interface SelResult { + /** + * Map from an availability key + * to an array of contributions. + */ + [avKey: string]: { + exchangeBaseUrl: string; + denomPubHash: string; + expireWithdraw: TalerProtocolTimestamp; + expireDeposit: TalerProtocolTimestamp; + maxAge: number; + contributions: AmountJson[]; + }; +} + +export function testing_selectGreedy( + ...args: Parameters +): ReturnType { + return selectGreedy(...args); +} + +function selectGreedy( + req: SelectPayCoinRequestNg, + candidateDenoms: AvailableDenom[], + wireFeesPerExchange: Record, + tally: CoinSelectionTally, +): SelResult | undefined { + const { wireFeeAmortization } = req; + const selectedDenom: SelResult = {}; + for (const denom of candidateDenoms) { + const contributions: AmountJson[] = []; + + // Don't use this coin if depositing it is more expensive than + // the amount it would give the merchant. + if (Amounts.cmp(denom.feeDeposit, denom.value) > 0) { + tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit); + continue; + } + + for ( + let i = 0; + i < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining); + i++ + ) { + tally = tallyFees( + tally, + wireFeesPerExchange, + wireFeeAmortization, + denom.exchangeBaseUrl, + Amounts.parseOrThrow(denom.feeDeposit), + ); + + const coinSpend = Amounts.max( + Amounts.min(tally.amountPayRemaining, denom.value), + denom.feeDeposit, + ); + + tally.amountPayRemaining = Amounts.sub( + tally.amountPayRemaining, + coinSpend, + ).amount; + + contributions.push(coinSpend); + } + + if (contributions.length) { + const avKey = makeAvailabilityKey( + denom.exchangeBaseUrl, + denom.denomPubHash, + denom.maxAge, + ); + let sd = selectedDenom[avKey]; + if (!sd) { + sd = { + contributions: [], + denomPubHash: denom.denomPubHash, + exchangeBaseUrl: denom.exchangeBaseUrl, + maxAge: denom.maxAge, + expireDeposit: denom.stampExpireDeposit, + expireWithdraw: denom.stampExpireWithdraw, + }; + } + sd.contributions.push(...contributions); + selectedDenom[avKey] = sd; + } + } + return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined; +} + +function selectForced( + req: SelectPayCoinRequestNg, + candidateDenoms: AvailableDenom[], +): SelResult | undefined { + const selectedDenom: SelResult = {}; + + const forcedSelection = req.forcedSelection; + checkLogicInvariant(!!forcedSelection); + + for (const forcedCoin of forcedSelection.coins) { + let found = false; + for (const aci of candidateDenoms) { + if (aci.numAvailable <= 0) { + continue; + } + if (Amounts.cmp(aci.value, forcedCoin.value) === 0) { + aci.numAvailable--; + const avKey = makeAvailabilityKey( + aci.exchangeBaseUrl, + aci.denomPubHash, + aci.maxAge, + ); + let sd = selectedDenom[avKey]; + if (!sd) { + sd = { + contributions: [], + denomPubHash: aci.denomPubHash, + exchangeBaseUrl: aci.exchangeBaseUrl, + maxAge: aci.maxAge, + expireDeposit: aci.stampExpireDeposit, + expireWithdraw: aci.stampExpireWithdraw, + }; + } + sd.contributions.push(Amounts.parseOrThrow(forcedCoin.value)); + selectedDenom[avKey] = sd; + found = true; + break; + } + } + if (!found) { + throw Error("can't find coin for forced coin selection"); + } + } + + return selectedDenom; +} + +export function checkAccountRestriction( + paytoUri: string, + restrictions: AccountRestriction[], +): { ok: boolean; hint?: string; hintI18n?: InternationalizedString } { + for (const myRestriction of restrictions) { + switch (myRestriction.type) { + case "deny": + return { ok: false }; + case "regex": + const regex = new RegExp(myRestriction.payto_regex); + if (!regex.test(paytoUri)) { + return { + ok: false, + hint: myRestriction.human_hint, + hintI18n: myRestriction.human_hint_i18n, + }; + } + } + } + return { + ok: true, + }; +} + +export interface SelectPayCoinRequestNg { + exchanges: AllowedExchangeInfo[]; + auditors: AllowedAuditorInfo[]; + wireMethod: string; + contractTermsAmount: AmountJson; + depositFeeLimit: AmountJson; + wireFeeLimit: AmountJson; + wireFeeAmortization: number; + prevPayCoins?: PreviousPayCoins; + requiredMinimumAge?: number; + forcedSelection?: ForcedCoinSel; + + /** + * Deposit payto URI, in case we already know the account that + * will be deposited into. + * + * That is typically the case when the wallet does a deposit to + * return funds to the user's own bank account. + */ + depositPaytoUri?: string; +} + +export type AvailableDenom = DenominationInfo & { + maxAge: number; + numAvailable: number; +}; + +async function selectPayMerchantCandidates( + ws: InternalWalletState, + req: SelectPayCoinRequestNg, +): Promise<[AvailableDenom[], Record]> { + return await ws.db.runReadOnlyTx( + ["exchanges", "exchangeDetails", "denominations", "coinAvailability"], + async (tx) => { + // FIXME: Use the existing helper (from balance.ts) to + // get acceptable exchanges. + const denoms: AvailableDenom[] = []; + const exchanges = await tx.exchanges.iter().toArray(); + const wfPerExchange: Record = {}; + loopExchange: for (const exchange of exchanges) { + const exchangeDetails = await getExchangeWireDetailsInTx( + tx, + exchange.baseUrl, + ); + // 1.- exchange has same currency + if (exchangeDetails?.currency !== req.contractTermsAmount.currency) { + continue; + } + let wireMethodFee: string | undefined; + // 2.- exchange supports wire method + loopWireAccount: for (const acc of exchangeDetails.wireInfo.accounts) { + const pp = parsePaytoUri(acc.payto_uri); + checkLogicInvariant(!!pp); + if (pp.targetType !== req.wireMethod) { + continue; + } + const wireFeeStr = exchangeDetails.wireInfo.feesForType[ + req.wireMethod + ]?.find((x) => { + return AbsoluteTime.isBetween( + AbsoluteTime.now(), + AbsoluteTime.fromProtocolTimestamp(x.startStamp), + AbsoluteTime.fromProtocolTimestamp(x.endStamp), + ); + })?.wireFee; + let debitAccountCheckOk = false; + if (req.depositPaytoUri) { + // FIXME: We should somehow propagate the hint here! + const checkResult = checkAccountRestriction( + req.depositPaytoUri, + acc.debit_restrictions, + ); + if (checkResult.ok) { + debitAccountCheckOk = true; + } + } else { + debitAccountCheckOk = true; + } + + if (wireFeeStr) { + wireMethodFee = wireFeeStr; + break loopWireAccount; + } + } + if (!wireMethodFee) { + continue; + } + wfPerExchange[exchange.baseUrl] = Amounts.parseOrThrow(wireMethodFee); + + // 3.- exchange is trusted in the exchange list or auditor list + let accepted = false; + for (const allowedExchange of req.exchanges) { + if (allowedExchange.exchangePub === exchangeDetails.masterPublicKey) { + accepted = true; + break; + } + } + for (const allowedAuditor of req.auditors) { + for (const providedAuditor of exchangeDetails.auditors) { + if (allowedAuditor.auditorPub === providedAuditor.auditor_pub) { + accepted = true; + break; + } + } + } + if (!accepted) { + continue; + } + // 4.- filter coins restricted by age + let ageLower = 0; + let ageUpper = AgeRestriction.AGE_UNRESTRICTED; + if (req.requiredMinimumAge) { + ageLower = req.requiredMinimumAge; + } + const myExchangeCoins = + await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll( + GlobalIDB.KeyRange.bound( + [exchangeDetails.exchangeBaseUrl, ageLower, 1], + [ + exchangeDetails.exchangeBaseUrl, + ageUpper, + Number.MAX_SAFE_INTEGER, + ], + ), + ); + // 5.- save denoms with how many coins are available + // FIXME: Check that the individual denomination is audited! + // FIXME: Should we exclude denominations that are + // not spendable anymore? + for (const coinAvail of myExchangeCoins) { + const denom = await tx.denominations.get([ + coinAvail.exchangeBaseUrl, + coinAvail.denomPubHash, + ]); + checkDbInvariant(!!denom); + if (denom.isRevoked || !denom.isOffered) { + continue; + } + denoms.push({ + ...DenominationRecord.toDenomInfo(denom), + numAvailable: coinAvail.freshCoinCount ?? 0, + maxAge: coinAvail.maxAge, + }); + } + } + logger.info(`available denoms ${j2s(denoms)}`); + // Sort by available amount (descending), deposit fee (ascending) and + // denomPub (ascending) if deposit fee is the same + // (to guarantee deterministic results) + denoms.sort( + (o1, o2) => + -Amounts.cmp(o1.value, o2.value) || + Amounts.cmp(o1.feeDeposit, o2.feeDeposit) || + strcmp(o1.denomPubHash, o2.denomPubHash), + ); + return [denoms, wfPerExchange]; + }, + ); +} + +/** + * Get a list of denominations (with repetitions possible) + * whose total value is as close as possible to the available + * amount, but never larger. + */ +export function selectWithdrawalDenominations( + amountAvailable: AmountJson, + denoms: DenominationRecord[], + denomselAllowLate: boolean = false, +): DenomSelectionState { + let remaining = Amounts.copy(amountAvailable); + + const selectedDenoms: { + count: number; + denomPubHash: string; + }[] = []; + + let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency); + let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency); + + denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate)); + denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value)); + + for (const d of denoms) { + const cost = Amounts.add(d.value, d.fees.feeWithdraw).amount; + const res = Amounts.divmod(remaining, cost); + const count = res.quotient; + remaining = Amounts.sub(remaining, Amounts.mult(cost, count).amount).amount; + if (count > 0) { + totalCoinValue = Amounts.add( + totalCoinValue, + Amounts.mult(d.value, count).amount, + ).amount; + totalWithdrawCost = Amounts.add( + totalWithdrawCost, + Amounts.mult(cost, count).amount, + ).amount; + selectedDenoms.push({ + count, + denomPubHash: d.denomPubHash, + }); + } + + if (Amounts.isZero(remaining)) { + break; + } + } + + if (logger.shouldLogTrace()) { + logger.trace( + `selected withdrawal denoms for ${Amounts.stringify(totalCoinValue)}`, + ); + for (const sd of selectedDenoms) { + logger.trace(`denom_pub_hash=${sd.denomPubHash}, count=${sd.count}`); + } + logger.trace("(end of withdrawal denom list)"); + } + + return { + selectedDenoms, + totalCoinValue: Amounts.stringify(totalCoinValue), + totalWithdrawCost: Amounts.stringify(totalWithdrawCost), + }; +} + +export function selectForcedWithdrawalDenominations( + amountAvailable: AmountJson, + denoms: DenominationRecord[], + forcedDenomSel: ForcedDenomSel, + denomselAllowLate: boolean, +): DenomSelectionState { + const selectedDenoms: { + count: number; + denomPubHash: string; + }[] = []; + + let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency); + let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency); + + denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate)); + denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value)); + + for (const fds of forcedDenomSel.denoms) { + const count = fds.count; + const denom = denoms.find((x) => { + return Amounts.cmp(x.value, fds.value) == 0; + }); + if (!denom) { + throw Error( + `unable to find denom for forced selection (value ${fds.value})`, + ); + } + const cost = Amounts.add(denom.value, denom.fees.feeWithdraw).amount; + totalCoinValue = Amounts.add( + totalCoinValue, + Amounts.mult(denom.value, count).amount, + ).amount; + totalWithdrawCost = Amounts.add( + totalWithdrawCost, + Amounts.mult(cost, count).amount, + ).amount; + selectedDenoms.push({ + count, + denomPubHash: denom.denomPubHash, + }); + } + + return { + selectedDenoms, + totalCoinValue: Amounts.stringify(totalCoinValue), + totalWithdrawCost: Amounts.stringify(totalWithdrawCost), + }; +} + +export interface CoinInfo { + id: string; + value: AmountJson; + denomDeposit: AmountJson; + denomWithdraw: AmountJson; + denomRefresh: AmountJson; + totalAvailable: number | undefined; + exchangeWire: AmountJson | undefined; + exchangePurse: AmountJson | undefined; + duration: Duration; + exchangeBaseUrl: string; + maxAge: number; +} + +export interface SelectedPeerCoin { + coinPub: string; + coinPriv: string; + contribution: AmountString; + denomPubHash: string; + denomSig: UnblindedSignature; + ageCommitmentProof: AgeCommitmentProof | undefined; +} + +export interface PeerCoinSelectionDetails { + exchangeBaseUrl: string; + + /** + * Info of Coins that were selected. + */ + coins: SelectedPeerCoin[]; + + /** + * How much of the deposit fees is the customer paying? + */ + depositFees: AmountJson; + + maxExpirationDate: TalerProtocolTimestamp; +} + +export type SelectPeerCoinsResult = + | { type: "success"; result: PeerCoinSelectionDetails } + | { + type: "failure"; + insufficientBalanceDetails: PayPeerInsufficientBalanceDetails; + }; + +export interface PeerCoinRepair { + exchangeBaseUrl: string; + coinPubs: CoinPublicKeyString[]; + contribs: AmountJson[]; +} + +export interface PeerCoinSelectionRequest { + instructedAmount: AmountJson; + + /** + * Instruct the coin selection to repair this coin + * selection instead of selecting completely new coins. + */ + repair?: PeerCoinRepair; +} + +/** + * Get coin availability information for a certain exchange. + */ +async function selectPayPeerCandidatesForExchange( + ws: InternalWalletState, + tx: WalletDbReadOnlyTransaction<["coinAvailability", "denominations"]>, + exchangeBaseUrl: string, +): Promise { + const denoms: AvailableDenom[] = []; + + let ageLower = 0; + let ageUpper = AgeRestriction.AGE_UNRESTRICTED; + const myExchangeCoins = + await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll( + GlobalIDB.KeyRange.bound( + [exchangeBaseUrl, ageLower, 1], + [exchangeBaseUrl, ageUpper, Number.MAX_SAFE_INTEGER], + ), + ); + + for (const coinAvail of myExchangeCoins) { + const denom = await tx.denominations.get([ + coinAvail.exchangeBaseUrl, + coinAvail.denomPubHash, + ]); + checkDbInvariant(!!denom); + if (denom.isRevoked || !denom.isOffered) { + continue; + } + denoms.push({ + ...DenominationRecord.toDenomInfo(denom), + numAvailable: coinAvail.freshCoinCount ?? 0, + maxAge: coinAvail.maxAge, + }); + } + // Sort by available amount (descending), deposit fee (ascending) and + // denomPub (ascending) if deposit fee is the same + // (to guarantee deterministic results) + denoms.sort( + (o1, o2) => + -Amounts.cmp(o1.value, o2.value) || + Amounts.cmp(o1.feeDeposit, o2.feeDeposit) || + strcmp(o1.denomPubHash, o2.denomPubHash), + ); + + return denoms; +} + +interface PeerCoinSelectionTally { + amountAcc: AmountJson; + depositFeesAcc: AmountJson; + lastDepositFee: AmountJson; +} + +/** + * exporting for testing + */ +export function testing_greedySelectPeer( + ...args: Parameters +): ReturnType { + return greedySelectPeer(...args); +} + +function greedySelectPeer( + candidates: AvailableDenom[], + instructedAmount: AmountLike, + tally: PeerCoinSelectionTally, +): SelResult | undefined { + const selectedDenom: SelResult = {}; + for (const denom of candidates) { + const contributions: AmountJson[] = []; + for ( + let i = 0; + i < denom.numAvailable && + Amounts.cmp(tally.amountAcc, instructedAmount) < 0; + i++ + ) { + const amountPayRemaining = Amounts.sub( + instructedAmount, + tally.amountAcc, + ).amount; + // Maximum amount the coin could effectively contribute. + const maxCoinContrib = Amounts.sub(denom.value, denom.feeDeposit).amount; + + const coinSpend = Amounts.min( + Amounts.add(amountPayRemaining, denom.feeDeposit).amount, + maxCoinContrib, + ); + + tally.amountAcc = Amounts.add(tally.amountAcc, coinSpend).amount; + tally.amountAcc = Amounts.sub(tally.amountAcc, denom.feeDeposit).amount; + + tally.depositFeesAcc = Amounts.add( + tally.depositFeesAcc, + denom.feeDeposit, + ).amount; + + tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit); + + contributions.push(coinSpend); + } + if (contributions.length > 0) { + const avKey = makeAvailabilityKey( + denom.exchangeBaseUrl, + denom.denomPubHash, + denom.maxAge, + ); + let sd = selectedDenom[avKey]; + if (!sd) { + sd = { + contributions: [], + denomPubHash: denom.denomPubHash, + exchangeBaseUrl: denom.exchangeBaseUrl, + maxAge: denom.maxAge, + expireDeposit: denom.stampExpireDeposit, + expireWithdraw: denom.stampExpireWithdraw, + }; + } + sd.contributions.push(...contributions); + selectedDenom[avKey] = sd; + } + if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) { + break; + } + } + + if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) { + return selectedDenom; + } + return undefined; +} + +export async function selectPeerCoins( + ws: InternalWalletState, + req: PeerCoinSelectionRequest, +): Promise { + const instructedAmount = req.instructedAmount; + if (Amounts.isZero(instructedAmount)) { + // Other parts of the code assume that we have at least + // one coin to spend. + throw new Error("amount of zero not allowed"); + } + return await ws.db.runReadWriteTx( + [ + "exchanges", + "contractTerms", + "coins", + "coinAvailability", + "denominations", + "refreshGroups", + "peerPushDebit", + ], + async (tx) => { + const exchanges = await tx.exchanges.iter().toArray(); + const exchangeFeeGap: { [url: string]: AmountJson } = {}; + const currency = Amounts.currencyOf(instructedAmount); + for (const exch of exchanges) { + if (exch.detailsPointer?.currency !== currency) { + continue; + } + const candidates = await selectPayPeerCandidatesForExchange( + ws, + tx, + exch.baseUrl, + ); + const tally: PeerCoinSelectionTally = { + amountAcc: Amounts.zeroOfCurrency(currency), + depositFeesAcc: Amounts.zeroOfCurrency(currency), + lastDepositFee: Amounts.zeroOfCurrency(currency), + }; + const resCoins: { + coinPub: string; + coinPriv: string; + contribution: AmountString; + denomPubHash: string; + denomSig: UnblindedSignature; + ageCommitmentProof: AgeCommitmentProof | undefined; + }[] = []; + + if (req.repair && req.repair.exchangeBaseUrl === exch.baseUrl) { + for (let i = 0; i < req.repair.coinPubs.length; i++) { + const contrib = req.repair.contribs[i]; + const coin = await tx.coins.get(req.repair.coinPubs[i]); + if (!coin) { + throw Error("repair not possible, coin not found"); + } + const denom = await ws.getDenomInfo( + ws, + tx, + coin.exchangeBaseUrl, + coin.denomPubHash, + ); + checkDbInvariant(!!denom); + resCoins.push({ + coinPriv: coin.coinPriv, + coinPub: coin.coinPub, + contribution: Amounts.stringify(contrib), + denomPubHash: coin.denomPubHash, + denomSig: coin.denomSig, + ageCommitmentProof: coin.ageCommitmentProof, + }); + const depositFee = Amounts.parseOrThrow(denom.feeDeposit); + tally.lastDepositFee = depositFee; + tally.amountAcc = Amounts.add( + tally.amountAcc, + Amounts.sub(contrib, depositFee).amount, + ).amount; + tally.depositFeesAcc = Amounts.add( + tally.depositFeesAcc, + depositFee, + ).amount; + } + } + + const selectedDenom = greedySelectPeer( + candidates, + instructedAmount, + tally, + ); + + if (selectedDenom) { + let minAutorefreshExecuteThreshold = TalerProtocolTimestamp.never(); + for (const dph of Object.keys(selectedDenom)) { + const selInfo = selectedDenom[dph]; + // Compute earliest time that a selected denom + // would have its coins auto-refreshed. + minAutorefreshExecuteThreshold = TalerProtocolTimestamp.min( + minAutorefreshExecuteThreshold, + AbsoluteTime.toProtocolTimestamp( + getAutoRefreshExecuteThreshold({ + stampExpireDeposit: selInfo.expireDeposit, + stampExpireWithdraw: selInfo.expireWithdraw, + }), + ), + ); + const numRequested = selInfo.contributions.length; + const query = [ + selInfo.exchangeBaseUrl, + selInfo.denomPubHash, + selInfo.maxAge, + CoinStatus.Fresh, + ]; + logger.info(`query: ${j2s(query)}`); + const coins = + await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll( + query, + numRequested, + ); + if (coins.length != numRequested) { + throw Error( + `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`, + ); + } + for (let i = 0; i < selInfo.contributions.length; i++) { + resCoins.push({ + coinPriv: coins[i].coinPriv, + coinPub: coins[i].coinPub, + contribution: Amounts.stringify(selInfo.contributions[i]), + ageCommitmentProof: coins[i].ageCommitmentProof, + denomPubHash: selInfo.denomPubHash, + denomSig: coins[i].denomSig, + }); + } + } + + const res: PeerCoinSelectionDetails = { + exchangeBaseUrl: exch.baseUrl, + coins: resCoins, + depositFees: tally.depositFeesAcc, + maxExpirationDate: minAutorefreshExecuteThreshold, + }; + return { type: "success", result: res }; + } + + const diff = Amounts.sub(instructedAmount, tally.amountAcc).amount; + exchangeFeeGap[exch.baseUrl] = Amounts.add( + tally.lastDepositFee, + diff, + ).amount; + + continue; + } + + // We were unable to select coins. + // Now we need to produce error details. + + const infoGeneral = await getPeerPaymentBalanceDetailsInTx(ws, tx, { + currency, + }); + + const perExchange: PayPeerInsufficientBalanceDetails["perExchange"] = {}; + + let maxFeeGapEstimate = Amounts.zeroOfCurrency(currency); + + for (const exch of exchanges) { + if (exch.detailsPointer?.currency !== currency) { + continue; + } + const infoExchange = await getPeerPaymentBalanceDetailsInTx(ws, tx, { + currency, + restrictExchangeTo: exch.baseUrl, + }); + let gap = + exchangeFeeGap[exch.baseUrl] ?? Amounts.zeroOfCurrency(currency); + if (Amounts.cmp(infoExchange.balanceMaterial, instructedAmount) < 0) { + // Show fee gap only if we should've been able to pay with the material amount + gap = Amounts.zeroOfCurrency(currency); + } + perExchange[exch.baseUrl] = { + balanceAvailable: Amounts.stringify(infoExchange.balanceAvailable), + balanceMaterial: Amounts.stringify(infoExchange.balanceMaterial), + feeGapEstimate: Amounts.stringify(gap), + }; + + maxFeeGapEstimate = Amounts.max(maxFeeGapEstimate, gap); + } + + const errDetails: PayPeerInsufficientBalanceDetails = { + amountRequested: Amounts.stringify(instructedAmount), + balanceAvailable: Amounts.stringify(infoGeneral.balanceAvailable), + balanceMaterial: Amounts.stringify(infoGeneral.balanceMaterial), + feeGapEstimate: Amounts.stringify(maxFeeGapEstimate), + perExchange, + }; + + return { type: "failure", insufficientBalanceDetails: errDetails }; + }, + ); +} -- cgit v1.2.3