Thuật Toán Đồ Thị Để Phát Hiện Arbitrage: Từ Bellman-Ford Đến RICH

Phần 1 của chuỗi "Chuỗi Arbitrage Phức Tạp Giữa Hợp Đồng Tương Lai và Thị Trường Giao Ngay"

Hãy tưởng tượng thị trường tiền điện tử như một sinh vật sống và thở, nơi hàng nghìn mức giá thay đổi mỗi giây trên hàng trăm sàn giao dịch. Trong sự hỗn loạn này, xuất hiện những chênh lệch giá tạm thời — "sự kém hiệu quả" — cho phép kiếm lợi nhuận không có rủi ro. Đó chính là arbitrage. Nhưng chúng ta không nói về các hoán đổi hai bước đơn giản. Chúng ta đang đi sâu vào các chuỗi đa tài sản phức tạp, nơi lợi nhuận chỉ có thể được tìm thấy bằng cách nhảy từ BTC sang ETH, rồi sang SOL, rồi sang USDT, và cuối cùng quay lại BTC.

Làm thế nào để chúng ta tìm những chuỗi này trong hàng triệu khả năng theo thời gian thực? Câu trả lời nằm ở Lý Thuyết Đồ Thị.

Trong bài viết này, chúng ta sẽ đi từ các thuật toán cổ điển đến nghiên cứu học thuật tiên tiến nhất, triển khai mọi thứ bằng Rust để đạt hiệu suất tối đa.

Trực quan hóa công nghệ cao của đồ thị arbitrage: các nút đại diện cho tài sản, và các cạnh đại diện cho các cặp giao dịch. Một vòng được làm nổi bật đại diện cho một cơ hội sinh lời đã được phát hiện.

1. Thị Trường Như Một Đồ Thị

Để áp dụng các thuật toán đồ thị, trước tiên chúng ta phải biểu diễn thị trường một cách chính xác.

1.1 Đỉnh và Cạnh

• Đỉnh (Nút): Tài sản (BTC, ETH, USDT, v.v.).
• Cạnh (Liên kết): Cặp giao dịch (BTC/USDT, ETH/BTC).
• Trọng số: Tỷ giá hối đoái.

Nếu chúng ta có tỷ giá $R(i, j)$ (bao nhiêu tài sản $j$ chúng ta nhận được cho 1 đơn vị tài sản $i$), cơ hội arbitrage tồn tại nếu một vòng $(i_1, i_2, \dots, i_k, i_1)$ tạo ra: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Từ Nhân Sang Cộng

Máy tính cộng nhanh hơn nhiều so với nhân, và hầu hết các thuật toán đường đi ngắn nhất được thiết kế cho phép tính tổng. Chúng ta sử dụng một mẹo toán học đơn giản: logarithm. Vì $\ln(a \times b) = \ln(a) + \ln(b)$, điều kiện trở thành: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Hoặc, bằng cách đảo dấu để tìm vòng âm: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Bây giờ, mỗi cạnh có trọng số $w = -\ln(R)$. Nhiệm vụ của chúng ta là tìm một vòng có tổng trọng số âm.

2. Phương Pháp Cổ Điển: Bellman-Ford

Thuật toán Bellman-Ford là "Hello World" của việc phát hiện arbitrage. Nó được thiết kế để tìm đường đi ngắn nhất và có thể tự nhiên phát hiện các vòng âm.

2.1 Thuật Toán Trong Rust

Sử dụng crate petgraph, chúng ta có thể triển khai điều này một cách hiệu quả:

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 Độ Phức Tạp và Hạn Chế

Bellman-Ford chạy trong $O(V \times E)$, trong đó $V$ là số lượng tài sản và $E$ là số lượng cặp giao dịch.

• Ưu điểm: Đảm bảo tìm thấy vòng nếu nó tồn tại.
• Nhược điểm: Quá chậm cho Giao Dịch Tần Số Cao (HFT) khi số lượng tài sản tăng lên. Nó cũng chỉ tìm được một vòng tại một thời điểm.

3. SPFA: Giải Pháp Thay Thế Nhanh Hơn

