最近有人問DAG相關的東西，今天就來說說關于DAG的話題，DAG是一個數據結構名詞，有項目用了這種復雜的結構來存儲交易數據，本文只能粗略探討一下

如果你還記得大學開設的《數據結構》科目，DAG出現在那本書的最后一章“圖論”中，圖應該是最復雜的數據結構了，所以當時我們學校并沒有教最后一章，只是讓感興趣的人自學，由于后來的工作中最多用到B+樹，對于圖的學習只是停留在表面，只是記得存儲圖最好的方式是采用“鄰接多重表”這種結構。

什么是DAG

圖和樹一樣，是一種數據結構，在計算機科學中往往為了避免復雜的數據結構影響開發和數學建模會將結構進行簡化或者約束，比如“樹”這種結構其實根據定義也是很復雜的，當時真正用的時候“二叉樹”用的最廣泛，二叉樹就是規定一個根只能有兩個葉子。

所以在圖論中，為了簡化這種結構，分為有向圖和無向圖兩大類，在無向圖中進一步進行約束形成了DAG（有向無環圖），所謂無環是指它是由集合的頂點和有向邊構成，每條邊連接一個頂點到另一個，這樣，在一些頂點v開始，沿著有序的邊，最終循環回再次到V是不可能的，其實圖是樹的一種泛化，真正在用的時候一般會通過深度優先或者廣度優先規則把圖拆成“森林”就是多顆“樹”，而DAG圖由于規則的定義更容易拆成一顆“樹”，這也就是為什么圖有很多種，而DAG應用最為廣泛的原因。

上圖從左到右分別是二叉樹、DAG圖、和普通有向圖的圖例，可以在最右側的圖明顯看到存在一個“環”，此圖可以非常容易的理解什么叫DAG圖了。

DAG與區塊鏈

目前采用DAG作為存儲結構的代表項目有dagcoin、Byteball、Iota，我看過前兩個的白皮書，dagcoin和byteball白皮書在DAG部分完全一致看其中一個即可，很多人說采用了DAG已經不屬于區塊鏈了，因為傳統區塊鏈采用“鏈”式結構，其實傳統區塊鏈中存在多條鏈的分支更類似一棵樹，而最終確認的是最長鏈，也就是在樹的結構中找到一條合法的鏈而已。

而采用了DAG結構的項目，為了避免雙花問題，還是有所謂的”主鏈“概念，其實就是經過見證人認定的最短路徑了，所以我認為DAG還是應該歸類到區塊鏈范疇，其本質沒有大的改變，只是采用了DAG結構，效率更好，對于沒有”異議“的交易，可以采用DAG進行打包，Byteball將其定義為”球“，圖論中有詳細的描述，也是為了減少復雜度，如下圖：

相比傳統鏈式結構，采用DAG面臨的雙花問題會非常復雜，根據Byteball的描述，采用了見證人主鏈概念，維持一條公認的主鏈作為憑證，而其他分支只要不和主鏈沖突都可以視為有效交易，我個人認為采用DAG并不能減少目前區塊鏈面臨的存儲空間問題，當然DAG可以提升效率，由于其數據結構非常復雜，對編碼要求更高，安全性有待觀察，對于算力攻擊問題，我有個擔憂，希望與DAG研究深入的人交流，就是傳統鏈式結構，你必須保持持續的算力優勢才能更改交易，否則最終長鏈可以將短期算力優勢形成的鏈廢掉，但是采用DAG分塊的方式，你只需要在一定時間內的算力保持優先形成一個DAG塊，那么是不是今后所有的交易都會繼承這個錯誤呢？

區塊鏈最讓人感興趣的地方就是不斷的創新和敢于利用新技術，當然就數據結構理論從70年代以來基本上沒有什么變化，只是傳統的軟件項目很少利用到這些理論，計算機圖形學是我看到的利用復雜數據結構最多的地方，而且商業項目能用到B+樹已經是極限了，而區塊鏈的發展讓人驚喜，理論聯系實際的好榜樣！

最后說一句，區塊鏈技術終究是計算機技術的一種，沒有必要將其神話，所有的結構和實現都可以在《數據結構》本科教材中找到，但是要靈活運用在業務場景中，需要取舍和經過實踐檢驗。