diff options
Diffstat (limited to 'packages/taler-wallet-core/src/util/coinSelection.ts')
-rw-r--r-- | packages/taler-wallet-core/src/util/coinSelection.ts | 294 |
1 files changed, 191 insertions, 103 deletions
diff --git a/packages/taler-wallet-core/src/util/coinSelection.ts b/packages/taler-wallet-core/src/util/coinSelection.ts index bb901fd75..39f667496 100644 --- a/packages/taler-wallet-core/src/util/coinSelection.ts +++ b/packages/taler-wallet-core/src/util/coinSelection.ts @@ -29,6 +29,7 @@ import { AgeCommitmentProof, AgeRestriction, AmountJson, + AmountLike, AmountResponse, Amounts, AmountString, @@ -58,7 +59,16 @@ import { AllowedExchangeInfo, DenominationRecord, } from "../db.js"; -import { getExchangeDetails, isWithdrawableDenom } from "../index.js"; +import { + DbReadOnlyTransaction, + getExchangeDetails, + GetReadOnlyAccess, + GetReadWriteAccess, + isWithdrawableDenom, + StoreNames, + WalletDbReadOnlyTransaction, + WalletStoresV1, +} from "../index.js"; import { InternalWalletState } from "../internal-wallet-state.js"; import { getMerchantPaymentBalanceDetails, @@ -257,10 +267,9 @@ export async function selectPayCoinsNew( wireFeeAmortization, } = req; - const [candidateDenoms, wireFeesPerExchange] = await selectPayMerchantCandidates( - ws, - req, - ); + // FIXME: Why don't we do this in a transaction? + const [candidateDenoms, wireFeesPerExchange] = + await selectPayMerchantCandidates(ws, req); const coinPubs: string[] = []; const coinContributions: AmountJson[] = []; @@ -619,7 +628,7 @@ async function selectPayMerchantCandidates( if (!accepted) { continue; } - //4.- filter coins restricted by age + // 4.- filter coins restricted by age let ageLower = 0; let ageUpper = AgeRestriction.AGE_UNRESTRICTED; if (req.requiredMinimumAge) { @@ -636,7 +645,7 @@ async function selectPayMerchantCandidates( ], ), ); - //5.- save denoms with how many coins are available + // 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? @@ -813,7 +822,6 @@ export interface CoinInfo { maxAge: number; } - export interface SelectedPeerCoin { coinPub: string; coinPriv: string; @@ -837,33 +845,6 @@ export interface PeerCoinSelectionDetails { depositFees: AmountJson; } -/** - * Information about a selected coin for peer to peer payments. - */ -export interface PeerCoinInfo { - /** - * Public key of the coin. - */ - coinPub: string; - - coinPriv: string; - - /** - * Deposit fee for the coin. - */ - feeDeposit: AmountJson; - - value: AmountJson; - - denomPubHash: string; - - denomSig: UnblindedSignature; - - maxAge: number; - - ageCommitmentProof?: AgeCommitmentProof; -} - export type SelectPeerCoinsResult = | { type: "success"; result: PeerCoinSelectionDetails } | { @@ -887,6 +868,119 @@ export interface PeerCoinSelectionRequest { repair?: PeerCoinRepair; } +/** + * Get coin availability information for a certain exchange. + */ +async function selectPayPeerCandidatesForExchange( + ws: InternalWalletState, + tx: WalletDbReadOnlyTransaction<"coinAvailability" | "denominations">, + exchangeBaseUrl: string, +): Promise<AvailableDenom[]> { + 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; +} + +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; + const coinSpend = Amounts.max( + Amounts.min(amountPayRemaining, denom.value), + denom.feeDeposit, + ); + tally.amountAcc = Amounts.add(tally.amountAcc, coinSpend).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, + }; + } + 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, @@ -915,42 +1009,16 @@ export async function selectPeerCoins( if (exch.detailsPointer?.currency !== currency) { continue; } - // FIXME: Can't we do this faster by using coinAvailability? - const coins = ( - await tx.coins.indexes.byBaseUrl.getAll(exch.baseUrl) - ).filter((x) => x.status === CoinStatus.Fresh); - const coinInfos: PeerCoinInfo[] = []; - for (const coin of coins) { - const denom = await ws.getDenomInfo( - ws, - tx, - coin.exchangeBaseUrl, - coin.denomPubHash, - ); - if (!denom) { - throw Error("denom not found"); - } - coinInfos.push({ - coinPub: coin.coinPub, - feeDeposit: Amounts.parseOrThrow(denom.feeDeposit), - value: Amounts.parseOrThrow(denom.value), - denomPubHash: denom.denomPubHash, - coinPriv: coin.coinPriv, - denomSig: coin.denomSig, - maxAge: coin.maxAge, - ageCommitmentProof: coin.ageCommitmentProof, - }); - } - if (coinInfos.length === 0) { - continue; - } - coinInfos.sort( - (o1, o2) => - -Amounts.cmp(o1.value, o2.value) || - strcmp(o1.denomPubHash, o2.denomPubHash), + const candidates = await selectPayPeerCandidatesForExchange( + ws, + tx, + exch.baseUrl, ); - let amountAcc = Amounts.zeroOfCurrency(currency); - let depositFeesAcc = Amounts.zeroOfCurrency(currency); + const tally: PeerCoinSelectionTally = { + amountAcc: Amounts.zeroOfCurrency(currency), + depositFeesAcc: Amounts.zeroOfCurrency(currency), + lastDepositFee: Amounts.zeroOfCurrency(currency), + }; const resCoins: { coinPub: string; coinPriv: string; @@ -959,9 +1027,8 @@ export async function selectPeerCoins( denomSig: UnblindedSignature; ageCommitmentProof: AgeCommitmentProof | undefined; }[] = []; - let lastDepositFee = Amounts.zeroOfCurrency(currency); - if (req.repair) { + 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]); @@ -984,49 +1051,70 @@ export async function selectPeerCoins( ageCommitmentProof: coin.ageCommitmentProof, }); const depositFee = Amounts.parseOrThrow(denom.feeDeposit); - lastDepositFee = depositFee; - amountAcc = Amounts.add( - amountAcc, + tally.lastDepositFee = depositFee; + tally.amountAcc = Amounts.add( + tally.amountAcc, Amounts.sub(contrib, depositFee).amount, ).amount; - depositFeesAcc = Amounts.add(depositFeesAcc, depositFee).amount; + tally.depositFeesAcc = Amounts.add( + tally.depositFeesAcc, + depositFee, + ).amount; } } - for (const coin of coinInfos) { - if (Amounts.cmp(amountAcc, instructedAmount) >= 0) { - break; + const selectedDenom = greedySelectPeer( + candidates, + instructedAmount, + tally, + ); + + if (selectedDenom) { + for (const dph of Object.keys(selectedDenom)) { + const selInfo = selectedDenom[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})`, + ); + } + 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 gap = Amounts.add( - coin.feeDeposit, - Amounts.sub(instructedAmount, amountAcc).amount, - ).amount; - const contrib = Amounts.min(gap, coin.value); - amountAcc = Amounts.add( - amountAcc, - Amounts.sub(contrib, coin.feeDeposit).amount, - ).amount; - depositFeesAcc = Amounts.add(depositFeesAcc, coin.feeDeposit).amount; - resCoins.push({ - coinPriv: coin.coinPriv, - coinPub: coin.coinPub, - contribution: Amounts.stringify(contrib), - denomPubHash: coin.denomPubHash, - denomSig: coin.denomSig, - ageCommitmentProof: coin.ageCommitmentProof, - }); - lastDepositFee = coin.feeDeposit; - } - if (Amounts.cmp(amountAcc, instructedAmount) >= 0) { + const res: PeerCoinSelectionDetails = { exchangeBaseUrl: exch.baseUrl, coins: resCoins, - depositFees: depositFeesAcc, + depositFees: tally.depositFeesAcc, }; return { type: "success", result: res }; } - const diff = Amounts.sub(instructedAmount, amountAcc).amount; - exchangeFeeGap[exch.baseUrl] = Amounts.add(lastDepositFee, diff).amount; + + const diff = Amounts.sub(instructedAmount, tally.amountAcc).amount; + exchangeFeeGap[exch.baseUrl] = Amounts.add( + tally.lastDepositFee, + diff, + ).amount; continue; } |