在Trias同“北大軟微-八分量協同創新實驗室”聯合開展的學術沙龍上，北京大學方躍堅副教授同大家分享了《基於圖結構DAG（Directed Acylic Graphs)對共識演算法的價值的思考》。
以下是方教授帶來的此次分享內容：
圖結構演算法研究背景
眾所周知，現有的共識演算法並不完美。以比特幣為例，比特幣採用的是PoW共識演算法，而PoW演算法面臨著嚴重的效率問題，而比特幣受限於共識演算法和區塊容量，每分鐘只能處理約2000筆交易（一說是每秒7筆，主要取決於交易大小），相對緩慢的速率使得比特幣網路上的擁堵成為常事。
比特幣的效率瓶頸，主要在於其驗證需基於最長鏈的序列簽名。因為在一維度的鏈狀結構中，區塊的產生嚴格按照時間順序產生，需要上一個區塊進行廣播後才能產生下一個區塊，並且需要所有節點共同認證，而這個過程較為漫長。
為解決這個問題，可以引入圖結構DAG，降低了區塊產生過程的順序要求，有利於區塊產生過程的並行性，也就是說，可能有兩個甚至更多的區塊共同產生。
提高並行性將會大大提高計算速率，突破共識演算法的效率瓶頸，但同時也會帶來產生冗餘或錯誤區塊等不良影響，需要進行總的排序和驗證對它進行篩選。因此基於DAG的共識演算法的關鍵之處在於節點之間的聯絡關係和最終正確區塊的選擇辦法。
下面我們分析一些具體的專案演算法。
Inclusive blockchain protocols
由以色列學者提出，可被視為最基本的DAG共識演算法。它和最長鏈共識演算法的唯一區別在於引入了DAG圖狀結構。區塊之間由最基本的父子節點進行連線，並遵循最長鏈演算法，按照區塊的時間關係，當鏈長度相同時選擇時間較早的區塊。
其效率可以如上圖所示，紅色代表最優效果，藍色表示採用圖計算的實際效果，綠色代表未採用的效果。
phantom
最大K聚類演算法選擇區塊，其概要可歸納為：只有一個帶加入區塊的DAG圖的反錐面的節點數＜=K，即除該區塊鏈能到達的路徑上的區塊和能達到該區塊的路徑上的區塊外的其它區塊數，該區塊才能夠加入DAG。
在下圖中，加入DAG的是正確區塊，標為藍色，而不加入DAG圖的是非正確區塊鏈，即可能是惡意或冗餘區塊，標註為紅色。
以該圖為例，比如節點I，I的錐面包括A,B,F,C,D，即能到達的節點數，而反錐面節點即是所有藍色節點減去錐面節點，只剩下G和J，只有2個。而E,H,K三個被認為是冗餘的，不予以採信。
一言以蔽之，一個節點的反錐面越小，該節點與其它節點的聯絡性越強。其優點在於具有良好的擴充套件性，但不能保證強的線性排序和livebess。即難度杜絕惡意挖礦，延遲釋出的情況，在抵抗這種攻擊的能力略顯不足。
Specture
區塊間也是透過基本連線方式（即父子節點連線方式），主要透過一種區塊鏈投票演算法，並優先選擇所在錐面節點總數多的區塊排在前面，對區塊進行總排序，如果兩個區塊相沖突，它將選擇總排序後未知靠前的區塊。
對於已經有兩個區塊，X，Y，是將X還是Y放在前面呢？因為區塊6-8可以看到區塊X，看不到區塊Y，他們會把X排在前面，同樣的，區塊9-11只能看到區塊Y，它們會把區塊Y排在前面，區塊12根據圖結構認為X排在前面，而區塊1-5一致認為X在前面是因為結構中更多的區塊都認為X應該在前面。
Conflux
該專案演算法的連線方式在基本連線的基礎上，又加進了索引連線。所謂索引連線，指的是此區塊之前發現其他區塊（非父子）也會連線在一起，在此基礎上也能大幅度提升效率。據悉，清華姚班曾參與一次實驗，在亞馬遜EC2雲用2萬臺機器節點實驗，達到5.76GB/h的吞吐率，每秒實現了6400個交易，吸引了國內外許多資本的關注。
其演算法依然是GHOST演算法，與以太坊相似，GHOST演算法是一種主鏈選擇協議，以包括子樹數目最多為基本原則，即根據這條路徑從根區塊對應鏈上節點連線的節點總數決定。
Snowflake to Avalanche
該專案區塊之間由基本的連線方式（父子區塊）所連線，根據隨機查詢和基於DAG圖的二著色的顏色信心值選擇正確的交易。
每個節點初始化都是無色的，每個節點隨機查詢周圍的其他節點，對周邊節點的顏色（紅色或藍色）進行統計，在查詢K次之後，選擇顏色統計大的作為自己的顏色，並對改變的顏色信心值加1.
在引入DAG圖之後，其中的每個節點在改變顏色的同時，都會更新祖先交易的信心值（加1），並更新祖先提交的優先（perfer）交易。
倘若交易中的所有祖先交易（父節點，或父節點之上的節點）均為優先（prefer），則該交易為強優先，系統隨機選擇一個節點查詢一個交易，如果返回的是強優先交易，則投票數量加1.
當該交易投票數達到一定的閾值，或者交易透過到達一定數量的成功查詢，則該交易被判定為正確。
結語
方躍堅副教授對上述5個專案演算法進行了簡明的介紹，並表示現在的國內外基於圖結構的演算法研究方興未艾，還有很多極具創意的新興演算法有待研究。Trias CTO 魏明也指出，現在矽谷的許多投資機構都已經把注意力從人工智慧轉移到區塊鏈。
即使到現在，還有很多人認為區塊鏈就等於炒幣，其實並不然，與人工智慧，雲端計算，大資料一樣，區塊鏈也是近年來的一項新技術，只是此前外界賦予了它過多的金融屬性。Trias此後會繼續和北大軟微學院開展區塊鏈研討技術沙龍，也歡迎更多有識之士參與進來，分享大家的知識和見解，謝謝大家。
原作 | 方躍堅
整理 | 鄭辰
出品 | Trias團隊
