A technique review and opt on Tornado Cash

In this post, we analyze the design of Tornado Cash and propose some optimization on utility issues. Eigen Network uses Stealth Address and zk-zkRollup to realize a low-gas cost, programmable and easy-to-use privacy layer for the EVM-compatible ecosystem.

The tornado cash includes the following four steps：

Deposit： a user generates a transaction as follows: selects two random numbers $(r_1, r_2)$, computes its hash as a commitment $Com = Hash(r_1, r_2)$, pays a fixed quantity of tokens as well as the commitment $Com$ to a Proxy. The Proxy will send the tokens and commitment $Com$ to a capital pool.

Verify： Miners of the system verify the validity of the transaction. If it is valid, then the token will be added to the capital pool, and the commitment $Com$ will be added to a Merkle tree. Otherwise, reject.

Withdraw： a user generates a zero-knowledge proof: uses his random numbers $(r_1, r_2)$, commitment $Com$ and its Merkle path $Merkle_path(Com)$ as WITNESS to generate a proof; uses the random number $r_1$ to generate a key $image = Hash(r1)$; adds a public address of the receiver in the end.

The content of zero-knowledge proof is as follows:

$pub_input = (Merkle_root, image, address) $

$witness = (r1, r2, Com, Merkle_path(Com)) $

$Circuit(pub_input, witness) = 0$

The specific circuit constraints are as follows:

$image = Hash(r1)$

$Com = Hash(r1, r2)$

$Merkle_root = Hash(Com, Merkle_path(Com)) $

Verify： Miners of the system verify the validity of the proof and the key. If it is valid, then a fixed quantity of tokens will be paid to the address and the key image will be added to a KEY pool. Otherwise, reject.

Analysis:

Advantage: the above principle realizes coin mixing. In the deposit step, Verifiers will gain from the sender, while in Withdraw step, they will gain from the Proxy. Therefore, it can trace the identity of the sender in the deposit step, but it can’t trace the identity of the sender in withdraw step.

Disadvantage: each transaction involves two random numbers $(r_1, r_2)$. If a user needs to pay a big amount of tokens, then a large number of random numbers need to be stored. Once the random numbers are leaked, their consequences are equivalent to the private key leaked.

The other disadvantage of tornado cash

Only a fixed amount of tokens can be paid at a time. Assume that the fixed amount is 10, if a user has 10,000 tokens, then he needs to use the protocol 1000 times. There are too many transactions, resulting in wasting GAS.

Solution:

Deposit: generate ten thousand commitments $Com_1,…,Com_{10,000}$, pays the 10,000 tokens and ten thousand commitments to the Proxy。

Withdraw: If the user wants to take out his 5000 tokens, he uses the corresponding 5000 random numbers to generate a zero-knowledge proof, then the capital pool pays 5000 tokens to the corresponding address.

This optimization has been adopted in the Tornado Cash Nova.

Stealth Addresses

Initialize: In an elliptic curve system. The system generator is G.

KeyGeneration: the private key of a receiver is $(a,b)$, his corresponding public key is $(A,B)$. It satisfies the following discrete logarithm relation: $A=a*G, B=b*G$

AddressGeneration: a sender selects a random number $r$, computes as follows $R=r*G, P=Hash(r*A)*G+B$. Where $R$ is auxiliary public information, $P$ is the stealth address of a receiver. Denote as $(P, R)$.

NewKeyGeneration: the receiver uses his private key $(a,b)$ and the public auxiliary information $R$ to compute his new private key $sk_p=Hash(a*R) + b$

Analysis: the sender and the receiver can be a user or different users. If a user, then the sender computes his stealth address as $(P,R)$, and his corresponding new private keys is $sk_p=Hash(a*R) + b$.

An optimized Tornado cash

Deposit：a user uses the above stealth addresses technique to calculate his stealth address as (P,R) and new private sk_p=Hash(A *R)+ B. calculates two random numbers $r_1=Hash(sk_p,0), r_2=Hash(sk_p,1)$.The rest process of the Deposit is the same as before.

Withdraw： the public address of the receiver is $Address = (P, R) $. The rest process in the withdrawal step is the same as before.

Analysis:

If a user needs to pay a big amount of tokens, then a large number of random numbers need not be stored, as only the receiver can compute the random numbers corresponding with the address.

In the next post, we will introduce our privacy layer’s design.