Fluid limit of a distributed ledger model with random delay

本論文は、バッチ到着とランダムな遅延を考慮した分散型台帳（DAG）モデルの漸近挙動を解析し、到着率を無限大に、間隔をゼロに近づけることで、遅延偏微分方程式の解として表される流体極限により葉の数や頂点の特性を近似可能であることを示し、その安定性とシミュレーションによる検証を行ったものである。

要約

1. 舞台設定：デジタルのお祭り会場

まず、この世界を**「巨大なお祭り会場」**だと想像してください。

• 参加者（ユーザー）： 会場に来た人々。
• 注文（トランザクション）： 人々が「この料理が欲しい！」と注文すること。
• 料理人（マイナー/ノード）： 注文を受けて料理を作る人々。
• 料理（ブロック）： 完成した料理。
• 調理時間（Proof of Work）： 料理を作るのに必要な時間。

このお祭りでは、注文が来るとすぐに料理ができるわけではありません。**「調理時間（Proof of Work）」**という作業を済ませないと、その料理は「完成品」として会場に並べられません。

2. 問題点：注文が殺到するとどうなる？

このお祭りの面白いルールは以下の通りです。

1. 注文の選び方： 新しい注文（料理）は、すでに「完成して並んでいる料理（Tips）」の中から、ランダムに 2 つを選んで、それらを「親」にします。
2. 調理の遅延： 注文が入ってから、実際に料理が完成して並ぶまでには、**「調理時間」**がかかります。
   • 簡単な料理（短時間）もあれば、複雑な料理（長時間）もあります。
   • 注文が入った瞬間は「調理中（未完成）」の状態です。
   • 調理が終わると「完成品（Tips）」として並びます。
3. 次の注文： 新しい注文は、この「完成品」の中から 2 つを選んで、自分の「親」にします。

ここで起きる問題：
注文が殺到すると、「調理中」の料理が山積みになります。また、「完成品」がどれくらいあるかも、調理時間のバラつきによってコロコロ変わります。

• 調理時間がバラバラだと、「いつ完成するか」が予測しにくくなります。
• 注文が急増すると、「未完成の料理（調理中）」が溢れすぎて、システムがパンクするのではないか？
• 逆に、完成品が少なくなると、新しい注文が「親」を見つけられなくなるのではないか？

この**「注文の殺到」と「調理時間のバラつき」が、システムの安定性にどう影響するか**を、この論文は解明しようとしています。

3. 研究の核心：「流体（水の流れ）」のイメージ

研究者たちは、個々の注文（1 つの料理）を追いかけるのではなく、**「注文の海（流体）」**として捉えることにしました。

• 個々の注文 = 波や泡（ランダムで予測不能）。
• 注文の海全体 = 川の流れ（一定の法則に従って動く）。

彼らはこう考えました。

「注文が 1 件 1 件来るのを追うのは大変だ。でも、**『1 秒間に何件来るか』という『流れの速さ（流速）』と、『川全体の水量』**に注目すれば、全体の流れは予測できるのではないか？」

彼らは、**「注文が無限に速く、かつ非常に細かく来る」という極限状態を仮定し、その時のシステムがどう動くかを「遅延微分方程式（PDE）」**という数式で表しました。

これを**「流体限界（Fluid Limit）」と呼んでいます。
つまり、「個々の料理人の忙しさはランダムでも、川全体の水位（システムの状態）は、滑らかな水の流れのように予測可能だ」**という発見です。

4. 重要な発見：「調理時間」のバラつきが鍵

これまでの研究では、「調理時間は全員同じ（固定）」と仮定されることが多かったのですが、この論文は**「調理時間は人によって違う（ランダム）」**という現実的な条件を取り入れました。

• 発見： 調理時間がバラバラだと、システムの状態（「未完成の料理」や「完成品」の数）を予測するのが難しくなります。
• 解決： しかし、彼らは新しい数学的なモデルを開発し、**「調理時間がバラバラでも、全体の流れ（流体）は安定して予測できる」**ことを証明しました。
• 安全への示唆： 「完成品（Tips）」の数が多すぎると、新しい注文が「親」を見つけにくくなり、システムが遅くなります。逆に少なすぎると、セキュリティが弱くなります。この「流体モデル」を使えば、**「最適な注文の量」や「調理時間のバランス」**を計算し、システムが安全に動くための条件を見つけることができます。

