## Building an on-chain dark pool with Unyfy

<figure style="width:100%;margin:0px">
<img src="https://hackmd.io/_uploads/S1mdn7QeT.png" style="width:100%"/>
<figcaption align = "center"><i>Shielding open orders makes it difficult for adversarial traders to manipulate markets. They won't be able to gauge the effect their treasury would have on the mid-price.</i></figcaption>
</figure>

### Manipulation resistance for small cap tokens
Dark pools in traditional finance are used for minimizing price impact. The [Unyfy](https://unyfy.xyz/) team sees the role of dark pools in crypto in an entirely different light. Rather than using its properties to protect institutional traders in big cap markets, they aim to protect community members in small cap markets.

Ethereum's dark forest is notoriously dangerous for new groups who want to bootstrap communities via token distribution. These groups are targeted by malicious traders who pump token price, wait for the subsequent uptick, then dump all holdings for profit. The process is often fatal.

The solution's simple. Make the primary medium of token exchange a dark pool. Observers should have no bearing on the distribution of liquidity across prices. There could be large orders right above or below the mid-price with enough liquidity to absorb adversarial pump and dumps. As such, bots who attempt to manipulate the market do so at a significant risk to their treasuries.

### Running the order book fully on-chain
Unyfy needs users to retain custody over funds and have control over orders. In other words, they need to run the dark pool fully on-chain.

Placing and cancelling shielded orders is straightforward. Users keep hiding commitments on-chain and transition them using ZKPs to fulfill validity predicates. The problem presents itself when users attempt to fill these orders. Doing so requires seeing and transitioning shielded state they do not own. This is difficult due to fragmentation. User A cannot see or modify user B's shielded state.

## Our protocol for de-fragmenting shielded state

<figure style="width:100%;margin:0px">
<img src="https://hackmd.io/_uploads/BJI-rX7lT.png" style="width:100%"/>
<figcaption align = "center"><i>Users submit transactions that place and fill orders directly to the chain. Elliptic's bridge shares user A's crossing orders with user B. User B uses this knowledge to complete their ZKPs.</i></figcaption>
</figure>

### Unyfy is partnering with Elliptic

Elliptic's service solves Unyfy's problem of fragmented shielded state. It allows user A in Unyfy's protocol to see and modify user B's shielded state. We do so while upholding three properties that are pre-requisites for an application like Unyfy:

1. Malicious actors must not have the ability to steal funds or have them move in any way that is not initiated by the appropriate owners.
2. Computation and communication must scale sub-linearly with the number of users. Unyfy anticipates a large number of concurrent users during periods of peak activity.
3. Trades must execute asynchronously. Users with open orders cannot stay online 24/7 to communicate with potential counterparties.

### How we bridge shielded state for Unyfy users

Elliptic provides Unyfy users with the information necessary to complete ZKPs for transitioning counterparty shielded state. The process begins with Unyfy customers transmitting their orders in the clear to Elliptic prior to taking action with the chain. These orders go directly to Elliptic's secure enclaves, where no one, not even operators, can view. Other customers who demonstrate they are valid counterparties can then learn about these shielded orders and act on them.

This cryptosystem meets Unyfy's requirements of self-custody and full order control. Computational integrity is based on pure cryptographic assymptions. Shielding is based on Elliptic's trusted hardware assumptions. Future releases from Elliptic will maintain shielded information across an MPC network to further increase defensive depth.

Unyfy's engineers will take on the application-specific portion of the build. These include the circuits, client functions, and contracts. Elliptic will provide the proof completion mechanism, equipped with data availability, load balancing, reorg protection, rate limiting, notification flows, etc. Elliptic also provides libraries for common operations (eg. extracting outputs from witness generation) that will be useful for Unyfy engineers.

### Shielding the price of an order, and nothing else

We've streamlined our construction to shield prices of open orders, and not a single bit more. Total buy and sell side liquidity, depth at the best bid / ask, exchange paths, and filled orders are all public by design.

This aligns with Elliptic's goals of building maximally transparent systems with the minimal shielding mechanics that people needed to build interesting applications. Our design philosophy yields the following benefits for Unyfy:

1. Fast client-side proving. We've removed all instances of merkle trees (`600 constraints` per hash on top of an average tree depth of 32), non-native field aritmetic (`4000 constraints` per mul), and group operations (`2000 constraints` per point mul). Our circuits are simple, and that's reflected in our proving times. The UX benefit is significant.
2. Information equity. Efforts to shield on-chain state are commonly thwarted with statistical analyses. Many protocols are theoretically hiding, but fall short in practice. The small subset of the population able to compile heuristics and develop effective models reap all of the benefits of knowing what they shouldn't. Even worse, users of the protocol operate under the assumption of complete information asymmetry when it is seldom the case. Actively shielding as little information as possible mitigates these inequities in knowledge.
3. Compliance. Providing anonymity brings unwanted illicit activity and regulatory risk. We do not provide anonymity.

### Representing the limit order book

We instantiate our zero knowledge proof system $(P, V)$ over the curve `bn128`. All variables are in its scalar field $F$.

An order is represented as the following object, with a transparent structure $t$ and shielded structure $s$:

{
    t: (ϕ, χ, d)
    s: (p, v, α)
}

with the following definitions:
- $\phi$: side of the order, 0 when it's a bid, 1 when it's an ask
- $\chi$: token address for the target project
- $d$: denomination, either the token address of USDC or ETH (set to `0x1` for this case)
- $p$: price, denominated in $d$, with scaling factor $10^9$ but only $10^7$ precision
- $v$: volume, amount of token to exchange, with scaling factor $10^9$
- $\alpha$: access key, randomly sampled from $F$, protects against brute force attacks, meant to be revealed to counterparties

We employ a cryptographic hash function $H$ to create hiding commitments for the shielded structure. The chain only sees the commitment $\bar O = \{t: O.t, s: H(O.s)\}$.

The on-chain orderbook comprises of 1) a list of these comitments $\{\bar O_i\}_{i=0}^N$ and 2) the Ethereum public keys $pk$ of the commitment owners.

