什么是DAG，DAG應(yīng)該歸類(lèi)到區(qū)塊鏈里面嗎？

最近有人問(wèn)DAG相關(guān)的東西，今天就來(lái)說(shuō)說(shuō)關(guān)于DAG的話(huà)題，DAG是一個(gè)數(shù)據(jù)結(jié)構(gòu)名詞，有項(xiàng)目用了這種復(fù)雜的結(jié)構(gòu)來(lái)存儲(chǔ)交易數(shù)據(jù)，本文只能粗略探討一下

如果你還記得大學(xué)開(kāi)設(shè)的《數(shù)據(jù)結(jié)構(gòu)》科目，DAG出現(xiàn)在那本書(shū)的最后一章“圖論”中，圖應(yīng)該是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)了，所以當(dāng)時(shí)我們學(xué)校并沒(méi)有教最后一章，只是讓感興趣的人自學(xué)，由于后來(lái)的工作中最多用到B+樹(shù)，對(duì)于圖的學(xué)習(xí)只是停留在表面，只是記得存儲(chǔ)圖最好的方式是采用“鄰接多重表”這種結(jié)構(gòu)。

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

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

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

目前采用DAG作為存儲(chǔ)結(jié)構(gòu)的代表項(xiàng)目有dagcoin、Byteball、Iota，我看過(guò)前兩個(gè)的白皮書(shū)，dagcoin和byteball白皮書(shū)在DAG部分完全一致看其中一個(gè)即可，很多人說(shuō)采用了DAG已經(jīng)不屬于區(qū)塊鏈了，因?yàn)閭鹘y(tǒng)區(qū)塊鏈采用“鏈”式結(jié)構(gòu)，其實(shí)傳統(tǒng)區(qū)塊鏈中存在多條鏈的分支更類(lèi)似一棵樹(shù)，而最終確認(rèn)的是最長(zhǎng)鏈，也就是在樹(shù)的結(jié)構(gòu)中找到一條合法的鏈而已。

而采用了DAG結(jié)構(gòu)的項(xiàng)目，為了避免雙花問(wèn)題，還是有所謂的”主鏈“概念，其實(shí)就是經(jīng)過(guò)見(jiàn)證人認(rèn)定的最短路徑了，所以我認(rèn)為DAG還是應(yīng)該歸類(lèi)到區(qū)塊鏈范疇，其本質(zhì)沒(méi)有大的改變，只是采用了DAG結(jié)構(gòu)，效率更好，對(duì)于沒(méi)有”異議“的交易，可以采用DAG進(jìn)行打包，Byteball將其定義為”球“，圖論中有詳細(xì)的描述，也是為了減少?gòu)?fù)雜度，如下圖：

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

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

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