5. まとめ：なぜこれが重要なのか？

この研究は、以下のようなことを教えてくれます。

• 予測の精度向上： 「注文が急増したらどうなるか？」をシミュレーションするだけで、実際にコンピュータを動かす（調理する）必要がなくなります。数学の式（流体モデル）を使えば、システムがパンクするかどうかを事前に知ることができます。
• セキュリティの強化： 「いつまで経っても料理が完成しない（承認されない）」というリスクを減らすために、システム設計をどう調整すればいいかを提案できます。
• 現実への適用： 実際のブロックチェーンや IOTA などのシステムは、この「流体モデル」で記述できるほど複雑ですが、同時に「川の流れ」のように法則に従っていることがわかりました。

一言で言えば：
「お祭りの注文が殺到しても、**『川の流れ』**のように全体を見渡せば、いつまで経っても料理が完成しないという混乱は起きないし、安全に運営できるよ」ということを、数学的に証明した研究です。

---

簡単な比喩まとめ：

• ブロックチェーン/DAG = 巨大なお祭り会場。
• 注文（トランザクション） = 料理の注文。
• Proof of Work（調理時間） = 料理を作る時間（人によって違う）。
• Fluid Limit（流体限界） = 個々の注文を追うのではなく、「注文の海の流れ」全体を見て予測する方法。
• この論文の貢献 = 「調理時間がバラバラでも、川の流れ（システム）は安定して予測できるよ！」と証明した。

技術概要

以下は、J. Feng と C. King による論文「Fluid limit of a Distributed Ledger Model with Random Delay（ランダムな遅延を伴う分散型台帳モデルの流体極限）」の技術的な要約です。

1. 問題設定 (Problem)

分散型台帳（DL）、特にブロックチェーンや DAG（有向非巡回グラフ）構造を持つシステム（例：IOTA/Tangle）は、すべての信頼されたネットワークメンバーが透明性を持ってデータを更新できる分散データベースです。これらのシステムのダイナミクスは DAG として数学的に表現されます。

本研究が扱う核心的な問題は以下の通りです：

• Proof-of-Work (POW) の遅延: ユーザーが新しいブロック（頂点）を作成しても、即座にネットワークに追加されるわけではありません。POW 計算を完了させるまでの「ランダムな遅延」が存在します。
• ランダムな POW 期間: 従来の研究（例：[14]）では POW 期間が一定（固定値）であると仮定されていましたが、現実のシステムでは計算負荷やネットワーク状況により POW 期間は確率的に変動します。
• バッチ到着と同時到着: 複数のユーザーが同時にブロックを作成・送信するシナリオ（バッチ到着）を考慮する必要があります。
• モデルの複雑化: POW 期間がランダムである場合、ある「ティップ（未承認のブロック）」がいつ承認（他のブロックに接続される）されるかが不確実になり、システムの挙動解析が極めて困難になります。

本研究の目的は、ランダムな POW 期間とバッチ到着を考慮した DAG モデルの漸近的な挙動を解析し、その流体極限（Fluid Limit）を導出することです。

2. 手法 (Methodology)

著者らは、到着率 $\lambda$ を無限大に、到着間隔 $\epsilon$ を 0 に近づける極限（Fluid Limit 近似）を用いて、確率過程を決定論的な偏微分方程式（PDE）系で近似するアプローチを採用しました。

• モデルの定式化:
  • 各頂点は、既存の「ティップ（Tips）」から 2 つの親をランダムに選択して接続します（IOTA のルール）。
  • POW 期間は $\{h_1, h_2, ..., h_M\}$ の離散値から確率 $p_i$ で選択されます。
  • 頂点は「フリーティップ（未選択）」と「ペンディングティップ（親に選択され、POW 中）」に分類されます。
  • ペンディングティップは、残存寿命（Residual Lifetime, RLT）という変数で管理され、親に選択されたタイミングや POW 完了時刻に基づいて状態が遷移します。
• 更新則の導出:
  • 離散時間ステップごとのティップ数、フリーティップ数、ペンディングティップ数の更新則を確率変数（二項分布など）を用いて記述しました。
  • 期待値の主要項（Leading order term）のみを抽出し、高次項を無視することで、確率過程の平均的な挙動を捉えます。
