# Sandscreener - Project Description

Sandscreener is a full-stack set of tools that enables a Tornado Cash user (User) to *anonymously* prove to an interested party (Auditor) that the User's deposit address is not in a blocklist specified by a verified third party (Editor).

## Original Tornado Cash

In the original Tornado Cash, the User is proving that they have deposited funds into a smart contract pool to be able to withdraw the said funds. The withdrawal is performed after some delay and goes to a user's address different from their deposit address. Since the proving process does not leave any record and is anonymous, it effectively decouples the deposit and the withdrawal addresses.

Upon the User's deposit, the Tornado Cash generates a deposit ID whose hash is stored publicly in the Tornado contract and a withdrawal ID that is known only to the User (generated in the frontend and recorded by the User). The deposit and withdrawal IDs are cryptographically linked, so it is easy to verify their relation by performing certain hashing operations. Therefore, from the viewpoint of Tornado Cash, when a user comes to withdraw their funds from the pool, they must prove that there is a publicly recorded deposit ID hash for what they claim to be a withdrawal ID. Zero-knowledge proof (ZKP) is used for it to keep the User's deposit ID unknown to Tornado Cash and any external observer. The ZKP is performed on the user end (inside the frontend). The User feeds the deposit and withdrawal IDs into the ZK prover. The prover outputs a true or false value that essentially says that:
* This withdrawal ID is indeed linked to some anonymous deposit ID;
* That anonymous deposit ID's hash was indeed recorded in the Tornado Cash contract.
The User is then allowed to perform the withdrawal to their other address.

## The Problem

In the described system, User's deposit address is only linked to the deposit ID, and the User's withdrawal address is only linked to the withdrawal ID. Therefore, the withdrawing User can't prove anything about their deposit address (e.g., the source of funds) without openly (as opposed to anonymously) proving the relationship between deposit and withdrawal.

## Sandscreener - The Solution

The Sandscreener aims to prove that the users' deposit ID is not included in a given blocklist without revealing anything more than the withdrawal ID (as in the original Tornado Cash). The original ZKP of Tornado Cash checks that the user deposit ID was recorded in a smart contract. The deposit IDs are recorded into a tree-like cryptographic data structure. This kind of data structure is convenient to prove the inclusion of some ID because only a few pieces of data are necessary for the proof (there is no need to go through all the recorded IDs to find the one in question). The problem is that this original data structure includes both blocklisted and non-blocklisted deposit IDs, and it is impossible to know whether the User's deposit ID is blocklisted.

The Sandscreener solves the problem by constructing a similar tree-like cryptographic data structure (exclusion tree) consisting only of blocklisted IDs. The Sandscreener then can prove that the user deposit ID is not included in this data structure by using a very similar check to the original Tornado Cash.

## Practical example

Let's say that the community or some interested party (e.g., OFAC) has composed a blocklist of known "malicious actor" addresses. The Sandscreener then constructs the exclusion deposit tree. Assuming that the number of blocklisted deposits is much less than the number of all the deposits in a certain Tornado pool, any non-blocklisted user can prove their right to withdraw from the pool and simultaneously prove non-inclusion of their deposit address into the blocklist, all while staying anonymous.

## Technical Details
#### Project architecture overview

**Sandscreener Auditor blocklist repository**

Editors can submit their blocklists into the Auditor-maintained smart contract in the form of an IPFS hash of a list file (JSON array of addresses). The Auditor will grant the Editors write access to the smart contract. The smart contract will accept the list from the authorized Editors.

The smart contract also maintains a mapping of the User withdrawal addresses to the array of exclusion proofs.

**Sandscreener User frontend** enables the User to generate and submit to the Auditor the zero-knowledge proof (ZKP) of non-inclusion into a certain Editor blocklist (chosen by the User) by providing their deposit and withdrawal IDs (so-called private note in Tornado Cash). The ZKP performs the exclusion proof by proving two statements:
1) The withdrawal ID corresponds to a certain deposit ID in the original deposit ID tree;
2) The aforementioned deposit ID is not present in the exclusion tree.

Technically, the proof of inclusion is performed using a Merkle tree by providing the path to a deposit ID known only to the User and checking the publicly known tree root. The proof of exclusion is performed using a sparse Merkle tree, where the deposit IDs are treated as numbers and sorted in ascending order. The ZKP then verifies that:

1) The User's commitment value falls between some adjacent deposit ID values in the exclusion tree (but not equal to any of them);
2) The path to those adjacent values (only known to the proving User) corresponds to the publicly known tree root (provided by the Auditor).

The User will then be able to store the proof and sorted tree root in the blocklist repository contract.

**Sandscreener Auditor backend** Auditor backend provides the REST API services:

* for the User to obtain the necessary parameters for the ZKP (e.g., exclusion tree calculated according to the blocklist);
* for the Auditor to accept and verify the ZKP submitted by the User.

The Auditor backend is containerized so that the Auditor can deploy it with minimum effort.