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: