# An EVM compatible P2P mixer

## Motivation and Related Works

### Tornado
Privacy is important and needed. We had a good privacy enhancing protocol on Ethereum. They are shutdowning it.

There are basically three things that led to the "shutdown"[^1] of Tornado:

- relying on interface
- tornado.cash is a brand
- the account based model of ethereum leads to a "account is the center" so basically tornado.cash is a brand and there is _the_ smart contract to go to
- this doesn't happen in the UTXO model
- tornado.cash relies on network effect (aka anonimity set)
- consequence: difficult to spark clones

### Good ol' casinos
in 2009-2013 there were a lot of Bitcoin based casinos online. One of the main features of them was that:
- no KYC
- a big poooling of funds

People were used to "clean" their funds by sending their bitcoin from address A to the casino, play a couple of games, wait for some days, redeem the remaining of their funds to new address B. Since funds were put into a pool and there was no KYC, an external observer (not the casino) was not able to link addresses A and B with enough certainty.

Still, the casino could snitch on you *and* today everything related to crypto has more KYC than other businesses

## Goal

To create a way to pool transactions together and remove linkability, without running into the same mistakes of tornado cash. In practice, the goal is thecreatio of P2P disposable mixers which comes and go. A easy to use interface can be provided as application (e.g. as Bisq does)

## Design Overview

Assume three people want to mix their coins. They can't go to tornado anymore. But they can pool their fund together in a smart contract, and then get their share.

If things are done correctly (e.g. each transaction has the same amount of ethers), external observers won't be able to know the relation between *before* address and *after* addresses

||
|:--:|
| <b>Fig1: overview of protocol</b>|

With reference to fig1. Assume addresses $A,B$ and $C$ **put** 1ETH each in a smart contract. This is the before phase. In the after phase, addresses $D,E$ and $F$ **withdraw** the addresses. At minimum, no internal observer (owners of $A,B,C$) or external observer (e.g. chainanalysis or viewer of Etherscan) should be able to link *before* addresses with *after* address.

Practically we want to give meaning to the words **put** and **withdraw** introduced before. More formally, we want

- no party can cheat others and **withdraw** more than what he **put**
- therefore each party MUST **put** something
- no external observer $E$ can correlate **put* with **withdraw**

## Goal Formalization

Assume $n$ users $U_1,\ldots,U_n$ want to mix funds. For easines, we say that address `0xui` belong to user $U_i$ (e.g. `0xu3` belong to user $U_3$ ). Similarly, let $N_1,\ldots,N_n$ be the *new* indexing of the *same* entities *after* the run of the protocol, with addresses `0xni` belonging to $N_i$. Let's call the protocol $\pi$. Then the goal of $\pi$ is to move funds from `0xui` to `0xnj`. Formally, the goal of the protocol is to produce a permutation $\pi$ such that

1. each user $U_i$:
1. knows $\pi(U_i)=N_j$ (correctness)
2. **doesn't** know the result of $\pi(U_k), \forall k\in\{1,\ldots,i-1,i+1,\ldots,n\}$ (unlinkability for internal parties)
2. each external observer $E$ **doesn't** know the result of $\pi(U_k), \forall k\in\{1,\ldots,n\}$ (unlinkability for external parties)
3. if every party acts honestly then
$$
\pi(U_1,\ldots,U_n)=N_1,\ldots,N_n
$$
(liveness)

## Threshold signatures

