Derecho: Privacy Pools with Proof-Carrying Disclosures

Privacy pools use zero-knowledge proofs to enable anonymous transfers of assets on account-based smart contract platforms such as Ethereum. In a nutshell, these privacy pools enable users to deposit funds into a shared pool, anonymously transfer funds within the pool, and later withdraw funds without linkage to their previous transactions. While these pools offer a valuable service for users who desire privacy on smart contract platforms, they may also be subject to misuse by cybercriminals.

In August 2022, the U.S. Department of Treasury sanctioned Tornado Cash, the largest Ethereum privacy pool, on the premise that it enables illicit actors to hide the origin of funds, citing its usage by the DPRK-sponsored Lazarus Group to launder over $455 million dollars worth of stolen cryptocurrency. This ruling effectively made it illegal for U.S. persons/institutions to use or accept funds that went through Tornado Cash, sparking a global discussion among privacy rights activists and lawmakers.

Against this backdrop, we present Derecho, a system that institutions could use to request cryptographic attestations of fund origins rather than naively rejecting all funds coming from privacy pools. Derecho is a novel application of proof-carrying data, which allows users to propagate allowlist membership proofs through a privacy pool’s transaction graph. Derecho is backwards-compatible with existing Ethereum privacy pool designs, adds no significant overhead in gas costs, and costs users only a few seconds to produce attestations. This blog post provides a high-level summary of this system, which is based on proof-carrying disclosures. For more details, check out the full paper. We also developed an open-source implementation, which is available here.

Potential Solutions

A simple solution would restrict deposits into and withdrawals from the privacy pool to accounts on a specific allowlist.¹ For example, the allowlist might be the set of all public Ethereum addresses that are not on the Specially Designated Nationals List. However, allowlists are expected to vary by jurisdiction, and may be updated dynamically.

An alternative solution is for users to generate attestations when necessary, selectively disclosing information about the provenance of funds withdrawn from the pool. When cryptocurrency is deposited into a privacy pool like Tornado Cash, a digital receipt in the form of a cryptographic commitment is generated, and the depositor retains a secret key required to use this receipt later. A user withdraws $x$ units of cryptocurrency from the pool by presenting a zero-knowledge proof that it knows the secret key of an unused receipt for this exact amount of cryptocurrency, and a keyed hash of the receipt called a nullifier. The nullifier still hides the receipt but prevents it from being used twice. While this zero-knowledge proof reveals little information by default (other than transaction validity), a user could choose to reveal more information about the origin of a withdrawal to an interested party (e.g., an exchange). In fact, zero-knowledge proofs can be used to selectively disclose information about the unique deposit receipt, including membership of the depositing account on an allowlist. This general approach was outlined recently in various online discussions. Similar solutions were proposed more than a decade ago in the context of Tor and blocklisting of IP-addresses.

However, this system of user-generated disclosures becomes more challenging in pools that support in-pool transfers. The recipient of funds must retain the ability to prove facts about its provenance, in particular, that the funds originated via deposits from accounts on a given set of allowlists. We solve this problem using proof-carrying data, a generalization of incrementally verifiable computation that offers a powerful approach to recursive proof composition. When a user makes their first transaction within the pool, the user generates membership proofs for a set of allowlists. Subsequent transactions within the pool generate new membership proofs that are derived from (i.e., prove knowledge of) the previous membership proofs of the transaction inputs and the details of the current transaction. These membership proofs, which we call proof-carrying disclosures, can be verified efficiently and may be communicated directly to the recipient of funds.

Technical Overview

A key goal in the system design was to develop a solution that can be introduced as an add-on component to existing privacy pools on Ethereum and other smart contract platforms. To facilitate adoption of the system, the design should not require changes to the transaction functionality of the privacy pool contract or introduce any significant gas costs to users. Furthermore, it should maintain the existing security properties of the privacy pool while optionally allowing for attestations of allowlist membership.

Derecho assumes the existence of a set of allowlists that are maintained external to the system, where each allowlist contains a list of Ethereum public-key addresses, along with a dynamic accumulator $A$ (e.g., a Merkle tree) which aggregates the allowlists. That is, for each public key $\mathsf{pk}$ on allowlist with identifier $\mathsf{al}$ the element $H(\mathsf{al}||\mathsf{pk})$ is inserted into $A$, where $H$ is a collision-resistant hash function. For simplicity we restrict to privacy pools that manage only one cryptocurrency asset at a time, but the system easily generalizes to pools that manage assets of multiple types. The pool contract maintains an accumulator $R$ of records, where each record is a hash digest (i.e., cryptographic commitment).

