# ZIP-7: AMM 2.0 (Architecture)

<!-- prettier-ignore -->
:::info
Author: Dr. Malte Kliemann
Revision: 3
:::

## PR0: Fix Fixed Math Types

The functions `b*` (`bmul`, etc.) used to do math with the `Balance` type put an enourmous strain on the developer as they require excessive conversions between `u128` and `Balance`. Most multiplication of fixed decimal numbers looks like this:

let z = bmul(x.saturated_into(), y.saturated_into())?.saturated_into();

To make matters worse, sometime type annotations are necessary to help Rust's compiler with type inferrence.

We will replace this with:

let z = x.bmul(y)?;

In detail:

- Define convenience traits `Checked*Res` which wrap `Checked*` but return `Result<Self, DispatchError>` instead of `Option<Self>` and blanket implement them.
- Define traits `FixedMul`, `FixedDiv`, etc., each of which contain the logic of the `b*` functions currently contained in the `fixed.rs` of zrml-swaps and `zeitgeist_primitives::math::fixed` (except for power functions, which will be handled in a separate PR for the sake of simplicity), and add `*_floor` and `*_ceil` variants of these functions with the specified rounding behavior. The functions will return a `Result<Balance, DispatchError>` to make them convenient.
- Blanket implement `Fixed*` for all types which implement `AtLeast32BitUnsigned`. (This may seem like slight overkill, but is convenient when trying to convert `BASE` to the balance type.)
- Replace all usages of the old `b*` functions with the new functions _using the appropriate rounding behavior_ (always round to the signer's disadvantage).

This comes at no real cost to us as all substrate balance types implement `AtLeast32BitUnsigned`.

## PR1: Implement Liquidity Trees

This PR will remove thee restriction that pools can only be deployed by the market creator by replacing `SoloLp` with an implementation of the liquidity tree.

The _liquidity tree_ is a tool for tracking liquidity in a designated system. This tool is essentially a segment tree with a maximum depth of $D = 10$, which allows for a maximum of $N = 2^D = 1024$ nodes. Each node in the tree represents the position of a liquidity provider.

Each node in the tree contains the following information:

- The owner's `account`
- The owner's `stake` in the pool
- The owner's `fees`
- The `descendant_stake` of the owner's descendants
- The `lazy_fees` for lazy distribution

The `stake` field is so-to-speak equivalent to the pool shares balance in the old AMM design.

A node of the tree is deemed _abandoned_ if the owner's stake is zero. Alongside the tree, two maps are maintained:

- A map which stores abandoned nodes. This map enables nodes abandoned by their owner to be _reassigned_.
- A map which maps owners to their node. This enables fast lookup.

### Exit Fees

### Lazy Propagation of Fees

Fees are propagated up the tree in a 'lazy' manner, i.e., the propagation happens when liquidity providers deposit or withdraw. The process of lazy propagation at a node $n$ is as follows:

If node.descendant_stake == 0 then
    node.fees ← node.fees + node.lazy_fees
Else
    fees ← (node.descendant_stake / (node.stake + node.descendant_stake)) * node.lazy_fees
    node.fees ← node.fees + fees
    remaining ← node.lazy_fees - fees
    For each child in node.children() do
        child.lazy_fees ← child.lazy_fees + (child.stake / child.descendant_stake) * remaining
    End For
End If
node.lazy_fees ← 0

### Denial of Service Attack

An attacker might attempt to execute a Denial of Service (DoS) attack. This attack comes in two flavors, both griefing-only vectors: preventing others from joining the tree and degrading its performance.

The first aspect of the attack, preventing others from joining the tree, would involve an attacker adding liquidity repeatedly to fill up all the positions in the tree. Our current structure counters this by increasing the required liquidity for each position by 1%. Therefore, to prevent others from joining the tree, the attacker would need to provide the $1.01^N \approx 26612$ fold of the initial required liquidity at the final position. Given a minimum liquidity of 10 DOT, this would amount to a substantial sum, well over a million dollars at the current market price. Moreover, if the attacker withdraws their liquidity, the abandoned nodes are reassigned, forcing the attacker to remain a liquidity provider to maintain the attack.

The second aspect of the attack, degrading the performance of the tree, is largely mitigated by the design of the liquidity tree. The operations of adding to or withdrawing from the tree have time complexity of $O(\log n)$, due to the binary tree structure. Therefore, regardless of the number of nodes in the tree, the time required to perform these operations increases logarithmically, not linearly. This limits the effectiveness of an attack aimed at degrading performance by clogging the tree with nodes.

In summary, although a determined attacker might attempt to clog the liquidity tree, the economic and computational challenges posed by such an attack make it unlikely to be successful or sustained.

#### Limitations

- Can't have more than $N = 1024$ liquidity providers per pool.
- Reading data from the tree instead of an indexer may cause some confusion. It's difficult to tell how many fees you're actually owed until the propagation is done.

## PR2: Implement AMM 2.0

AMM 2.0 will be implemented without restrictions:

- Remove requirement that a market have only two outcomes
- Remove lower price barrier for buys
- Extend testing of `math.rs`

The main problem that we encountered when implementing AMM 2.0 was how to allow users to buy at small prices. Recall that the amount $y(x)$ received when buying $i$ for $x$ units of collateral is

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

The problem is that if the price $p_i = e^{-r_i/b}$ is very small or even underflows to zero and $x$ is every small, then the argument of the logarithm is very close to zero, where the logarithm's derivative goes to infinity. The closer the argument is to zero, the worse the effect of rounding errors.

The solution is to require that the argument of of $\ln$ is always sufficiently large. If $p_i$ is very small (or, equivalently, $r_i$ is very large), then $x$ must be very large. The exact values are chosen as follows. We require that the argument $e^{x/b} - 1 + e^{-r_i/b}$ be larger than $c = \frac{1}{10}$. On the interval $[c, \infty]$, the logarithm has derivative $\leq c^{-1} = 10$, so all rounding errors in the argument of $\ln$ cause (only) ten times the error in the calculation of $\ln$.

Of course, we need to keep the other restriction, which is $x \leq Ab$ where $A$ is a small constant, say, $20$. This is required to prevent overflows when calculating $e^{x/b}$.

## PR3: Sunsetting Old Pools

This section describes the process of sunsetting the old pools. As this can be done in a separate pull request, we shall do so:

- Remove Rikiddo from swaps:
- Remove `FixedTypeU`
- Remove `FixedTypeS`
- Remove `MinSubsidy`
- Remove `MinSubsidyPerAccount`
- Remove `RikiddoSigmoidFeeMarketEma`
- Remove `pool_join_subsidy`
- Remove `pool_exit_subsidy`
- Remove appropriate errors and events
- Remove `SubsidyProviders`
- Remove `distribute_pool_share_rewards`
- Remove `destroy_pool_in_subsidy_phase`
- Remove `end_subsidy_phase`
- Remove all `if`-`else` and `match` expressions involving `ScoringRule::Rikiddo` (in `get_spot_price`, for example)
- Remove Rikiddo from the runtime
- Remove Rikiddo from prediction-markets:
- Remove all `if`-`else` and `match` expressions involving `ScoringRule::Rikiddo` (in `approve_market`, for example)
- Remove `MaxSubsidyPeriod`
- Remove `MinSubsidyPeriod`
- Remove swaps dependency from from prediction-markets:
- Remove `create_cpmm_market_and_deploy_asstes`
- Remove `deploy_swap_pool_and_additional_liquidity`
- Remove `deploy_swap_pool_for_market`
- Remove `Config::Swaps`
- Remove clean up functionality from swaps:
- Remove `admin_clean_up_pool`
- Remove `clean_up_pool`
- Remove `clean_up_pool_categorical`
- Remove automated arbitrage from swaps:
- Remove `ARBITRAGE_THRESHOLD` and `ON_IDLE_MIN_WEIGHT`
- Remove `PoolsCachedForArbitrage`
- Remove `Hooks::on_idle`
- Remove `execute_arbitrage_all`
- Remove `apply_to_cached_pool`
- Remove `execute_arbitrage`
- Remove `arbitrage.rs`
- Move `root.rs` to `primitives::math` (might be useful in the future)
- Remove `ScoringRule::CPMM`
- Mark `MarketStatus::Suspended`, `MarketStatus::CollectingSubsidy` and `MarketStatus::InsufficientSubsidy` as deprecated (avoids a migration)
- Remove `market_account` from `MarketCommons`

Note that the Rikiddo pallet will remain unchanged. We refrain from removing the `total_subsidy` field from the `Pool` struct in an effort to keep things simple. This will be done in a separate PR described below.

In addition to these changes, a migration to handle left-over liquidity is required:

- Close all pools that are currently open
- Migrate all markets from `ScoringRule::CPMM` to `ScoringRule::Lmsr`
- Clear caches used for auto-closing pools

All "old" pools are then closed and no longer accept swaps or liquidity, but users will still be able to withdraw their funds. All pools with ID greater or equal to the cut-off will behave normally. New pools can only be created via root.

Liquidity providers are not actively involved in the migration. After withdrawing their remaining liquidity from the old pools, they can use the new pools without any restrictions.

## PR4: Using zrml-swaps for Other Purposes

Make pool creation more monolithic.

- Remove `PoolStatus`.
- Change fields from the struct `Pool`:
- Remove `base_asset`
- Remove `market_id`
- Remove `scoring_rule`
- Remove `total_subsidy`
- Replace `pool_status` with `open: bool`
- Change type of `swap_fee` from `Option<Balance>` to `Balance`
- Add an `owner` field of type `PoolOrigin`
- Add a `create_pool` extrinsic which can only be called by `PoolOrigin` (details left to the implementor)
- Add a `close_pool` extrinsic which allows `owner` to close pools which are no longer needed or wanted (details left to the implementor)
- Set `PoolOrigin` to `EnsureRoot` for now; allow users to create their own pools later

While we're at it, we will rename the field `scoring_rule` of `Market` to `trading_mechanism` as the term _scoring rule_ does not apply to CDA or parimutuel.

Of course, this includes a storage migration. Since we're already doing some housekeeping, we'll also make the following changes:

- Change the type of `total_weight` from `Option<u128>` to `Balance` (remove `Option` and make the type generic over `Balance`)
- Change the type of `weights` from `Option<BTreeMap<Asset<MarketId>, u128>>` to `BTreeMap<Asset<MarketId>, Balance>` (remove `Option` and make the type generic over `Balance`)

This allows us to make the Balancer math generic over `Balance`, considerably reducing the need for `saturated_into` calls in zrml-swaps.