Algoritma Graf untuk Deteksi Arbitrase: Dari Bellman-Ford hingga RICH

Bagian 1 dari seri "Rantai Arbitrase Kompleks antara Futures dan Spot"

Bayangkan pasar cryptocurrency sebagai organisme hidup yang bernapas, di mana ribuan harga berubah setiap detik di ratusan bursa. Dalam kekacauan ini, perbedaan harga sementara muncul—"inefisiensi"—yang memungkinkan perolehan keuntungan tanpa risiko. Inilah arbitrase. Namun kita tidak berbicara tentang pertukaran dua langkah sederhana. Kita menyelami rantai multi-aset yang kompleks, di mana keuntungan mungkin hanya ditemukan dengan berpindah dari BTC ke ETH, lalu ke SOL, lalu ke USDT, dan akhirnya kembali ke BTC.

Bagaimana cara menemukan rantai-rantai ini di antara jutaan kemungkinan secara real-time? Jawabannya terletak pada Teori Graf.

Dalam artikel ini, kita akan menelusuri jalan dari algoritma klasik hingga penelitian akademis mutakhir, dengan mengimplementasikan semuanya dalam Rust untuk performa maksimal.

Visualisasi berteknologi tinggi dari graf arbitrase: node mewakili aset, dan edge mewakili pasangan perdagangan. Siklus yang disorot mewakili peluang menguntungkan yang terdeteksi.

1. Pasar sebagai Graf

Untuk menerapkan algoritma graf, kita harus terlebih dahulu merepresentasikan pasar dengan benar.

1.1 Simpul dan Sisi

• Simpul (Node): Aset (BTC, ETH, USDT, dll.).
• Sisi (Edge): Pasangan perdagangan (BTC/USDT, ETH/BTC).
• Bobot: Nilai tukar.

Jika kita memiliki nilai tukar $R(i, j)$ (berapa banyak aset $j$ yang kita dapatkan untuk 1 unit aset $i$), peluang arbitrase ada jika siklus $(i_1, i_2, \dots, i_k, i_1)$ menghasilkan: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Dari Perkalian ke Penjumlahan

Komputer jauh lebih cepat dalam penjumlahan daripada perkalian, dan sebagian besar algoritma jalur terpendek dirancang untuk penjumlahan. Kita menggunakan trik matematika sederhana: logaritma. Karena $\ln(a \times b) = \ln(a) + \ln(b)$, kondisinya menjadi: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Atau, dengan membalik tanda untuk menemukan siklus negatif: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Kini, setiap sisi memiliki bobot $w = -\ln(R)$. Tugas kita adalah menemukan siklus dengan total bobot negatif.

2. Pendekatan Klasik: Bellman-Ford

Algoritma Bellman-Ford adalah "Hello World"-nya deteksi arbitrase. Algoritma ini dirancang untuk menemukan jalur terpendek dan secara alami dapat mendeteksi siklus negatif.

2.1 Algoritma dalam Rust

Menggunakan crate petgraph, kita dapat mengimplementasikannya secara efisien:

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 mengembalikan jarak atau error jika siklus negatif ditemukan
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // Tidak ada siklus negatif
        Err(error) => {
            // Dalam implementasi nyata, kita akan merekonstruksi siklus 
            // menggunakan peta pendahulu dari error
            println!("Arbitrase terdeteksi!");
            None 
        }
    }
}

2.2 Kompleksitas dan Keterbatasan

Bellman-Ford berjalan dalam $O(V \times E)$, di mana $V$ adalah jumlah aset dan $E$ adalah jumlah pasangan perdagangan.

• Kelebihan: Menjamin ditemukannya siklus jika ada.
• Kekurangan: Terlalu lambat untuk High-Frequency Trading (HFT) ketika jumlah aset bertambah. Selain itu, hanya menemukan satu siklus dalam satu waktu.

3. SPFA: Alternatif yang Lebih Cepat

Shortest Path Faster Algorithm (SPFA) adalah versi Bellman-Ford yang dioptimalkan yang menggunakan antrean untuk menghindari perhitungan berulang.

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; // Siklus negatif terdeteksi
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

Dalam praktiknya, SPFA sering berjalan dalam $O(k \times E)$ di mana $k \ll V$, membuatnya jauh lebih cepat untuk graf pasar yang jarang.

4. Penelitian Modern: Algoritma RICH

Pada tahun 2024, para peneliti mengusulkan algoritma RICH (Rapid Identification of Cyclic High-profitability). Berbeda dengan Bellman-Ford, RICH dioptimalkan khusus untuk graf keuangan di mana:

1. Graf berukuran kecil hingga menengah (ratusan aset).
2. Bobot berubah setiap milidetik.
3. Kita perlu menemukan siklus yang paling menguntungkan, bukan hanya siklus mana saja.

4.1 Inovasi Utama RICH

• Pemangkasan (Pruning): Langsung membuang jalur yang tidak mungkin menghasilkan siklus menguntungkan berdasarkan jalur terbaik yang diketahui saat ini.
• Pencarian Berlapis: Mencari siklus dengan panjang yang semakin bertambah (3-kaki, 4-kaki, 5-kaki) menggunakan optimisasi bitmask.
• Pembaruan Inkremental: Alih-alih menjalankan ulang algoritma penuh, hanya memperbarui bagian graf yang terpengaruh oleh perubahan harga.

5. Tantangan Implementasi: Biaya dan Likuiditas

Perdagangan nyata tidak gratis. Siklus multi-kaki $(A \to B \to C \to A)$ dikenakan tiga biaya perdagangan terpisah.

5.1 Memasukkan Biaya

Kita harus menyesuaikan bobot sisi kita: $w = -\ln(R \times (1 - \text{fee}))$ Hal ini secara signifikan memangkas graf, karena banyak siklus teoretis tereliminasi oleh biaya eksekusi.

5.2 Likuiditas dan Slippage

Saat Anda membeli lebih banyak suatu aset, harga naik (slippage). Siklus yang tampak menguntungkan untuk $100 mungkin menjadi kerugian untuk$10.000. Model graf tingkat lanjut menggunakan bobot parametrik, di mana $w$ adalah fungsi dari volume $V$. Hal ini mengubah masalah dari pencarian jalur terpendek sederhana menjadi masalah Optimisasi Konveks pada graf.

6. Mengapa Rust?

Dalam dunia arbitrase, 100 mikrodetik adalah perbedaan antara keuntungan dan peluang yang "terlewat".

• Keamanan Memori: Tidak ada jeda pengumpul sampah (GC) yang dapat membekukan bot pada momen kritis.
• Abstraksi Tanpa Biaya: Kita dapat menggunakan struktur graf tingkat tinggi tanpa kehilangan performa raw pointer.
• Konkurensi: "Fearless Concurrency" Rust memungkinkan kita mengurai umpan WebSocket dari 10 bursa secara paralel dan memperbarui graf bersama dengan aman.

Kesimpulan

Algoritma graf adalah mesin di balik arbitrase kripto modern. Sementara Bellman-Ford memberikan fondasi, sistem modern menggunakan varian yang dioptimalkan seperti SPFA atau algoritma khusus seperti RICH.

Di bagian berikutnya dari seri ini, kita akan melihat Arbitrase Futures-Spot, di mana kita memperluas graf kita dari pertukaran aset sederhana untuk mencakup funding rate dan strategi cash-and-carry.

Apakah Anda membangun sistem perdagangan latensi rendah? Lihat Template Rust HFT Open Source kami.