DEEP DIVE: DAG

DAG（非巡回有向グラフ）：鎖でも木でもない、因果を表す構造

Gitのコミット履歴も、IPFSがコンテンツを束ねるMerkle DAGも、ブロックチェーンを「1本の鎖」から「網」へ拡張しようとするTangleやGHOSTDAGのような台帳も、根底にあるのは同じ構造、DAG（Directed Acyclic Graph、非巡回有向グラフ）です。「辿っても決して後戻りしない」というただ一つの制約が、なぜ分散システムの因果関係を表現する自然な言語になるのかを、定義から実例まで詳説します。

DAGとは何か: 定義とトポロジカルソート

DAG（非巡回有向グラフ）は、その名の通り2つの要素からなります。有向グラフ（ノード同士を結ぶ辺に向きがある）であり、かつ非巡回（辺をどれだけ辿っても、出発したノードに戻ってくる経路が存在しない）です。「Aの子孫を辿っていけばいつかAに戻ってくる」ということが決してありません。これが「非巡回」の意味するところで、DAGでは全ての辺が何らかの意味で「前から後ろへ」しか流れません。

木（Tree）との違いは、ノードが複数の親を持てるかどうかにあります。木では各ノードの親はちょうど1つ（ルートのみ0個）で、経路が分岐することはあっても再び合流することはありません。DAGはこの制約を外し、複数の経路が1つのノードへ合流（converge）することを許します。木はDAGの特殊ケースであり、逆に言えばDAGは木よりも表現力の高い構造だと言えます。

トポロジカルソートの存在: 有向グラフがトポロジカル順序（すべての辺が「前から後ろ」を向くような頂点の一列並べ）を持つことと、そのグラフが非巡回であることは同値である。DAGなら必ず少なくとも1つのトポロジカル順序が存在する。
到達可能性が半順序（partial order）を成す: ノードAからノードBへ辺を辿って到達できるとき「A ≤ B」と定義すると、この関係は反射律・反対称律・推移律を満たす半順序になる。巡回がないからこそ反対称律（A ≤ B かつ B ≤ A ならA = B）が成り立つ。
「半」順序である理由: 半順序は全順序と違い、すべてのノードの組が比較可能とは限らない。互いに祖先・子孫の関係にない2ノードは「並行（concurrent）」であり、どちらが先とも言えない。
トポロジカル順序は一意とは限らない: 同じDAGに対して妥当なトポロジカル順序は複数存在しうる。「唯一の正しい順序」を求める場面では、別途の順序付けルールが必要になる。

なぜ分散システムでDAGなのか: 因果関係という半順序

分散システムには、全ノードが共有する物理的なグローバルクロックが存在しません。したがって「すべてのイベントがどの順序で起きたか」という全順序を、外部の観測者なしに一意に定めることは原理的にできません。しかし、あるイベントが別のイベントの原因になりうるかどうか、すなわち因果関係は定義できます。Leslie Lamportは1978年の論文「Time, Clocks, and the Ordering of Events in a Distributed System」で、この関係をhappened-before関係（記号 →）として定式化しました。これは全順序ではなく半順序であり、AとBが互いにhappened-beforeでなければ、両者は並行（concurrent）です。

happened-before関係を実際に計算する仕組みがベクタークロック（Fidge、Mattern、ともに1988年）です。各ノードが「自分が観測した各ノードのイベント数」を並べたベクトルを持ち、メッセージ送受信のたびに更新します。この仕組みが暗黙のうちに構築しているのは、イベントを頂点、直接の因果依存を辺としたDAGそのものです。つまりDAGは、分散システムの因果関係を表現するための特別な発明ではなく、happened-before関係というものの持つ数学的構造をそのまま可視化した姿にすぎません。

独立な処理を無理に直列化しない: 全順序を強制すると、本来は無関係な操作同士まで待ち合わせが発生し、ネットワーク分断時には身動きが取れなくなる。DAGは依存がある部分だけを順序づけ、独立な部分は並行のまま扱える。
ゴシップとの相性: ゴシッププロトコルによる非同期な情報伝播では、各ノードが情報を受け取った順にそのまま因果グラフを組み立てていける。全順序への強制的な整列を待つ必要がない。

実例で見るDAG

Git: コミットDAG

各コミットは、親コミットのハッシュへのポインタを持ちます。通常は親が1つですが、マージコミットは親を2つ（以上）持ち、別々に進んだ複数のブランチの履歴を1つのノードへ合流させます。「ブランチ」という概念自体は独立した実体ではなく、特定のコミットを指す単なる可変のポインタ（ref）にすぎません。git log --graphで表示されるのは、まさにこのコミットDAGの可視化です。

IPFSのMerkle DAG

Merkle木で述べた通り、IPFSはコンテンツをチャンクへ分割し、各チャンクを子のハッシュで指し示すリンクによって束ねます。ここで使われる「ハッシュで子を指す」というリンクの張り方こそが、巡回を原理的に不可能にしています。ノードBがノードAの子になるには、Aを構築する時点でBのハッシュがすでに確定していなければならず、Bが後からAを指し返して巡回を作ることはできません。同一内容のチャンクは常に同一のハッシュを持つため、木ではなく複数の親を許すDAGとして扱うことで、自然な重複排除（deduplication）も実現されます。

