# Private order matching & zk atomic swap

Private order matching uses the 'Socialist Millionare' protocol to match the trade orders without revealing the details. The matched result can also be used to enforce a zk transfer pool to execute a zk atomic swap correctly.

## Private order matching

### Step 1. Make a new order

Let's assume that Alice wants to get 100 DAI by giving 1 ETH. And Bob wants to get 1 ETH by giving 100 DAI.

Alice's order: `'GET DAI' (1, 100)(ETH/DAI)`
Bob's order: `'GET ETH' (1, 100)(ETH/DAI)`

sell = field('GET DAI')
buy = field('GET ETH')
order = field('(1, 100)(ETH/DAI)')

| What only Alice knows | What everyone knows | What only Bob knows |
| -------- | -------- | -------- |
|$order_a$ | $sell$, $buy$, $pk_a$, $pk_b$ | $order_b$ |

### Step 2. Create the homomorphic hidings for each other.

In this situation, Alice and Bob will generates new homomorphic hidings for the 'socialist millionare' protocol using their own salts and each other's public key. As a result, each homomorphic hidings are below:

- Alice's homomorphic hiding: $H_a = g^{sell \cdot pk_b \cdot salt_{a} \cdot order_a}$
- Alice's public salt: $S_a = g^{sell \cdot pk_b \cdot salt_{a}}$
- Bob's homomorphic hiding: $H_b = g^{buy \cdot pk_a \cdot salt_{b} \cdot order_b}$
- Bob's public salt: $S_b = g^{buy \cdot pk_a \cdot salt_{b}}$

And they share their homomorphic hidings each other.

| What only Alice knows | What everyone knows | What only Bob knows |
| -------- | -------- | -------- |
|$order_a$, $salt_a$ | $sell$, $buy$, $pk_a$, $pk_b$, $H_a$, $H_b$, $S_a$, $S_b$ | $order_b$, $salt_b$|

### Step 3. Alice and Bob checks that they have a same order.

Now using the given values, Alice and Bob check that they have a same order by themselves.

- If Alice's calculation $H_b == order_a \cdot S_b$ is true, she knows that $order_a == order_b$.
- If Bob calculate $H_a == order_b \cdot S_a$ is true, he also knows that $order_b == order_a$.
- Now they know that they have a same order each other.

| What Alice only knows | What everyone knows | What Bob only knows |
| -------- | -------- | -------- |
|$order_a$, $salt_a$ , $order_a \cdot S_b == H_b$| $sell$, $buy$, $pk_a$, $pk_b$, $H_a$, $H_b$, $S_a$, $S_b$ | $order_b$, $salt_b$, $order_b \cdot S_a == H_a$|

## Using $H$ for zk atomic swap

To make the atomic swap happen with the matched order, use the combined homomorphic hiding $H$ to combine 2 zk transfers. Here $H$ equals to the below:

$H = g^{sell \cdot buy \cdot pk_a \cdot pk_b \cdot salt_a \cdot salt_b \cdot order}$

And then Alice's and Bob's zk transfers for the atomic swap should look like this:

#### Alice's zk transfer for the atomic swap

| - NoteA1(input) | + NoteA2(output) | + NoteA3(output) | Sum |
| --------------- | ---------------- | ---------------- | --- |
| ETH: 3 | ETH: 2 | ETH: 1 | 0 |
| DAI: 500 | DAI: 500 | DAI: 0 | 0 |
| Owner: Alice | Owner: Alice | Owner: Bob | |

#### Bob's zk transfer for the atomic swap

| - NoteB1(input) | + NoteB2(output) | + NoteB3(output) | Sum |
| --------------- | ---------------- | ---------------- | --- |
| ETH: 8 | ETH: 8 | ETH: 0 | 0 |
| DAI: 900 | DAI: 800 | DAI: 100 | 0 |
| Owner: Bob | Owner: Bob | Owner: Alice | |

In this pair, Alice splits her asset into two notes and give one to Bob. Otherwise, Bob also split his assets and give one to Alice. The newly exchanging notes should have the same information in the homomorphicall hidden commitment $H$.

### Alice's SNARK

public inputs:
    Note A1's nullifier
    Note A2's hash
    Note A3's hash
    H<=(sell, buy, pk_a, pk_b, salt_a, salt_b, order)

private inputs:
    Note A1's details [3, 500, Alice]
    Note A1's spending signature from Alice's key
    Note A2's details [2, 500, Alice]
    Note A3's details [1, 0, Bob]
    Bob's public key [pk_b]
    Bob's public salt S_b<=(buy, pk_a, salt_b)
    order [1, 100] = (order_x, order_y)
    salt_a
    
Constraints:
    1. The hash of Note A1, A2, and A3 are all valid.
    2. Note A1's included in the shielded pool.
    3. Note A1's nullifier is correctly derived from the A1's details.
    4. output notes - input notes == 0 (A2 + A3 - A1 == 0)
    5. A3's owner == pk_b
    6. A3's value == if 'sell' then (order_x, 0) else (0, order_y)
    7. if sell:
            H == sell * pk_b * salt_a * order * S_b
       elif buy: 
            H == buy * pk_b * salt_a * order * S_b

### Bob's SNARK

public inputs:
    Note B1's nullifier
    Note B2's hash
    Note B3's hash
    H<=(sell, buy, pk_a, pk_b, salt_a, salt_b, order)

private inputs:
    Note B1's details [8, 900, Bob]
    Note B1's spending signature from Alice's key
    Note B2's details [8, 800, Bob]
    Note B3's details [8, 100, Alice]
    Alice's public key [pk_a]
    Alice's public salt S_a<=(buy, pk_b, salt_a)
    order [1, 100] = (order_x, order_y)
    salt_a
    
Constraints:
    1. The hash of Note B1, B2, and B3 are all valid.
    2. Note B1's included in the shielded pool.
    3. Note B1's nullifier is correctly derived from the B1's details.
    4. output notes - input notes == 0 (B2 + B3 - B1 == 0)
    5. B3's owner == pk_a
    6. B3's value == if 'sell' then (order_x, 0) else (0, order_y)
    7. if sell:
            H == sell * pk_a * salt_b * order * S_a
       elif buy: 
            H == buy * pk_a * salt_b * order * S_a

With this construction, we can let Alice and Bob match their order privately and also execute the zk atomic swap.