diff options
Diffstat (limited to 'packages/taler-wallet-core/src/util/coinSelection.ts')
| -rw-r--r-- | packages/taler-wallet-core/src/util/coinSelection.ts | 597 |
1 files changed, 596 insertions, 1 deletions
diff --git a/packages/taler-wallet-core/src/util/coinSelection.ts b/packages/taler-wallet-core/src/util/coinSelection.ts index 0bd624bf7..176d636fc 100644 --- a/packages/taler-wallet-core/src/util/coinSelection.ts +++ b/packages/taler-wallet-core/src/util/coinSelection.ts @@ -23,13 +23,35 @@ /** * Imports. */ +import { GlobalIDB } from "@gnu-taler/idb-bridge"; import { + AbsoluteTime, AgeCommitmentProof, + AgeRestriction, AmountJson, Amounts, + CoinStatus, + DenominationInfo, DenominationPubKey, + DenomSelectionState, + ForcedCoinSel, + ForcedDenomSel, + j2s, Logger, + parsePaytoUri, + PayCoinSelection, + PayMerchantInsufficientBalanceDetails, + strcmp, } from "@gnu-taler/taler-util"; +import { + AllowedAuditorInfo, + AllowedExchangeInfo, + DenominationRecord, +} from "../db.js"; +import { getExchangeDetails, isWithdrawableDenom } from "../index.js"; +import { InternalWalletState } from "../internal-wallet-state.js"; +import { getMerchantPaymentBalanceDetails } from "../operations/balance.js"; +import { checkDbInvariant, checkLogicInvariant } from "./invariants.js"; const logger = new Logger("coinSelection.ts"); @@ -125,7 +147,7 @@ export interface CoinSelectionTally { * Account for the fees of spending a coin. */ export function tallyFees( - tally: CoinSelectionTally, + tally: Readonly<CoinSelectionTally>, wireFeesPerExchange: Record<string, AmountJson>, wireFeeAmortization: number, exchangeBaseUrl: string, @@ -193,3 +215,576 @@ export function tallyFees( 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<SelectPayCoinsResult> { + const { + contractTermsAmount, + depositFeeLimit, + wireFeeLimit, + wireFeeAmortization, + } = req; + + const [candidateDenoms, wireFeesPerExchange] = await selectCandidates( + 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.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})`, + ); + } + 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; + maxAge: number; + contributions: AmountJson[]; + }; +} + +function selectGreedy( + req: SelectPayCoinRequestNg, + candidateDenoms: AvailableDenom[], + wireFeesPerExchange: Record<string, AmountJson>, + 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, + }; + } + 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, + }; + } + 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 interface SelectPayCoinRequestNg { + exchanges: AllowedExchangeInfo[]; + auditors: AllowedAuditorInfo[]; + wireMethod: string; + contractTermsAmount: AmountJson; + depositFeeLimit: AmountJson; + wireFeeLimit: AmountJson; + wireFeeAmortization: number; + prevPayCoins?: PreviousPayCoins; + requiredMinimumAge?: number; + forcedSelection?: ForcedCoinSel; +} + +export type AvailableDenom = DenominationInfo & { + maxAge: number; + numAvailable: number; +}; + +export async function selectCandidates( + ws: InternalWalletState, + req: SelectPayCoinRequestNg, +): Promise<[AvailableDenom[], Record<string, AmountJson>]> { + return await ws.db + .mktx((x) => [ + x.exchanges, + x.exchangeDetails, + x.denominations, + x.coinAvailability, + ]) + .runReadOnly(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<string, AmountJson> = {}; + for (const exchange of exchanges) { + const exchangeDetails = await getExchangeDetails(tx, exchange.baseUrl); + // 1.- exchange has same currency + if (exchangeDetails?.currency !== req.contractTermsAmount.currency) { + continue; + } + let wireMethodFee: string | undefined; + // 2.- exchange supports wire method + for (const acc of exchangeDetails.wireInfo.accounts) { + const pp = parsePaytoUri(acc.payto_uri); + checkLogicInvariant(!!pp); + if (pp.targetType === req.wireMethod) { + // also check that wire method is supported now + const wireFeeStr = exchangeDetails.wireInfo.feesForType[ + req.wireMethod + ]?.find((x) => { + return AbsoluteTime.isBetween( + AbsoluteTime.now(), + AbsoluteTime.fromTimestamp(x.startStamp), + AbsoluteTime.fromTimestamp(x.endStamp), + ); + })?.wireFee; + if (wireFeeStr) { + wireMethodFee = wireFeeStr; + } + break; + } + } + if (!wireMethodFee) { + break; + } + 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, + }); + } + } + // 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[], +): 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(isWithdrawableDenom); + denoms.sort((d1, d2) => + Amounts.cmp( + DenominationRecord.getValue(d2), + DenominationRecord.getValue(d1), + ), + ); + + for (const d of denoms) { + let count = 0; + const cost = Amounts.add( + DenominationRecord.getValue(d), + d.fees.feeWithdraw, + ).amount; + for (;;) { + if (Amounts.cmp(remaining, cost) < 0) { + break; + } + remaining = Amounts.sub(remaining, cost).amount; + count++; + } + if (count > 0) { + totalCoinValue = Amounts.add( + totalCoinValue, + Amounts.mult(DenominationRecord.getValue(d), 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, +): DenomSelectionState { + const selectedDenoms: { + count: number; + denomPubHash: string; + }[] = []; + + let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency); + let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency); + + denoms = denoms.filter(isWithdrawableDenom); + denoms.sort((d1, d2) => + Amounts.cmp( + DenominationRecord.getValue(d2), + DenominationRecord.getValue(d1), + ), + ); + + for (const fds of forcedDenomSel.denoms) { + const count = fds.count; + const denom = denoms.find((x) => { + return Amounts.cmp(DenominationRecord.getValue(x), fds.value) == 0; + }); + if (!denom) { + throw Error( + `unable to find denom for forced selection (value ${fds.value})`, + ); + } + const cost = Amounts.add( + DenominationRecord.getValue(denom), + denom.fees.feeWithdraw, + ).amount; + totalCoinValue = Amounts.add( + totalCoinValue, + Amounts.mult(DenominationRecord.getValue(denom), 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), + }; +} |