When describing the protocol, we often employ an auxiliary variable $b$ to describe a balance. It is a pair with the first element specifying an amount of the target project's token and the second element specifying an amount of the denomination token. A balance will always be used in conjunction with an order $O$, so target and denomination tokens are unambiguous.

Readers will have to excuse our blend of lax notation from mathematics and lax notation from computer science. The purist descriptions grew too verbose. Scaling factors are also redacted for brevity, but must be included during implementation to handle float operations.

### Client functions for interacting with the dark pool

Users place orders by constructing $\bar O$, proving this was done faithfully, and backing it with the appropriate tokens. Bids are backed with the $d$ token. Asks are backed with the $\chi$ token.

$place(\phi, \chi, d, p, v)$
1. Sample $\alpha\leftarrow$$ $F$. Construct $O = \{s: (\phi, \chi, d), t: (p, v, \alpha)\}$.
2. Run witness generation for the $back$ circuit, assigning its outputs $\{\bar O, b\}$ to local variables.
6. Let $P$ be the predicate "reveal this order iff it is finalized on-chain AND the requester owns an opposing active order within the limit bounds". Send $O$ and $\bar O$ to Elliptic. We will attach the predicate $P$. Elliptic acknowledges the message and sends back the signature $\sigma = Sign(sk_{ellp}, \bar O)$.
11. Generate ZKP $\pi_{back} = P(pp_{back}.pkey, \bar O, b)$, where $pp_{back}.pkey$ is the proving key for our $back$ circuit.
12. Publish contract call $place(\pi_{back}, \bar O, b, \sigma)$ to the chain, along with the tokens specified in $b$.

