Deep EVM #14 : Construire un algorithme de cycles d'arbitrage — DFS sur un graphe de pools

Modéliser les DEX comme un graphe

Pour trouver des opportunités d’arbitrage, nous devons d’abord modéliser l’ensemble des pools de liquidité comme un graphe dirigé.

Chaque pool AMM (Uniswap V2, V3, Sushiswap, etc.) représente une arête bidirectionnelle entre deux tokens :

struct Pool {
    address: Address,
    token0: Address,
    token1: Address,
    reserve0: U256,
    reserve1: U256,
    fee: u32,  // En points de base (30 = 0.3%)
}

struct Graph {
    adjacency: HashMap<Address, Vec<(Address, Pool)>>,  // token -> [(token, pool)]
}

Sur Ethereum mainnet, il y a plus de 100 000 pools. Notre graphe a des milliers de nœuds (tokens) et des centaines de milliers d’arêtes (pools).

DFS avec détection de cycles

Un cycle d’arbitrage est un chemin qui commence et se termine au même token, où l’exécution du chemin produit plus de tokens qu’au départ.

fn find_cycles(
    graph: &Graph,
    start_token: Address,
    max_depth: usize,
) -> Vec<Vec<Pool>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    let mut visited = HashSet::new();

    dfs(
        graph,
        start_token,
        start_token,
        &mut path,
        &mut visited,
        &mut result,
        max_depth,
    );
    result
}

fn dfs(
    graph: &Graph,
    current: Address,
    target: Address,
    path: &mut Vec<Pool>,
    visited: &mut HashSet<Address>,
    result: &mut Vec<Vec<Pool>>,
    max_depth: usize,
) {
    if path.len() > max_depth {
        return;
    }

    if path.len() >= 2 && current == target {
        result.push(path.clone());
        return;
    }

    visited.insert(current);

    if let Some(neighbors) = graph.adjacency.get(&current) {
        for (next_token, pool) in neighbors {
            if *next_token == target || !visited.contains(next_token) {
                path.push(pool.clone());
                dfs(graph, *next_token, target, path, visited, result, max_depth);
                path.pop();
            }
        }
    }

    visited.remove(&current);
}

Calcul du profit d’un cycle

Pour chaque cycle trouvé, calculez le montant de sortie en simulant les swaps séquentiels :

fn calculate_output(
    pools: &[Pool],
    amount_in: U256,
) -> U256 {
    let mut current_amount = amount_in;

    for pool in pools {
        current_amount = get_amount_out(
            current_amount,
            pool.reserve_in,
            pool.reserve_out,
            pool.fee,
        );
    }

    current_amount
}

fn get_amount_out(
    amount_in: U256,
    reserve_in: U256,
    reserve_out: U256,
    fee_bps: u32,
) -> U256 {
    let fee_multiplier = 10000 - fee_bps;
    let amount_in_with_fee = amount_in * fee_multiplier;
    let numerator = amount_in_with_fee * reserve_out;
    let denominator = reserve_in * 10000 + amount_in_with_fee;
    numerator / denominator
}

Un cycle est rentable si calculate_output(cycle, amount) > amount.

Élagage pour les performances

Avec 100 000+ pools, le DFS naïf est trop lent. Techniques d’élagage :

1. Limiter la profondeur — Les cycles de plus de 4-5 sauts sont rarement rentables
2. Filtrer les pools illiquides — Ignorer les pools avec moins de 1000 $ de liquidité
3. Token de départ stratégique — Commencer par WETH, USDC, USDT qui apparaissent dans la plupart des cycles rentables
4. Pré-filtrage des paires — Indexer les pools par token pour un accès O(1)

Optimisation du montant d’entrée

Une fois un cycle rentable identifié, trouvez le montant d’entrée optimal par recherche binaire :

fn optimal_input(
    pools: &[Pool],
    min_amount: U256,
    max_amount: U256,
) -> (U256, U256) {  // (montant_optimal, profit)
    let mut lo = min_amount;
    let mut hi = max_amount;

    for _ in 0..64 {  // 64 itérations = précision de 1 wei
        let mid = (lo + hi) / 2;
        let profit_mid = calculate_output(pools, mid) - mid;
        let profit_mid_plus = calculate_output(pools, mid + 1) - (mid + 1);

        if profit_mid_plus > profit_mid {
            lo = mid;
        } else {
            hi = mid;
        }
    }

    let optimal = (lo + hi) / 2;
    let profit = calculate_output(pools, optimal) - optimal;
    (optimal, profit)
}

Conclusion

La recherche de cycles d’arbitrage est le cœur de tout bot MEV d’arbitrage. Le DFS sur un graphe de pools, combiné avec un élagage agressif et une optimisation du montant d’entrée, permet de scanner des milliers de chemins en quelques millisecondes.

Dans le prochain article, nous couvrirons la simulation MEV : fork d’état, recherche binaire de montant optimal, et la contrainte du délai de 12 secondes.