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

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

什么是DAG

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

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

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

DAG與區(qū)塊鏈

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

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

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

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

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