圖結(jié)構(gòu)算法研究背景

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

比特幣的效率瓶頸，主要在于其驗(yàn)證需基于最長(zhǎng)鏈的串行簽名。因?yàn)樵谝痪S度的鏈狀結(jié)構(gòu)中，區(qū)塊的產(chǎn)生嚴(yán)格按照時(shí)間順序產(chǎn)生，需要上一個(gè)區(qū)塊進(jìn)行廣播后才能產(chǎn)生下一個(gè)區(qū)塊，并且需要所有節(jié)點(diǎn)共同認(rèn)證，而這個(gè)過(guò)程較為漫長(zhǎng)。

為解決這個(gè)問(wèn)題，可以引入圖結(jié)構(gòu)DAG，降低了區(qū)塊產(chǎn)生過(guò)程的順序要求，有利于區(qū)塊產(chǎn)生過(guò)程的并行性，也就是說(shuō)，可能有兩個(gè)甚至更多的區(qū)塊共同產(chǎn)生。

提高并行性將會(huì)大大提高計(jì)算速率，突破共識(shí)算法的效率瓶頸，但同時(shí)也會(huì)帶來(lái)產(chǎn)生冗余或錯(cuò)誤區(qū)塊等不良影響，需要進(jìn)行總的排序和驗(yàn)證對(duì)它進(jìn)行篩選。因此基于DAG的共識(shí)算法的關(guān)鍵之處在于節(jié)點(diǎn)之間的聯(lián)系關(guān)系和最終正確區(qū)塊的選擇辦法。

下面我們分析一些具體的項(xiàng)目算法。

由以色列學(xué)者提出，可被視為最基本的DAG共識(shí)算法。它和最長(zhǎng)鏈共識(shí)算法的唯一區(qū)別在于引入了DAG圖狀結(jié)構(gòu)。區(qū)塊之間由最基本的父子節(jié)點(diǎn)進(jìn)行連接，并遵循最長(zhǎng)鏈算法，按照區(qū)塊的時(shí)間關(guān)系，當(dāng)鏈長(zhǎng)度相同時(shí)選擇時(shí)間較早的區(qū)塊。

其效率可以如上圖所示，紅色代表最優(yōu)效果，藍(lán)色表示采用圖計(jì)算的實(shí)際效果，綠色代表未采用的效果。

phantom

最大K聚類算法選擇區(qū)塊，其概要可歸納為：只有一個(gè)帶加入?yún)^(qū)塊的DAG圖的反錐面的節(jié)點(diǎn)數(shù)＜=K，即除該區(qū)塊鏈能到達(dá)的路徑上的區(qū)塊和能達(dá)到該區(qū)塊的路徑上的區(qū)塊外的其它區(qū)塊數(shù)，該區(qū)塊才能夠加入DAG。

在下圖中，加入DAG的是正確區(qū)塊，標(biāo)為藍(lán)色，而不加入DAG圖的是非正確區(qū)塊鏈，即可能是惡意或冗余區(qū)塊，標(biāo)注為紅色。

以該圖為例，比如節(jié)點(diǎn)I，I的錐面包括A，B，F(xiàn)，C，D，即能到達(dá)的節(jié)點(diǎn)數(shù)，而反錐面節(jié)點(diǎn)即是所有藍(lán)色節(jié)點(diǎn)減去錐面節(jié)點(diǎn)，只剩下G和J，只有2個(gè)。而E，H，K三個(gè)被認(rèn)為是冗余的，不予以采信。

一言以蔽之，一個(gè)節(jié)點(diǎn)的反錐面越小，該節(jié)點(diǎn)與其它節(jié)點(diǎn)的聯(lián)系性越強(qiáng)。其優(yōu)點(diǎn)在于具有良好的擴(kuò)展性，但不能保證強(qiáng)的線性排序和livebess。即難度杜絕惡意挖礦，延遲發(fā)布的情況，在抵抗這種攻擊的能力略顯不足。

Specture

區(qū)塊間也是通過(guò)基本連接方式（即父子節(jié)點(diǎn)連接方式），主要通過(guò)一種區(qū)塊鏈投票算法，并優(yōu)先選擇所在錐面節(jié)點(diǎn)總數(shù)多的區(qū)塊排在前面，對(duì)區(qū)塊進(jìn)行總排序，如果兩個(gè)區(qū)塊相沖突，它將選擇總排序后未知靠前的區(qū)塊。

