OrderBook Contract

The OrderBook.sol contract is the core trading engine of Worldbook. It implements a sophisticated order matching system with gas-optimized skip lists and comprehensive order lifecycle management.

Contract Overview

  • File: OrderBook.sol

  • Size: ~2,600 lines of code

  • Gas Optimized: Uses skip lists for O(log n) performance

  • Security: Includes reentrancy guards, pause functionality, and comprehensive validation

Key Features

Advanced Data Structures

  • Skip Lists: Probabilistic data structures for efficient price level traversal

  • Doubly-Linked Lists: FIFO order queues within each price level

  • Gas Threshold Controls: Prevents out-of-gas scenarios during matching

Order Types Support

  • Limit Orders: Standard price-controlled orders

  • Market Orders: Immediate execution at best available price

  • Post-Only Orders: Liquidity-adding orders only

  • IOC Orders: Immediate-or-Cancel execution

  • FOK Orders: Fill-or-Kill execution

Execution Features

  • Self-Trade Prevention: Configurable STP modes per user

  • Match Limit Controls: Prevents out-of-gas during matching

  • Best Price Caching: O(1) access to best bid/ask prices

  • Maker Rebates: Support for negative maker fees

Core Components

1. Skip List Implementation

The OrderBook uses skip lists for efficient price level management:

// Skip List Constants
uint8 internal constant SKIPLIST_MAX_LEVEL = 9;
uint256 internal constant SKIPLIST_P_DENOMINATOR = 4;
uint256 internal constant BUY_SENTINEL_PRICE = type(uint256).max;
uint256 internal constant SELL_SENTINEL_PRICE = 0;

// Skip List Data Structures
mapping(uint256 => uint256[SKIPLIST_MAX_LEVEL]) internal nextBuyPriceNode;
mapping(uint256 => uint256[SKIPLIST_MAX_LEVEL]) internal nextSellPriceNode;
mapping(uint256 => uint8) public buyPriceNodeHeight;
mapping(uint256 => uint8) public sellPriceNodeHeight;

Skip List Benefits:

  • O(log n) search, insert, and delete operations

  • Efficient price level traversal

  • Reduced gas costs compared to other implementations

2. Order Storage

Each order is stored with comprehensive metadata:

struct Order {
    uint64 id;                    // Unique order identifier
    address trader;               // Order owner
    uint256 price;               // Order price
    uint256 amount;              // Base token amount
    uint256 filled;              // Amount already filled
    uint256 quoteAmount;         // Quote token amount locked
    uint256 quoteAmountFilled;   // Quote amount filled
    uint64 timestamp;            // Order creation timestamp
    bool isBuyOrder;             // Buy (true) or sell (false)
    bool isActive;               // Order active status
    bool postOnly;               // Post-only restriction
    MatchLimitBehavior matchLimitBehavior; // Match limit handling
    uint64 nextOrderId;          // Next order in price level
    uint64 prevOrderId;          // Previous order in price level
}

3. Price Level Management

Each price level maintains order queues:

// Price level heads and tails for FIFO ordering
mapping(uint256 => uint64) public priceLevelHeadBuy;
mapping(uint256 => uint64) public priceLevelTailBuy;
mapping(uint256 => uint64) public priceLevelHeadSell;
mapping(uint256 => uint64) public priceLevelTailSell;

// Volume tracking for each price level
mapping(uint256 => uint256) public buyVolumeAtPrice;
mapping(uint256 => uint256) public sellVolumeAtPrice;

// Best price caching for O(1) access
uint256 public bestBidPrice;  // Highest buy price with volume
uint256 public bestAskPrice;  // Lowest sell price with volume

4. User Balance Management

The contract tracks withdrawable balances:

// User withdrawable balances
mapping(address => uint256) public withdrawableBase;
mapping(address => uint256) public withdrawableQuote;

// User active orders tracking
mapping(address => uint64[]) public userActiveOrders;
mapping(uint64 => uint256) private orderIdToActiveOrderIndex;

Core Functions

Order Creation

The OrderBook uses separate public entry points for buy and sell orders, but internally they both use a unified _createOrder function for the core logic.

Primary Order Creation Functions

function createBuyOrder(
    uint256 baseAmount,
    uint256 price,
    bool postOnly,
    ExecutionType executionType,
    MatchLimitBehavior behavior,
    uint256 maxMatches,
    bool _claimTokensAfter
) external override nonReentrant whenNotPaused returns (
    uint64 orderId,
    uint256 baseFilled,
    uint256 quoteFilled,
    uint256 baseFee
)

function createSellOrder(
    uint256 baseAmount,
    uint256 price,
    bool postOnly,
    ExecutionType executionType,
    MatchLimitBehavior behavior,
    uint256 maxMatches,
    bool _claimTokensAfter
) external override nonReentrant whenNotPaused returns (
    uint64 orderId,
    uint256 baseFilled,
    uint256 quoteFilled,
    uint256 quoteFee
)

Batch Order Creation

