###### tags: `zip`

# ZIP-8: Hybrid CDA

<!-- prettier-ignore -->
:::warning
Author: Dr. Malte Kliemann
Revision: 6
:::

## Introduction

The following architecture design allows users of the Zeitgeist runtime to use the DLMSR AMM and CDA in parallel on the markets they create by splitting and routing trades to achieve the best execution price.

The design requires an off-chain matcher to provide a list of order IDs which should be used to fill the users order. Using the on-chain router in combination with an off-chain matcher has one crushing advantage over just using an off-chain matcher: If multiple trades come in on the same block, collisions can be avoided.

## Blockchain Architecture Changes

### Scoring Rules

The `Lmsr` and `Orderbook` variants are removed from the `ScoringRule` enum and replaced by `AmmCdaHybrid`, which allows a market to use both the order book and the AMM. This will require a storage migration.

### zrml-hybrid-router

A new pallet zrml-hybrid-router will be introduced to allow atomic routing of trades between zrml-neo-swaps and zrml-orderbook. The pallet has the following extrinsics:

/// Routes a buy order to AMM and CDA to achieve the best average execution price.
///
/// # Parameters
///
/// * `market_id`: The ID of the market to buy from.
/// * `asset_count`: The number of assets traded on the market.
/// * `asset`: The asset to buy.
/// * `amount`: The amount of `asset` to buy.
/// * `max_price`: The maximum price to buy at.
/// * `orders`: A list of orders from the book to use.
/// * `strategy`: The strategy to handle the remaining order when the `max_price` is reached.
///
/// The elements of `orders` are the orders that the router may use to execute the order. If any of
/// these orders are already filled, they are ignored. It is not necessary for the router to use all
/// specified orders. The smaller the vector, the larger the risk that the AMM is used to fill large
/// chunks of the order.
///
/// The `orders` vector **must** be sorted in ascending order by the price of their associated
/// orders. Failing this, the behavior of `buy` is undefined.
///
/// If the maximum price is reached before the entire buy order is filled, the `strategy` parameter
/// decides if the order is rolled back (`Strategy::ImmediateOrCancel`) or if a limit order for the
/// remaining amount is placed (`Strategy::LimitOrder`).
fn buy(
    origin: OriginFor<T>,
    market_id: MarketIdOf<T>,
    asset_count: u16,
    asset: AssetOf<T>,
    amount: BalanceOf<T>,
    max_price: BalanceOf<T>,
    orders: Vec<OrderIdOf<T>>,
    strategy: Strategy,
) -> DispatchResult;

/// Same as above, m.m.
fn sell(
    origin: OriginFor<T>,
    market_id: MarketIdOf<T>,
    asset_count: u16,
    asset: AssetOf<T>,
    amount: BalanceOf<T>,
    min_price: BalanceOf<T>,
    orders: Vec<OrderIdOf<T>>,
    strategy: Strategy,
) -> DispatchResult;

The `Strategy` object is defined as follows:

/// Represents the strategy used when placing an order in a trading environment.
enum Strategy {
    /// The trade is rolled back if it cannot be executed fully.
    ImmediateOrCancel,
    /// Partially fulfills the order if possible, placing the remainder in the order book. Favors
    /// achieving a specific price rather than immediate execution.
    LimitOrder,
}

The behavior of `buy` will be described in detail below. The behavior of `sell` is symmetric.

A call to `buy` errors when any of the following happens:

- If one of the orders is not from `market_id`.
- If strategy is `ImmediateOrCancel` and the `max_price` is reached.
- If an execution on the AMM or the book fail. Note that this should contain all the classic reasons why a trade might fail: Insufficient funds, etc.

The pallet uses the following config variables to route the trade and acquire info from the AMM and CDA:

type Amm: AmmApi;
type Orderbook: OrderbookApi;

These APIs are defined as Rust traits:

trait AmmApi {
    type AccountId;
    type MarketId;
    type Balance;

    /// Returns the amount a user has to buy to move the price of `asset` to `until`; zero if the
    /// current spot price is above `until`.
    fn calculate_buy_amount_until(
        market_id: Self::MarketId,
        asset: AssetOf<Self>,
        until: Self::Balance
    ) -> Result<Self::Balance, DispatchError>;

