Adding an anonymity revoker to Tornado Cash: Design
The ideas for this article were developed in collaboration with César Descalzo.
Launched on Ethereum in 2019, Tornado Cash [1] is one of the most popular cryptocurrency privacy protocols in the space. It allows users to deposit ETH (and other ERC-20 tokens) into a privacy pool from a source address $\alpha_s$ and then withdraw it into a destination address $\alpha_d$ without $\alpha_s$ and $\alpha_d$ ever being linkable, thus providing a strong form of privacy. There are contexts, however, where one may wish to give a certain entity, and only that entity, the power to deanonymise the users - that is, link the deposit from $\alpha_s$ to the withdrawal into $\alpha_d$, thus tracking the flow of assets. Compliance is one obvious case where such a mechamism could be of interest.
In this article, we propose a small modification to the Tornado Cash protocol which allows any holder of a certain secret deanonymisation key $sk$ to perform the aforementioned linking. Section 1 goes over the original Tornado Cash protocol in some detail. In section 2, we introduce the modified deanonymisable design, with section 3 giving some intuition of the security guarantees afforded by the proposed scheme. The reader is warned that the design is rather abstract and does not delve into many fundamental implementational aspects such as the choice of parameters and primitives.
1. Tornado Cash refresher
Let us devote a few lines to recalling how Tornado Cash works at a high level. The specifics of how these transactions proceed in practice are somewhat more complex, but it suffices for this post to distill the protocol down to its central ideas.
At its core, Tornado Cash is a smart contract $C$ that holds a certain amount of an asset - which we will assume to be ETH for simplicity - and exposes two basic functions: $C_{\mathsf{deposit}}$ and $C_{\mathsf{withdraw}}$. Initially, a user generates a random value (technically, two) and transforms it in order to obtain a commitment $c$ and a nullifier hash $h$. They then call $C_{\mathsf{deposit}}$ (on-chain), transferring a certain amount of ETH to the contract and asking it to store the commitment. At a later time, they can invoke $C_{\mathsf{withdraw}}$ to retrieve the funds by sending to the contract the desired destination address $\alpha_d$, the nullifier hash and some additional data proving they are the rightful owners of the funds. The contract then performs a number of checks and, if satisfied, transfers the ETH to $\alpha_d$. The following properties are essential:
The contract does not delete the commitment $c$ from its storage (which is public) upon withdrawal: this would allow any observer of the chain to relate $\alpha_s$ and $\alpha_d$ as the addresses with triggered the creation and destruction of $c$, respectively. In fact, the call to $C_{\mathsf{withdraw}}$ does not even provide $C$ with the commitment. Double spending is prevented by the next two points instead.
The nullifier-hash check in $C_{\mathsf{withdraw}}$ allows the user to retrieve the amount of funds they deposited into the commitment that was generated together with that hash. As we will see in a few lines, this guarantee is cryptographic in nature: it is computationally infeasible to produce two different valid nullifier hashes for the same commitment.
Upon successful withdrawal, $C$ appends the received nullifier hash to a list in its storage, rejecting any subsequent withdrawals that attempt to reuse previous nullifier hashes.
Crucially, the calls to $C_{\mathsf{deposit}}$ and $C_{\mathsf{withdraw}}$ are public: everyone on the blockchain can see the address $\alpha_s$ that triggers the former as well as the address $\alpha_d$ that is specified as the destination in the latter. This is simply a consequence of how blockchains with the account-based model operate.
Before delving into the exact shape of the protocol, it should be stressed that, even though the cryptographic scheme in Tornado Cash realises the above requirements without directly revealing the connection between the source and destination addresses, there exist techniques which could potentially provide such a link. Privacy pool deanonymisation is a deep and much-researched topic relying on notions such as transaction timing and anonymity-set study, which are far beyond the scope of this post.
Anonymity preservation is also the reason why all commitments in any given privacy pool must have the same value, a detail we have conspicuously avoided so far. Specifically, if address $\alpha_s$ were to deposit, say, 2.423 ETH into the pool in the form of a commitment, and later on another address $\alpha_d$ were to withdraw that exact amount, privacy would be shattered. More formally, the anonimity set of $\alpha_s$ consists of the addresses which deposited exactly 2.423 ETH into the pool - a group which is likely to be unacceptably small. For that reason, Tornado Cash offers several pools, each of which operates only on commitments of one concrete value, which in the case of ETH ranges from 0.1 to 100 ETH in powers of 10. For a more detailed relation of the pools, cf. [2]. In this post, we will restrict to a privacy pool with a single fixed ETH amount $\varepsilon$. It should be pointed out that more sophisticated privacy protocols, including the evolution of Tornado Cash (Tornado Cash Nova), allow for variable amounts by using more sophisticated deposit and withdrawal schemes.
There are three main cryptographic primitives involved in the Tornado Cash protocol: hash functions, Merkle trees and zkSNARKs. Although familiarity with these is highly recommended, here is a very brief description of each which should aid with comprehension of the remainder of the explanation:
A hash function $H$ takes in a bit string of arbitrary length and outputs a bit string of fixed length. Intuitively speaking, the output should look random (even though the function is deterministic) and it should be infeasible to construct two different inputs yielding the same output.
A Merkle tree allows a party to commit to a list of values $l_1, \ldots, l_n$ (the leaves) in the form of a single one $o$ (the root), which can be exposed to the public; and later on, prove to any other party that a specific value $l_i$ was at a specific position $i$ in original list by providing a short proof (containing approximately $\log(n)$ elements). It should be infeasible to construct valid proofs that two different elements were at the same position in the list.
A zkSNARK (zero-knowledge succinct non-interactive argument of knowledge) enables a party to prove to another one that they know a value $w$ which is in a certain relation $\mathcal{R}$ with another value $x$ (which we write as $(x, w) \in \mathcal{R}$), where both $x$ and $\mathcal{R}$ are publicly known whereas $w$ is kept secret all along. Succinctness refers to the fact that verifying such a proof should be much faster than manually checking $(x, w) \in \mathcal{R}$ provided $x$ and $w$, whereas non-interactivity means that the party holding $w$ can produce such a proof without active participation from the party they wish to convince (which only receives the proof afterwards).
In the case of the original Tornado Cash protocol (whitepaper here), the chosen primitives were:
The Pedersen hash function on the Baby-Jubjub elliptic curve, which (imprecisely speaking) on input $x$ outputs the point $x \cdot G$ for some fixed $G$. Both the scalar field of the curve (onto which $x$ is projected) and its field of definition have elements which are approximately $256$ bits in size. The output hash is typically compressed by providing only the first coordinate, which lies in the latter field denoted by $\mathbb{F}_p$ here.
The Merkle tree has $n = 2^{20}$ leaves (and therefore height $20$) and is constructed using the MiMC hash function] $\mathbb{F}_p \times \mathbb{F}_p \to \mathbb{F}_p$ (cf. [3]).
The zkSNARK of choice is Groth16 over $\mathbb{F}_p$, which has constant-size proofs and very fast verification times, making it very appealing for on-chain verification (which $C_{\mathsf{withdraw}}$ must perform).
The privacy pool’s smart contract $C$ stores the following:
A list $L_o$ of latest roots, which starts off empty. This list has a predefined maximum length $\lambda$, set to 100 in the whitepaper.
A list $L_h$ of nullifier hashes, which starts off empty.
A Merkle tree $T$, which we refer to as the commitment tree, initially resulting from compressing $2^n$ uninitialised leaves into a root (an uninitialised leaf can be represented by the value $0$, for instance). The height $n$ is set to 20 in Tornado Cash. Note that the pool can never receive more than $2^n$ deposits in total, since each commitment is stored in a leaf and does not get removed upon withdrawal, as already explained.
We note that, in practice, the two lists above can be stored as trees for faster search; and only part of $T$ needs to be stored (the path from the last initialised leaf to the root).
In addition to the aforementioned stored values, $C$ has its own ETH balance which will grow and shrink in increments of $\varepsilon$.
We are now in a position to outline both protocol algorithms ($\mathsf{deposit}$ and $\mathsf{withdraw}$) from the user and pool’s point of view:
Deposit
A user with Ethereum address $\alpha_s$ holding at least $\varepsilon$ ETH generates the deposit information as follows:
$\mathsf{deposit}() \to c, k, r$:
- Sample two 248-bit strings $k, r \xleftarrow{R} \{0, 1\}^{248}$ uniformly. These are called nullifier and secret, respectively.
- Compute the commitment $c = H(k \Vert r)$, where $\Vert$ denotes concatenation.
We note that the secret $r$ is called randomess in the whitepaper (hence the notation); our nomenclature, on the other hand, agrees with the public implementation. The commitment $c$ also receives the name note. This commitment is public, whereas $k$ and $r$ should remain secret and together form a decommitment (or coin) $(k, r)$. In practice, the decommitment is stored by a wallet or similar application.
After generating a commitment $c$, the user deposits it into the privacy pool contract $C$ by sending $c$ alongside $\varepsilon$ ETH to the $C_{\mathsf{deposit}}$ function. Upon receiving such a call, the contract executes the following:
$C_{\mathsf{deposit}}(c)$:
- If $T$ is full (i. e. all of its $2^n$ leaves are initialised), abort.
- Add $c$ to the commitment tree $T$ by setting its leftmost uninitialised leaf to $c$ and recomputing all affected nodes up to the root.
- Append the updated root of $T$ to $L_o$. If $L_o$ would have $\lambda + 1$ elements as a result, remove the first one.
- Increase own balance by $\varepsilon$ (this is handled automatically by the blockchain).
Withdraw
Suppose a user has deposited a commitment $c$ as above and has the corresponding decommitment $(k, r)$. In order to withdraw the assets into a destination address $\alpha_d$, they must prove to the pool contract that they know the decommitment corresponding to a commitment $c$ stored in the tree without revealing which commitment that is. In order to avoid double spending, they will expose a nullifier hash $h$ which is bound to that specific commitment but such that $c$ cannot be determined from $h$ without breaking the hash function $H$.
As a preparatory step, the user needs to query the blockchain for the current state of the Merkle tree $T$ stored in $C$. Since $c$ has already been deposited into the contract, one of $T$’s leaves is precisely $c$.
$\mathsf{withdraw}(\alpha_d, c, k, r, T) \to \pi, o, h$:
- Determine the index $i$ of $c$ as a leaf of $T$ as well as the list $s$ of siblings of the path connecting $c$ to the root $o$.
- Compute the nullifier hash $h = H(k)$.
- Produce a zkSNARK proof $\pi$ for the relation $\mathcal{R}_w$ with (public) instance $(\alpha_d, o, h)$ and (private) witness $(c, k, r, i, s)$ satisfying:
- $H(k) = h$
- $H(k \Vert r) = c$
- $s$ is a valid Merkle proof that $c$ is the $i$-th leaf in a $2^n$-level tree with root $o$.
Having computed $\pi$, the user calls the $C_{\mathsf{withdraw}}$ function:
$C_{\mathsf{withdraw}}(\pi, \alpha_d, o, h)$:
- If the root $o$ is not in the list $L_o$ of latest roots: abort.
- If the nullifier hash $h$ is in the list $L_h$: abort.
- Verify $\pi$ with public instance $(\alpha_d, o, h)$. If invalid: abort.
- Transfer $\varepsilon$ ETH from own funds to address $\alpha_d$.
- Append $h$ to $L_h$.
The fact that the above scheme satisfies the desired privacy pool properties follows from the security guarantees of the cryptographic primitives involved. These properties will be discussed in some more detail for the modified protocol in section 3. However, some remarks are in order at this point regarding a couple of aspects omitted from the above explanation in order to keep the cryptography in focus:
Calling $C_{\mathsf{deposit}}$ and $C_{\mathsf{withdraw}}$, like all Ethereum smart-contract invocations, comes at a gas cost. In the context of privacy protocols, this is especially problematic at withdrawal, which often has as its destination a newly created address $\alpha_s$ with no funds and which therefore cannot be used to call $C_{\mathsf{withdraw}}$. The most common way to address this issue is the usage of an intermediary called the relayer, who pays the gas cost upfront and then receives a small part of the withdrawn assets as a fee. Although the relayer role is baked into the Tornado Cash protocol, we omit it here for simplicity.
Determining the updated state of $T$ within $C$ in preparation for the call to $\mathsf{withdraw}$ requires access to the current blockchain state and is often handled by the wallet application, which queries an Ethereum node.
We now clarify two aspects of the protocol which might seem odd at first glance. The reader is invited to ponder on them before reading on:
Why does the contract $C$ need store the list $L_o$ of latest roots instead of only the last one?
Why is $\alpha_d$ included in the public instance of the relation $\mathcal{R}_w$ if it is not featured in any of the relation’s instance-witness conditions?
The reasons are as follows:
There is a delay between the moment the user privately assembles the transaction for $\mathsf{withdraw}$ (determining $T$) and calls $C_{\mathsf{withdraw}}$, and the moment the transaction is included onchain. During that intervening time, other users’ calls to $C_{\mathsf{deposit}}$ could be processed, thus altering $T$. Were $C$ to only store the latest state of the tree, these alterations would render the proof submitted with the call to $C_{\mathsf{withdraw}}$ invalid. Instead, the above system suffices as long as less than $\lambda$ deposits are made between proof generation and withdrawal processing.
This simply prevents copycat attacks, where another party (such as a malicious wallet, relayer or man in the middle) could copy the payload of the original call to $C_{\mathsf{withdraw}}$ - including, most notably, the proof $\pi$ - and simply replace the destination address $\alpha_d$ with another one of their choice. Baking $\alpha_d$ into the relation prevents observers form modifying that piece of data without invalidating the proof (although the specifics of this admittedly depend on the chosen zkSNARK).
2. An alternative design
Suppose we now wish to add the possibility for a certain party, which we call the anonymity revoker, to break the unlinkability of deposits and withdrawals - that is, to connect the source address $\alpha_s$ to the destination one $\alpha_d$. We impose some natural restrictions:
Deanonymisation should not require active participation from any party other than the anonymity revoker. In particular, the depositor/withdrawer should not be able to prevent deanonymisation by refusing to engage.
The costs of deanonymisation should not grow linearly in the number of deposits made into the privacy pool (except possibly for lightweight operations such as list searching).
A natural way to realise requirement 1 is to incorporate into the deposit/withdrawal process a public-key encryption scheme $E$. The anonymity revoker generates a key pair $(sk, pk)$ and shares the public key $pk$, which gets baked into the algorithms as shown below. They can then relate deposits to withdrawals using the secret key $sk$, which may therefore also be called deanonymisation key. We denote the encryption of a message $m$ by $E(pk, m)$ and the decryption of a ciphertext $e$ by $D(sk, e)$ (although we will be deliberately ambigious about the exact spaces where these objects live). In order for the proposed scheme to work, $E$ must be deterministic, which might raise some eyebrows. This fundamental assumption is discussed in section 3.
The privacy pool, once again taking the form of a smart contract $C$, initialises following elements just like in the original protocol from section 1:
The list $L_o$ of latest roots with maximum length $\lambda$.
The list $L_e$ of nullifier-hash encryptions (which replaces $L_h$).
The Merkle tree $T$ initially consisting of $2^n$ uninitialised leaves.
Modified deposit algorithms
A user with Ethereum address $\alpha_s$ holding at least $\varepsilon$ ETH generates the deposit information as follows:
$\mathsf{deposit}() \to c, k$:
- Sample a 248-bit string $k \xleftarrow{R} \{0, 1\}$ uniformly, which is again called the nullifier.
- Compute the commitment $c = H(H(k))$.
This time around, there is only one piece of randomness $k$. In order to compose the hash function with itself when computing $H(H(k))$, the output of the first call has to be cast into $H$’s input type. How to do this and the security of such a composition should be studied on a case-by-case basis. We point out that the proposed scheme still works if the outer hash function is different from the inner one.
When the user calls the contract $C$’s deposit function, the latter proceeds exactly as before:
$C_{\mathsf{deposit}}(c)$:
- If $T$ is full (i. e. all of its leaves are initialised), abort.
- Append $c$ to the commitment tree $T$ by setting its leftmost uninitialised leaf to $c$ and recomputing the affected nodes.
- Append the updated root of $T$ to $L_o$. If $L_o$ would have $\lambda + 1$ elements as a result, remove the first one.
- Increase own balance by $\varepsilon$ (this is handled automatically by the blockchain).
Modified withdrawal algorithms
After depositing a commitment $c$ with nullifier $k$ as above, a user queries the blockchain for the latest state of $C$’s tree $T$ just like before. They then need to prove knowledge of a witness for a slightly more complicated relation than in the original protocol:
$\mathsf{withdraw}(\alpha_d, c, k, T) \to \pi, o, e$:
- Determine the index $i$ of $c$ as a leaf of $T$ as well as the list $s$ of siblings of the path connecting $c$ to the root $o$.
- Compute the nullifier-hash encryption $e = E(pk, H(k))$.
- Produce a zkSNARK proof $\pi$ for the relation $\widetilde{\mathcal{R}}_w$ with (public) instance $(\alpha_d, o, e)$ and (private) witness $(c, k, i, s)$ satisfying:
- $H(H(k)) = c$
- $E(pk, H(k)) = e$
- $s$ is a valid Merkle proof that $c$ is the $i$-th leaf in a $2^n$-leaf Merkle tree with root $o$.
The contracts’s $C_{\mathsf{withdraw}}$ function remains essentially unchanged:
$C_{\mathsf{withdraw}}(\pi, \alpha_d, o, e)$:
- If the root $o$ is not in the list $L_o$ of latest roots: abort.
- If the nullifier-hash encryption $e$ is in the list $L_e$: abort.
- Verify $\pi$ with public instance $(\alpha_d, o, e)$. If invalid: abort.
- Transfer $\varepsilon$ ETH from own funds to address $\alpha_d$.
- Append $e$ to $L_e$.
Deanonymisation
The anonymity revoker only needs to keep track of each commitment $c$ deposited into the pool and its source address $\alpha_s$ (which can be stored in a list or a more search-friendly structure such as a hash map). Once they wish to deanonymise a withdrawal into address $\alpha_d$, they need only explore the (publicly visible) call to $C_{\mathsf{withdraw}}$ and decrypt the nullifier-hash encryption $e$ therein, obtaining the nullifier hash $H(k) = D(sk, e)$. Applying $H$ to the latter recovers the commitment $c = H(H(k))$, which in turn leads to the source address $\alpha_s$ after a list/dictionary search.
The modified protocol has similar costs to its original version, the main difference being that the relation $\widetilde{\mathcal{R}}_w$ contains a (native and in-circuit) call to $E$ (the two calls to $H$ and the Merkle path verification are the same in both cases).
3. Security
Let us explore some of the modified scheme’s security properties. Some of them are shared with Tornado Cash but need to be considered in a new light due the existence of the anonymity revoker, whereas others are unique to the new version. We again stress that these guarantees are cryptographic, that is: breaking them is computationally infeasible and/or relies on events with negligible probability. The reader is warned that the discussion below does not constitute a formal, thorough or careful security analysis and should not be relied upon in critical contexts. In this regard, any comments and corrections are welcome at antonio@np.engineering.
Only commitments deposited into the contract can be withdrawn: More specifically, a withdrawal on nullifier-hash encryption $e$ only goes through if $e$ is of the form $E(pk, H(k))$ for some $k$ such that $H(H(k))$ is in the tree $T$. The zkSNARK proof $\pi$ ensures this with the caveat that, since $c$ is part of the witness and therefore private, an attacker could provide a different commitment than the actual tree leaf - but this is precisely what the security properties of Merkle trees rule out (asuming $H$ is cryptographically secure).
No coin can be withdrawn twice: The function $C_{\mathsf{withdraw}}$ ensures that a successfully withdrawn commitment $c$ is uniquely determined by $e$ as $c = H(D(sk, e))$ (except with neglibible probability). Because $C$ keeps a list $L_e$ of all previous successful values $e$ and rejects them in subsequent withdrawal attempts, the same $c$ cannot arise from two successful withdrawals.
Any commitment can be withdrawn if its nullifier $k$ is known unless a commitment with the same $k$ has been already deposited and withdrawn: Assuming a user has successfully called $C_{\mathsf{deposit}}(c)$ with $c$ of the form $H(H(k))$, nothing can fail in the subsequent execution of $\mathsf{withdraw}$. The only remaining step is $C_{\mathsf{withdraw}}$, which contains three abortion conditions:
The first one is the root $o$ not appearing in the list $L_o$. As already discussed, if $o$ was honestly fetched from the network, this can only happen if $\lambda$ deposits or more were made between root fetching and withdrawal processing. If this is the case, the user can fetch a new root and attempt to withdraw again. This can be mitigated by increasing $\lambda$ if protocol activity is expected to be high (which only comes at the cost of $C$ storing more field elements and searching through a longer list). We stress that, whatever the (non-negative) value of $\lambda$, withdrawals are guaranteed to be possible eventually, since the number of deposits into the privacy pool is limited to $2^n$.
The second one is the commitment $c$ having already been withdrawn. By the validity of the proof $\pi$ submitted for that original withdrawal, $c$ is of the form $H(H(k’))$ for some $k’$ known to the original withdrawer. By assuption of this security guarantee, we can assume $k’ \neq k$. But then either $H(k) = H(k’)$, in which case a collision has been found for $H$; or $H(k) \neq H(k’)$, in which case a collision for has been found as well (note that $c = H(H(k)) = H(H(k’))$).
The last one is the proof $\pi$ failing to verify, which can never happen as long as a valid $k$ is known and $\mathsf{withdraw}$ is executed honestly. This relies on the zkSNARK being complete, which is the case in all schemes used in practice either perfectly or up to a negligible soundness error (i. e. an honestly generated proof can fail to verify, but that event has negibile probability).
A commitment $c$ cannot be withdrawn if its $k$ is unknown: The validity of the proof $\pi$ submitted upon withdrawal guarantees knowledge of $k’$ such that $H(H(k’)) = c$ by definition of a zkSNARK. If the depositor knew $k$ such that $c = H(H(k))$, the fact that collisions for $H$ should be infeasible to find implies $k = k’$ (in two steps, as in the previous point).
If $k$ is unknown to the attacker, they can not prevent a user who knows $k$ from withdrawing the coin: the analysis here proceeds along the same lines as point 3. It should be noted that the anonymity revoker, despite their knowledge of $sk$, is unable to frontrun the depositor too: the only additional power granted by $sk$ is the recovery of $H(k) = D(sk, e)$, but withdrawal requires a proof of knowledge of $k$, which should be impossible to compute even when having $H(k)$ at one’s disposal.
The proof $\pi$ is binding: one can not use the same proof with a different nullifier-hash encryption or another recipient address: This is contingent on the non-malleability of chosen zkSNARK, since $\alpha_d$ is not restricted by the proven relation $\widetilde{\mathcal{R}}_w$. It can indeed be achieved with a suitable zkSNARK choice (note that Groth16 is malleable in its original form, cf. here for more information on the subject: https://geometry.xyz/notebook/groth16-malleability - thanks goes to Marti Górny for pointing this out!).
Every withdrawn commitment can be deanonymised: Withdrawal requires the validity of a proof $\pi$ with public instance $(\alpha_d, o, e)$ guaranteeing that a commitment $c = H(D(sk, e))$ is in the tree $T$ (with root $o \in L_o$). Having knowledge of $sk$ and the address $\alpha_s$ which placed $c$ into $T$ (which is public) enables deanonymisation.
Only a party with knowledge of $sk$ can deanonymise: Deanonymising a withdrawal with proof $\pi$ on public instance $(\alpha_d, o, e)$ is synonymous with finding the associated commitment $c$ (which can then be tracked to recover $\alpha_s$ - or the other way around from a security-reduction perspective), that is, computing $c = H(D(sk, e))$. The public information available to an attacker without knowledge of $sk$ consists of:
The tree $T$ which contains all possible candidates for $c$ as well as the (possibly outdated) root $o$. For commitments deposited honestly, this candidate is of the form $H(H(k’))$ for some $k’$ - but this need not be the case for all leaves in the tree.
The nullifier ciphertext $e$ reflected in the instance.
The destination address $\alpha_d$, which is mathematically unrelated to all other objects.
First note that having access to candidates for $c$ does not allow an attacker to recover $H(k’)$ assuming $H$ is secure. In order to conclude that $k’$ itself cannot be recovered, however, we need to introduce an important assumption: the composition $H(H(-))$ should itself be a cryptographically secure hash function. We defer the consideration of what this should exactly mean to a more detailed analysis. It should nonetheless be noted that, in general, composing two hash function reduces the bits of security of properties such as collision resistance. Were $k’$ to be recovered for each candidate leaf, hashing them and then encrypting them with $pk$ would recover $e$ and thus break anonymity (and, more importantly, allow for malicious withdrawal).
Computing $D(sk, e)$ from $e$ without knowledge of $sk$ should be infeasible if $(E, D)$ satisfies reasonable encryption security guarantees. Finally, arguing why $c = H(D(sk, e))$ cannot be recovered directly without computing the intermediate value $D(sk, e)$ is tricker to do abstractly due to the difficulty of ruling out interactions between $H$ and $D$ (which should still have negligible property if $sk$ is sampled from a large space). We will not pursue the issue further at this point.
Leakage of the secret key $sk$ breaks anonymity but does not enable malicious withdrawals: It might seem like knowledge of $sk$ only provides an attacker with increased capabilities after withdrawal, since only then is $e$ (which is encrypted using $pk$) known. This logic would however be flawed as a malicious intermediary (as before: wallet application, relayer, man in the middle or similar) could have access to $e$ before the withdrawal were processed. In any case, even with knowledge of a valid $e$, and therefore of $H(k)$, the attacker would need to find a preimage $k’$ of $H(k)$ under $H$, the knowledge of which is required to construct a new proof $\pi’$ with modified destination address $\alpha_d’$. But achieving this is infeasable if $H$ is a cryptographically secure hash function.
The above discussion should illustrate why it is crucial for $C_{\mathsf{withdraw}}$ not to store $e$ in $L_e$ if the proof $\pi$ is invalid, as doing so would allow men in the middle to lock depositors out of their funds. This was already taken into account in the original Tornado Cash protocol.
Regarding the determinism of $E$, non-random encryption functions (such as “textbook RSA”) are generally frowned upon, and with good reason: they fail to meet basic requirements such as semantic security. However, the role of $E$ in the proposed scheme is to encrypt $H(k)$, where the hash function $H$ intuitively masking the properties of $k$ that $E$ could leak. This is far from a security argument and, as stated above, the choice of $E$ and $H$, as well as their potential interaction, is a critical aspect to study when implementing the proposed protocol.
On that note, replacing $E$ by a more sophisticated encryption scheme could allow for a protocol with more fine-grained deanonymisation control. An obvious example would be a $k$-out-of-$n$ scheme where $k$ parties from among $n$ would need to collaborate to decrypt $e$, and hence also to deanonymise a withdrawal. Those considerations, however, are best left to future work.
References
[1] Tornado Cash whitepaper: https://berkeley-defi.github.io/assets/material/Tornado%20Cash%20Whitepaper.pdf
[2] How does Tornado Cash work? https://www.coincenter.org/education/advanced-topics/how-does-tornado-cash-work
[3] MiMC hash: https://byt3bit.github.io/primesym/mimc
Author: Antonio Mejías Gil