Арбитражды аныктоо үчүн граф алгоритмдери: Беллман-Форддон RICH чейин

"Фьючерстер менен спот ортосундагы татаал арбитраждык чынжырлар" сериясынын 1-бөлүгү

Криптовалюта рыногун жүздөгөн биржаларда ар секунд сайын миңдеген баа өзгөрүп турган тирүү организм катары элестетиңиз. Ушул хаоста тобокелсиз пайда табууга мүмкүнчүлүк берген убактылуу баа айырмачылыктары — "натыйжасыздыктар" — пайда болот. Бул — арбитраж. Бирок биз жөнөкөй эки кадамдуу алмашуу жөнүндө сүйлөбөй жатабыз. Биз пайданы 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. Классикалык мамиле: Беллман-Форд

Беллман-Форд алгоритми — арбитражды аныктоонун "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 Татаалдык жана чектөөлөр

Беллман-Форд $O(V \times E)$ убакытында иштейт, мында $V$ — активдердин саны, ал $E$ — соода жуптарынын саны.

• Артыкчылыктары: Эгер цикл бар болсо, аны табууга кепилдик берет.
• Кемчиликтери: Активдердин саны көбөйгөндө жогорку жыштыктагы соода (HFT) үчүн өтө жай. Ошондой эле ал бир учурда бир гана циклди табат.

3. SPFA: тезирээк альтернатива

Shortest Path Faster Algorithm (SPFA) — ашыкча эсептөөлөрдөн качуу үчүн кезекти колдонгон Беллман-Форд алгоритминин оптималдаштырылган версиясы.

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$, бул аны сейрек рынок графтары үчүн алда канча тезирээк кылат.

4. Заманбап изилдөө: RICH алгоритми

2024-жылы изилдөөчүлөр RICH (Rapid Identification of Cyclic High-profitability) алгоритмин сунушташты. Беллман-Форддон айырмаланып, RICH так молиялык графтар үчүн атайын оптималдаштырылган, мында:

1. Граф кичине же орто өлчөмдө (жүздөгөн активдер).
2. Салмактар ар миллисекунд сайын өзгөрөт.
3. Бизге каалаган цикл эмес, эң пайдалуу циклди табуу керек.

4.1 RICH алгоритминин негизги жаңылыктары

• Кыркуу (Pruning): Ал учурдагы белгилүү болгон эң жакшы жолго таянып, пайдалуу циклге эч кандай жол ала албай турган жолдорду дароо четке кагат.
• Катмардуу издөө: Ал биттик маска оптималдаштыруларын колдонуп, узундугу өсүп жаткан циклдерди (3, 4, 5 кадамдуу) издейт.
• Инкременталдык жаңылоолор: Толук алгоритмди кайра иштетүүнүн ордуна, ал баа өзгөрүшүнөн таасирленген графтын бөлүктөрүн гана жаңылайт.

5. Ишке ашыруу кыйынчылыктары: комиссиялар жана ликвиддүүлүк

Чыныгы соода бекер эмес. Көп кадамдуу $(A \to B \to C \to A)$ цикли үч өзүнчө соода комиссиясын алып келет.

5.1 Комиссияларды эске алуу

Биз чет салмактарын тууралашыбыз керек: $w = -\ln(R \times (1 - \text{fee}))$ Бул графты олуттуу түрдө кыркат, анткени көптөгөн теориялык циклдер аткаруу наркынан жок болот.

5.2 Ликвиддүүлүк жана сыдырылуу (slippage)

Активди канчалык көп сатып алсаңыз, баа ошончолук көтөрүлөт (сыдырылуу). $100 үчүн пайдалуу көрүнгөн цикл$10,000 үчүн чыгым болушу мүмкүн. Өнүккөн граф моделдери параметрдик салмактарды колдонушат, мында $w$ — көлөм $V$ функциясы. Бул маселени жөнөкөй эң кыска жол издөөдөн графтагы дөңес оптимизациялоо (convex optimization) маселесине айландырат.

6. Эмнеге Rust?

Арбитраж дүйнөсүндө 100 микросекунда пайда менен "өткөрүп жиберилген" мүмкүнчүлүктүн ортосундагы айырмачылыкты түзөт.

• Эс тутум коопсуздугу: Ботту маанилүү учурда токтото ала турган таштанды жыйноочунун (GC) тыныгуулары жок.
• Нөл баалуу абстракциялар: Биз чийки көрсөткүчтөрдүн өндүрүмдүүлүгүн жоготпостон, жогорку деңгээлдеги граф түзүлүштөрүн колдоно алабыз.
• Параллелдүүлүк: Rust-тун "Fearless Concurrency" касиети бизге 10 биржадан WebSocket агымдарын параллелдүү талдап, жалпы графты коопсуз жаңылоого мүмкүнчүлүк берет.

Жыйынтык

Граф алгоритмдери заманбап крипто арбитраждын кыймылдаткычы болуп саналат. Беллман-Форд негизди түзсө, заманбап системалар SPFA сыяктуу оптималдаштырылган варианттарды же RICH сыяктуу адистештирилген алгоритмдерди колдонушат.

Бул сериянын кийинки бөлүгүндө биз фьючерс-спот арбитражын карайбыз, мында графыбызды жөнөкөй актив алмашуудан фандинг чендерин жана cash-and-carry стратегияларын камтууга чейин кеңейтебиз.

Төмөн кечигүүчү соода системаларын түзүп жатасызбы? Биздин ачык булактуу Rust HFT үлгүсүн караңыз.