function createOrders(
    OrderParams[] calldata params,
    uint256 maxMatches
) external override nonReentrant whenNotPaused returns (uint64[] memory orderIds)

Creates multiple orders in a single transaction for gas efficiency.

Internal Order Creation Process (_createOrder):

  1. Validates order parameters (amount, price, tick size)

  2. Checks minimum quote value requirements

  3. Locks appropriate collateral (quote for buy, base for sell)

  4. Creates order record with unique ID

  5. Attempts matching (unless post-only)

  6. Handles post-match order placement based on execution type

  7. Calculates and applies taker fees

  8. Emits events and returns execution details

Order Matching Engine

_matchOrder()

The core matching algorithm:

  1. Price Discovery: Uses skip lists to find best opposing orders

  2. FIFO Execution: Processes orders in time priority within price levels

  3. Gas Management: Monitors gas consumption to prevent out-of-gas

  4. Partial Fills: Supports partial order execution

  5. Settlement: Updates balances and removes filled orders

Matching Priority:

  • Price Priority: Better prices get filled first

  • Time Priority: Earlier orders at same price get filled first

  • Pro-Rata: Not used; strict FIFO within price levels

Self-Trade Prevention: When a taker order would match with a maker order from the same trader:

  • EXPIRE_MAKER: Cancels the maker order and continues matching

  • SKIP: Skips the maker order without matching

  • NONE: Allows the self-trade to execute

Order Cancellation

cancelOrders()

function cancelOrders(uint64[] calldata orderIds) external nonReentrant returns (bool[] memory success)

Process:

  1. Batch cancellation of multiple orders

  2. Validates order ownership and status for each

  3. Removes orders from orderbook structures

  4. Refunds locked collateral to user

  5. Updates user's active orders list

  6. Returns success status for each cancellation

cancelAndReplaceOrders()

function cancelAndReplaceOrders(
    uint64[] calldata cancelIds,
    OrderParams[] calldata createParams,
    uint256 maxMatches
) external override nonReentrant whenNotPaused returns (uint64[] memory newOrderIds)

Atomically cancels existing orders and places new ones in a single transaction. This is gas-efficient for order updates and ensures no gap in market exposure.

OrderParams Structure:

struct OrderParams {
    uint256 amount;              // Base token amount
    uint256 price;               // Order price
    bool isBuyOrder;             // True for buy, false for sell
    bool postOnly;               // Post-only flag
    ExecutionType executionType; // Standard, IOC, or FOK
    MatchLimitBehavior matchLimitBehavior; // Cancel or PlaceAtLast
}

Balance Management

claimTokens()

function claimTokens() external nonReentrant

Users can claim their withdrawable token balances accumulated from:

  • Cancelled order refunds

  • Maker fee rebates (when maker fee is negative)

  • Filled order proceeds

  • Self-trade prevention refunds

Gas Optimization Features

1. Skip List Efficiency

  • O(log n) operations instead of O(n) linear searches

  • Reduced gas costs for price level traversal

  • Efficient insertion and deletion

2. Match Limit Controls

// Match limit behavior options
enum MatchLimitBehavior {
    Cancel,        // Cancel order if match limit reached
    PlaceAtLast    // Place remaining as limit order at last checked price
}

// ExecutionType for order behavior
enum ExecutionType {
    Standard,      // Normal limit order
    IOC,          // Immediate-or-Cancel
    FOK           // Fill-or-Kill
}

3. Cached Best Prices

uint256 public bestBidPrice;  // Cached highest buy price
uint256 public bestAskPrice;  // Cached lowest sell price

O(1) access to best prices without skip list traversal.

4. Empty Price Level Cleanup

function cleanupEmptyPriceLevels(uint256 maxCleanups, bool isBuy) 
    external onlyManagerRole(keccak256("ADMIN_ROLE")) 
    returns (uint256 cleanedCount)

Removes zombie price levels from the skip list to maintain efficiency.

Security Features

1. Access Control

modifier onlyManagerRole(bytes32 role) {
    if (!manager.hasOrderBookRole(role, msg.sender)) 
        revert OrderBook__InsufficientRole();
    _;
}

2. Reentrancy Protection

contract OrderBook is ReentrancyGuard {
    // All external functions use nonReentrant modifier
}

3. Pausable Operations

contract OrderBook is Pausable {
    // Trading can be paused in emergencies
}

4. Input Validation

  • Zero amount/price checks

  • Tick size validation

  • Minimum quote amount enforcement

  • Token approval verification

Events

Order Events

event OrderCreated(
    uint64 orderId,
    address trader,
    bool isBuy,
    uint256 price,
    uint256 baseAmount,
    uint64 timestamp
);

event OrderFilled(
    uint64 orderId,
    address trader,
    bool isBuyOrder,
    uint256 price,
    uint256 amount
);

event OrderCancelled(
    uint64 orderId,
    address recipient,
    bool isBuyOrder,
    uint256 price,
    uint256 remainingAmount
);

event OrderReduced(
    uint64 orderId,
    address trader,
    bool isBuyOrder,
    uint256 price,
    uint256 amountFilledInStep,
    uint256 remainingAmount
);

