摘要：同時因為所有節(jié)點都是對等節(jié)點，避免了潛在的攻擊風(fēng)險。創(chuàng)建輪次一個事件的創(chuàng)建輪次是或者，其中是該事件父節(jié)點的最大輪次。

在深入探索Hashgraph之前，我們先聊聊關(guān)于共識協(xié)議的背景，眾所周知比特幣和以太坊目前都采用POW共識機制，如果暫不考慮大礦場聯(lián)合做些小動作，工作量證明機制確實是個非常安全的協(xié)議，簡單粗暴的算法設(shè)計從經(jīng)濟收益層面杜絕了幾乎99%的潛在攻擊，比特幣網(wǎng)絡(luò)從2009年運行至今幾乎沒出過什么嚴(yán)重的BUG，即使從軟件代碼上來看也稱得上是一個相當(dāng)可靠的系統(tǒng)。然而隨著整個網(wǎng)絡(luò)資源規(guī)模飛速增長，POW機制帶來的資源消耗問題越來越難以忽視。摩根士丹利在2018年1月發(fā)布的一份研究報告中指出，2017年比特幣挖礦業(yè)務(wù)共消耗了36太瓦時的能源，相當(dāng)于卡塔爾一年的能源消耗量，預(yù)計2018年的電力需求將增至三倍以上，與阿根廷全國一年能源消耗量相當(dāng)。POW機制引起的計算力消耗是否真的是毫無價值的能源浪費，對于這個問題社區(qū)存在不同的聲音（V神在不同場合都發(fā)表過對資源浪費問題的重視，以太坊也正在準(zhǔn)備向POS機制切換），小編對此保留意見，畢竟我不是專業(yè)的經(jīng)濟學(xué)家，但是對了達(dá)成全網(wǎng)共識是否真的需要消耗大量資源，我認(rèn)為將來一定會出現(xiàn)更有效率的解決方案。

? 再來看另一個應(yīng)用頗多的POS系，包括BM在多個項目里采用的DPOS機制，誠然在資源消耗方面有了相當(dāng)多的改進，但DPOS機制在去中心化方面遠(yuǎn)遠(yuǎn)不如POW，雖然牛逼如BM的大神多次提到一定數(shù)量的出塊節(jié)點足以保證全網(wǎng)去中心化同時大大提高交易處理能力，但是我相信有權(quán)力與利益集中的地方一定不會那么風(fēng)平浪靜，并且存在了相對中心化的節(jié)點后，相當(dāng)于是給攻擊者框定了攻擊目標(biāo)，DPOS能否抵御各種系統(tǒng)性風(fēng)險需要打個大大的問號。

? 要從根本上提高去中心化系統(tǒng)效率，共識協(xié)議一定是個繞不開的話題，很多團隊對此提出了很多不同的方案，Hashgraph就是其中之一，相比于其他還只有天馬行空的想法，Hashgraph已經(jīng)發(fā)布了可用的SDK。

? 根據(jù)白皮書定義，Hashgraph是一種數(shù)據(jù)結(jié)構(gòu)和共識算法。Hashgraph不是數(shù)字貨幣，也不是區(qū)塊鏈（因為它其實是DAG圖，并非是鏈?zhǔn)浇Y(jié)構(gòu)），嚴(yán)格說也不單單是協(xié)議。Hashgraph更像是一個底層的出塊層而非一個完整的系統(tǒng)。Hashgraph的SDK中包含一個數(shù)字貨幣的Demo，但那僅僅用于演示證明Hashgraph可以用于構(gòu)建數(shù)字貨幣。Hashgraph能為分布式APP提供高效、公平、安全的基礎(chǔ)設(shè)施。高吞吐量和異步拜占庭容錯（ABFT）的特點，使得Hashgraph在公鏈和私有鏈領(lǐng)域都有潛在的使用價值，并且，在保證去中心化的同時不需要繁重的工作量證明。

公平

采用一致的時間戳，每一個區(qū)塊（實際上是事件，下文會談到）以及區(qū)塊里的每一筆交易都有順序

安全

Hashgraph是一個ABFT系統(tǒng)，沒有一個節(jié)點可以阻止網(wǎng)絡(luò)達(dá)成共識或者在達(dá)成共識之后修改數(shù)據(jù)，號稱能達(dá)到銀行級別的安全性

速度

