wallet-core: do p2p coin selection based on coin availability records

2 files changed, 231 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;
       }
diff --git a/packages/taler-wallet-core/src/util/query.ts b/packages/taler-wallet-core/src/util/query.ts
index 527cbdf63..71f80f8aa 100644
--- a/packages/taler-wallet-core/src/util/query.ts
+++ b/packages/taler-wallet-core/src/util/query.ts
@@ -429,6 +429,46 @@ export type GetReadOnlyAccess<BoundStores> = {
     : unknown;
 };
 
+export type StoreNames<StoreMap> = StoreMap extends {
+  [P in keyof StoreMap]: StoreWithIndexes<infer SN1, infer SD1, infer IM1>;
+}
+  ? keyof StoreMap
+  : unknown;
+
+export type DbReadOnlyTransaction<
+  StoreMap,
+  Stores extends StoreNames<StoreMap> & string,
+> = StoreMap extends {
+  [P in Stores]: StoreWithIndexes<infer SN1, infer SD1, infer IM1>;
+}
+  ? {
+      [P in Stores]: StoreMap[P] extends StoreWithIndexes<
+        infer SN,
+        infer SD,
+        infer IM
+      >
+        ? StoreReadOnlyAccessor<GetRecordType<SD>, IM>
+        : unknown;
+    }
+  : unknown;
+
+export type DbReadWriteTransaction<
+  StoreMap,
+  Stores extends StoreNames<StoreMap> & string,
+> = StoreMap extends {
+  [P in Stores]: StoreWithIndexes<infer SN1, infer SD1, infer IM1>;
+}
+  ? {
+      [P in Stores]: StoreMap[P] extends StoreWithIndexes<
+        infer SN,
+        infer SD,
+        infer IM
+      >
+        ? StoreReadWriteAccessor<GetRecordType<SD>, IM>
+        : unknown;
+    }
+  : unknown;
+
 export type GetReadWriteAccess<BoundStores> = {
   [P in keyof BoundStores]: BoundStores[P] extends StoreWithIndexes<
     infer SN,