    fn buy(
        who: Self::AccountId,
        market_id: Self::MarketId,
        asset_out: AssetOf<Self>,
        amount_in: Self::Balance,
        min_amount_out: Self::Balance,
    ) -> DispatchResult;

    /// Returns the amount a user has to sell to move the price of `asset` to `until`; zero if the
    /// current spot price is below `until`.
    fn calculate_sell_amount_until(
        market_id: Self::MarketId,
        asset: AssetOf<Self>,
        until: Self::Balance
    ) -> Result<Self::Balance, DispatchError>;

    fn sell(
        who: Self::AccountId,
        market_id: Self::MarketId,
        asset_out: AssetOf<Self>,
        amount_in: Self::Balance,
        min_amount_out: Self::Balance,
    ) -> DispatchResult;
}

trait OrderbookApi {
    type Balance;
    type MarketId;
    type Order;
    type OrderId;

    /// Returns the order with the specified `order_id`.
    fn order(order_id: Self::OrderId) -> Result<Self::Order, DispatchError>;

    fn fill_order(
        who: Self::AccountId,
        order_id: Self::OrderId,
        maker_partial_fill: Option<Self::Balance>
    ) -> DispatchResult;

    fn place_order(
        who: Self::AccountId,
        market_id: Self::MarketId,
        maker_asset: AssetOf<Self>,
        maker_amount: Self::Balance,
        taker_asset: AssetOf<Self>,
        taker_amount: Self::Balance
    ) -> DispatchResult;
}

Obviously, these APIs will be implemented by the `Pallet<T>` objects in zrml-neo-swaps and zrml-orderbook, resp. The functions `buy`, `sell`, `*_order` are implemented using the `do_*` functions in the `Pallet<T>` implementation. Documentation can be copied from these extrinsics.

`calculate_*_amount_until` are immplemented in `math.rs` using the same "dance" as for the other members of `MathOps`. Then `calculate_*_amount_until` are also implemented as members of `PoolOperations`; `AmmApi::calculate_*_amount_until` is them implemented using `PoolOperations::calculate_*_amount_until`.

Due to the fact that fees are applied to buys on the AMM before the trade is executed, `calculate_buy_amount_until` needs to calculate what fees will be applied. To that end, the `DistributeFees` trait needs to be extended by a `peek` function which performs a dry run of `distribute` and, in case of the neo-swaps implementation of this trait, returns which external fees and swap fees would have been deducted.

Of course, neither API is complete by any means. They are designed solely to suit the needs of zrml-hybrid-router.

The exact behavior of `buy` is as follows:

Define maybe_buy_from_amm(who, market_id, asset, amount, price):
    If Amm.get_pool(market_id).is_err()
        Return amount
    End If

    remaining ← amount
    amm_amount ← Amm.calculate_buy_amount_until(market_id, asset, price)
    amm_amount ← min(amm_amount, remaining)

    If amm_amount > 0 then
        # Beware of very small amounts triggering ExistentialDeposit errors!
        Amm.buy(who, market_id, asset, amm_amount, 0)
        remaining ← remaining.saturating_sub(amm_amount)
    End If

    Return remaining
End Define
    
Define buy(origin, market_id, asset_count, asset, amount, max_price, orders, strategy):
    who ← ensure_origin(origin)?
    remaining ← amount
    For each order_id in orders do
        order ← Orderbook.order(order_id)
        If order.is_err() then
            Continue
        Else
            order ← order.unwrap()
        End If

        # We shouldn't have to do this, expecting the off-chain matcher to provide proper data, but
        # we're all friends here.
        If order.price() > max_price then
            Raise Exception
        End If

        remaining ← maybe_buy_from_amm(who, market_id, asset, remaining, order.price())

        If remaining != 0 then
            filled ← Orderbook.fill_order(who, order.id, remaining)
            remaining ← remaining.saturating_sub(filled)
        Else
            Break
        End If
    End For

    If remaining > 0 then
        remaining ← maybe_buy_from_amm(who, market_id, asset, remaining, max_price)
    EndIf

    If remaining > 0 then
        If strategy == Strategy.ImmediateOrCancel then
            Raise Exception
        ElseIf strategy == Strategy.LimitOrder then
            Orderbook.place_order(who, market_id, asset, remaining, some_other_asset, max_price)
        End If
    End If
