Are you an LLM? Read llms.txt for a summary of the docs, or llms-full.txt for the full context.
Skip to content

Tick Tree Structure

The tick tree is the core data structure that enables efficient price discovery in Vif. It's a 3-level bitmap tree where each level uses 256-bit integers as bitmaps.

Tree Architecture

Root Layer (256 bits)
    ↓
Level 1 Layer (256 × 256 bits)
    ↓
Level 2 Layer (256 × 256 × 256 bits)

Each set bit in a bitmap indicates that price level is active (has offers).

Finding the Best Price

To find the best price (lowest tick for asks, highest tick for bids):

1. Find least significant set bit in root bitmap
   → gives rootIndex (0-255)
 
2. Go to level1[rootIndex], find LSB
   → gives level1Index (0-255)
 
3. Go to level2[rootIndex][level1Index], find LSB
   → gives level2Index (0-255)
 
4. Calculate final tick index:
   index = (rootIndex << 16) | (level1Index << 8) | level2Index
   or equivalently:
   index = rootIndex * 65536 + level1Index * 256 + level2Index

Finding the Next Price

After consuming all offers at the current price, we need to find the next best price:

1. Unset the current bit in level2 bitmap
2. Find next LSB in level2
   - If found: done
   - If not found: move to step 3
 
3. Unset the current bit in level1 bitmap
4. Find next LSB in level1
   - If found: go down to corresponding level2, find its LSB
   - If not found: move to step 5
 
5. Unset the current bit in root bitmap
6. Find next LSB in root
   - If found: go down through level1 and level2
   - If not found: no more prices available

This traversal algorithm ensures O(1) complexity for moving to the next price point.

Storage Layout

The entire tree is stored as a fixed-size array:

// Total elements: 1 + 256 + 256*256 = 65,793 uint256 slots
tree[0]              // Root bitmap (1 slot)
tree[1..256]         // Level 1 bitmaps (256 slots)
tree[257..65792]     // Level 2 bitmaps (65,536 slots)

This fixed allocation means:

  • Predictable gas costs for tree operations
  • No dynamic allocation overhead
  • Maximum of 16,777,216 possible price points (256³)

Index ↔ Tick ↔ Price Conversion

Index to Tick

Ticks are signed 24-bit integers, while indices are unsigned:

const MAX_TICK = 8_388_607; // type(int24).max
 
tick = index - MAX_TICK;
index = tick + MAX_TICK;

Tick to Price

The price is calculated as:

price=1.00001tickprice = 1.00001^{tick}

Where price represents the ratio inboundAmount / outboundAmount.

Key properties:
  • Higher tick = higher price = worse for taker
  • Lower tick = lower price = better for taker
  • 1 tick = 0.1 basis point (0.001%) price movement

In-Contract Calculation

Prices are represented as Q128.128 fixed-point numbers using binary exponentiation:

// For negative ticks:
price = binaryExp(-|tick|)
 
// For positive ticks:
price = 1 / binaryExp(|tick|)

See Binary Exponentiation for implementation details.

Tick Spacing

Markets can specify a tick spacing to:

  • Reduce gas costs on volatile pairs
  • Prevent penny-jumping (makers placing orders 1 tick better)
  • Align with traditional market tick sizes
// Example: tickSpacing = 10
// Only ticks ..., -20, -10, 0, 10, 20, ... are valid
 
actualTick = round(requestedTick / tickSpacing) * tickSpacing

When placing an order:

  • Your requested tick is rounded towards zero to the nearest valid tick
  • The tree only activates indices corresponding to valid ticks

Example: WETH/USDC Market

Let's trace finding the best ask price in a WETH/USDC market:

// Setup
outboundToken = WETH
inboundToken = USDC
tickSpacing = 1
 
// Current state: offers at ticks -2,072,336 and -2,000,000
// These correspond to prices ~1000 USDC and ~1200 USDC per WETH
 
// Finding best price (lowest tick):
tick₁ = -2,072,336
index₁ = -2,072,336 + 8,388,607 = 6,316,271
 
// Convert to tree coordinates:
rootIndex = 6,316,271 >> 16 = 96
level1Index = (6,316,271 >> 8) & 0xFF = 101
level2Index = 6,316,271 & 0xFF = 143
 
// Tree lookup:
root[96] has bit set → check level1[96][101]
level1[96][101] has bit set → check level2[96][101][143]
level2[96][101][143] has bit set at position 143
 
// Result: Best offer is at tick -2,072,336
price = 1.00001^(-2,072,336) ≈ 0.8187 WETH/USDC
or equivalently: ~1221.7 USDC/WETH

Gas Optimization

The bitmap structure provides exceptional gas efficiency:

OperationGas CostNotes
Find best price~3 SLOADOne per level
Move to next price~3-9 SLOADDepends on tree descent
Activate price~3 SSTORESet bits in each level
Deactivate price~3 SSTOREUnset bits in each level

Compare this to:

  • Linked list: O(n) traversal, unpredictable gas
  • Heap: O(log n) operations, expensive updates
  • Sorted array: O(n) insertion, O(1) lookup

The bitmap tree achieves near-constant time operations regardless of the number of active price points.

Related Concepts