「イーサリアムキラー」と呼ばれる一部の暗号プロトコルは、その通称に反して目に見える成功事例はあまり多くはありません。一方、DAG(Directed Acyclic Graph)は「ブロックチェーンキラー」と称されています。
DAGのアプローチ、実用性、可能性を理解するには、技術的な観点からDAGを深く掘り下げることが必要です。簡単に言えば、DAGは、データやその反復の完全性を損なうことなく、同時開発を可能にするデータ構造モデルです。DAGsモデルは、異なるステージで提供されるループやフィードバックを考慮しない線形履歴モデルに取って代わる役割を担っています。
有向性非循環グラフとは
DAGとは、一連のアクティビティと、あるアクティビティから別のアクティビティへの流れを表現したグラフです。アクティビティは円(頂点)で描かれ、アクティビティが行われた順番は、一方向性の矢印を持つ線(辺)で表現されます。DAGモデルは非常に柔軟性が高く、開発者は自分自身を表現することができます。
頂点とエッジは基本的にDAGのコアを形成しており、ブロックチェーンにおけるブロックの働きと似ています。また、ブロックのミンティングと同様に、トランザクションは前のトランザクションを参照してネットワークに追加されます。
出典:techvidvan.com
有向非環状グラフの仕組み
ダンとグレンがGoogle Docsでブダペストへの旅程を作成しているとします。ダンは、「場所」「距離」「所要時間」の3つの小見出しをつけてデータを入力していきます。グレンは、旅程に加えるべき場所の写真を添えて、文書を更新していきます。このように、情報の追加と編集はそれぞれ別のタイミングで行われています。
さて、線形履歴モデルでは、ダンは時間をさかのぼり、過去のバージョンの文書を手に入れて、入力を続けることはできません。なぜなら、線形モデルでは、変更は最新バージョンにしか行えないからです。一方、DAGモデルでは、ダンは以前のバージョンのコピーを取り、データを入力し続けることができます。
注意すべき点は、ダンが入力している最後のバージョンには、ダンの最初のバージョンを指す矢印が記録され、アクティビティと編集の流れを表していることです。
有向グラフが非循環であるかどうかを調べるには?
グラフが以下のような場合、そのグラフは非循環的であると言われます。
- ノード(要素)数が0
- 葉がある
- 位相幾何学的にソートできる
グラフが非循環的であるかどうかを調べるツールには、次のようなものがあります。
- Kahnアルゴリズム:ノードの存在をチェック
- Tarjanアルゴリズム:ノード・葉の存在などの接続をテスト
- DFS (Depth First Search)
有向非環状グラフの応用
プロジェクト管理
企業では、DAG対応のワークフロー管理ソフトウェアを使用して、プロセスの計画、整理、スケジュール管理を行っています。各プロセスにはタスクのリストがあり、それらを組み合わせてDAGを形成します。ここでは、グラフの各頂点が完了する必要のあるアクティビティに対応しており,辺は次のアクティビティに移る前に取る必要のあるアクションと結びついています。
分散型台帳
DAGは、仕事の証明やステーク証明のコンセンサスメカニズムを備えた従来のブロックチェーンネットワークよりも、取引を記録するのが容易です。また、グラフ構造を持つことから、ブロックチェーン技術よりも効率的な場合が多いとされています。
データ処理ネットワーク
データの記録から集計まで、データパイプライン全体でDAGモデルを採用しています。DAGモデルでは、クリティカルパスの流れの中に複数のパスを認識するため、ワンクッション置くことができます。また、入力があればすぐに並列処理を開始できるため、ソリューションの同時進行が可能になります。
出典:Medium.com
ブロックチェーンと有向性非環状グラフの比較
ブロックチェーン技術とDAGは、異なるメカニズムで分散型台帳に取引を記録します。前者がブロックと分散型検証を用いて取引を認証するのに対し、後者は前の取引を証拠として検証を行います。これは、マイナーやバリデーターの絶対的な要件がないことを意味し、すなわち、必要なガス料金がない、または最小限であることを意味します。
DAGのインフラは、容易にスケールアップでき、しかも取引の実施を容易にします。ブロックチェーンネットワークは、効率的なスケールアップができない一方で、権威の概念が排除されているため、運営の分散化を実現しています。しかし、現状においてDAGは、プライベートネットワークシステムでかなりの程度まで中央集権化されている状態にあります。
DAGの採用が進めば、大量のトランザクションを最小限の消費電力とハードウェアで管理できるようになります。
結論
DAGはまだ発展途上の段階にあります。潜在的な可能性はあるものの、実現可能性やスケーラビリティの評価はまだ行われていません。また、開発者がDAGをdAppや製品のコアとして採用するのに必要な時間も重要な要素となっています。Web3に向けた動きが加速する中、DAGはブロックチェーン業界が必要としている刺激剤になるかもしれません。