Arbitraj Tespiti için Graf Algoritmaları: Bellman-Ford'dan RICH'e

"Vadeli İşlemler ile Spot Arasındaki Karmaşık Arbitraj Zincirleri" serisinin 1. Bölümü

Kripto para piyasasını, yüzlerce borsada her saniye binlerce fiyatın değiştiği, canlı nefes alan bir organizma olarak hayal edin. Bu kargaşada, geçici fiyat tutarsızlıkları ortaya çıkar — "verimsizlikler" — ve bunlar risksiz kâr elde etmeye olanak tanır. Buna arbitraj denir. Ancak basit iki adımlı takaslardan söz etmiyoruz. BTC'den ETH'e, ardından SOL'a, ardından USDT'ye ve nihayet BTC'ye geri dönerek kâr bulunabilen karmaşık çok varlıklı zincirlere dalıyoruz.

Gerçek zamanlı olarak milyonlarca olasılık arasından bu zincirleri nasıl buluruz? Yanıt Graf Teorisi'nde yatmaktadır.

Bu makalede, maksimum performans için her şeyi Rust'ta uygulayarak klasik algoritmalardan son teknoloji akademik araştırmalara uzanan yolu kat edeceğiz.

Bir arbitraj grafının yüksek teknolojili görselleştirmesi: düğümler varlıkları, kenarlar ise işlem çiftlerini temsil eder. Vurgulanan döngü, tespit edilmiş kârlı bir fırsatı simgeler.

1. Piyasa Bir Graf Olarak

Graf algoritmalarını uygulamak için önce piyasayı doğru biçimde temsil etmemiz gerekir.

1.1 Köşeler ve Kenarlar

• Köşeler (Düğümler): Varlıklar (BTC, ETH, USDT vb.).
• Kenarlar (Bağlantılar): İşlem çiftleri (BTC/USDT, ETH/BTC).
• Ağırlıklar: Döviz kuru.

$i$ varlığının 1 birimi için $j$ varlığından ne kadar aldığımızı gösteren $R(i, j)$ kurunu ele aldığımızda, bir döngünün $(i_1, i_2, \dots, i_k, i_1)$ arbitraj fırsatı sunması için şu koşulun sağlanması gerekir: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Çarpımdan Toplamaya

Bilgisayarlar toplamayı çarpmaya kıyasla çok daha hızlı yapar ve çoğu en kısa yol algoritması toplamlar için tasarlanmıştır. Basit bir matematiksel hile kullanıyoruz: logaritma. $\ln(a \times b) = \ln(a) + \ln(b)$ olduğundan, koşul şu hale gelir: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Ya da işareti çevirerek bir negatif döngü bulmak için: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Artık her kenarın ağırlığı $w = -\ln(R)$'dir. Görevimiz, negatif toplam ağırlığa sahip bir döngü bulmaktır.

2. Klasik Yaklaşım: Bellman-Ford

Bellman-Ford algoritması, arbitraj tespitinin "Merhaba Dünya"sıdır. En kısa yolları bulmak için tasarlanmıştır ve doğası gereği negatif döngüleri tespit edebilir.

2.1 Rust'ta Algoritma

petgraph crate'ini kullanarak bunu verimli biçimde uygulayabiliriz:

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, mesafeleri döndürür ya da negatif döngü bulunursa hata verir
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // Negatif döngü yok
        Err(error) => {
            // Gerçek bir uygulamada döngüyü, hatadaki önceki düğüm haritasını
            // kullanarak yeniden oluştururduk
            println!("Arbitraj tespit edildi!");
            None 
        }
    }
}

2.2 Karmaşıklık ve Sınırlamalar

Bellman-Ford, $V$ varlık sayısı ve $E$ işlem çifti sayısı olmak üzere $O(V \times E)$ karmaşıklığında çalışır.

• Artılar: Döngü varsa bulmayı garanti eder.
• Eksiler: Varlık sayısı büyüdüğünde Yüksek Frekanslı İşlem (HFT) için çok yavaştır. Ayrıca aynı anda yalnızca bir döngü bulur.

