Trias網(wǎng)絡(luò)中的DAG數(shù)據(jù)結(jié)構(gòu)介紹

區(qū)塊鏈常用的是“區(qū)塊＋鏈”的數(shù)據(jù)結(jié)構(gòu)。簡單來說，所謂區(qū)塊，指的是單位時間內(nèi)由記賬者將交易記錄整體打一個包，新生區(qū)塊與上一個區(qū)塊銜接在一起，形成區(qū)塊鏈。比特幣，以太坊等項目采用的都是這種方式。

這種鏈狀結(jié)構(gòu)雖然具備比較簡單快速確認的優(yōu)點，但也存在著固有的頑疾。首當其沖的就是鏈狀結(jié)構(gòu)難以提高吞吐量，所以效率一直比較低，整個網(wǎng)絡(luò)中只能存在一條單鏈，無法并發(fā)執(zhí)行，如果區(qū)塊過小，勢必造成交易的大幅延遲，而區(qū)塊如果較大，又會造成數(shù)據(jù)量膨脹，普通節(jié)點用戶不堪重負，DDos攻擊等問題。此外，還存在能耗問題，安全問題等潛在問題。

DAG（Directed Acyclic Graph，有向無環(huán)圖）原本是計算機領(lǐng)域的一種常用的數(shù)據(jù)結(jié)構(gòu)，由于其具備良好的多線程特點，能夠?qū)^(qū)塊鏈從一維的線狀單點寫入升級為三維多點并行工作，現(xiàn)在成為區(qū)塊鏈世界中越來越重要的發(fā)展方向。

一、Trias中的DAG結(jié)構(gòu)

Trais采用雙層共識方法，即請求網(wǎng)絡(luò)吞吐時使用DAG，確認時使用鏈式結(jié)構(gòu)。因為DAG屬于異步通訊方式，如果把事務(wù)操作進行異步處理，那么就可以顯著的增加網(wǎng)絡(luò)吞吐量。因此Trias設(shè)計了DAG的吞吐緩存共識層。

這里解釋一下同步&異步通訊。同步通訊意味著客戶端和服務(wù)強耦合，與同步通訊相反，異步通訊不要求捆綁所有的服務(wù)和層，允許存在一定的時間差。舉一個例子，我喊朋友去吃飯，如果是同步通訊，朋友就得放下手中的事情，立刻響應(yīng)我的請求；而在異步通訊中，則允許朋友忙完手里的事情，再來跟我吃飯。

Trias中的StreamNet就是基于DAG系統(tǒng)的設(shè)計，其針對現(xiàn)有區(qū)塊鏈系統(tǒng)容易出現(xiàn)雙花、重放攻擊、交易速度慢、Coordinator的引入導致中心化等問題。以流式圖計算為基礎(chǔ)，設(shè)計出的一套新的DAG共識層。

在StreamNet中，它的每個節(jié)點（site）代表一個交易，而有向邊則代表交易之間的確認關(guān)系。如下圖所示，site0表示創(chuàng)世交易（Genesis），理論上講是100%被確認的交易。在圖中，site1表示其中的第一筆交易，被后續(xù)的site2，3，4確認。而未被確認的交易我們稱之為tip，如site6，就是一個TIp。

二、交易的實現(xiàn)過程

假如創(chuàng)世交易Genesis的初始數(shù)字資產(chǎn)為5，現(xiàn)在Genesis希望將1個數(shù)字資產(chǎn)轉(zhuǎn)賬給Alice，并在后續(xù)過程中將另外1個數(shù)字資產(chǎn)轉(zhuǎn)賬給Bob。那么，這個交易過程在StreamNet是如何確認的呢？

在這里，每一筆交易都必須找到兩個TIp交易來進行確認。例如Genesis轉(zhuǎn)賬給Alice的交易確認了Genesis本身，而Genesis在后續(xù)轉(zhuǎn)賬給Bob的交易則確認了Genesis本身和Genesis轉(zhuǎn)賬給Alice的交易。換言之，StreamNet上附著的每一筆交易都要做足夠的工作量證明，即PoW。

值得一提的是，雖然同樣用到了PoW，但這與比特幣挖礦不同。這個過程難度不會隨著交易多少而增減，也不會產(chǎn)生“礦工”這個角色。

如果其中某一步產(chǎn)生了差錯，如上述過程中，Genesis要把10個數(shù)字資產(chǎn)轉(zhuǎn)賬給Bob，顯然其賬戶中的數(shù)字資產(chǎn)并不夠10，正產(chǎn)情況下，這個過程會導致驗證失敗。倘若選擇欺騙，或者篡改數(shù)據(jù)，就會導致在后續(xù)的交易過程中被其他節(jié)點拒絕驗證。

三、如何選擇TIp

在StreamNet中有交易速率的概念，用λ來表示。另外，我們用η來表示一筆交易在附著在StreamNet上后有多少時間單位沒有被其他交易確認。

在選擇TIp 上，我們至少要考慮兩個層面，一是選擇的算法不能太過復雜，否則會影響交易速率λ，二是要盡力照顧到全網(wǎng)中未被確認的交易，不能使一些交易在經(jīng)過太長時間后仍未被確認。

最基本的選擇算法就是從創(chuàng)世交易Genesis開始，對批準它的交易以均等的概率進行游走，直到選出一個tip為止。如上圖中Alice要把手中的數(shù)字資產(chǎn)轉(zhuǎn)賬給Sam，在選擇tip時，選擇創(chuàng)世交易Genesis轉(zhuǎn)賬給Alice和Bob的概率各為1/2。這種算法有一個問題，就是會產(chǎn)生懶交易，即新交易總是批準老交易而不被懲罰。

那么，有什么辦法來阻止懶交易呢？或者，什么樣的選擇算法才是好算法呢？