End Define

Note that `Order::price` needs to be implemented, as well.

#### Notes

- The off-chain matcher should offer the user an option to set a "gas usage" which determines how many elements `orders` will have. If the user is conservative with their gas usage, only the absolute minimum of orders is used. This can lead to unfavorable execution prices and/or arbitrage. If the user is spewy, they pay more fees, but have a higher chance of successful and cheap execution.
- The `asset_count` parameter is used for benchmarking purposes only.
- We should use `benchmarks_v2` for benchmarks. To avoid overcomplicating things, benchmarks should be pessimistic. The weight of `buy` and `sell` must be expressed as a function of `orders.len()`.
- If time permits using both mocks (due to the plug-and-play nature of the pallet) and integration testing would be preferred.
- There's a griefing vector where someone might make a bunch of small bids to made placing an ask exceedingly costly. This is prevented by two mechanisms: 1) There's a minimum order size implemented for the order book; 2) if necessary, the off-chain matcher will ignore orders that are too small to be profitable for the signer.

### Formulas

#### Slippage When Buying

Let $p_i(r) = e^{-r_i/b}$ denote the price function of a pool with reserve $r$. Buying outcome $i$ for $x$ dollars changes the reserve to $r_k' = r_k + x$ for $k \neq i$ and $r_i' = r_i - y(x)$, where

$$
y(x) = b \ln( e^{x/b} - 1 + e^{-r_i/b} ) + r_i - x.
$$

Thus,

$$
r_i' = -b \ln(e^{x/b} - 1 + e^{-r_i/b}) + x
$$

The price of $i$ post-execution is

