아비트라지 탐지를 위한 그래프 알고리즘: Bellman-Ford에서 RICH까지

시리즈 "선물과 현물 간의 복잡한 아비트라지 체인" 제1부

암호화폐 시장을 수백 개의 거래소에서 매초 수천 개의 가격이 변동하는 살아 숨 쉬는 유기체로 상상해 보세요. 이 혼돈 속에서 일시적인 가격 불일치—"비효율성"—가 발생하며, 이를 통해 무위험 수익을 얻을 수 있습니다. 이것이 아비트라지입니다. 하지만 우리는 단순한 2단계 스왑에 대해 이야기하는 것이 아닙니다. BTC에서 ETH로, 그다음 SOL로, USDT로, 그리고 마지막으로 다시 BTC로 돌아오는 복잡한 멀티에셋 체인을 깊이 파고들 것입니다.

수백만 가지 가능성 중에서 실시간으로 이러한 체인을 어떻게 찾을 수 있을까요? 답은 그래프 이론에 있습니다.

이 글에서는 고전적인 알고리즘에서 최첨단 학술 연구까지의 여정을 따라가며, 최대 성능을 위해 모든 것을 Rust로 구현합니다.

아비트라지 그래프의 하이테크 시각화: 노드는 자산을, 엣지는 거래 쌍을 나타낸다. 강조된 순환은 탐지된 수익 기회를 나타낸다.

1. 그래프로서의 시장

그래프 알고리즘을 적용하려면 먼저 시장을 올바르게 표현해야 합니다.

1.1 정점과 간선

• 정점(노드): 자산 (BTC, ETH, USDT 등).
• 간선(링크): 거래 쌍 (BTC/USDT, ETH/BTC).
• 가중치: 환율.

환율 $R(i, j)$ (자산 $i$ 1단위로 자산 $j$를 얼마나 얻을 수 있는지)가 있을 때, 순환 $(i_1, i_2, \dots, i_k, i_1)$이 다음을 만족하면 아비트라지 기회가 존재합니다: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 곱셈에서 덧셈으로

컴퓨터는 곱셈보다 덧셈이 훨씬 빠르며, 대부분의 최단 경로 알고리즘은 합계를 위해 설계되었습니다. 간단한 수학적 트릭인 로그를 사용합니다. $\ln(a \times b) = \ln(a) + \ln(b)$ 이므로 조건은 다음과 같이 됩니다: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ 또는 부호를 뒤집어 음의 순환을 찾습니다: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

이제 각 간선의 가중치는 $w = -\ln(R)$입니다. 우리의 과제는 총 가중치가 음인 순환을 찾는 것입니다.

2. 고전적 접근법: Bellman-Ford

Bellman-Ford 알고리즘은 아비트라지 탐지의 "Hello World"입니다. 최단 경로를 찾도록 설계되었으며, 자연스럽게 음의 순환을 감지할 수 있습니다.

2.1 Rust로 구현한 알고리즘

petgraph 크레이트를 사용하여 효율적으로 구현할 수 있습니다:

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::bellman_ford;

fn find_arbitrage_bellman_ford(
    graph: &DiGraph<&str, f64>,
    start_node: NodeIndex
) -> Option<Vec<NodeIndex>> {
    // Bellman-Ford returns distances or an error if a negative cycle is found
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // No negative cycles
        Err(error) => {
            // In a real implementation, we would reconstruct the cycle
            // using the predecessor map from the error
            println!("Arbitrage detected!");
            None
        }
    }
}

2.2 복잡도와 한계

Bellman-Ford는 $O(V \times E)$로 실행되며, $V$는 자산 수, $E$는 거래 쌍 수입니다.

• 장점: 순환이 존재하면 반드시 찾는 것을 보장합니다.
• 단점: 자산 수가 증가하면 고빈도 거래(HFT)에는 너무 느립니다. 또한 한 번에 하나의 순환만 찾습니다.

3. SPFA: 더 빠른 대안

**Shortest Path Faster Algorithm(SPFA)**은 큐를 사용하여 불필요한 계산을 피하는 Bellman-Ford의 최적화 버전입니다.

use std::collections::VecDeque;

