How does Tornado Cash work?

This article assumes some familiarity with crypto such as hash functions and Merkle trees.

Thanks to Suah Kim for providing valuable feedback and creating the first diagram.

Introduction

One of the most striking aspects of blockchains is that all transactions are public. While this makes blockchains completely auditable, it also means that privacy is difficult to achieve. The desire for privacy on the blockchain led to the creation of Mixers. A Mixer is a third-party service that can be used for making private blockchain transactions. The way it works is that users deposit cryptocurrency into the Mixer account and then can withdraw the same amount of cryptocurrency (minus a fee) into a new account which is unrelated to their original account. Since there are many users making deposits and many users making withdrawals, it’s not possible to know which deposit a particular withdrawal corresponds to. In this way, the user can anonymize cryptocurrency that has been linked to their ID or to a particular event.

One possible way deposits and withdrawals could be linked is by their amount. For example if there is a deposit for 3.518 ETH and a withdrawal for 3.512 ETH then it might be guessed that they correspond to each other. Because of this, for the best privacy the Mixer should only allow deposits of a fixed amount, say 0.1 ETH. This makes it slightly less convenient for the user, but ensures the best privacy. Another way that deposits and withdrawals could be linked is if the withdrawal is made immediately after the deposit. For this reason users are recommended to wait for some time before making the withdrawal.

This diagram shows an example of depositing and withdrawing from a smart contract. It is clear to see that the deposit account “A” and withdrawal account “E” are likely linked because the withdrawal and the deposit amount are the same (3.512 ETH). However, it is hard to say which deposit account is linked with the withdrawal account “D”, because both deposit accounts “B” and “C” deposited exactly 0.1 ETH, the same as “D”’s withdrawal amount.

The weakness with Mixers is that they require users to trust the operator. To withdraw their cryptocurrency from a Mixer, the user sends a message to the operator of the Mixer telling them which deposit was theirs, proving they own the public key that made this deposit and supplying a fresh address for the operator to send their cryptocurrency to. There is nothing forcing the operator to actually transfer the cryptocurrency to the users new address, and nothing preventing the operator revealing which deposit a withdrawal was linked to. To achieve trustlessness the Mixer needs to be operated by a smart contract. But then everyone will be able to see exactly what the Mixer is doing and privacy will be lost, right? Amazingly, No! It’s possible to design the Mixer in such a way that it can operate in public and still maintain privacy. This is done using zero-knowledge proofs, in particular a zk-SNARK algorithm called Groth16.

An example of a zero-knowledge proof

The details of Groth16 work are beyond the scope of this article, but as an example of a zero-knowledge proof think about the following problem: Suppose there is a graph (a set of vertices with some edges between them) and you want to convince your friend that you know a way to colour the vertices of this graph using just three colours in such a way that any two vertices that are joined by an edge have different colours. The straightforward way to do this would be to colour the vertices as required and then show your friend who could check it. However, suppose you wish to keep the knowledge of how to do the colouring to yourself. Is it still possible to convince your friend that you know a way to colour the graph without revealing what it is?

The answer is yes, and it can be done as follows. First put a piece of paper at each vertex and colour the pieces with red, green and blue such that any two vertices joined by an edge have different colours. Then turn all the pieces of paper over. Then ask your friend to pick any two vertices that are joined by an edge and flip the pieces of paper at these vertices to check that they are different. This doesn’t completely convince your friend that all the colours are valid since there may another pair of vertices that are joined by an edge but coloured the same. But then you can permute the colours and play the game over and over again. If there are two vertices joined by an edge that are coloured the same then your friend would expect to get lucky and choose it eventually. If this never happens then they can be convinced that the colouring is valid. More precisely, suppose there is an edge with both ends coloured the same, then the probability that your friend doesn’t choose this edge is E-1/E (where E is the number of edges in the graph). Repeating the game n times, the probability you don’t get caught is (E-1/E)^n, which decreases to zero as n increases. Thus we can prove the vertices of the graph can be coloured using three colours without revealing how. In Tornado Cash the user uses similar ideas to prove that one of the deposits belongs to them without revealing which one.

After committing to the colouring, your friend chooses two vertices joined by an edge and then you reveal that these two vertices are differently coloured (in this example green and blue).

Outline of the tornado cash contract

