[feature] Order books v2

Order Books

THORChain uses CLPs (continuous liquidity pools) to execute trades, instead of order books (as we see in traditional finance). There are lot of benefits to CLPs, such as always having a counterparty for every trade. But there are cases where order books are more useful such as market making, or being able to put up a limit order. This "set and forget" tool can be very helpful and expand the type of person THORChain can be useful for. In addition, orders awaiting execution can be done in a way that contributes to pool depths.

What's Changed?

All non-native assets secured by THORChain must be deployed in a pool and paired with $RUNE. This is to ensure economic security. But deployed assets into the pool are susceptible to IL, which is counterproductive for staging capital for order book purposes. This has been the blocker in the past for implementing order books.

The advancement of synthetic assets, along with protocol funds being deployed into pools to counter LP leverage, opened the door to being economically and technically able to have order books on THORChain.

Design

Users send in a layer1 asset (ie BTC.BTC or RUNE) with a memo that is the same as the swap memo, but with order as the prefix instead of swap. The layer1 asset gets (feelessly) swapped to the synthetic counterpart and owned by the protocol, where it awaits execution. This also means that orders awaiting execution contribute to pool depths and therefore produce revenue for LPs/Nodes, fees are taken for creating and canceling the order. For orders where $RUNE is the sell (or from) asset (ie no immediate swap fee), a $RUNE fee is calculated in a swap to the layer1 asset and donated to the pool (same upon cancellation).

With the input number of coins (which should have a minimum value to protect against attacks), and the swap limit, the network can determine a ratio between the two input/output coins. This is used as a quick means to index and preprocess orders. Orders are placed into the kvstore with the following path

/oi/<input-asset>-<output-asset>/<ratio>

NOTE ratio will be a number (1e8 notation), but will need to be buffered/prefixed with 0s so that all ratios have the same length (in chars). This is to ensure iterating over the kvstore will have the correct order. So with a length of 3,

5    --> 005
50   --> 050
500  --> 500
5000 --> 500

The ratio length can be arbitrarily long (while keeping in mind chain bloat).

The value of this kvstore item is a list of txn hashes (which will commonly contain only a single hash). There should be a max cap on the number of hashes in this value, controlled by mimir. Suggestion is 50 to start.

[<hash1>, <hash2>]

The actual order details are stored in another location of

/o/<txhash>

Order Books

The number of order books on THORChain can be calculated as pnum(pnum+1) where pnum is the number of pools. This does include directional trades with single swaps and double swaps.

Order Book Execution

An order book is only executed after the swap queue is processed. Successful swaps that took place are tracked, which informs the network which order books need to be checked for any orders that are now executable. For example, if there was a single swap from BTC --> RUNE in the given block, the network shall test all order books where the "to" asset is BTC (which should be pnum+1 of order books).

When an order book is checked for executable swaps, the current ratio between the from/to asset is calculated, and the network iterates over this kvstore path (/o/<input-asset>-<output-asset>/...) and quickly tests the order ratio against the current ratio, which effectively tests a perfect swap (feeless). If this doesn't pass, then we can break the loop and assume the remainder of the orders cannot be satisfied and do not need to be tested. If it does pass, the network can do a second test which includes swap fees. If this doesn't pass, we skip it and try the next order. If it does pass, the order is removed from the order book and added to the swap queue (which maintains swap execution priority). Any orders that fail the swap due to swap limit not being met, are removed from the swap queue and added back to the order book. All other errors trigger a refund. Only 100 orders can be added to the swap queue each block (since there is a 100 swap limit per block anyways). This puts a cap on the max computational expense of managing the order books.

Here is a flow chart showing this logic.

This design ensures that only some order books are checked in each block (sometimes none), only some orders within each order book and only highly confident orders are going to get added to the swap queue to be attempted to be executed. This should mean that there is no upward bound on how many orders the network can hold computationally (although chain bloat should be considered).

Order Cancellation

A new memo is created to cancel an order which looks like this

order-:<txhash>

Canceled order get swapped (feelessly) back to the layer1 asset if the order was provided as a layer1 asset.