logo

如何基於DAG實現智能合約

瀏覽數

2

簡介

DAG(有向無環圖)是一種非線性數據結構,可以替代區塊鏈,用於分布式賬本的存儲。這種結構在並發的場景下有更好的性能表現,但在實際應用中會面臨更多的技術挑戰。其中,最大的挑戰在於,基於DAG結構實現智能合約,要比基於區塊鏈結構困難得多。本文將討論DAG和區塊鏈這兩種賬本結構,在加密貨幣和智能合約兩個場景下的不同,以及如何基於DAG來實現智能合約。

加密貨幣的基本概念

首先,我們先從最簡單的場景出發——加密貨幣。加密貨幣是一個分布式數據庫,存儲了每個賬戶的余額信息。在加密貨幣網絡上運行著很多台計算機,這些計算機稱為節點(Node)。每一個節點都會存儲一份關於賬戶余額的數據,這份數據通常被稱為“狀態”(State)。

與傳統的中心化銀行系統不同,這種分布式賬本要求所有節點對狀態達成某種共識。或者說,對任意一個賬戶來說,要求這個網絡上每台計算機所存儲的余額都是一致的。由於狀態的數據量比較大,在網絡上傳輸全部數據非常困難,因此,在這種系統中,往往只傳輸那些能夠引起狀態變化的事件,也就是“交易”(Transaction)。想想看,你的錢不會無緣無故的增加或減少,只有在別人向你付款,或者你向別人付款的時候,賬戶余額才會發生變化。因此,只要知道一個賬戶所有歷史轉賬(Transfer)記錄,就可以很容易計算出當前的余額。

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

區塊鏈和DAG

區塊鏈是一種經典的賬本結構,廣泛應用於比特幣、以太坊等去中心化系統。它將一組交易打包成區塊(Block),通過哈希引用將區塊組織成一個鏈式結構。而DAG是在區塊鏈的基礎上擴展出來的另外一種賬本結構。在DAG賬本中,一個區塊通常只包含一個交易,它們彼此之間通過哈希引用,構成一種有向圖結構,並且保證圖中不存在環路。

DAG賬本有很多不同的變體。例如,任意一個交易均引用兩個其他交易作為其前驅節點,所構成的DAG被稱為“Tangle”,應用於IOTA等項目;在另外一種DAG結構中,交易被組織成若幹條鏈,並通過一些成對的交易彼此鏈接,這種DAG被稱為“Block Lattice”,應用於Nano、Vite等項目。大部分人沒有意識到,事實上,區塊鏈結構也是DAG的一個特例。

vrC6KOrKVDUuofjk6pqe4r8gbYPFNGW6wKYAcY4q.png

圖:基於不同數據結構來組織賬本
基於區塊鏈的加密貨幣
那麽問題來了,假如每個節點拿到的賬本是完全一樣的,那麽根據這個賬本計算出來的狀態是否也完全一樣呢?首先來看區塊鏈這種結構。在這種結構中,所有的交易都是有序的,改變任何兩個交易的順序,都會破壞區塊鏈的哈希引用關系,從而破壞賬本的有效性。因此,無論在哪個節點上進行計算,從同一個初始狀態出發,經歷同樣的轉賬交易序列,總會產生相同的結果。非常完美,不是嗎?無論是比特幣還是以太坊,節點之間不需要傳輸和比較龐大的狀態數據,只需要就賬本數據達成共識就行了。賬本中所包含的信息,就足夠一個節點計算出正確的狀態了。

wHoX4sBqptpR9oAcxVW5APt7fkp4fZ6SRI9bJuv1.png 

圖:基於區塊鏈賬本的加密貨幣
基於DAG的加密貨幣
我們在來看看DAG賬本,是不是還具有這樣的特性。好運氣還在,在DAG賬本中,雖然一些交易之間的順序從賬本中已經獲取不到了,但這些順序並不影響節點計算狀態。因為加密貨幣中的狀態計算,都是對余額的加減運算,這些運算是滿足交換律的,只要保證任何賬戶的余額不小於0,交易的先後是無所謂的。因此,無論如何遍歷DAG賬本,最終計算的賬戶余額數據都一樣,也就是說,任何節點都可以通過DAG賬本來恢覆正確的狀態。

cbbtz00XFYkcn02nV9YvRbZm7rSOv34mcihoraLV.png 

