อัลกอริทึมกราฟสำหรับการตรวจจับอาร์บิทราจ: จาก Bellman-Ford สู่ RICH

ตอนที่ 1 ของซีรีส์ "ห่วงโซ่อาร์บิทราจที่ซับซ้อนระหว่างสัญญาซื้อขายล่วงหน้าและสปอต"

ลองจินตนาการถึงตลาดคริปโตเคอร์เรนซีในฐานะสิ่งมีชีวิตที่หายใจและเต้นชีพจรอยู่ตลอดเวลา โดยราคาหลายพันรายการเปลี่ยนแปลงทุกวินาทีบนร้อยกว่าการแลกเปลี่ยน ในความวุ่นวายนี้ ความไม่สอดคล้องกันของราคาชั่วคราวเกิดขึ้น ซึ่งเรียกว่า "ความไม่มีประสิทธิภาพ" ที่เปิดโอกาสให้ทำกำไรได้โดยไม่มีความเสี่ยง นี่คืออาร์บิทราจ แต่เราไม่ได้พูดถึงการแลกเปลี่ยนแบบสองขั้นตอนง่าย ๆ เรากำลังดำดิ่งลงสู่ห่วงโซ่หลายสินทรัพย์ที่ซับซ้อน ซึ่งอาจพบกำไรได้ก็ต่อเมื่อกระโดดจาก BTC ไป ETH แล้วไป SOL แล้วไป USDT และกลับมาที่ BTC

เราจะหาห่วงโซ่เหล่านี้ท่ามกลางความเป็นไปได้นับล้านแบบในเวลาจริงได้อย่างไร คำตอบอยู่ที่ทฤษฎีกราฟ

ในบทความนี้ เราจะเดินทางจากอัลกอริทึมคลาสสิกสู่งานวิจัยระดับแนวหน้า โดยนำไปใช้งานใน Rust เพื่อประสิทธิภาพสูงสุด

การแสดงภาพกราฟอาร์บิทราจระดับไฮเทค: โหนดแทนสินทรัพย์ และเส้นเชื่อมแทนคู่การซื้อขาย วงจรที่ถูกเน้นแสดงโอกาสที่ทำกำไรได้ซึ่งตรวจพบแล้ว

1. ตลาดในรูปแบบกราฟ

เพื่อนำอัลกอริทึมกราฟมาใช้ เราต้องแสดงตลาดในรูปแบบที่ถูกต้องก่อน

1.1 จุดยอดและเส้นเชื่อม

• จุดยอด (โหนด): สินทรัพย์ (BTC, ETH, USDT เป็นต้น)
• เส้นเชื่อม (ลิงก์): คู่การซื้อขาย (BTC/USDT, ETH/BTC)
• น้ำหนัก: อัตราแลกเปลี่ยน

ถ้าเรามีอัตรา $R(i, j)$ (จำนวนของสินทรัพย์ $j$ ที่เราได้รับต่อ 1 หน่วยของสินทรัพย์ $i$) โอกาสอาร์บิทราจจะเกิดขึ้นหากวงจร $(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. แนวทางคลาสสิก: Bellman-Ford

อัลกอริทึม Bellman-Ford คือ "Hello World" ของการตรวจจับอาร์บิทราจ ออกแบบมาเพื่อหาเส้นทางสั้นที่สุดและสามารถตรวจจับวงจรลบได้โดยธรรมชาติ

2.1 อัลกอริทึมใน Rust

โดยใช้ crate 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 ความซับซ้อนและข้อจำกัด

Bellman-Ford ทำงานใน $O(V \times E)$ โดยที่ $V$ คือจำนวนสินทรัพย์และ $E$ คือจำนวนคู่การซื้อขาย

• ข้อดี: รับประกันว่าจะพบวงจรหากมีอยู่
• ข้อเสีย: ช้าเกินไปสำหรับการซื้อขายความถี่สูง (HFT) เมื่อจำนวนสินทรัพย์เพิ่มขึ้น นอกจากนี้ยังพบได้ครั้งละ หนึ่ง วงจรเท่านั้น

3. SPFA: ทางเลือกที่เร็วกว่า

Shortest Path Faster Algorithm (SPFA) คือเวอร์ชันที่ปรับปรุงของ Bellman-Ford ที่ใช้คิวเพื่อหลีกเลี่ยงการคำนวณซ้ำที่ไม่จำเป็น

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) ซึ่งต่างจาก Bellman-Ford ตรงที่ RICH ได้รับการปรับแต่งโดยเฉพาะสำหรับกราฟทางการเงินที่:

