Arbitrajni aniqlash uchun graf algoritmlari: Bellman-Forddan RICH gacha

"Fyuchers va spot o'rtasidagi murakkab arbitraj zanjirlari" turkumining 1-qismi

Kriptovalyuta bozorini yuzlab birjalarda har soniyada minglab narxlar o'zgarib turadigan tirik organizm sifatida tasavvur qiling. Ushbu tartibsizlikda vaqtinchalik narx tafovutlari — "samarasizliklar" — paydo bo'ladi, ular xavfsiz foyda olishga imkon beradi. Bu arbitrajdir. Ammo biz oddiy ikki bosqichli almashinuv haqida gapirmayapmiz. Biz murakkab ko'p aktivli zanjirlarga sho'ng'iyapmiz, bunda foyda faqat BTC dan ETH ga, keyin SOL ga, keyin USDT ga va nihoyat yana BTC ga sakrash orqaligina topilishi mumkin.

Real vaqt rejimida millionlab imkoniyatlar orasidan bu zanjirlarni qanday topamiz? Javob graf nazariyasida yotadi.

Ushbu maqolada biz klassik algoritmlardan tortib eng ilg'or ilmiy tadqiqotlargacha bo'lgan yo'lni bosib o'tamiz va maksimal unumdorlik uchun hammasini Rust tilida amalga oshiramiz.

Arbitraj grafining yuqori texnologik vizualizatsiyasi: tugunlar aktivlarni, qirralar esa savdo juftliklarini ifodalaydi. Ajratilgan sikl aniqlangan foydali imkoniyatni ko'rsatadi.

1. Bozor graf sifatida

Graf algoritmlarini qo'llash uchun avvalo bozorni to'g'ri tasvirlashimiz kerak.

1.1 Uchlar va qirralar

• Uchlar (tugunlar): Aktivlar (BTC, ETH, USDT va h.k.).
• Qirralar (bog'lanishlar): Savdo juftliklari (BTC/USDT, ETH/BTC).
• Og'irliklar: Ayirboshlash kursi.

Agar bizda $R(i, j)$ kursi bo'lsa ($i$ aktivining 1 birligiga $j$ aktividan qancha olamiz), $(i_1, i_2, \dots, i_k, i_1)$ sikli quyidagi natijani bersa, arbitraj imkoniyati mavjud bo'ladi: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Ko'paytirishdan qo'shishga o'tish

Kompyuterlar ko'paytirishdan ko'ra qo'shishda ancha tezroq ishlaydi, va eng qisqa yo'l algoritmlarining ko'pchiligi yig'indilar uchun mo'ljallangan. Biz oddiy matematik hiylani qo'llaymiz: logarifm. $\ln(a \times b) = \ln(a) + \ln(b)$ bo'lgani uchun, shart quyidagicha bo'ladi: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Yoki, manfiy siklni topish uchun belgini teskari o'girsak: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Endi har bir qirraning og'irligi $w = -\ln(R)$ bo'ladi. Bizning vazifamiz — umumiy og'irligi manfiy bo'lgan siklni topish.

2. Klassik yondashuv: Bellman-Ford

Bellman-Ford algoritmi arbitrajni aniqlashning "Hello World"idir. U eng qisqa yo'llarni topish uchun mo'ljallangan va tabiiy ravishda manfiy sikllarni aniqlay oladi.

2.1 Rust tilidagi algoritm

petgraph cratesidan foydalanib, buni samarali amalga oshirishimiz mumkin:

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 Murakkablik va cheklovlar

Bellman-Ford $O(V \times E)$ vaqtida ishlaydi, bunda $V$ — aktivlar soni, $E$ esa savdo juftliklari soni.

• Afzalliklari: Agar sikl mavjud bo'lsa, uni topishga kafolat beradi.
• Kamchiliklari: Aktivlar soni ortishi bilan yuqori chastotali savdo (HFT) uchun juda sekin. Shuningdek, u bir vaqtning o'zida faqat bitta siklni topadi.

3. SPFA: tezroq alternativa

Shortest Path Faster Algorithm (SPFA) — ortiqcha hisob-kitoblardan qochish uchun navbatdan foydalanadigan Bellman-Ford algoritmining optimallashtirilgan versiyasi.

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
}