this section is written to understand the [Less-Naive implementation](#Less-Naive-Implementation) section. feel free to skip it if you already know what they are.

I wrote about this kind of signature scheme [here](https://bowtiedproghorn.substack.com/p/multisig-and-threshold-sigs). In this section I just highlight some point.

In a threshold signature scheme users $U_1,\ldots,U_n$ get together to sign a message/transaction. For our intent and purposes, we assume the threshold signature scheme used here is a $n$-of-$n$ scheme, so all parties are required to sign in order for the signature to be valid. Formally, a $n$-of-$n$ threshold signature scheme is a 3ple ($DKeyGen$,$ThSign$,$Ver$) such that:
- $(sk_1,\ldots,sk_n;pk)\gets DKeyGen(1^\lambda)$; a distributed key-generation algorithm that produces $n$ secret keys (one for each participant) and _one_ public key used to verify the signatures
- $\sigma\gets ThSign(sk_1,\ldots,sk_n;m)$; an (interactive) signature algorithm which produces _one_ (regardless of the number of participants) signature for a message $m$
- `0|1`$\gets Ver(\sigma,pk)$; a (non interactive) verification algorithm

## Naive implementation

### Implementation
In a naive implementation, the contract could wait for all people to put the funds in it and when the last person sends its funds the contract sends the funds to the *after addresses*. More formally, given the same notation as before, and writing a contract in a pseudo-code similar to solidity:

/// listing 1

address beforeAddr[n] = [0xu1,0xu2,...,0xun];
address afterAddr[n] = [0xn1,0xn2,...,0xnn];
map(address => bool) hasPutAlready
uint val //value in ether to put in smart contract
uint waitPeriod = 3 hours
uint deadline = now + waitPeriod

function checkIfEveryonePut(hasPutAlready) private returns (bool success){
    for r,v in hasPutAlready{ \\\ I admit that this is more Python than Solidity
        if v == false:
            return false
    return true
    }
}
function receive() public payable {
    require(msg.value == val, "wrong number of ethers")
    require(hasPutAlready[msg.sender] == false, "Address has already put funds in this smart contrac")
    hasPutAlready[msg.sender] == true
    
    if (now < deadline) {
        if checkIfEveryonePut(hasPutAlready) == true {
            for (i in 1..n){
                send ether to afterAddr[i]
            }

            self distruction of contract

        }
    } else {
        for (i in 1..n){
            if (hasPutAlready[i] == true) { send ether to beforeAddr[i] }
        }

        self distruction of contract
    }
        
}

There fore the contract either receives all the ethers and then sends them to the `afterAddress`, or (if deadline reached) it reinburses those who put the funds in it.
### Problem with Implementation

- who puts the smart contract? if one of the users does it, then it is the leader
- this guy could snitch on the others
- "this contract appears to be some kind of mixer" <- no plausible deniability

Since there are these blatant problems, I do not go into a detailed analysis or specification of this implementation

## Less-Naive Implementation
Goal of this implemnentation is to give users at least some plausible deniability. Note that this is more than what you have with tornado, since if you use tornado, then you mixed your funds.
### Implementation
here is how the users approach the task, see Fig2 for a scheme:
1. $U_1,\ldots,U_n$ exchange the new addresses (see section [New Addresses Exchange](#New-Addresses-Exchange)) and decide a value in ether to exchange (see also [Other Tokens](#Other-tokens) )
1. $U_1,\ldots,U_n$ create a joint public key $pk$ and therefore a EOA address `0xpk` using $DKeyGen$ (see [Threshold signatures section](#Threshold-signatures)) and send some funds to `0xpk`
3. $U_1,\ldots,U_n$ use `0xpk` to deploy a smart contract $SC$ (see `listing2` below) and set `0xpk` as owner
3. $U_1,\ldots,U_n$ send funds to $SC$ (see [Different Amounts](#Different-amounts) below)
6. $U_1,\ldots,U_n$ threshold-sing a tx from $SC$ to $N_1,\ldots,N_n$
- *de facto* this transaction is signed by the owner

||
|:--:|
|Fig2. scheme of steps of less-naive implementation|

/// listing 2

address afterAddr[n] = [0xn1,0xn2,...,0xnn];
address owner
uint totVal //total value in ether to put in smart contract
uint sum = 0 // initialize the counter of funds
uint waitPeriod = 3 hours
uint deadline = now + waitPeriod

map(bytes32 => uint) HashesToVal
map(bytes32 => address) HashesToAddr //for emergency redeem

construct {
    owner = msg.sender
}

modifier onlyOwner {
    require(msg.sender == owner)
    _;
}

function receive(bytes32 hash, address emergencyRedeemAddr) public payable {
    require(now < deadline,"time's up!")
    HashesToVal[hash] = msg.value //map a hash provided by msg.sender to the value he sent
    HashesToAddr[hash] = emergencyRedeemAddr //map a hash provided by msg.sender to the address he provided
    sum += msg.value
    
}


function spend() public onlyOwner{
    require(now < deadline,"time's up!")
    if (sum == totVal){
        for i in 1..n {
            success= send totVal/n to afterAddr[i]
        }
    }
}

function redeem(string memory str, bytes32 hash) {
    require(now >= deadline,"too soon!")
    if ( keccak256(abi.encodePacked(str)) == hash) {
        send HashesToVal[hash] to HashesToAddr[hash]
    }
}

Notes:
- see how funciton `redeem` works: users can supply a *specific* address to the smart contract: in case the mixing fails, each user can redeem the funds on that addres. it can be different from the `msg.sender` one: the idea is to rpovide a little bit of privacy for honest users even if the protocol fails
- there is no `beforeAddress`: this way there is no permanent record of who wanted to mix funds. In theory anybody can fund the smart contract. this (non rational) move would still benefit the honest users since the `afterAddresses` are fixed
- only the `owner` can distribute the funds. Still, the owner is actually a $n$-of-$n$ multisig which produce one signature
### New Addresses Exchange
in theory each $U_i$ can communicate his address to the other users. But by doing so he will let them know his new addreass, breaking the *unlinkability for internal parties* goal (see [Goal Formalization](#Goal-Formalization)).

Fortunately, multiparty computation could help us. Private set union (PSU, see eg [^psu]) is a multiparty protocol that let users create a set from data. The set is the union of the data provided by the user. While the data per se will not be private at the end, *who* provided *which piece* of data remain private. Of course it is meaningless to operate a PSU protocol betwen two parties and the more parties the better from aprivacy point of view. In case there are many parties, then the *unlinkability for internal parties* goal is satisfied.
### Plausible Deniability
### Other tokens
You could exchange other tokens e.g. wBTC this way. It is not important as long as
- users put more funds in `0xpk` to pay for fees
- the smart contract $SC$ changes accordingly

### Different amounts
Nothing prevents the fact that there are more *new* addresses than old ones. Assume e.g. that the value in ether is 1 and $U_1$ wants to split its funds, which are a total of 3 eth. Then $U_1$ will provide three new addresses $N_{i_1},N_{i_2},N_{i_3}$, and he wille send 3eth to $SC$. since users use PSU to exchange addresses, they will know somebody put more than one address, but they will not know who. Further more, they will see $U_1$ put 3eth, but they will not know what are the three new addresses he controls. therefore *unlinkability for internal parties* goal is satisfied.

This works also on reverse. Assume that user controlling $U_2$ and $U_3$ wants to consolidate accounts in a way that makes him preserve two different histories (e.g. because he want to send the to an exchange with KYC without revealing his real accounts, see e.g. [here](https://bowtiedproghorn.substack.com/i/50445248/first-heuristic)). then he can easily provide only one address $N_{i_2}$ as user $U_2$ and `null` as user $U_3$. since the use of PSU nobody knows who sent the `null` address instead.

### Problem with Implementation
- somehow still based on anonimity set
- other?

## Security
we can prove security in the ideal-real paradigm [^ideal]
### Ideal scenario
TODO
### Proof of Security
TODO

## TODOs
- how people match? may be based on how Bisq works?
- can we lower the round of communication? (2/3 right now)

[^1]: ofc is not a complete shutdown, you can bypass the interface etc etc. Still, it feels that way rn
[^psu]: see [this repo](https://github.com/osu-crypto/PSU) and [related paper](https://eprint.iacr.org/2019/776.pdf), even though they are a little old (2019), they could be used here
[^ideal]: see e.g. [this tutorial](https://eprint.iacr.org/2016/046.pdf) by Lindell