Deep EVM #14: Arbitrage-Zyklen-Finder — DFS auf einem Pool-Graphen

Das Problem

Arbitrage in DeFi bedeutet, Preisunterschiede zwischen Liquiditaetspools auszunutzen. Aber wie findet man profitable Zyklen unter Tausenden von Pools?

Der Token-Pool-Graph modelliert das Problem:

• Knoten: Token (ETH, USDC, DAI, …)
• Kanten: Liquiditaetspools (Uniswap V2-Paare, V3-Pools, Curve-Pools)
• Zyklen: Pfade, die zum Start-Token zurueckkehren

Ein Arbitrage-Zyklus beginnt und endet beim selben Token (z.B. ETH -> USDC -> DAI -> ETH) und ist profitabel, wenn das Produkt der Wechselkurse > 1 ist.

Tiefensuche (DFS) fuer Zyklen

use std::collections::{HashMap, HashSet};

struct PoolGraph {
    adjacency: HashMap<Address, Vec<(Address, Pool)>>,
}

impl PoolGraph {
    fn find_cycles(
        &self,
        start: Address,
        max_hops: usize,
    ) -> Vec<Vec<Pool>> {
        let mut cycles = Vec::new();
        let mut path = Vec::new();
        let mut visited = HashSet::new();
        
        self.dfs(
            start,
            start,
            max_hops,
            &mut path,
            &mut visited,
            &mut cycles,
        );
        cycles
    }
    
    fn dfs(
        &self,
        current: Address,
        target: Address,
        remaining_hops: usize,
        path: &mut Vec<Pool>,
        visited: &mut HashSet<Address>,
        cycles: &mut Vec<Vec<Pool>>,
    ) {
        if remaining_hops == 0 { return; }
        
        if let Some(neighbors) = self.adjacency.get(&current) {
            for (next_token, pool) in neighbors {
                if *next_token == target && !path.is_empty() {
                    // Zyklus gefunden!
                    let mut cycle = path.clone();
                    cycle.push(pool.clone());
                    cycles.push(cycle);
                    continue;
                }
                
                if visited.contains(next_token) { continue; }
                
                visited.insert(*next_token);
                path.push(pool.clone());
                self.dfs(*next_token, target, remaining_hops - 1,
                         path, visited, cycles);
                path.pop();
                visited.remove(next_token);
            }
        }
    }
}

Skalierung: Millionen von Zyklen

Mit 5.000+ Pools auf Ethereum explodiert die Anzahl moeglicher Zyklen. Strategien zur Bewaeltigung:

1. Hop-Begrenzung

Beschraenke die maximale Zykluslaenge auf 3-4 Hops. Laengere Zyklen haben selten genug Profit, um die Gaskosten zu decken.

2. Deduplizierung mit keccak256

Sortiere die Pool-Adressen in jedem Zyklus und hashe sie:

use tiny_keccak::{Hasher, Keccak};

fn cycle_hash(pools: &[Pool]) -> [u8; 32] {
    let mut sorted: Vec<Address> = pools.iter()
        .map(|p| p.address)
        .collect();
    sorted.sort();
    
    let mut hasher = Keccak::v256();
    for addr in &sorted {
        hasher.update(addr.as_bytes());
    }
    let mut output = [0u8; 32];
    hasher.finalize(&mut output);
    output
}

3. Parallelisierung

Verwende rayon fuer parallele DFS auf verschiedenen Start-Token:

use rayon::prelude::*;

let all_cycles: Vec<Vec<Pool>> = tokens.par_iter()
    .flat_map(|token| graph.find_cycles(*token, 4))
    .collect();

Profitabilitaetsberechnung

Fuer jeden gefundenen Zyklus berechnen Sie den erwarteten Gewinn:

fn calculate_profit(
    cycle: &[Pool],
    amount_in: U256,
) -> Option<U256> {
    let mut current_amount = amount_in;
    
    for pool in cycle {
        current_amount = pool.get_amount_out(current_amount)?;
    }
    
    if current_amount > amount_in {
        Some(current_amount - amount_in)
    } else {
        None
    }
}

Fazit

Der Arbitrage-Zyklen-Finder ist der erste Schritt in der MEV-Pipeline. Er identifiziert alle moeglichen profitablen Pfade auf dem DEX-Graphen. Die naechsten Schritte — Simulation, optimale Eingabemenge und Bundle-Erstellung — bauen auf diesen Zyklen auf.