Algoritmi su Grafi per il Rilevamento dell'Arbitraggio: Da Bellman-Ford a RICH

Parte 1 della serie "Catene di Arbitraggio Complesse tra Futures e Spot"

Immaginate il mercato delle criptovalute come un organismo vivo e pulsante, dove migliaia di prezzi cambiano ogni secondo su centinaia di exchange. In questo caos sorgono temporanee discrepanze di prezzo—"inefficienze"—che consentono di ottenere profitti privi di rischio. Questo è l'arbitraggio. Ma non parliamo di semplici swap in due passaggi. Ci immergiamo in catene multi-asset complesse, in cui un profitto può essere trovato solo saltando da BTC a ETH, poi a SOL, poi a USDT, e infine di nuovo a BTC.

Come trovare queste catene tra milioni di possibilità in tempo reale? La risposta risiede nella Teoria dei Grafi.

In questo articolo percorreremo il cammino dagli algoritmi classici alla ricerca accademica all'avanguardia, implementando tutto in Rust per ottenere le massime prestazioni.

Una visualizzazione ad alta tecnologia di un grafo di arbitraggio: i nodi rappresentano gli asset e gli archi rappresentano le coppie di trading. Un ciclo evidenziato rappresenta un'opportunità profittevole rilevata.

1. Il Mercato come Grafo

Per applicare gli algoritmi su grafi, dobbiamo prima rappresentare correttamente il mercato.

1.1 Vertici e Archi

• Vertici (Nodi): Asset (BTC, ETH, USDT, ecc.).
• Archi (Connessioni): Coppie di trading (BTC/USDT, ETH/BTC).
• Pesi: Il tasso di cambio.

Se disponiamo di un tasso $R(i, j)$ (quanto dell'asset $j$ otteniamo per 1 unità dell'asset $i$), esiste un'opportunità di arbitraggio se un ciclo $(i_1, i_2, \dots, i_k, i_1)$ produce: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Dalla Moltiplicazione all'Addizione

I computer sono molto più veloci nell'addizione che nella moltiplicazione, e la maggior parte degli algoritmi per il percorso più breve è progettata per le somme. Utilizziamo un semplice trucco matematico: il logaritmo. Poiché $\ln(a \times b) = \ln(a) + \ln(b)$, la condizione diventa: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Oppure, invertendo il segno per trovare un ciclo negativo: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Ora ogni arco ha un peso $w = -\ln(R)$. Il nostro obiettivo è trovare un ciclo con peso totale negativo.

2. Approccio Classico: Bellman-Ford

L'algoritmo di Bellman-Ford è il "Hello World" del rilevamento dell'arbitraggio. È progettato per trovare i percorsi più brevi e può rilevare naturalmente i cicli negativi.

2.1 L'Algoritmo in Rust

Utilizzando il crate petgraph, possiamo implementarlo in modo efficiente:

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 restituisce le distanze o un errore se viene trovato un ciclo negativo
    match bellman_ford(graph, start_node) {
        Ok(_) => None, // Nessun ciclo negativo
        Err(error) => {
            // In un'implementazione reale, ricostruiremmo il ciclo 
            // usando la mappa dei predecessori dall'errore
            println!("Arbitraggio rilevato!");
            None 
        }
    }
}

2.2 Complessità e Limitazioni

Bellman-Ford viene eseguito in $O(V \times E)$, dove $V$ è il numero di asset ed $E$ è il numero di coppie di trading.

• Pro: Garantisce di trovare un ciclo se esiste.
• Contro: Troppo lento per il High-Frequency Trading (HFT) quando il numero di asset cresce. Inoltre trova solo un ciclo alla volta.

3. SPFA: Un'Alternativa più Veloce

Lo Shortest Path Faster Algorithm (SPFA) è una versione ottimizzata di Bellman-Ford che utilizza una coda per evitare calcoli ridondanti.

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; // Ciclo negativo rilevato
                }
                if !in_queue[v] {
                    queue.push_back(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    false
}

In pratica, SPFA viene spesso eseguito in $O(k \times E)$ dove $k \ll V$, rendendolo molto più veloce per i grafi di mercato sparsi.

4. Ricerca Moderna: L'Algoritmo RICH

Nel 2024, i ricercatori hanno proposto l'algoritmo RICH (Rapid Identification of Cyclic High-profitability). A differenza di Bellman-Ford, RICH è specificamente ottimizzato per i grafi finanziari in cui:

1. Il grafo è di dimensioni da piccole a medie (centinaia di asset).
2. I pesi cambiano ogni millisecondo.
3. È necessario trovare il ciclo più redditizio, non semplicemente un ciclo qualsiasi.

4.1 Innovazioni Chiave di RICH

• Potatura: Scarta immediatamente i percorsi che non possono portare a un ciclo redditizio in base al percorso attualmente noto come migliore.
• Ricerca a Strati: Cerca cicli di lunghezza crescente (3 gambe, 4 gambe, 5 gambe) utilizzando ottimizzazioni con bitmask.
• Aggiornamenti Incrementali: Invece di rieseguire l'intero algoritmo, aggiorna solo le parti del grafo interessate da una variazione di prezzo.

5. Sfide di Implementazione: Commissioni e Liquidità

Il trading reale non è gratuito. Un ciclo multi-step $(A \to B \to C \to A)$ comporta tre commissioni di trading separate.

5.1 Incorporare le Commissioni

Dobbiamo adeguare i pesi degli archi: $w = -\ln(R \times (1 - \text{fee}))$ Questo pota significativamente il grafo, poiché molti cicli teorici vengono eliminati dal costo di esecuzione.

5.2 Liquidità e Slippage

Più si acquista di un asset, più il prezzo sale (slippage). Un ciclo che sembra redditizio per $100 potrebbe risultare in perdita per$10.000. I modelli di grafo avanzati usano pesi parametrici, dove $w$ è una funzione del volume $V$. Questo trasforma il problema da una semplice ricerca del percorso più breve in un problema di Ottimizzazione Convessa su un grafo.

6. Perché Rust?

Nel mondo dell'arbitraggio, 100 microsecondi sono la differenza tra un profitto e un'opportunità "mancata".

• Sicurezza della Memoria: Nessuna pausa del garbage collector (GC) che potrebbe bloccare il bot in un momento critico.
• Astrazioni a Costo Zero: Possiamo usare strutture di grafi di alto livello senza perdere le prestazioni dei puntatori grezzi.
• Concorrenza: La "Fearless Concurrency" di Rust ci consente di analizzare feed WebSocket da 10 exchange in parallelo e aggiornare il grafo condiviso in modo sicuro.

Conclusione

Gli algoritmi su grafi sono il motore dietro il moderno arbitraggio sulle criptovalute. Mentre Bellman-Ford fornisce le basi, i sistemi moderni usano varianti ottimizzate come SPFA o algoritmi specializzati come RICH.

Nella prossima parte di questa serie, esamineremo l'Arbitraggio Futures-Spot, in cui espandiamo il nostro grafo dai semplici swap di asset per includere i tassi di finanziamento e le strategie cash-and-carry.

Stai costruendo sistemi di trading a bassa latenza? Dai un'occhiata al nostro Template HFT Open Source in Rust.