- Introduction
- Understanding Trees and Graphs: The Foundation
- The Evolution from Traditional to Tree-Based DeFi
- Why Trees Matter in DeFi
- Tree Design Patterns in Production DeFi
The trend of using complex data structures in Smart contracts is increasing and fascinating at the same time, that in order to join any DeFi project, one must understand the underlying data structures, Trees, and Graphs and not just arrays and mappings. This document explores the shift from traditional DeFi implementations to Tree and Graph based architectures, highlighting their advantages, design patterns, and real-world applications through detailed case studies of live production protocols.
If your background is not computer science or related, and you are in the blockchain space, you might find it a bit difficult to maintain your position in the industry either as a Builder, Auditor, or a Researcher, as more and more projects are adopting complex data structures in order to improve performance.
I will explore the evolution of DeFi protocols from traditional implementations to Trees and Graphs based architectures, highlighting the advantages and design patterns that have emerged in recent years and simplifying the understanding of these complex structures with code samples, and a coded solidity example.
Before diving into DeFi applications, let's establish a solid understanding of these fundamental data structures. Whether you're a seasoned developer or new to computer science, this section will provide the conceptual foundation needed to understand their revolutionary application in DeFi protocols.
A tree is a hierarchical data structure that organizes data in a parent-child relationship. Think of it like a family tree or an organizational chart - there's a clear hierarchy with one root at the top, and each element (called a "node") can have children below it.
- Root: The topmost node (like a CEO in a company)
- Parent/Child: Each node can have children, and each child has exactly one parent
- Leaf: Nodes with no children (like employees with no direct reports)
- Depth: How many levels deep the tree goes
- Path: The route from one node to another
Root (CEO)
/ \
Manager A Manager B
/ \ |
John Sarah Alice
- Binary Trees: Each node has at most 2 children (Manager A has John and Sarah)
- Segment Trees: Specialized for range queries and updates
- Merkle Trees: Used for cryptographic proofs (not covered in this doc)
A graph is a more flexible structure consisting of vertices (nodes) connected by edges (connections). Unlike trees, graphs can have cycles and multiple paths between nodes. Think of it like a city road network - intersections (vertices) are connected by roads (edges), and you might reach the same destination through different route combinations.
- Vertices (Nodes): The entities in the graph (intersections, tokens, pools)
- Edges: The connections between vertices (roads, swap pairs)
- Directed vs Undirected: Whether connections have direction (one-way vs two-way)
- Cycles: Circular paths (A connects to B, B to C, C back to A)
- Connected Components: Groups of vertices that can reach each other
Paris ---- Amsterdam ---- Madrid
| | |
| | |
London ---- Berlin --------/
In this graph, you can travel from Paris to Madrid via multiple paths: Paris→Amsterdam→Madrid (direct, 2 hops), Paris→London→Berlin→Madrid (longer, 3 hops), or Paris→Amsterdam→Berlin→Madrid (alternative, 3 hops).
| Aspect | Trees | Graphs |
|---|---|---|
| Structure | Hierarchical, no cycles | Flexible, can have cycles |
| Use Case | Range queries, hierarchical data | Network relationships, pathfinding |
| DeFi Application | Price ranges, liquidity tiers | Token swap routing, pool connections |
| Complexity | Simpler to traverse | A bit more complex |
In early DeFi (2020-2022), most protocols used simple data structures:
// Traditional approach - simple but inefficient
mapping(address => uint256) balances; // O(1) lookup, but no relationships
uint256[] prices; // O(n) for range operations
mapping(uint256 => uint256) liquidityByTick; // O(n) for multi-tick updatesProblems with traditional approaches:
- Linear complexity: Updating multiple related items requires individual operations
- No relationships: Can't efficiently model connections between tokens/pools
- Gas inefficiency: Each operation costs gas, multiple operations cost multiple gas
- Limited queries: Hard to ask "what's the total liquidity in this price range?"
// Tree approach - efficient range updates
function updateLiquidityRange(uint256 start, uint256 end, uint256 amount) {
// O(log n) instead of O(n) - exponentially better!
tree.updateRange(start, end, amount);
}// Graph approach - model complex token relationships
function findBestSwapPath(address tokenA, address tokenB) returns (address[] path) {
// Can find optimal multi-hop routes through connected pools
return graph.shortestPath(tokenA, tokenB);
}- Linear Array Storage: Most early AMMs used simple array-based liquidity tracking
- Hash Map Lookups: Price discovery through basic mapping structures
- Sequential Processing: Order matching and liquidity provision in linear time
- Gas Inefficiency: O(n) operations for price updates and range queries
- Hierarchical Data Organization: Multi-level tree structures for efficient range queries
- Logarithmic Complexity: O(log n) operations for most critical functions
- Spatial Indexing: Tree-based tick and price range management
- Optimized Gas Usage: Batch operations and efficient traversal algorithms
Modern concentrated liquidity protocols need to:
- Efficiently find active liquidity at specific price points
- Update multiple price ranges simultaneously
- Handle range overlaps and merging
Traditional Approach:
// O(n) complexity for range updates
mapping(uint256 => uint256) liquidityByTick;
function updateLiquidity(uint256[] memory ticks, uint256[] memory amounts) {
for (uint i = 0; i < ticks.length; i++) {
liquidityByTick[ticks[i]] += amounts[i];
}
}Tree-Based Approach:
// O(log n) complexity using tree structure
function updateLiquidityRange(uint256 lowerTick, uint256 upperTick, uint256 amount) {
tree.updateRange(lowerTick, upperTick, amount);
}As I journeyed though various DeFi protocols during development, audits and research, I discovered several innovative tree and graph based design patterns that have been successfully implemented in production environments. Here are some notable examples:
The Burve protocol written as a Diamond pattern implements a graph-based liquidity pool system. When you think of Graph, you think of nodes (Vertices) connected (Edges) and finding the shortest path between them, which is a key aspect in terms of developing Graph Algorithms in solidity, especially when it comes to optimizing gas costs and ensuring efficient data retrieval. Unlike trees, graph is not hierarchical but a collection of nodes and edges, so a vertice can connect to multiple edges and form complex relationships.
- Vertices represent tokens/assets (You can call it nodes- (tokens, vaults, reserves))
- Closures represent groups of tokens (vertices) that can be swapped with each other (subgraphs). Think of it like a subgraph within the larger graph structure, where all tokens (Vertices) in the closure are interconnected and can be swapped directly with one another.
- Value Tokens represent shares in the overall liquidity system (you can think of it as a representation of the value of the assets in the system)
- Edges are implicitly defined by closures (tokens in the same closure can be swapped). You can think of it as the connections between nodes in a graph.
graph TB
subgraph Closure1 ["📦 Closure 1: ETH-USDC Pool"]
V1[🔵 ETH Vertex]
V2[🔵 USDC Vertex]
V1 -.->|swap| V2
V2 -.->|swap| V1
end
subgraph Closure2 ["📦 Closure 2: USDC-DAI Pool"]
V3[🔵 USDC Vertex]
V4[🔵 DAI Vertex]
V3 -.->|swap| V4
V4 -.->|swap| V3
end
subgraph Closure3 ["📦 Closure 3: ETH-USDC-WBTC Pool"]
V5[🔵 ETH Vertex]
V6[🔵 USDC Vertex]
V7[🔵 WBTC Vertex]
V5 -.->|swap| V6
V5 -.->|swap| V7
V6 -.->|swap| V7
end
%% Bridge connections
V2 -.->|same token| V3
V1 -.->|same token| V5
V2 -.->|same token| V6
%% Node styling with better contrast
classDef ethNode fill:#1f77b4,stroke:#333,stroke-width:2px,color:#fff
classDef usdcNode fill:#2ca02c,stroke:#333,stroke-width:2px,color:#fff
classDef daiNode fill:#ff7f0e,stroke:#333,stroke-width:2px,color:#fff
classDef wbtcNode fill:#d62728,stroke:#333,stroke-width:2px,color:#fff
class V1,V5 ethNode
class V2,V3,V6 usdcNode
class V4 daiNode
class V7 wbtcNode
While this is similar to how you set path in Uniswap, the key difference is that in Burve, you don't have to deploy multiple pools of contracts, tokens are grouped into closures (Nodes), and swaps can only occur directly between tokens within the same closure(Node). If two tokens are not in the same closure (Node), a multi-hop swap through bridge tokens (tokens that exist in multiple closures (Nodes) is required). Unlike when a pool can only have 1 pair of tokens, in Burve, each closure (Node) can contain multiple tokens, allowing for more complex swap paths and better liquidity distribution and you only have to pay fees for the closures you use.
graph LR
subgraph Step1 ["📦 Step 1: User wants ETH → DAI"]
ETH1[🔵 ETH]
DAI1[🔵 DAI]
ETH1 -.->|❌ Not in same closure| DAI1
end
subgraph Step2 ["📦 Step 2: Find path through USDC"]
ETH2[🔵 ETH]
USDC2[🔵 USDC<br/>Bridge Token]
DAI2[🔵 DAI]
ETH2 -.->|✅ Closure 1| USDC2
USDC2 -.->|✅ Closure 2| DAI2
end
subgraph Step3 ["📦 Step 3: Two-hop swap"]
Route[🔵 ETH → USDC → DAI<br/>2 transactions, 2 fees]
end
Step1 --> Step2
Step2 --> Step3
%% Node styling with better contrast matching first diagram
classDef ethNode fill:#1f77b4,stroke:#333,stroke-width:2px,color:#fff
classDef usdcNode fill:#2ca02c,stroke:#333,stroke-width:2px,color:#fff
classDef daiNode fill:#ff7f0e,stroke:#333,stroke-width:2px,color:#fff
classDef routeNode fill:#9467bd,stroke:#333,stroke-width:2px,color:#fff
class ETH1,ETH2 ethNode
class USDC2 usdcNode
class DAI1,DAI2 daiNode
class Route routeNode
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract BurveGraphSimplified {
// Core graph structures
struct Vertex {
uint256 id;
address tokenAddress;
string tokenType; // "token", "vault", "reserve"
uint256 balance;
}
struct Closure {
uint256 id;
string name;
uint256[] vertexIds; // Vertices in this closure
bool active;
}
// Global mappings (like actual Burve)
mapping(uint256 => Vertex) public vertices;
mapping(uint256 => Closure) public closures;
mapping(uint256 => mapping(uint256 => bool)) public vertexInClosure;
uint256 public nextVertexId = 1;
uint256 public nextClosureId = 1;
// Create a new closure (protocol function, not user)
function createClosure(string memory _name) external returns (uint256) {
uint256 closureId = nextClosureId++;
closures[closureId] = Closure(closureId, _name, new uint256[](0), true);
return closureId;
}
// Add vertex to system
function addVertex(address _tokenAddress, string memory _tokenType) external returns (uint256) {
uint256 vertexId = nextVertexId++;
vertices[vertexId] = Vertex(vertexId, _tokenAddress, _tokenType, 0);
return vertexId;
}
// Add vertex to closure (creates implicit edges)
function addVertexToClosure(uint256 _vertexId, uint256 _closureId) external {
require(vertices[_vertexId].id != 0, "Vertex doesn't exist");
require(closures[_closureId].id != 0, "Closure doesn't exist");
closures[_closureId].vertexIds.push(_vertexId);
vertexInClosure[_vertexId][_closureId] = true;
}
// Check if two vertices can swap directly (same closure)
function canSwapDirect(uint256 _fromVertex, uint256 _toVertex) external view returns (bool) {
// Check if both vertices exist in the same closure
for (uint256 i = 1; i < nextClosureId; i++) {
if (vertexInClosure[_fromVertex][i] && vertexInClosure[_toVertex][i]) {
return true;
}
}
return false;
}
// Find swap path (simplified)
function findSwapPath(uint256 _fromVertex, uint256 _toVertex)
external view returns (uint256[] memory path) {
// Simplified: find common closure or bridge vertex
// In real implementation, this would use graph algorithms
}
}This is the basic structure of how the graph is represented in Burve and how swaps are facilitated through closures. The actual implementation would be more complex, especially in terms of pathfinding and optimizing for gas costs, but this gives a foundational understanding of the graph-based approach in the Burve protocol.
The Ammplify protocol implements a binary tree-based liquidity management system built as a Diamond proxy pattern. Unlike traditional AMMs that process liquidity linearly tick-by-tick, Ammplify organizes price ranges into a hierarchical binary tree structure that enables efficient range operations and dramatic gas optimizations.
To give a short illustration of what Binary Tree is: When you think of Binary Tree, you think of a hierarchical structure where each node has at most two children (left and right), unlike graphs where nodes can connect to multiple other nodes. In trees, there's exactly one path between any two nodes, and there's a clear parent-child relationship with a single root at the top. Let me not bore you with Tree explanation. In Ammplify, the binary tree consists of:
- Nodes represent price ranges (ticks) with different granularities - each covering a specific width of price space
- Keys uniquely identify each node using base + width encoding packed into 48-bit values
- Routes define optimal paths through the tree for range operations (like updating liquidity from tick 100 to 200)
- Walkers traverse the tree to update liquidity and balances using the calculated routes
- LCA (Lowest Common Ancestor) optimizes tree traversal by finding the smallest subtree containing the target range
graph TD
subgraph "Ammplify Binary Tree - Price Range [0, 15]"
Root["🌳 Root Node<br/>Range: [0, 15]<br/>Width: 16<br/>Key: (0, 16)"]
L1L["🔵 Left Child<br/>Range: [0, 7]<br/>Width: 8<br/>Key: (0, 8)"]
L1R["🔵 Right Child<br/>Range: [8, 15]<br/>Width: 8<br/>Key: (8, 8)"]
L2LL["🟢 Node<br/>Range: [0, 3]<br/>Width: 4<br/>Key: (0, 4)"]
L2LR["🟢 Node<br/>Range: [4, 7]<br/>Width: 4<br/>Key: (4, 4)"]
L2RL["🟢 Node<br/>Range: [8, 11]<br/>Width: 4<br/>Key: (8, 4)"]
L2RR["🟢 Node<br/>Range: [12, 15]<br/>Width: 4<br/>Key: (12, 4)"]
L3LLL["🟡 Leaf [0,1]<br/>Width: 2<br/>Key: (0, 2)"]
L3LLR["🟡 Leaf [2,3]<br/>Width: 2<br/>Key: (2, 2)"]
L3LRL["🟡 Leaf [4,5]<br/>Width: 2<br/>Key: (4, 2)"]
L3LRR["🟡 Leaf [6,7]<br/>Width: 2<br/>Key: (6, 2)"]
end
Root --> L1L
Root --> L1R
L1L --> L2LL
L1L --> L2LR
L1R --> L2RL
L1R --> L2RR
L2LL --> L3LLL
L2LL --> L3LLR
L2LR --> L3LRL
L2LR --> L3LRR
%% Styling
classDef rootNode fill:#8B4513,stroke:#333,stroke-width:3px,color:#fff
classDef l1Node fill:#4169E1,stroke:#333,stroke-width:2px,color:#fff
classDef l2Node fill:#32CD32,stroke:#333,stroke-width:2px,color:#fff
classDef leafNode fill:#FFD700,stroke:#333,stroke-width:2px,color:#000
class Root rootNode
class L1L l1Node
class L1R l1Node
class L2LL l2Node
class L2LR l2Node
class L2RL l2Node
class L2RR l2Node
class L3LLL leafNode
class L3LLR leafNode
class L3LRL leafNode
class L3LRR leafNode
While this is similar to how you might update multiple ticks in Uniswap, the key difference is that in Ammplify, liquidity operations are organized into a tree structure where range updates follow optimal paths through the tree hierarchy. Unlike when you have to update each tick individually, in Ammplify, the tree walker finds the Lowest Common Ancestor (LCA) that covers your range and efficiently updates only the necessary nodes, allowing for logarithmic complexity instead of linear operations and you only pay gas for the nodes you actually modify.
graph LR
subgraph Step1 ["📦 Step 1: User wants to add liquidity to 4,7"]
Range1[🔵 Target Range: 4,7]
Problem1[❌ Need to find which tree nodes to update]
Range1 -.->|need efficient path| Problem1
end
subgraph Step2 ["📦 Step 2: Find LCA that covers 4,7"]
LCA[🔵 LCA: 4,4<br/>Covers exactly 4,7]
Path[🔵 Optimal Path Found:<br/>From Root to 4,4 to children]
LCA -.->|✅ Perfect match| Path
end
subgraph Step3 ["📦 Step 3: Tree walking execution"]
Result[🔵 Update 4,4 to 4,2 and 6,2<br/>O log n complexity]
end
Step1 --> Step2
Step2 --> Step3
%% Node styling matching tree diagram
classDef rangeNode fill:#32CD32,stroke:#333,stroke-width:2px,color:#fff
classDef lcaNode fill:#4169E1,stroke:#333,stroke-width:2px,color:#fff
classDef resultNode fill:#FFD700,stroke:#333,stroke-width:2px,color:#000
class Range1,LCA rangeNode
class Path lcaNode
class Problem1,Result resultNode
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract AmmplifyTreeSimplified {
struct TreeNode {
uint24 base; // Starting tick
uint24 width; // Range width (power of 2)
uint128 liquidity; // Liquidity at this node
uint128 subtreeLiq; // Total liquidity in subtree
}
// Tree storage: Key (base, width) -> Node data
mapping(uint48 => TreeNode) public nodes;
uint24 public rootWidth;
// Initialize the tree with a root width (must be power of 2)
constructor(uint24 _rootWidth) {
require(_rootWidth > 0 && (_rootWidth & (_rootWidth - 1)) == 0, "Root width must be power of 2");
rootWidth = _rootWidth;
}
// Create tree key from base and width
function makeKey(uint24 base, uint24 width) public pure returns (uint48) {
return (uint48(width) << 24) | base;
}
// Add liquidity to a range [left, right]
function addLiquidity(uint24 left, uint24 right, uint128 amount) external {
require(left <= right, "Invalid range");
require(right < rootWidth, "Range exceeds tree bounds");
// Use simplified iterative approach
_updateRange(left, right, amount);
}
// ITERATIVE tree walking (simplified Ammplify LCA approach)
function _updateRange(uint24 left, uint24 right, uint128 amount) internal {
// 1. Find LCA that contains the range (like real Ammplify)
uint24 lcaWidth = findLCAWidth(left, right);
uint24 lcaBase = left & ~(lcaWidth - 1);
// 2. Walk down from root to LCA, updating subtree totals
uint24 currentBase = 0;
uint24 currentWidth = rootWidth;
while (currentWidth > lcaWidth) {
uint48 key = makeKey(currentBase, currentWidth);
nodes[key].subtreeLiq += amount * lcaWidth; // Width-weighted like Ammplify
// Navigate toward LCA
uint24 midPoint = currentBase + currentWidth / 2;
if (lcaBase < midPoint) {
currentWidth /= 2; // Go left
} else {
currentBase = midPoint; // Go right
currentWidth /= 2;
}
}
// 3. Update the LCA node itself
uint48 lcaKey = makeKey(lcaBase, lcaWidth);
nodes[lcaKey].subtreeLiq += amount * lcaWidth;
// 4. If LCA exactly matches our range, add direct liquidity
if (lcaBase == left && (lcaBase + lcaWidth - 1) == right) {
nodes[lcaKey].liquidity += amount;
} else {
// 5. Otherwise, recursively update children (simplified)
_updateLCAChildren(lcaBase, lcaWidth, left, right, amount);
}
}
// Handle range updates within the LCA subtree
function _updateLCAChildren(uint24 base, uint24 width, uint24 left, uint24 right, uint128 amount) internal {
if (width == 1) {
// Leaf node - add direct liquidity
uint48 key = makeKey(base, width);
nodes[key].liquidity += amount;
return;
}
uint24 midPoint = base + width / 2;
uint24 leftWidth = width / 2;
uint24 rightWidth = width / 2;
// Update left child if range overlaps
if (left < midPoint) {
uint48 leftKey = makeKey(base, leftWidth);
uint24 leftEnd = min(right, midPoint - 1);
uint24 childAmount = (leftEnd - left + 1);
nodes[leftKey].subtreeLiq += childAmount * amount;
if (base == left && (base + leftWidth - 1) == leftEnd) {
nodes[leftKey].liquidity += amount;
} else if (leftWidth > 1) {
_updateLCAChildren(base, leftWidth, left, leftEnd, amount);
}
}
// Update right child if range overlaps
if (right >= midPoint) {
uint48 rightKey = makeKey(midPoint, rightWidth);
uint24 rightStart = max(left, midPoint);
uint24 childAmount = (right - rightStart + 1);
nodes[rightKey].subtreeLiq += childAmount * amount;
if (midPoint == rightStart && (midPoint + rightWidth - 1) == right) {
nodes[rightKey].liquidity += amount;
} else if (rightWidth > 1) {
_updateLCAChildren(midPoint, rightWidth, rightStart, right, amount);
}
}
}
// Query liquidity at a specific tick
function getLiquidityAt(uint24 tick) external view returns (uint128 totalLiq) {
require(tick < rootWidth, "Tick out of bounds");
// Walk down tree to accumulate liquidity
uint24 currentBase = 0;
uint24 currentWidth = rootWidth;
while (currentWidth >= 1) {
uint48 key = makeKey(currentBase, currentWidth);
totalLiq += nodes[key].liquidity;
if (currentWidth == 1) break;
// Navigate to appropriate child
uint24 midPoint = currentBase + currentWidth / 2;
if (tick < midPoint) {
currentWidth /= 2;
} else {
currentBase = midPoint;
currentWidth /= 2;
}
}
}
// Get node data at specific base and width
function getNode(uint24 base, uint24 width) public view returns (TreeNode memory) {
uint48 key = makeKey(base, width);
return nodes[key];
}
// Helper function for testing - get root node
function getRootNode() external view returns (TreeNode memory) {
return getNode(0, rootWidth);
}
function findLCAWidth(uint24 left, uint24 right) internal pure returns (uint24) {
if (left == right) return 1;
uint24 diff = left ^ right;
return msb(diff) << 1; // Next power of 2
}
function min(uint24 a, uint24 b) internal pure returns (uint24) {
return a < b ? a : b;
}
function max(uint24 a, uint24 b) internal pure returns (uint24) {
return a > b ? a : b;
}
// Simple MSB function for demonstration
function msb(uint24 x) internal pure returns (uint24 r) {
if (x >= 0x100) { x >>= 8; r += 8; }
if (x >= 0x10) { x >>= 4; r += 4; }
if (x >= 0x4) { x >>= 2; r += 2; }
if (x >= 0x2) r += 1;
}
}This is the basic structure of how the binary tree is represented in Ammplify and how range updates are facilitated through tree traversal. The actual implementation would be more complex, especially in terms of fee calculations and maker/taker interactions, but this gives a foundational understanding of the tree-based approach in the Ammplify protocol.
In production, Ammplify uses this tree system for:
- Maker Operations: Adding/removing liquidity ranges efficiently
- Taker Operations: Borrowing liquidity against collateral
- Fee Distribution: Proportional fee sharing across tree nodes
- Price Discovery: Fast lookups for active liquidity at current price
- Rebalancing: Moving liquidity between price ranges with minimal gas
This binary tree architecture represents a fundamental evolution in AMM design, moving from linear tick processing to hierarchical range management, enabling new possibilities for capital efficiency and gas optimization in DeFi.