Арбитражды анықтауға арналған граф алгоритмдері: Беллман-Форддан 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 үлгісін қараңыз.