圖:基於DAG賬本的加密貨幣
基於DAG的智能合約
談完了加密貨幣,我們再來看看智能合約。在現實世界中,很多應用場景不像加密貨幣那樣只記錄一個余額就足夠了。例如飛機票預訂應用,在狀態中需要記錄一個航班上每一個座位的歸屬。這個時候,交易也不再僅僅表示轉賬了,可能包含任何對智能合約的請求數據,例如一張機票的預訂請求。這個時候,改變兩個交易的先後順序,就有可能產生不同的狀態。想想看,如果Alice和Bob都嘗試去預訂同一班飛機上的同一個座位,那麽這個座位將歸屬於先預訂的那個人。在智能合約的場景下,好運氣終結了,交易之間不再完全滿足交換律了。這就迫使我們不得不去認真對待賬本中每個交易之間的順序。

5ZzPKB0aLCwyQIFCKIA9o5OtoZNVBSuN3LmHdLpg.png 

圖:基於DAG賬本(Tangle)的智能合約
那麽,到底哪些交易是必須進行排序的,而哪些交易不用關註順序呢?最理想的情況是,寫一個函數,可以根據系統中部署的智能合約邏輯,判斷任何兩個交易順序是否會影響最終狀態。假如有這樣的函數存在,我們就可以在構造DAG賬本時,知道哪些交易之間必須建立一個哈希引用。或者通俗的說,在表示DAG賬本的圖中,明確的知道哪些圓圈之間必須加一個箭頭連接起來。遺憾的是,這個的函數的計算量非常大,無法用於現實的系統。所以我們只能放棄這種“完美”的方案,采用另一種更為簡單粗暴的方法。

構造對智能合約友好的DAG
為了給出一個簡單的交易排序規則,我們需要對系統做一些限制:
首先,我們將系統的狀態,或者稱“世界狀態”,看作是由每個賬戶的狀態組合而成的。其中任何兩個賬戶的狀態都是獨立的,不會互相影響。一個用戶的余額不會根據另一個用戶余額的變動而發生改變,一個合約的數據也不會受另一個合約影響。
然後,我們限制每一個交易只能影響一個賬戶的狀態。比如轉賬交易,在我們的方案中,一個交易要麽使某一個賬戶余額減少,要麽使某一個賬戶余額增加,而不能同時改變兩個賬戶的余額。也就是說,轉賬交易被拆分成“出賬交易”和“入賬交易”。同樣的,智能合約調用的交易也被拆分成“請求交易”和“響應交易”。
有了上面兩條限制,排序規則就變得簡單了:那些影響同一個賬戶狀態的交易之間必須進行排序;另外,一對“請求交易”和“響應交易”也必須滿足請求交易在響應交易之前。
按照這種規則進行排序的DAG賬本,每個賬戶都有一組有序的交易,或者說每個賬戶都擁有一條自己的區塊鏈,稱之為“賬戶鏈”。另外,不同的賬戶鏈之間也會通過一對請求-響應交易之間的順序建立起聯系。這種結構的DAG就是前文提到的“Block Lattice”。

DSCEqIYYuPvBzmRNxEjOH2Byu7thU9DzueIomMeb.png 

圖:基於DAG賬本(Block Lattice)的智能合約
基於這樣的賬本結構,你會發現,世界又恢覆了秩序。無論以什麽樣的順序遍歷DAG賬本,只要遵循賬本中記錄的交易順序,總可以計算出同樣的世界狀態。這也是Vite項目選擇這種結構作為賬本的原因。而采用Tangle結構實現智能合約,就必須引入另外一套排序規則。這在邏輯上相當於在原來DAG結構之外,針對同一組交易,另外建立一個不同的DAG結構,專門服務於智能合約,增加了工程實現上的難度。

總結
本文簡要描述了去中心化系統中的不同賬本結構,以及基於DAG結構實現加密貨幣和智能合約的區別。最後總結出一種在工程上易於實現智能合約的DAG結構。讀者如果希望探尋更多的細節,可以閱讀Vite白皮書(https://vite.org)。


作者簡介
劉春明,畢業於中國科技大學及中科院軟件所。資深技術專家,區塊鏈領域專家。曾任京東高級架構師,美團點評技術總監。現任Vite Labs創始人,中國區塊鏈應用研究協會常務理事。