根據(jù)官網(wǎng)的測試數(shù)據(jù)，可以達(dá)到驚人的 250000 TPS

這里我們簡單講一下BFT算法，中文名拜占庭算法，不了解拜占庭將軍問題的可以上網(wǎng)搜索下。我們知道因為FLP不可能定理（在網(wǎng)絡(luò)可靠且存在節(jié)點失效的異步分布式系統(tǒng)中，不存在一個可以解決一致性問題的確定性算法），BFT算法中的節(jié)點通信基本都是同步的，并且雖然PBFT（實用拜占庭容錯）大大優(yōu)化了消息傳播的復(fù)雜度，但是實際使用中差不多也就支持到100個節(jié)點就是極限了，因此BFT算法只適用于非公鏈場景，其次它本身對動態(tài)節(jié)點場景的處理也非常麻煩，而節(jié)點隨意加入或者退出在公鏈環(huán)境下是非常常見的。那么Hashgraph究竟是如何實現(xiàn)異步BFT的呢，白皮書中hashgraph對共識定義做了一些放寬（還是得要適當(dāng)?shù)耐讌f(xié)啊~），在極小概率下共識算法可能會無限執(zhí)行，但是這一概率幾乎為0。Hashgraph的共識算法是非確定性的，但是能保證最終確定性，也就是說我雖然無法保證在某個時間點下所有節(jié)點狀態(tài)保持一致，但我能保證在最終某個時刻下所有節(jié)點對某個時間點之前的網(wǎng)絡(luò)歷史達(dá)成一致。同時因為所有節(jié)點都是對等節(jié)點，避免了潛在的DDOS攻擊風(fēng)險。

謠言算法（Gossip about Gossip）

虛擬投票（Virtual Voting）

謠言算法

謠言算法也叫八卦算法，在分布式系統(tǒng)中式非常常見的概念，這里的謠言或者八卦之的是一段我知道但是另一個人不知道的信息，顧名思義，算法運行原理和實際生活中辦公室八卦傳播類似，當(dāng)一個人知道一個八卦后，經(jīng)過有限時間傳播后，最后整個辦公室都會知道這一八卦。

在Hashgraph中，每一個節(jié)點都在傳播經(jīng)過簽名的新交易已經(jīng)從臨近節(jié)點接收到的交易信息。當(dāng)某個節(jié)點收到包含新交易信息的數(shù)據(jù)后，會組合并可能添加自己所知道的交易成為一個新的事件（event，類似于比特幣中的區(qū)塊Block，為了便于理解，下文中的事件和區(qū)塊都是指同一個東西）傳播出去，并且這個事件包含兩個哈希，一個指向該節(jié)點上次最新的事件，另一個指向該節(jié)點所收到的另一個節(jié)點的最新事件，然后對整個事件加上時間戳并簽名，整個循環(huán)不斷進行直到所有節(jié)點都獲得相同的信息。

假設(shè)網(wǎng)絡(luò)中有4個對等節(jié)點，P、Q、R、S，初始狀態(tài)下各自都有一個新的事件

Q節(jié)點隨機選擇S節(jié)點傳播消息，意思就是Q節(jié)點發(fā)送所有他自己知道而S不知道的信息給S，S確認(rèn)消息后創(chuàng)建一個新事件，同時指向S和Q的最新事件。

S節(jié)點隨機選擇Q傳播消息，這個消息包含三個事件

現(xiàn)在，Q節(jié)點收到了包含三個事件的消息，隨著消息在節(jié)點間不斷傳播，整個Hashgraph結(jié)構(gòu)可能會是以下樣子，這是一個通過加密哈希值連接的圖，因此叫做哈希圖（Hashgraph）

虛擬投票

上面我們看到了Hashgraph如何在節(jié)點之間通信，但這僅僅只是通信步驟，節(jié)點之間達(dá)成共識還需要虛擬投票機制，為什么說是虛擬投票，因為通過執(zhí)行謠言算法后所有節(jié)點都是全節(jié)點，都存儲了完整的網(wǎng)絡(luò)歷史，在需要對某一提案達(dá)成共識時并不需要大規(guī)模的消息通信，每個節(jié)點獨立執(zhí)行投票算法，并且所有節(jié)點一定會得出相同的共識結(jié)果。在討論具體的投票步驟前，有必要列下Hashgraph白皮書中描述的相關(guān)術(shù)語，不然真的會看得云里霧里，我將盡可能地說人話

