圖結構算法研究背景

眾所周知，現有的共識算法并不完美。以比特幣為例，比特幣采用的是PoW共識算法，而PoW算法面臨著嚴重的效率問題，而比特幣受限于共識算法和區塊容量，每分鐘只能處理約2000筆交易（一說是每秒7筆，主要取決于交易大小），相對緩慢的速率使得比特幣網絡上的擁堵成為常事。

比特幣的效率瓶頸，主要在于其驗證需基于最長鏈的串行簽名。因為在一維度的鏈狀結構中，區塊的產生嚴格按照時間順序產生，需要上一個區塊進行廣播后才能產生下一個區塊，并且需要所有節點共同認證，而這個過程較為漫長。

為解決這個問題，可以引入圖結構DAG，降低了區塊產生過程的順序要求，有利于區塊產生過程的并行性，也就是說，可能有兩個甚至更多的區塊共同產生。

提高并行性將會大大提高計算速率，突破共識算法的效率瓶頸，但同時也會帶來產生冗余或錯誤區塊等不良影響，需要進行總的排序和驗證對它進行篩選。因此基于DAG的共識算法的關鍵之處在于節點之間的聯系關系和最終正確區塊的選擇辦法。

下面我們分析一些具體的項目算法。

由以色列學者提出，可被視為最基本的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 魏明也指出，現在硅谷的許多投資機構都已經把注意力從人工智能轉移到區塊鏈。