AMR: Autonomous Coin Mixer with Privacy Preserving Reward Distribution

In three numbers

The problem

Mixers hide you in a crowd that has no reason to stay

A mixer like Tornado Cash takes fixed-size deposits and later pays them out to fresh addresses. Nobody can tell which deposit a withdrawal came from. Nobody, that is, except by guessing among the deposits still in the pool. That pool is the anonymity set: the more deposits sit in it, and the longer they stay, the weaker the guess.

But coins in a mixer earn nothing, so people withdraw soon after they deposit. In Tornado Cash's 10 ETH pool, we counted 2,810 deposits and 2,606 withdrawals over eight months (§7.3). Whenever withdrawals catch up with deposits, the anonymity set falls to zero.

A reward is itself a transaction, though, and an observer will try to link it to a deposit. So the reward must not shrink the crowd a withdrawal hides in. The next section shows how AMR ensures that.

Interactive · Figures 4–6 of the paper

Walk the protocol: deposit, reward, withdraw

Every deposit adds a commitment $\mathsf{cm}=H_p(k\,\|\,r)$ to a Merkle tree. The depositor keeps the note $(k,r)$ secret. Spending a note means proving in zero knowledge that it sits under some root, and revealing its nullifier $\mathsf{sn}=H_p(k)$ so it cannot be spent twice. Step through Alice's life in the pool, including the three ways a transaction gets rejected.

1. Deposit: a fixed amount $\mathsf{amt}$ goes into the contract.
2. Lend: the contract deposits it into a lending platform $\Sigma$.
3. Reward: prove a deposit is $\ge t_{con}$ blocks old and receive governance tokens.
4. Withdraw: prove that some deposit is yours and receive $\mathsf{amt}$ at a fresh address.
5. Redeem: the contract pulls the funds and accrued interest $R$ from $\Sigma$.
6. Share: the interest goes to a pool $\Gamma_{\mathsf{AMR}}$ for token lockers.

Toy instance for illustration: depth $d=3$, $k=3$ recent roots, $t_{con}=3$ blocks, and roots named by counter instead of hash values. The paper evaluates $d=10$ to $30$ and uses $k=1000$ in its front-running example. The rules follow Figures 4–6: the reward-root rotation (if $\mathsf{Block.Height}-\mathsf{root}^{\mathsf{next}}.\mathsf{blockheight}\ge t_{con}$, then $\mathsf{root}^{\mathsf{curr}}\leftarrow\mathsf{root}^{\mathsf{next}}$ and $\mathsf{root}^{\mathsf{next}}\leftarrow\mathsf{root}_{new}$), a single NullifierList for rewards and withdrawals (§5.2), and $\mathsf{sn}=H_p(k_{dep})$ for both.

Interactive · Figure 9 of the paper

How long should the reward make you wait?

A reward proof reveals that its deposit is at least $t_{con}$ blocks old. That reduces the adversary's search to deposits made before $h-t_{con}$ (Claim 1). A withdrawal loses nothing, because every reward adds a fresh commitment back to the tree (Claim 2). The designer's knob is $t_{con}$: the longer the wait, the more deposits arrive in the meantime. To size it, we measured how many deposits Tornado Cash's 10 ETH pool received per window, from block 9,161,895 (25 December 2019) to block 10,726,597 (25 August 2020).

Both claims assume secure primitives and that deposit addresses are independent and unlinkable (§6.1). The paper argues them informally, as proof sketches (§6). The "approximately 4.5 days" for 30,000 blocks is the paper's own conversion. We do not convert the other windows to days.

Interactive · Table 1, Figures 7 and 8 of the paper

What each operation costs, by tree depth and hash

The Merkle depth $d$ sets the capacity ($2^d$ leaves) and the price. A deposit hashes a path of length $d$ on-chain, so its gas grows with $d$. Verifying a withdrawal is one Groth16 check, so it stays flat. A reward does both. The hash inside the circuit, MiMC or Poseidon, changes the constraint count and therefore the client's proving time.

Deployment gas is not plotted: it is a one-time cost of about 6–8M, which §7.2 gives for both hashes, and Figure 7 draws it as a single series. Figure 7 also draws a single "Withdraw" series for both hashes. Gas values come from graph/graph-generating.ipynb, the notebook that plots Figure 7.

Interactive · Section 8 of the paper

Constant cost against ring-sized cost

Möbius hides a sender in a ring signature, and its gas grows linearly with the ring. That caps its anonymity set at 24 ($8m$ gas to withdraw, §1). Anonymous Zether reaches a ring of 64 at $48.7m$ gas per transfer, beyond the roughly $15m$ block gas limit of the time. AMR's withdrawal verifies one constant-size proof, whatever the pool size. Pick which AMR figure to compare against: the ratios the paper quotes depend on it.

