diff options
Diffstat (limited to 'packages/taler-wallet-core/src/util')
-rw-r--r-- | packages/taler-wallet-core/src/util/coinSelection.test.ts | 322 | ||||
-rw-r--r-- | packages/taler-wallet-core/src/util/coinSelection.ts | 246 |
2 files changed, 0 insertions, 568 deletions
diff --git a/packages/taler-wallet-core/src/util/coinSelection.test.ts b/packages/taler-wallet-core/src/util/coinSelection.test.ts deleted file mode 100644 index fe9672116..000000000 --- a/packages/taler-wallet-core/src/util/coinSelection.test.ts +++ /dev/null @@ -1,322 +0,0 @@ -/* - 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 <http://www.gnu.org/licenses/> - */ - -/** - * Imports. - */ -import test from "ava"; -import { - AgeRestriction, - AmountJson, - Amounts, - DenomKeyType, -} from "@gnu-taler/taler-util"; -import { AvailableCoinInfo, selectPayCoinsLegacy } from "./coinSelection.js"; - -function a(x: string): AmountJson { - const amt = Amounts.parse(x); - if (!amt) { - throw Error("invalid amount"); - } - return amt; -} - -function fakeAci(current: string, feeDeposit: string): AvailableCoinInfo { - return { - value: a(current), - availableAmount: a(current), - coinPub: "foobar", - denomPub: { - cipher: DenomKeyType.Rsa, - rsa_public_key: "foobar", - age_mask: 0, - }, - feeDeposit: a(feeDeposit), - exchangeBaseUrl: "https://example.com/", - maxAge: AgeRestriction.AGE_UNRESTRICTED, - }; -} - -function fakeAciWithAgeRestriction( - current: string, - feeDeposit: string, -): AvailableCoinInfo { - return { - value: a(current), - availableAmount: a(current), - coinPub: "foobar", - denomPub: { - cipher: DenomKeyType.Rsa, - rsa_public_key: "foobar", - age_mask: 2446657, - }, - feeDeposit: a(feeDeposit), - exchangeBaseUrl: "https://example.com/", - maxAge: AgeRestriction.AGE_UNRESTRICTED, - }; -} - -test("it should be able to pay if merchant takes the fees", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.1"), - fakeAci("EUR:1.0", "EUR:0.0"), - ]; - acis.forEach((x, i) => (x.coinPub = String(i))); - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.1"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - - if (!res) { - t.fail(); - return; - } - t.deepEqual(res.coinPubs, ["1", "0"]); - t.pass(); -}); - -test("it should take the last two coins if it pays less fees", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.5"), - fakeAci("EUR:1.0", "EUR:0.0"), - // Merchant covers the fee, this one shouldn't be used - fakeAci("EUR:1.0", "EUR:0.0"), - ]; - acis.forEach((x, i) => (x.coinPub = String(i))); - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.5"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - - if (!res) { - t.fail(); - return; - } - t.deepEqual(res.coinPubs, ["1", "2"]); - t.pass(); -}); - -test("it should take the last coins if the merchant doest not take all the fee", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.5"), - fakeAci("EUR:1.0", "EUR:0.5"), - // this coin should be selected instead of previous one with fee - fakeAci("EUR:1.0", "EUR:0.0"), - ]; - acis.forEach((x, i) => (x.coinPub = String(i))); - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.5"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - - if (!res) { - t.fail(); - return; - } - t.deepEqual(res.coinPubs, ["2", "0"]); - t.pass(); -}); - -test("it should use 3 coins to cover fees and payment", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.5"), //contributed value 1 (fee by the merchant) - fakeAci("EUR:1.0", "EUR:0.5"), //contributed value .5 - fakeAci("EUR:1.0", "EUR:0.5"), //contributed value .5 - ]; - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.5"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - - if (!res) { - t.fail(); - return; - } - t.true(res.coinPubs.length === 3); - t.pass(); -}); - -test("it should return undefined if there is not enough coins", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.5"), - fakeAci("EUR:1.0", "EUR:0.5"), - fakeAci("EUR:1.0", "EUR:0.5"), - ]; - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:4.0"), - depositFeeLimit: a("EUR:0.2"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - - t.true(!res); - t.pass(); -}); - -test("it should return undefined if there is not enough coins (taking into account fees)", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.5"), - fakeAci("EUR:1.0", "EUR:0.5"), - ]; - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.2"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - t.true(!res); - t.pass(); -}); - -test("it should not count into customer fee if merchant can afford it", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.1"), - fakeAci("EUR:1.0", "EUR:0.1"), - ]; - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:2.0"), - depositFeeLimit: a("EUR:0.2"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - t.truthy(res); - t.true(Amounts.cmp(res!.customerDepositFees, "EUR:0.0") === 0); - t.true( - Amounts.cmp(Amounts.sum(res!.coinContributions).amount, "EUR:2.0") === 0, - ); - t.pass(); -}); - -test("it should use the coins that spent less relative fee", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.2"), - fakeAci("EUR:0.1", "EUR:0.2"), - fakeAci("EUR:0.05", "EUR:0.05"), - fakeAci("EUR:0.05", "EUR:0.05"), - ]; - acis.forEach((x, i) => (x.coinPub = String(i))); - - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:1.1"), - depositFeeLimit: a("EUR:0.4"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - if (!res) { - t.fail(); - return; - } - t.deepEqual(res.coinPubs, ["0", "2", "3"]); - t.pass(); -}); - -test("coin selection 9", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAci("EUR:1.0", "EUR:0.2"), - fakeAci("EUR:0.2", "EUR:0.2"), - ]; - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:1.2"), - depositFeeLimit: a("EUR:0.4"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - }); - if (!res) { - t.fail(); - return; - } - t.true(res.coinContributions.length === 2); - t.true( - Amounts.cmp(Amounts.sum(res.coinContributions).amount, "EUR:1.2") === 0, - ); - t.pass(); -}); - -test("it should be able to use unrestricted coins for age restricted contract", (t) => { - const acis: AvailableCoinInfo[] = [ - fakeAciWithAgeRestriction("EUR:1.0", "EUR:0.2"), - fakeAciWithAgeRestriction("EUR:0.2", "EUR:0.2"), - ]; - const res = selectPayCoinsLegacy({ - candidates: { - candidateCoins: acis, - wireFeesPerExchange: {}, - }, - contractTermsAmount: a("EUR:1.2"), - depositFeeLimit: a("EUR:0.4"), - wireFeeLimit: a("EUR:0"), - wireFeeAmortization: 1, - requiredMinimumAge: 13, - }); - if (!res) { - t.fail(); - return; - } - t.true(res.coinContributions.length === 2); - t.true( - Amounts.cmp(Amounts.sum(res.coinContributions).amount, "EUR:1.2") === 0, - ); - t.pass(); -}); diff --git a/packages/taler-wallet-core/src/util/coinSelection.ts b/packages/taler-wallet-core/src/util/coinSelection.ts index d2f12baf5..12f87a920 100644 --- a/packages/taler-wallet-core/src/util/coinSelection.ts +++ b/packages/taler-wallet-core/src/util/coinSelection.ts @@ -25,15 +25,11 @@ */ import { AgeCommitmentProof, - AgeRestriction, AmountJson, Amounts, DenominationPubKey, - ForcedCoinSel, Logger, - PayCoinSelection, } from "@gnu-taler/taler-util"; -import { checkLogicInvariant } from "./invariants.js"; const logger = new Logger("coinSelection.ts"); @@ -194,245 +190,3 @@ export function tallyFees( wireFeeCoveredForExchange, }; } - -/** - * 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 function selectPayCoinsLegacy( - req: SelectPayCoinRequest, -): PayCoinSelection | undefined { - const { - candidates, - contractTermsAmount, - depositFeeLimit, - wireFeeLimit, - wireFeeAmortization, - } = req; - - if (candidates.candidateCoins.length === 0) { - return undefined; - } - 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, - candidates.wireFeesPerExchange, - wireFeeAmortization, - prev.exchangeBaseUrl, - prev.feeDeposit, - ); - tally.amountPayRemaining = Amounts.sub( - tally.amountPayRemaining, - prev.contribution, - ).amount; - - coinPubs.push(prev.coinPub); - coinContributions.push(prev.contribution); - } - - const prevCoinPubs = new Set(prevPayCoins.map((x) => x.coinPub)); - - // Sort by available amount (descending), deposit fee (ascending) and - // denomPub (ascending) if deposit fee is the same - // (to guarantee deterministic results) - const candidateCoins = [...candidates.candidateCoins].sort( - (o1, o2) => - -Amounts.cmp(o1.availableAmount, o2.availableAmount) || - Amounts.cmp(o1.feeDeposit, o2.feeDeposit) || - DenominationPubKey.cmp(o1.denomPub, o2.denomPub), - ); - - // 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. - - for (const aci of candidateCoins) { - // 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.availableAmount) > 0) { - continue; - } - - if (Amounts.isZero(tally.amountPayRemaining)) { - // We have spent enough! - break; - } - - // The same coin can't contribute twice to the same payment, - // by a fundamental, intentional limitation of the protocol. - if (prevCoinPubs.has(aci.coinPub)) { - continue; - } - - if (req.requiredMinimumAge != null) { - const index = AgeRestriction.getAgeGroupIndex( - aci.denomPub.age_mask, - req.requiredMinimumAge, - ); - // if (!aci.ageCommitmentProof) { - // // No age restriction, can't use for this payment - // continue; - // } - if ( - aci.ageCommitmentProof && - aci.ageCommitmentProof.proof.privateKeys.length < index - ) { - // Available age proofs to low, can't use for this payment - continue; - } - } - - tally = tallyFees( - tally, - candidates.wireFeesPerExchange, - wireFeeAmortization, - aci.exchangeBaseUrl, - aci.feeDeposit, - ); - - let coinSpend = Amounts.max( - Amounts.min(tally.amountPayRemaining, aci.availableAmount), - aci.feeDeposit, - ); - - tally.amountPayRemaining = Amounts.sub( - tally.amountPayRemaining, - coinSpend, - ).amount; - coinPubs.push(aci.coinPub); - coinContributions.push(coinSpend); - } - - if (Amounts.isZero(tally.amountPayRemaining)) { - return { - paymentAmount: contractTermsAmount, - coinContributions, - coinPubs, - customerDepositFees: tally.customerDepositFees, - customerWireFees: tally.customerWireFees, - }; - } - return undefined; -} - -export function selectForcedPayCoins( - forcedCoinSel: ForcedCoinSel, - req: SelectPayCoinRequest, -): PayCoinSelection | undefined { - const { - candidates, - contractTermsAmount, - depositFeeLimit, - wireFeeLimit, - wireFeeAmortization, - } = req; - - if (candidates.candidateCoins.length === 0) { - return undefined; - } - 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(), - }; - - // Not supported by forced coin selection - checkLogicInvariant(!req.prevPayCoins); - - // Sort by available amount (descending), deposit fee (ascending) and - // denomPub (ascending) if deposit fee is the same - // (to guarantee deterministic results) - const candidateCoins = [...candidates.candidateCoins].sort( - (o1, o2) => - -Amounts.cmp(o1.availableAmount, o2.availableAmount) || - Amounts.cmp(o1.feeDeposit, o2.feeDeposit) || - DenominationPubKey.cmp(o1.denomPub, o2.denomPub), - ); - - // 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. - - // Set of spent coin indices from candidate coins - const spentSet: Set<number> = new Set(); - - for (const forcedCoin of forcedCoinSel.coins) { - let aci: AvailableCoinInfo | undefined = undefined; - for (let i = 0; i < candidateCoins.length; i++) { - if (spentSet.has(i)) { - continue; - } - if ( - Amounts.cmp(forcedCoin.value, candidateCoins[i].availableAmount) != 0 - ) { - continue; - } - spentSet.add(i); - aci = candidateCoins[i]; - break; - } - - if (!aci) { - throw Error("can't find coin for forced coin selection"); - } - - tally = tallyFees( - tally, - candidates.wireFeesPerExchange, - wireFeeAmortization, - aci.exchangeBaseUrl, - aci.feeDeposit, - ); - - let coinSpend = Amounts.parseOrThrow(forcedCoin.contribution); - - tally.amountPayRemaining = Amounts.sub( - tally.amountPayRemaining, - coinSpend, - ).amount; - coinPubs.push(aci.coinPub); - coinContributions.push(coinSpend); - } - - if (Amounts.isZero(tally.amountPayRemaining)) { - return { - paymentAmount: contractTermsAmount, - coinContributions, - coinPubs, - customerDepositFees: tally.customerDepositFees, - customerWireFees: tally.customerWireFees, - }; - } - return undefined; -} |