ИнженерияMar 28, 2026
Deep EVM #14: Поиск арбитражных циклов — DFS на графе пулов
OS
Open Soft Team
Engineering Team
Арбитраж как задача на графах
Арбитраж между DEX-пулами — по сути задача поиска прибыльных циклов в ориентированном взвешенном графе. Узлы — токены, рёбра — пулы ликвидности, веса — обменные курсы с учётом комиссий.
Если произведение весов рёбер вдоль цикла > 1, цикл прибылен.
Моделирование графа
Структуры данных
use std::collections::HashMap;
#[derive(Clone, Debug)]
pub struct Pool {
pub address: Address,
pub token0: Address,
pub token1: Address,
pub reserve0: U256,
pub reserve1: U256,
pub fee: u32, // fee в базисных пунктах (30 = 0.3%)
pub protocol: Protocol,
}
#[derive(Clone, Debug)]
pub enum Protocol {
UniswapV2,
UniswapV3,
SushiSwap,
Curve,
}
#[derive(Clone, Debug)]
pub struct Edge {
pub pool: Pool,
pub token_in: Address,
pub token_out: Address,
}
pub struct ArbitrageGraph {
// token_address → vec of edges starting from this token
pub adjacency: HashMap<Address, Vec<Edge>>,
pub tokens: Vec<Address>,
}
Построение графа
impl ArbitrageGraph {
pub fn new() -> Self {
Self {
adjacency: HashMap::new(),
tokens: Vec::new(),
}
}
pub fn add_pool(&mut self, pool: Pool) {
// Каждый пул создаёт два ребра: token0→token1 и token1→token0
let edge_forward = Edge {
pool: pool.clone(),
token_in: pool.token0,
token_out: pool.token1,
};
let edge_reverse = Edge {
pool: pool.clone(),
token_in: pool.token1,
token_out: pool.token0,
};
self.adjacency
.entry(pool.token0)
.or_default()
.push(edge_forward);
self.adjacency
.entry(pool.token1)
.or_default()
.push(edge_reverse);
// Добавляем токены если новые
if !self.adjacency.contains_key(&pool.token0) {
self.tokens.push(pool.token0);
}
if !self.adjacency.contains_key(&pool.token1) {
self.tokens.push(pool.token1);
}
}
}
Расчёт обменного курса
Для AMM с формулой x * y = k (Uniswap V2):
pub fn get_amount_out(
amount_in: U256,
reserve_in: U256,
reserve_out: U256,
fee_bps: u32,
) -> U256 {
// amount_out = reserve_out * amount_in_with_fee
// / (reserve_in * 10000 + amount_in_with_fee)
let fee_factor = 10000 - fee_bps; // 9970 для 0.3% комиссии
let amount_in_with_fee = amount_in * U256::from(fee_factor);
let numerator = reserve_out * amount_in_with_fee;
let denominator = reserve_in * U256::from(10000) + amount_in_with_fee;
numerator / denominator
}
Для ребра графа:
impl Edge {
pub fn get_output(&self, amount_in: U256) -> U256 {
let (reserve_in, reserve_out) = if self.token_in == self.pool.token0 {
(self.pool.reserve0, self.pool.reserve1)
} else {
(self.pool.reserve1, self.pool.reserve0)
};
get_amount_out(amount_in, reserve_in, reserve_out, self.pool.fee)
}
}
Поиск циклов: DFS
Наивный подход — перечислить все циклы длины 2-4, начинающиеся и заканчивающиеся на WETH (или другом базовом токене):
#[derive(Clone, Debug)]
pub struct ArbitrageRoute {
pub edges: Vec<Edge>,
pub profit_ratio: f64, // > 1.0 означает прибыль
}
impl ArbitrageGraph {
pub fn find_cycles(
&self,
start_token: Address,
max_depth: usize,
) -> Vec<ArbitrageRoute> {
let mut routes = Vec::new();
let mut path = Vec::new();
let mut visited_pools = std::collections::HashSet::new();
self.dfs(
start_token,
start_token,
&mut path,
&mut visited_pools,
max_depth,
&mut routes,
);
routes
}
fn dfs(
&self,
current: Address,
target: Address,
path: &mut Vec<Edge>,
visited_pools: &mut std::collections::HashSet<Address>,
max_depth: usize,
routes: &mut Vec<ArbitrageRoute>,
) {
if path.len() > max_depth {
return;
}
// Если мы вернулись к стартовому токену (и прошли хотя бы 2 ребра)
if path.len() >= 2 && current == target {
let ratio = self.calculate_profit_ratio(path);
if ratio > 1.0 {
routes.push(ArbitrageRoute {
edges: path.clone(),
profit_ratio: ratio,
});
}
return;
}
if let Some(edges) = self.adjacency.get(¤t) {
for edge in edges {
// Не используем один пул дважды в одном пути
if visited_pools.contains(&edge.pool.address) {
continue;
}
visited_pools.insert(edge.pool.address);
path.push(edge.clone());
self.dfs(
edge.token_out,
target,
path,
visited_pools,
max_depth,
routes,
);
path.pop();
visited_pools.remove(&edge.pool.address);
}
}
}
fn calculate_profit_ratio(&self, path: &[Edge]) -> f64 {
// Используем логарифмы для избежания overflow
let mut log_ratio = 0.0_f64;
for edge in path {
let (reserve_in, reserve_out) = if edge.token_in == edge.pool.token0 {
(edge.pool.reserve0, edge.pool.reserve1)
} else {
(edge.pool.reserve1, edge.pool.reserve0)
};
let fee_factor = (10000 - edge.pool.fee) as f64 / 10000.0;
let rate = reserve_out.as_u128() as f64
/ reserve_in.as_u128() as f64
* fee_factor;
log_ratio += rate.ln();
}
log_ratio.exp()
}
}
Оптимизация DFS
Pruning — отсечение бесперспективных путей
На каждом шаге DFS вычисляем текущий обменный курс. Если он уже ниже порога прибыльности — отсекаем ветку:
fn dfs_with_pruning(
&self,
current: Address,
target: Address,
path: &mut Vec<Edge>,
visited_pools: &mut HashSet<Address>,
max_depth: usize,
current_amount: U256, // текущий баланс по пути
start_amount: U256, // стартовый баланс
routes: &mut Vec<ArbitrageRoute>,
) {
if path.len() > max_depth {
return;
}
if path.len() >= 2 && current == target {
if current_amount > start_amount {
let profit = current_amount - start_amount;
routes.push(ArbitrageRoute {
edges: path.clone(),
profit_ratio: current_amount.as_u128() as f64
/ start_amount.as_u128() as f64,
});
}
return;
}
// Pruning: если текущий баланс < 50% от стартового — бесперспективно
if current_amount < start_amount / 2 {
return;
}
// ... продолжение DFS
}
Параллелизация
Каждый стартовый токен можно обрабатывать в отдельном потоке:
use rayon::prelude::*;
pub fn find_all_arbitrage(graph: &ArbitrageGraph) -> Vec<ArbitrageRoute> {
let base_tokens = vec![WETH, USDC, USDT, DAI, WBTC];
base_tokens
.par_iter()
.flat_map(|token| {
graph.find_cycles(*token, 4)
})
.collect()
}
Алгоритм Беллмана-Форда для обнаружения отрицательных циклов
Альтернатива DFS — классический алгоритм Беллмана-Форда. Если веса рёбер — отрицательные логарифмы обменных курсов, то отрицательный цикл = прибыльный арбитраж:
pub fn bellman_ford_negative_cycles(
graph: &ArbitrageGraph,
source: Address,
) -> Vec<Vec<Address>> {
let n = graph.tokens.len();
let mut dist: HashMap<Address, f64> = HashMap::new();
let mut pred: HashMap<Address, Option<(Address, Edge)>> = HashMap::new();
for token in &graph.tokens {
dist.insert(*token, f64::INFINITY);
pred.insert(*token, None);
}
dist.insert(source, 0.0);
// Релаксация N-1 раз
for _ in 0..n - 1 {
for (token, edges) in &graph.adjacency {
for edge in edges {
let weight = -compute_log_rate(edge); // отрицательный логарифм
let new_dist = dist[token] + weight;
if new_dist < dist[&edge.token_out] {
dist.insert(edge.token_out, new_dist);
pred.insert(edge.token_out, Some((*token, edge.clone())));
}
}
}
}
// N-я итерация: если ещё возможна релаксация — найден отрицательный цикл
let mut cycles = Vec::new();
for (token, edges) in &graph.adjacency {
for edge in edges {
let weight = -compute_log_rate(edge);
if dist[token] + weight < dist[&edge.token_out] {
// Обнаружен отрицательный цикл — восстанавливаем путь
let cycle = reconstruct_cycle(&pred, edge.token_out);
cycles.push(cycle);
}
}
}
cycles
}
fn compute_log_rate(edge: &Edge) -> f64 {
let (reserve_in, reserve_out) = if edge.token_in == edge.pool.token0 {
(edge.pool.reserve0, edge.pool.reserve1)
} else {
(edge.pool.reserve1, edge.pool.reserve0)
};
let fee_factor = (10000 - edge.pool.fee) as f64 / 10000.0;
let rate = reserve_out.as_u128() as f64 / reserve_in.as_u128() as f64 * fee_factor;
rate.ln()
}
Обновление графа в реальном времени
Граф должен обновляться при каждом новом блоке и при получении pending-транзакций:
pub async fn update_reserves(
graph: &mut ArbitrageGraph,
provider: &Provider<Ws>,
pools: &[Address],
) {
for pool_addr in pools {
let reserves = get_reserves(provider, *pool_addr).await;
if let Some(edges) = graph.adjacency.values_mut().flatten().find(|e| {
e.pool.address == *pool_addr
}) {
edges.pool.reserve0 = reserves.0;
edges.pool.reserve1 = reserves.1;
}
}
}
Производительность
Для основной сети Ethereum:
| Параметр | Значение |
|---|---|
| Кол-во пулов (Uniswap V2 + Sushi) | ~50,000 |
| Кол-во уникальных токенов | ~30,000 |
| Циклы длины 2 (парные) | ~5,000 |
| Циклы длины 3 (треугольные) | ~500,000 |
| Время DFS (max_depth=3) | ~50 мс |
| Время DFS (max_depth=4) | ~2 сек |
Для MEV критично уложиться в 12 секунд (время слота). На практике серчеры ограничиваются глубиной 3-4 и фильтруют пулы по минимальной ликвидности.
Итоги
Поиск арбитражных возможностей — задача на графах. DFS с pruning — простой и эффективный подход для циклов длины 2-4. Беллман-Форд обнаруживает отрицательные циклы через логарифмические веса. Параллелизация через rayon ускоряет перебор. В следующей статье мы рассмотрим симуляцию найденных маршрутов — бинарный поиск оптимального размера и форк стейта.