How Tornado Cash works

Taking the 100 DAI pool of tornado cash as an example, the process of anoninmizing coins takes two steps:

Depositing: Alice, together with other people, send 100DAI-transactions to that pool.
Withdrawing: Alice withdraws her money to new fresh address.

The overall structure of tornado cash

The main idea is that coins get mixed: since there were many people who deposited, observers don’t know whose money was withdrawn. The key problem is in proving, from the viewpoint of Alice’s_new_address, that Alice’s_old_address has deposited money previously, but without revealing Alice’s_old_address.

The smart contract variables

The tornado cash smart contract contains:

Its balance.
All the coins (chunks of 100 DAI) that were depositied, in the form of a Merkle root hash of a Merkle tree of hight 20. If you haven’t seen Merkle trees, read this.
“next” which is a number that represents the next available leaf for storing coins in the Merkle tree.
The Merkle proof for the “next” leaf in the tree.
Nullifiers: certain hashes that represent withdrawn coins.

Tornado cash 100 DAI pool [smart contract] Balance: 500 DAI coins root hash: 0fda45… next: 4 MerkleProof(4): … Nullifiers: [one entry per withdrawn coin] nf

_1

_2

Merkle tree that stores coins, schematically; in reality, the height is 20.

In the above example we see three coins in the Merkle tree, balance 500 DAI, and two nullifiers stored. To explain the rest of the details, it is best to describe the functionality of tornado cash smart contract.

The smart contract functionality

Assume now H $_1$ ,H $_2$ : B→ {0,1} $^{256}$ are two hash functions, where B is a certain set (in fact, Pedersen’s hash functions are used; see the whitepaper at the end).

Alice wants to deposit 100 DAI:

Chooses random k,r in B, and sets coin4 = H $_1$ (k,r)
Writes coin4 in leaf #4 in the tree, and generates a new proof NewMerkleProof(5). (to generate NewMerkleProof(5) Alice only needs the old MerkleProof(5) together with coin4)
Sends [100 DAI, coin4, MerkleProof(5)] to smart contract.
Stores and keeps secret the values (k, r), one note per coin deposited.

Tornado contract does:

Uses coin4 and MerkleProof(4) to compute the updated Merkle root.
Verifies that the proof π = MerkleProof(5) is consistent with the updated Merkle root
If valid: updates variables accordingly

Alice wants to withdraw coin4 to Alice’s_new_address:

Has a note (k, r)
Sets nf = H $_2$ (k)
Proves “I have a note for some (without specifying) leaf in the coins tree, and its nullifier is nf”, by producing the a zk-SNARK proof π that, without revealing [k,r and coin4] proves: (i) coin4 = (leaf #4 of coins root hash) is valid (ii) coin4 = H $_1$ (k,r) (iii) nf = H $_2$ (k)

‣

Remark. To produce such a zk-SNARK, the inputs are the following: (click to expand)

• public statement x = (coins root hash, nf, Alice’s_new_address) • private witness w = (k, r, coin4, MerkleProof(coin4)) • arithmetic circuit C(x, w) = 0 iff: (i) coin4 = (leaf #3 of coins root hash), i.e. MerkleProof(coin4) is valid (ii) coin4 = H $_1$ (k,r) (iii) nf = H $_2$ (k)

For what is a zk-SNARK and how it is produced we refer the reader to modules 1-3 here.

Sends [nf, proof π, Alice’s_new_address] to the smart contract
Smart contract checks: (i) proof π is valid for (coins root, nf, Alice’s_new_address) ⇒ the unrevealed coin4 was indeed deposited by Alice. (ii) nf is not in the list of existing nullifiers ⇒ coin4 was not withdrawn before.
Smart contract sends 100 DAI to Alice’s_new_address

To reiterate important poins:

nf and proof π reveal nothing about which coin was spent.
coin4 cannot be withdrawn again, because its corresponding nf = H $_2$ (k’) is now nullified.
observer only sees the coins (coin1, coin2, …), but doesn’t know which of those coins are withdrawn.
anonimity set of Bob is all the coins deposited to Tornado cash, with the upper limit $2^{20}\sim 1\text{ million}$ people.

Relayers and compliance

There is one problem in the above design: in the withdrawal step, tornado cash smart contract needs gas to send 100DAI to Alice’s_new_address, and therefore Alice needs to provide this gas somehow. If it is paid from Alice’s address, then the fresh address is linkable to Alice…

Tornado’s simple solution is to use an intermediate relay service, in the following manner:

Remark: relays and Tornado cash smart contract also charge a fee.

Another important remark is that, upon withdrawal, user can choose to generate a PDF that de-anonimizes their coins, in order to present it to centralized exchange or some other authority that demands to know the origin of coins (to be sure that the coins were not stolen, for example).

The final diagram that summarizes mechanics

Resources: Dan Boneh’s lecture, Vitalik’s post and whitepaper below.

Tornado Cash Whitepaper.pdf176.9KB