Titan Backtest Reportの詳細な解説（日本語翻訳）

これは、Titan DEXアグリゲーターのパフォーマンスを検証するためのバックテストレポートの解説です。

SOLANAにおいてDEXアグリゲーターといえばJupiter１強でした。現在限られたユーザーが対象ですが、新たなDEXアグリゲーターとしてTitanが登場しました。TitanはJupiterとの違いを分かりやすく説明する為にtitan-backtest-report-1をブログに掲載しています。perplexity翻訳ですが読んでみましょう。

@Titan_Exchange

概要

Titanは、自社のプラットフォームの性能を他のプラットフォームと比較するために、バックテストレポートを作成しました。このレポートは、2024年11月19日に公開・更新されました。

バックテストは、スロット296946213付近のデータを使用して実行されました。実際のレイテンシ要件を再現するために、経路決定に時間制限が設けられています。テストデータは静的であるため、これは両方のアルゴリズムにとって最高のシナリオを表しています。実際には、Solanaのエコシステムが本質的に静的ではなく、他のユーザーがスワップを実行することでプールの挙動が変化するため、両方のアルゴリズムのパフォーマンスはここで概説されているよりも悪化します。

従来のDEXアグリゲーターの手法

多くのDEXアグリゲーターは、経路探索に最短経路アルゴリズムを使用しています。このアルゴリズムは、実装が比較的簡単で、大規模なネットワークでも高速であることが知られています。

具体的な手法は以下の通りです。

グラフ構造化: 各トークンをノード、各プールをエッジとして表現します。
価格設定: 各プールには、現在のトークンから隣接するトークンへの移動コストを示すスポット価格が関連付けられています。
最短経路探索: 最も単純なDEXアグリゲーターは、ダイクストラの最短経路アルゴリズムなどを使用して最短経路を見つけ、この経路をユーザーに提供します。
負のサイクルへの対応: 仮想通貨市場には自然に負のサイクルが発生するため、アルゴリズムに修正を加える必要があります。これにより、実行時間（スリッページ）またはソリューションの最適性の保証が犠牲になる可能性があります。
価格インパクトの考慮: ユーザーの取引量が増加すると平均支払価格が悪化するため、価格インパクトを考慮する必要があります。グラフを拡張し、各エッジを多数のエッジに分割することで、価格インパクトを近似できます。これにより、問題は最小コストフロー問題に変換されます。

このアプローチにより、多項式時間グラフアルゴリズムの利点を維持できますが、価格インパクトを考慮するためにグラフのサイズを大きくすると、実行時間が増加します。

Titanのアプローチ

Titanでは、独自の独自アプローチを使用して経路探索問題を解決します。このアプローチは、凸最適化のさまざまな手法を利用することで、上記のような課題を回避します。

その結果、Titanは、機械が対応できる任意の精度で問題を解決しながら、他のプラットフォームよりも大幅に優れた経路を提供できます。最も重要なことは、特定のエクスチェンジを介してスワップを行う際にユーザーが受ける価格インパクトを適切に解決できることです。

バックテストの結果

TitanのアルゴリズムとJupiterのアルゴリズムを比較した結果、以下のことがわかりました。

トークンリスト: さまざまなシナリオを捉え、流動性の高いペアでのアルゴリズムの性能を示すために、さまざまなトークンを選択しました。
全体的なパフォーマンス: Titanのアルゴリズムは、87％のケースでJupiterを上回りました。最大で25％のパフォーマンス向上が見られました。
スリッページと取引量: Titanのアルゴリズムは、取引量が少ない場合でも多い場合でも、Jupiterのルーティングアルゴリズムと同等以上の性能を発揮します。特に取引量の少ないユーザーにとって、Titanは大幅に優れた結果を提供します。

トークンリスト

Outperformance Heatmap

かなりの部分でアウトパフォームしているのが見受けられる

実行に関する注記

