make planchet management during withdrawal O(n) instead of O(n^2)

13 files changed, 409 insertions, 247 deletions

diff --git a/src/crypto/workers/cryptoApi.ts b/src/crypto/workers/cryptoApi.ts
index a6f9d162d..14964e4d8 100644
--- a/src/crypto/workers/cryptoApi.ts
+++ b/src/crypto/workers/cryptoApi.ts
@@ -30,6 +30,7 @@ import {
   RefreshSessionRecord,
   TipPlanchet,
   WireFee,
+  DenominationSelectionInfo,
 } from "../../types/dbTypes";
 
 import { CryptoWorker } from "./cryptoWorker";
@@ -435,7 +436,7 @@ export class CryptoApi {
     exchangeBaseUrl: string,
     kappa: number,
     meltCoin: CoinRecord,
-    newCoinDenoms: DenominationRecord[],
+    newCoinDenoms: DenominationSelectionInfo,
     meltFee: AmountJson,
   ): Promise<RefreshSessionRecord> {
     return this.doRpc<RefreshSessionRecord>(
diff --git a/src/crypto/workers/cryptoImplementation.ts b/src/crypto/workers/cryptoImplementation.ts
index de3b88bb8..dc0452dc1 100644
--- a/src/crypto/workers/cryptoImplementation.ts
+++ b/src/crypto/workers/cryptoImplementation.ts
@@ -34,6 +34,7 @@ import {
   TipPlanchet,
   WireFee,
   CoinSourceType,
+  DenominationSelectionInfo,
 } from "../../types/dbTypes";
 
 import { CoinDepositPermission, RecoupRequest } from "../../types/talerTypes";
@@ -359,14 +360,15 @@ export class CryptoImplementation {
     exchangeBaseUrl: string,
     kappa: number,
     meltCoin: CoinRecord,
-    newCoinDenoms: DenominationRecord[],
+    newCoinDenoms: DenominationSelectionInfo,
     meltFee: AmountJson,
   ): RefreshSessionRecord {
-    let valueWithFee = Amounts.getZero(newCoinDenoms[0].value.currency);
+    const currency = newCoinDenoms.selectedDenoms[0].denom.value.currency;
+    let valueWithFee = Amounts.getZero(currency);
 
-    for (const ncd of newCoinDenoms) {
-      valueWithFee = Amounts.add(valueWithFee, ncd.value, ncd.feeWithdraw)
-        .amount;
+    for (const ncd of newCoinDenoms.selectedDenoms) {
+      const t = Amounts.add(ncd.denom.value, ncd.denom.feeWithdraw).amount;
+      valueWithFee = Amounts.add(valueWithFee, Amounts.mult(t, ncd.count).amount).amount;
     }
 
     // melt fee
@@ -386,9 +388,11 @@ export class CryptoImplementation {
       transferPubs.push(encodeCrock(transferKeyPair.ecdhePub));
     }
 
-    for (const denom of newCoinDenoms) {
-      const r = decodeCrock(denom.denomPub);
-      sessionHc.update(r);
+    for (const denomSel of newCoinDenoms.selectedDenoms) {
+      for (let i = 0; i < denomSel.count; i++) {
+        const r = decodeCrock(denomSel.denom.denomPub);
+        sessionHc.update(r);
+      }
     }
 
     sessionHc.update(decodeCrock(meltCoin.coinPub));
@@ -396,27 +400,29 @@ export class CryptoImplementation {
 
     for (let i = 0; i < kappa; i++) {
       const planchets: RefreshPlanchetRecord[] = [];
-      for (let j = 0; j < newCoinDenoms.length; j++) {
-        const transferPriv = decodeCrock(transferPrivs[i]);
-        const oldCoinPub = decodeCrock(meltCoin.coinPub);
-        const transferSecret = keyExchangeEcdheEddsa(transferPriv, oldCoinPub);
-
-        const fresh = setupRefreshPlanchet(transferSecret, j);
-
-        const coinPriv = fresh.coinPriv;
-        const coinPub = fresh.coinPub;
-        const blindingFactor = fresh.bks;
-        const pubHash = hash(coinPub);
-        const denomPub = decodeCrock(newCoinDenoms[j].denomPub);
-        const ev = rsaBlind(pubHash, blindingFactor, denomPub);
-        const planchet: RefreshPlanchetRecord = {
-          blindingKey: encodeCrock(blindingFactor),
-          coinEv: encodeCrock(ev),
-          privateKey: encodeCrock(coinPriv),
-          publicKey: encodeCrock(coinPub),
-        };
-        planchets.push(planchet);
-        sessionHc.update(ev);
+      for (let j = 0; j < newCoinDenoms.selectedDenoms.length; j++) {
+        const denomSel = newCoinDenoms.selectedDenoms[j];
+        for (let k = 0; k < denomSel.count; k++) {
+          const coinNumber = planchets.length;
+          const transferPriv = decodeCrock(transferPrivs[i]);
+          const oldCoinPub = decodeCrock(meltCoin.coinPub);
+          const transferSecret = keyExchangeEcdheEddsa(transferPriv, oldCoinPub);
+          const fresh = setupRefreshPlanchet(transferSecret, coinNumber);
+          const coinPriv = fresh.coinPriv;
+          const coinPub = fresh.coinPub;
+          const blindingFactor = fresh.bks;
+          const pubHash = hash(coinPub);
+          const denomPub = decodeCrock(denomSel.denom.denomPub);
+          const ev = rsaBlind(pubHash, blindingFactor, denomPub);
+          const planchet: RefreshPlanchetRecord = {
+            blindingKey: encodeCrock(blindingFactor),
+            coinEv: encodeCrock(ev),
+            privateKey: encodeCrock(coinPriv),
+            publicKey: encodeCrock(coinPub),
+          };
+          planchets.push(planchet);
+          sessionHc.update(ev);
+        }
       }
       planchetsForGammas.push(planchets);
     }
@@ -432,9 +438,23 @@ export class CryptoImplementation {
 
     const confirmSig = eddsaSign(confirmData, decodeCrock(meltCoin.coinPriv));
 
-    let valueOutput = Amounts.getZero(newCoinDenoms[0].value.currency);
-    for (const denom of newCoinDenoms) {
-      valueOutput = Amounts.add(valueOutput, denom.value).amount;
+    let valueOutput = Amounts.getZero(currency);
+    for (const denomSel of newCoinDenoms.selectedDenoms) {
+      const denom = denomSel.denom;
+      for (let i = 0; i < denomSel.count; i++) {
+        valueOutput = Amounts.add(valueOutput, denom.value).amount;
+      }
+    }
+
+    const newDenoms: string[] = [];
+    const newDenomHashes: string[] = [];
+
+    for (const denomSel of newCoinDenoms.selectedDenoms) {
+      const denom = denomSel.denom;
+      for (let i = 0; i < denomSel.count; i++) {
+        newDenoms.push(denom.denomPub);
+        newDenomHashes.push(denom.denomPubHash);
+      }
     }
 
     const refreshSession: RefreshSessionRecord = {
@@ -442,8 +462,8 @@ export class CryptoImplementation {
       exchangeBaseUrl,
       hash: encodeCrock(sessionHash),
       meltCoinPub: meltCoin.coinPub,
-      newDenomHashes: newCoinDenoms.map((d) => d.denomPubHash),
-      newDenoms: newCoinDenoms.map((d) => d.denomPub),
+      newDenomHashes,
+      newDenoms,
       norevealIndex: undefined,
       planchetsForGammas: planchetsForGammas,
       transferPrivs,
diff --git a/src/operations/balance.ts b/src/operations/balance.ts
index c369af193..b5c1ec79e 100644
--- a/src/operations/balance.ts
+++ b/src/operations/balance.ts
@@ -106,18 +106,19 @@ export async function getBalancesInsideTransaction(
     }
   });
 
-  await tx.iter(Stores.withdrawalGroups).forEach((wds) => {
-    let w = wds.totalCoinValue;
-    for (let i = 0; i < wds.planchets.length; i++) {
-      if (wds.withdrawn[i]) {
-        const p = wds.planchets[i];
-        if (p) {
-          w = Amounts.sub(w, p.coinValue).amount;
-        }
-      }
-    }
-    addTo(balanceStore, "pendingIncoming", w, wds.exchangeBaseUrl);
-  });
+  // FIXME: re-implement
+  // await tx.iter(Stores.withdrawalGroups).forEach((wds) => {
+  //   let w = wds.totalCoinValue;
+  //   for (let i = 0; i < wds.planchets.length; i++) {
+  //     if (wds.withdrawn[i]) {
+  //       const p = wds.planchets[i];
+  //       if (p) {
+  //         w = Amounts.sub(w, p.coinValue).amount;
+  //       }
+  //     }
+  //   }
+  //   addTo(balanceStore, "pendingIncoming", w, wds.exchangeBaseUrl);
+  // });
 
   await tx.iter(Stores.purchases).forEach((t) => {
     if (t.timestampFirstSuccessfulPay) {
diff --git a/src/operations/history.ts b/src/operations/history.ts
index f32dbbe2d..669a6cf85 100644
--- a/src/operations/history.ts
+++ b/src/operations/history.ts
@@ -22,7 +22,6 @@ import {
   Stores,
   ProposalStatus,
   ProposalRecord,
-  PlanchetRecord,
 } from "../types/dbTypes";
 import { Amounts } from "../util/amounts";
 import { AmountJson } from "../util/amounts";
@@ -34,7 +33,6 @@ import {
   ReserveType,
   ReserveCreationDetail,
   VerbosePayCoinDetails,
-  VerboseWithdrawDetails,
   VerboseRefreshDetails,
 } from "../types/history";
 import { assertUnreachable } from "../util/assertUnreachable";
@@ -177,6 +175,7 @@ export async function getHistory(
       Stores.tips,
       Stores.withdrawalGroups,
       Stores.payEvents,
+      Stores.planchets,
       Stores.refundEvents,
       Stores.reserveUpdatedEvents,
       Stores.recoupGroups,
@@ -209,23 +208,6 @@ export async function getHistory(
 
       tx.iter(Stores.withdrawalGroups).forEach((wsr) => {
         if (wsr.timestampFinish) {
-          const cs: PlanchetRecord[] = [];
-          wsr.planchets.forEach((x) => {
-            if (x) {
-              cs.push(x);
-            }
-          });
-
-          let verboseDetails: VerboseWithdrawDetails | undefined = undefined;
-          if (historyQuery?.extraDebug) {
-            verboseDetails = {
-              coins: cs.map((x) => ({
-                value: Amounts.stringify(x.coinValue),
-                denomPub: x.denomPub,
-              })),
-            };
-          }
-
           history.push({
             type: HistoryEventType.Withdrawn,
             withdrawalGroupId: wsr.withdrawalGroupId,
@@ -233,12 +215,12 @@ export async function getHistory(
               HistoryEventType.Withdrawn,
               wsr.withdrawalGroupId,
             ),
-            amountWithdrawnEffective: Amounts.stringify(wsr.totalCoinValue),
+            amountWithdrawnEffective: Amounts.stringify(wsr.denomsSel.totalCoinValue),
             amountWithdrawnRaw: Amounts.stringify(wsr.rawWithdrawalAmount),
             exchangeBaseUrl: wsr.exchangeBaseUrl,
             timestamp: wsr.timestampFinish,
             withdrawalSource: wsr.source,
-            verboseDetails,
+            verboseDetails: undefined,
           });
         }
       });
diff --git a/src/operations/pending.ts b/src/operations/pending.ts
index a797763bf..14072633c 100644
--- a/src/operations/pending.ts
+++ b/src/operations/pending.ts
@@ -246,7 +246,7 @@ async function gatherWithdrawalPending(
   resp: PendingOperationsResponse,
   onlyDue = false,
 ): Promise<void> {
-  await tx.iter(Stores.withdrawalGroups).forEach((wsr) => {
+  await tx.iter(Stores.withdrawalGroups).forEachAsync(async (wsr) => {
     if (wsr.timestampFinish) {
       return;
     }
@@ -258,11 +258,14 @@ async function gatherWithdrawalPending(
     if (onlyDue && wsr.retryInfo.nextRetry.t_ms > now.t_ms) {
       return;
     }
-    const numCoinsWithdrawn = wsr.withdrawn.reduce(
-      (a, x) => a + (x ? 1 : 0),
-      0,
-    );
-    const numCoinsTotal = wsr.withdrawn.length;
+    let numCoinsWithdrawn = 0;
+    let numCoinsTotal = 0;
+    await tx.iterIndexed(Stores.planchets.byGroup, wsr.withdrawalGroupId).forEach((x) => {
+      numCoinsTotal++;
+      if (x.withdrawalDone) {
+        numCoinsWithdrawn++;
+      }
+    });
     resp.pendingOperations.push({
       type: PendingOperationType.Withdraw,
       givesLifeness: true,
@@ -443,6 +446,7 @@ export async function getPendingOperations(
       Stores.tips,
       Stores.purchases,
       Stores.recoupGroups,
+      Stores.planchets,
     ],
     async (tx) => {
       const walletBalance = await getBalancesInsideTransaction(ws, tx);
diff --git a/src/operations/refresh.ts b/src/operations/refresh.ts
index 924769334..56d18f28b 100644
--- a/src/operations/refresh.ts
+++ b/src/operations/refresh.ts
@@ -67,7 +67,9 @@ export function getTotalRefreshCost(
   const withdrawDenoms = getWithdrawDenomList(withdrawAmount, denoms);
   const resultingAmount = Amounts.add(
     Amounts.getZero(withdrawAmount.currency),
-    ...withdrawDenoms.map((d) => d.value),
+    ...withdrawDenoms.selectedDenoms.map(
+      (d) => Amounts.mult(d.denom.value, d.count).amount,
+    ),
   ).amount;
   const totalCost = Amounts.sub(amountLeft, resultingAmount).amount;
   logger.trace(
@@ -130,7 +132,7 @@ async function refreshCreateSession(
 
   const newCoinDenoms = getWithdrawDenomList(availableAmount, availableDenoms);
 
-  if (newCoinDenoms.length === 0) {
+  if (newCoinDenoms.selectedDenoms.length === 0) {
     logger.trace(
       `not refreshing, available amount ${amountToPretty(
         availableAmount,
diff --git a/src/operations/reserves.ts b/src/operations/reserves.ts
index 153ad6b88..f6671d48f 100644
--- a/src/operations/reserves.ts
+++ b/src/operations/reserves.ts
@@ -33,7 +33,6 @@ import {
   updateRetryInfoTimeout,
   ReserveUpdatedEventRecord,
   WalletReserveHistoryItemType,
-  DenominationRecord,
   PlanchetRecord,
   WithdrawalSourceType,
 } from "../types/dbTypes";
@@ -593,33 +592,6 @@ export async function confirmReserve(
   });
 }
 
-async function makePlanchet(
-  ws: InternalWalletState,
-  reserve: ReserveRecord,
-  denom: DenominationRecord,
-): Promise<PlanchetRecord> {
-  const r = await ws.cryptoApi.createPlanchet({
-    denomPub: denom.denomPub,
-    feeWithdraw: denom.feeWithdraw,
-    reservePriv: reserve.reservePriv,
-    reservePub: reserve.reservePub,
-    value: denom.value,
-  });
-  return {
-    blindingKey: r.blindingKey,
-    coinEv: r.coinEv,
-    coinPriv: r.coinPriv,
-    coinPub: r.coinPub,
-    coinValue: r.coinValue,
-    denomPub: r.denomPub,
-    denomPubHash: r.denomPubHash,
-    isFromTip: false,
-    reservePub: r.reservePub,
-    withdrawSig: r.withdrawSig,
-    coinEvHash: r.coinEvHash,
-  };
-}
-
 /**
  * Withdraw coins from a reserve until it is empty.
  *
@@ -654,7 +626,7 @@ async function depleteReserve(
     withdrawAmount,
   );
   logger.trace(`got denom list`);
-  if (denomsForWithdraw.length === 0) {
+  if (!denomsForWithdraw) {
     // Only complain about inability to withdraw if we
     // didn't withdraw before.
     if (Amounts.isZero(summary.withdrawnAmount)) {
@@ -675,15 +647,42 @@ async function depleteReserve(
 
   const withdrawalGroupId = encodeCrock(randomBytes(32));
 
-  const totalCoinValue = Amounts.sum(denomsForWithdraw.map((x) => x.value))
-    .amount;
-
   const planchets: PlanchetRecord[] = [];
-  for (const d of denomsForWithdraw) {
-    const p = await makePlanchet(ws, reserve, d);
-    planchets.push(p);
+  let coinIdx = 0;
+  for (let i = 0; i < denomsForWithdraw.selectedDenoms.length; i++) {
+    const d = denomsForWithdraw.selectedDenoms[i];
+    const denom = d.denom;
+    for (let j = 0; j < d.count; j++) {
+      const r = await ws.cryptoApi.createPlanchet({
+        denomPub: denom.denomPub,
+        feeWithdraw: denom.feeWithdraw,
+        reservePriv: reserve.reservePriv,
+        reservePub: reserve.reservePub,
+        value: denom.value,
+      });
+      const planchet: PlanchetRecord = {
+        blindingKey: r.blindingKey,
+        coinEv: r.coinEv,
+        coinEvHash: r.coinEvHash,
+        coinIdx,
+        coinPriv: r.coinPriv,
+        coinPub: r.coinPub,
+        coinValue: r.coinValue,
+        denomPub: r.denomPub,
+        denomPubHash: r.denomPubHash,
+        isFromTip: false,
+        reservePub: r.reservePub,
+        withdrawalDone: false,
+        withdrawSig: r.withdrawSig,
+        withdrawalGroupId: withdrawalGroupId,
+      };
+      planchets.push(planchet);
+      coinIdx++;
+    }
   }
 
+  logger.trace("created plachets");
+
   const withdrawalRecord: WithdrawalGroupRecord = {
     withdrawalGroupId: withdrawalGroupId,
     exchangeBaseUrl: reserve.exchangeBaseUrl,
@@ -693,23 +692,24 @@ async function depleteReserve(
     },
     rawWithdrawalAmount: withdrawAmount,
     timestampStart: getTimestampNow(),
-    denoms: denomsForWithdraw.map((x) => x.denomPub),
-    withdrawn: denomsForWithdraw.map((x) => false),
-    planchets,
-    totalCoinValue,
     retryInfo: initRetryInfo(),
     lastErrorPerCoin: {},
     lastError: undefined,
+    denomsSel: {
+      totalCoinValue: denomsForWithdraw.totalCoinValue,
+      totalWithdrawCost: denomsForWithdraw.totalWithdrawCost,
+      selectedDenoms: denomsForWithdraw.selectedDenoms.map((x) => {
+        return {
+          countAllocated: x.count,
+          countPlanchetCreated: x.count,
+          denomPubHash: x.denom.denomPubHash,
+        };
+      }),
+    },
   };
 
-  const totalCoinWithdrawFee = Amounts.sum(
-    denomsForWithdraw.map((x) => x.feeWithdraw),
-  ).amount;
-  const totalWithdrawAmount = Amounts.add(totalCoinValue, totalCoinWithdrawFee)
-    .amount;
-
   const success = await ws.db.runWithWriteTransaction(
-    [Stores.withdrawalGroups, Stores.reserves],
+    [Stores.withdrawalGroups, Stores.reserves, Stores.planchets],
     async (tx) => {
       const newReserve = await tx.get(Stores.reserves, reservePub);
       if (!newReserve) {
@@ -723,7 +723,10 @@ async function depleteReserve(
         newReserve.currency,
       );
       if (
-        Amounts.cmp(newSummary.unclaimedReserveAmount, totalWithdrawAmount) < 0
+        Amounts.cmp(
+          newSummary.unclaimedReserveAmount,
+          denomsForWithdraw.totalWithdrawCost,
+        ) < 0
       ) {
         // Something must have happened concurrently!
         logger.error(
@@ -731,20 +734,23 @@ async function depleteReserve(
         );
         return false;
       }
-      for (let i = 0; i < planchets.length; i++) {
-        const amt = Amounts.add(
-          denomsForWithdraw[i].value,
-          denomsForWithdraw[i].feeWithdraw,
-        ).amount;
-        newReserve.reserveTransactions.push({
-          type: WalletReserveHistoryItemType.Withdraw,
-          expectedAmount: amt,
-        });
+      for (let i = 0; i < denomsForWithdraw.selectedDenoms.length; i++) {
+        const sd = denomsForWithdraw.selectedDenoms[i];
+        for (let j = 0; j < sd.count; j++) {
+          const amt = Amounts.add(sd.denom.value, sd.denom.feeWithdraw).amount;
+          newReserve.reserveTransactions.push({
+            type: WalletReserveHistoryItemType.Withdraw,
+            expectedAmount: amt,
+          });
+        }
       }
       newReserve.reserveStatus = ReserveRecordStatus.DORMANT;
       newReserve.retryInfo = initRetryInfo(false);
       await tx.put(Stores.reserves, newReserve);
       await tx.put(Stores.withdrawalGroups, withdrawalRecord);
+      for (const p of planchets) {
+        await tx.put(Stores.planchets, p);
+      }
       return true;
     },
   );
diff --git a/src/operations/tip.ts b/src/operations/tip.ts
index 6f492ea31..27956e26e 100644
--- a/src/operations/tip.ts
+++ b/src/operations/tip.ts
@@ -30,6 +30,7 @@ import {
   initRetryInfo,
   updateRetryInfoTimeout,
   WithdrawalSourceType,
+  TipPlanchet,
 } from "../types/dbTypes";
 import {
   getExchangeWithdrawalInfo,
@@ -72,6 +73,7 @@ export async function getTipStatus(
   ]);
 
   if (!tipRecord) {
+    await updateExchangeFromUrl(ws, tipPickupStatus.exchange_url);
     const withdrawDetails = await getExchangeWithdrawalInfo(
       ws,
       tipPickupStatus.exchange_url,
@@ -79,6 +81,11 @@ export async function getTipStatus(
     );
 
     const tipId = encodeCrock(getRandomBytes(32));
+    const selectedDenoms = await getVerifiedWithdrawDenomList(
+      ws,
+      tipPickupStatus.exchange_url,
+      amount,
+    );
 
     tipRecord = {
       tipId,
@@ -100,6 +107,17 @@ export async function getTipStatus(
       ).amount,
       retryInfo: initRetryInfo(),
       lastError: undefined,
+      denomsSel: {
+        totalCoinValue: selectedDenoms.totalCoinValue,
+        totalWithdrawCost: selectedDenoms.totalWithdrawCost,
+        selectedDenoms: selectedDenoms.selectedDenoms.map((x) => {
+          return {
+            countAllocated: x.count,
+            countPlanchetCreated: x.count,
+            denomPubHash: x.denom.denomPubHash,
+          };
+        }),
+      },
     };
     await ws.db.put(Stores.tips, tipRecord);
   }
@@ -185,18 +203,21 @@ async function processTipImpl(
     return;
   }
 
-  if (!tipRecord.planchets) {
-    await updateExchangeFromUrl(ws, tipRecord.exchangeUrl);
-    const denomsForWithdraw = await getVerifiedWithdrawDenomList(
-      ws,
-      tipRecord.exchangeUrl,
-      tipRecord.amount,
-    );
+  const denomsForWithdraw = tipRecord.denomsSel;
 
-    const planchets = await Promise.all(
-      denomsForWithdraw.map((d) => ws.cryptoApi.createTipPlanchet(d)),
-    );
+  if (!tipRecord.planchets) {
+    const planchets: TipPlanchet[] = [];
 
+    for (const sd of denomsForWithdraw.selectedDenoms) {
+      const denom = await ws.db.getIndexed(Stores.denominations.denomPubHashIndex, sd.denomPubHash);
+      if (!denom) {
+        throw Error("denom does not exist anymore");
+      }
+      for (let i = 0; i < sd.countAllocated; i++) {
+        const r = await ws.cryptoApi.createTipPlanchet(denom);
+        planchets.push(r);
+      }
+    }
     await ws.db.mutate(Stores.tips, tipId, (r) => {
       if (!r.planchets) {
         r.planchets = planchets;
@@ -244,6 +265,7 @@ async function processTipImpl(
     throw Error("number of tip responses does not match requested planchets");
   }
 
+  const withdrawalGroupId = encodeCrock(getRandomBytes(32));
   const planchets: PlanchetRecord[] = [];
 
   for (let i = 0; i < tipRecord.planchets.length; i++) {
@@ -261,16 +283,15 @@ async function processTipImpl(
       withdrawSig: response.reserve_sigs[i].reserve_sig,
       isFromTip: true,
       coinEvHash,
+      coinIdx: i,
+      withdrawalDone: false,
+      withdrawalGroupId: withdrawalGroupId,
     };
     planchets.push(planchet);
   }
 
-  const withdrawalGroupId = encodeCrock(getRandomBytes(32));
-
   const withdrawalGroup: WithdrawalGroupRecord = {
-    denoms: planchets.map((x) => x.denomPub),
     exchangeBaseUrl: tipRecord.exchangeUrl,
-    planchets: planchets,
     source: {
       type: WithdrawalSourceType.Tip,
       tipId: tipRecord.tipId,
@@ -278,12 +299,11 @@ async function processTipImpl(
     timestampStart: getTimestampNow(),
     withdrawalGroupId: withdrawalGroupId,
     rawWithdrawalAmount: tipRecord.amount,
-    withdrawn: planchets.map((x) => false),
-    totalCoinValue: Amounts.sum(planchets.map((p) => p.coinValue)).amount,
     lastErrorPerCoin: {},
     retryInfo: initRetryInfo(),
     timestampFinish: undefined,
     lastError: undefined,
+    denomsSel: tipRecord.denomsSel,
   };
 
   await ws.db.runWithWriteTransaction(
@@ -301,12 +321,13 @@ async function processTipImpl(
 
       await tx.put(Stores.tips, tr);
       await tx.put(Stores.withdrawalGroups, withdrawalGroup);
+      for (const p of planchets) {
+        await tx.put(Stores.planchets, p);
+      }
     },
   );
 
   await processWithdrawGroup(ws, withdrawalGroupId);
-
-  return;
 }
 
 export async function acceptTip(
diff --git a/src/operations/withdraw.ts b/src/operations/withdraw.ts
index 1f5bfd0b9..8e40a953f 100644
--- a/src/operations/withdraw.ts
+++ b/src/operations/withdraw.ts
@@ -14,7 +14,7 @@
  GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
  */
 
-import { AmountJson } from "../util/amounts";
+import { AmountJson, Amounts } from "../util/amounts";
 import {
   DenominationRecord,
   Stores,
@@ -24,8 +24,8 @@ import {
   initRetryInfo,
   updateRetryInfoTimeout,
   CoinSourceType,
+  DenominationSelectionInfo,
 } from "../types/dbTypes";
-import * as Amounts from "../util/amounts";
 import {
   BankWithdrawDetails,
   ExchangeWithdrawDetails,
@@ -74,33 +74,52 @@ function isWithdrawableDenom(d: DenominationRecord): boolean {
 export function getWithdrawDenomList(
   amountAvailable: AmountJson,
   denoms: DenominationRecord[],
-): DenominationRecord[] {
+): DenominationSelectionInfo {
   let remaining = Amounts.copy(amountAvailable);
-  const ds: DenominationRecord[] = [];
+
+  const selectedDenoms: {
+    count: number;
+    denom: DenominationRecord;
+  }[] = [];
+
+  let totalCoinValue = Amounts.getZero(amountAvailable.currency);
+  let totalWithdrawCost = Amounts.getZero(amountAvailable.currency);
 
   denoms = denoms.filter(isWithdrawableDenom);
   denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value));
 
-  // This is an arbitrary number of coins
-  // we can withdraw in one go.  It's not clear if this limit
-  // is useful ...
-  for (let i = 0; i < 1000; i++) {
-    let found = false;
-    for (const d of denoms) {
-      const cost = Amounts.add(d.value, d.feeWithdraw).amount;
+  for (const d of denoms) {
+    let count = 0;
+    const cost = Amounts.add(d.value, d.feeWithdraw).amount;
+    for (;;) {
       if (Amounts.cmp(remaining, cost) < 0) {
-        continue;
+        break;
       }
-      found = true;
       remaining = Amounts.sub(remaining, cost).amount;
-      ds.push(d);
-      break;
+      count++;
     }
-    if (!found) {
+    if (count > 0) {
+      totalCoinValue = Amounts.add(
+        totalCoinValue,
+        Amounts.mult(d.value, count).amount,
+      ).amount;
+      totalWithdrawCost = Amounts.add(totalWithdrawCost, cost).amount;
+      selectedDenoms.push({
+        count,
+        denom: d,
+      });
+    }
+
+    if (Amounts.isZero(remaining)) {
       break;
     }
   }
-  return ds;
+
+  return {
+    selectedDenoms,
+    totalCoinValue,
+    totalWithdrawCost,
+  };
 }
 
 /**
@@ -167,14 +186,18 @@ async function processPlanchet(
   if (!withdrawalGroup) {
     return;
   }
-  if (withdrawalGroup.withdrawn[coinIdx]) {
-    return;
-  }
-  const planchet = withdrawalGroup.planchets[coinIdx];
+  const planchet = await ws.db.getIndexed(Stores.planchets.byGroupAndIndex, [
+    withdrawalGroupId,
+    coinIdx,
+  ]);
   if (!planchet) {
     console.log("processPlanchet: planchet not found");
     return;
   }
+  if (planchet.withdrawalDone) {
+    console.log("processPlanchet: planchet already withdrawn");
+    return;
+  }
   const exchange = await ws.db.get(
     Stores.exchanges,
     withdrawalGroup.exchangeBaseUrl,
@@ -243,25 +266,32 @@ async function processPlanchet(
   let withdrawalGroupFinished = false;
 
   const success = await ws.db.runWithWriteTransaction(
-    [Stores.coins, Stores.withdrawalGroups, Stores.reserves],
+    [Stores.coins, Stores.withdrawalGroups, Stores.reserves, Stores.planchets],
     async (tx) => {
       const ws = await tx.get(Stores.withdrawalGroups, withdrawalGroupId);
       if (!ws) {
         return false;
       }
-      if (ws.withdrawn[coinIdx]) {
+      const p = await tx.get(Stores.planchets, planchet.coinPub);
+      if (!p) {
+        return false;
+      }
+      if (p.withdrawalDone) {
         // Already withdrawn
         return false;
       }
-      ws.withdrawn[coinIdx] = true;
-      delete ws.lastErrorPerCoin[coinIdx];
-      let numDone = 0;
-      for (let i = 0; i < ws.withdrawn.length; i++) {
-        if (ws.withdrawn[i]) {
-          numDone++;
+      p.withdrawalDone = true;
+      await tx.put(Stores.planchets, p);
+
+      let numNotDone = 0;
+
+      await tx.iterIndexed(Stores.planchets.byGroup, withdrawalGroupId).forEach((x) => {
+        if (!x.withdrawalDone) {
+          numNotDone++;
         }
-      }
-      if (numDone === ws.denoms.length) {
+      });
+
+      if (numNotDone == 0) {
         ws.timestampFinish = getTimestampNow();
         ws.lastError = undefined;
         ws.retryInfo = initRetryInfo(false);
@@ -298,7 +328,7 @@ export async function getVerifiedWithdrawDenomList(
   ws: InternalWalletState,
   exchangeBaseUrl: string,
   amount: AmountJson,
-): Promise<DenominationRecord[]> {
+): Promise<DenominationSelectionInfo> {
   const exchange = await ws.db.get(Stores.exchanges, exchangeBaseUrl);
   if (!exchange) {
     console.log("exchange not found");
@@ -318,14 +348,18 @@ export async function getVerifiedWithdrawDenomList(
 
   let allValid = false;
 
-  let selectedDenoms: DenominationRecord[];
+  let selectedDenoms: DenominationSelectionInfo;
 
   do {
     allValid = true;
     const nextPossibleDenoms = [];
     selectedDenoms = getWithdrawDenomList(amount, possibleDenoms);
     console.log("got withdraw denom list");
-    for (const denom of selectedDenoms || []) {
+    if (!selectedDenoms) {
+      console;
+    }
+    for (const denomSel of selectedDenoms.selectedDenoms) {
+      const denom = denomSel.denom;
       if (denom.status === DenominationStatus.Unverified) {
         console.log(
           "checking validity",
@@ -349,7 +383,7 @@ export async function getVerifiedWithdrawDenomList(
         nextPossibleDenoms.push(denom);
       }
     }
-  } while (selectedDenoms.length > 0 && !allValid);
+  } while (selectedDenoms.selectedDenoms.length > 0 && !allValid);
 
   console.log("returning denoms");
 
@@ -402,6 +436,23 @@ async function resetWithdrawalGroupRetry(
   });
 }
 
+async function processInBatches(workGen: Iterator<Promise<void>>, batchSize: number): Promise<void> {
+  for (;;) {
+    const batch: Promise<void>[] = [];
+    for (let i = 0; i < batchSize; i++) {
+      const wn = workGen.next();
+      if (wn.done) {
+        break;
+      }
+      batch.push(wn.value);
+    }
+    if (batch.length == 0) {
+      break;
+    }
+    await Promise.all(batch);
+  }
+}
+
 async function processWithdrawGroupImpl(
   ws: InternalWalletState,
   withdrawalGroupId: string,
@@ -420,11 +471,21 @@ async function processWithdrawGroupImpl(
     return;
   }
 
-  const ps = withdrawalGroup.denoms.map((d, i) =>
-    processPlanchet(ws, withdrawalGroupId, i),
-  );
-  await Promise.all(ps);
-  return;
+  const numDenoms = withdrawalGroup.denomsSel.selectedDenoms.length;
+  const genWork = function*(): Iterator<Promise<void>> {
+    let coinIdx = 0;
+    for (let i = 0; i < numDenoms; i++) {
+      const count = withdrawalGroup.denomsSel.selectedDenoms[i].countAllocated;
+      for (let j = 0; j < count; j++) {
+        yield processPlanchet(ws, withdrawalGroupId, coinIdx);
+        coinIdx++;
+      }
+    }
+  }
+
+  // Withdraw coins in batches.
+  // The batch size is relatively large
+  await processInBatches(genWork(), 50);
 }
 
 export async function getExchangeWithdrawalInfo(
@@ -447,14 +508,6 @@ export async function getExchangeWithdrawalInfo(
     baseUrl,
     amount,
   );
-  let acc = Amounts.getZero(amount.currency);
-  for (const d of selectedDenoms) {
-    acc = Amounts.add(acc, d.feeWithdraw).amount;
-  }
-  const actualCoinCost = selectedDenoms
-    .map((d: DenominationRecord) => Amounts.add(d.value, d.feeWithdraw).amount)
-    .reduce((a, b) => Amounts.add(a, b).amount);
-
   const exchangeWireAccounts: string[] = [];
   for (const account of exchangeWireInfo.accounts) {
     exchangeWireAccounts.push(account.payto_uri);
@@ -462,9 +515,11 @@ export async function getExchangeWithdrawalInfo(
 
   const { isTrusted, isAudited } = await getExchangeTrust(ws, exchangeInfo);
 
-  let earliestDepositExpiration = selectedDenoms[0].stampExpireDeposit;
-  for (let i = 1; i < selectedDenoms.length; i++) {
-    const expireDeposit = selectedDenoms[i].stampExpireDeposit;
+  let earliestDepositExpiration =
+    selectedDenoms.selectedDenoms[0].denom.stampExpireDeposit;
+  for (let i = 1; i < selectedDenoms.selectedDenoms.length; i++) {
+    const expireDeposit =
+      selectedDenoms.selectedDenoms[i].denom.stampExpireDeposit;
     if (expireDeposit.t_ms < earliestDepositExpiration.t_ms) {
       earliestDepositExpiration = expireDeposit;
     }
@@ -512,6 +567,11 @@ export async function getExchangeWithdrawalInfo(
     }
   }
 
+  const withdrawFee = Amounts.sub(
+    selectedDenoms.totalWithdrawCost,
+    selectedDenoms.totalCoinValue,
+  ).amount;
+
   const ret: ExchangeWithdrawDetails = {
     earliestDepositExpiration,
     exchangeInfo,
@@ -520,13 +580,13 @@ export async function getExchangeWithdrawalInfo(
     isAudited,
     isTrusted,
     numOfferedDenoms: possibleDenoms.length,
-    overhead: Amounts.sub(amount, actualCoinCost).amount,
+    overhead: Amounts.sub(amount, selectedDenoms.totalWithdrawCost).amount,
     selectedDenoms,
     trustedAuditorPubs,
     versionMatch,
     walletVersion: WALLET_EXCHANGE_PROTOCOL_VERSION,
     wireFees: exchangeWireInfo,
-    withdrawFee: acc,
+    withdrawFee,
     termsOfServiceAccepted: tosAccepted,
   };
   return ret;
diff --git a/src/types/dbTypes.ts b/src/types/dbTypes.ts
index 158d438cf..df019fc00 100644
--- a/src/types/dbTypes.ts
+++ b/src/types/dbTypes.ts
@@ -1,17 +1,17 @@
 /*
- This file is part of TALER
- (C) 2018 GNUnet e.V. and INRIA
+ This file is part of GNU Taler
+ (C) 2018-2020 Taler Systems S.A.
 
- TALER is free software; you can redistribute it and/or modify it under the
+ 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.
 
- TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ 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
- TALER; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
  */
 
 /**
@@ -608,7 +608,25 @@ export interface PlanchetRecord {
    * Public key of the coin.
    */
   coinPub: string;
+
+  /**
+   * Private key of the coin.
+   */
   coinPriv: string;
+
+  /**
+   * Withdrawal group that this planchet belongs to
+   * (or the empty string).
+   */
+  withdrawalGroupId: string;
+
+  /**
+   * Index within the withdrawal group (or -1).
+   */
+  coinIdx: number;
+
+  withdrawalDone: boolean;
+
   /**
    * Public key of the reserve, this might be a reserve not
    * known to the wallet if the planchet is from a tip.
@@ -889,6 +907,8 @@ export interface TipRecord {
    */
   planchets?: TipPlanchet[];
 
+  denomsSel: DenomSelectionState;
+
   /**
    * Response if the merchant responded,
    * undefined otherwise.
@@ -1356,6 +1376,28 @@ export interface WithdrawalSourceReserve {
 
 export type WithdrawalSource = WithdrawalSourceTip | WithdrawalSourceReserve;
 
+export interface DenominationSelectionInfo {
+  totalCoinValue: AmountJson;
+  totalWithdrawCost: AmountJson;
+  selectedDenoms: {
+    /**
+     * How many times do we withdraw this denomination?
+     */
+    count: number;
+    denom: DenominationRecord;
+  }[];
+}
+
+export interface DenomSelectionState {
+  totalCoinValue: AmountJson;
+  totalWithdrawCost: AmountJson;
+  selectedDenoms: {
+    denomPubHash: string;
+    countAllocated: number;
+    countPlanchetCreated: number;
+  }[];
+}
+
 export interface WithdrawalGroupRecord {
   withdrawalGroupId: string;
 
@@ -1379,22 +1421,13 @@ export interface WithdrawalGroupRecord {
    */
   timestampFinish?: Timestamp;
 
-  totalCoinValue: AmountJson;
-
   /**
    * Amount including fees (i.e. the amount subtracted from the
    * reserve to withdraw all coins in this withdrawal session).
    */
   rawWithdrawalAmount: AmountJson;
 
-  denoms: string[];
-
-  planchets: (undefined | PlanchetRecord)[];
-
-  /**
-   * Coins in this session that are withdrawn are set to true.
-   */
-  withdrawn: boolean[];
+  denomsSel: DenomSelectionState;
 
   /**
    * Retry info, always present even on completed operations so that indexing works.
@@ -1625,6 +1658,22 @@ export namespace Stores {
     }
   }
 
+  class PlanchetsStore extends Store<PlanchetRecord> {
+    constructor() {
+      super("planchets", { keyPath: "coinPub" });
+    }
+    byGroupAndIndex = new Index<string, PlanchetRecord>(
+      this,
+      "withdrawalGroupAndCoinIdxIndex",
+      ["withdrawalGroupId", "coinIdx"],
+    );
+    byGroup = new Index<string, PlanchetRecord>(
+      this,
+      "withdrawalGroupIndex",
+      "withdrawalGroupId",
+    );
+  }
+
   class RefundEventsStore extends Store<RefundEventRecord> {
     constructor() {
       super("refundEvents", { keyPath: "refundGroupId" });
@@ -1681,6 +1730,7 @@ export namespace Stores {
   export const tips = new TipsStore();
   export const senderWires = new SenderWiresStore();
   export const withdrawalGroups = new WithdrawalGroupsStore();
+  export const planchets = new PlanchetsStore();
   export const bankWithdrawUris = new BankWithdrawUrisStore();
   export const refundEvents = new RefundEventsStore();
   export const payEvents = new PayEventsStore();
diff --git a/src/types/walletTypes.ts b/src/types/walletTypes.ts
index ed334bc47..da87b1c1c 100644
--- a/src/types/walletTypes.ts
+++ b/src/types/walletTypes.ts
@@ -30,9 +30,9 @@
 import { AmountJson, codecForAmountJson } from "../util/amounts";
 import * as LibtoolVersion from "../util/libtoolVersion";
 import {
-  DenominationRecord,
   ExchangeRecord,
   ExchangeWireInfo,
+  DenominationSelectionInfo,
 } from "./dbTypes";
 import { Timestamp } from "../util/time";
 import {
@@ -77,7 +77,7 @@ export interface ExchangeWithdrawDetails {
   /**
    * Selected denominations for withdraw.
    */
-  selectedDenoms: DenominationRecord[];
+  selectedDenoms: DenominationSelectionInfo;
 
   /**
    * Fees for withdraw.
diff --git a/src/util/amounts.ts b/src/util/amounts.ts
index 5953f5130..d962b6cbd 100644
--- a/src/util/amounts.ts
+++ b/src/util/amounts.ts
@@ -332,6 +332,33 @@ function check(a: any): boolean {
   }
 }
 
+function mult(a: AmountJson, n: number): Result {
+  if (!Number.isInteger(n)) {
+    throw Error("amount can only be multipied by an integer");
+  }
+  if (n < 0) {
+    throw Error("amount can only be multiplied by a positive integer");
+  }
+  if (n == 0) {
+    return { amount: getZero(a.currency), saturated: false };
+  }
+  let acc = {... a};
+  while (n > 1) {
+    let r: Result;
+    if (n % 2 == 0) {
+      n = n / 2;
+      r = add(acc, acc);
+    } else {
+      r = add(acc, a);
+    }
+    if (r.saturated) {
+      return r;
+    }
+    acc = r.amount;
+  }
+  return { amount: acc, saturated: false };
+}
+
 // Export all amount-related functions here for better IDE experience.
 export const Amounts = {
   stringify: stringify,
@@ -341,9 +368,11 @@ export const Amounts = {
   add: add,
   sum: sum,
   sub: sub,
+  mult: mult,
   check: check,
   getZero: getZero,
   isZero: isZero,
   maxAmountValue: maxAmountValue,
   fromFloat: fromFloat,
+  copy: copy,
 };
diff --git a/src/webex/renderHtml.tsx b/src/webex/renderHtml.tsx
index a56af37fc..39ff470a2 100644
--- a/src/webex/renderHtml.tsx
+++ b/src/webex/renderHtml.tsx
@@ -25,7 +25,6 @@
  */
 import { AmountJson } from "../util/amounts";
 import * as Amounts from "../util/amounts";
-import { DenominationRecord } from "../types/dbTypes";
 import { ExchangeWithdrawDetails } from "../types/walletTypes";
 import * as i18n from "./i18n";
 import React from "react";
@@ -208,31 +207,6 @@ function FeeDetailsView(props: {
   }
 
   const denoms = rci.selectedDenoms;
-
-  const countByPub: { [s: string]: number } = {};
-  const uniq: DenominationRecord[] = [];
-
-  denoms.forEach((x: DenominationRecord) => {
-    let c = countByPub[x.denomPub] || 0;
-    if (c === 0) {
-      uniq.push(x);
-    }
-    c += 1;
-    countByPub[x.denomPub] = c;
-  });
-
-  function row(denom: DenominationRecord): JSX.Element {
-    return (
-      <tr>
-        <td>{countByPub[denom.denomPub] + "x"}</td>
-        <td>{renderAmount(denom.value)}</td>
-        <td>{renderAmount(denom.feeWithdraw)}</td>
-        <td>{renderAmount(denom.feeRefresh)}</td>
-        <td>{renderAmount(denom.feeDeposit)}</td>
-      </tr>
-    );
-  }
-
   const withdrawFee = renderAmount(rci.withdrawFee);
   const overhead = renderAmount(rci.overhead);
 
@@ -266,7 +240,19 @@ function FeeDetailsView(props: {
               <th>{i18n.str`Deposit Fee`}</th>
             </tr>
           </thead>
-          <tbody>{uniq.map(row)}</tbody>
+          <tbody>
+            {denoms.selectedDenoms.map((ds) => {
+              return (
+                <tr key={ds.denom.denomPub}>
+                  <td>{ds.count + "x"}</td>
+                  <td>{renderAmount(ds.denom.value)}</td>
+                  <td>{renderAmount(ds.denom.feeWithdraw)}</td>
+                  <td>{renderAmount(ds.denom.feeRefresh)}</td>
+                  <td>{renderAmount(ds.denom.feeDeposit)}</td>
+                </tr>
+              );
+            })}
+          </tbody>
         </table>
       </div>
       <h3>Wire Fees</h3>