DAG（有向無環圖）是一種非線性數據結構，可以替代區塊鏈，用于分布式賬本的存儲。這種結構在并發的場景下有更好的性能表現，但在實際應用中會面臨更多的技術挑戰。

其中，最大的挑戰在于，基于DAG結構實現智能合約，要比基于區塊鏈結構困難得多。

本文將討論DAG和區塊鏈這兩種賬本結構，在加密貨幣和智能合約兩個場景下的不同，以及如何基于DAG來實現智能合約。

在談什么是DAG之前，讓我們先從最簡單的場景出發——加密貨幣。加密貨幣是一個分布式數據庫，存儲了每個賬戶的余額信息。在加密貨幣網絡上運行著很多臺計算機，這些計算機稱為節點（Node）。每一個節點都會存儲一份關于賬戶余額的數據，這份數據通常被稱為「狀態」（State）。

與傳統的中心化銀行系統不同，這種分布式賬本要求所有節點對狀態達成某種共識。或者說，對任意一個賬戶來說，要求這個網絡上每臺計算機所存儲的余額都是一致的。

由于狀態的數據量比較大，在網絡上傳輸全部數據非常困難，因此，在這種系統中，往往只傳輸那些能夠引起狀態變化的事件，也就是「交易」（Transaction）。

想想看，你的錢不會無緣無故的增加或減少，只有在別人向你付款，或者你向別人付款的時候，賬戶余額才會發生變化。因此，只要知道一個賬戶所有歷史轉賬（Transfer）記錄，就可以很容易計算出當前的余額。

在加密貨幣系統中，所有發生過的轉賬交易，都記錄在一個被稱為「賬本」（Ledger）的數據結構中。這種賬本通過密碼學的方式進行了某種加密，使得每一個節點都可以驗證自己獲取的賬本數據是不是被篡改過。

區塊鏈和DAG

說完了加密貨幣，那么它跟DAG有什么關系呢？

首先，要知道區塊鏈是一種經典的賬本結構，廣泛應用于比特幣、以太坊等去中心化系統。它將一組交易打包成區塊(Block)，通過哈希引用將區塊組織成一個鏈式結構。

而DAG是在區塊鏈的基礎上擴展出來的另外一種賬本結構。在DAG賬本中，一個區塊通常只包含一個交易，它們彼此之間通過哈希引用，構成一種有向圖結構，并且保證圖中不存在環路。

DAG賬本有很多不同的變體。例如，任意一個交易均引用兩個其他交易作為其前驅節點，所構成的DAG被稱為「Tangle」，應用于IOTA等項目；在另外一種DAG結構中，交易被組織成若干條鏈，并通過一些成對的交易彼此鏈接，這種DAG被稱為「Block Lattice」，應用于Nano、Vite等項目。

然而，大部分人沒有意識到，事實上，區塊鏈結構也是DAG的一個特例。

基于不同數據結構來組織賬本

基于區塊鏈的加密貨幣

那么問題來了，假如每個節點拿到的賬本是完全一樣的，那么根據這個賬本計算出來的狀態是否也完全一樣呢？

首先來看區塊鏈這種結構。在這種結構中，所有的交易都是有序的，改變任何兩個交易的順序，都會破壞區塊鏈的哈希引用關系，從而破壞賬本的有效性。

因此，無論在哪個節點上進行計算，從同一個初始狀態出發，經歷同樣的轉賬交易序列，總會產生相同的結果。看起來非常完美，不是嗎？

無論是比特幣還是以太坊，節點之間不需要傳輸和比較龐大的狀態數據，只需要就賬本數據達成共識就行了。賬本中所包含的信息，就足夠一個節點計算出正確的狀態了。

基于區塊鏈賬本的加密貨幣

?基于DAG的加密貨幣

我們再來看看DAG賬本，是不是還具有這樣的特性。好運氣還在，在DAG賬本中，雖然一些交易之間的順序從賬本中已經獲取不到了，但這些順序并不影響節點計算狀態。

