Conflux 的自我进化：从 DAG 到树图| 对话伍鸣
Conflux?的身份不再是?DAG，它是樹圖。
受訪者：Conflux?CTO?伍鳴
采訪?&.撰文：李畫
這是一次特別的采訪。
采訪前我們想要?Conflux?的首席技術官伍鳴博士幫我們解答的疑問是：「DAG」與「鏈」的本質區別是什么？我們為什么要用它？它自身的局限性又在哪里？
采訪時伍鳴卻告訴我們，Conflux?已不再把自己歸類為?DAG，它的新身份是樹圖（Tree-Graph）。
不過我們的疑問依然被解答了，因為最有趣的地方就在于，Conflux?從?DAG?類別變更為樹圖類別的原因，恰恰能回答采訪前我們想要弄明白的那三個問題。甚至因為引入了樹圖概念，我們能從一個更高的角度來理解這些問題。
區塊鏈賬本的結構反映的是區塊與區塊之間的連接關系，而這種連接關系是由「指針」決定的。更科學的賬本分類方法不是基于它的形狀，而是基于其「指針」的類別、數量。
我們的采訪對象伍鳴是?Conflux?的聯合創始人，在加入?Conflux?之前任微軟亞洲研究院系統組資深研究員，主要的研究方向為分布式事務處理系統、圖計算引擎和人工智能平臺，他在分布式系統的設計和實現上擁有豐富的專業知識。
Conflux?是使用樹圖結構的公有鏈，其團隊成員大多擁有美國一流大學的留學背景和在硅谷、華爾街的多年工作經驗，有著突出的科研能力與技術能力。姚期智院士是?Conflux?團隊的首席科學家。
01
鏈、DAG、樹圖：結構不同能力不同?
問：DAG、樹圖這些非鏈式的賬本結構能被認為是區塊鏈嗎？
伍鳴：不管是鏈、DAG，還是樹圖，我們要通過它們解決的問題其實是一樣的，我們可以用區塊鏈技術這個詞把它們概括起來。
問：鏈結構、DAG?結構、樹圖結構的本質區別是什么？為什么?Conflux?是樹圖而不是?DAG？
伍鳴：你可以認為在鏈結構里，每個區塊只能有一個指針，這個指針是指向其父親區塊的，那么所有區塊就會一個接一個連起來，形成一個鏈狀的結構。
DAG?結構概括來講是指每個區塊有多于一個的指針，可以指向多于一個的其他區塊，形成的是一個有向無環的圖狀結構。
Conflux?的樹圖結構不同于鏈或?DAG?只有一類指針，它的每個區塊都有兩種指針，一種指針指向父親區塊，且只能有一個父親，與傳統的鏈式結構一樣；一種指針指向引用區塊，需要引用多個區塊，表達不同區塊間的?happens-before（先行發生）關系。
所以，在?Conflux?里有兩種類型的邊，父邊（父親指針確定的邊）和引用邊（引用指針確定的邊）。如果只看父邊，賬本的結構是一棵樹；如果同時看父邊和引用邊，賬本的結構是一個圖。樹圖結構就是指在圖中包含了一棵樹的這樣一種結構。
我們覺得如果繼續叫?DAG?可能會讓大家產生誤解，因為目前其他基于?DAG?的區塊鏈系統都只有一種類型的連接區塊或交易的邊，因此有了樹圖這個概念。樹圖它更接近于?Conflux?賬本結構的本質。
問：Conflux?為什么要引入兩種指針？三種不同賬本結構的區塊鏈系統會有何不同？
伍鳴：三種不同賬本結構下的區塊鏈系統最大的不同在于，它們對全序的支持或實現方式是不一樣的。
鏈結構支持全序，DAG?結構天然形成的是偏序，樹圖結構支持全序。
鏈結構中舍棄了分叉上的區塊，其主鏈上的區塊都有著唯一的父子關系，天然形成一個確定的順序，所有人都可以按照這個順序執行區塊里的交易，所有人最后都能夠達到一個一致的狀態。
DAG?結構中天然形成的是一個偏序。偏序的意思是說如果圖中的兩個區塊之間沒有直接的邊，或者兩個區塊之間不存在一條路徑，就沒有辦法確定這兩個區塊及它們所包含的交易間的順序。
不過?DAG?可以通過設計為區塊排出全序，現有的?DAG?有些支持全序有些不支持全序。
樹圖結構通過引入主鏈和?Epoch?的概念，實現了對區塊全序的支持，這也是Conflux?有兩種指針的原因。（如何實現全序將在下一節詳細介紹）
問：為什么要排全序，偏序會帶來什么問題？
伍鳴：一個區塊鏈系統，如果只需要處理普通的轉賬交易，又能通過指針保證并發交易間沒有因果關系，那它也許可以用偏序。
因為這種系統只需要處理加減操作，而加減操作是滿足交換律和結合律的，交易的執行順序對系統狀態沒有影響，系統最終的狀態是一致的。
但偏序不能支持智能合約，因為智能合約是圖靈完備的，它需要表達復雜的邏輯計算，它有乘法，一旦有乘法和加法就不會滿足交換律了。
也就是說，兩筆交易?A?和?B，先執行?A?后執行?B?得到的狀態與先執行?B?后執行?A?得到的狀態是不一樣的。偏序下兩筆交易有可能以任意的順序執行，那么不同的礦工就會得到不同的系統狀態，就無法取得共識。
如果一條鏈想要支持智能合約，就要支持全序。
問：既然為了實現全序要多做工作，為什么使用?DAG?或樹圖，而不是鏈結構？
伍鳴：區塊鏈會產生很多分叉，鏈結構是無法定義分叉上的區塊的執行順序的，它只能選擇丟掉分叉。
丟掉分叉會犧牲掉一些區塊，不僅浪費了資源，還制約了吞吐率；丟掉分叉也會犧牲一些安全性，因為在最長鏈共識機制下，分叉上的區塊是不能為最長鏈共識作出貢獻的，比如有很多好人區塊分叉的話，這些區塊就不能用來貢獻最長鏈，也就不能用來貢獻鏈的安全，壞人可以用更少的算力攻擊這條鏈。
樹圖和實現了全序的?DAG?把分叉區塊加入到賬本中，并定義了分叉上區塊的執行順序。
把所有的區塊都算進來，也就讓所有區塊都貢獻到系統的吞吐率上，這使得系統的瓶頸就不再是共識機制，而是網絡本身。只要網絡足夠快，系統的性能就還能再高，從而使得整個系統在不犧牲安全性的同時獲得更高的吞吐率。
02
Conflux 如何實現全序
問：Conflux?如何實現全序？
伍鳴：Conflux?是通過引入主鏈這個概念最終實現全序的。我們之前講過每個區塊都有兩種指針，其中一種是指向父親區塊的，這種指針決定的賬本結構是一棵樹，通過這棵樹可以確定一條主鏈。
具體實現上，Conflux?采用了?Ghost?和?Epoch?這兩種規則。Ghost?規則用來確定主鏈，Epoch?規則用來確定區塊的順序，兩者結合，就能實現區塊的全序。
問：Ghost?如何確定主鏈？
伍鳴：Ghost?從創世區塊開始，迭代的去從孩子區塊中選擇放在主鏈上的下一個區塊，選擇規則是挑選擁有最大子樹的孩子區塊為主鏈區塊。
如下圖所示，區塊?A?和區塊?B?是創世區塊的兩個孩子區塊。A?子樹有6個區塊，B?子樹有5個區塊，所以選擇區塊?A?作為緊接著創世區塊的主鏈上的區塊。根據同樣的規則，把區塊?C,E,H?都選擇進了主鏈。
（圖中實線箭頭指向父親區塊，虛線箭頭指向引用區塊）
問：Epoch?如何實現對區塊的排序？
伍鳴：Conflux?中的每個新區塊在產生時，除了選擇主鏈（該區塊觀察到的主鏈）上的最后一個區塊作為自己的父親區塊外，還必須把所有自己觀察到的但還沒有被其他區塊引用的區塊引用起來，表達不同區塊之間的?happens-before?的關系。
如上圖所示，如果一個機器節點在產生區塊E的時候，發現系統中已經有了區塊D，而且這個時候區塊?D?還未被任何其他區塊引用，那么區塊?E?就把自己的引用指針指向區塊?D，也就是說在區塊E和區塊?D?之間加上一個有向的引用邊，表示?D?是在?E?之前產生的。
主鏈上的每一個區塊確定一個?Epoch。在分叉上的區塊屬于哪個?Epoch，是由第一個產生在它之后的主鏈區塊所在的?Epoch?決定的。比如區塊?D?屬于?Epoch?E，因為?D?最先被?E?引用，所以產生在?E?之前，但是?D?并不產生在?C?之前。
問：在同一個?Epoch?內，區塊間的順序是如何確定的？
伍鳴：在每一個?Epoch?內部，Conflux?用拓撲排序確定區塊間的順序。如果出現平局，再根據區塊的哈希值來排序。
如此一來，通過?Ghost?規則確定主鏈，通過?Epoch?規則確定區塊的大體順序，通過拓撲和哈希排序實現同一?Epoch?內區塊的順序，最終，Conflux?的樹圖結構賬本提供了一個一致的區塊全序。
03
DAG 和樹圖引發的思考
問：如果多個節點同時出塊，這些區塊又都有效，會不會同一時間段產生大量區塊？這樣一來，每個區塊中引用指針占的空間會不會變得很大？?
伍鳴：不會的，實際上整個系統的出塊率是固定的，我們會動態的去調整出塊難度，出塊率很高，我們就增加難度把它降下來，出塊率很低，我們就減少難度讓它增上去。
問：如果多個節點同時出塊，并發區塊中應該會包含相同的交易，怎么解決重復打包交易的問題？
伍鳴：Conflux?采用的是混合策略（Mixed-Strategy，博弈論中的一種策略），礦工們根據交易費的選擇權重隨機地從交易等待池中選取交易。隨機是比較抽象的一個描述，它實際上很復雜，礦工會跟隨這種隨機方法選取交易，讓自己打包交易獲得的回報最大化。
當然不可能完全避免重復，交易池的交易越多重復概率越小，在正常情況下可能有30%左右的交易重復。如果交易池里的交易很少，比如說最極端的情況，只有一個交易，那當然是會重復的，因為所有人都會打包這個交易。
問：如果多個節點同時出塊，有沒有可能發生交易沖突的問題？
伍鳴：一般我們說的交易沖突是指上一個交易把錢花光沒有余額了，但后面還有交易。Conflux?通過區塊全序保證了交易的執行順序，就會避免這個問題，如果發生在前邊的交易把錢花光了，就會讓它后邊的交易變為無效。
另一種情況是相同的交易有可能被打包到不同的區塊里，在這種情況下，Conflux?只接受在區塊全序中排在最開始位置的這筆交易，而把后面的交易變為無效。
問：因為賬本結構的復雜性，會不會出現不同節點賬本不一致的情況？
伍鳴：肯定是有的，但經過一段時間以后就能確定賬本。有一個公式可以算出主鏈區塊被統一的概率，大概五、六個?Epoch?后，賬本就能一致。
問：樹圖在51%攻擊上的安全性是怎么樣的？
伍鳴：Conflux?中只要主鏈定了，交易的全序就定了，攻擊者想發動51%攻擊、想改變交易的順序，就必須改變主鏈的順序。
因此在51%攻擊上，樹圖的安全性和?Ghost?鏈的安全性是差不多的。
Ghost?規則比最長鏈規則安全，Ghost?看的是子樹的權重，把分叉上的區塊也考慮到了，所有的區塊、所有的算力都貢獻到主鏈的選擇上，能夠嚴格地滿足51%這個概念。但最長鏈規則沒有考慮分叉鏈上算力的浪費。
問：在對礦工的激勵機制上，樹圖跟鏈式結構有什么不同？
伍鳴：有一種情況是樹圖中才會出現的。樹圖需要區塊去引用其他區塊，表達不同區塊之間的?happens-before?的關系，那有的區塊可能不去正常引用其他區塊，就是說看到其他區塊也不引用。這是我們不希望看到的情況。
另一種發生在樹圖上的欺騙行為在傳統的鏈上也會發生，就是產生區塊但不廣播，偷偷挖一個私有的鏈，等到某個時機再放出去。
在這兩種情況下，這些不正常區塊的并發區塊會變得很多，因為它們和其他區塊之間缺少?happens-before?關系。Conflux?以此為依據去懲罰這兩種行為：并發區塊的個數越多，礦工獲得的獎勵越少。
04
結束語
鏈式結構放棄了分叉上的區塊，這樣做雖然犧牲了一定的吞吐率，卻保證了交易的全序。DAG?把分叉上的區塊都納入到賬本中，這樣做雖然不再浪費算力，卻引入了一個如何對區塊排序的難題。
有的?DAG?干脆不對區塊排序，因為在一些應用場景下，交易的全序可能并不那么重要，比如?IOTA。其他?DAG?則需要設計一種方法，實現對區塊的排序。比如?Byteball?、Hashgraph。
當我們深入地去了解不排全序的?DAG、排全序的?DAG、排全序?DAG?的不同排序方法，以及這些?DAG?采用的不同賬本結構，就會發現它們是截然不同的。
或許正因如此，Conflux?不再把自己歸類為?DAG，而具有兩種不同類別指針的它也確實與?DAG?有著不小的區別，樹圖也許更接近其本質。
于是，這次帶著弄清?DAG?與鏈的差別開始的采訪，最后得出的結論是：不同DAG?項目的差別，比?DAG?與鏈的差別都大。
本文轉載自碳鏈價值
總結
以上是生活随笔為你收集整理的Conflux 的自我进化：从 DAG 到树图| 对话伍鸣的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Scrapy 第一次爬虫
- 下一篇： 【python基础】猜数字游戏