※ 本記事は2022/11/25時点での筆者の知る範囲での情報の公開であり、再現性や結果を保証するものではありません。当記事の内容を応用する場合は、ご自身でもDYORの精神で情報収集することを推奨します。
DAG(Directed Acyclic Graph: 有向非巡回グラフ)
データ分析に使われているグラフです。 例えば, 複数の事象の因果関係を考える際の分析に使われています。
データを記録するデータ構造としてDAGを採用することで分散型台帳を実現できます。
つまりブロックチェーン関連で出てくるDAGとは, ブロックを一つのチェーンにリンクさせていくブロックチェーンとは別の, 分散型台帳の仕組みのことです。
DAG概要
頂点と辺で構成されていて, 各辺は矢印で表す( = 方向を持つ)。
-
事象aとbで言えば, aが原因でbが起きる場合, a → b で表す。
-
ブロックチェーン的に言えば, ブロックaの次にブロックbがリンクする場合, a → b で表す。
(実際にはブロックではなく, トランザクション同士が直接繋がるらしい。後詳しく。)
巡回することがない。
-
aから伸びた矢印が巡ってaに戻ることはない。
各点の繋がりにおいて, 分岐はするが方向性が有る。
-
後戻りする事がない。
つまり, 巡回する事がない点の繋がり(事象の因果関係や分散型台帳のリンク)をDAGで表現する事ができる。
DAGとブロックチェーン ポイント1
ブロックチェーンもDAGも, 単なる分散型台帳のデータ構造を表します。
ブロックチェーンはトランザクションをまとめたブロックが暗号学的に繋がっている。
DAGはトランザクション同士が直接暗号学的に繋がっている。
DAGとブロックチェーン ポイント2
分散型台帳にデータを記録する上で
-
誰が記録をするのか
-
どの記録は信頼できるのか
が重要 → コンセンサスメカニズム。
ブロックチェーンにPoWやPoSがあるように, DAGを使った分散型台帳にも, 開発者が適切だと考えるコンセンサスメカニズムがそれぞれあります。
IOTA
DAGを使用するIOTAという仮想通貨プロジェクトがあるので, そちらのdocsに記載されていたところを読み解きます。
ここでは, ブロックチェーンの代表としてBitcoinと, IOTAを比較して説明されています。
BitcoinとIOTAを比較するポイント2つ。
-
新しいブロックはどこに接続するべきか
-
取引確定はどのように判断するのか
Bitcoin
-
新しいブロックはどこに接続するべきか
(やや語弊があるが) 新しいブロックは最長のチェーンを承認すべき。 -
取引確定はどのように判断するのか
深さが6ブロック以上あり, 最長チェーンと繋がっている場合, 確定とみなせる。
IOTA
-
新しいブロックはどこに接続するべきか
新しいトランザクション(上の図でのIとG)はそれ以前の2つのトンラザションを選択し, 承認する。過去の各トランザクションにはどれだけ承認されたかの信頼度を示す重みというものがあり, より重みが高いトランザクションを選択するアルゴリズムになっている。
例えば上の図でDは合計の重み9(D3 + F1 + H3 + I1 + G1)を持っている。
(3はそのトランザクションの発行者が投資した作業量。詳しくは画像のリンクに飛んでください！)承認の際に2つのトランザクションに対してPoWを行うという話があったので, 暗号学的にリンクしているのだと思います。
-
取引確定はどのように判断するのか
トランザクションの重みが非常に高い場合。つまりほとんどのトランザクションによって承認されている場合。
ここで話したコンセンサスメカニズムはIOTAのもので, 他にも各プロジェクトで異なるメカニズムがあります。
例えば, 以下はAvalancheのものです。
DAGが解決する問題
-
トランザクションが複数の親を持つ事ができるので, 別のトランザクションの処理を待つ必要がなく高速となり, スケーラビリティもあります。
あるトランザクションが親Aを承認している間に別のトランザクションも親Aを承認して接続できます。 -
マイニングがないので, 手数料も環境負荷も低くなります。
承認作業はトランザクションを発行するノードが自身で行います(IOTAでは２つの承認にPoWを使用する)。
DAGの課題
- 新しい技術で, 実績が少ない。
補足
スマートコントラクトのように, ある取引が他の取引より前に行われたかどうかを知る必要があるものには向かないらしいです。
なので, avalancheではスマートコントラクト用のブロックチェーンには(DAGに使用しているものから)改良したコンセンサスプロトコルを用意しています。
以下を参考にしました。
以下私の見解です。
-
DAGは並列処理が行われているから, スマートコントラクトを動かすような特定の取引の前後を気にするのには向かない。
-
通貨の支払いなどはそれぞれの順序は関係なく, 結果として, 残高があり取引可能かを見るからDAGが有用。
-
Avalancheはデジタル資産のペイメント用の分散型台帳であるx-chainには, 最適な形としてDAGを採用。