/* 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, CoinPublicKeyString, CoinStatus, DenominationInfo, DenominationPubKey, DenomSelectionState, Duration, ForcedCoinSel, ForcedDenomSel, InternationalizedString, j2s, Logger, parsePaytoUri, PayCoinSelection, PayMerchantInsufficientBalanceDetails, PayPeerInsufficientBalanceDetails, strcmp, TalerProtocolTimestamp, UnblindedSignature, } from "@gnu-taler/taler-util"; import { DenominationRecord } from "../db.js"; import { getExchangeWireDetailsInTx, isWithdrawableDenom, WalletDbReadOnlyTransactionArr, } from "../index.js"; import { InternalWalletState } from "../internal-wallet-state.js"; import { getMerchantPaymentBalanceDetails, getPeerPaymentBalanceDetailsInTx, } from "../operations/balance.js"; import { getAutoRefreshExecuteThreshold } from "../operations/common.js"; import { checkDbInvariant, checkLogicInvariant } from "./invariants.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 .mktx((x) => [x.coins, x.denominations]) .runReadOnly(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: WalletDbReadOnlyTransactionArr<["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 .mktx((x) => [ x.exchanges, x.contractTerms, x.coins, x.coinAvailability, x.denominations, x.refreshGroups, x.peerPushDebit, ]) .runReadWrite(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 }; }); }