Deep EVM #14: 차익거래 사이클 찾기 — 풀 그래프에서의 DFS
Engineering Team
토큰-풀 그래프
차익거래 사이클은 동일한 토큰으로 시작하고 끝나는 스왑 시퀀스로, 입력보다 더 많은 출력을 생산합니다. 이러한 사이클을 체계적으로 찾기 위해 DeFi 생태계를 방향 그래프로 모델링합니다:
- 노드 = 토큰 (WETH, USDC, DAI, WBTC, …)
- 엣지 = 두 토큰 간 스왑을 가능하게 하는 유동성 풀
Uniswap V2 페어(WETH/USDC)는 두 개의 방향 엣지를 생성합니다: WETH→USDC와 USDC→WETH. Uniswap V3 풀도 동일하지만 다른 가격 책정(집중 유동성)을 사용합니다. 3개의 토큰이 있는 Balancer 가중 풀은 6개의 방향 엣지를 생성합니다(모든 쌍의 양방향).
use std::collections::HashMap;
#[derive(Clone, Debug)]
pub struct Pool {
pub address: Address,
pub token0: Address,
pub token1: Address,
pub protocol: Protocol,
pub fee: u32, // basis points
pub reserve0: U256,
pub reserve1: U256,
}
#[derive(Clone, Debug)]
pub enum Protocol {
UniswapV2,
UniswapV3,
SushiSwap,
Curve,
Balancer,
}
pub struct TokenGraph {
// token_address → vec of (other_token, pool)
pub adjacency: HashMap<Address, Vec<(Address, Pool)>>,
}
impl TokenGraph {
pub fn new() -> Self {
Self {
adjacency: HashMap::new(),
}
}
pub fn add_pool(&mut self, pool: Pool) {
self.adjacency
.entry(pool.token0)
.or_default()
.push((pool.token1, pool.clone()));
self.adjacency
.entry(pool.token1)
.or_default()
.push((pool.token0, pool));
}
}
이더리움 메인넷에는 약 80,000개의 활성 유동성 풀이 있습니다. 그래프에는 약 15,000개의 고유 토큰과 약 160,000개의 방향 엣지가 있습니다.
DFS 사이클 감지
“기본 토큰”(일반적으로 WETH, ETH 단위로 이익을 원하므로)에서 시작하는 깊이 우선 검색을 사용하여 차익거래 사이클을 찾습니다.
#[derive(Clone, Debug)]
pub struct Cycle {
pub pools: Vec<Pool>,
pub tokens: Vec<Address>, // 토큰 경로: [WETH, USDC, DAI, WETH]
pub id: [u8; 32], // 중복 제거를 위한 keccak256 해시
}
pub fn find_cycles(
graph: &TokenGraph,
start_token: Address,
max_depth: usize, // 일반적으로 2-4 홉
) -> Vec<Cycle> {
let mut results = Vec::new();
let mut path_tokens = vec![start_token];
let mut path_pools: Vec<Pool> = Vec::new();
let mut visited = HashSet::new();
visited.insert(start_token);
dfs(
graph,
start_token,
start_token,
max_depth,
&mut path_tokens,
&mut path_pools,
&mut visited,
&mut results,
);
results
}
fn dfs(
graph: &TokenGraph,
current: Address,
start: Address,
max_depth: usize,
path_tokens: &mut Vec<Address>,
path_pools: &mut Vec<Pool>,
visited: &mut HashSet<Address>,
results: &mut Vec<Cycle>,
) {
if path_pools.len() >= max_depth {
return;
}
let neighbors = match graph.adjacency.get(¤t) {
Some(n) => n,
None => return,
};
for (next_token, pool) in neighbors {
// 시작점으로 2홉 이상 돌아왔으면 사이클을 찾은 것
if *next_token == start && path_pools.len() >= 2 {
let mut cycle_tokens = path_tokens.clone();
cycle_tokens.push(start);
let mut cycle_pools = path_pools.clone();
cycle_pools.push(pool.clone());
let id = compute_cycle_id(&cycle_pools);
results.push(Cycle {
pools: cycle_pools,
tokens: cycle_tokens,
id,
});
continue;
}
// 토큰을 재방문하지 않음 (시작점 제외)
if visited.contains(next_token) {
continue;
}
visited.insert(*next_token);
path_tokens.push(*next_token);
path_pools.push(pool.clone());
dfs(
graph,
*next_token,
start,
max_depth,
path_tokens,
path_pools,
visited,
results,
);
path_tokens.pop();
path_pools.pop();
visited.remove(next_token);
}
}
max_depth 매개변수
깊이 매개변수는 사이클 길이(홉 수)를 제어합니다:
- depth=2: 직접 차익거래. WETH→USDC→WETH (두 풀). 단순하고 경쟁적.
- depth=3: 삼각 차익거래. WETH→USDC→DAI→WETH. 최적 지점 — 경쟁 서처가 적을 만큼 복잡하지만 빠르게 시뮬레이션할 만큼 단순.
- depth=4: 사각 차익거래. 더 높은 잠재 이익이지만 기하급수적으로 더 많은 사이클을 평가해야 하고 가스 비용이 높음.
- depth=5+: 가스 비용 후 거의 수익성이 없음. 검색 공간이 조합적으로 폭발.
풀: 80,000
깊이 2 사이클: ~50,000
깊이 3 사이클: ~15,000,000
깊이 4 사이클: ~2,000,000,000+
실무에서 깊이 3이 프로덕션 최적 지점입니다. 약 1,500만 개의 삼각 사이클을 찾고 시뮬레이션할 가치가 있는 약 100,000개로 필터링합니다.
Keccak256으로 중복 제거
DFS는 중복 사이클을 생성합니다: WETH→USDC→DAI→WETH와 WETH→DAI→USDC→WETH는 반대 방향으로 순회한 같은 사이클입니다. 정규 해시를 사용하여 중복을 제거합니다:
use tiny_keccak::{Hasher, Keccak};
fn compute_cycle_id(pools: &[Pool]) -> [u8; 32] {
// 정규 표현을 위해 풀 주소를 정렬
let mut addresses: Vec<Address> = pools.iter().map(|p| p.address).collect();
addresses.sort();
let mut hasher = Keccak::v256();
for addr in &addresses {
hasher.update(addr.as_bytes());
}
let mut output = [0u8; 32];
hasher.finalize(&mut output);
output
}
해싱 전에 풀 주소를 정렬하면 같은 사이클의 양 방향이 동일한 ID를 생성합니다. HashSet<[u8; 32]>에 삽입하고 중복을 건너뜁니다.
왜 더 간단한 해시 대신 keccak256인가? 1,500만 사이클 집합에서 128비트 해시의 충돌 확률은 무시할 수 없습니다. 256비트에서는 충돌이 천문학적으로 불가능합니다.
필터링: 수백만을 수천으로 줄이기
모든 사이클이 시뮬레이션할 가치가 있는 것은 아닙니다. 필터를 적용합니다:
유동성 필터
준비금이 임계값 이하인 풀이 포함된 사이클을 폐기합니다. 유동성이 100달러인 풀은 의미 있는 차익거래를 생산할 수 없습니다.
fn has_sufficient_liquidity(cycle: &Cycle, min_reserve_usd: f64) -> bool {
cycle.pools.iter().all(|pool| {
let reserve_usd = estimate_reserve_usd(pool);
reserve_usd >= min_reserve_usd
})
}
부실 필터
N 블록 이상 유휴(스왑 없음) 상태인 모든 풀이 포함된 사이클을 폐기합니다. 부실 풀에는 차익거래가 거의 없습니다.
토큰 블랙리스트
스캠 토큰, 전송 수수료 토큰, 전송 제한이 있는 토큰을 제외합니다. 시뮬레이션에서는 수익성이 있어 보이지만 온체인에서 실패합니다.
const BLACKLISTED_TOKENS: &[&str] = &[
"0x...", // 알려진 전송 수수료 토큰
"0x...", // 알려진 허니팟
];
fn contains_blacklisted_token(cycle: &Cycle) -> bool {
cycle.tokens.iter().any(|t| {
BLACKLISTED_TOKENS.contains(&format!("{:?}", t).as_str())
})
}
정적 수익성 추정
완전한 시뮬레이션 전에, 상수곱 공식을 사용하여 대략적인 수익성 추정치를 계산합니다:
fn estimate_output_v2(
amount_in: U256,
reserve_in: U256,
reserve_out: U256,
fee_bps: u32,
) -> U256 {
let fee_factor = 10000 - fee_bps; // 예: 0.3% 수수료에 9970
let numerator = amount_in * reserve_out * U256::from(fee_factor);
let denominator = reserve_in * U256::from(10000) + amount_in * U256::from(fee_factor);
numerator / denominator
}
fn estimate_cycle_profit(
cycle: &Cycle,
input_amount: U256,
) -> Option<U256> {
let mut current_amount = input_amount;
for (i, pool) in cycle.pools.iter().enumerate() {
let token_in = cycle.tokens[i];
let (reserve_in, reserve_out) = if token_in == pool.token0 {
(pool.reserve0, pool.reserve1)
} else {
(pool.reserve1, pool.reserve0)
};
current_amount = estimate_output_v2(
current_amount,
reserve_in,
reserve_out,
pool.fee,
);
}
if current_amount > input_amount {
Some(current_amount - input_amount)
} else {
None
}
}
이 추정치는 불완전하지만(Uniswap V3 틱 수학, Curve 스테이블스왑 곡선 등을 무시) 비용이 많이 드는 시뮬레이션 전에 95%의 비수익 사이클을 제거합니다.
확장: 병렬화와 점진적 업데이트
80,000개 풀에서 전체 그래프를 구축하고 DFS를 실행하는 데 단일 코어에서 5-10초가 걸립니다. 프로덕션 봇의 경우 시작 비용으로 괜찮습니다. 그러나 풀 상태는 매 블록(12초)마다 변경되므로 점진적 업데이트가 필요합니다:
pub struct CycleIndex {
pub cycles_by_pool: HashMap<Address, Vec<CycleId>>,
pub all_cycles: HashMap<CycleId, Cycle>,
}
impl CycleIndex {
/// 풀의 준비금이 변경되면, 이 풀을 포함하는
/// 사이클만 무효화하고 재평가
pub fn on_pool_update(&self, pool_address: Address) -> Vec<&Cycle> {
self.cycles_by_pool
.get(&pool_address)
.map(|ids| {
ids.iter()
.filter_map(|id| self.all_cycles.get(id))
.collect()
})
.unwrap_or_default()
}
}
Uniswap V2 풀에서 Sync 이벤트가 발생하면 해당 풀의 준비금을 업데이트하고 해당 풀을 포함하는 사이클만 재평가합니다. 이렇게 하면 블록당 작업이 수백만 사이클에서 수백 개로 줄어듭니다.
DFS 자체에 대해서는 Rayon을 사용하여 기본 토큰 간에 병렬화합니다:
use rayon::prelude::*;
let base_tokens = vec![weth, usdc, usdt, dai, wbtc];
let all_cycles: Vec<Cycle> = base_tokens
.par_iter()
.flat_map(|base| find_cycles(&graph, *base, 3))
.collect();
요약
사이클 찾기는 MEV 파이프라인의 첫 번째 단계입니다. 유동성 풀의 평면 목록을 구조화된 차익거래 기회 집합으로 변환합니다. 핵심 결정 — 그래프 표현, DFS 깊이, 중복 제거 전략, 필터링 휴리스틱 — 이 기회 집합의 품질과 범위를 결정합니다. 다음 기사에서는 이러한 사이클을 시뮬레이션합니다: 차입 금액에 대한 이진 검색, 상태 포크, 12초 블록 마감 시간과의 경쟁.