​
Matching Engine

The matching engine is the core of the OrderBook contract, responsible for organizing orders by price and executing trades when compatible orders meet.

​
Price Tree Structure

Orders are organized using Red-Black Trees for efficient price-level management:

​
Why Red-Black Trees?

OperationComplexityBenefit
Insert price levelO(log n)Fast order placement
Remove price levelO(log n)Efficient level removal
Find best priceO(1)*Instant best bid/ask lookup
Find next priceO(log n)Quick iteration through prices
*With cached pointers to best prices

​
Order Queues

At each price level, orders are stored in a FIFO queue:

​
Queue Structure

struct OrderQueue {
    uint256 head;      // First order ID
    uint256 tail;      // Last order ID
    uint256 count;     // Number of orders
    uint256 volume;    // Total volume at this price
}

​
Queue Operations

OperationDescription
EnqueueAdd new order at tail
DequeueRemove filled order from head
PeekView head order without removal

​
Matching Algorithm

​
Price-Time Priority

The matching engine follows strict price-time priority:
  1. Price Priority: Best prices match first
    • Buy orders: Highest bid first
    • Sell orders: Lowest ask first
  2. Time Priority: At same price, FIFO order

​
Matching Process

​
Match Execution

For each potential match: 
// Determine fill quantity
uint256 fillQty = min(takerRemaining, makerRemaining);

// Calculate quote amount
uint256 quoteAmount = (fillQty * price) / PRICE_SCALE;

// Execute settlement
balanceManager.transferLockedFrom(maker, taker, baseCurrency, fillQty);
balanceManager.transferLockedFrom(taker, maker, quoteCurrency, quoteAmount);

// Update order states
makerOrder.filled += fillQty;
takerOrder.filled += fillQty;

​
Iteration Limits

To prevent gas exhaustion, matching has configurable limits:
LimitPurpose
maxIterationsMaximum price levels to traverse
maxOrdersPerLevelMaximum orders to match at single price

​
Gas-Bounded Matching

If limits are reached:
  • IOC/FOK: Cancel remaining
  • GTC: Remaining quantity rests in book

​
Price Level Management

​
Adding a Price Level

When the first order arrives at a new price:

​
Removing a Price Level

When the last order at a price is filled/cancelled:

​
Spread and Best Prices

​
Spread Definition

Spread = Best Ask - Best Bid

​
Best Price Tracking

The engine maintains pointers to best prices for O(1) access: 
struct OrderBookState {
    uint256 bestBid;     // Highest buy price
    uint256 bestAsk;     // Lowest sell price
    // ... other state
}
Updated after each:
  • Order placement (if improves best)
  • Order cancellation (if was best)
  • Order fill (if empties best level)

​
Cross-Spread Execution

When a new order’s price crosses the spread:

​
Buy Order Crossing Ask

​
Execution Price

Trades execute at the maker’s price (resting order):
  • Buy crossing ask: Executes at ask price
  • Sell crossing bid: Executes at bid price
This ensures price improvement for aggressive orders.

​
Performance Characteristics

​
Time Complexity

OperationAverageWorst
Place order (no match)O(log n)O(log n)
Place order (with match)O(log n + m)O(n)
Cancel orderO(log n)O(log n)
Get best priceO(1)O(1)
Where:
  • n = number of price levels
  • m = number of orders matched

​
Space Complexity

StructureSize
Price treeO(n) price levels
Order queuesO(m) total orders
Order storageO(m) orders

​
Hooks Integration

The matching engine can trigger hooks at key points: Hooks can:
  • Validate orders against custom rules
  • Log trading activity
  • Trigger external integrations
  • Implement trading restrictions