fn spfa_negative_cycle(n: usize, adj: &Vec<Vec<(usize, f64)>>) -> bool {
    let mut dist = vec![0.0; n];
    let mut count = vec![0; n];
    let mut in_queue = vec![false; n];
    let mut queue = VecDeque::new();

    for i in 0..n {
        in_queue[i] = true;
        queue.push_back(i);
    }

    while let Some(u) = queue.pop_front() {
        in_queue[u] = false;
        for &(v, weight) in &adj[u] {
            if dist[v] > dist[u] + weight {
                dist[v] = dist[u] + weight;
                count[v] = count[u] + 1;
                if count[v] >= n {
                    return true; // Negative cycle detected
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

실제로 SPFA는 $O(k \times E)$ ($k \ll V$)로 실행되는 경우가 많아, 희소한 시장 그래프에서 Bellman-Ford보다 훨씬 빠릅니다.

4. 최신 연구: RICH 알고리즘

2024년, 연구자들은 RICH(Rapid Identification of Cyclic High-profitability) 알고리즘을 제안했습니다. Bellman-Ford와 달리, RICH는 다음과 같은 금융 그래프에 특화되어 최적화되었습니다:

1. 그래프가 소~중 규모 (수백 개의 자산).
2. 가중치가 밀리초마다 변경됨.
3. 임의의 순환이 아닌 가장 수익성 높은 순환을 찾아야 함.

4.1 RICH의 핵심 혁신

• 가지치기: 현재 알려진 최적 경로를 기반으로 수익성 있는 순환으로 이어질 수 없는 경로를 즉시 제거합니다.
• 계층적 탐색: 비트마스크 최적화를 사용하여 증가하는 길이(3-레그, 4-레그, 5-레그)의 순환을 탐색합니다.
• 점진적 업데이트: 전체 알고리즘을 다시 실행하는 대신, 가격 변경의 영향을 받는 그래프 부분만 업데이트합니다.

5. 구현 과제: 수수료와 유동성

실제 거래에는 비용이 듭니다. 멀티레그 순환 $(A \to B \to C \to A)$에서는 세 번의 별도 거래 수수료가 발생합니다.

5.1 수수료 반영

간선 가중치를 조정해야 합니다: $w = -\ln(R \times (1 - \text{fee}))$ 이것은 그래프를 크게 가지치기하며, 많은 이론적 순환이 실행 비용으로 인해 무효화됩니다.

5.2 유동성과 슬리피지

자산을 더 많이 구매할수록 가격이 올라갑니다(슬리피지). $100에서 수익성 있어 보이는 순환이$10,000에서는 손실이 될 수 있습니다. 고급 그래프 모델은 파라메트릭 가중치를 사용하며, $w$는 거래량 $V$의 함수가 됩니다. 이로 인해 문제는 단순한 최단 경로 탐색에서 그래프 위의 볼록 최적화 문제로 전환됩니다.

6. 왜 Rust인가?

아비트라지의 세계에서 100마이크로초는 수익과 "놓친" 기회의 차이입니다.

• 메모리 안전성: 가비지 컬렉터(GC) 일시 정지가 없어 중요한 순간에 봇이 멈추지 않습니다.
• 제로 코스트 추상화: 원시 포인터의 성능을 잃지 않으면서 고수준 그래프 구조를 사용할 수 있습니다.
• 동시성: Rust의 "두려움 없는 동시성"을 통해 10개 거래소의 WebSocket 피드를 병렬로 파싱하고 공유 그래프를 안전하게 업데이트할 수 있습니다.

결론

그래프 알고리즘은 현대 암호화폐 아비트라지의 핵심 엔진입니다. Bellman-Ford가 기초를 제공하지만, 최신 시스템은 SPFA와 같은 최적화된 변형이나 RICH와 같은 특화 알고리즘을 사용합니다.

이 시리즈의 다음 파트에서는 선물-현물 아비트라지를 다루며, 단순 자산 스왑에서 펀딩 레이트와 캐시 앤 캐리 전략으로 그래프를 확장합니다.

저지연 거래 시스템을 구축 중이신가요? 오픈소스 Rust HFT 템플릿을 확인해 보세요.