After commiting to an order $O_{own}$, the user can request Elliptic for all crosses up to 3x the order volume. For instance, a bid for 1000 `LINK` will return at most 3000 `LINK` worth of crossed asks. The user selects the best $n$ orders that cross $\{O_i\}_{i=0}^n$. Consuming all orders involved settles the trade. Settling will seldom be exact. For that reason, we create $\bar O_{cho}$ for the change order of $O_{own}$ and $\bar O_{chn}$ for the change order of $O_n$. These change orders are analogous to [Bitcoin change addresses](https://support.blockchain.com/hc/en-us/articles/4417082392724-What-are-change-addresses-and-how-do-they-work-#:~:text=Change%20addresses%20are%20an%20aspect,of%20the%20output%20being%20spent.).

$fill(O_{own}, \{O_i\}_{i=0}^n)$
1. Run witness generation for the $fill$ circuit, assigning its outputs $\{\bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_n.p, \bar O_{cho}, \bar O_{chn}, O_{cho}, O_{chn}\}$ to local variables.
9. Let $P$ be the predicate "reveal this order iff it is finalized on-chain AND the requester owns an opposing order within the limit bounds". Send $\{O_{cho}, O_{chn}, \bar O_{cho}, \bar O_{chn}\}$to Elliptic. We will attach the predicate $P$. Elliptic acknowledges the messages and sends back the signatures $\sigma_{cho} = Sign(sk_{ellp}, \bar O_{cho})$ and $\sigma_{chn} = Sign(sk_{ellp}, \bar O_{chn})$.
11. Optional. Use Elliptic's circom library to encrypt $O_{chn}$ under a key $k$ that's shared with the owner of $O_n$. Add $Enc(k, O_{chn})$ to the ZKP. Unnecessary to do in the first release.
12. Generate ZKP $\pi_{fill} = P(pp_{fill}.pkey, \bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_n.p, \bar O_{cho}, \bar O_{chn})$, where $pp_{fill}.pkey$ is the proving key for our $fill$ circuit.
13. Publish contract call $fill(\pi_{fill}, \bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_n.p, \bar O_{cho}, \bar O_{chn}, \sigma_{cho}, \sigma_{chn})$ to the chain.

Users can cancel their open orders and regain the tokens that back them. This is straightforward in our open ownership model. The user only needs to prove the backing amount and sign the transaction using the ETH account of the owner. Logic for cancelling an order has heavy symmetries to placing one, with the below client function even using the same $back$ circuit.

$cancel(O)$
1. Run witness generation for the $cancel$ circuit, assigning its outputs $\{\bar O, b\}$ to local variables.
2. Generate ZKP $\pi_{back} = P(pp_{back}.pkey, \bar O, b)$, where $pp_{back}.pkey$ is the proving key for our $back$ circuit.
8. Publish contract call $cancel(\pi_{back}, \bar O, b)$, receiving the tokens specified in $b$.

### ZKPs for attesting to valid state transitions

We want to convince the verifier that the order committed to by $\bar O$ requires $b$ tokens to be unilaterally filled by a counterparty. For instance, an ask for 200 `LINK` must be backed by 200 `LINK`.

$back() \rightarrow \{\bar O, b\}$
1. Load private signals $\{O\}$.
2. Construct $\bar O = (O.t, H(O.s))$.
4. Compute the balance needed to back this order. If $O.t.\phi == 0$, then set $b = (0, (O.s.p)(O.s.v))$. If $O.t.\phi == 1$, then set $b = (O.s.v, 0)$. Notice that price is a free variable in both tuples. Observers will know the max amount of buy or sell side liquidity provided by this order, but have no information on the price this liquidity is introduced at.
5. Add $\{\bar O, b\}$ as public outputs.

Order commitments can only be consumed when balances are created according to the underlying orders. For instance, filling an ask for 20 `LINK` at the price of 1.32 `USDC` should result in a balance of at least 26.4 `USDC` for the order's owner. We also explicitly expose the price of the last order that was completely filled so observers can estimate the spread.

Strong post-fill shielding is left out by design. The balance payout, along with the initial backing amount, allows observers to compute the price each $O_i \forall i \in [0, n-1)$ is filled at. We've confirmed with the Unyfy team that this does not take away from the effectiveness of their application. Exact prices for $O_{own}$ and $O_n$ are still shielded, though they are anchored to the exposed price of $O_{n-1}$. Balance computation is still done in-circuit, not primarily for shielding properties, but for succinctness since we are deploying to Mainnet.

$fill() \rightarrow \{\bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_{n-1}.p, \bar O_{cho}, \bar O_{chn}, O_{cho}, O_{chn}\}$
1. Load private signals $\{O_{own}, \{O_i\}_{i=0}^n\}$.
2. Assert $O_{own}$ is large enough to completely fill $\{O_i\}_{i=0}^{n-1}$ and at least partially fill $O_{n}$.
3. Construct $\bar O_{own} = (O_{own}.t, H(O_{own}.s))$ and $\bar O_i = (O_i.t, H(O_i.s)) \forall i \in [0, n)$.
4. Let $\gamma = min(O_{own}.s.v, \sum_{i=0}^n O_i.s.v)$ be the amount of $\chi$ token exchanged in this fill.
5. Compute balances $b_{own}$ and $\{b_i\}_{i=0}^n$. If $O_{own}.t.\phi == 0$, then $b_{own} = (\gamma, \nu)$ and $b_i = (0, (O_i.s.p)(O_i.s.v))$. Compute $\nu$ by subtracting the cost of $\gamma$ tokens across $\{O_i\}_{i=0}^n$ from what the cost would have been at price $O_{own}.s.p$. If $O_{own}.t.\phi == 1$, then $b_{own} = (0, \nu$ and $b_i = (O_i.s.v, 0) \forall i \in [0, n-1)$ and $b_n = (\gamma - \sum_{i=0}^{n-1} O_i.s.v, 0)$. Compute $\nu$ by summing the cost of $\gamma$ tokens across $\{O_i\}_{i=0}^n$.

This might be a bit confusing for readers, so we clearly delineate how balances are updated in both bid and ask cases:
#### Bid v/s Ask balance updates

| **Bid Case ($O_{\text{own}}.t.\phi=0$)** | **Ask Case ($O_{\text{own}}.t.\phi=1$)** |
|:----------------------------------------:|:----------------------------------------:|
| **Initial** | **Initial** |
| $b_{\text{own}} = (0, (O_{\text{own}}.s.p) (O_{\text{own}}.s.v))$ | $b_{\text{own}} = (\gamma, 0)$ |
| $b_i = (\gamma_{i}, 0)$ | $b_i = (0, (O_{\text{i}}.s.p)(O_{\text{i}}.s.v))$ |
| **Final** | **Final** |
| $\gamma = \sum_{i=0}^{n-1} \gamma_i + k$ | $\gamma = \sum_{i=0}^{n-1} O_{i}.s.v + k$ |
| Orders 0 to $n-1$ fully filled, | Orders 0 to $n-1$ fully filled, |
| $n^{th}$ order at least partially filled. | $n^{th}$ order at least partially filled. |
| $k \leq \gamma_n$ | $k \leq O_{n}.v$ |
| $\nu=(O_{\text{own}}.s.p)(O_{\text{own}}.s.v)-\sum_{i=0}^{n-1} \gamma_i(O_i.s.p) - k (O_n.s.p)$ | $\nu= \sum_{i=0}^{n-1} (O_i.s.v)(O_i.s.p) + k(O_n.s.p)$ |
| $b_{\text{own}}=(\gamma, \nu)$ | $b_{\text{own}}=(0,\nu)$ |
| $b_i$ for $0\leq i < n= (0, (O_{\text{own}}.s.p) (O_{\text{own}}.s.v))$ | $b_i$ for $0\leq i < n= (O_i.s.v,0)$ |
| Here, $\gamma_i == O_i.s.v$ | |
| $b_n=(\gamma_n-k, k (O_n.s.p))$ | $b_n=(k, (O_n.s.p)(O_n.s.v-k))$ |

7. Construct $O_{cho}$ with all attributes of $O_{own}$, subtracting $\gamma$ from volume and replacing the access key with a newly sampled $\alpha$. If $\gamma == O_{own}.s.v$, then use dummy values for $O_{cho}$.
8. Construct $O_{chn}$ with all attributes of $O_{n}$, subtracting $\gamma - \sum_{i=0}^{n-1} O_i.s.v$ from volume and replacing the access key with a newly sampled $\alpha$. If $\gamma == \sum_{i=0}^n O_i.s.v$, then use dummy values for $O_{chn}$.
9. Construct $\bar O_{cho} = (O_{cho}.t, H(O_{cho}.s))$ and $\bar O_{chn} = (O_{chn}.t, H(O_{chn}.s))$.
10. Add $\{\bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_{n-1}.p, \bar O_{cho}, \bar O_{chn}\}$ as public outputs.

### The chain is the source of truth for dark pool state and token ownership

Contract behavior is fully specified by the above descriptions. Writing the psuedocode here for completeness. The Solidity complements of the core three functions all involve 1) verifying the ZKP for proper commitent construction and balance attestation, 2) distributing balances, and 3) tracking the consumption of commitments.

