# Penumbra Dex Planning

## Action Items

* Routing
* Have high level algorithm designed (https://hackmd.io/jtoiMn0pQnSTZlOi2ig5Wg)
* Specify/formalize routing algorithm for first version of dex (seems like multi-hop routing isn't well described)
* Aggregate liquidity between pairs
* https://github.com/penumbra-zone/penumbra/issues/1722
* Does 4-5 hops make sense? Do some statistical analysis possibly (maybe better after mainnet when there are real liquidity positions)
* Balance AMM trade efficiency vs computational complexity of routing
* Binning of positions
* Does caching routes also make sense? Unclear
* Bin based on ticks similar to Uniswap (https://duality.gitbook.io/duality-documentation/concepts/ticks)
* Ticks based on log scale, each tick = 1 bp relative to adjacent tick
* Initial implementation can be w/o binning
* Implementation Order
1. Composition of AMMs (for routing): if we have one AMM trading between asset 1 and 2, and one trading between 2 and 3, we should be able to compose the two to trade between 1 and 3
- Add type information to trading struct
- Implement formulas in DEX engine design doc. Part of this is making the formulas work for fixed-width integers and managing precision.
- Tests
2. Implement `Path` type for routing
- Maintains a list of asset IDs and an end-to-end trading function
- For Path of length 1, list of asset IDs: [asset1, asset2] and trading function is the original trading function
- We'll want a `Path.extend(&self, trading_function: TradingFunction) -> Path` method that puts the next asset ID into the list and composes the trading functions together
- Stub struct

                struct Path {
                    asset_ids: Vec<asset::Id>,
                    trading_function: TradingFunction,
                }
                
                impl Path {
                    pub fn start(&self) -> asset::Id {
                        // return first element
                    }
                    
                    pub fn end(&self) -> asset::Id {
                        // return last element
                    }
                }
                
                impl PartialOrd for Path {
                    // comparison should return `None` if start and end asset IDs don't match
                    // otherwise compare by price
                }

3. Design indices for liquidity positions
- Non-consensus index by price
- Want to be able to query for cheapest position for some directional trading pair (check DEX engine design doc for notes)
- Want a big-endian key encoding so we can do range queries that return positions in order
- Let's _maybe not_ bin these from the start, but plan to eventually, since the routing and execution phases have different semantics
- Rabbit holes: How do we adjust bins by adding/removing positions? Are those operations numerically stable? Do we have error propagation, or do we have to rebuild the bins every time positions change?
- Consensus indices to track all positions
- Unclear what these should look like
- Probably want a `PositionManager` similar to `NoteManager` to encapsulate state-related functions and enforce consensus logic and indexing etc.
- Implementation of action handlers for `Position` actions
4. Implement routing
- Use data from part 3 with the `Path` from part 2 along with the algorithm from part 1 to construct paths based on trading pairs and available liquidity positions
- Want to specify a max-length for routes as a parameter for the routing code
- How do we bound the number of edges we consider?
- Don't want a situation where dust positions blow up graph traversal
- Based on amount of available liquidity, to exclude dust positions? Heuristics are unclear
5. Implement execution
- Routing is approximate (but consistent), but execution must be exact
- Routing may perform rounding, binning, etc. to optimize
- Execution will take the `Path` output from routing, and begin executing based on the maximum input for that path (estimated by the `TradingFunction` from the `Path`)
- Walk along the Path and use all liquidity positions necessary at each hop
- Make trades against each position and update the available reserves (via `PositionManager`, which will causes indices to be updated)
6. Implement Arbitrage
- Form a path from Penumbra -> Penumbra, and find out whether the optimal price is `<1`
- If so, execute, and burn the profit
* Execution
* How do you accumulate AMM products in uint256, what size is necessary?
* Convert existing swap to use new dex liquidity positions instead of fixed positions
* Routing (and execution) both need to happen when the `Swap` is processed, `SwapClaim` will release outputs
* Are there slippage limits/price limits?
* Yes, probably as a global consensus parameter
* May want to change Component trait to take `&mut State` instead of `&mut StateTransaction` so we can construct transactions on-demand
* This would allow us to trigger the slippage limit by raising an Error, undoing the in-progress execution phase `StateTransaction`
* What does it mean to place a market order? Swap is market order, limit orders are handled by placing LP
* Does our algorithm exhaust optimal paths that don't fulfill all swaps? i.e. 10% of PEN -> Atom can be fulfilled through a cheaper route, and the other 90% needs a more expensive route
* Not as written (draw the rest of the owl)
* How to join interface from shielded pool to dex engine isn't fully described
* Find best priced path, execute until liquidity exhausted, repeat
* If there's not enough liquidity we could: abort the whole trade, or change semantics of `BatchSwapOutputData` to no longer have explicit success/failure and price it in to exchange rates to represent partial execution
* https://github.com/penumbra-zone/penumbra/issues/1724
* Proto Interfaces
* Settle on interfaces
* Are we done here?
* Liquidity Position Management
* We have some protos but no implementations
* Implement:
* `PositionOpen`
* `PositionClose`
* `PositionWithdraw`
* `PositionRewardClaim`
* ~~Modify existing CPMM reserves to iterate over all open liquidity positions~~
* It should be removed, instead, it doesn't make sense with the new AMM design (hence `Stub`)
* https://github.com/penumbra-zone/penumbra/issues/1725
* Probably want to have some functions to approx Univ2, Univ3, etc. for a few known AMMs
* Testing
* Kind of tricky if you don't have liquidity positions to work against
* Possible (in theory) to approximate payoff curve of a CPMM using all linear positions
* Might make sense to figure that out earlier, so when we want to do testing, we can build out positions to test against based on having Univ2 pools for every pair
* We could propose a desired payoff curve and then generate test positions that approximate that payoff curve
* Future
* Market maker APIs (price feeds, simulated trades, etc.)
* Osmosis replication for stress testing? Collect trades from Osmosis pools and replay on our dex, evaluate: do users get better trade execution, is there less slippage, etc. do we want this before mainnet? Seems nice-to-have -- priority?
* Sharding of swaps client-side (could happen post-mainnet, should be relatively simple) -- priority?
* pcli: view route of trade, useful for debugging
* dust positions can add computational cost forever, ideas:
* gas attached to positions rather than transactions?
* every time position is executed against, charge a little gas
* or, if the pricing of the dust positions is out of step with the rest of the positions, they won't be considered during routing so this won't be an issue