Thuật toán Đường Đi Ngắn Nhất Nhanh Hơn (SPFA) là phiên bản tối ưu hóa của Bellman-Ford sử dụng hàng đợi để tránh các tính toán dư thừa.

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
}

Trong thực tế, SPFA thường chạy trong $O(k \times E)$ trong đó $k \ll V$, làm cho nó nhanh hơn nhiều đối với các đồ thị thị trường thưa.

4. Nghiên Cứu Hiện Đại: Thuật Toán RICH

Vào năm 2024, các nhà nghiên cứu đề xuất thuật toán RICH (Rapid Identification of Cyclic High-profitability). Không giống như Bellman-Ford, RICH được tối ưu hóa đặc biệt cho các đồ thị tài chính nơi:

1. Đồ thị có quy mô nhỏ đến trung bình (hàng trăm tài sản).
2. Trọng số thay đổi mỗi mili-giây.
3. Chúng ta cần tìm vòng có lợi nhất, không chỉ bất kỳ vòng nào.

4.1 Những Đổi Mới Chính của RICH

• Cắt tỉa: Nó ngay lập tức loại bỏ các đường dẫn không thể dẫn đến một vòng sinh lời dựa trên đường dẫn tốt nhất hiện tại đã biết.
• Tìm kiếm Theo Lớp: Nó tìm kiếm các vòng có độ dài tăng dần (3 nhánh, 4 nhánh, 5 nhánh) sử dụng tối ưu hóa bitmask.
• Cập Nhật Gia Tăng: Thay vì chạy lại toàn bộ thuật toán, nó chỉ cập nhật các phần của đồ thị bị ảnh hưởng bởi sự thay đổi giá.

5. Thách Thức Triển Khai: Phí và Thanh Khoản

Giao dịch thực tế không miễn phí. Một vòng đa nhánh $(A \to B \to C \to A)$ phát sinh ba khoản phí giao dịch riêng biệt.

5.1 Tích Hợp Phí

Chúng ta phải điều chỉnh trọng số cạnh của mình: $w = -\ln(R \times (1 - \text{fee}))$ Điều này cắt tỉa đáng kể đồ thị, vì nhiều vòng lý thuyết bị loại bỏ bởi chi phí thực thi.

5.2 Thanh Khoản và Trượt Giá

Khi bạn mua nhiều tài sản hơn, giá tăng lên (trượt giá). Một vòng trông có lợi với $100 có thể là thua lỗ với$10,000. Các mô hình đồ thị nâng cao sử dụng trọng số tham số, trong đó $w$ là hàm của khối lượng $V$. Điều này biến bài toán từ tìm kiếm đường đi ngắn nhất đơn giản thành bài toán Tối Ưu Hóa Lồi trên đồ thị.

6. Tại Sao Dùng Rust?

Trong thế giới arbitrage, 100 micro-giây là sự khác biệt giữa lợi nhuận và một cơ hội bị "bỏ lỡ".

• An Toàn Bộ Nhớ: Không có khoảng dừng trình thu gom rác (GC) có thể làm đông bot vào thời điểm quan trọng.
• Trừu Tượng Hóa Không Chi Phí: Chúng ta có thể sử dụng các cấu trúc đồ thị cấp cao mà không mất hiệu suất của con trỏ thô.
• Đồng Thời: "Fearless Concurrency" của Rust cho phép chúng ta phân tích cú pháp các luồng WebSocket từ 10 sàn giao dịch song song và cập nhật đồ thị dùng chung một cách an toàn.

Kết Luận

Các thuật toán đồ thị là động cơ đằng sau arbitrage tiền điện tử hiện đại. Trong khi Bellman-Ford cung cấp nền tảng, các hệ thống hiện đại sử dụng các biến thể tối ưu hóa như SPFA hoặc các thuật toán chuyên biệt như RICH.

Trong phần tiếp theo của chuỗi bài này, chúng ta sẽ xem xét Arbitrage Hợp Đồng Tương Lai-Giao Ngay, nơi chúng ta mở rộng đồ thị từ các hoán đổi tài sản đơn giản để bao gồm tỷ lệ tài trợ và các chiến lược cash-and-carry.

Bạn đang xây dựng các hệ thống giao dịch độ trễ thấp? Hãy xem Open Source Rust HFT Template của chúng tôi.