From b7f7b956028566c689d802258937deb081d5dc60 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Thu, 15 Sep 2022 20:16:42 +0200 Subject: wallet-core: towards faster coin selection --- packages/taler-util/src/walletTypes.ts | 3 + packages/taler-wallet-core/src/db.ts | 5 + .../taler-wallet-core/src/operations/deposits.ts | 8 +- packages/taler-wallet-core/src/operations/pay.ts | 213 ++++++++++++++++++++- .../src/util/coinSelection.test.ts | 22 +-- .../taler-wallet-core/src/util/coinSelection.ts | 6 +- packages/taler-wallet-core/src/wallet.ts | 31 +-- 7 files changed, 239 insertions(+), 49 deletions(-) diff --git a/packages/taler-util/src/walletTypes.ts b/packages/taler-util/src/walletTypes.ts index 7fcb752b1..c3e5c6ed0 100644 --- a/packages/taler-util/src/walletTypes.ts +++ b/packages/taler-util/src/walletTypes.ts @@ -694,6 +694,7 @@ const codecForDenominationInfo = (): Codec => .property("stampExpireWithdraw", codecForTimestamp) .property("stampExpireLegal", codecForTimestamp) .property("stampExpireDeposit", codecForTimestamp) + .property("exchangeBaseUrl", codecForString()) .build("codecForDenominationInfo"); export interface DenominationInfo { @@ -747,6 +748,8 @@ export interface DenominationInfo { * Data after which coins of this denomination can't be deposited anymore. */ stampExpireDeposit: TalerProtocolTimestamp; + + exchangeBaseUrl: string; } export type Operation = "deposit" | "withdraw" | "refresh" | "refund"; diff --git a/packages/taler-wallet-core/src/db.ts b/packages/taler-wallet-core/src/db.ts index 2c4d55820..760234941 100644 --- a/packages/taler-wallet-core/src/db.ts +++ b/packages/taler-wallet-core/src/db.ts @@ -348,6 +348,7 @@ export namespace DenominationRecord { stampExpireWithdraw: d.stampExpireWithdraw, stampStart: d.stampStart, value: DenominationRecord.getValue(d), + exchangeBaseUrl: d.exchangeBaseUrl, }; } } @@ -1778,6 +1779,10 @@ export const WalletStoresV1 = { { byBaseUrl: describeIndex("byBaseUrl", "exchangeBaseUrl"), byDenomPubHash: describeIndex("byDenomPubHash", "denomPubHash"), + byDenomPubHashAndStatus: describeIndex("byDenomPubHashAndStatus", [ + "denomPubHash", + "status", + ]), byCoinEvHash: describeIndex("byCoinEvHash", "coinEvHash"), }, ), diff --git a/packages/taler-wallet-core/src/operations/deposits.ts b/packages/taler-wallet-core/src/operations/deposits.ts index e6f1591ee..9747f21a3 100644 --- a/packages/taler-wallet-core/src/operations/deposits.ts +++ b/packages/taler-wallet-core/src/operations/deposits.ts @@ -51,7 +51,7 @@ import { OperationStatus, } from "../db.js"; import { InternalWalletState } from "../internal-wallet-state.js"; -import { selectPayCoins } from "../util/coinSelection.js"; +import { selectPayCoinsLegacy } from "../util/coinSelection.js"; import { readSuccessResponseJsonOrThrow } from "../util/http.js"; import { spendCoins } from "../wallet.js"; import { getExchangeDetails } from "./exchanges.js"; @@ -271,7 +271,7 @@ export async function getFeeForDeposit( const candidates = await getCandidatePayCoins(ws, csr); - const payCoinSel = selectPayCoins({ + const payCoinSel = selectPayCoinsLegacy({ candidates, contractTermsAmount: csr.amount, depositFeeLimit: csr.maxDepositFee, @@ -367,7 +367,7 @@ export async function prepareDepositGroup( wireMethod: contractData.wireMethod, }); - const payCoinSel = selectPayCoins({ + const payCoinSel = selectPayCoinsLegacy({ candidates, contractTermsAmount: contractData.amount, depositFeeLimit: contractData.maxDepositFee, @@ -470,7 +470,7 @@ export async function createDepositGroup( wireMethod: contractData.wireMethod, }); - const payCoinSel = selectPayCoins({ + const payCoinSel = selectPayCoinsLegacy({ candidates, contractTermsAmount: contractData.amount, depositFeeLimit: contractData.maxDepositFee, diff --git a/packages/taler-wallet-core/src/operations/pay.ts b/packages/taler-wallet-core/src/operations/pay.ts index 5e3c3dd15..fb3b2b991 100644 --- a/packages/taler-wallet-core/src/operations/pay.ts +++ b/packages/taler-wallet-core/src/operations/pay.ts @@ -26,6 +26,7 @@ */ import { AbsoluteTime, + AgeRestriction, AmountJson, Amounts, codecForContractTerms, @@ -36,6 +37,8 @@ import { ConfirmPayResultType, ContractTerms, ContractTermsUtil, + DenominationInfo, + DenominationPubKey, Duration, encodeCrock, ForcedCoinSel, @@ -50,6 +53,7 @@ import { PreparePayResult, PreparePayResultType, RefreshReason, + strcmp, TalerErrorCode, TalerErrorDetail, TalerProtocolTimestamp, @@ -86,9 +90,11 @@ import { assertUnreachable } from "../util/assertUnreachable.js"; import { AvailableCoinInfo, CoinCandidateSelection, + CoinSelectionTally, PreviousPayCoins, selectForcedPayCoins, - selectPayCoins, + selectPayCoinsLegacy, + tallyFees, } from "../util/coinSelection.js"; import { getHttpResponseErrorDetails, @@ -962,7 +968,7 @@ async function handleInsufficientFunds( } }); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates, contractTermsAmount: contractData.amount, depositFeeLimit: contractData.maxDepositFee, @@ -1019,6 +1025,205 @@ async function unblockBackup( }); } +export interface SelectPayCoinRequestNg { + exchanges: string[]; + auditors: string[]; + wireMethod: string; + contractTermsAmount: AmountJson; + depositFeeLimit: AmountJson; + wireFeeLimit: AmountJson; + wireFeeAmortization: number; + prevPayCoins?: PreviousPayCoins; + requiredMinimumAge?: number; +} + +export type AvailableDenom = DenominationInfo & { + numAvailable: number; +}; + +/** + * 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 ws.db + .mktx((x) => [x.exchanges, x.exchangeDetails, x.denominations]) + .runReadOnly(async (tx) => { + 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 !== contractTermsAmount.currency) { + continue; + } + let accepted = false; + if (req.exchanges.includes(exchange.baseUrl)) { + accepted = true; + } else { + for (const auditor of exchangeDetails.auditors) { + if (req.auditors.includes(auditor.auditor_url)) { + accepted = true; + } + } + } + if (!accepted) { + continue; + } + // FIXME: Do this query more efficiently via indexing + const exchangeDenoms = await tx.denominations.indexes.byExchangeBaseUrl + .iter(exchangeDetails.exchangeBaseUrl) + .filter((x) => x.freshCoinCount != null && x.freshCoinCount > 0); + // FIXME: Should we exclude denominations that are + // not spendable anymore? + for (const denom of exchangeDenoms) { + denoms.push({ + ...DenominationRecord.toDenomInfo(denom), + numAvailable: denom.freshCoinCount ?? 0, + }); + } + } + return [denoms, wfPerExchange]; + }); + + const coinPubs: string[] = []; + const coinContributions: AmountJson[] = []; + const currency = contractTermsAmount.currency; + + let tally: CoinSelectionTally = { + amountPayRemaining: contractTermsAmount, + amountWireFeeLimitRemaining: wireFeeLimit, + amountDepositFeeLimitRemaining: depositFeeLimit, + customerDepositFees: Amounts.getZero(currency), + customerWireFees: Amounts.getZero(currency), + wireFeeCoveredForExchange: new Set(), + }; + + 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); + } + + // Sort by available amount (descending), deposit fee (ascending) and + // denomPub (ascending) if deposit fee is the same + // (to guarantee deterministic results) + candidateDenoms.sort( + (o1, o2) => + -Amounts.cmp(o1.value, o2.value) || + Amounts.cmp(o1.feeDeposit, o2.feeDeposit) || + strcmp(o1.denomPubHash, o2.denomPubHash), + ); + + // 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. + + const selectedDenom: { + [dph: string]: AmountJson[]; + } = {}; + + 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) { + continue; + } + + if (Amounts.isZero(tally.amountPayRemaining)) { + // We have spent enough! + break; + } + + tally = tallyFees( + tally, + wireFeesPerExchange, + wireFeeAmortization, + aci.exchangeBaseUrl, + 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) { + selectedDenom[aci.denomPubHash] = contributions; + } + + if (Amounts.isZero(tally.amountPayRemaining)) { + await ws.db + .mktx((x) => [x.coins, x.denominations]) + .runReadOnly(async (tx) => { + for (const dph of Object.keys(selectedDenom)) { + const contributions = selectedDenom[dph]; + const coins = await tx.coins.indexes.byDenomPubHashAndStatus.getAll( + [dph, CoinStatus.Fresh], + contributions.length, + ); + if (coins.length != contributions.length) { + throw Error( + `coin selection failed (not available anymore, got only ${coins.length}/${contributions.length})`, + ); + } + coinPubs.push(...coins.map((x) => x.coinPub)); + coinContributions.push(...contributions); + } + }); + + return { + paymentAmount: contractTermsAmount, + coinContributions, + coinPubs, + customerDepositFees: tally.customerDepositFees, + customerWireFees: tally.customerWireFees, + }; + } + } + return undefined; +} + export async function checkPaymentByProposalId( ws: InternalWalletState, proposalId: string, @@ -1079,7 +1284,7 @@ export async function checkPaymentByProposalId( wireFeeAmortization: contractData.wireFeeAmortization, wireMethod: contractData.wireMethod, }); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates, contractTermsAmount: contractData.amount, depositFeeLimit: contractData.maxDepositFee, @@ -1408,7 +1613,7 @@ export async function confirmPay( requiredMinimumAge: contractData.minimumAge, }); } else { - res = selectPayCoins({ + res = selectPayCoinsLegacy({ candidates, contractTermsAmount: contractData.amount, depositFeeLimit: contractData.maxDepositFee, diff --git a/packages/taler-wallet-core/src/util/coinSelection.test.ts b/packages/taler-wallet-core/src/util/coinSelection.test.ts index 55c007bbc..3c6ad0d82 100644 --- a/packages/taler-wallet-core/src/util/coinSelection.test.ts +++ b/packages/taler-wallet-core/src/util/coinSelection.test.ts @@ -19,7 +19,7 @@ */ import test from "ava"; import { AmountJson, Amounts, DenomKeyType } from "@gnu-taler/taler-util"; -import { AvailableCoinInfo, selectPayCoins } from "./coinSelection.js"; +import { AvailableCoinInfo, selectPayCoinsLegacy } from "./coinSelection.js"; function a(x: string): AmountJson { const amt = Amounts.parse(x); @@ -66,7 +66,7 @@ test("it should be able to pay if merchant takes the fees", (t) => { ]; acis.forEach((x, i) => (x.coinPub = String(i))); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -94,7 +94,7 @@ test("it should take the last two coins if it pays less fees", (t) => { ]; acis.forEach((x, i) => (x.coinPub = String(i))); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -122,7 +122,7 @@ test("it should take the last coins if the merchant doest not take all the fee", ]; acis.forEach((x, i) => (x.coinPub = String(i))); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -148,7 +148,7 @@ test("it should use 3 coins to cover fees and payment", (t) => { fakeAci("EUR:1.0", "EUR:0.5"), //contributed value .5 ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -174,7 +174,7 @@ test("it should return undefined if there is not enough coins", (t) => { fakeAci("EUR:1.0", "EUR:0.5"), ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -194,7 +194,7 @@ test("it should return undefined if there is not enough coins (taking into accou fakeAci("EUR:1.0", "EUR:0.5"), fakeAci("EUR:1.0", "EUR:0.5"), ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -213,7 +213,7 @@ test("it should not count into customer fee if merchant can afford it", (t) => { fakeAci("EUR:1.0", "EUR:0.1"), fakeAci("EUR:1.0", "EUR:0.1"), ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -240,7 +240,7 @@ test("it should use the coins that spent less relative fee", (t) => { ]; acis.forEach((x, i) => (x.coinPub = String(i))); - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -263,7 +263,7 @@ test("coin selection 9", (t) => { fakeAci("EUR:1.0", "EUR:0.2"), fakeAci("EUR:0.2", "EUR:0.2"), ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, @@ -290,7 +290,7 @@ test("it should be able to use unrestricted coins for age restricted contract", fakeAciWithAgeRestriction("EUR:1.0", "EUR:0.2"), fakeAciWithAgeRestriction("EUR:0.2", "EUR:0.2"), ]; - const res = selectPayCoins({ + const res = selectPayCoinsLegacy({ candidates: { candidateCoins: acis, wireFeesPerExchange: {}, diff --git a/packages/taler-wallet-core/src/util/coinSelection.ts b/packages/taler-wallet-core/src/util/coinSelection.ts index 97e25abd3..9622b3a76 100644 --- a/packages/taler-wallet-core/src/util/coinSelection.ts +++ b/packages/taler-wallet-core/src/util/coinSelection.ts @@ -97,7 +97,7 @@ export interface SelectPayCoinRequest { requiredMinimumAge?: number; } -interface CoinSelectionTally { +export interface CoinSelectionTally { /** * Amount that still needs to be paid. * May increase during the computation when fees need to be covered. @@ -125,7 +125,7 @@ interface CoinSelectionTally { /** * Account for the fees of spending a coin. */ -function tallyFees( +export function tallyFees( tally: CoinSelectionTally, wireFeesPerExchange: Record, wireFeeAmortization: number, @@ -204,7 +204,7 @@ function tallyFees( * * This function is only exported for the sake of unit tests. */ -export function selectPayCoins( +export function selectPayCoinsLegacy( req: SelectPayCoinRequest, ): PayCoinSelection | undefined { const { diff --git a/packages/taler-wallet-core/src/wallet.ts b/packages/taler-wallet-core/src/wallet.ts index 49c7f77cf..4751f7976 100644 --- a/packages/taler-wallet-core/src/wallet.ts +++ b/packages/taler-wallet-core/src/wallet.ts @@ -743,19 +743,9 @@ async function getExchangeDetailedInfo( return; } - const denominations: DenomInfo[] = denominationRecords.map((x) => ({ - denomPub: x.denomPub, - denomPubHash: x.denomPubHash, - feeDeposit: x.fees.feeDeposit, - feeRefresh: x.fees.feeRefresh, - feeRefund: x.fees.feeRefund, - feeWithdraw: x.fees.feeWithdraw, - stampExpireDeposit: x.stampExpireDeposit, - stampExpireLegal: x.stampExpireLegal, - stampExpireWithdraw: x.stampExpireWithdraw, - stampStart: x.stampStart, - value: DenominationRecord.getValue(x), - })); + const denominations: DenomInfo[] = denominationRecords.map((x) => + DenominationRecord.toDenomInfo(x), + ); return { info: { @@ -1591,20 +1581,7 @@ class InternalWalletStateImpl implements InternalWalletState { } const d = await tx.denominations.get([exchangeBaseUrl, denomPubHash]); if (d) { - const denomInfo = { - denomPub: d.denomPub, - denomPubHash: d.denomPubHash, - feeDeposit: d.fees.feeDeposit, - feeRefresh: d.fees.feeRefresh, - feeRefund: d.fees.feeRefund, - feeWithdraw: d.fees.feeWithdraw, - stampExpireDeposit: d.stampExpireDeposit, - stampExpireLegal: d.stampExpireLegal, - stampExpireWithdraw: d.stampExpireWithdraw, - stampStart: d.stampStart, - value: DenominationRecord.getValue(d), - }; - return denomInfo; + return DenominationRecord.toDenomInfo(d); } return undefined; } -- cgit v1.2.3