When a user first deposits $x$ units of cryptocurrency into the privacy pool from a public Ethereum address $\mathsf{pk}_s$, a record of the form $H(x||\mathsf{pk}_1 || r_1)$ is added to the accumulator $R$, where $\mathsf{pk}_1$ is a shielded public-key address and $r$ is a nonce that will later be used to nullify the record upon a transfer or withdrawal. A transfer transaction may create a new record $H(x||\mathsf{pk}_2 || r_2)$, a nullifier $\mathsf{n} = H(r_1)$, and would include a zero-knowledge proof that a record $c = H(x||\mathsf{pk}_1 || r_1)$ exists in $R$ such that $\mathsf{n} = H(r_1)$. The transfer transaction may also create multiple output records of the form $H(x'||\mathsf{pk}' || r')$, and the zero-knowledge proof would additionally attest that $\sum_i x'_i = x$. A withdrawal transaction contains a similar zero-knowledge proof, but publicly reveals the output amount $y$ and a destination Ethereum address $\mathsf{pk}_d$, at which point $y$ units are withdrawn from the pool and delivered to $\mathsf{pk}_d$.

We define membership of records on allowlists recursively as follows. The initial record created upon deposit is a member of allowlist $\mathsf{al}$ if and only if its source Ethereum address $\mathsf{pk}_s$ is a member of $\mathsf{al}$. A record created as the output of a transfer transaction is a member of $\mathsf{al}$ if and only if all the inputs records to the transfer are members of $\mathsf{al}$. Finally, we say that a withdrawal transaction is a member of $\mathsf{al}$ if and only if all the input records to this withdrawal are members of $\mathsf{al}$. (Note that this final allowlist attestation refers to the withdrawal transaction itself rather than the Ethereum destination address $\mathsf{pk}_d$, which may or may not be on the allowlist for other reasons.)

Since the initial record created upon deposit is publicly linked to the Ethereum source address $\mathsf{pk}_s$ via the on-chain deposit transaction, it is straightforward for a user to produce a membership proof of the deposit record on a list $\mathsf{al}$ by providing a membership proof for $\mathsf{pk}_s$ using the accumulator $A$, which could be verified given the Ethereum transaction log. Producing membership disclosure proofs for the output records of transactions is more subtle. If a user already has membership proofs for all the input records to a transfer transaction with respect to a list $\mathsf{al}$, then it can create a membership proof for an output record of this transaction by proving its knowledge of valid $\mathsf{al}$ membership proofs for all the input records to the transaction. The same could be done for a withdrawal transaction. Since neither the output record nor the transaction log contains explicit references linking it to transaction inputs, but only nullifiers $n_i$ for each input record, the zero-knowledge disclosure proof repeats the logic of the transfer proof: for each $n_i$, it proves knowledge of an input record $c_i = H(x_i||\mathsf{pk}_i || r_i)$ such that $n_i = H(r_i)$ and additionally knowledge of a valid membership proof $\pi_i$ for $c_i$. This recursive proof of knowledge is possible via a proof-carrying data (PCD) scheme.

However, a problem immediately arises: the validity of $\pi_i$ is not actually verifiable against the record commitment $c_i$ alone. For example, verifying the initial membership proof of a deposit record $c$ required checking against the blockchain transaction log to obtain the link between the record $c$ and a source Ethereum address $\mathsf{pk}_s$. Naively, if the public input required to verify a membership includes the entire blockchain transaction log then the recursive zero-knowledge proof statement would become impractically large. The standard trick around this problem is to replace the transaction log public input with an accumulator digest $T$: the membership disclosure proof for a deposit record $c$ now includes both an accumulator membership proof for $T$ of a transaction linking $c$ to $\mathsf{pk}_s$ and an accumulator membership proof for $A$ showing $\mathsf{pk}_s$ is on the list $\mathsf{al}$.

However, yet another subtle complication arises when attempting to produce recursive membership proofs for the output records of transfers. Suppose the user has a membership proof $\pi$ for an input record $c$ to a transfer creating an output record $c'$. Suppose further that the accumulator digest $T$ commits to the transaction log state at the time $t$ that $\pi$ was created, and that the accumulator state $T'$ commits to the transaction log state at the time $t'$ that the new transfer is occurring. The value $T$ is required as input to verify $\pi$, but is unknown to the recipient of the transfer at the time $t'$. Thus, $T$ is not available as a public input to verify the recursive disclosure created for $c'$, rather, the disclosure must prove knowledge of both $\pi$, $c$ and $T$ against which $\pi$ is valid. Moreover, without additional restrictions, the prover would be free to invent a malicious proof $\pi^*$ valid against a $T^*$ unrelated to the true blockchain state at any point in history.

To resolve this problem, we use history accumulators, which commit not only to the current state of a set but also all historical states. History accumulators provide an efficient mechanism to prove that a digest $T$ represents a valid historical state $\sigma$, which can be verified against the current digest $T'$ of the history accumulator. Altogether, these techniques result in a system that only requires a few seconds to produce attestations on a consumer-grade laptop. These attestations can be efficiently verified by the recipient of funds with respect to the current blockchain state. Due to the fact that these proofs do not need to be verified by the smart contract, we were able to leverage recent developments in PCD that trade a larger proof size for very fast proving times.

System Evaluation

We implemented our construction of proof-carrying disclosures using Rust and the Arkworks ecosystem. Our implementation consists of $\approx$ 5500 lines of code and is available open source. The constraints and proof-carrying data primitives are implemented within the Arkworks ecosystem. We instantiate the PCD scheme of [BCLMS21] with the Pasta cycle of elliptic curves. This scheme uses a transparent setup. The constraint count has been optimized through usage of the Poseidon hash function.

We evaluated the performance on a laptop with an Apple M1 Max processor. For a tree depth of 20 and single-threaded execution, the setup time was 5.4 seconds, the proving time was 19.2 seconds, and the verification time was 12.6 seconds. With multi-threaded execution, the setup time was 2.0 seconds, the proving time was 3.4 seconds, and the verification time was 1.9 seconds. The proof size was 6.3 MB for a tree depth of 20.

Future Work

It would be interesting to develop alternative constructions that more directly support blocklist non-membership proofs. The challenge with supporting blocklists more directly is that a user can easily transfer funds from a blocklisted address $\mathsf{pk}_s$ to a fresh Ethereum address $\mathsf{pk}'_s$ before depositing into the privacy pool. The funds might then be transfered several hops within the pool before the blocklist could be updated to include $\mathsf{pk}'_s$. We discuss the tradeoffs between designs based on allowlists and designs based on blocklists in more detail in the full version of the paper.