3. SPFA: Daha Hızlı Bir Alternatif

Shortest Path Faster Algorithm (SPFA), gereksiz hesaplamalardan kaçınmak için kuyruk kullanan, Bellman-Ford'un optimize edilmiş bir sürümüdür.

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; // Negatif döngü tespit edildi
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

Uygulamada SPFA genellikle $O(k \times E)$ ($k \ll V$) karmaşıklığında çalışır; bu da onu seyrek piyasa grafları için çok daha hızlı kılar.

4. Modern Araştırma: RICH Algoritması

2024 yılında araştırmacılar RICH (Rapid Identification of Cyclic High-profitability) algoritmasını önerdi. Bellman-Ford'un aksine RICH, şu özelliklere sahip finansal graflar için özel olarak optimize edilmiştir:

1. Graf küçük ile orta büyüklüktedir (yüzlerce varlık).
2. Ağırlıklar her milisaniyede değişir.
3. Yalnızca herhangi bir döngüyü değil, en kârlı döngüyü bulmamız gerekir.

4.1 RICH'in Temel Yenilikleri

• Budama: Mevcut en iyi bilinen yola dayanarak kârlı bir döngüye kesinlikle yol açamayacak yolları anında eler.
• Katmanlı Arama: Bitmask optimizasyonlarını kullanarak artan uzunluktaki döngüleri (3 bacaklı, 4 bacaklı, 5 bacaklı) arar.
• Artımlı Güncellemeler: Algoritmayı baştan çalıştırmak yerine yalnızca fiyat değişikliğinden etkilenen grafın bölümlerini günceller.

5. Uygulama Zorlukları: Ücretler ve Likidite

Gerçek işlemler ücretsiz değildir. $(A \to B \to C \to A)$ çok bacaklı bir döngü, üç ayrı işlem ücreti doğurur.

5.1 Ücretlerin Dahil Edilmesi

Kenar ağırlıklarımızı ayarlamamız gerekir: $w = -\ln(R \times (1 - \text{fee}))$ Bu, birçok teorik döngü yürütme maliyetiyle elendiğinden grafı önemli ölçüde budlar.

5.2 Likidite ve Kayma

Bir varlığı daha fazla satın aldıkça fiyat artar (kayma). 100 dolarda kârlı görünen bir döngü, 10.000 dolarda zarar verebilir. Gelişmiş graf modelleri, $w$'nin hacim $V$'nin bir fonksiyonu olduğu parametrik ağırlıklar kullanır. Bu, problemi basit bir en kısa yol aramasından graf üzerinde bir Konveks Optimizasyon problemine dönüştürür.

6. Neden Rust?

Arbitraj dünyasında 100 mikrosaniye, kâr ile "kaçırılmış" bir fırsat arasındaki farktır.

• Bellek Güvenliği: Botu kritik bir anda dondurabilecek çöp toplayıcı (GC) duraklaması yoktur.
• Sıfır Maliyetli Soyutlamalar: Ham işaretçilerin performansını kaybetmeden yüksek düzeyli graf yapıları kullanabiliriz.
• Eş Zamanlılık: Rust'ın "Korkusuz Eş Zamanlılığı", 10 borsadan WebSocket akışlarını paralel olarak ayrıştırmamıza ve paylaşılan grafı güvenli biçimde güncellememize olanak tanır.

Sonuç

Graf algoritmaları, modern kripto arbitrajının motorudur. Bellman-Ford temeli sağlarken modern sistemler SPFA gibi optimize edilmiş varyantları ya da RICH gibi özelleştirilmiş algoritmaları kullanır.

Bu serinin bir sonraki bölümünde, grafımızı basit varlık takaslarından fonlama oranlarını ve taşıma ticareti stratejilerini kapsayacak şekilde genişlettiğimiz Vadeli İşlem-Spot Arbitrajına bakacağız.

Düşük gecikmeli işlem sistemleri mi oluşturuyorsunuz? Açık Kaynaklı Rust HFT Şablonumuza göz atın.