From b0cc65e17f2348f46ae1c9b88b69abae11266899 Mon Sep 17 00:00:00 2001 From: Sebastian Date: Fri, 31 Mar 2023 12:27:05 -0300 Subject: move coin selection function to coinSelection.ts and added a test placeholder, and some fixes: * selectCandidates was not save wire fee * selectCandidates show check wire fee time range --- .../taler-wallet-core/src/operations/deposits.ts | 2 +- .../taler-wallet-core/src/operations/exchanges.ts | 2 +- .../src/operations/pay-merchant.ts | 488 +---------------- .../taler-wallet-core/src/operations/refresh.ts | 6 +- .../taler-wallet-core/src/operations/withdraw.ts | 162 +----- .../src/util/coinSelection.test.ts | 29 + .../taler-wallet-core/src/util/coinSelection.ts | 597 ++++++++++++++++++++- .../taler-wallet-core/src/util/denominations.ts | 27 + 8 files changed, 681 insertions(+), 632 deletions(-) create mode 100644 packages/taler-wallet-core/src/util/coinSelection.test.ts diff --git a/packages/taler-wallet-core/src/operations/deposits.ts b/packages/taler-wallet-core/src/operations/deposits.ts index c6cd4732c..64217acab 100644 --- a/packages/taler-wallet-core/src/operations/deposits.ts +++ b/packages/taler-wallet-core/src/operations/deposits.ts @@ -76,9 +76,9 @@ import { extractContractData, generateDepositPermissions, getTotalPaymentCost, - selectPayCoinsNew, } from "./pay-merchant.js"; import { getTotalRefreshCost } from "./refresh.js"; +import { selectPayCoinsNew } from "../util/coinSelection.js"; /** * Logger. diff --git a/packages/taler-wallet-core/src/operations/exchanges.ts b/packages/taler-wallet-core/src/operations/exchanges.ts index 8a98c8299..d9051b32f 100644 --- a/packages/taler-wallet-core/src/operations/exchanges.ts +++ b/packages/taler-wallet-core/src/operations/exchanges.ts @@ -63,6 +63,7 @@ import { ExchangeRecord, WalletStoresV1, } from "../db.js"; +import { isWithdrawableDenom } from "../index.js"; import { InternalWalletState, TrustInfo } from "../internal-wallet-state.js"; import { checkDbInvariant } from "../util/invariants.js"; import { @@ -78,7 +79,6 @@ import { } from "../util/retries.js"; import { WALLET_EXCHANGE_PROTOCOL_VERSION } from "../versions.js"; import { runOperationWithErrorReporting } from "./common.js"; -import { isWithdrawableDenom } from "./withdraw.js"; const logger = new Logger("exchanges.ts"); diff --git a/packages/taler-wallet-core/src/operations/pay-merchant.ts b/packages/taler-wallet-core/src/operations/pay-merchant.ts index 25153f9fb..f8fa1d34d 100644 --- a/packages/taler-wallet-core/src/operations/pay-merchant.ts +++ b/packages/taler-wallet-core/src/operations/pay-merchant.ts @@ -24,12 +24,10 @@ /** * Imports. */ -import { GlobalIDB } from "@gnu-taler/idb-bridge"; import { AbortingCoin, AbortRequest, AbsoluteTime, - AgeRestriction, AmountJson, Amounts, ApplyRefundResponse, @@ -44,9 +42,8 @@ import { CoinStatus, ConfirmPayResult, ConfirmPayResultType, - MerchantContractTerms, + constructPayUri, ContractTermsUtil, - DenominationInfo, Duration, encodeCrock, ForcedCoinSel, @@ -54,11 +51,13 @@ import { HttpStatusCode, j2s, Logger, + makeErrorDetail, + makePendingOperationFailedError, MerchantCoinRefundFailureStatus, MerchantCoinRefundStatus, MerchantCoinRefundSuccessStatus, + MerchantContractTerms, NotificationType, - parsePaytoUri, parsePayUri, parseRefundUri, PayCoinSelection, @@ -66,19 +65,24 @@ import { PreparePayResultType, PrepareRefundResult, RefreshReason, - strcmp, + TalerError, TalerErrorCode, TalerErrorDetail, TalerProtocolTimestamp, + TalerProtocolViolationError, TransactionType, URL, - constructPayUri, - PayMerchantInsufficientBalanceDetails, } from "@gnu-taler/taler-util"; +import { + getHttpResponseErrorDetails, + readSuccessResponseJsonOrErrorCode, + readSuccessResponseJsonOrThrow, + readTalerErrorResponse, + readUnexpectedResponseDetails, + throwUnexpectedRequestError, +} from "@gnu-taler/taler-util/http"; import { EddsaKeypair } from "../crypto/cryptoImplementation.js"; import { - AllowedAuditorInfo, - AllowedExchangeInfo, BackupProviderStateTag, CoinRecord, DenominationRecord, @@ -89,51 +93,29 @@ import { WalletContractData, WalletStoresV1, } from "../db.js"; -import { - makeErrorDetail, - makePendingOperationFailedError, - TalerError, - TalerProtocolViolationError, -} from "@gnu-taler/taler-util"; import { GetReadWriteAccess, PendingTaskType } from "../index.js"; import { EXCHANGE_COINS_LOCK, InternalWalletState, } from "../internal-wallet-state.js"; import { assertUnreachable } from "../util/assertUnreachable.js"; +import { PreviousPayCoins, selectPayCoinsNew } from "../util/coinSelection.js"; +import { checkDbInvariant } from "../util/invariants.js"; +import { GetReadOnlyAccess } from "../util/query.js"; import { - CoinSelectionTally, - PreviousPayCoins, - tallyFees, -} from "../util/coinSelection.js"; -import { - getHttpResponseErrorDetails, - readSuccessResponseJsonOrErrorCode, - readSuccessResponseJsonOrThrow, - readTalerErrorResponse, - readUnexpectedResponseDetails, - throwUnexpectedRequestError, -} from "@gnu-taler/taler-util/http"; -import { checkDbInvariant, checkLogicInvariant } from "../util/invariants.js"; -import { + constructTaskIdentifier, OperationAttemptResult, OperationAttemptResultType, RetryInfo, - TaskIdentifiers, scheduleRetry, - constructTaskIdentifier, + TaskIdentifiers, } from "../util/retries.js"; import { makeTransactionId, runOperationWithErrorReporting, spendCoins, - storeOperationError, - storeOperationPending, } from "./common.js"; -import { getExchangeDetails } from "./exchanges.js"; import { createRefreshGroup, getTotalRefreshCost } from "./refresh.js"; -import { GetReadOnlyAccess } from "../util/query.js"; -import { getMerchantPaymentBalanceDetails } from "./balance.js"; /** * Logger. @@ -877,434 +859,6 @@ async function unblockBackup( }); } -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]> { - 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 = {}; - for (const exchange of exchanges) { - const exchangeDetails = await getExchangeDetails(tx, exchange.baseUrl); - if (exchangeDetails?.currency !== req.contractTermsAmount.currency) { - continue; - } - let wireMethodSupported = false; - for (const acc of exchangeDetails.wireInfo.accounts) { - const pp = parsePaytoUri(acc.payto_uri); - checkLogicInvariant(!!pp); - if (pp.targetType === req.wireMethod) { - wireMethodSupported = true; - break; - } - } - if (!wireMethodSupported) { - break; - } - exchangeDetails.wireInfo.accounts; - 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; - } - let ageLower = 0; - let ageUpper = AgeRestriction.AGE_UNRESTRICTED; - if (req.requiredMinimumAge) { - ageLower = req.requiredMinimumAge; - } - const myExchangeDenoms = - await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll( - GlobalIDB.KeyRange.bound( - [exchangeDetails.exchangeBaseUrl, ageLower, 1], - [ - exchangeDetails.exchangeBaseUrl, - ageUpper, - Number.MAX_SAFE_INTEGER, - ], - ), - ); - // FIXME: Check that the individual denomination is audited! - // FIXME: Should we exclude denominations that are - // not spendable anymore? - for (const denomAvail of myExchangeDenoms) { - const denom = await tx.denominations.get([ - denomAvail.exchangeBaseUrl, - denomAvail.denomPubHash, - ]); - checkDbInvariant(!!denom); - if (denom.isRevoked || !denom.isOffered) { - continue; - } - denoms.push({ - ...DenominationRecord.toDenomInfo(denom), - numAvailable: denomAvail.freshCoinCount ?? 0, - maxAge: denomAvail.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]; - }); -} - -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[]; - }; -} - -export function selectGreedy( - req: SelectPayCoinRequestNg, - candidateDenoms: AvailableDenom[], - wireFeesPerExchange: Record, - tally: CoinSelectionTally, -): SelResult | undefined { - const { wireFeeAmortization } = req; - const selectedDenom: SelResult = {}; - for (const aci of candidateDenoms) { - const contributions: AmountJson[] = []; - for (let i = 0; i < aci.numAvailable; i++) { - // 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.value) > 0) { - tally.lastDepositFee = Amounts.parseOrThrow(aci.feeDeposit); - continue; - } - - if (Amounts.isZero(tally.amountPayRemaining)) { - // We have spent enough! - break; - } - - tally = tallyFees( - tally, - wireFeesPerExchange, - wireFeeAmortization, - aci.exchangeBaseUrl, - Amounts.parseOrThrow(aci.feeDeposit), - ); - - let coinSpend = Amounts.max( - Amounts.min(tally.amountPayRemaining, aci.value), - aci.feeDeposit, - ); - - tally.amountPayRemaining = Amounts.sub( - tally.amountPayRemaining, - coinSpend, - ).amount; - contributions.push(coinSpend); - } - - if (contributions.length) { - 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(...contributions); - selectedDenom[avKey] = sd; - } - - if (Amounts.isZero(tally.amountPayRemaining)) { - return selectedDenom; - } - } - return undefined; -} - -export 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 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; - - const [candidateDenoms, wireFeesPerExchange] = await selectCandidates( - ws, - req, - ); - - // logger.trace(`candidate denoms: ${j2s(candidateDenoms)}`); - - 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), - }, - }; -} - export async function checkPaymentByProposalId( ws: InternalWalletState, proposalId: string, @@ -1704,9 +1258,7 @@ export async function confirmPay( const contractData = d.contractData; - let selectCoinsResult: SelectPayCoinsResult | undefined = undefined; - - selectCoinsResult = await selectPayCoinsNew(ws, { + const selectCoinsResult = await selectPayCoinsNew(ws, { auditors: contractData.allowedAuditors, exchanges: contractData.allowedExchanges, wireMethod: contractData.wireMethod, diff --git a/packages/taler-wallet-core/src/operations/refresh.ts b/packages/taler-wallet-core/src/operations/refresh.ts index 477a00503..70f0579c0 100644 --- a/packages/taler-wallet-core/src/operations/refresh.ts +++ b/packages/taler-wallet-core/src/operations/refresh.ts @@ -85,10 +85,8 @@ import { } from "../util/retries.js"; import { makeCoinAvailable } from "./common.js"; import { updateExchangeFromUrl } from "./exchanges.js"; -import { - isWithdrawableDenom, - selectWithdrawalDenominations, -} from "./withdraw.js"; +import { selectWithdrawalDenominations } from "../util/coinSelection.js"; +import { isWithdrawableDenom } from "../index.js"; const logger = new Logger("refresh.ts"); diff --git a/packages/taler-wallet-core/src/operations/withdraw.ts b/packages/taler-wallet-core/src/operations/withdraw.ts index 2c91d4184..643737e93 100644 --- a/packages/taler-wallet-core/src/operations/withdraw.ts +++ b/packages/taler-wallet-core/src/operations/withdraw.ts @@ -93,7 +93,6 @@ import { runLongpollAsync, runOperationWithErrorReporting, } from "../operations/common.js"; -import { walletCoreDebugFlags } from "../util/debugFlags.js"; import { HttpRequestLibrary, HttpResponse, @@ -123,168 +122,17 @@ import { getExchangeTrust, updateExchangeFromUrl, } from "./exchanges.js"; +import { + selectForcedWithdrawalDenominations, + selectWithdrawalDenominations, +} from "../util/coinSelection.js"; +import { isWithdrawableDenom } from "../index.js"; /** * Logger for this file. */ const logger = new Logger("operations/withdraw.ts"); -/** - * Check if a denom is withdrawable based on the expiration time, - * revocation and offered state. - */ -export function isWithdrawableDenom(d: DenominationRecord): boolean { - const now = AbsoluteTime.now(); - const start = AbsoluteTime.fromTimestamp(d.stampStart); - const withdrawExpire = AbsoluteTime.fromTimestamp(d.stampExpireWithdraw); - const started = AbsoluteTime.cmp(now, start) >= 0; - let lastPossibleWithdraw: AbsoluteTime; - if (walletCoreDebugFlags.denomselAllowLate) { - lastPossibleWithdraw = start; - } else { - lastPossibleWithdraw = AbsoluteTime.subtractDuraction( - withdrawExpire, - durationFromSpec({ minutes: 5 }), - ); - } - const remaining = Duration.getRemaining(lastPossibleWithdraw, now); - const stillOkay = remaining.d_ms !== 0; - return started && stillOkay && !d.isRevoked && d.isOffered; -} - -/** - * 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), - }; -} - /** * Get information about a withdrawal from * a taler://withdraw URI by asking the bank. diff --git a/packages/taler-wallet-core/src/util/coinSelection.test.ts b/packages/taler-wallet-core/src/util/coinSelection.test.ts new file mode 100644 index 000000000..7814a9233 --- /dev/null +++ b/packages/taler-wallet-core/src/util/coinSelection.test.ts @@ -0,0 +1,29 @@ +/* + This file is part of GNU Taler + (C) 2022 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 + */ +import test, { ExecutionContext } from "ava"; + +function expect(t: ExecutionContext, thing: any): any { + return { + deep: { + equal: (another: any) => t.deepEqual(thing, another), + equals: (another: any) => t.deepEqual(thing, another), + }, + }; +} + +test("should have a test", (t) => { + expect(t, true).equal(true); +}); 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, wireFeesPerExchange: Record, 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 { + 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, + 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]> { + 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 = {}; + 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), + }; +} diff --git a/packages/taler-wallet-core/src/util/denominations.ts b/packages/taler-wallet-core/src/util/denominations.ts index ef35fe198..fb766e96a 100644 --- a/packages/taler-wallet-core/src/util/denominations.ts +++ b/packages/taler-wallet-core/src/util/denominations.ts @@ -20,12 +20,16 @@ import { Amounts, AmountString, DenominationInfo, + Duration, + durationFromSpec, FeeDescription, FeeDescriptionPair, TalerProtocolTimestamp, TimePoint, WireFee, } from "@gnu-taler/taler-util"; +import { DenominationRecord } from "../db.js"; +import { walletCoreDebugFlags } from "./debugFlags.js"; /** * Given a list of denominations with the same value and same period of time: @@ -443,3 +447,26 @@ export function createTimeline( return result; }, [] as FeeDescription[]); } + +/** + * Check if a denom is withdrawable based on the expiration time, + * revocation and offered state. + */ +export function isWithdrawableDenom(d: DenominationRecord): boolean { + const now = AbsoluteTime.now(); + const start = AbsoluteTime.fromTimestamp(d.stampStart); + const withdrawExpire = AbsoluteTime.fromTimestamp(d.stampExpireWithdraw); + const started = AbsoluteTime.cmp(now, start) >= 0; + let lastPossibleWithdraw: AbsoluteTime; + if (walletCoreDebugFlags.denomselAllowLate) { + lastPossibleWithdraw = start; + } else { + lastPossibleWithdraw = AbsoluteTime.subtractDuraction( + withdrawExpire, + durationFromSpec({ minutes: 5 }), + ); + } + const remaining = Duration.getRemaining(lastPossibleWithdraw, now); + const stillOkay = remaining.d_ms !== 0; + return started && stillOkay && !d.isRevoked && d.isOffered; +} -- cgit v1.2.3