Algoritmos de grafos para la detección de arbitraje: de Bellman-Ford a RICH

Parte 1 de la serie "Cadenas de arbitraje complejas entre futuros y spot"

Imagina el mercado de criptomonedas como un organismo vivo donde miles de precios cambian cada segundo en cientos de exchanges. En este caos surgen discrepancias temporales de precios —"ineficiencias"— que permiten obtener beneficios sin riesgo. Esto es el arbitraje. Pero no hablamos de simples swaps de dos pasos. Nos adentramos en cadenas complejas multiactivo donde el beneficio solo puede encontrarse saltando de BTC a ETH, luego a SOL, luego a USDT y finalmente de vuelta a BTC.

¿Cómo encontramos estas cadenas entre millones de posibilidades en tiempo real? La respuesta está en la teoría de grafos.

En este artículo recorreremos el camino desde los algoritmos clásicos hasta la investigación académica más puntera, implementando todo en Rust para obtener el máximo rendimiento.

Una visualización de alta tecnología de un grafo de arbitraje: los nodos representan activos y las aristas representan pares de trading. Un ciclo resaltado representa una oportunidad rentable detectada.

1. El mercado como grafo

Para aplicar algoritmos de grafos, primero debemos representar el mercado correctamente.

1.1 Vértices y aristas

• Vértices (nodos): Activos (BTC, ETH, USDT, etc.).
• Aristas (enlaces): Pares de trading (BTC/USDT, ETH/BTC).
• Pesos: El tipo de cambio.

Si tenemos una tasa $R(i, j)$ (cuánto del activo $j$ obtenemos por 1 unidad del activo $i$), existe una oportunidad de arbitraje si 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 De la multiplicación a la suma

Los ordenadores son mucho más rápidos sumando que multiplicando, y la mayoría de los algoritmos de camino más corto están diseñados para sumas. Usamos un simple truco matemático: el logaritmo. Dado que $\ln(a \times b) = \ln(a) + \ln(b)$, la condición se convierte en: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ O, invirtiendo el signo para encontrar un ciclo negativo: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Ahora, cada arista tiene un peso $w = -\ln(R)$. Nuestra tarea es encontrar un ciclo con peso total negativo.

2. Enfoque clásico: Bellman-Ford

El algoritmo de Bellman-Ford es el "Hola Mundo" de la detección de arbitraje. Está diseñado para encontrar caminos más cortos y puede detectar ciclos negativos de forma natural.

2.1 El algoritmo en Rust

Usando el crate petgraph, podemos implementarlo de forma eficiente:

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 Complejidad y limitaciones

Bellman-Ford se ejecuta en $O(V \times E)$, donde $V$ es el número de activos y $E$ es el número de pares de trading.

• Ventajas: Garantiza encontrar un ciclo si existe.
• Desventajas: Demasiado lento para el trading de alta frecuencia (HFT) cuando crece el número de activos. Además, solo encuentra un ciclo a la vez.

3. SPFA: una alternativa más rápida

El Shortest Path Faster Algorithm (SPFA) es una versión optimizada de Bellman-Ford que usa una cola para evitar cálculos redundantes.

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
}

En la práctica, SPFA suele ejecutarse en $O(k \times E)$, donde $k \ll V$, lo que lo hace mucho más rápido para grafos de mercado dispersos.

4. Investigación moderna: el algoritmo RICH

En 2024, unos investigadores propusieron el algoritmo RICH (Rapid Identification of Cyclic High-profitability). A diferencia de Bellman-Ford, RICH está específicamente optimizado para grafos financieros donde:

1. El grafo es de tamaño pequeño a mediano (cientos de activos).
2. Los pesos cambian cada milisegundo.
3. Necesitamos encontrar el ciclo más rentable, no solo cualquier ciclo.

4.1 Innovaciones clave de RICH

• Poda (Pruning): Descarta inmediatamente los caminos que no pueden conducir a un ciclo rentable, basándose en el mejor camino conocido actualmente.
• Búsqueda por capas: Busca ciclos de longitud creciente (3, 4, 5 tramos) usando optimizaciones de máscara de bits.
• Actualizaciones incrementales: En lugar de volver a ejecutar el algoritmo completo, solo actualiza las partes del grafo afectadas por un cambio de precio.

5. Retos de implementación: comisiones y liquidez

El trading real no es gratuito. Un ciclo de varios tramos $(A \to B \to C \to A)$ conlleva tres comisiones de trading separadas.

5.1 Incorporación de comisiones

Debemos ajustar los pesos de nuestras aristas: $w = -\ln(R \times (1 - \text{fee}))$ Esto reduce significativamente el grafo, ya que muchos ciclos teóricos quedan eliminados por el coste de ejecución.

5.2 Liquidez y slippage

A medida que compras más de un activo, el precio sube (slippage). Un ciclo que parece rentable para 100 $podría ser una pérdida para 10.000$. Los modelos de grafos avanzados usan pesos paramétricos, donde $w$ es una función del volumen $V$. Esto convierte el problema de una simple búsqueda de camino más corto en un problema de optimización convexa sobre un grafo.

6. ¿Por qué Rust?

En el mundo del arbitraje, 100 microsegundos marcan la diferencia entre un beneficio y una oportunidad "perdida".

• Seguridad de memoria: Sin pausas del recolector de basura (GC) que puedan congelar el bot en un momento crítico.
• Abstracciones de coste cero: Podemos usar estructuras de grafos de alto nivel sin perder el rendimiento de los punteros nativos.
• Concurrencia: La "Fearless Concurrency" de Rust nos permite analizar en paralelo los feeds de WebSocket de 10 exchanges y actualizar el grafo compartido de forma segura.

Conclusión

Los algoritmos de grafos son el motor detrás del arbitraje moderno de criptomonedas. Mientras que Bellman-Ford sienta las bases, los sistemas modernos usan variantes optimizadas como SPFA o algoritmos especializados como RICH.

En la próxima parte de esta serie, veremos el arbitraje entre futuros y spot, donde ampliaremos nuestro grafo desde simples intercambios de activos hasta incluir las tasas de financiación (funding rates) y las estrategias cash-and-carry.

¿Estás construyendo sistemas de trading de baja latencia? Echa un vistazo a nuestra plantilla de HFT en Rust de código abierto.