Trade Events

event Trade(
    uint64 takerOrderId,
    uint64 makerId,
    address buyer,
    address seller,
    uint256 baseFilledAmount,
    uint256 priceLevel,
    uint256 totalQuoteValue,
    uint256 baseFeePaid,
    uint256 quoteFeePaid,
    bool isTakerBuy
);

Error Handling

Common Errors

error OrderBook__BaseAmountZero();
error OrderBook__PriceZero();
error OrderBook__InvalidPriceTick();
error OrderBook__PostOnlyOrderWouldMatch();
error OrderBook__OrderNotFound();
error OrderBook__NotOrderOwner();
error OrderBook__InsufficientBalance();
error OrderBook__IncomingFOTNotAllowed();

Integration Points

Manager Contract Integration

  • Role-based access control

  • Fee calculation delegation

  • Registration and configuration

Token Contract Integration

  • ERC20 token transfers

  • Balance tracking

  • Approval management

Frontend Integration

  • Event-based order updates

  • Real-time orderbook data

  • Transaction status monitoring

Performance Characteristics

Time Complexity

  • Order Creation: O(log n) for skip list operations

  • Order Matching: O(log n) for price discovery, O(1) for FIFO

  • Order Cancellation: O(log n) for skip list updates

  • Balance Queries: O(1) for cached values

Space Complexity

  • Skip Lists: O(n log n) for price level indexing

  • Order Storage: O(n) for order records

  • Price Levels: O(m) where m is number of active price levels

Gas Consumption

Based on comprehensive gas analysis testing:

Place Order Operations

  • Order at new price level: ~400k gas

  • Order at existing price level: ~300k gas

Order Matching (Taker Orders)

  • Base cost: ~500k gas

  • Per additional match: +~50k gas

  • Formula: 500k + (50k × (matches-1))

Cancel Order Operations

  • Single cancellation: ~100k gas

  • Batch cancellations (more efficient):

    • Base: ~100k gas

    • Per additional cancel: +~30k gas

    • Formula: 100k + (30k × (cancels-1))

Note: Actual gas usage may vary

Configuration Parameters

System Constants

uint256 public constant PRICE_PRECISION = 1e18;
uint256 public constant FEE_DENOM = 1_000_000;
uint8 internal constant SKIPLIST_MAX_LEVEL = 9;

Admin-Configurable Parameters

uint256 public minQuoteAmount;          // Minimum order size in quote token
uint256 public tickSize;                // Price increment size (0 = no restriction)

Contract Registration

registerOrderBook()

function registerOrderBook() public override

Registers the OrderBook with the Manager contract after deployment. This function:

  1. Calls the Manager's registerOrderBook function

  2. Passes the base token, quote token, and OrderBook address

  3. Enables the OrderBook to be discovered and used by traders

Registration Process:

  • Deploy OrderBook contract with proper parameters

  • Call registerOrderBook() to register with Manager

  • Manager validates bytecode hash and parameters

  • OrderBook becomes available for trading

Best Practices

For Traders

  1. Set Appropriate Gas Limits: Ensure sufficient gas for order execution

  2. Monitor Order Status: Track order fills and cancellations

  3. Use Post-Only for Market Making: Avoid taker fees when providing liquidity

  4. Consider Gas Threshold Behavior: Choose appropriate handling for large orders

For Developers

  1. Event Monitoring: Subscribe to relevant events for real-time updates

  2. Error Handling: Implement comprehensive error handling for all scenarios

  3. Gas Estimation: Provide accurate gas estimates for different order types

  4. State Management: Maintain local state synchronized with contract events

Gas Optimization Tips

  1. Use Batch Operations: Cancel multiple orders in one transaction to save ~60% gas

  2. Place Orders at Existing Price Levels: Saves ~40% gas compared to creating new levels

  3. Set Appropriate Match Limits: Control maximum gas usage for large orders

  4. Consider Order Size: Larger orders matching multiple counterparties are more gas-efficient per unit traded

  5. Use cancelAndReplaceOrders: More efficient than separate cancel and create transactions

Fee System with Maker Rebates

Fee Calculation

The OrderBook supports both positive fees and negative fees (rebates):

// Fee calculation with rebate support
function _calculateMatchFeesAndNets(
    uint256 amountToFill,
    uint256 priceLevel,
    uint256 takerFeeRate,
    int256 makerFeeRate,    // Can be negative for rebates
    bool isTakerBuy
) internal view returns (...)

Rebate Rules:

  • Maker fees can be negative to incentivize liquidity

  • Rebates are paid in the same token type as taker fees

  • Rebates cannot exceed the taker fee amount

  • Net protocol fees = taker fees + maker fees - rebates

Fee Distribution:

  • Buy takers pay base token fees

  • Sell takers pay quote token fees

  • Maker rebates match the taker's fee token type

The OrderBook contract represents a sophisticated implementation of decentralized trading infrastructure, balancing performance, security, and usability for professional-grade DeFi applications.

Previous4-Tier Fee SystemNextSkip List Implementation

Last updated