Original authors: Barry WhiteHat, Kobi Gurkan; full spec fleshed out by Koh Wei Jie; developed with assistance from the members of the [Semaphore Society Telegram group](https://t.me/joinchat/B-PQx1U3GtAh--Z4Fwo56A).

# MicroMix: A noncustodial Ethereum mixer based on zero-knowledge signalling

Since Ethereum transfers are fully visible on-chain, anyone who knows a user's address can trace the source of their funds, determine even how much they own, and analyse their on-chain activity. As such, users do not enjoy much financial privacy beyond pseudonymity. Some workarounds to obscure value flows, like using a centralised exchange wallet or a custodial mixing service, however, introduce a high degree of counterparty and surveillance risk. What the Ethereum ecosystem needs is a noncustodial mixer which works through strong cryptography, rather than on trust.

This is a specification for a minimal Ethereum mixer based on zero-knowledge proofs. It improves transaction privacy by breaking the on-chain link between recipient and destination addresses. It allows a set of users to deposit a fixed amount of ETH or ERC20 tokens each (e.g. 0.1 ETH or 100 tokens), and pay a third-party relayer to trustlessly withdraw the ETH or tokens respectively to a fresh address. As the mixer is noncustodial, they can permissionlessly withdraw their own ETH at any time.

Under the hood, the mixer uses the [Semaphore](https://github.com/kobigurk/semaphore) zero-knowledge signalling smart contracts and circuits. At this stage, it relies on a single relayer node, and will only support fixed amounts. Future versions of this mixer will employ a [burn relay registry](https://ethresear.ch/t/burn-relay-registry-decentralized-transaction-abstraction-on-layer-2/5820) to safely reduce centralisation.

> [TOC]

## Simplified user flow

Assume that there are three users who want to mix their funds: Alice, Bob, and Charlie, and a relayer (also known as an operator), Oscar.

1. Alice, Bob, and Charlie each deposit 1 ETH into the mixer's smart contract. This deposit transaction carries a piece of data which commits to their identity.

2. To increase her anonymity, Alice's user interface waits till after midnight UTC time to expose a button, which when clicked, generates a zk-SNARK proof and sends it to Oscar. Public inputs to this proof include the recipient's address and a fee for Oscar. The proof demonstrates that Alice had previously deposited ETH and that she had not already withdrawn it. This step, notably, does not reveal Alice's original identity.

3. Oscar invokes the contract's mix function, which verifies the proof and transfers ETH to the recipient's address. It also sends the a small fee to Oscar.

4. If Alice wishes to withdraw her ETH by herself, she can do so herself, but this will not give her privacy as this transaction will link her depositing and receiving addresses.

## Technical overview


*Figure: Overview of system components.*

The mixer comprises of a user-facing web3 dApp and the relayer's backend server. The dApp allows users to deposit ETH or tokens and submit withdrawal proofs at a predetermined time (specifically midnight UTC). Even though the user relies on the relayer to perform withdrawals transactions, they can opt to use the dApp to withdraw their funds at any time at the cost of some anonymity.

This system is more complex than other dApps which share this pattern web3-client-server pattern. As will be described below, the UI includes an EdDSA keystore and proof generation capabilities, and the relayer's server should have internal daemons to handle a hot wallet and transaction nonces.

## Component specifications

### The Semaphore zk-SNARK circuit

**TODO:** In-depth spec of Semaphore. Alternatively, add it as an appendix. Note that the work to be done on the mixer will entail major changes to Semaphore, so its readme on Github will be obsolete in regards to the mixer.

#### Public inputs
| Name| Description |
|-|-|
| `signal` |The hash of `recipientAddress`, `broadcasterAddress`, and `fee`|
| `externalNullifier` | See below |
| `root` | See below |
| `nullifiersHash` | See below |

Semaphore uses `externalNullifier` and `nullifiersHash` to prevent double-withdrawals from the same user. Semaphore also uses `root` (along with other private inputs below) to ensure that the user is indeed a depositer.

#### Private inputs

All the private inputs to the circuit are the same as those described in the [Semaphore documentation](https://github.com/kobigurk/semaphore#zksnark-statement). At the time of writing, these are:

* `identityPk`
* `identityNullifier`
* `identityPathElements`
* `identityPathIndex`
* `authSigR`
* `authSigS`

#### Trusted setup ceremony

**TODO:** Figure out how to perform a [Powers of Tau](https://github.com/matter-labs/powersoftau) ceremony for a `circom` trusted setup. Also look into the Gnosis team's trusted setup, if they did one.

#### Batched deposits and Pedersen hashes

**TODO:** There is a case to be made about replacing the MiMC hash function in Semaphore with Pedersen hashes for reasons of cryptographic security. As the gas costs for Pedersen hashes before [EIP-1829](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1829.md) and [EIP-1962](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1962.md) are very high, there should also be a way for anyone (such as the relayer) to batch deposits and add them to the Semaphore tree. These two changes are major overhauls to Semaphore. Note that while batched deposits can be done without using Pedersen hashes, if we use expensive Pedersen hashes, we must use batched deposits. This can be done after the minimal mixer.

### The mixer contract

| Storage variable | Type | Description |
|-|-|-|
| `mixAmt` | `address` | The constant amount of ETH or tokens that a user can mix per deposit |
| `semaphore` | `Semaphore` | The address of the deployed Semaphore contract, represented as a `Semaphore` type in Solidity |
| `token` | `address` | If the contract is meant to mix ERC20 tokens, this should be the token contract's address. If it is meant to mix ETH only, the address should be the zero address `0x0000...`.

| Function | For ETH or ERC20 |Description |
|-|-|-|
|`deposit`| ETH | Payble function for ETH deposits |
|`mix`| ETH | Verify a withdrawal proof and transfer ETH to the recipient |
|`depositERC20` | ERC20 | Transfer `mixAmt` tokens from the caller into the contract |
| `mixERC20` | ERC20 | Verify a withdrawal proof and transfer tokens to the recipient |

#### `deposit(uint256 _identityCommitment)`

This function will invoke the Semaphore contract's `insertIdentity()` function, passing on the `identityCommitment` value as the leaf. In turn, `insertIdentity()` updates the identity Merkle tree in the contract. `identityCommitment` should be the Pedersen hash of `identityPk` (the user's EdDSA public key) and `identityNullifier`

`identityNullifier` should be a random 31-byte (253 bits, to be precise) value for each deposit.

#### `depositERC20(uint256 _identityCommitment)`

Does the same as `deposit()` as described above, but instead of accepting ETH, this function invokes the `transferFrom()` ERC20 function of the `token` contract to transfer tokens from the sender to itself.

#### `mix(DepositProof _proof, address payable _relayerAddress)`

`mix` lets anyone with a valid and unspent zk-SNARK proof of a prior deposit release funds to a recipient. The operator pays the gas for this transaction, and receives `_proof.fee` in return. We intend for third party relayers to make these transactions via a [burn relay registry](https://ethresear.ch/t/burn-relay-registry-decentralized-transaction-abstraction-on-layer-2/5820). An economically rational operator will only act on mix requests where the fee is high enough to compensate for the service they provide and the gas they pay.

The function does the following:

1. Validate the zk-SNARK. If it is valid, proceed.
2. Check that `_proof.fee` is less than `mixAmt`.
3. Insert `signal` (from the proof input) into the Semaphore contract's signal hash Merkle tree.
4. Update to the mapping of seen nullifiers in the Semaphore contract to prevent double-withdrawals.
5. Send `_proof.fee` to the relayer at `_relayerAddress`.
6. Send `funds - _proof.fee` to the recipient.

#### `mixERC20(DepositProof _proof, address payable _relayerAddress)`

Does the same as `mix()` but transfers tokens instead of ETH. Note that the fee is paid to the relayer in tokens.

##### The `DepositProof` data structure

The mixer contract will use code from `circom`'s Solidity zk-SNARK verifier. As `circom`'s contract internally defines a `Proof` struct, the mixer's `mix` function uses a struct named `DepositProof` instead:

struct DepositProof {
    bytes32 signal;
    uint[2] a;
    uint[2][2] b;
    uint[2] c;
    uint[4] input;
    address recipientAddress;
    uint256 fee;
}

The values in `input` are:

1. `root`
2. `nullifiersHash`
3. `signalHash`
4. `externalNullifier`

The `signal` input to the zk-SNARK, also referred to as `computedSignal`, is the Keccak256 hash of the `recipientAddress`, `broadcasterAddress`, and `fee`.

### Broadcast server

#### Browser requirements to generate proofs

The UI requires a browser which natively supports the Javascript `BigInt`, such as Firefox 68 (yet to be released at the time of writing) or Chrome 67 and above.

#### web3

The browser should be web3-enabled — that is, it should have a way to sign and send Ethereum transactions, such as the [MetaMask](https://metamask.io/) extension. The UI should also intelligently keep track and display the user's selected wallet via an on-screen widget. Good examples include those from Uniswap and Radar Relay.

*Figure: The wallet widget from [Radar Relay](https://app.radarrelay.com/)*

#### Withdrawals at midnight, UTC

To increase the anonymity set, the UI will force the user to wait till after midnight, UTC time, before they can perform a withdrawal. The UI will only show a button to let the user withdraw funds after midnight. This restriction is only at the UI level.

This approach is a response to an initial technique of waiting for a certain number of deposits or a random time interval, whichever is longer. Said technique, however, would make the mixer vulerable to spam attacks where a user can be deanonymised by an attacker which fills up the deposit limit such that the effective anonymity set of the victim is only 1. Downsides to this technique, however, include the fact that this technique does not *strongly guarantee* a large anonymity set, especially when usage of the mixer is low.

Additionally, wait times can be adjusted such as once every 6 hours or once an hour.

[Olivier from Argent](https://twitter.com/oli_vdb) contributed this idea and the above analysis.

#### EdDSA keystore

The UI will create an EdDSA key each time a user makes a deposit. A user's EdDSA key is essential for them to generate a withdrawal proof. Without this key, they cannot mix or withdraw their funds. As such, if they lose their key, they will lose any funds deposited using it.

The UI ensures availability of keys by storing them in the brower's localStorage. To keep the MVP minimal, which only handles small amounts of ETH, we do not encrypt the key.

# Stage 2 ideas (for reference only)

## EdDSA key encryption

UIs which handle larger amounts, should encrypt it with a password that only the user knows. **TODO:** The internal mechanism for key encryption and storage. Check out [Hedgehog](https://hedgehog.audius.co/), which stores an entropy key in the user's localStorage and uses AES-256-CBC along with a username and password to encrypt a BIP-32 seed. Their approach should be examined and adopted if it makes sense. Another good approach is to use NaCl, which offers safe defaults. Also figure out how to isolate EdDSA key management code from the rest of the UI as we need to prevent NPM supply chain attacks. This may entail implementing enhancements to wallets to create a standard EdDSA signing API.

Also see the [App Keys standard](https://ethereum-magicians.org/t/eip-erc-app-keys-application-specific-wallet-accounts/2742/37), currently in progress.

## Security model

**TODO:** Create a security model around key reuse, backup, and loss. Map out risks and potential recovery mechanisms if a user loses their EdDSA key, or if it is stolen.

### EdDSA key reuse

**TODO:** check whether it's okay to reuse keys

### EdDSA key compromise

There is a risk that if a user's EdDSA key is stolen by an attacker, such as if malicious code finds its way into the frontend via an NPM security hole and extracts it from `localStorage`.

### EdDSA key loss

#### Process flow of withdrawal batching

Once a user makes a deposit, the UI will force them to wait a random amount of time (e.g. between 10 and 30 mins), and then generate the proof required to perform the withdrawal. The proof is then sent to the broadcaster, but it must have enough proofs to batch together to provide a strong enough anonymity set.

##### HaRold's notes on batching multiple proofs into one

Note that this differs from the MVP proposal of sequentially processing an array of multiple proofs.

> [name=HaRold] Batching proofs together does three things:
> 1. Aggregate gas saving, would only require 1 zkSNARK proof per batch
> 2. Obscures ordering of withdraws from on-chain contract, makes chronological window more fuzzy by bucketing payments into same timeframe/epoch
> 3. Batch must support 1-N transactions (with N being the maximum), otherwise low transaction volume will block withdraws if a full batch of N is required.

> [name=HaRold] Problem with batching: the anonymity relies upon the user submitting the zkSNARK proof to the chain. Using [Groth16BatchVerifier](https://github.com/matter-labs/Groth16BatchVerifier) you can get a slight cost reduction when verifying multiple proofs, but without recursive SNARKs (or snark-inside-snark verification), or verifying ring-signatures inside a zkSNARK, you would lose all anonymity between the user and the transaction relayer.

Let the safe minimum anonymity set be `n`. In practice, this could be around 6 to 8. The user may also opt for extra privacy, which entails a larger anonymity set `k`. Since the Semaphore contract stores a history of up to 100 Merkle tree roots (currently an arbitary number), that is the maximum value of `k`.

> [name=HaRold] I don't think 6-8 is a safe number for an anonymity set, but it's the cross-over point where a ring linkable ring-signature of 6-8 participants becomes equivalent in gas price to a zkSNARK proof.
> An anonymity set of hundreds to thousands is much better, and is achievable using both linkable ring signatures (with multiple rounds of mixing) or a zero-knowledge proof (e.g. a zkSNARK) of set membership (where the anonymity set is continuously growing the longer you delay your withdraw).

There needs to be further research to decide on the exact values `n` and `k`, where there are acceptable tradeoffs between privacy and waiting time for the minimal mixer.

Given the above context, consider the process flow from the broadcaster's point of view. We assume that there are no other anonymity set sizes besides `n` and `k`.

The broadcaster keeps track of two lists of proofs `b[]` and `c[]`. Each proof list has a UUID. It also has a threshold value `t` between 1 and 100 whose use will be described below.

Whenever the user submits a proof via a `submitProof(proof, minAnonSet)` API endpiont, the broadcaster follows these steps:

1. If `minAnonSet == n`:

1.1. Generate a random value `r` between 0 and 100.

1.2. If `r > t`, append `proof` to `c`. Next, if `len(c) == k`, asynchronously dispatch `c` to the `mix()` contract function.

1.3. If `r <= t`, append `proof` to `b`. Next, if `len(b) == n`, asynchronously dispatch `b` to the `mix()` contract function.

2. Otherwise:

2.1. Append `proof` to `c`.

2.2. If `len(c) == k`, asynchronously dispatch `c` to the `mix()` contract function.

3. Respond with a success code, and if the `mix()` contract function was invoked, its transaction hash.

In effect, this algorithm randomly funnels 1 out of 5 users who do not opt for extra privacy to the higher anonymity set of size `k`. This means that the users who do opt for extra privacy do not have to wait for up to `k-1` other users who want extra privacy, and `100 - t`% of users who go with the default option can enjoy extra privacy. The downside is that `t`% of users who go with the default have to wait slightly longer to get their funds mixed.

Note that `t` is an arbitary value. To determine an optimum `t`, one should consider the estimated percentage of users who want extra privacy and the ratio `n : k`.

# Original spec (for reference only)

## Roles
1. User who deposits eth and wants to send them to another address.
2. Broadcaster who wants to pay for user's transactions and get a fee for it.

## Deposit
`deposit(uint256 identity_commitment)`
1. Send a fixed denomination to the smart contract as well as a public key.
2. The smart contracts checks the amount and token being sent.
3. The smart contract adds your public key to the merkle tree

## Broadcaster registration
`register(address pubkey, string tor_address, uint256 fee)`

There is a smart contract where anyone can register to be an operator by posting a mapping for their public key to tor address as well as the fee they charge in wei, which they can update.

User can select any of these operators to broadcast their transactions. The operator is selected via `burnedFee` weighted by their fee requirement and some randomness.

## Broadcaster node

1. People who want to withdraw connect to the broadcaster via tor
2. They send the broadcaster a snark proof
3. The broadcaster waits a random amount of time less than 3 minutes and then broadcasts the proof
4. The broadcaster validates the proof
5. The broadcaster checks that that proof has not been broadcast already
6. The broadcaster checks that the fee of that proof is enough to pay their costs.
7. The broadcaster broadcasts the proof as part of a batch of other proofs.
8. The smart contract processes them and sends the funds them as follows.

## Withdraw

struct proof {   
        bytes memory signal,
        uint[2] a,
        uint[2][2] b,
        uint[2] c,
        uint[5] input // (root, nullifiers_hash, signal_hash, external_nullifier, broadcaster_address)
}
withdraw(proof[] proofs)

`input = hash(recipient, broadcaster, fee)`

For each proof in proofs we check
1. Anyone can call the contract with a snark proof.
2. The contract validates the proof
3. Takes the recipient address from the snark public input.
4. Takes the broadcaster from the public input.
5. Checks that the fee of the transaction matches the fee that the smart contract quotes.
6. Takes the fee from the public input of the snark and sends the fee to the broadcaster
7. Sends the funds - 2 * fee to the recipient
8. Sends the fee to the broadcaster
9. Burns the remaining fee to discourage griefing.
10. The amount of fee that a given operator has burned is stored in `burnedFee[address] -> uint256` mapping.
11. This can be used to select the operator to use.

## Griefing

There is a possibility that a user sends a transaction to multiple broadcasters. The first one to withdraw gets the fee. The remainder get nothing and lose some of their gas payment.

We mitigate this 5 ways

1. Each transaction burns half of the fee so this attack costs the attacker fee as long as there is only a single operator attacked.
2. We use a random delay of ~1.5 minutes to ensure that only a single operator broadcasts a transaction at once.
3. The operator can validate multiple proofs in a single transaction which means that each replayed proof has marginal cost of checking the nullifier mapping + call data for the proof + the opportunity cost of including another transaction. This should be less than fee which the attacker needs to burn in order to run this attack. Giving us a griefing factor of less than 1.
4. The smart contract checks the nullifier first and skips to the next transaction if it has already been processed.
5. The broadcaster monitors the tx pool before broadcasting to ensure no one had broadcast the same proof.

## Contract interaction

Think about how to let mixer interact nicely with smart contracts on eth.

## On the way to production

* Pedersen hashes
* Replace Merkle tree hashes with Pedersen hashes.
* **Note:** the Pedersen hashes in EthSnarks may not work with `circom`'s Pedersen circuits.
* Replace insertion mechanism to collect leaves into a list.
* Allow anyone to batch the leaves and update the root using a SNARK proof.
* Sync
* The user's client needs to implement an incremental witness mechanism, such that for their own leaves, the path to the current root is updated with each new inserted leaf.
* Enable a user to synchronize to the latest state of the contract, by an API the operator provides. The operator will give the user all the leaves, allowing the user to incrementally update their witnesses.
* An alternative is allowing a user to directly communicate with their Ethereum node to do that. The disadvantage is a slower sync, since users now have to go over blocks not involving the contract, with no seemingly added benefit of security (assuming the user eventually verifies the root with the current state of the contract).

## Transaction abstraction by abusing front-running bots

1. Turns out there are a bunch of bots on eth that use a bunch of huristics to see if they can make money with transactions.
2. One simple thing they do is replace an address with their own address and rebroadcast check with the EVM if their balance will be increased after the broadcast.
3. I think that this might be a really simple transaction abstraction where we broadcast a transaction and these front runners try see that they can make money if they pay a higher fee for it.
4. The question is that if we broadcast a transaction from an address that has 0 eth will it get sent broadly enough that it these front runners will see it and check that its possible to make money with this tx.

We should do a test to see nodes will propogate 0 value transactions