事件（event）

在上面的謠言算法中我們已經(jīng)接觸到了這個概念，類似于比特幣中的區(qū)塊，事件是一個包含有兩個哈希指針的數(shù)據(jù)結(jié)構(gòu)，并且可以包括0個或若干交易信息，節(jié)點在創(chuàng)建事件的同時會加上時間戳并且對整個事件數(shù)字簽名

絕對多數(shù)（supermajority）

超過2/3以上節(jié)點的數(shù)量，在很多DPOS系算法上也有這個概念

可見（seeing）

當(dāng)事件B可以沿著哈希指針找到事件A，那么事件B就可見事件A

強可見（ strongly seeing）

當(dāng)事件B能找到事件A的所有路徑中跨越了絕對多數(shù)的節(jié)點，那么事件B強可見事件A。白皮書中提到經(jīng)過數(shù)學(xué)論證可以保證兩個強可見的節(jié)點在虛擬投票時能獲得一致的結(jié)果

見證人（witness）

每個節(jié)點在每個輪次中創(chuàng)建的第一個事件就是見證人事件，即該輪次的祖先事件，節(jié)點可能在某個輪次中沒有見證人事件

知名見證人（famous witness）

如果R輪的見證人能被絕對多數(shù)的R+1輪見證人可見，則它就是知名見證人。具體的計算方法詳見后文。

創(chuàng)建輪次（round created）

一個事件的創(chuàng)建輪次是R或者R+1，其中R是該事件父節(jié)點的最大輪次。當(dāng)且僅當(dāng)事件能強可見絕對多數(shù)的R輪見證人，則該事件的創(chuàng)建輪次為R+1。

接受輪次（round received）

如果R輪（創(chuàng)建輪次）中的所有知名見證人可見某一普通事件，則該事件的接受輪次就是R輪，如果某普通事件沒有被R輪所有知名見證人可見，則它的接受輪次一定晚于R輪

一個投票過程的例子

下圖已經(jīng)劃分好了各個創(chuàng)建輪次，圖中的DAG圖自下而上增長，關(guān)于如何劃分創(chuàng)建輪次后面會詳細(xì)談到，每個節(jié)點在同步到新事件后，可以立刻開始計算創(chuàng)建輪次

然后，我們按照見證人的定義標(biāo)記每輪次的見證人事件，如下：

對于每一個見證人，我們需要判斷它是否是知名見證人，我們以判斷B2事件是否是知名見證人為例，根據(jù)知名見證人的定義我們需要判斷A3、B3、C3和D3事件能夠可見B2，這其實就是一個選舉過程，每一個見證人都會對B2進行投票來決定B2是否知名。

A3事件可見B2，可見路徑如下黃線，我們可以說B2是A3的祖先事件，A3是B2的兒子事件或派生事件，A3可見B2，因此A3投票YES

同理其他3個見證人，經(jīng)過投票后所有見證人都投YES，因此我們預(yù)判B2事件將是知名見證人，但需要注意的是選舉過程并沒有結(jié)束哦，還有一步計票階段，計票必須由下一輪見證人完成，因此B4和D4將進行計票，雖然這幅圖中沒有A4和C4，但是隨著時間推移它們一定會出現(xiàn)并且也將參與計票

在計票階段，R+2輪見證人會從自己強可見的R+1見證人處收集投票結(jié)果，一旦某個投票結(jié)果的計票數(shù)量超過絕對多數(shù)即認(rèn)為該結(jié)果有效，也就是達(dá)成共識。根據(jù)數(shù)學(xué)理論證明，任何一個R+2輪見證人如果對投票結(jié)果做出了決定，那么這個結(jié)果就是全網(wǎng)的結(jié)論，如果這輪見證人無法做出決定，就由下一輪見證人計票決定，直到得出確切結(jié)論。具體來看個例子，B4到A3有三條可見路徑且跨越了3個節(jié)點，因此B4強可見A3事件，即B4從A3處收集到的投票結(jié)果是YES

同理可得，B4強可見B3、C3和D3事件

通過合計，B4事件收集到了4個YES投票，顯然我們可以得出結(jié)論：B2是知名見證人！我們將在圖中用綠色標(biāo)記出這些知名見證人。然后我們繼續(xù)對C2事件進行知名性判斷，由于C2下一輪的見證人投票結(jié)果為1YES，3NO，B4在計票后顯然會判定不是知名見證人，我們將C2標(biāo)記為藍(lán)色，同時白皮書有數(shù)學(xué)驗證可以保證所有其他見證人也做出同樣的決定。

