# Penumbra DEX Engine Design

## Overview

We follow the notation in [Improved Price Oracles: Constant Function Market Makers][ipo-cfmm].

Penumbra uses a hybrid, order-book-like AMM with automatic routing. Liquidity on Penumbra is recorded as many individual concentrated liquidity positions, akin to an order book. Each liquidity position is its own AMM, with its own fee tier, and that AMM has the simplest possible form, a constant-sum (fixed-price) market maker. These component AMMs are synthesized into a global AMM by the DEX engine, which optimally routes trades across the entire liquidity graph. Because each component AMM is of the simplest possible form, this optimization problem is easy to solve: it's a graph traversal.

## Execution Phases

Penumbra has no intra-block trade ordering, so DEX execution operates at the end of the block in four phases:

1. All newly opened liquidity positions are added to the active set.
2. Trades are batched by liquidity pair and executed (in what order? random?).
3. The chain arbitrages all active positions using an infinite-sized flash loan and burns the arbitrage profits.
4. All newly closed positions are removed from to the active set.

Because execution is phased, market-makers can create fill-or-kill positions with prices valid for exactly one block without having to compete for ordering within that block, by opening and then closing a liquidity position in the same transaction.

## Trading Functions

Each position's trading function is of the form
$$
\varphi(R) = p_1R_1 + p_2R_2
$$

with a fee parameter $\gamma$.

A trade with input amounts $\Delta = (\Delta_1, \Delta_2)$ and output amounts $\Lambda = (\Lambda_1, \Lambda_2)$ is accepted if and only if
$$
\varphi(R) = \varphi(R + \gamma\Delta - \Lambda).
$$

The new reserves from this trade are $R' = R + \gamma\Delta - \Lambda$. Conservation of value is recorded by the equation
$$
R + \Delta = (R + \gamma\Delta - \Lambda) + \Lambda + (1-\gamma)\Delta.
$$

On the left-hand side, we have the initial reserves $R$ (held by the AMM) and the trade input $\Delta$ (held by the trader); on the right-hand side, we have the updated reserves $R' = R + \gamma\Delta - \Lambda$ (held by the AMM), the trade output $\Lambda$ (held by the trader), and the fee $(1-\gamma)\Delta$.

The fee is recorded by being accumulated into the position's reserves, which are updated as
$$
R'' = R' + (1 - \gamma)\Delta.
$$

### Explicit Formulas

In practice, $\Delta_1 \Delta_2 = 0$, i.e., one or the other input type is zero.

When $\Delta_2 = 0$, $\Lambda_1 = 0$ and the trader is trading $\Delta_1$ for $\Lambda_2$. The formulas become
$$
\varphi(R) = \varphi(R + \gamma\Delta - \Lambda) \\
p_1R_1 + p_2R_2 = p_1(R_1 + \gamma\Delta_1) + p_2(R_2 - \Lambda)
$$

so we can compute $\Lambda_2$ as
$$
p_2\Lambda_2 = p_1(R_1 + \gamma\Delta_1) - p_1R_1 + p_2R_2 - p_2R_2 \\
\Lambda_2 = \frac {p_1} {p_2} \gamma \Delta_1
$$

Similarly, when trading $\Delta_2$ for $\Lambda_1$, we have
$$
\Lambda_1 = \frac {p_2} {p_1} \gamma \Delta_2.
$$

These formulas clarify the role of $p_1$ and $p_2$ as controlling the price, and $\gamma$ as controlling the spread.

### Composition of AMMs

Given two AMMs, $\varphi(R_1, R_2) = p_1 R_1 + p_2 R_2$ with fee $\gamma$ trading between assets $1$ and $2$ and $\psi(S_2, S_3) = q_2 S_2 + q_3 S_3$ with fee $\delta$ trading between assets $2$ and $3$, we can compose $\varphi$ and $\psi$ to obtain a synthetic position $\chi$ trading between assets $1$ and $3$ that first trades along $\varphi$ and then $\psi$ (or along $\psi$ and then $\varphi$).

We want to write the trading function of this AMM as $\chi(T_1, T_3) = r_1 T_1 + r_3 T_3$ with fee $\varepsilon$, prices $r_1, r_2$, and reserves $T_1, T_2$.

