Pay Less for Your Privacy: Towards Cost-Effective On-Chain Mixers

In three numbers

What batching buys

Tornado-Cash-style mixers hide a withdrawal among every earlier deposit, but they charge each depositor for re-hashing the whole deposit Merkle tree with a SNARK-friendly hash.

The problem

Every deposit pays for the whole tree

A mixer contract keeps all deposit commitments $\mathsf{cm}_i$ as leaves of a Merkle tree of depth $d$. To withdraw, a client proves in zero knowledge that it can open some leaf under a recent root, and reveals a nullifier so the same leaf cannot be spent twice. Appending a leaf means recomputing the $d$ hashes on its path to the root — cheap in theory, $O(\log n)$, but with a SNARK-friendly hash such as MiMC that path costs around a million gas, and it is paid again for every one of $k$ deposits: $O(k\cdot\log n)$.

The paper's design, inspired by Merkle Mountain Ranges, stores only the $O(\log l)$ “peaks” of the partially built subtree on-chain. Most deposits hash nothing or a few levels; the $l$-th deposit completes the subtree and walks it up to the root. Because that last client pays much more, every other client in the queue adds a small fee $d^0$ that the contract forwards to whoever closes the queue. A second variant (VC) lets that last client compute the new root off-chain and submit a proof, so the contract only verifies.

Interactive · Figure 2 of the paper

Build the pyramid one deposit at a time

Press Deposit. Orange leaves are queued, not yet under any root; dashed boxes are the peaks the contract keeps in its deposit queue. Watch which hashes each deposit triggers — and who pays for the walk to the root. Switch to Basic mixer to see the one-deposit-one-update behaviour of today's mixers.

Counts are hash evaluations from the construction in §5, which calls deposits of even index $i$ free — the index is 0-based, as in Fig. 2 (a leaf of index $i$ inside its queue merges once for each trailing 1-bit of $i$; the $l$-th deposit also hashes the $d-\log_2 l$ levels above the subtree), drawn on a depth-5 tree for legibility. They are not gas: measured gas also includes per-transaction costs that do not shrink with batching, which is why the curves below flatten near 145K.

Interactive · Figures 10 and 11 of the paper

Gas per deposit versus queue size

Average gas paid per client, measured on a local EVM (ganache) for eight queue sizes and five tree depths. Drag the queue size: the slider stops only at the eight measured sizes. Deeper trees cost more at small queues, but the cost of the root walk is shared by more clients as $l$ grows and every depth converges.

Data provenance. No raw measurements ship with the paper. Every MPB and VC value here was recovered from the vector coordinates of the markers in the paper's own figure files (Fig. 10, mpb_gascost_all.pdf; Fig. 11, mpb_gascost_with_vc.pdf), to better than ±1K gas, and is shown to the nearest thousand. The $d=20$ series is identical in both figures, and matches the labels the authors printed on an earlier plot of the same data (555k, 338k, 235k, 187k, 164k, 154k, 148k, 146k) to within 1K. The Tornado Cash line, 1,111,030 gas, is stated in the text. The text lists queue sizes up to 128; both figures plot a further point at 256.

Interactive · Figure 9 of the paper

The price of batching: waiting for the queue

A queued deposit is not under any root yet, so it cannot be withdrawn and does not enlarge anyone's anonymity set. How long that lasts depends on how busy the pool is. The paper measured the average gap $\Delta$ between two Tornado Cash deposits in each ETH pool and uses 12-second post-merge slots.

Busy-ness varies: from October 1, 2020 to the OFAC sanctions on August 8, 2022 the four pools averaged $51\pm25$ deposits a day, and $9\pm8$ afterwards (Fig. 15). On that basis the paper notes that with $l=32$ users would wait less than 4 days on average.

Interactive · Table 1 of the paper

Keeping the last depositor whole

The client who closes a queue pays for the whole root update. So the first $l-1$ clients of queue $i$ each pay a fee $d^0_i=C_{i-1}/l$, calibrated on what the previous queue cost; the contract accumulates it and forwards it to the last client. Gas prices drift between queues, so the last client's net cost $d^1_i$ differs from everyone else's — by exactly $gas_{update}$ times the price change. That is the paper's $\varepsilon$-fairness with $\varepsilon=gas_{update}$.

As in §7.3, $gas_{update}$ is taken as $l$ times the average per-client deposit gas (Fig. 10, $d=20$, recovered values). Over any $n\le7$ days, more than 80% of the gas-price differences between Tornado Cash deposits were below 30 Gwei (Fig. 12), which is why the preset uses $\Delta p=30$. A price drop can make $d^1_i$ negative: the refund then exceeds the last client's gas bill.