\begin{align*}
p_i(r') &= \exp(\ln(e^{x/b} - 1 + e^{-r_i/b}) - x/b) \\
&= (e^{x/b} - 1 + e^{-r_i/b}) e^{-x/b} \\
&= 1 + e^{-x/b} (e^{-r_i/b} - 1) \\
&= 1 + e^{-x/b} (p_i(r) - 1).
\end{align*}

This formula can be used to calculate slippage. Furthermore, if we prescribe some $q \in (p_i(r), 1)$, we can see by solving for $x$ that the amount $x$ required to buy in order to move the price to $q$ is

$$
x = - b \ln \left(\frac{1-q}{1 - p_i(r)} \right).
$$

Taking fees into account changes the formula. Let $f$ denote the swap and external fees as fractional. As fees are deducted _before_ the trade, we just need to replace $x$ with $\hat x = (1 - f)x$.

#### Slippage When Selling

Selling the outcome $i$ for $x$ dollars changes the reserve of $i$ from $r_i$ to $r_i' = r_i + x' = r_i + x - z(x)$ where

$$
z(x) = -b \ln (e^{r_i/b} - 1 + e^{-x/b}) + r_i
$$

The price of $i$ post-execution is

\begin{align*}
p_i(r') &= \exp(-x/b - \ln(e^{r_i/b} - 1 + e^{-x/b})) \\
&= e^{-x/b} \exp(-\ln(e^{r_i/b} - 1 + e^{-x/b})) \\
&= \frac{e^{-x/b}}{e^{r_i/b} - 1 + e^{-x/b}}.
\end{align*}

Letting $q = p_i(r')$ and solving for $x$ yields

$$
x = b \ln \left( - \frac{1}{p_i(r)^{-1} - 1} + \frac{1}{q(p_i(r)^{-1} - 1)} \right).
$$

The point here is that we don't have to calculate $e^{r_i/b}$. It's perfectly sufficient to calculate $p_i(r) = e^{-r_i/b}$ and then take the reciprocal. Given our limits on prices in DLMSR, this should never be an issue.

Taking fees into account does not change any of the above since fees are deducted from the amount of collateral received by the trader _after_ the trade has gone through.

## Appendix: CDA Arbitrage

### Type I

For a market with $n$ outcomes, let $b_i$ and $a_i$ denote the current (largest) bid and (smallest) ask for $i$. If there is no bid for $i$, then $b_i = 0$ by definition; if there is no ask for $i$, then $a_i = 1$ by definition. Let $B = \sum_i b_i$ and $A = \sum_i a_i$ (the _total bid_ and _total ask_).

Arbitrage similar to that which we experienced with AMM 1.0 occurs in the following scenarios:

- (Mint-sell) If $B \geq 1$, then Alice can buy a number of complete sets (paying $1$ dollar per unit) and fill the bids until $B < 1$, receiving $B$ dollars per complete set sold. This yields a profit of $B - 1$ dollars per complete set.
- (Buy-burn) If $A \leq 1$, then Alice can fill the asks until $A > 1$, receiving $A$ complete sets for each dollar spent, and then sell the complete sets. This yields a profit of $A - 1$ dollars per complete set. Note that $A \leq 1$ implies that for every outcome $i$, there's placed at least on ask.

<!-- prettier-ignore -->
:::info
**Examples.** (1) Suppose we have the following bids:

- Outcome 1: Bid price = $0.40$ for $100$ units
- Outcome 2: Bid price = $0.35$ for $200$ units
- Outcome 3: Bid price = $0.30$ for $150$ units

The total bid is $1.05$. The arbitrage execution is as follows:

- Alice buys $100$ complete sets for $1.00$ dollars each.
- She sells $100$ units of $1$ for $0.40$ each, $100$ units of $2$ for $0.35$ each and $100$ units of $3$ for $0.30$ each, receiving $105$ dollars and making a profit of $5$ dollars.

The remaining bids are:

- Outcome 2: Bid price = $0.35$ for $100$ units
- Outcome 3: Bid price = $0.30$ for $50$ units

(2) Suppose we have the following asks:

- Outcome 1: Ask price = $0.30$ for $100$ units
- Outcome 2: Ask price = $0.35$ for $200$ units
- Outcome 3: Ask price = $0.30$ for $150$ units

The total ask is $0.95$. The arbitrage execution is as follows:

- Alice buys $100$ units of $1$, $2$ and $3$ each, spending $95$ dollars.
- She sells $100$ complete sets for $100$ dollars total, making a profit of $5$ dollars.

(3) It's not even necessary to sell the complete set if there are outcomes without bids. Suppose we have the following bids:

- Outcome 1: Bid price = $0.40$ for $100$ units
- Outcome 2: None
- Outcome 3: Bid price = $0.70$ for $150$ units

Then Alice can go ahead, buy $100$ complete sets and then fill the two orders to make a profit of $10$ dollars are $100$ units of outcome $2$. Note that the symmetric process for asks does _not_ work.
:::

Agents can always place orders which result in $A < 1$ or $B > 1$, but it's a mistake to do so. Instead, there's always a better option: If an agent wants to place an order which would move the market into arbitrage-able state, there's always a better option:

- Suppose that Alice wants to place a bid for $x$ units of $i$ at a price of $p$ which would move the total bid to $B > 1$. Let $B' < 1$ be the current total bid. Assume that you can buy $y$ units of each outcome token $j \neq i$ until the total bid slips below $B - p$. Then, instead of placing her bid, Alice can buy $z = \min\{x, y\}$ complete sets and fill the bids for the outcomes $j \neq i$. Then one of two things will happen:

- If $z = y$ (and thus $z < x$), then Alice has received $z$ units of the outcome token she was looking to buy, and the total bid is less than $B - p$. She can now place a bid for the remaining $x - z$ units of $i$ at price $p$ and will no longer move the total bid above $1$.
- If $z = x$ (and thus $z < y$), then Alice has received all $x$ units of the outcome token she was looking to buy.

In both cases, she only paid $1 - B'$ dollars per unit of $i$. Note that since $B' + p > 1$, we have $1 - B' < p$. This means that Alice paid less than she would have had to if she had placed a bid at price $p$.

- Suppose, on the contrary, Alice wants to place an ask to the tun of $x$ units of outcome $i$ at a price of $p$ which currently has no asks and which would keep the total ask $\leq 1$ (in other words, Alice want to quickly get rid of her tokens at a low price). Let $A' \geq 1$ be the current total ask. The fact that Alice's ask is the one to push the total ask below $1$ means that $A' - a_i + p < 1$.

Let $q = A' - a_i$. This is the current spot price for buying a "partial set" of all outcomes $k \neq i$. Assume that you can buy $y$ units of each outcome $k \neq i$ by filling other asks before this spot price slips above $1 - p$. Then, instead of placing her ask, Alice can buy $z = \min\{x, y\}$ units of each outcome $k \neq i$ and then sell $z$ complete sets (Alice already owns $x$ units of $i$). Then one of two things will happen:

- If $z = y$ (and thus $z < x$), then Alice has received $z$ dollars for selling complete sets. She still has $x - z$ units of $i$ left, and she has pushed the "partial set" spot price above $1 - p$. If she now places her order, this will move the total ask to the sum of the partial spot price $1 - p$ and the price she charges, $p$. In other words, the total ask is moved above $1$.
- If $z = x$ (and thus $z < y$), then Alice has received $x$ dollars for selling complete sets. She's gotten rid of all her holding of $i$ and has only paid $1 - p$ (at most) for each unit of partial sets. In effect, she's old her holdings of $i$.

A priori, we don't know exactly how much Alice has paid for the complete sets she then later sold (the spot price of partial sets may slip up gradually), but since she only bought $z$ of them, they cost at most $1 - p$ dollars, and at least some of them cost less. This nets Alice a profit of at least $p$ per complete set, her original price for selling $i$. So in effect, Alice has gotten rid of (some of) her $i$ tokens at at least as good a price as she intended.

<!-- prettier-ignore -->
:::info
**Examples.** (1.1) Suppose we have the following bids:

- Outcome 1: Bid price = $0.40$ for $100$ units
- Outcome 2: Bid price = $0.35$ for $200$ units
- Outcome 3: Bid price = $0.20$ for $150$ units

Alice wants to place a bid for $150$ units of $3$ at a price of $.40$. Doing so would push the market into an arbitrage-able state. Instead, she buys $100$ units of complete sets and then fills the first order and partially fills the second order. She retains $100$ units of $3$ and receives $75$ dollars, meaning that she paid only $25$ dollars for those $100$ units of $3$. This leave the order book in the following state:

- Outcome 1: None
- Outcome 2: Bid price = $0.35$ for $100$ units
- Outcome 3: Bid price = $0.20$ for $150$ units

Now Alice can place a bid for $50$ units of $3$ at a price of $.40$ without pushing the market into arbitrage-able state.

(1.2) Using the same setup as before, assume that Alice wants to place a bid for $50$ units of $3$ at a price of $.40$. Doing so would push the market into an arbitrage-able state. Instead, she buys $50$ units of complete sets and then fills the first and second orders partially. She retains $50$ units of $3$ and receives $37.5$ dollars, meaning that she paid only $12.5$ dollars for those $50$ units of $3$. This leave the order book in the following state:

- Outcome 1: Bid price = $0.40$ for $50$ units
- Outcome 2: Bid price = $0.35$ for $150$ units
- Outcome 3: Bid price = $0.20$ for $150$ units

(2.1) Suppose we have the following asks

- Outcome 1: Ask price = $0.30$ for $100$ units
- Outcome 2: Ask price = $0.35$ for $200$ units
- Outcome 3: Ask price = $0.40$ for $150$ units

Alice wants to place an ask for $150$ units of $3$ at a price of $0.20$. This would move the market into arbitrage-able state. Instead, she (paritally) fills the two orders for outcomes $1$ and $2$, yielding $100$ partial sets and leaving the market in the following state:

- Outcome 1: None
- Outcome 2: Ask price = $0.35$ for $100$ units
- Outcome 3: Ask price = $0.40$ for $150$ units

She can now sell $100$ complete sets, which means she's effectively sold $100$ units of $3$ at a price of $0.35$, and she can now place her ask without risking arbitrage, leaving the market in the following state:

- Outcome 1: None
- Outcome 2: Ask price = $0.35$ for $100$ units
- Outcome 3:
- Ask price = $0.40$ for $150$ units
- Ask price = $0.20$ for $50$ units (Alice's order)

(2.2) Using the same setup as before, assume that Alice wants to place a bid for $50$ units of $3$ at a price of $.20$. Doing so would push the market into an arbitrage-able state. This would move the market into arbitrage-able state. Instead, she (paritally) fills the two orders for outcomes $1$ and $2$, yielding $50$ partial sets and leaving the market in the following state:

- Outcome 1: Ask price = $0.30$ for $50$ units
- Outcome 2: Ask price = $0.35$ for $150$ units
- Outcome 3: Ask price = $0.40$ for $150$ units

She can now sell $50$ complete sets, which means she's effectively sold all her holding of $3$ at a price of $0.35$.
:::

<!-- prettier-ignore -->
:::info
**Note.** Provided that in the current state of the market arbitrage is not possible, not that filling an order can never more the market into a state where arbitrage is possible:

- When a bid is (partially) filled, changing the total bid from $B$ to $B'$, then $B' \leq B$ (this is true in particular if the filled bid was the last bid according to the definition above). Thus, $B' \leq B \leq 1$ is still satisfied and there's no danger of arbitrage.
- When an ask is (partially) filled, changing the total ask from $A$ to $A'$, then $A' \geq A$ (this is true in particular if the filled ask was the last ask according to the definition above). Thus, $A' \geq A \geq 1$ is still satisfied and there's no danger of arbitrage. If this is done, then the arbitrage circumvention described above should be used if necessary.
:::

### Type II

We discuss a second type of arbitrage which will most likely matter when dealing with binary markets.

#### Binary Markets

In this section we consider a binary market with outcomes _Yes_/_No_.

<!-- prettier-ignore -->
:::info
**Theorem.** An ask (resp. bid) for $x$ _Yes_ at a price of $p$ is equivalent to a bid (resp. ask) for $x$ _No_ at a price of $1 - p$ in the following sense: If a taker wants to buy $y \leq x$ units of _Yes_, instead of filling the ask (resp. bid) for _Yes_, they can buy $y$ complete sets and fill the bid (resp. ask) for _No_.
:::

This allows us to view a binary prediction market almost like a market for a single token.

<!-- prettier-ignore -->
:::info
**Example.** Suppose we have the following bids and asks on the market:

- Yes: Ask price = $0.80$ for $150$ units
- No: Bid price = $0.30$ for $50$ units

Suppose Alice wants to buy $100$ units of Yes. She could just partially fill the ask and pay $.80$ per unit. But instead, she could buy $50$ complete sets (yielding $50$ units of Yes/No but costing $50$ dollars), fill the bid (leaving her with $50$ Yes and $30$ dollars), effectively only paying $.70$ per unit of _Yes_, and then partially fill the ask for another $50$ units of Yes at a price of $.8$.
:::

#### Multi-Markets

We consider a multi-market with outcomes $1, \ldots, n$.

<!-- prettier-ignore -->
:::info
**Theorem.** Let $I \subseteq \{1, \ldots, n\}$ and let $J = \{1, \ldots, n\} \setminus I$ be its complement. Then as ask (resp. bid) for $x$ units of each $i \in I$ at a total price of $p$ is equivalent to a bid (resp. ask) for $x$ units of each $j \in J$ at a total price of $1 - p$ in the following sense: If a taker wants to buy $y \leq x$ units of each $i \in I$, instead of directly filling the asks, they can buy $y$ complete sets and fill the bids instead.
:::

This type of arbitrage will probably occur rarely, but might be matter.

<!-- prettier-ignore -->
:::info
**Example.** Suppose we have the following bids and asks on a market with five outcomes $1, \ldots, 5$:

- Outcome 1: Ask price = $0.40$ for $150$ units
- Outcome 2: Ask price = $0.35$ for $150$ units
- Outcome 3: Bid price = $0.10$ for $150$ units
- Outcome 4: Bid price = $0.10$ for $150$ units
- Outcome 5: Bid price = $0.10$ for $100$ units

Suppose Alice wants to buy $50$ units of $1$ and $2$. She could just partially fill the first two asks, paying $.75$ per "set" of $(1, 2)$. But she could also buy $50$ complete sets and then fill the bids for $3, 4, 5$, which will net her $.3$ dollars per "set" of $(3, 4, 5)$, effectively paying $.7$ dollars per set of $(1, 2)$. Note that if Alice wanted $150$ units, she can only buy $100$ units using arbitrage (until the bid for outcome $5$ is filled), and would have to buy the last $50$ units the conventional way.
:::