Titanは、実行に関しても独自のアプローチを採用しています。経路を短縮したり、ユーザーをサンドイッチ攻撃に晒したり、より高い手数料を要求したりする代わりに、スリッページ認識を最適化アルゴリズムのコアに組み込んでいます。

プールの将来の挙動を予測することで、特定の経路に沿ったテールリスクを推定できます。ユーザーが経路を選択してからスワップを実行するまでの時間差を考慮し、アウトプットを最大化するだけでなく、テールリスクへのエクスポージャーを最小限に抑えます。これにより、Titanを優先プラットフォームとして使用し続けるにつれて、ユーザーが得られるアウトパフォーマンスが向上します。

ボリュームに対するスリッページ

最短経路アルゴリズムの種類

トポロジカルソートの最短経路アルゴリズム

SWAP取引がサイクルを持たず、ある順序でしか実行できない場合、
グラフは有向非巡回グラフ (DAG) となります。この場合、各取引が依存関係にあるため、トポロジカルソートを使って最適な順序（最短経路）を求めます。

順次更新:
トポロジカルソートされた順に、各取引のコストを更新していきます。
たとえば：

A → B: 0 + 2 = 2

A → C: 0 + 3 = 3

B → D: 2 + 1 = 3

C → D: 3 + 1 = 4（すでに D は 3 なので更新せず）

D → E: 3 + 2 = 5

トポロジカルソートの最短経路アルゴリズム:
最適な取引シーケンスは、A → B → D → E（コスト 5）となり、すべての取引が原子的に実行され、途中で片方のみ失敗するリスクがありません。
依存関係が明確な取引シーケンスでは、トポロジカルソートにより効率的に最短経路を求めることができます。

ダイクストラの最短経路アルゴリズム

A の処理:
A → B (0+2=2), A → C (0+3=3)

B の処理:
B → D (2+1=3)

C の処理:
C → D (3+1=4) → 既に D は 3 のため更新せず

D の処理:
D → E (3+2=5)

ダイクストラ:
負のエッジがない状況では、ダイクストラのアルゴリズムを用いて最短経路を計算します。
ダイクストラのアルゴリズムでも、最短経路は A → B → D → E（合計コスト 5）となり、各取引はアトミックにまとめられることで、失敗リスクを避けながら実行できます。

以下に、両アルゴリズムの大きな違いを簡潔にまとめます。

対象グラフの種類
- トポロジカルソート: 有向非巡回グラフ（DAG）専用。
- ダイクストラ: 負のエッジがなければ、サイクルがあっても使える。
処理の流れ
- トポロジカルソート:
  グラフ全体を依存関係順に並べ、順番に頂点のコストを更新する。
  （全頂点を一度ずつ処理するため、計算量は (O(V+E))）
- ダイクストラ:
  未確定頂点の中から常に最小コストの頂点を選び、その周辺を更新する。
  （ヒープを用いると (O((V+E)\log V)) となる）
アルゴリズムの性質
- トポロジカルソート:
  事前に全体の順序が決まるため、各頂点の更新順序が固定される。
- ダイクストラ:
  状況に応じて最小値の頂点を動的に選ぶため、グラフ全体の構造に依存して更新順序が決まる。

以上が、トポロジカルソートとダイクストラの大きな違いです。

まとめ
最適なルートを選ぶトークンのSWAP、つまりDEX（分散型取引所）アグリゲーターでは、複数の市場間の取引を一括して実行するため、最適な取引シーケンス（＝最短経路）を見つけることが一番重要です。
どちらの手法も、最適なトークンSWAP取引を実行する際に、最適なルートを選定するための有効な方法ですが、Titanは独自のアプローチでJupiterをわずかに上回る最適なルート選定に自信があるようです

結論

Titanのバックテストレポートは、そのプラットフォームが従来のDEXアグリゲーターよりも優れたパフォーマンスを発揮できることを示しています。独自のアプローチとスリッページ認識により、Titanはユーザーにとってより効率的で安全な取引環境を提供します。

Citations:
[1] https://titandex.io/blog/titan-backtest-report-1

Perplexity の Eliot より: pplx.ai/share