Matching Engine

Implementing the matching engine on-chain is challenging, as most matching engines used in traditional finance utilize algorithms with linear complexity. On-chain, all transactions are subject to gas limits per block and per transaction. To tackle this problem, we adapted a matching algorithm with logarithmic complexity for on-chain use. This approach was inspired by a talk by J. Poon and C. Jeffrey at Warp.

Basic Matching Algorithm Idea:

Order Storage: Orders are stored in radix trees (separate trees for bids and asks), with a combination of price and order number serving as a key. Each node contains Sum Qty and Sum Value, which are the sum of the number of tokens and the number of coins of its child nodes, respectively.

By construction, the length of the key is 64 bits, so the maximum height of the tree is 64, meaning that any order can be executed in up to 127 steps. Logarithmic complexity essentially allows us to have finite complexity for a reasonable range of price and order values. We allow 6-digit price precision, meaning a tick size of less than 0.001%. More on that in the section "Prices and Precision."

Order Execution: To match bids with an opposing sell market order, we iterate across the rightmost branch of the tree until we find the largest sub-tree that can be fully executed by the sell order.

Then we remove that sub-tree from the bid tree and transfer the Sum Value amount of tokens to the seller. All the limit orders that were removed from the tree are considered executed. As the tree height is proportionate to the logarithm of the number of orders (with a maximum height of 64 in our case), we have demonstrated that order execution indeed has logarithmic complexity.

Further Optimizations to Reduce Median Gas Costs

To reduce the median gas costs of main operations (limit order, market order, change order), we introduce the following optimizations:

1. Rightmost Branch Optimization: In the current order book setting, most orders arrive near the top of the book, making it inefficient to iterate from the root each time. To address this, we adjust the way we store the rightmost branch. Instead of storing the sum of child nodes, we will store only the sum of the leftmost nodes. This allows us to avoid traversing all the way to the root of the tree when changing some node in the rightmost branch.

2. Storage Pre-allocation: Writing to a new storage slot in the EVM is much more expensive than rewriting an existing storage slot. To mitigate this, we will keep a list of previously used storage slots and reallocate them to new orders once the old orders are canceled or executed.