On-chain mixers, such as Tornado Cash (TC), have become a popular privacy solution for many
non-privacy-preserving blockchain users. These mixers enable users to deposit a fixed amount of
coins and withdraw them to another address, while effectively reducing the linkability between these
addresses and securely obscuring their transaction history. However, the high cost of interacting
with existing on-chain mixer smart contracts prohibits standard users from using the mixer, mainly
due to the use of computationally expensive cryptographic primitives. For instance, the deposit cost
of TC on Ethereum is approximately 1.1m gas (i.e., 66 USD in June 2023), which is 53× higher than
issuing a base transfer transaction.
In this work, we introduce the Merkle Pyramid Builder approach, to incrementally build the
Merkle tree in an on-chain mixer and update the tree per batch of deposits, which can therefore
decrease the overall cost of using the mixer. Our evaluation results highlight the effectiveness of
this approach, showcasing a significant reduction of up to 7× in the amortized cost of depositing
compared to state-of-the-art on-chain mixers. Importantly, these improvements are achieved without
compromising users’ privacy. Furthermore, we propose the utilization of verifiable computations to
shift the responsibility of Merkle tree updates from on-chain smart contracts to off-chain clients,
which can further reduce deposit costs. Additionally, our analysis demonstrates that our designs
ensure fairness by distributing Merkle tree update costs among clients over time.