技術要約：オンチェーン・レジストリにおける定数時間アペンドのコスト分析

問題提起

プロベナンス・ツリー（PT）は、オペレーター制御のプロベナンス・インフラストラクチャのデータ基盤として使用される、追加専用（append-only）の有向非巡回グラフ（DAG）である。PTの基礎となるアペンド操作が、レジストリのサイズやツリーの深さに依存せず、$O(1)$ のガスコストであることを以前の研究では主張していたが、この主張には、独立したプリミティブとしての形式的な分離、明示的な定数境界、および業界標準であるインクリメンタル・マークル・ツリー（IMT）に対する実証的なベンチマークが欠けていた。

IMTは、ゼロ知識プロトコル（例：Tornado Cash、Semaphore）やロールアップのステートコミットメントにおいて支配的であり、簡潔な $O(\log N)$ の包含証明を提供するが、アペンドコストはツリーの深さに比例して対数的に増加する（$\Theta(\log N)$）。プロベナンス・レジストリのように、簡潔なメンバーシップ証明が主要なクエリではないアプリケーションの場合、IMTのコストのトレードオフはあまり好ましくないが、代替案がより安価になるクロスオーバーポイントは厳密に確立されていない。

メソドロジー

本論文では、**親ハッシュ有向非巡回グラフ（PHDAG）**を独立したプリミティブとして分離し、**インクリメンタル・マークル・ツリー（IMT）**と比較することを、以下の3つの観点から行う。

1. 形式的複雑性分析： 著者らはPHDAGのアペンド操作を定式化し、それがレジストリのサイズ（$n$）や深さに依存せず、限定された数のEVM操作を実行することを証明した。これに対し、IMTのフロントイヤー更新ループは、深さ（$d$）に対して線形にスケールする。
2. 確率的コストモデリング： IMTのアペンドコストはリーフインデックスのバイナリ表現（ハミング重み）に基づいて変動することを認識し、著者らはリーフインデックスの一様分布下でのIMTの1回あたりの挿入ガスコストを、ランダム変数としてモデル化した。彼らは、「ライトレベル（フロントイヤーの更新）」と「リードレベル（書き込みを行わずにトラバースする）」を区別しながら、IMTコストの平均と分散に関する閉形式の式を導出した。
3. 実証的検証： 両方のプリミティブの独立したコントラクトをBase Sepoliaテストネットにデプロイした。実験はツリーの深さ1から25までを対象とした。
   • IMT： 分散を捉えるために、各深さに対して $\max(d, 2)$ 回のアペンドを行う「比例的な深さスイープ」を通じてテストした。
   • PHDAG： コスト分布と分散を特徴付けるための200回のアペンド実行を通じてテストした。
   • メトリクス： 初期コールドストレージの初期化コストを除外し、定常状態のパフォーマンスに焦点を当てるため、トランザクションレシートからガス消費量を測定した。

主要な貢献

1. PHDAGの形式的複雑性

本論文は、PHDAGのアペンドが厳密に $O(1)$ のガスコストであることを確立している。

• メカニズム： 各アペンドは、一意の識別子によってキー付けされた、以前は未接触であった3つのストレージスロット（コールドSSTORE）への書き込みと、カウンタへのウォームライトを行う。
• 不変性： コストはグローバルなレジストリサイズ $n$ およびあらゆるツリーの深さの概念に対して不変である。トランザクションのアクセスリストは各トランザクションの開始時にリセットされる。PHDAGは毎回新しいスロットに書き込むため、コストは契約の状態ではなく、固定された操作数にのみ依存する。
• 再構築： 本論文は、イベントストリームが正準な履歴を保持しているため、公開イベントログから完全なレジストリを $O(|V|)$ の時間で、オフチェーンへの依存なしに再構築できることを証明している。

2. IMTの確率的モデル

著者らは、IMTの1回あたりの挿入コスト $g$ がリーフインデックス $i$ に依存するランダム変数であることを導出した：

• 平均： $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$、ここで $c_L$ と $c_R$ はそれぞれライトレベルとリードレベルの限界コストである。
• 分散： $Var[g] = (c_L - c_R)^2 \frac{d}{4}$。
• 含意： 相対的な分散（変動係数）は深さが増すにつれて減少するが、絶対的な標準偏差は $\Theta(\sqrt{d})$ として成長し、高深度のレジストリにおける運用の予測不可能性をもたらす。

3. 実証的クロスオーバーと検証

• PHDGAのパフォーマンス： アペンドあたり一定の 76,276ガス（標準偏差 $\approx 6$ ガス）と測定され、深さ不変性が確認された。
• IMTのパフォーマンス： コストは深さに比例して線形に増加した。
• クロスオーバーポイント： PHDAGがIMTよりも安価になる深さは、$d \approx 6$ から $7.2$ の間で特定された。
  • $d=6$ において、測定されたIMTコスト（$\approx 78,000$ ガス）はPHDAGのコストを上回った。
  • （一様インデックス分布の下での）生涯平均クロスオーバーは $d^* \approx 7.2$ と計算された。

結果

実証データは理論モデルを検証している：

• PHDAG は、テストされたすべての深さにおいて、無視できるほどの分散と一定のコストを示す。
• IMT は、線形のコスト成長と、深さとともに増大する絶対分散を示す。
• プロダクションの文脈： 調査されたすべてのプロダクション・レジストリ（Tornado Cash, Semaphore, zkSync, Scroll, Linea）は、深さ $d \ge 20$ で動作している。したがって、これらすべてのシステムは現在、簡潔な包含証明を必要としない限り、PHDAGの方が厳密に安価であり、予測可能なコストを提供する領域で動作している。

意義と主張

本論文は、以下の条件を満たす追加専用のプロベナンス・レジストリにとって、PHDAGプリミティブが優れた選択肢であると主張している：

1. 簡潔なメンバーシップ証明が不要であること： プロベナンスのクエリは通常、親チェーンのトラバースや一意識別子による存在確認を伴い、これらは $O(\log N)$ のマークル証明ではなく、$O(|V|)$ のログベースの再構築によってサポートされる。
2. コストの予測可能性が重要であること： 高ボリュームのアペンドサービスを管理するオペレーターにとって、PHDKの分散がほぼゼロであることは、IMTと比較して、ワーストケースのガスタイル（最悪値の裾）のために予算を組む必要性を排除するという大きな運用上の利点をもたらす。
3. 堅牢性が極めて重要であること： PHDAGのログ正準デザインにより、レジストリの履歴は、現在の契約ストレージの状態やオフチェーンのインデキシングサービスに依存することなく、公開イベントログのみから再構築可能であり、破壊不可能なものとなる。

著者らは、PHDAGがイーサリアムのプロベナンス・インフラストラクチャのための統一されたインターフェースとして標準化される強力な候補であり、非ZKアプリケーションに対して、深さに依存するIMTに代わる、定数コストかつ深さ不変の選択肢を提供すると結論付けている。