First, write the trade inputs and outputs for each AMM as $\Delta^\chi = (\Delta^\chi_1, \Delta^\chi_3)$, $\Lambda^\chi = (\Lambda^\chi_1, \Lambda^\chi_3)$, $\Delta^\varphi = (\Delta^\varphi_1, \Delta^\varphi_2)$, $\Lambda^\varphi = (\Lambda^\varphi_1, \Lambda^\varphi_2)$, $\Delta^\psi = (\Delta^\psi_2, \Delta^\psi_3)$, $\Lambda^\psi = (\Lambda^\psi_2, \Lambda^\psi_3)$, where the subscripts index the asset type and the superscripts index the AMM. We want $\Delta^\chi = \Delta^\varphi + \Delta^\psi$ and $\Lambda^\chi = \Lambda^\varphi + \Lambda^\psi$, meaning that
$$
(\Delta_1^\chi, \Delta_3^\chi) = (\Delta_1^\varphi, \Delta_3^\psi), \\
(\Lambda_1^\chi, \Lambda_3^\chi) = (\Lambda_1^\varphi, \Lambda_3^\psi), \\
(\Delta_2^\varphi, \Delta_2^\psi) = (\Lambda_2^\psi, \Lambda_2^\varphi).
$$

The reserves $T_1$ are precisely the maximum possible output $\Lambda_1^\chi$. On the one hand, we have $\Lambda_1^\chi = \Lambda_1^\varphi \leq R_1$, since we cannot obtain more output from $\varphi$ than its available reserves. On the other hand, we also have
$$
\Lambda_1^\chi = \Lambda_1^\varphi = \frac {p_2} {p_1} \gamma \Delta_2^\varphi = \frac {p_2} {p_1} \gamma \Lambda_2^\psi \leq \frac {p_2} {p_1} \gamma S_2,
$$

since we cannot input more into $\varphi$ than we can obtain as output from $\psi$. This means we have
$$
T_1 = \max \left\{ R_1, \frac {p_2} {p_1} \gamma S_2 \right\} \\
T_3 = \max \left\{ S_3, \frac {q_2} {q_3} \delta R_2 \right\},
$$

using similar reasoning for $T_3$ as for $T_1$.

On input $\Delta^\chi_1$, the output $\Lambda^\chi_3$ is
$$
\Lambda^\chi_3 = \Lambda^\psi_3
= \frac {q_2} {q_3} \delta \Delta^\psi_2
= \frac {q_2} {q_3} \delta \Lambda^\varphi_2
= \frac {q_2 p_1} {q_3 p_2} \delta \gamma \Delta^\varphi_1
= \frac {q_2 p_1} {q_3 p_2} \delta \gamma \Delta^\chi_1,
$$

and similarly on input $\Delta^\chi_3$, the output $\Lambda^\chi_1$ is
$$
\Lambda^\chi_1 = \Lambda^\varphi_1
= \frac {p_2} {p_1} \gamma \Delta^\varphi_2
= \frac {p_2} {p_1} \gamma \Lambda^\psi_2
= \frac {p_2 q_3} {p_1 q_2} \gamma \delta \Delta^\psi_1
= \frac {p_2 q_3} {p_1 q_2} \gamma \delta \Delta^\chi_1,
$$

so we can write the trading function $\chi$ of the composition as
$$
\chi(T_1, T_3) = r_1 T_1 + r_3T_3
$$

with $r_1 = p_1 q_2$, $r_3 = p_2 q_3$, fee $\varepsilon = \gamma \delta$, and reserves $T_1$, $T_3$.

## Liquidity Positions

A **liquidity position** consists of:

* A trading pair $(\mathsf a_1, \mathsf a_2)$ recording the asset IDs of the assets in the pair. The asset IDs are $F_q$ elements, and the pair is made order-independent by requiring that $\mathsf a_1 < \mathsf a_2$.
* A trading function $\varphi$, specified by $p_1, p_2, \gamma$.
* A random, globally-unique 32-byte nonce $n$.

This data is hashed to form the **position ID**, which uniquely identifies the position. The position nonce ensures that it is not possible to create two positions with colliding position IDs.

The reserves are pointed to by the position ID and recorded separately, as they change over time as trades are executed against the position. One way to think of this is to think of the position ID as an ephemeral account content-addressed by the trading function whose assets are the reserves and which is controlled by bearer NFTs recorded in the shielded pool.

