MAOB Architecture

Overview

The Midpoint Anchored Order Book (MAOB) is a discrete-rung order book anchored to an oracle midpoint. It is engineered to make on-chain order books practical: bounded loops, deterministic rounding, and O(log n) claim accounting without per-order fill updates on every trade, allowing for O(1) matching within rungs.

Core responsibilities

MAOB implements the core on-chain trading engine:

• Order management: create, store, and manage maker orders through placement, fills, claims, and cancellations.
• Order matching: price-time priority across rungs, FIFO ordering within each rung.
• Token custody: custody base tokens and quote tokens for makers, and settle to withdrawable balances.

Engineering Highlights

The contract combines several techniques that make a fully on-chain order book feasible:

• Bounded execution: a 64-rung design plus bitmask traversal yields predictable, bounded loops for takers.
• Fixed rung lattice: replaces skip list traversal with a compact rung grid and active*Rungs bitmasks.
• Generation-based queues: when a rung empties, a new generation resets queue state without costly cleanup.
• Fenwick tree accounting: queue end and cancellation trees provide O(log n) prefix sums, enabling scalable FIFO claims.
• Segmented settlement: cumulative fill segments allow computing any order's output by range without updating every order on every fill.
• O(1) per-rung matching: each rung match updates aggregated totals and emits a single fill event without iterating maker orders.

These choices let MAOB deliver deterministic pricing, fair FIFO ordering, and scalable claims while keeping gas usage predictable.

Architecture at a glance

• Oracle anchor: IOracleAdapter.getPrice(address orderBook) provides a midpoint price with precision and staleness checks.
• Fixed rung lattice: bpsRungs defines up to MAX_RUNGS = 64 discrete price offsets in 0.1 bps units.
• Side-specific liquidity pools: askRungs (base tokens) and bidRungs (quote tokens) track rung totals.
• Active rung bitmasks: activeAskRungs and activeBidRungs enable fast rung traversal.
• FIFO queue accounting: per-rung QueuePosition, per-rung gen (generation), and claim ranges.
• Fenwick trees: fwEnd and fwCancel track queue sizes and cancellations for O(log n) claims.
• Fill segments: per-rung+side+generation FillSegment[] stores cumulative input/output and rounding remainder.
• Withdrawable ledger: withdrawableBase and withdrawableQuote collect claimed output before withdrawal.

Order lifecycle

Maker placement

Makers add liquidity using:

• addLiquidityAsk(rung, baseAmount)
• addLiquidityBid(rung, quoteAmount)
• addLiquidityBatch(liquidityOrders)

Key mechanics:

• Oracle safety: _getMidPrice() enforces non-zero price/precision and staleness bounds.
• Min quote token checks: minQuoteMaker ensures orders meet minimum value thresholds.
• Single transfer per side in batch: base tokens and quote tokens are transferred once per batch.
• Queue positioning: _createOrder assigns claimRangeStart/claimRangeEnd using a frontier computed from cumulative fills and cancellations for FIFO fairness.
• Rung activation: activeAskRungs/activeBidRungs are toggled as rungs become non-empty.

Taker execution

Taker flows include:

• buyBaseExactOut / buyBaseTargetIn
• sellBaseTargetIn / sellBaseExactOut

Key mechanics:

• Bounded traversal: _activeMask(maxRung, active*Rungs) plus _lsbIndex walks only active rungs up to maxRung.
• Deterministic pricing: rung prices are derived from the oracle midpoint with fixed bps offsets and rounding to PRICE_SIGFIGS.
• Segmented fills: _recordFill and _recordFillWithRemainder update cumulative fill segments without touching each maker order.
• O(1) per-rung matching: fills update rung totals, fill segments, and emit a single RungFilled event without iterating makers.
• Guardrails: deadline, min quote token checks, and slippage limits (maxQuoteIn, minBaseOut, minQuoteOut, maxBaseIn).

Claims and cancellations

• Claiming: _claimOrder computes claimable output using per-order claim ranges and fill segments, then credits withdrawable balances.
• Cancelling: _cancelOrderInternal marks remaining input in the cancel Fenwick tree, refunds remaining input to withdrawable balances, and preserves filled amounts for later claims.
• Withdrawals: _withdraw transfers accumulated base tokens and quote tokens to the maker.

Claim range settlement (FIFO)

Every resting order owns a continuous claim range (claimRangeStart, claimRangeEnd) representing its slice of the rung queue. The rung frontier advances as takers fill the rung, with cancellations tracked in the Fenwick trees.

Claimable input is computed from the frontier and the order's range:

filled = min(frontier, claimRangeEnd) - claimRangeStart

This keeps FIFO ordering without iterating other makers and allows claims to remain O(log n) even as the queue grows.

Pricing and rounding

MAOB prices each rung relative to the oracle midpoint:

• Ask price: mid * (RUNG_DENOM + rungBps) / RUNG_DENOM
• Bid price: mid * (RUNG_DENOM - rungBps) / RUNG_DENOM

Key precision mechanics:

• baseScale and quoteScale normalize token decimals.
• _roundPriceQ rounds to PRICE_SIGFIGS significant figures for deterministic pricing.
• _applyRemainder carries remainder across fills so rounding is fair and consistent across partial fills and claims.