Recursive ZK-SNARKs: Improving Tornado Cash Security and Note Management
Tornado Cash is a service on the Ethereum blockchain (and on a couple other networks) that allows users to deposit Ether or tokens and hide the source of the funds with the power of modern cryptography; users can deposit funds and then withdraw them to make it impossible to connect these two interactions.
How does this work from the user’s perspective?
When an user deposits funds they are given back a text string like this:
tornado-eth-0.1–5–0x8db49b7febf50f55b8476b91d80c0b58e479b94fa4ba565c7dcc550bc9d381f0f281587ae9081c168a62fa33b5a4ce39172d01a36d6e726bc632c4e57c09
This text string is called “a note”. A note can be redeemed to get one’s funds back from the system. Anyone having this note in their possession, can redeem the note and get the underlying funds. When we are observing this example note in more detail, we can see that the note is from eth pool (“-eth-”), The deposit resides on the Göerli network (chain id = 5), and it’s worth 0.1 Göerli ETH.
On top of all this information we can dig more information about the note by correlating it with the underlying blockchain. Tornado Cash has a handy ready-made tool for this, called Tornado Cash Compliance Tool. When we paste our note into this tool, we can see following information:
We can see:
- Which address made the deposit: 0x41a7ce9d735815f333d9969de8225a6477afca17
- When it was made: Dec 31, 2021 10:41 AM +UTC
- Which transaction made the deposit: 0x283a3b024ccb056218b4d2ae31158deec2b07aead18fbfb66b46cd9527db21dc
- The commitment: 0x29227939570d64bbccb243bd0343b0b1206f514ceb6816be7387a81a5813a050
We should also be able to get “secret” and “nullifier” from this information (which are used internally by Tornado Cash), but the compliance tool does not show this information.
If a note is leaked, everything shown above gets to be seen by an attacker and they also get to keep the funds in it! Thus it’s good to keep a good eye on your notes! These notes can be considered as being “toxic waste”.
Note management is also difficult as hardware wallets, such as Ledger or Trezor, do not support them. So users need to store them separately on pieces of paper, offline computers, online computers and such.
Fixing the identified security issues
We have identified two note management issues that needs to be fixed:
1) Leaking a note allows attacker to steal all the underlying funds
2) Leaking a note allows attacker to know the source of the funds
The first issue is easy to fix. When a user is making a deposit, a user could directly point the withdrawal address to the tornado cash system at the same time. This would preferably be a fresh address with no existing transactions or other connections. When the user then wants to withdraw funds, the funds would directly go to this predetermined address. Now, if a note is leaked, an attacker could not steal the funds, instead, they could only initiate the withdrawal process and withdraw the funds to the legitimate users address. While this would be an unfortunate event, it results in no loss of the funds.
When a user is withdrawing funds from the current version of Tornado Cash, the user needs to choose how large of a bribe is paid to a relayer to send the on-chain transaction. This is also something that we need to set in stone at the time of deposit, as otherwise an attacker could act as a relayer and steal all the funds by setting the relayer bribe to 100%! We can define the max bribe amount, and then at withdrawal time, an user can choose a bribe up to this limit. This reduces attackers’ profits to only a small sum.
This improvement allows us to store our note via a less secure manner, as no one could rob our money by stealing the note anymore. However, the attacker would still end up knowing where the money came from (the second issue).
Hiding the source of funds from a Tornado note
The second issue is a bit more challenging to solve, but even the current version of Tornado Cash has one solution for it. We can perform a “withdraw-deposit ceremony” where a user withdraws their note to a new address, and then deposits it back to the system, resulting in a new note. When such a note is leaked, the attacker can only see the time when the withdrawal-deposit ceremony was conducted last time, but the note no longer points to the transaction that brought the funds to Tornado Cash in the first place.
It is recommended that this ceremony is conducted periodically. As all the deposits that happened after the most recent ceremony cannot be linked to this note. This would reduce the anonymity set significantly.
A big drawback of this ceremony is that it costs a lot of gas to conduct on Ethereum. Also Tornado Cash supports only fixed size notes: 0.1 ETH, 1 ETH, 10 ETH and 100 ETH. So when a withdrawal of 1 ETH is made, the user has to pay some ETH amount to the relayer conducting the withdrawal resulting in the user having less than 1 ETH left. This amount cannot be stored as 1 ETH note anymore! A user would need to get more ETH on this account somewhere, or store the note in multiple 0.1 ETH notes to be able to return the funds back to Tornado Cash. Ugh!
Conducting the withdraw-deposit ceremony off-chain
A straightforward idea to fix the issue is to move the on-chain ceremony to off-chain, but how? Let’s look at how Tornado Cash works currently and then think how we could perform the same off-chain.
Tornado Cash deposit
1) A random secret and random nullifier is generated by the user
2) A commitment is generated as commitment = PedersenHash(secret, nullifier)
3) A transaction is sent to the Ethereum where ETH amount deposit is made and our commitment is stored on a Merkle tree on Tornado Cash contract
(https://github.com/tornadocash/tornado-core)
Tornado Cash withdrawal
1) User makes a zk-snark proof that he knows a merkle path to the commitment leaf and the preimage to this leaf (secret, nullifier).
2) User reveals nullifier to the contract
3) It’s checked that proof is valid and that nullifier is not used, if so the user is able to withdraw and the nullifier is marked as spent. The same note won’t function again because the nullifier is already spent.
When looking at the protocol explanation above, we can come up with one simple idea to fix both of our issues. We can make a Tornado Cash deposit and then right away make the withdrawal proof for it. Then instead of sending the proof right away to a relayer it’s kept and the initial note is scrapped. When a user would then actually want to withdraw, the proof is sent as normally. When the note is scrapped and only the proof is kept, the attacker cannot change the withdrawal address (the issue 1) and the withdrawal proof doesn’t directly contain information that is directly tied to the deposit transaction (the issue 2).
However, the proof is tied to the merkle root of the time when the withdrawal proof was made. This would reveal information about the age of the note, but would not completely deanonymize us if leaked. However, if all Tornado Cash users would always perform this ceremony right after deposit, it would make it quite easy to deanonymize users.
To get away from this new issue, we could have two computers. One computer would be kept securely (a cold wallet) while the other would act as a hot wallet. The cold wallet would contain our toxic waste note, and the hot wallet would only contain these withdrawal proofs. The cold wallet would then be used to periodically generate new proofs and these new proofs would be stored on the hot wallet. Upon generating new proofs, the old proofs would be discarded.
This scheme doesn’t completely get rid of the toxic waste issue, but it would allow secure and fast spending of the notes when funds are needed.
While the mentioned scheme is already an improvement on the old scheme, can we do better? The answer is Yes! But this requires significant changes on the core of the Tornado Cash contracts.
Recursive zero knowledge proofs
The solution is recursive zero knowledge proofs: A proof that contains another proof which could even contain another proof and so on. This is possible with ZK-SNARK proof technology that Tornado Cash already uses. Here’s a good introduction on how recursive ZK-SNARKs work and how they can be used for batching of transactions. The use case is a bit different, but the idea is the same.
Here’s a proposal how we can leverage recursive proofs with Tornado Cash like system to fix the issue 2 off chain:
Let’s denote Tornado Cash commitment merkle roots at each time step t as M(t). We also add a new merkle tree construct HM(t) that contains all historical commitment merkle roots M(t)’s up to t: HM(t) = MerkleTree(M(0), M(1), …, M(t)).
1) t = 0: At deposit, a commitment is made: commitment = Pedersen(secret, nullifier), this is stored to the commitment merkle tree: M(t = 0). The new updated root M(t = 0) is also stored in the HM(t = 0) merkle tree.
2) t = 1: We make a ZK-SNARK proof that our commitment is in the current merkle root M(t = 1) (Similar to Tornado Cash withdrawal, except we don’t submit this on-chain). We can now discard our secret.
3) t = 2: As we now have a proof that our commitment is in the commitment merkle tree M(t = 1), we can make a proof that HM(t = 2) contains a merkle root that contains our commitment, with our nullifier.
4) t = 3: We can now keep creating recursive proofs that HM(t = 3) contains a merkle tree root (HM(t = 2)) that contains our commitment, with our nullifier. Our recursive proof also validates the previous proof, to be sure one cannot make recursive proofs about invalid proofs.
We keep looping over step 4 periodically and always discarding the previous proofs. We keep the valid nullifier, and submit it on-chain with the recursive proof when we are ready to withdraw. If a note is leaked, it would only leak information about the note’s age since the last rolling.
The protocol proses one interesting challenge: When a proof is updated to the most up to date merkle tree and the old proof is discarded, a chain reorg can happen. This causes our new proof to be invalid if Tornado Cash deposits are made in different order than they were made in our proofs! To get around this problem, we could always keep e.g. three newest notes, and always when generating new proofs, we check that our newest note is still included in the blockchain. If it’s not, we generate the new proof from a bit older note. One other way around this issue is to always keep the newest note, but never generate it at the top of the chain, but farer away, as the top has the highest chance to get reorged.
The new procedure has a couple more drawbacks compared the old Tornado Cash system:
1) We need to have a internet connected computer that periodically fetches the new updated merkle tree and rolls the recursive proofs on top of the old proofs. However, this is only optional, if the user does not want to do this, Tornado Cash would function as it used to.
2) The gas cost goes up a bit as we need to maintain yet another on-chain merkle tree.
3) Creating recursive proofs takes longer time than creating simpler proofs. However, on-chain computing effort should be about the same.
4) A common complaint regarding ZK systems is that they are complex. This would further increase the complexity of a relatively simple ZK system.
Even with these drawbacks, I don’t feel any of them are crucial. The suggested changes make Tornado Cash notably more secure. The scheme makes it possible for an user to store their notes on a relatively insecure device. Like save them in a password manager without worrying too much about their host being compromised and losing their money or their anonymity. Only losing a note altogether would result in a loss. The insecure device should not maintain logs of the old notes thought, as leakage of logs would leak your anonymity!
No more sweaty hand note management anymore! Hurray!
Thank you for Kobi Gurkan and experience for the feedback.