1. กราฟมีขนาดเล็กถึงกลาง (สินทรัพย์หลายร้อยรายการ)
2. น้ำหนักเปลี่ยนแปลงทุกมิลลิวินาที
3. เราต้องการหาวงจรที่ทำกำไรได้ มากที่สุด ไม่ใช่แค่ วงจรใดก็ได้

4.1 นวัตกรรมสำคัญของ RICH

• การตัดทอน: ทิ้งเส้นทางที่ไม่มีทางนำไปสู่วงจรที่ทำกำไรได้ทันที โดยอิงจากเส้นทางที่ดีที่สุดที่รู้จักในปัจจุบัน
• การค้นหาแบบเป็นชั้น: ค้นหาวงจรที่มีความยาวเพิ่มขึ้น (3 ขา, 4 ขา, 5 ขา) โดยใช้การปรับแต่ง bitmask
• การอัปเดตแบบเพิ่มทีละน้อย: แทนที่จะรันอัลกอริทึมเต็มรูปแบบใหม่ จะอัปเดตเฉพาะส่วนของกราฟที่ได้รับผลกระทบจากการเปลี่ยนแปลงราคา

5. ความท้าทายในการนำไปใช้งาน: ค่าธรรมเนียมและสภาพคล่อง

การซื้อขายจริงไม่ฟรี วงจรหลายขา $(A \to B \to C \to A)$ มีค่าธรรมเนียมการซื้อขายแยกกันสามรายการ

5.1 การรวมค่าธรรมเนียม

เราต้องปรับน้ำหนักเส้นเชื่อม: $w = -\ln(R \times (1 - \text{fee}))$ สิ่งนี้ตัดทอนกราฟอย่างมีนัยสำคัญ เนื่องจากวงจรเชิงทฤษฎีจำนวนมากถูกทำลายโดยต้นทุนการดำเนินการ

5.2 สภาพคล่องและสลิปเพจ

เมื่อคุณซื้อสินทรัพย์มากขึ้น ราคาจะสูงขึ้น (สลิปเพจ) วงจรที่ดูเหมือนทำกำไรได้สำหรับ $100 อาจขาดทุนสำหรับ$10,000 โมเดลกราฟขั้นสูงใช้ น้ำหนักพาราเมตริก โดยที่ $w$ เป็นฟังก์ชันของปริมาณ $V$ ซึ่งเปลี่ยนปัญหาจากการค้นหาเส้นทางสั้นที่สุดแบบง่ายเป็นปัญหา การปรับแต่งนูน บนกราฟ

6. ทำไมต้อง Rust?

ในโลกของอาร์บิทราจ 100 ไมโครวินาทีคือความแตกต่างระหว่างกำไรกับโอกาสที่ "หลุดมือ"

• ความปลอดภัยของหน่วยความจำ: ไม่มีการหยุดชะงักจากตัวเก็บขยะ (GC) ที่อาจทำให้บอทหยุดทำงานในช่วงเวลาสำคัญ
• การแยกส่วนที่ไม่มีต้นทุน: เราสามารถใช้โครงสร้างกราฟระดับสูงโดยไม่สูญเสียประสิทธิภาพของพอยน์เตอร์ดิบ
• การทำงานพร้อมกัน: "Fearless Concurrency" ของ Rust ช่วยให้เราสามารถแยกวิเคราะห์ฟีด WebSocket จาก 10 การแลกเปลี่ยนพร้อมกันและอัปเดตกราฟที่แชร์ร่วมกันได้อย่างปลอดภัย

บทสรุป

อัลกอริทึมกราฟคือเครื่องยนต์ที่ขับเคลื่อนอาร์บิทราจคริปโตสมัยใหม่ ในขณะที่ Bellman-Ford เป็นรากฐาน ระบบสมัยใหม่ใช้เวอร์ชันที่ปรับแต่งแล้วอย่าง SPFA หรืออัลกอริทึมเฉพาะทางอย่าง RICH

ในตอนถัดไปของซีรีส์นี้ เราจะดูที่ อาร์บิทราจสัญญาซื้อขายล่วงหน้า-สปอต ซึ่งเราขยายกราฟจากการแลกเปลี่ยนสินทรัพย์แบบธรรมดาให้รวมถึงอัตราเงินทุนและกลยุทธ์ cash-and-carry

คุณกำลังสร้างระบบการซื้อขายเวลาแฝงต่ำอยู่ใช่ไหม? ดู Open Source Rust HFT Template ของเรา