# In Search of Efficient On-Chain CLOBS

## Introduction
The DeFi ecosystem, rich in innovation, has birthed diverse trading mechanisms, each with its unique set of advantages and challenges. Central to these mechanisms are the Central Limit Order Books (CLOBs), known for their capacity to enable precise price discovery and offer traders unparalleled control. Historically, the transition of CLOBs to on-chain platforms was riddled with challenges. The inherent throughput limitations of traditional L1 and L2 solutions curbed the swift operations CLOBs demanded, often rendering them unprofitable for market makers. Additionally, the transparent nature of on-chain operations opened the door for validators to engage in front-running, exploiting the spread by manipulating transaction sequences. Furthermore, the intricate operations intrinsic to CLOBs could lead to skyrocketing gas costs, especially during network congestion periods. The emergence of advanced scaling solutions and faster EVMs is reshaping the landscape, presenting fresh opportunities and challenges for on-chain CLOB implementations. This article introduces an optimised on-chain CLOB tackling all these challenges.

## Algorithm
### Overview
Orders are stored in a hash map and price ordering is not done on-chain. Sorted list price points/order IDs are sent as calldata while placing market orders which removes the scope for MEVs by front-running transactions. We rely on the fact that market orders want the best price and hence will send the sorted list of price points/order IDs. Only time priority is verified by the smart contract on-chain as there is no incentive for market orders to sort order IDs in this order. We use a sliding window mechanism to enforce time priority.

Before we dive into the algorithm, let us understand some basic structures used for storing limit orders.
1. Buy and sell limit orders are stored in separate hashmaps on-chain. The order is referenced by an `orderId` and stores the following data:
i. `ownerAddress`: Address of the maker
ii. `price`: Price point to place the limit order
iii. `size`: Size of the order
iv. `acceptableRange` (this is used for Time priority validation, more about it later)
2. Buy and sell price points at which orders are placed are also stored in separate hashmaps on-chain. A price point is first created when the first order is placed at this price. Price points are referenced by the `price` and have the following data:
i. `totalCompletedOrCanceledOrders`: Sum of all the order sizes claimed or cancelled orders at this price point.
ii. `totalOrdersAtPrice`: Sum of all the order sizes placed at this price point.
iii. `executableSize`: Total volume of market orders that that have been placed but not claimed by the maker order.

### Cranked Orderbook
In the cranked order book, matching and settlement are two different steps. That is, when a market order is placed, the volume filled by this market order is marked as claimable on-chain and maker orders have to be claimed separately either individually or in a batched transaction.

The cranked orderbook maintains Price Time Priority.
#### Placing a Limit order
1. A price point is created if it does not already exist.
2. An incremental counter which is a uint256 is used to store `orderIds`.
3. A limit order is stored against the `orderId`, the `acceptableRange` for this order is equal to the `totalOrdersAtPrice` for the given price point.
4. The `totalOrdersAtPrice` of the price point of the order is incremented with the order size.
5. As this does not involve any sort of iteration, a limit order can be placed in constant time(constant gas).

#### Cancelling a Limit order
1. The order is fetched by the `orderId`.
2. The size of the order is updated to zero.
3. The `totalCompletedOrCanceledOrders` for the price point corresponding to this order is increased by the `orderSize`.
4. As this does not involve any sort of iteration, a limit order can be cancelled in constant time(constant gas).

#### Placing Market order
1. A market order call requires two arguments
i. `pricePoints`: a sorted list of price points you want to execute against.
ii. `size`: order size
2. It iterates over the list of price points as long as the volume available at that price point can only partially fill the market order given by the user and updates the `executableSize` of the price point such that it stops iterating when either the size requirement is met at that price point, there are no more price points in the call data.
3. We chose to use calldata instead of having a sorted list of price points on-chain for the following reasons:
i. Placing limit orders will become more expensive (O(log(n))).
ii. Validators can front-run by adding a better price point than that existing on-chain when a suitable market order pair is received. As market orders already have a list of price points, frontrunning by adding a better price can’t be achieved.

