DAG技術淺探

DAG（Directed Acyclic Graph）又稱「有向無環圖」

即是由集合的頂點和有向邊構成，每條邊連接一個頂點到另一個，這樣，從某個頂點V開始，沿著有序的邊，最終循環回再次到V是不可能的

以下是二叉樹，DAG和有向圖的區別 （摘自網上資源）

基於DAG數據結構的區塊鏈網路如何運行呢？

目前採用DAG作為存儲結構的代表項目有dagcoin、Byteball、IOTA。以IOTA的底層數據結構Tangle為例，通過節點發出的所有交易構成了這個有向無環圖的集合。當一個新的交易發生後，它必須驗證之前的兩個交易，這些驗證關係就表示為有方向的邊。

如下圖（圖中，時間走向總是從左到右，一個小方框代表一筆交易）。

Tangle的數據結構圖(DAG)

關於DAG的幾個概念：

交易的自身權重

與發送這筆交易的節點所投入的工作量成正比。節點的工作量越大，這個節點發出交易的權重就越大

交易的累計權重

是這個交易的自身權重與直接及間接驗證這個交易的所有交易的自身權重之和

Tip

沒有被驗證的交易

交易的高度

從創世交易到當前這個交易的最長路徑

交易的深度

從當前這個交易到某個tip（未被驗證的交易）的最長路徑

交易的積分

當前這筆交易的自身權重與所有它驗證的那些交易的自身權重之和

例子

DAG結構範例

如上圖，一個小方框代表一筆交易，方框右下角較小的數字表示這筆交易的自身權重，方框中字體較大的數字代表這筆交易的累計權重。

交易F經過交易A、B、C、E四個交易直接或者間接被驗證。交易F的累計權重就是交易A、B、C、E四個交易的各自自身權重之和，即 9=3+1+3+1+1。

一開始的Tips是交易A和交易C。當一個新的交易X被添加到網路中，並對交易A和交易C進行了驗證之後，交易X就成為了網路中唯一的Tip。同時，整個網路中的其他所有交易的累計權重都增加3（即交易X的自身權重）。

DAG的高度與深度

交易G的高度為1，深度為4（最長路徑為：G-F-D-B-A）。而交易F的高度為2（最長路徑為：創始交易-G-F），深度為3（最長路徑為：F-D-B-A）。

交易A直接或間接驗證了交易B、D、F、G，因此交易A的積分=1+3+1+3+1=9。同樣的，交易C直接或間接驗證了D、E、F、G，因此交易C的積分=1+1+1+3+1=7。

DAG相比於傳統區塊鏈的優勢

1）數據結構保證了較強的可擴展性

DAG中，每筆交易都能看作一個區塊，每個區塊有多個指向。拓展性強，無容量限制。隨著 參與者的增多，網路也會趨向穩定，區塊確認時間也越來越快。

2）共識機制帶來的零手續費

傳統的區塊鏈中，交易者和礦工是分開的，這樣就容易導致算力中心化和高昂的手續費等問題；而DAG中，交易者本身也是礦工，這樣網路能完全去中心和，也無需支付手續費。

本文作者為U贊發燒友何怡彬

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！