// 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:

// 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.

// client functions
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$.