Matching Engine

The CVEX Protocol's Matching Engine is designed to overcome challenges inherent in implementing a traditional order book within a smart contract environment. A key issue arises when a taker order matches with a significantly large number of maker orders, disproportionately increasing execution costs for the taker. To address this, CVEX divides the order matching process into two distinct phases:

1. Order Sampling: In this phase, matched limit orders are efficiently sampled from the order book and transferred into a clearance queue as a collective group. This process is managed by the entity initiating the taker order.

2. Order Clearance: This phase involves the execution of queued orders and is carried out by Clearance Bots.

For efficient order sampling, the CVEX Protocol utilises a specialised data structure similar to an Order Statistic Tree. This binary tree, which separates buy and sell orders for each contract, exhibits the following characteristics:

• Each node in the tree represents a limit order, without intermediate nodes.

• Orders are organised based on traditional order book rules, sorted by price and then by time of placement.

• The AVL algorithm, tailored for smart contract environments to minimise read operations during rebalancing, ensures effective depth maintenance.

• Every node cumulatively tracks the sum of quote amounts (in contract value) and net amounts (in USDC) for all encompassed orders within their respective subtrees.

Representation of an order book on CVEX. The number in each node represents the cumulative sum of the quote amount in their subtrees. For illustration, we assume that all orders are of size 1.

This order organisation enables efficient aggregated requests, such as grouping orders by price intervals or their cumulative amounts. In the matching process, the protocol first locates a path from the root to the final order matched a taker order. This is achieved by navigating from the root, ensuring the cumulative quote amount on the left side of the path equals the taker order's size.

Bold nodes represent matched orders. The arrows indicate the path from the root to the last matched order.

Upon identifying the last order, the tree is divided along this path into two distinct sections: a forest of subtrees containing matched orders and an unbalanced tree with the remaining orders. The forest comprises a number of subtrees, capped by the original tree's height $O(\log n)$, where $n$ is the total number of orders. If the last order is partially matched, the protocol duplicates its node, including it in both the forest and the remaining tree.

The path divides the tree into a forest with two subtrees (comprising 4 and 2 nodes), and the remaining unbalanced tree.

After the tree cut, the remaining tree is rebalanced with at most $O(\log n)$ rotations. The root nodes of the matched subtrees are then moved to the clearance queue, also with $O(\log n)$ complexity.

This distinctive process separates the execution of taker orders from matched maker orders. Instead of immediate execution, matched maker orders are queued for clearance, processed with $O(n)$ complexity by Clearance Bots. The gas for this clearance is pre-funded by the Operational Fees paid by limit order owners, stored in the Operational Fund until order fulfilment. Clearance Bots receive reimbursement for the gas burned for order clearance from the Operational Fund, with an added premium.

CVEX's matching engine thereby ensures $O(\log n)$ complexity for executing orders, regardless of the number of matched orders. This approach enables the traditional order book model to operate on-chain, ensuring both fair cost distribution and efficient order processing.