#### Claiming Limit Order
1. The order is fetched by the `orderId`.
2. The `claimedSize` of the order is defined as:
i. 0 if `acceptableRange > executableSize + totalCompletedOrCanceledOrders`
ii. `executableSize + totalCompletedOrCanceledOrders - acceptableRange` otherwise
3. The size of the order is updated to `size - claimedSize`.
4. As this does not involve any sort of iteration, a limit order can be claimed in constant time(constant gas).

### Crankless Orderbook
In the crankless order book, market orders directly fill limit orders. The crankless orderbook maintains Price Time Priority.

Placing and cancelling limit orders are the same as cranked order book. The crankless order book does not involve claiming limit orders. For market orders, the crankless order book utilises `orderIds` instead of price points. Validation remains the same as claiming.

## Design Choices
### Limit Orders
Efficiently placing and cancelling limit orders has been given the highest priority as deep order books with large liquidity are extremely important for price discovery. If it is expensive to place/cancel limit orders market makers will be disincentivised to provide liquidity. High gas fees on limit orders make it almost impossible for HFT firms to take part in providing liquidity as they can’t make profits on the spread.
Keeping this in mind, our architecture allows the placing and cancelling of limit orders in O(1) at any price point on the order book.

### Market Orders
Market orders need to be matched on-chain with the limit orders with price-time priority. While deciding on how market orders should be matched, we explored two options, that is, a cranked order book where market orders fill price points and limit orders can be settled at a later time and a crankless order book where market orders execute limit orders and are settled in a single transaction.

## Benchmarks
We benchmarked both the order books with a spot market. The gas utilisation data includes gas utilised for transferring an ERC20 token.

### Cranked Order Book
In the cranked order book, market orders fill price points and limit orders can be settled at a later point. The smart contract enforces that the orders are settled with price-time priority.

We implemented this and benchmarked the gas utilisation over a hardhat fork and found the following results.


The above graphs show the gas utilisation for different types of transactions:
1. **Placing Limit orders: 134,904 gas**
Excluding the first limit order, all further limit orders utilise a constant gas, irrespective of the depth of the order book or the price point at which the order is being placed.
2. **Placing Limit orders at existing price points: 137,704 gas**
When a limit order is placed at an existing price point, it utilises a slightly higher amount of gas. This can be attributed to the update of one extra uin256 storage variable.
3. **Cancelling Limit orders: 79,483 gas**
Cancelling limit orders utilises a constant amount of gas.
4. **Claiming Limit orders: 77,611 gas**
Claiming limit orders utilises a constant amount of gas. This step can be abstracted away by executor bots by taking an upfront execution fee from the market makers.
5. **Placing Market Orders**
Market orders iterate over consecutive price points and fill limit orders. The cranked order book does not settle every limit order, but the liquidity providers are expected to claim the limit order at a later point.
It utilises **29,146 gas** for every extra price point iterated. This can be seen in the second graph.

### Crankless Order Book
In the crankless order book, market orders directly fill limit orders. The smart contract enforces that the orders are settled with price-time priority.

We implemented this and benchmarked the gas utilisation over a hardhat fork and found the following results.


Placing limit orders at new price points and existing price points and cancelling limit orders behave exactly the same way as in a cranked order book.

1. **Placing Market Orders**
Market orders iterate over consecutive orders settling every order.
It utilises **17,074 gas** for every extra order ID filled. This can be seen in the second graph.
When a market order has to iterate over price points as well, it utilises an additional **17,074 gas**.

## Cranked vs Crankless
Using a cranked order book instead of a crankless one increases the gas utilisation of limit orders by almost 60% which is a big jump disincentivizing market makers and HFTs.
The additional gas paid by takers for settling every limit order is 17,074 in stark contrast to 77,611 for claiming a maker order. However, batching claim transactions will result in significant gas optimisations for claiming limit orders.

## Existing solutions on EVM
1. **CLOBER**: Uses segmented trees at every price point. Insertion takes log(n) which is expensive. We replace the segmented tree with a single uint256 variable and use a sliding window.
2. **Gridex**: Gridex allows users to provide liquidity in grids, time priority is not maintained in every grid.