आर्बिट्राज पहचान के लिए ग्राफ एल्गोरिदम: बेलमैन-फोर्ड से 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 गुणा से जोड़ की ओर

कंप्यूटर गुणा करने की तुलना में जोड़ने में कहीं अधिक तेज़ होते हैं, और अधिकांश शॉर्टेस्ट-पाथ एल्गोरिदम योगों के लिए डिज़ाइन किए गए हैं। हम एक सरल गणितीय तरकीब का उपयोग करते हैं: लघुगणक (logarithm)। चूंकि $\ln(a \times b) = \ln(a) + \ln(b)$, यह शर्त बन जाती है: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ या, नकारात्मक चक्र (negative cycle) खोजने के लिए चिह्न को पलटकर: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

अब, हर एज का वेट $w = -\ln(R)$ होता है। हमारा कार्य नकारात्मक कुल वेट वाला एक चक्र खोजना है।

2. शास्त्रीय दृष्टिकोण: बेलमैन-फोर्ड

बेलमैन-फोर्ड एल्गोरिदम आर्बिट्राज पहचान का "हैलो वर्ल्ड" है। इसे शॉर्टेस्ट पाथ खोजने के लिए डिज़ाइन किया गया है और यह स्वाभाविक रूप से नकारात्मक चक्रों का पता लगा सकता है।

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: एक तेज़ विकल्प

शॉर्टेस्ट पाथ फास्टर एल्गोरिदम (SPFA) बेलमैन-फोर्ड का एक अनुकूलित संस्करण है जो अनावश्यक गणनाओं से बचने के लिए एक क्यू (queue) का उपयोग करता है।

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$ होता है, जिससे यह विरल (sparse) बाजार ग्राफ के लिए काफी तेज़ हो जाता है।

4. आधुनिक शोध: RICH एल्गोरिदम

2024 में, शोधकर्ताओं ने RICH (Rapid Identification of Cyclic High-profitability) एल्गोरिदम प्रस्तावित किया। बेलमैन-फोर्ड के विपरीत, RICH विशेष रूप से वित्तीय ग्राफ के लिए अनुकूलित है जहां:

1. ग्राफ छोटे से मध्यम आकार का है (सैकड़ों एसेट्स)।
2. वेट हर मिलीसेकंड बदलते हैं।
3. हमें सबसे लाभदायक चक्र खोजना है, न कि केवल कोई चक्र।

4.1 RICH की प्रमुख नवीनताएं

• प्रूनिंग: यह वर्तमान में ज्ञात सर्वश्रेष्ठ पथ के आधार पर उन पथों को तुरंत खारिज कर देता है जो किसी भी तरह से लाभदायक चक्र की ओर नहीं ले जा सकते।
• लेयर्ड सर्च: यह बिटमास्क अनुकूलन का उपयोग करते हुए बढ़ती लंबाई (3-चरण, 4-चरण, 5-चरण) के चक्रों की खोज करता है।
• वृद्धिशील अपडेट: पूरे एल्गोरिदम को फिर से चलाने के बजाय, यह केवल ग्राफ के उन हिस्सों को अपडेट करता है जो मूल्य परिवर्तन से प्रभावित होते हैं।

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) रुकावट नहीं, जो किसी महत्वपूर्ण क्षण पर बॉट को फ्रीज कर सकती है।
• ज़ीरो-कॉस्ट एब्स्ट्रैक्शन: हम रॉ पॉइंटर्स के प्रदर्शन को खोए बिना हाई-लेवल ग्राफ संरचनाओं का उपयोग कर सकते हैं।
• कंकरेंसी: Rust की "फियरलेस कंकरेंसी" हमें 10 एक्सचेंजों से WebSocket फीड को समानांतर में पार्स करने और साझा ग्राफ को सुरक्षित रूप से अपडेट करने की अनुमति देती है।

निष्कर्ष

ग्राफ एल्गोरिदम आधुनिक क्रिप्टो आर्बिट्राज के पीछे का इंजन हैं। जबकि बेलमैन-फोर्ड आधार प्रदान करता है, आधुनिक सिस्टम SPFA जैसे अनुकूलित वेरिएंट या RICH जैसे विशेष एल्गोरिदम का उपयोग करते हैं।

इस श्रृंखला के अगले भाग में, हम फ्यूचर्स-स्पॉट आर्बिट्राज को देखेंगे, जहां हम अपने ग्राफ को साधारण एसेट स्वैप से बढ़ाकर फंडिंग रेट्स और कैश-एंड-कैरी रणनीतियों को शामिल करेंगे।

क्या आप लो-लेटेंसी ट्रेडिंग सिस्टम बना रहे हैं? हमारे ओपन सोर्स Rust HFT टेम्पलेट को देखें।