• 流体極限の導出:
  • $\lambda, N, \epsilon^{-1} \to \infty$ の極限をとることで、離散的な差分方程式を連続的な**遅延偏微分方程式（Delayed PDEs）**の系に変換しました。
  • 得られた PDE は、現在の状態だけでなく、過去の状態（遅延 $h_i$ を含む）にも依存する構造を持っています。
• 収束性の証明:
  • 確率過程と流体極限（PDE の解）との差 $g(T)$ が、時間 $T$ において確率 1 で 0 に収束することを示すために、マルティンゲール不等式（Azuma-Hoeffding 不等式）と離散 Gronwall の補題を用いました。
  • 初期条件が適切に設定されている場合、任意の有限時間区間 $[0, T]$ において、シミュレーションされたランダム過程が流体極限に指数関数的に近づいていくことを証明しました。

3. 主要な貢献 (Key Contributions)

1. ランダムな POW 期間を考慮した流体極限モデルの確立:
   • 固定された POW 期間を仮定した既存の研究 [14] を拡張し、POW 期間がマルチノミアル分布（離散確率分布）に従う場合の流体極限を初めて導出しました。
   • これにより、ランダムな遅延下での DAG のダイナミクスを、一連の遅延 PDE によって記述できるようになりました。
2. ティップのリスク分類と詳細な解析:
   • 単なるティップ数のみならず、ティップを「残存寿命」や「タイプ（POW 期間の種類）」に基づいて分類し、それぞれの状態遷移を詳細にモデル化しました。
   • これにより、セキュリティ観点から「どの程度のリスク（いつ承認されるか）にさらされているティップの割合」を評価する新たな指標を提供しました。
3. 厳密な収束性の証明:
   • 離散確率過程と流体極限の間の誤差が、パラメータ（到着率、バッチサイズなど）が適切に増大する条件下で確率的に 0 に収束することを数学的に厳密に証明しました。
   • 具体的には、誤差の確率上限を明示的な式（式 3.2）として与えています。
4. 平衡状態の解析:
   • 流体極限の定常状態（Equilibrium point）を解析し、パラメータ（POW 期間の分布など）が安定時のティップ数にどのように影響するかを明らかにしました。

4. 結果 (Results)

• 流体極限の精度: シミュレーション結果（図 4）は、スケーリングされたランダム過程が流体極限（PDE の解）に非常に良く一致することを示しています。ランダムな変動は小さく、システムはほぼ決定論的に振る舞います。
• 安定状態の性質:
  • 安定状態において、フリーティップ数 $f$、ペンディングティップ数 $w$、総ティップ数 $l$ の間には $f = w = l/2$ という関係が成り立ちます（親を 2 つ選ぶ場合）。
  • 平均 POW 期間 $\sum p_i h_i$ が短いほど、ティップは速く承認されるため、システム内の待機しているティップ数（$l$）は減少します。
• パラメータの影響: POW 期間の分布（$p_i, h_i$）がシステムの安定状態の値を決定づけることが示されました。
• 収束速度: 誤差 $g(T)$ は、$\epsilon \to 0$ および $N \to \infty$ の条件下で確率 0 に収束しますが、時間 $T$ が無限大に発散する場合は発散する可能性があります。

5. 意義 (Significance)

• 理論的基盤の強化: 分散型台帳、特に DAG 構造を持つシステム（IOTA など）のセキュリティと安定性を数学的に厳密に解析するための強力なツールを提供しました。
• 実用的な洞察: 流体極限モデルを用いることで、実際の POW 計算をシミュレートすることなく（計算コストを大幅に削減）、システムの長期挙動やティップ数の予測が可能になります。
• セキュリティ評価への応用: ティップが承認されるまでの時間（検証速度）はシステムのセキュリティ（二重支払い攻撃への耐性など）に直結します。本研究で導出された流体極限は、ランダムな遅延下での検証速度や、攻撃に対するシステムの堅牢性を評価するための基礎となります。
• 将来の研究方向: 敵対的攻撃（Adversarial attacks）や通信遅延を組み合わせたさらなる解析、およびより複雑なプロトコルへの拡張の可能性を示唆しています。

総じて、この論文はランダムな遅延を伴う分散型台帳の複雑な確率的挙動を、解析的に扱いやすい流体極限モデルへと変換し、その正当性を数学的に保証した重要な研究です。