アービトラージ検出のためのグラフアルゴリズム：Bellman-FordからRICHまで

シリーズ「先物とスポット間の複雑なアービトラージチェーン」第1部

暗号通貨市場を、数百の取引所にわたって毎秒数千の価格が変動する、生きた呼吸する有機体として想像してみてください。このカオスの中で、一時的な価格の乖離—「非効率性」—が発生し、リスクフリーの利益を可能にします。これがアービトラージです。しかし、ここでは単純な2ステップのスワップについて話しているのではありません。BTCからETH、次にSOL、USDT、そして最後にBTCに戻るといった、複雑なマルチアセットチェーンを深く掘り下げます。

数百万の可能性の中から、リアルタイムでこれらのチェーンをどのように見つけるのでしょうか？答えはグラフ理論にあります。

この記事では、古典的なアルゴリズムから最先端の学術研究までの道のりをたどり、最大のパフォーマンスを得るためにすべてをRustで実装します。

アービトラージグラフのハイテクビジュアライゼーション：ノードはアセットを、エッジは取引ペアを表す。ハイライトされたサイクルは検出された収益機会を示す。

1. グラフとしての市場

グラフアルゴリズムを適用するには、まず市場を正しく表現する必要があります。

1.1 頂点とエッジ

• 頂点（ノード）： アセット（BTC、ETH、USDTなど）。
• エッジ（リンク）： 取引ペア（BTC/USDT、ETH/BTC）。
• 重み： 為替レート。

レート $R(i, j)$（アセット $i$ 1単位でアセット $j$ がいくら得られるか）がある場合、サイクル $(i_1, i_2, \dots, i_k, i_1)$ が以下を満たすとアービトラージ機会が存在します： $R(i_1, i_2) \times R(i_2, i_3) \times \dots \times R(i_k, i_1) > 1$

1.2 乗算から加算へ

コンピュータは乗算よりも加算のほうがはるかに高速であり、ほとんどの最短経路アルゴリズムは和のために設計されています。シンプルな数学的トリック、対数を使います。 $\ln(a \times b) = \ln(a) + \ln(b)$ であるため、条件は次のようになります： $\ln(R_1) + \ln(R_2) + \dots + \ln(R_k) > 0$ または、符号を反転して負の閉路を見つけます： $(-\ln(R_1)) + (-\ln(R_2)) + \dots + (-\ln(R_k)) < 0$

これで、各エッジの重みは $w = -\ln(R)$ になります。私たちの課題は、合計重みが負のサイクルを見つけることです。

2. 古典的アプローチ：Bellman-Ford

Bellman-Fordアルゴリズムは、アービトラージ検出の「Hello World」です。最短経路を見つけるために設計されており、自然に負の閉路を検出できます。

2.1 RustでのアルゴリズムDa

petgraphクレートを使用して、効率的に実装できます：

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 計算量と制約

Bellman-Fordの計算量は $O(V \times E)$ で、$V$ はアセット数、$E$ は取引ペア数です。

• 利点： サイクルが存在する場合、確実に見つけることを保証します。
• 欠点： アセット数が増えると、高頻度取引（HFT）には遅すぎます。また、一度に1つのサイクルしか見つけられません。

3. SPFA：より高速な代替手段

Shortest Path Faster Algorithm（SPFA） はBellman-Fordの最適化版で、キューを使用して冗長な計算を回避します。

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
}

実際には、SPFAは $O(k \times E)$（$k \ll V$）で動作することが多く、スパースな市場グラフではBellman-Fordよりもはるかに高速です。

4. 最新の研究：RICHアルゴリズム

2024年、研究者たちは**RICH（Rapid Identification of Cyclic High-profitability）**アルゴリズムを提案しました。Bellman-Fordとは異なり、RICHは以下のような金融グラフに特化して最適化されています：

1. グラフが小〜中規模（数百のアセット）。
2. 重みがミリ秒ごとに変化する。
3. 任意のサイクルではなく、最も収益性の高いサイクルを見つける必要がある。

4.1 RICHの主要なイノベーション

• 枝刈り： 現在の最良経路に基づいて、収益性の高いサイクルにつながる可能性のない経路を即座に除外します。
• 階層的探索： ビットマスク最適化を使用して、増加する長さ（3レッグ、4レッグ、5レッグ）のサイクルを探索します。
• インクリメンタル更新： 完全なアルゴリズムを再実行するのではなく、価格変更の影響を受けたグラフの部分のみを更新します。

5. 実装の課題：手数料と流動性

実際の取引は無料ではありません。マルチレッグサイクル $(A \to B \to C \to A)$ では、3つの個別の取引手数料が発生します。

5.1 手数料の組み込み

エッジの重みを調整する必要があります： $w = -\ln(R \times (1 - \text{fee}))$ これによりグラフが大幅に枝刈りされ、多くの理論的なサイクルが実行コストにより無効になります。

5.2 流動性とスリッページ

アセットの購入量が増えるほど、価格は上昇します（スリッページ）。100ドルで収益性のあるサイクルでも、10,000ドルでは損失になる可能性があります。 高度なグラフモデルではパラメトリック重みを使用し、$w$ はボリューム $V$ の関数になります。これにより問題は、単純な最短経路探索からグラフ上の凸最適化問題に変わります。

6. なぜRustなのか？

アービトラージの世界では、100マイクロ秒が利益と「見逃した」機会の差になります。

• メモリ安全性： ガベージコレクター（GC）の一時停止がなく、重要な瞬間にボットがフリーズすることがありません。
• ゼロコスト抽象化： 生ポインタのパフォーマンスを失うことなく、高レベルのグラフ構造を使用できます。
• 並行性： Rustの「恐れなき並行性」により、10の取引所からのWebSocketフィードを並列に解析し、共有グラフを安全に更新できます。

まとめ

グラフアルゴリズムは、現代の暗号通貨アービトラージの中核エンジンです。Bellman-Fordが基盤を提供しますが、最新のシステムではSPFAのような最適化されたバリアントやRICHのような特化アルゴリズムを使用しています。

このシリーズの次のパートでは、先物-スポットアービトラージを取り上げ、単純なアセットスワップからファンディングレートやキャッシュ・アンド・キャリー戦略へとグラフを拡張します。

低レイテンシの取引システムを構築していますか？オープンソースのRust HFTテンプレートをご覧ください。