These are single values quoted in the paper, not measured curves. We draw no line through Möbius from its one point. The operations differ: Zeth's number is proof verification only, and the Zether figures are per transfer. Ratios are our arithmetic on the selected values.

Guarantees

What AMR promises, and under which assumptions

Threat model (§4.5): computationally bounded adversaries corrupting at most 1/3 of consensus participants, with miner powers (reordering and injecting transactions). Withdrawal and reward fees are paid through a non-adversarial relayer or an unlinkable funded address. The lending platforms are assumed secure.

Measured

Implementation and results

The circuits are written in Circom and proven with Groth16 via snarkjs, with a Pedersen hash for $H_p$ and MiMC or Poseidon for $H_{2p}$. The contract is 1,013 lines of Solidity. Measurements ran on an Intel Core i5-7400 @3.80 GHz with 32 GB RAM (§7.1).

Table 1 · zk-SNARK setup cost of the withdraw circuit

$\mathsf{vk}_{wdr}=640$ B. Constraint counts equal $1{,}815+243d$ (Poseidon) and $1{,}815+1{,}323d$ (MiMC) exactly at all five depths (§7.2). We checked each row.

Lending-platform overhead (§7.2, the paper's estimate)

From Etherscan and Compound's documentation: depositing into Aave or Compound costs about $0.3m$ gas. Redeeming costs under $0.2m$ (Aave) or under $0.1m$ (Compound). So expect about $+0.3m$ per AMR deposit and $+0.2m$ per withdrawal.

Tornado Cash 10 ETH pool (§7.3)

From block 9,161,895 to 10,726,597: 2,810 deposits and 2,606 withdrawals. Figure 10 plots both as cumulative counts. Its time series is not in the paper's repository, so we do not redraw it.

Where the numbers disagree

We reproduce each source as written. Where two places disagree, we show both and mark our own arithmetic.

1. Headline gas. The abstract and §1 say a deposit costs $1.2m$ gas ($\$31.95$), a withdrawal $0.3m$ ($\$9.12$) and a reward $1.5m$ ($\$41.07$), at 70 Gwei and $\$380.4$/ETH. Figure 7 at $d=30$ gives deposit 1,482,672 (MiMC) or 1,288,077 (Poseidon), withdraw 378,090, and reward 1,860,762 (MiMC) or 1,666,167 (Poseidon). §8's "32×" and "130×" against 48.7m gas match the Figure 7 MiMC values, not §1's. At the footnote's prices, $\$9.12$ corresponds to about 343K gas (our arithmetic).
2. Withdraw gas. §7.2 says about 320,000 "for all tree depths and both choices of hash functions". Figure 7's values are 378,066 / 378,078 / 325,051 / 378,078 / 378,090 at $d=10$…$30$.
3. Reward gas. §7.2 says a reward costs a deposit plus a withdrawal. That holds for every Figure 7 point except MiMC at $d=10$ (831,649 vs 912,086) and $d=20$ (1,302,969 vs 1,361,631), where the notebook hard-codes the value. Those two points are hollow on the chart.
4. Deposits during a 30,000-block wait. §7.3 says "an additional 52". Figure 9's bar is labelled 53.40.
5. Poseidon speed-up. §7.2 reports "a reduction of 3×" in proving time. Figure 8 gives 10.625 / 3.607 ≈ 2.9× at $d=30$ but 4.152 / 2.107 ≈ 2.0× at $d=10$ (our arithmetic).
6. ETH price. §1 prices gas at $\$380.4$/ETH. §6.3 values 10,020 ether at "38m USD" and 20 ether at "76,000 USD", about $\$3{,}800$/ETH (our arithmetic).

Code and deployment

The paper does not publish its source code. As listed in the paper, AMR was deployed to the Ethereum Kovan testnet at 0xdE992c4fBd0f39E5c0356e6365Bcfafa1e94970b, and a demo video is at youtu.be/-oAQlsRTF08.

Cite

Cite this work

@inproceedings{le2021amr,
  title         = {{AMR}: Autonomous Coin Mixer with Privacy Preserving Reward Distribution},
  author        = {Le, Duc V. and Gervais, Arthur},
  booktitle     = {3rd ACM Conference on Advances in Financial Technologies (AFT '21)},
  address       = {Arlington, VA, USA},
  publisher     = {ACM},
  year          = {2021},
  doi           = {10.1145/3479722.3480800},
  eprint        = {2010.01056},
  archivePrefix = {arXiv}
}