Positions have four **position states**, and can only progress through them in sequence:

* an **opened** position has reserves and can be traded against;
* a **closed** position has been deactivated and cannot be traded against, but still has reserves;
* a **withdrawn** position has had reserves withdrawn;
* a **claimed** position has had any applicable liquidity incentives claimed.

Control over a position is tracked by a **liquidity position NFT** (**LPNFT**) that records both the position ID and the position state. Having the LPNFT record both the position state and ID means that the transaction value balance mechanism can be used to enforce state transitions:

- the `PositionOpen` action debits the initial reserves and credits an opened position NFT;
- the `PositionClose` action debits an opened position NFT and credits a closed position NFT;
- the `PositionWithdraw` action debits a closed position NFT and credits a withdrawn position NFT and the final reserves;
- the `PositionRewardClaim` action debits a withdrawn position NFT and credits a claimed position NFT and any liquidity incentives.

Separating _closed_ and _withdrawn_ states is necessary because phased execution means that the exact state of the final reserves may not be known until the closure is processed position is removed from the active set.

However, having to wait for the next block to withdraw funds does not necessarily cause a gap in available capital: a marketmaker wishing to update prices block-by-block can stack the `PositionWithdraw` for the last block's position with a `PositionOpen` for their new prices and a `PositionClose` that expires the new position at the end of the next block.

Separating _withdrawn_ and _claimed_ states allows retroactive liquidity incentives (e.g., $X$ rewards over some time window, allocated pro rata to liquidity provided, etc). As yet there are no concrete plans for liquidity incentives, but it seems desirable to build a hook for them, and to allow them to be funded permissionlessly (e.g., so some entity can decide to subsidize liquidity on X pair of their own accord).

## Routing

To route a trade, perform a graph traversal from the source asset $\mathsf s$ to the target asset $\mathsf t$, building up a path that tracks its component positions as well as the trading function of the whole path. Select the path with the lowest price, and fill as much of the trade as possible. If not all of the trade can be filled, repeat the process with the remaining quantity.

To perform the graph traversal, use a variant of Bellman-Ford. Maintain a mapping `BTreeMap<asset::Id, Path>` recording the optimal route from $\mathsf s$ to $\mathsf a$ for each intermediate asset $\mathsf a$ we've considered. Starting at $\mathsf s$, iterate over all neighboring assets $\mathsf a$

- [ ] Fill in description

Each `Path` contains:

- a "whole-path" trading function and synthetic reserves
- data implying the list of positions we would execute against if we were to use the path
- [ ] do we want to track a list of positions here, or do we want to track just the list of intermediate assets?

The `Path` API would primarily be:

- `Path::extend(&self, edge: TradingFunction) -> Result<Path>` extends `self` along `edge` or errors if the asset types don't line up
- `impl PartialOrd for Path` where comparison is `None` if the start and end assets aren't equal, and otherwise compares by price

## Data Types

- `TradingPair`: a pair of assets, made logically order-independent by always choosing a canonical ordering on asset IDs
- `BatchSwapOutputData`: describes the results of a batched swap
- `TradingFunction`: describes the AMM, consisting of
- `TradingPair` declaring the trading pair
- `BareTradingFunction` with $R_1$, $R_2$, $p_1$, $p_2$
- `Position`: contains a `TradingFunction`, and a nonce that should be globally unique (so that we can treat positions NFTs as bearer assets).
- `Reserves`: a pair of `Amount`s

## DEX State

### Consensus State

We need to record:

- A global, append-only set of nonces used by existing positions
- The set of positions for each trading pair (grouped by position state)
- The current reserves for each position (only needed for open and closed positions)
- The volume executed against each position (can be deleted at some point?)

Scratch:

- `dex/position_nonce/{nonce}`
- Records nonces used by existing liquidity positions
- On `PositionOpen`, check that the nonce is not present, then add it
- `dex/positions/{trading_pair}/opened/{position_id}`
- Records opened positions for the given `trading_pair`
-

### Nonconsensus State

- Additional indices on position data (what would be useful?)
- Cached routing data?
- Pre-compute some common routes on liquidity position creation? i.e. to penumbra, atom, btc, usdc etc.
- Store effective prices per block height and pair (tricky because they can change, is this even useful?)

