Deep EVM #14: Construyendo un Buscador de Ciclos de Arbitraje — DFS en un Grafo de Pools

El arbitraje como problema de grafos

El arbitraje en DeFi se modela naturalmente como un problema de grafos. Cada token es un nodo, y cada pool de liquidez (Uniswap, Sushiswap, Curve, etc.) es una arista dirigida con un peso que representa el tipo de cambio.

Un ciclo de arbitraje rentable es un ciclo en este grafo donde el producto de los tipos de cambio a lo largo del camino es mayor que 1:

ETH -> USDC -> DAI -> ETH
Si: rate(ETH->USDC) * rate(USDC->DAI) * rate(DAI->ETH) > 1.0
Entonces: el ciclo es rentable

Modelado del grafo

En Rust, representamos el grafo con listas de adyacencia:

use std::collections::HashMap;

struct Pool {
    address: Address,
    token0: Address,
    token1: Address,
    reserve0: U256,
    reserve1: U256,
    fee: u32, // 3000 = 0.3%
}

struct Graph {
    // token -> [(pool_index, next_token, direction)]
    adjacency: HashMap<Address, Vec<(usize, Address, bool)>>,
    pools: Vec<Pool>,
}

Detección de ciclos con DFS

Usamos búsqueda en profundidad (DFS) limitada para encontrar ciclos que comienzan y terminan en un token dado:

impl Graph {
    fn find_cycles(
        &self,
        start: Address,
        max_hops: usize,
    ) -> Vec<Vec<usize>> {
        let mut result = Vec::new();
        let mut path = Vec::new();
        let mut visited_pools = HashSet::new();
        
        self.dfs(
            start, start, &mut path,
            &mut visited_pools, &mut result,
            max_hops, 0,
        );
        
        result
    }
    
    fn dfs(
        &self,
        current: Address,
        target: Address,
        path: &mut Vec<usize>,
        visited_pools: &mut HashSet<usize>,
        result: &mut Vec<Vec<usize>>,
        max_hops: usize,
        depth: usize,
    ) {
        if depth > 0 && current == target {
            result.push(path.clone());
            return;
        }
        if depth >= max_hops {
            return;
        }
        
        if let Some(neighbors) = self.adjacency.get(&current) {
            for &(pool_idx, next_token, _dir) in neighbors {
                if visited_pools.contains(&pool_idx) {
                    continue;
                }
                
                visited_pools.insert(pool_idx);
                path.push(pool_idx);
                
                self.dfs(
                    next_token, target, path,
                    visited_pools, result,
                    max_hops, depth + 1,
                );
                
                path.pop();
                visited_pools.remove(&pool_idx);
            }
        }
    }
}

Cálculo de rentabilidad

Para cada ciclo encontrado, calculamos si es rentable simulando los swaps secuencialmente:

fn calculate_profit(
    &self,
    cycle: &[usize],
    initial_amount: U256,
) -> Option<U256> {
    let mut amount = initial_amount;
    
    for &pool_idx in cycle {
        let pool = &self.pools[pool_idx];
        amount = self.get_amount_out(
            amount, pool.reserve0, pool.reserve1, pool.fee
        );
    }
    
    if amount > initial_amount {
        Some(amount - initial_amount)
    } else {
        None
    }
}

fn get_amount_out(
    &self,
    amount_in: U256,
    reserve_in: U256,
    reserve_out: U256,
    fee: u32, // base 10000
) -> U256 {
    let fee_factor = 10000 - fee; // e.g., 9970 para 0.3%
    let numerator = amount_in * fee_factor * reserve_out;
    let denominator = reserve_in * 10000 + amount_in * fee_factor;
    numerator / denominator
}

Poda eficiente

Con miles de pools, el espacio de búsqueda es enorme. Técnicas de poda:

1. Limitar profundidad — Ciclos de 2-4 hops son los más rentables; 5+ rara vez lo son
2. Poda por liquidez — Ignorar pools con reservas menores a un umbral
3. Poda por token — Solo considerar tokens con suficiente liquidez y volumen
4. Poda temprana por precio — Si el producto parcial de tipos de cambio ya es < 0.99, podar
5. Paralelización — Buscar ciclos desde múltiples tokens iniciales en paralelo usando rayon

Optimización del monto inicial

Una vez encontrado un ciclo rentable, necesitamos optimizar cuánto capital invertir. Demasiado poco y el beneficio no cubre el gas; demasiado y el impacto de precio reduce las ganancias.

Usamos búsqueda binaria para encontrar el óptimo:

fn optimize_amount(
    &self,
    cycle: &[usize],
    min: U256,
    max: U256,
) -> (U256, U256) {
    let mut lo = min;
    let mut hi = max;
    let mut best_amount = lo;
    let mut best_profit = U256::zero();
    
    for _ in 0..64 { // 64 iteraciones = precisión de ~1 wei
        let mid = (lo + hi) / 2;
        if let Some(profit) = self.calculate_profit(cycle, mid) {
            if profit > best_profit {
                best_profit = profit;
                best_amount = mid;
            }
            lo = mid;
        } else {
            hi = mid;
        }
    }
    
    (best_amount, best_profit)
}

Conclusión

Encontrar ciclos de arbitraje es un problema combinatorio que requiere un balance entre exhaustividad y velocidad. La búsqueda DFS con poda agresiva y optimización del monto inicial proporciona un framework sólido para construir un searcher de arbitraje competitivo. En el próximo artículo, cubriremos la simulación de transacciones con state forks y la optimización bajo la presión del deadline de 12 segundos.