對(duì)于已經(jīng)有兩個(gè)區(qū)塊，X，Y，是將X還是Y放在前面呢？因?yàn)閰^(qū)塊6-8可以看到區(qū)塊X，看不到區(qū)塊Y，他們會(huì)把X排在前面，同樣的，區(qū)塊9-11只能看到區(qū)塊Y，它們會(huì)把區(qū)塊Y排在前面，區(qū)塊12根據(jù)圖結(jié)構(gòu)認(rèn)為X排在前面，而區(qū)塊1-5一致認(rèn)為X在前面是因?yàn)榻Y(jié)構(gòu)中更多的區(qū)塊都認(rèn)為X應(yīng)該在前面。

Conflux

該項(xiàng)目算法的連接方式在基本連接的基礎(chǔ)上，又加進(jìn)了索引連接。所謂索引連接，指的是此區(qū)塊之前發(fā)現(xiàn)其他區(qū)塊（非父子）也會(huì)連接在一起，在此基礎(chǔ)上也能大幅度提升效率。據(jù)悉，清華姚班曾參與一次實(shí)驗(yàn)，在亞馬遜EC2云用2萬(wàn)臺(tái)機(jī)器節(jié)點(diǎn)實(shí)驗(yàn)，達(dá)到5.76GB/h的吞吐率，每秒實(shí)現(xiàn)了6400個(gè)交易，吸引了國(guó)內(nèi)外許多資本的關(guān)注。

其算法依然是GHOST算法，與以太坊相似，GHOST算法是一種主鏈選擇協(xié)議，以包括子樹(shù)數(shù)目最多為基本原則，即根據(jù)這條路徑從根區(qū)塊對(duì)應(yīng)鏈上節(jié)點(diǎn)連接的節(jié)點(diǎn)總數(shù)決定。

Snowflake to Avalanche

該項(xiàng)目區(qū)塊之間由基本的連接方式（父子區(qū)塊）所連接，根據(jù)隨機(jī)查詢和基于DAG圖的二著色的顏色信心值選擇正確的交易。

每個(gè)節(jié)點(diǎn)初始化都是無(wú)色的，每個(gè)節(jié)點(diǎn)隨機(jī)查詢周圍的其他節(jié)點(diǎn)，對(duì)周邊節(jié)點(diǎn)的顏色（紅色或藍(lán)色）進(jìn)行統(tǒng)計(jì)，在查詢K次之后，選擇顏色統(tǒng)計(jì)大的作為自己的顏色，并對(duì)改變的顏色信心值加1.

在引入DAG圖之后，其中的每個(gè)節(jié)點(diǎn)在改變顏色的同時(shí)，都會(huì)更新祖先交易的信心值（加1），并更新祖先提交的優(yōu)先（perfer）交易。

倘若交易中的所有祖先交易（父節(jié)點(diǎn)，或父節(jié)點(diǎn)之上的節(jié)點(diǎn)）均為優(yōu)先（prefer），則該交易為強(qiáng)優(yōu)先，系統(tǒng)隨機(jī)選擇一個(gè)節(jié)點(diǎn)查詢一個(gè)交易，如果返回的是強(qiáng)優(yōu)先交易，則投票數(shù)量加1.

當(dāng)該交易投票數(shù)達(dá)到一定的閾值，或者交易通過(guò)到達(dá)一定數(shù)量的成功查詢，則該交易被判定為正確。

結(jié)語(yǔ)

方躍堅(jiān)副教授對(duì)上述5個(gè)項(xiàng)目算法進(jìn)行了簡(jiǎn)明的介紹，并表示現(xiàn)在的國(guó)內(nèi)外基于圖結(jié)構(gòu)的算法研究方興未艾，還有很多極具創(chuàng)意的新興算法有待研究。Trias CTO 魏明也指出，現(xiàn)在硅谷的許多投資機(jī)構(gòu)都已經(jīng)把注意力從人工智能轉(zhuǎn)移到區(qū)塊鏈。