The bulk of gas expenditure is from the ZKP verifier (300k gas) and the ERC20 `transfer()` (50k gas per balance) calls. As a rough estimate on Mainnet, this is $22 to fill one order against 6 orders and $14 to place / cancel orders. The actual costs when we deploy will be a bit higher when the other operations are included.

$place(\pi_{back}, \phi, \bar O, b, \sigma)$
1. Assert $V(pp_{back}.vkey, \pi_{back}, \bar O, b)$, where $pp_{back}.vkey$ is the verifying key for our $back$ circuit.
2. Assert $V_{sig}(pk_{ellp}, \bar O, \sigma)$, where $V_{sig}(⋅)$ is the algorithm from our chosen signature scheme.
3. Call `transfer(msg.sender, this, b.0)` for $O.t.χ$ and `transfer(msg.sender, this, b.1)` for $O.t.d$. Assume appropriate `ERC20` permissions.
4. Add $\bar O$ with owner `msg.sender` to contract storage.

$fill(\pi_{fill}, \bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_n.p, \bar O_{cho}, \bar O_{chn}, \sigma_{cho}, \sigma_{chn})$
1. Assert $V(pp_{fill}.vkey, \pi_{fill}, \bar O_{own}, \{\bar O_i\}_{i=0}^n, b_{own}, \{b_i\}_{i=0}^n, O_n.p, \bar O_{cho}, \bar O_{chn})$, where $pp_{fill}.vkey$ is the verifying key for our $fill$ circuit.
2. Assert $V_{sig}(pk_{ellp}, \bar O_{cho}, \sigma_{cho})$ and $V_{sig}(pk_{ellp}, \bar O_{chn}, \sigma_{chn})$, where $V_{sig}(⋅)$ is the algorithm from our chosen signature scheme.
3. Assert $\bar O_i \forall i \in [0, n)$ and $\bar O_{own}$ are active orders, then remove all of them from contract storage.
4. Assert `msg.sender` is the owner of $\bar O_{own}$.
5. Call `transfer(this, O_i_owner, b_i.0)` for $\bar O_i.t.χ$ and `transfer(this, b_i.1)` for $\bar O_i.t.d$ $\forall i \in [0, n)$. Assume appropriate `ERC20` permissions.
6. Call `transfer(this, msg.sender, b_own.0)` for $\bar O_{own}.t.χ$ and `transfer(this, b_own.1)` for $\bar O_{own}.t.d$. Assume appropriate `ERC20` permissions.
7. Add $\bar O_{cho}$ with owner `msg.sender` to contract storage.
8. Add $\bar O_{chn}$ with the owner of $O_n$ to contract storage.

