摘要：同時(shí)因?yàn)樗泄?jié)點(diǎn)都是對(duì)等節(jié)點(diǎn)，避免了潛在的攻擊風(fēng)險(xiǎn)。創(chuàng)建輪次一個(gè)事件的創(chuàng)建輪次是或者，其中是該事件父節(jié)點(diǎn)的最大輪次。

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

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

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

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

公平

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

安全

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

速度

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

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

謠言算法（Gossip about Gossip）

虛擬投票（Virtual Voting）

謠言算法

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

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

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

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

S節(jié)點(diǎn)隨機(jī)選擇Q傳播消息，這個(gè)消息包含三個(gè)事件

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

虛擬投票

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

事件（event）

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

絕對(duì)多數(shù)（supermajority）

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

可見（seeing）

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

強(qiáng)可見（ strongly seeing）

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

見證人（witness）

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

知名見證人（famous witness）

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

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

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

接受輪次（round received）

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

一個(gè)投票過程的例子

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

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

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

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

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

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

同理可得，B4強(qiáng)可見B3、C3和D3事件

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

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

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

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

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

接受輪次

共識(shí)時(shí)間戳

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

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

$> java -jar swirlds.jar

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

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

在2017年9月團(tuán)隊(duì)獲得了來自NEA的300萬美元的種子投資

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

社區(qū)熱度：

Twitter: 2.1 W

電報(bào)：2.7 W

Medium: 1.1 K

YouTube: 7.2 K

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