Deep EVM #14: Membangun Pencari Siklus Arbitrase — DFS pada Graf Pool

Masalah Pencarian Arbitrase

Arbitrase DEX pada dasarnya adalah masalah graf: setiap pool likuiditas adalah edge yang menghubungkan dua token (vertex). Siklus menguntungkan dalam graf ini merepresentasikan peluang arbitrase.

Misalnya:

• Pool A: WETH/USDC di Uniswap
• Pool B: USDC/DAI di SushiSwap
• Pool C: DAI/WETH di Curve

Jika harga relatif memungkinkan, siklus WETH -> USDC -> DAI -> WETH bisa menghasilkan lebih banyak WETH dari yang Anda mulai.

Membangun Graf Pool

Langkah pertama adalah membangun graf dari semua pool yang tersedia:

use std::collections::HashMap;

#[derive(Clone)]
struct Pool {
    address: Address,
    token0: Address,
    token1: Address,
    reserve0: U256,
    reserve1: U256,
    fee: u32, // basis points (30 = 0.3%)
}

struct PoolGraph {
    // token -> [(pool_index, other_token)]
    adjacency: HashMap<Address, Vec<(usize, Address)>>,
    pools: Vec<Pool>,
}

impl PoolGraph {
    fn new() -> Self {
        Self {
            adjacency: HashMap::new(),
            pools: Vec::new(),
        }
    }
    
    fn add_pool(&mut self, pool: Pool) {
        let idx = self.pools.len();
        self.adjacency
            .entry(pool.token0)
            .or_default()
            .push((idx, pool.token1));
        self.adjacency
            .entry(pool.token1)
            .or_default()
            .push((idx, pool.token0));
        self.pools.push(pool);
    }
}

Algoritma DFS untuk Pencarian Siklus

Kami menggunakan Depth-First Search (DFS) yang dimulai dari token tertentu dan mencari jalur yang kembali ke token awal:

impl PoolGraph {
    fn find_cycles(
        &self,
        start: Address,
        max_depth: usize,
    ) -> Vec<Vec<usize>> {
        let mut cycles = Vec::new();
        let mut path = Vec::new();
        let mut visited_pools = vec![false; self.pools.len()];
        
        self.dfs(
            start,
            start,
            &mut path,
            &mut visited_pools,
            &mut cycles,
            max_depth,
        );
        
        cycles
    }
    
    fn dfs(
        &self,
        current: Address,
        target: Address,
        path: &mut Vec<usize>,
        visited: &mut Vec<bool>,
        cycles: &mut Vec<Vec<usize>>,
        max_depth: usize,
    ) {
        if path.len() >= max_depth {
            return;
        }
        
        if let Some(neighbors) = self.adjacency.get(&current) {
            for &(pool_idx, next_token) in neighbors {
                if visited[pool_idx] {
                    continue;
                }
                
                // Siklus ditemukan!
                if next_token == target && path.len() >= 2 {
                    let mut cycle = path.clone();
                    cycle.push(pool_idx);
                    cycles.push(cycle);
                    continue;
                }
                
                visited[pool_idx] = true;
                path.push(pool_idx);
                self.dfs(next_token, target, path, visited, cycles, max_depth);
                path.pop();
                visited[pool_idx] = false;
            }
        }
    }
}

Menghitung Profitabilitas

Setelah menemukan siklus, kita perlu menghitung apakah siklus tersebut menguntungkan:

fn calculate_output(
    amount_in: U256,
    reserve_in: U256,
    reserve_out: U256,
    fee_bps: u32,
) -> U256 {
    let fee_multiplier = 10000 - fee_bps; // misal 9970 untuk 0.3%
    let amount_with_fee = amount_in * U256::from(fee_multiplier);
    let numerator = amount_with_fee * reserve_out;
    let denominator = reserve_in * U256::from(10000) + amount_with_fee;
    numerator / denominator
}

fn is_profitable(
    graph: &PoolGraph,
    cycle: &[usize],
    start_token: Address,
    amount_in: U256,
) -> Option<U256> {
    let mut current_amount = amount_in;
    let mut current_token = start_token;
    
    for &pool_idx in cycle {
        let pool = &graph.pools[pool_idx];
        let (reserve_in, reserve_out) = if current_token == pool.token0 {
            (pool.reserve0, pool.reserve1)
        } else {
            (pool.reserve1, pool.reserve0)
        };
        
        current_amount = calculate_output(
            current_amount,
            reserve_in,
            reserve_out,
            pool.fee,
        );
        
        current_token = if current_token == pool.token0 {
            pool.token1
        } else {
            pool.token0
        };
    }
    
    if current_amount > amount_in {
        Some(current_amount - amount_in)
    } else {
        None
    }
}

Optimasi Input Optimal

Keuntungan arbitrase adalah fungsi konkaf dari jumlah input. Ada jumlah optimal yang memaksimalkan keuntungan. Kita menggunakan binary search:

fn find_optimal_input(
    graph: &PoolGraph,
    cycle: &[usize],
    start_token: Address,
) -> (U256, U256) {
    let mut lo = U256::from(1_000_000u64);  // minimum 0.001 ETH
    let mut hi = U256::from(100_000_000_000_000_000_000u128); // 100 ETH
    
    for _ in 0..64 {
        let mid1 = lo + (hi - lo) / 3;
        let mid2 = hi - (hi - lo) / 3;
        
        let profit1 = is_profitable(graph, cycle, start_token, mid1)
            .unwrap_or(U256::ZERO);
        let profit2 = is_profitable(graph, cycle, start_token, mid2)
            .unwrap_or(U256::ZERO);
        
        if profit1 < profit2 {
            lo = mid1;
        } else {
            hi = mid2;
        }
    }
    
    let optimal = (lo + hi) / 2;
    let profit = is_profitable(graph, cycle, start_token, optimal)
        .unwrap_or(U256::ZERO);
    (optimal, profit)
}

Pertimbangan Praktis

1. Latensi — Pencarian harus selesai dalam milidetik. Batasi kedalaman DFS ke 3-4 hop.
2. Reserves stale — Gunakan event subscription untuk memperbarui reserves secara real-time.
3. Gas cost — Kurangi estimasi biaya gas dari profit untuk menentukan profitabilitas bersih.
4. Slippage — Swap besar memindahkan harga; perhitungan dengan reserves statis melebih-lebihkan profit.
5. Kompetisi — Pencari lain menemukan siklus yang sama; yang tercepat menang.

Kesimpulan

Pencarian siklus arbitrase adalah masalah graf klasik yang diterapkan ke DeFi. DFS dengan batasan kedalaman menemukan siklus, kalkulasi AMM menentukan profitabilitas, dan binary search mengoptimalkan jumlah input. Di artikel berikutnya, kita akan mensimulasikan siklus ini terhadap state fork untuk memverifikasi profitabilitas sebelum mengirim bundle.