$cancel(\pi_{back}, \bar O, b)$
1. Assert $V(pp_{back}.vkey, \pi_{back}, \bar O, b)$, where $pp_{back}.vkey$ is the verifying key for our $back$ circuit.
2. Assert `msg.sender` is the owner of $\bar O$
3. Call `transfer(this, msg.sender, b.0)` for $\bar O.t.χ$ and `transfer(this, msg.sender, b.1)` for $\bar O.t.d$. Assume appropriate `ERC20` permissions.
4. Remove $\bar O$ from contract storage.

### Malicious behavior that we want to protect against
1. **Can Unyfy or Elliptic steal user funds?** No, users hold custody over their funds and have sole control over their orders.
2. **Can users orders be consumed at a price outside of their stated bounds?** No, the integrity of filling orders is upheld via ZKPs.
3. **Can the dark pool be used to launder money?** No, we've removed all components of anonymity from our protocol. All edges of the transaction graph are public. We do not run relayers. All observers will know who traded with who, along with the value transferred in each exchange. Furthermore, we do not allow users to deposit from one account and withdraw to another. We also take the additional precaution of deposit screening with long (6hr+) time delays.
4. **Can a bot feign an order to see the whole order book?** No, they need to commit to the order to learn anything & Elliptic will only return the best crosses up to the order volume. If the attacker posts a small order with a wide range, only the single best price will be revealed. If the attacker posts a large order with a wide range, anyone can fill it. We can protect against commit-cancel patterns for this second case by enforcing a block delay- eg traders can only cancel orders after 10 blocks have passed.
7. **Can attackers halt the protocol?** Yes, temporarily. Since Elliptic's service for proof completion has hardware dependencies, attackers can mount physical attacks to take it down temporarily. The data availability solutions in place, however, let us reboot the service quickly. This dependency only applies to the matching process. At no point will any attackers be able to pause placing and cancelling orders. Funds can never be locked.
8. **Can these hardware dependencies be exploited to harm users?** Yes. In the event of a catastrophic exploit, malicious parties could gain visibility into the orderbook. We have taken steps to mitigate this serious risk, including careful selection of secure enclaves, minimized hardware roles in the cryptosystem, and streamlined processes for switching providers. Note: this all only applies to the order book's shielding property. At no point will attackers be able to steal funds or falsify order routing.