Now let’s look at the details of the tornado cash smart contract. (We will look at the case where there is a fixed deposit amount of 0.1 ETH.) The contract needs to keep track of the funds that have been deposited into it. This is done using commitments. To make a deposit the user chooses some random input data D and then applies a cryptographic hash function to that data. The output of the hash function is called the commitment C. The user then sends the commitment along with 0.1 ETH to the contract. Because cryptographic hash functions are one way functions, it is not possible to work out the input data D from the commitment C, so only the user knows D.

The contract keeps a record of deposits using a Merkle tree. (Each node of the Merkle tree stores a 32 byte value and each non-leaf node is the hash of its two child nodes). When it receives a deposit it stores the commitment in the next leaf that hasn’t been used yet. The height of the Merkle tree is chosen to be 20, so it has 2²⁰ leaves. After 2²⁰ deposits have been made the Merkle tree will be full and a new contract will need to be created. So when the tree is full, each deposit will have been “mixed” with 2²⁰ other deposits. Choosing the Merkle tree to have greater height would increase the privacy of the protocol, but it would also mean an increase in gas fees. This is because each deposit has to do an update on each level of the tree (along the path from the leaf being updated to the root) so the higher the tree the more updates needed. (It also increases the size of the proof needed for withdrawals).

This diagram shows a Merkle tree of height 4. There have been 3 deposits so far, with commitments C1,C2 and C3. All unfilled leaves of the Merkle tree contain a certain hash called the zerohash. The root of the tree is denoted by R.

To make a withdrawal a user must prove they are the owner of one of the commitments stored in the Merkle tree. They could do this by revealing the secret data D for one of the commitments, but this would link the withdrawal to a particular deposit so privacy would be lost. Instead the user uses Groth16 to create a proof that they are the owner of one the commitments stored in the Merkle tree with revealing which one. The smart contract checks the proof is valid and then sends 0.1 ETH to the withdrawers address.

Deposits & Withdrawals

Next we will look at how deposits and withdrawals work in some more details. The secret data the user chooses when making a deposit actually consists of two 248-bit numbers, the nullifier k and the secret r. Then the commitment is computed as the Pederson hash of the concatenation of k and r

This commitment is then sent to the contract with the deposit, and stored in the next unused leaf of the Merkle tree. (Initially all the leaves of the Merkle tree contain a particular 32 byte value chosen by the developers, which is gotten by hashing the word ‘tornado’ using keccak256.) To keep track of the index of the next unused leaf, the contract stores a variable which is initiated to 0 and incremented each time there is a deposit.

To make a withdrawal, the user computes the hash of the nullifier

Then the user creates a proof P of the following statement:

“I know numbers k and r and an index i and an array of hashes O such that N=H(k) and O is a Merkle proof that the leaf at index i contains H(k||r)”

The user sends the nullifier hash N, the proof P, and an Ethereum address A to the contract. The purpose of the nullifier hashes is to prevent the same deposit being withdrawn more than once. The contract stores a list of nullifier hashes, and every time a withdrawal is made, the contract appends the nullifier hash that was used to this list. Part of the check for a withdrawal transaction is to check that the submitted nullifier hash is not already included in this list.

Relayers

One of the issues that comes up when using Tornado Cash is that if you use your own account to pay for the gas for a withdrawal, then that withdrawal transaction gets linked to your current address. To overcome this issue, Tornado Cash has the option of using relayers. These are third party services that pay the gas for the withdrawal transaction upfront in return for a fee. The way they work is that the user creates their withdrawal request including proof P, nullifier hash N and withdrawal address A, and then sends this data to the relayer. (This can be done over TOR to remain anonymous to the relayer). The relayer then pays for the gas to submit the withdrawal transaction. Then the contract subtracts the gas used plus a fee from the 0.1 ETH and sends it to the relayer and sends the remainder of the ETH to the address specified in the withdrawal transaction. One final thing to note is that the withdrawal address A is included as one of the public inputs for the zk-SNARK proof, so it is not possible for the relayer to steal the user’s deposit by submitting the user’s proof with an altered withdrawal address, as this would invalidate the proof.

In summary, Tornado Cash enables private blockchain transactions by breaking the link between the source and destination of funds. It does this by mixing many user’s transactions together to obfuscate the links between sources and destinations. It manages to maintain privacy, despite being implemented as a smart contract, by using zero-knowledge proofs. One of the drawbacks of the protocol is that it requires fixed amount deposits in order to achieve the best privacy, which can be inconvenient. Another is that it makes use of third parties called relayers, which while not essential to the operation greatly improve usability.