[ipo-cfmm]: https://arxiv.org/abs/2003.10001

### scratch (the following is partly wrong)

Informally but slightly more precisely, a path consists of a list of liquidity positions, a fillable quantity $\Delta$, and a price $q$.

To route an input trade $\Delta_{\mathsf a}$ from $\mathsf a$ to $\mathsf b$, initialize an empty path with $\Delta = \Delta_{\mathsf a}$, $p = 1$, and an empty list of positions.

To extend a path along the liquidity graph (say via asset $\mathsf c$), construct (or query) the list of all liquidity positions with trading pair $(\mathsf a, \mathsf c)$ with nonzero reserves $R_{\mathsf a}$ of asset $\mathsf a$, sorted by the effective price $\gamma p/q$.[^1] Select the position with minimum price, push it to the list, and update $\Delta \gets \min \{\Delta, R_{\mathsf a}\}$, $r \gets r \gamma p / q$.

[^1]: If the canonical ordering of the pair is $(\mathsf c, \mathsf a)$, this would instead be sorting by $\gamma q/p$, but we ignore this case for simplicity of presentation.

- [ ] How do we formulate this in terms of exact integer arithmetic?

Exact version of one hop:

- pair $(\mathsf a, \mathsf c)$ with positions $\{ (\varphi^{(0)}, R^{(0)}), (\varphi^{(1)}, R^{(1)}), \ldots\}$ sorted by effective price $\gamma^{(i)} p^{(i)} / q^{(i)}$ with $R^{(i)}_{\mathsf c} \neq 0$
- how do we construct byte strings such that the lex order on those byte strings is the numeric order on $\gamma^{(i)} p^{(i)} / q^{(i)}$?
- we have an ordered k/v store for nonconsensus indexes, and we want the key to be some byte string with the correct ordering and the value to be data we use for working with the position
- big-endian integer encodings have the property that the ordering on encodings is the ordering on integers, but we have a fraction
- set the key as big-endian repr of $\lfloor 2^{128} \gamma^{(i)} p^{(i)} / q^{(i)} \rfloor$?
- set the value as $(\varphi^{(i)}, R^{(i)})$? or as the position ID? if position data, we have what we need immediately, if position ID, we have to query again, but we can then name the position when we want to execute against it later. or, we could save both
- Best price will be $(\varphi^{(0)}, R^{(0)})$, reserves are $R^{(0)} = (R_{\mathsf a}^{(0)},R_{\mathsf c}^{(0)})$
- We want to fill as much of the trade as possible against the reserves. There are two cases: either the reserves of the best position are enough to execute the entire trade, or they aren't, in which case we want to consume the entire available reserves, setting $R_{\mathsf c} =0$ exactly rather than a dust amount so that we'll exclude it from the list in future iterations.
- The maximal output occurs when $\Lambda = R_{\mathsf c}$. Since (with exact arithmetic) $\Lambda = \gamma \frac q p \Delta$, we have $\Delta = \frac p q \frac 1 \gamma \Lambda$, and we can write the input amount that causes the maximal output as $\Delta_{max} = \lceil \frac p q \frac 1 \gamma R_{\mathsf c} \rceil$. (Here, the correct way to ensure conservation of value is to round up, so that we consume more of the input amount).
- If $\Delta_{max} \leq \Delta$, the maximal output is less than the desired output, so we should consume the entire reserves, setting $\Lambda \gets R_{\mathsf c}$ and $\Delta \gets \Delta_{max}$
- If $\Delta_{max} > \Delta$, the maximal output is greater than the desired output, so we should
- Suppose we do the following:
- Set $\Delta' = \min \{ \Delta, R_{\mathsf c}^{(0)}\}$
- Compute $\Lambda = \operatorname{round}(\gamma \frac q p \Delta')$ ("correct" defn of round tbd)
- Update reserves $R \gets R + (\Delta, 0) - (0, \Lambda)$
- this will accumulate fees into position
- common case is that $\Delta > \Delta'$, in this case we want to execute so that $R^{(0)}_{\mathsf c}$ is set to $0$ exactly (rather than a dust amount), so that in the future, we exclude it from the list
- can we get that by working "forwards" from $\Delta'$ to $\Lambda$ or do we need to work "backwards"?
- tmp