值得一提的是，假如在下一輪無法做出決定（例如2:2的投票結(jié)果），則將延續(xù)到下一輪，根據(jù)數(shù)學(xué)定理只要我們在每十輪增加一個隨機輪次（coin round），則選舉過程最終一定會結(jié)束（以概率1收斂，通俗點說就是幾乎必然收斂，這是概率論中的概念）。在隨機輪中，收集到絕對多數(shù)結(jié)果的見證人僅投票而不做決定，而其他見證人則根據(jù)數(shù)字簽名的中間位進行隨機投票。我們繼續(xù)進行知名見證人的選舉，結(jié)果如下

一旦某個輪次確定了所有的知名見證人，就可以為這一輪次中的其他普通事件確定接受輪次和共識時間戳（consensus timestamp）。我們可以看到黑色事件可以被第二輪的所有知名見證人可見，因此它的接受輪次就是2

現(xiàn)在我們開始確定黑色事件的共識時間戳用于后續(xù)確定共識順序，尋找A節(jié)點最早的事件X，它既是A2的祖先也是黑色事件的兒子，同理尋找B節(jié)點的Y和D節(jié)點的Z。然后將XYZ事件的時間戳依次排序并取中位數(shù)作為黑色節(jié)點的共識時間戳。然后我們繼續(xù)確定其他節(jié)點的接受輪次

現(xiàn)在我們確定了10個接受輪次為2的事件，我們將為其排序得到全網(wǎng)公認(rèn)的順序，即共識順序。我們按照以下優(yōu)先級進行排序：

接受輪次

共識時間戳

按事件簽名和某隨機數(shù)異或的結(jié)果排序，這個隨機數(shù)通過該輪所有知名見證人的數(shù)字簽名進行異或運算得到

下面我們看一張共識算法的可視化圖，來自HashgraphDemo 應(yīng)用的運行結(jié)果，有興趣的同學(xué)可以下載官方的SDK包運行查看，SDK中包含若干個有趣的Demo（通過修改配置文件運行不同的demo）

$> java -jar swirlds.jar

? 前段時間我曾看到一篇文章說目前公鏈項目已經(jīng)扎堆得人滿為患了，是時候?qū)⒛抗饩劢沟絽f(xié)議層上，至少這里還不是那么擁擠，那么Hashgraph絕對是一個值得考慮的項目。需要注意的是，Hashrgaph目前并沒有開源，整個共識系統(tǒng)由一家商業(yè)軟件公司所有（Swirlds）。通過上文的分析，Hashgraph的共識過程相比于其他算法有很大的創(chuàng)新，有相當(dāng)?shù)陌踩碚撟C明，并且驗證簡單，同時其高并發(fā)低延遲的特性目前正在進行測試中。不過謠言算法真的適用于大規(guī)模公鏈環(huán)境依然值得商榷，而在私有鏈場景，Hashgraph已經(jīng)成功應(yīng)用于不少2B系統(tǒng)中。其次，在Hashgraph協(xié)議中所有節(jié)點必須保存全網(wǎng)數(shù)據(jù)，不知如何解決數(shù)據(jù)壓縮問題。不過總體來說，Hashgraph項目非常值得期待，在目前的測試數(shù)據(jù)來看，在許多場景下效果吊打大部分共識協(xié)議，技術(shù)細(xì)節(jié)論證嚴(yán)謹(jǐn)，團隊組建2年多，團隊老大Leemon Baird關(guān)于Hashgraph有多次精彩的公開演講，可以網(wǎng)上搜索。

最近的商業(yè)信息：

在2017年9月團隊獲得了來自NEA的300萬美元的種子投資

2017年10月有償授權(quán)美國信用聯(lián)盟使用hashgraph技術(shù)

社區(qū)熱度：

Twitter: 2.1 W

電報：2.7 W

Medium: 1.1 K

YouTube: 7.2 K

最后說一句，目前官方只允許合格投資者參與預(yù)售，這意味門檻非常高哦。開發(fā)人員和用戶可以參與到社區(qū)建設(shè)獲得代幣，具體信息關(guān)注官方渠道。