Hi! I have a suggestion on how to reduce deposit gas costs on L1 Ethereum:
- When a user (Alice) deposits, their leaf stored on-chain in a queue. No hashing is required. The deposit merkle root is not updated.
- Anyone (Bob) can merge a queue of multiple leaves to update the merkle root.
- In exchange for merging the leaves, Bob recieves the right to relay withdrawals for a certain time period.
- This right-to-relay may have a half-life; e.g. for the first hour, only Bob may relay transactions; for the second hour, Bob has the right to relay every other transaction, for the third hour, Bob has the right to relay every 4th transaction, and so on.
- The withdrawal fees that Bob earns covers the gas he spent to merge the leaves.
- Bob may grief the system by refusing to relay withdrawals. That’s OK as his right to relay transactions decays over time and any relayer may resume withdrawals. Though some careful design needs to be done to strike a right balance.
An implementation of a Merkle tree which queues leaves rather than updates the root per insertion is here. maci/AccQueue.sol at v1 · appliedzkp/maci · GitHub
The benefits of this approach are:
- Lower deposit gas costs for users, so Tornado Cash can remain accessible for small amounts.
- The overall gas spent is lower. Let’s say the tree depth is 20 and there are 32 deposits. If each deposit updates the root, the gas spent is
20n * 32 = 640n. But if a relayer merges the 32 leaves on behalf of the users, the gas spent is
31n + 15n = 46n(you need 31 hashes to merge 32 leaves to a subroot, and another 15 to update the main merkle root. Apologies in advance for any off-by-one errors in this calculation).
- No changes are needed to the zk-snark circuits.
The drawbacks are:
- A new deposit pool is necessary as the technique won’t work with the existing pools. If gas costs remain high though, the benefits of creating a new pool may outweigh the costs of a new anonymity set. For instance, if the high gas costs mean that nobody wants to use the 0.1 ETH pool, but would be willing to use a cheaper 0.1 ETH pool, then a new pool would be useful.
- Relayers may DoS the system if a lot of relayers have the sole right to relay withdrawals but do nothing. There may be ways to work around this, such as creating time windows where anyone can relay withdrawals (e.g. the first 10 minutes of every hour), so as to limit the impact of malicious relayers.
Another way to reward relayers is to distribute token rewards.