Amalda SPFA ko'pincha $O(k \times E)$ vaqtida ishlaydi, bunda $k \ll V$, bu uni siyrak bozor graflari uchun ancha tezroq qiladi.

4. Zamonaviy tadqiqot: RICH algoritmi

2024-yilda tadqiqotchilar RICH (Rapid Identification of Cyclic High-profitability) algoritmini taklif qilishdi. Bellman-Forddan farqli o'laroq, RICH quyidagi xususiyatlarga ega moliyaviy graflar uchun maxsus optimallashtirilgan:

1. Graf kichik yoki o'rta o'lchamda (yuzlab aktivlar).
2. Og'irliklar har millisekundda o'zgaradi.
3. Bizga har qanday emas, balki eng foydali siklni topish kerak.

4.1 RICH ning asosiy innovatsiyalari

• Kesish (Pruning): U hozirgi ma'lum bo'lgan eng yaxshi yo'lga asoslanib, foydali siklga hech qanday tarzda olib kela olmaydigan yo'llarni darhol rad etadi.
• Qatlamli qidiruv: U bitmask optimallashtirishlaridan foydalanib, uzunligi ortib boruvchi sikllarni (3, 4, 5 bosqichli) qidiradi.
• Bosqichma-bosqich yangilanishlar: To'liq algoritmni qayta ishga tushirish o'rniga, u faqat narx o'zgarishidan ta'sirlangan graf qismlarini yangilaydi.

5. Amalga oshirish qiyinchiliklari: komissiyalar va likvidlik

Haqiqiy savdo bepul emas. Ko'p bosqichli $(A \to B \to C \to A)$ sikli uchta alohida savdo komissiyasini keltirib chiqaradi.

5.1 Komissiyalarni hisobga olish

Biz qirra og'irliklarimizni sozlashimiz kerak: $w = -\ln(R \times (1 - \text{fee}))$ Bu grafni sezilarli darajada qisqartiradi, chunki ko'plab nazariy sikllar bajarish xarajati tufayli yo'q qilinadi.

5.2 Likvidlik va sirg'anish (slippage)

Aktivdan qancha ko'p sotib olsangiz, narx shuncha ko'tariladi (sirg'anish). $100 uchun foydali ko'rinadigan sikl$10,000 uchun zarar bo'lishi mumkin. Ilg'or graf modellari parametrik og'irliklardan foydalanadi, bunda $w$ hajm $V$ ning funksiyasidir. Bu muammoni oddiy eng qisqa yo'l qidiruvidan grafdagi qavariq optimallashtirish (convex optimization) muammosiga aylantiradi.

6. Nega Rust?

Arbitraj dunyosida 100 mikrosekund foyda va "qo'ldan boy berilgan" imkoniyat o'rtasidagi farqni belgilaydi.

• Xotira xavfsizligi: Botni muhim daqiqada muzlatib qo'yishi mumkin bo'lgan chiqindi yig'uvchi (GC) to'xtashlarining yo'qligi.
• Nol xarajatli abstraktsiyalar: Biz xom ko'rsatkichlar unumdorligini yo'qotmasdan yuqori darajadagi graf tuzilmalaridan foydalana olamiz.
• Parallellik: Rustning "Fearless Concurrency" xususiyati bizga 10 ta birjadan WebSocket oqimlarini parallel tahlil qilish va umumiy grafni xavfsiz yangilash imkonini beradi.

Xulosa

Graf algoritmlari zamonaviy kripto arbitrajining dvigateli hisoblanadi. Bellman-Ford poydevor yaratsa, zamonaviy tizimlar SPFA kabi optimallashtirilgan variantlardan yoki RICH kabi ixtisoslashtirilgan algoritmlardan foydalanadi.

Ushbu turkumning keyingi qismida biz fyuchers-spot arbitrajini ko'rib chiqamiz, unda grafimizni oddiy aktiv almashinuvidan fanding stavkalari va cash-and-carry strategiyalarini o'z ichiga oladigan tarzda kengaytiramiz.

Kam kechikuvchi savdo tizimlarini yaratyapsizmi? Bizning ochiq manbali Rust HFT shablonimizga nazar tashlang.