Algoritmos de grafos para detecção de arbitragem: de Bellman-Ford ao RICH

Parte 1 da série "Cadeias complexas de arbitragem entre futuros e spot"

Imagine o mercado de criptomoedas como um organismo vivo, onde milhares de preços mudam a cada segundo em centenas de exchanges. Nesse caos, surgem discrepâncias temporárias de preço — "ineficiências" — que permitem lucro sem risco. Isso é arbitragem. Mas não estamos falando de simples swaps em duas etapas. Estamos mergulhando em cadeias complexas multiativos, em que um lucro só pode ser encontrado saltando de BTC para ETH, depois para SOL, depois para USDT e, finalmente, de volta para BTC.

Como encontramos essas cadeias entre milhões de possibilidades em tempo real? A resposta está na teoria dos grafos.

Neste artigo, percorreremos o caminho dos algoritmos clássicos até a pesquisa acadêmica mais avançada, implementando tudo em Rust para o máximo de desempenho.

Uma visualização de alta tecnologia de um grafo de arbitragem: os nós representam ativos, e as arestas representam pares de negociação. Um ciclo destacado representa uma oportunidade lucrativa detectada.

1. O mercado como grafo

Para aplicar algoritmos de grafos, primeiro precisamos representar o mercado corretamente.

1.1 Vértices e arestas

• Vértices (nós): Ativos (BTC, ETH, USDT, etc.).
• Arestas (ligações): Pares de negociação (BTC/USDT, ETH/BTC).
• Pesos: A taxa de câmbio.

Se tivermos uma taxa $R(i, j)$ (quanto do ativo $j$ obtemos por 1 unidade do ativo $i$), existe uma oportunidade de arbitragem se um ciclo $(i_1, i_2, \dots, i_k, i_1)$ produzir: $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 Da multiplicação para a adição

Computadores são muito mais rápidos somando do que multiplicando, e a maioria dos algoritmos de caminho mais curto é projetada para somas. Usamos um truque matemático simples: o logaritmo. Como $\ln(a \times b) = \ln(a) + \ln(b)$, a condição se torna: $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ Ou, invertendo o sinal para encontrar um ciclo negativo: $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

Agora, cada aresta tem um peso $w = -\ln(R)$. Nossa tarefa é encontrar um ciclo com peso total negativo.

2. Abordagem clássica: Bellman-Ford

O algoritmo de Bellman-Ford é o "Hello World" da detecção de arbitragem. Ele foi projetado para encontrar caminhos mais curtos e pode detectar ciclos negativos de forma natural.

2.1 O algoritmo em Rust

Usando o crate petgraph, podemos implementar isso 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 Complexidade e limitações

Bellman-Ford executa em $O(V \times E)$, onde $V$ é o número de ativos e $E$ é o número de pares de negociação.

• Vantagens: Garante encontrar um ciclo se ele existir.
• Desvantagens: Muito lento para negociação de alta frequência (HFT) à medida que o número de ativos cresce. Também encontra apenas um ciclo por vez.

3. SPFA: uma alternativa mais rápida

O Shortest Path Faster Algorithm (SPFA) é uma versão otimizada do Bellman-Ford que usa uma fila 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
}

Na prática, o SPFA costuma executar em $O(k \times E)$, onde $k \ll V$, tornando-o muito mais rápido para grafos de mercado esparsos.

4. Pesquisa moderna: o algoritmo RICH

Em 2024, pesquisadores propuseram o algoritmo RICH (Rapid Identification of Cyclic High-profitability). Diferentemente do Bellman-Ford, o RICH é especificamente otimizado para grafos financeiros em que:

1. O grafo é de tamanho pequeno a médio (centenas de ativos).
2. Os pesos mudam a cada milissegundo.
3. Precisamos encontrar o ciclo mais lucrativo, não apenas qualquer ciclo.

4.1 Principais inovações do RICH

• Poda (Pruning): Descarta imediatamente caminhos que não podem, de forma alguma, levar a um ciclo lucrativo, com base no melhor caminho conhecido atualmente.
• Busca em camadas: Procura ciclos de comprimento crescente (3, 4, 5 etapas) usando otimizações de bitmask.
• Atualizações incrementais: Em vez de reexecutar o algoritmo completo, ele atualiza apenas as partes do grafo afetadas por uma mudança de preço.

5. Desafios de implementação: taxas e liquidez

Negociar de verdade não é gratuito. Um ciclo de várias etapas $(A \to B \to C \to A)$ gera três taxas de negociação distintas.

5.1 Incorporando taxas

Precisamos ajustar os pesos das nossas arestas: $w = -\ln(R \times (1 - \text{fee}))$ Isso reduz significativamente o grafo, já que muitos ciclos teóricos são eliminados pelo custo de execução.

5.2 Liquidez e slippage

Quanto mais você compra de um ativo, mais o preço sobe (slippage). Um ciclo que parece lucrativo para $100 pode ser um prejuízo para$10.000. Modelos de grafos avançados usam pesos paramétricos, em que $w$ é uma função do volume $V$. Isso transforma o problema de uma simples busca de caminho mais curto em um problema de otimização convexa em um grafo.

6. Por que Rust?

No mundo da arbitragem, 100 microssegundos fazem a diferença entre lucro e uma oportunidade "perdida".

• Segurança de memória: Sem pausas do coletor de lixo (GC) que possam congelar o bot em um momento crítico.
• Abstrações de custo zero: Podemos usar estruturas de grafos de alto nível sem perder o desempenho de ponteiros brutos.
• Concorrência: A "Fearless Concurrency" do Rust nos permite analisar em paralelo os feeds WebSocket de 10 exchanges e atualizar o grafo compartilhado com segurança.

Conclusão

Os algoritmos de grafos são o motor por trás da arbitragem moderna de criptomoedas. Enquanto o Bellman-Ford fornece a base, os sistemas modernos usam variantes otimizadas como o SPFA ou algoritmos especializados como o RICH.

Na próxima parte desta série, veremos a arbitragem futuros-spot, na qual expandiremos nosso grafo de simples trocas de ativos para incluir taxas de financiamento (funding rates) e estratégias de cash-and-carry.

Você está construindo sistemas de negociação de baixa latência? Confira nosso template open source de HFT em Rust.