Graafalgoritmen voor arbitragedetectie: van Bellman-Ford tot RICH

Deel 1 van de serie "Complexe arbitrageketens tussen futures en spot"

Stel je de cryptocurrencymarkt voor als een levend, ademend organisme waarin elke seconde duizenden prijzen veranderen op honderden exchanges. In deze chaos ontstaan tijdelijke prijsverschillen—"inefficiënties"—die risicovrije winst mogelijk maken. Dit is arbitrage. Maar we hebben het niet over simpele swaps in twee stappen. We duiken in complexe multi-asset ketens waarbij winst alleen te vinden is door van BTC naar ETH te springen, dan naar SOL, dan naar USDT, en uiteindelijk weer terug naar BTC.

Hoe vinden we deze ketens tussen miljoenen mogelijkheden in real-time? Het antwoord ligt in de grafentheorie.

In dit artikel doorlopen we het pad van klassieke algoritmen naar baanbrekend academisch onderzoek, waarbij we alles implementeren in Rust voor maximale prestaties.

Een hightech visualisatie van een arbitragegraf: knopen vertegenwoordigen assets, en verbindingen vertegenwoordigen handelsparen. Een gemarkeerde cyclus vertegenwoordigt een gedetecteerde winstgevende kans.

1. De markt als graaf

Om graafalgoritmen toe te passen, moeten we de markt eerst correct representeren.

1.1 Knopen en verbindingen

• Knopen (nodes): Assets (BTC, ETH, USDT, enz.).
• Verbindingen (edges): Handelsparen (BTC/USDT, ETH/BTC).
• Gewichten: De wisselkoers.

Als we een koers $R(i, j)$ hebben (hoeveel van asset $j$ we krijgen voor 1 eenheid van asset $i$), bestaat er een arbitragemogelijkheid als een cyclus $(i_1, i_2, \dots, i_k, i_1)$ het volgende oplevert: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Van vermenigvuldigen naar optellen

Computers zijn veel sneller in optellen dan in vermenigvuldigen, en de meeste kortste-padalgoritmen zijn ontworpen voor sommen. We gebruiken een eenvoudige wiskundige truc: de logaritme. Aangezien $\ln(a \times b) = \ln(a) + \ln(b)$, wordt de voorwaarde: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Of, door het teken om te draaien om een negatieve cyclus te vinden: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Elke verbinding heeft nu een gewicht $w = -\ln(R)$. Onze taak is het vinden van een cyclus met een negatief totaalgewicht.

2. Klassieke aanpak: Bellman-Ford

Het Bellman-Ford-algoritme is de "Hello World" van arbitragedetectie. Het is ontworpen om kortste paden te vinden en kan op natuurlijke wijze negatieve cycli detecteren.

2.1 Het algoritme in Rust

Met de petgraph-crate kunnen we dit efficiënt implementeren:

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 Complexiteit en beperkingen

Bellman-Ford draait in $O(V \times E)$, waarbij $V$ het aantal assets is en $E$ het aantal handelsparen.

• Voordelen: Garandeert het vinden van een cyclus als die bestaat.
• Nadelen: Te traag voor High-Frequency Trading (HFT) naarmate het aantal assets groeit. Het vindt bovendien maar één cyclus tegelijk.

3. SPFA: een sneller alternatief

De Shortest Path Faster Algorithm (SPFA) is een geoptimaliseerde versie van Bellman-Ford die een wachtrij gebruikt om overbodige berekeningen te vermijden.

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 de praktijk draait SPFA vaak in $O(k \times E)$ waarbij $k \ll V$, waardoor het veel sneller is voor ijle marktgrafen.

4. Modern onderzoek: het RICH-algoritme

In 2024 stelden onderzoekers het RICH (Rapid Identification of Cyclic High-profitability)-algoritme voor. In tegenstelling tot Bellman-Ford is RICH specifiek geoptimaliseerd voor financiële grafen waarin:

1. De graaf klein tot middelgroot is (honderden assets).
2. Gewichten elke milliseconde veranderen.
3. We de meest winstgevende cyclus moeten vinden, niet zomaar een cyclus.

4.1 Belangrijkste innovaties van RICH

• Pruning: Het verwerpt onmiddellijk paden die onmogelijk kunnen leiden tot een winstgevende cyclus, gebaseerd op het huidige best bekende pad.
• Gelaagd zoeken: Het zoekt naar cycli van toenemende lengte (3, 4, 5 stappen) met behulp van bitmask-optimalisaties.
• Incrementele updates: In plaats van het volledige algoritme opnieuw uit te voeren, worden alleen de delen van de graaf bijgewerkt die door een prijswijziging worden beïnvloed.

5. Implementatie-uitdagingen: kosten en liquiditeit

Echt handelen is niet gratis. Een cyclus met meerdere stappen $(A \to B \to C \to A)$ brengt drie afzonderlijke handelskosten met zich mee.

5.1 Kosten meenemen

We moeten onze randgewichten aanpassen: $w = -\ln(R \times (1 - \text{fee}))$ Dit snoeit de graaf aanzienlijk, aangezien veel theoretische cycli teniet worden gedaan door de uitvoeringskosten.

5.2 Liquiditeit en slippage

Naarmate je meer van een asset koopt, stijgt de prijs (slippage). Een cyclus die winstgevend lijkt voor $100 kan een verlies zijn voor$10.000. Geavanceerde graafmodellen gebruiken parametrische gewichten, waarbij $w$ een functie is van het volume $V$. Dit verandert het probleem van een eenvoudige kortste-padzoektocht in een convex-optimalisatieprobleem op een graaf.

6. Waarom Rust?

In de wereld van arbitrage maken 100 microseconden het verschil tussen winst en een "gemiste" kans.

• Geheugenveiligheid: Geen garbage collector-pauzes (GC) die de bot op een kritiek moment kunnen bevriezen.
• Zero-cost abstracties: We kunnen hoogwaardige graafstructuren gebruiken zonder de prestaties van rauwe pointers te verliezen.
• Concurrency: Rusts "Fearless Concurrency" stelt ons in staat om WebSocket-feeds van 10 exchanges parallel te verwerken en de gedeelde graaf veilig bij te werken.

Conclusie

Graafalgoritmen zijn de motor achter moderne crypto-arbitrage. Terwijl Bellman-Ford de basis legt, gebruiken moderne systemen geoptimaliseerde varianten zoals SPFA of gespecialiseerde algoritmen zoals RICH.

In het volgende deel van deze serie bekijken we futures-spotarbitrage, waarbij we onze graaf uitbreiden van eenvoudige asset-swaps naar het opnemen van funding rates en cash-and-carry-strategieën.

Bouw je low-latency handelssystemen? Bekijk onze open-source Rust HFT-template.