因為加密貨幣中的狀態計算，都是對余額的加減運算，這些運算是滿足交換律的，只要保證任何賬戶的余額不小于0，交易的先后是無所謂的。

因此，無論如何遍歷DAG賬本，最終計算的賬戶余額數據都一樣，也就是說，任何節點都可以通過DAG賬本來恢復正確的狀態。

?基于DAG賬本的加密貨幣

基于DAG的智能合約

看完了加密貨幣，我們再來看看智能合約。

在現實世界中，很多應用場景不像加密貨幣那樣只記錄一個余額就足夠了。例如飛機票預訂應用，在狀態中需要記錄一個航班上每一個座位的歸屬。這個時候，交易也不再僅僅表示轉賬了，可能包含任何對智能合約的請求數據，例如一張機票的預訂請求。

這個時候，改變兩個交易的先后順序，就有可能產生不同的狀態。想想看，如果Alice和Bob都嘗試去預訂同一班飛機上的同一個座位，那么這個座位將歸屬于先預訂的那個人。

在智能合約的場景下，好運氣終結了，交易之間不再完全滿足交換律了。這就迫使我們不得不去認真對待賬本中每個交易之間的順序。

基于DAG賬本(Tangle)的智能合約

?那么，到底哪些交易是必須進行排序的，而哪些交易不用關注順序呢？最理想的情況是，寫一個函數，可以根據系統中部署的智能合約邏輯，判斷任何兩個交易順序是否會影響最終狀態。

假如有這樣的函數存在，我們就可以在構造DAG賬本時，知道哪些交易之間必須建立一個哈希引用。或者通俗的說，在表示DAG賬本的圖中，明確的知道哪些圓圈之間必須加一個箭頭連接起來。

不過遺憾的是，這個的函數的計算量非常大，無法用于現實的系統。所以我們只能放棄這種“完美”的方案，采用另一種更為簡單粗暴的方法。

構造對智能合約友好的DAG

為了給出一個簡單的交易排序規則，我們需要對系統做一些限制。

首先，我們將系統的狀態，或者稱“世界狀態”，看作是由每個賬戶的狀態組合而成的。其中任何兩個賬戶的狀態都是獨立的，不會互相影響。一個用戶的余額不會根據另一個用戶余額的變動而發生改變，一個合約的數據也不會受另一個合約影響。

然后，我們限制每一個交易只能影響一個賬戶的狀態。比如轉賬交易，在我們的方案中，一個交易要么使某一個賬戶余額減少，要么使某一個賬戶余額增加，而不能同時改變兩個賬戶的余額。也就是說，轉賬交易被拆分成“出賬交易”和“入賬交易”。同樣的，智能合約調用的交易也被拆分成“請求交易”和“響應交易”。

有了上面兩條限制，排序規則就變得簡單了：那些影響同一個賬戶狀態的交易之間必須進行排序；另外，一對「請求交易」和「響應交易」也必須滿足請求交易在響應交易之前。

按照這種規則進行排序的DAG賬本，每個賬戶都有一組有序的交易，或者說每個賬戶都擁有一條自己的區塊鏈，稱之為「賬戶鏈」。另外，不同的賬戶鏈之間也會通過一對請求-響應交易之間的順序建立起聯系。這種結構的DAG就是前文提到的「Block Lattice」。

基于DAG賬本(Block Lattice)的智能合約?

基于這樣的賬本結構，你會發現，世界又恢復了秩序。無論以什么樣的順序遍歷DAG賬本，只要遵循賬本中記錄的交易順序，總可以計算出同樣的世界狀態。

這也是Vite等項目選擇這種結構作為賬本的原因。而采用Tangle結構實現智能合約，就必須引入另外一套排序規則。這在邏輯上相當于在原來DAG結構之外，針對同一組交易，另外建立一個不同的DAG結構，專門服務于智能合約，增加了工程實現上的難度。