Guarantees

What changes, and what does not

The paper's framework scores a mixer on five properties. Batching changes only efficiency and how fairness is achieved; the proofs for privacy and correctness go through unchanged.

Measured

Implementation and results

Withdrawal circuit in Circom; Groth16 via snarkjs; Pedersen hash for commitments ($H_p$) and MiMC for the tree ($H_{2p}$). Contracts deployed on a ganache EVM; experiments on an Intel Core i7-11800H at 2.30 GHz with 16 GB RAM. The VC deposit contract adapts the circuit of Tornado Cash's anonymity mining.

Average gas per deposit (Figs. 10 and 11)

Recovered from figure geometry, nearest 1K gas (see provenance). The text reports the VC deposit that updates the root at approximately 436K gas.

Contract deployment (Fig. 8)

Recovered from the bar heights in deploy_cost.pdf (±10K gas). The text: “always between 6M and 7M gas”, a one-time cost amortised over the life of the contract.

Tornado Cash measurements used by the paper

Provenance

Where the paper disagrees with itself

Each chart above reproduces its source faithfully. Where two places in the paper give different numbers, both are shown and flagged here rather than silently reconciled.

1. Finalisation time, formula vs. figure. §7.2 gives $\mathbb{E}_{final}=(l-1)\Delta/2$, but every point in Fig. 9 equals $l\cdot\Delta\cdot12\,$s — the time to fill the whole queue, roughly twice the formula for large $l$. The waiting-time chart plots both.
2. $gas_{update}$ in the fairness example. §7.3 computes $2^5\times1.78\times10^5=5.69M$ gas for “depth 20 (cf. Fig. 10)”. Fig. 10's $d=20$, $l=32$ point is ≈164K; ≈178K is the $d=30$ point. With 164K the example becomes ≈5.25M gas and ≈0.16 ETH instead of 0.17 ETH. The arithmetic of §7.3 itself is correct.
3. Largest queue size. §7.1 lists $l\in\{2,\dots,128\}$ and reports “around 146K” at $l=128$. Figs. 10–11 plot eight sizes up to $2^8=256$, and the “146k” label sits at 256. At 128 the recovered values range from ≈145K ($d=10$) to ≈152K ($d=30$).
4. VC saving ratio. §7.4 states a saving ratio of $\frac{1M}{436K\cdot l}=\frac{2.29}{l}$ for a queue of size $l$. Fig. 11 shows the MPB+VC per-client cost at $l=2$ as ≈273K gas, about 4.1× below Tornado Cash's 1,111,030, whereas $2.29/l$ gives 1.15 at $l=2$ and less than 1 from $l=4$. The formula is quoted, not used.
5. Figure numbering. Figure numbers on this page follow the full version (the linked PDF, also ePrint 2023/1222). The AFT proceedings version omits the VC setup pseudocode (Fig. 6 here), so its later figures are numbered one lower — Fig. 10 here is Fig. 9 there.
6. Chart data. No notebook or raw data ships with the paper. Values in the gas and deployment charts were recovered from the vector coordinates of the figure PDFs; values stated in prose are used verbatim.

Reference

Cite this work

@inproceedings{wang2023payless,
  title     = {Pay Less for Your Privacy: Towards Cost-Effective
               On-Chain Mixers},
  author    = {Wang, Zhipeng and Cirkovic, Marko and Le, Duc V. and
               Knottenbelt, William and Cachin, Christian},
  booktitle = {5th Conference on Advances in Financial Technologies
               (AFT 2023)},
  editor    = {Bonneau, Joseph and Weinberg, S. Matthew},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {282},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year      = {2023}
}

@misc{wang2023payless-full,
  author       = {Wang, Zhipeng and Cirkovic, Marko and Le, Duc V. and
                  Knottenbelt, William and Cachin, Christian},
  title        = {Pay Less for Your Privacy: Towards Cost-Effective
                  On-Chain Mixers},
  howpublished = {Cryptology ePrint Archive, Paper 2023/1222},
  year         = {2023},
  note         = {\url{https://eprint.iacr.org/2023/1222}}
}

Code and data. The paper has no code or data availability statement and links no public repository for its implementation. The only code it references is Tornado Cash's anonymity-mining circuit (tornadocash/tornado-anonymity-mining), which the authors adapted for the VC deposit evaluation.