Graphalgorithmen zur Arbitrage-Erkennung: Von Bellman-Ford bis RICH

Teil 1 der Serie "Komplexe Arbitrageketten zwischen Futures und Spot"

Stellen Sie sich den Kryptowährungsmarkt als einen lebendigen Organismus vor, in dem sich jede Sekunde Tausende von Preisen über Hunderte von Börsen hinweg ändern. In diesem Chaos entstehen vorübergehende Preisdiskrepanzen – "Ineffizienzen" –, die risikofreien Gewinn ermöglichen. Das ist Arbitrage. Doch wir sprechen hier nicht von einfachen zweistufigen Swaps. Wir tauchen in komplexe Multi-Asset-Ketten ein, in denen ein Gewinn nur durch einen Sprung von BTC zu ETH, dann zu SOL, dann zu USDT und schließlich zurück zu BTC zu finden ist.

Wie finden wir diese Ketten unter Millionen von Möglichkeiten in Echtzeit? Die Antwort liegt in der Graphentheorie.

In diesem Artikel bewegen wir uns von klassischen Algorithmen bis hin zu modernster akademischer Forschung und implementieren alles in Rust für maximale Performance.

Eine High-Tech-Visualisierung eines Arbitrage-Graphen: Knoten repräsentieren Assets, Kanten repräsentieren Handelspaare. Ein hervorgehobener Zyklus stellt eine erkannte profitable Gelegenheit dar.

1. Der Markt als Graph

Um Graphalgorithmen anzuwenden, müssen wir den Markt zunächst korrekt darstellen.

1.1 Knoten und Kanten

• Knoten (Nodes): Assets (BTC, ETH, USDT usw.).
• Kanten (Links): Handelspaare (BTC/USDT, ETH/BTC).
• Gewichte: Der Wechselkurs.

Wenn wir einen Kurs $R(i, j)$ haben (wie viel von Asset $j$ wir für 1 Einheit von Asset $i$ erhalten), existiert eine Arbitragemöglichkeit, wenn ein Zyklus $(i_1, i_2, \dots, i_k, i_1)$ Folgendes ergibt: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Von der Multiplikation zur Addition

Computer sind beim Addieren wesentlich schneller als beim Multiplizieren, und die meisten Kürzeste-Wege-Algorithmen sind für Summen konzipiert. Wir nutzen einen einfachen mathematischen Trick: den Logarithmus. Da $\ln(a \times b) = \ln(a) + \ln(b)$, wird die Bedingung zu: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Oder, indem wir das Vorzeichen umkehren, um einen negativen Zyklus zu finden: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Nun hat jede Kante ein Gewicht $w = -\ln(R)$. Unsere Aufgabe besteht darin, einen Zyklus mit negativem Gesamtgewicht zu finden.

2. Klassischer Ansatz: Bellman-Ford

Der Bellman-Ford-Algorithmus ist das "Hello World" der Arbitrage-Erkennung. Er wurde entwickelt, um kürzeste Wege zu finden, und kann auf natürliche Weise negative Zyklen erkennen.

2.1 Der Algorithmus in Rust

Mit der petgraph-Crate können wir dies effizient implementieren:

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 Komplexität und Einschränkungen

Bellman-Ford läuft in $O(V \times E)$, wobei $V$ die Anzahl der Assets und $E$ die Anzahl der Handelspaare ist.

• Vorteile: Garantiert das Finden eines Zyklus, falls einer existiert.
• Nachteile: Zu langsam für High-Frequency Trading (HFT), wenn die Anzahl der Assets wächst. Er findet außerdem jeweils nur einen Zyklus.

3. SPFA: Eine schnellere Alternative

Der Shortest Path Faster Algorithm (SPFA) ist eine optimierte Version von Bellman-Ford, die eine Warteschlange verwendet, um redundante Berechnungen zu vermeiden.

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
}

In der Praxis läuft SPFA oft in $O(k \times E)$, wobei $k \ll V$, was ihn für dünn besetzte Marktgraphen deutlich schneller macht.

4. Moderne Forschung: Der RICH-Algorithmus

Im Jahr 2024 schlugen Forscher den RICH (Rapid Identification of Cyclic High-profitability)-Algorithmus vor. Im Gegensatz zu Bellman-Ford ist RICH speziell für finanzielle Graphen optimiert, bei denen:

1. Der Graph klein bis mittelgroß ist (Hunderte von Assets).
2. Sich die Gewichte jede Millisekunde ändern.
3. Wir den profitabelsten Zyklus finden müssen, nicht nur irgendeinen Zyklus.

4.1 Wichtige Innovationen von RICH

• Pruning: Er verwirft sofort Pfade, die auf Basis des aktuell besten bekannten Pfades unmöglich zu einem profitablen Zyklus führen können.
• Geschichtete Suche: Er sucht nach Zyklen zunehmender Länge (3-Beine, 4-Beine, 5-Beine) mithilfe von Bitmask-Optimierungen.
• Inkrementelle Updates: Anstatt den vollständigen Algorithmus erneut auszuführen, aktualisiert er nur die Teile des Graphen, die von einer Preisänderung betroffen sind.

5. Herausforderungen bei der Implementierung: Gebühren und Liquidität

Echter Handel ist nicht kostenlos. Ein mehrstufiger Zyklus $(A \to B \to C \to A)$ zieht drei separate Handelsgebühren nach sich.

5.1 Berücksichtigung von Gebühren

Wir müssen unsere Kantengewichte anpassen: $w = -\ln(R \times (1 - \text{fee}))$ Dies dünnt den Graphen erheblich aus, da viele theoretische Zyklen durch die Ausführungskosten zunichtegemacht werden.

5.2 Liquidität und Slippage

Je mehr eines Assets Sie kaufen, desto mehr steigt der Preis (Slippage). Ein Zyklus, der für 100 $profitabel aussieht, kann bei 10.000$ ein Verlust sein. Fortgeschrittene Graphmodelle verwenden parametrische Gewichte, bei denen $w$ eine Funktion des Volumens $V$ ist. Dies verwandelt das Problem von einer einfachen Kürzeste-Wege-Suche in ein Konvexes-Optimierungs-Problem auf einem Graphen.

6. Warum Rust?

In der Welt der Arbitrage entscheiden 100 Mikrosekunden über Gewinn oder eine "verpasste" Gelegenheit.

• Speichersicherheit: Keine Garbage-Collector-Pausen (GC), die den Bot in einem kritischen Moment einfrieren könnten.
• Zero-Cost-Abstraktionen: Wir können High-Level-Graphstrukturen nutzen, ohne die Performance von rohen Zeigern zu verlieren.
• Nebenläufigkeit: Rusts "Fearless Concurrency" ermöglicht es uns, WebSocket-Feeds von 10 Börsen parallel zu verarbeiten und den gemeinsamen Graphen sicher zu aktualisieren.

Fazit

Graphalgorithmen sind der Motor hinter moderner Krypto-Arbitrage. Während Bellman-Ford die Grundlage bildet, nutzen moderne Systeme optimierte Varianten wie SPFA oder spezialisierte Algorithmen wie RICH.

Im nächsten Teil dieser Serie befassen wir uns mit Futures-Spot-Arbitrage, bei der wir unseren Graphen von einfachen Asset-Swaps erweitern, um Funding Rates und Cash-and-Carry-Strategien einzubeziehen.

Entwickeln Sie latenzarme Handelssysteme? Schauen Sie sich unsere Open-Source-Rust-HFT-Vorlage an.