DAG型台帳: ブロックチェーンを「鎖」から「網」へ

単一チェーンのブロックチェーンは、ある時点で複数のブロックが並行して提案されても、最終的には最長チェーン等のフォーク選択規則で1本を残し、それ以外は捨てます。DAG型台帳はこの発想を逆転させ、並行して提案された複数のブロックやトランザクションを捨てずにすべてグラフへ取り込んだ上で、どの部分を正当な履歴とみなすかを決める順序付けルールを別途用意します。

IOTAのTangle: 新規トランザクションが発行時に先行する2つのトランザクションを検証・承認する設計。ブロック単位でまとめず取引ごとに直接DAGへ連結することで、参加者が増えるほど処理能力が上がることを狙った。
GHOSTDAG（Kaspa）: Yonatan SompolinskyとAviv Zoharが提案したプロトコル。PoWによって並行して生成される複数のブロック（blockDAG）を捨てずに取り込み、ブロック同士の関係から「主鎖」を再帰的に選び出す順序付けルールを与える。Nakamoto的なPoWの安全性モデルを保ちながらブロック生成間隔を詰め、スループットを上げることを狙う。
Hashgraph: Leemon Bairdが考案した方式。「ゴシップ・アバウト・ゴシップ」でイベントの伝播履歴そのものをDAGとして構築し、そのDAG構造だけから投票を仮想的に再現する（virtual voting）ことでaBFT（非同期ビザンチン耐性）合意に到達する。

これらが狙うのは主にスループットの向上、つまり1本のチェーンでは順番待ちになっていた部分を並行処理できるようにすることです。しかし代償として合意の複雑さも増します。「どの部分DAGを正当な履歴とみなすか」を決める順序付けルールの安全性解析は、単純な最長チェーン規則よりもはるかに込み入っており、分散合意の設計と検証の難度を押し上げます。

CRDTと操作の因果DAG

オフラインでも複数人が同時編集できる共同編集システム（CRDT: Conflict-free Replicated Data Type）では、各編集操作を「どの操作の後に行われたか」という因果依存関係とともに記録し、これをDAGとして扱います。マージとは、2つのレプリカが持つ操作DAGを和集合として合成し、DAG上で祖先・子孫の関係にない（＝並行な）操作同士については決定的な優先規則で衝突を解消する手続きです。この因果DAGを効率よく突き合わせるレプリカ同期は、ゴシッププロトコルのanti-entropyと組み合わせて実装されることが多くあります。分散型SNSプロトコルであるAT Protocol（Bluesky）のリポジトリも、各コミットが親コミットのハッシュを指す連鎖としてDAG的な履歴を成しており、レコード本体を格納するMerkle Search Treeと組み合わさっています。

DAGは分散台帳や共同編集に限った話でもありません。makeやBazelのようなビルドシステムはタスク間の依存関係をDAGとして表現し、トポロジカルソートでビルド順序を決めます。npmやaptのようなパッケージマネージャも依存パッケージ同士の関係をDAGとして解決し、循環依存を検出するとインストールを拒否します。身近な場所にもDAGは息づいています。

鎖・木・DAGの構造比較

観点	鎖（ブロックチェーン）	木（Merkle Tree）	DAG
ノードの親の数	常に1つ（一本道）	常に1つ（ルートへ収束する階層）	複数の親を持てる（合流できる）
構造	線形な全順序	階層的な半順序（根から葉へ）	一般的な半順序（トポロジカル順序は複数ありうる）
フォークの扱い	最長チェーン等の規則で1本を残し他は破棄	静的な構造のため、通常フォークという概念自体がない	フォークを破棄せず取り込み、順序付けルールで解決
得意なこと	単純な合意（全順序の決定）	固定データ集合の効率的な包含証明	因果関係の表現、並行な更新の許容、スループット向上
代表例	Bitcoinのブロック連鎖	Merkle Tree・Gitのtreeオブジェクト	Gitのコミット履歴・IPFSのMerkle DAG・Tangle・GHOSTDAG

よくある誤解と注意点

「DAGは常にブロックチェーンより優れている」は誤解: DAGはスループットや並行性で有利になりうる一方、「どの部分DAGを正当な履歴とみなすか」を決める合意ルールの安全性解析は単純な一本鎖より複雑になりやすい。実際、初期のDAG型台帳の一部は、安全性を中央集権的な仕組みに依存していた時期もあった。
「DAGなら改ざん不可能」も誤解: 耐改ざん性はグラフの形そのものではなく、ハッシュ関数の衝突耐性・署名・そして分散合意やファイナリティの仕組みによって担保される。DAGは因果関係を表現する器にすぎず、それ自体が安全性を保証するわけではない。
「トポロジカル順序は一意に決まる」も誤解: 前述の通り、同じDAGに対して複数の妥当なトポロジカル順序が存在しうる。「唯一の正史」が必要な場面では、GHOSTDAGの順序付け規則のような追加のルールが別途要る。
「Merkle DAG」と「DAG型台帳」は別物: IPFSやGitのようにデータをハッシュで束ねるMerkle DAG（データ構造としての用途）と、TangleやGHOSTDAGのようなDAG型台帳（合意アーキテクチャとしての用途）は、同じグラフ理論の概念を使ってはいるが目的も設計も異なり、混同すべきではない。