背景
在深入探索Hashgraph之前止剖，我們先聊聊關(guān)于共識(shí)協(xié)議的背景亚茬，眾所周知比特幣和以太坊目前都采用POW共識(shí)機(jī)制郁岩，如果暫不考慮大礦場(chǎng)聯(lián)合做些小動(dòng)作耘拇，工作量證明機(jī)制確實(shí)是個(gè)非常安全的協(xié)議姐军，簡(jiǎn)單粗暴的算法設(shè)計(jì)從經(jīng)濟(jì)收益層面杜絕了幾乎99%的潛在攻擊铁材，比特幣網(wǎng)絡(luò)從2009年運(yùn)行至今幾乎沒(méi)出過(guò)什么嚴(yán)重的BUG，即使從軟件代碼上來(lái)看也稱得上是一個(gè)相當(dāng)可靠的系統(tǒng)奕锌。然而隨著整個(gè)網(wǎng)絡(luò)資源規(guī)模飛速增長(zhǎng)著觉，POW機(jī)制帶來(lái)的資源消耗問(wèn)題越來(lái)越難以忽視。摩根士丹利在2018年1月發(fā)布的一份研究報(bào)告中指出惊暴，2017年比特幣挖礦業(yè)務(wù)共消耗了36太瓦時(shí)的能源饼丘，相當(dāng)于卡塔爾一年的能源消耗量，預(yù)計(jì)2018年的電力需求將增至三倍以上辽话，與阿根廷全國(guó)一年能源消耗量相當(dāng)葬毫。POW機(jī)制引起的計(jì)算力消耗是否真的是毫無(wú)價(jià)值的能源浪費(fèi)，對(duì)于這個(gè)問(wèn)題社區(qū)存在不同的聲音（V神在不同場(chǎng)合都發(fā)表過(guò)對(duì)資源浪費(fèi)問(wèn)題的重視屡穗，以太坊也正在準(zhǔn)備向POS機(jī)制切換）贴捡，小編對(duì)此保留意見，畢竟我不是專業(yè)的經(jīng)濟(jì)學(xué)家村砂，但是對(duì)了達(dá)成全網(wǎng)共識(shí)是否真的需要消耗大量資源烂斋，我認(rèn)為將來(lái)一定會(huì)出現(xiàn)更有效率的解決方案。
? 再來(lái)看另一個(gè)應(yīng)用頗多的POS系础废，包括BM在多個(gè)項(xiàng)目里采用的DPOS機(jī)制汛骂，誠(chéng)然在資源消耗方面有了相當(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è)大大的問(wèn)號(hào)。
? 要從根本上提高去中心化系統(tǒng)效率芋绸，共識(shí)協(xié)議一定是個(gè)繞不開的話題媒殉，很多團(tuán)隊(duì)對(duì)此提出了很多不同的方案，Hashgraph就是其中之一摔敛，相比于其他還只有天馬行空的想法廷蓉，Hashgraph已經(jīng)發(fā)布了可用的SDK。
什么是 Hashgraph
? 根據(jù)白皮書定義马昙，Hashgraph是一種數(shù)據(jù)結(jié)構(gòu)和共識(shí)算法桃犬。Hashgraph不是數(shù)字貨幣刹悴，也不是區(qū)塊鏈（因?yàn)樗鋵?shí)是DAG圖，并非是鏈?zhǔn)浇Y(jié)構(gòu)）攒暇，嚴(yán)格說(shuō)也不單單是協(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í)不需要繁重的工作量證明琢歇。
三大特點(diǎn)
-
公平
采用一致的時(shí)間戳兰怠，每一個(gè)區(qū)塊（實(shí)際上是事件，下文會(huì)談到）以及區(qū)塊里的每一筆交易都有順序
-
安全
Hashgraph是一個(gè)ABFT系統(tǒng)李茫，沒(méi)有一個(gè)節(jié)點(diǎn)可以阻止網(wǎng)絡(luò)達(dá)成共識(shí)或者在達(dá)成共識(shí)之后修改數(shù)據(jù)揭保，號(hào)稱能達(dá)到銀行級(jí)別的安全性
-
速度
根據(jù)官網(wǎng)的測(cè)試數(shù)據(jù)，可以達(dá)到驚人的 250000 TPS
這里我們簡(jiǎn)單講一下BFT算法魄宏，中文名拜占庭算法秸侣，不了解拜占庭將軍問(wèn)題的可以上網(wǎng)搜索下。我們知道因?yàn)镕LP不可能定理（在網(wǎng)絡(luò)可靠且存在節(jié)點(diǎn)失效的異步分布式系統(tǒng)中宠互，不存在一個(gè)可以解決一致性問(wèn)題的確定性算法）味榛，BFT算法中的節(jié)點(diǎn)通信基本都是同步的，并且雖然PBFT（實(shí)用拜占庭容錯(cuò)）大大優(yōu)化了消息傳播的復(fù)雜度予跌，但是實(shí)際使用中差不多也就支持到100個(gè)節(jié)點(diǎn)就是極限了搏色，因此BFT算法只適用于非公鏈場(chǎng)景，其次它本身對(duì)動(dòng)態(tài)節(jié)點(diǎn)場(chǎng)景的處理也非常麻煩券册，而節(jié)點(diǎn)隨意加入或者退出在公鏈環(huán)境下是非常常見的频轿。那么Hashgraph究竟是如何實(shí)現(xiàn)異步BFT的呢，白皮書中hashgraph對(duì)共識(shí)定義做了一些放寬（還是得要適當(dāng)?shù)耐讌f(xié)啊~）烁焙，在極小概率下共識(shí)算法可能會(huì)無(wú)限執(zhí)行略吨，但是這一概率幾乎為0。Hashgraph的共識(shí)算法是非確定性的考阱，但是能保證最終確定性翠忠，也就是說(shuō)我雖然無(wú)法保證在某個(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)当娱。
兩大核心技術(shù)點(diǎn)
- 謠言算法（Gossip about Gossip）
- 虛擬投票（Virtual Voting）
工作原理
謠言算法
謠言算法也叫八卦算法，在分布式系統(tǒng)中式非常常見的概念考榨，這里的謠言或者八卦之的是一段我知道但是另一個(gè)人不知道的信息跨细，顧名思義，算法運(yùn)行原理和實(shí)際生活中辦公室八卦傳播類似河质，當(dāng)一個(gè)人知道一個(gè)八卦后冀惭，經(jīng)過(guò)有限時(shí)間傳播后，最后整個(gè)辦公室都會(huì)知道這一八卦掀鹅。
在Hashgraph中散休，每一個(gè)節(jié)點(diǎn)都在傳播經(jīng)過(guò)簽名的新交易已經(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è)通過(guò)加密哈希值連接的圖车要，因此叫做哈希圖（Hashgraph）
虛擬投票
上面我們看到了Hashgraph如何在節(jié)點(diǎn)之間通信允粤，但這僅僅只是通信步驟，節(jié)點(diǎn)之間達(dá)成共識(shí)還需要虛擬投票機(jī)制，為什么說(shuō)是虛擬投票类垫，因?yàn)橥ㄟ^(guò)執(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ù)語(yǔ)坞淮，不然真的會(huì)看得云里霧里，我將盡可能地說(shuō)人話:sweat_smile:
-
事件（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ù)字簽名
Nezn6.jpg
-
絕對(duì)多數(shù)（supermajority）
超過(guò)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)過(guò)數(shù)學(xué)論證可以保證兩個(gè)強(qiáng)可見的節(jié)點(diǎn)在虛擬投票時(shí)能獲得一致的結(jié)果
-
見證人（witness）
每個(gè)節(jié)點(diǎn)在每個(gè)輪次中創(chuàng)建的第一個(gè)事件就是見證人事件烹玉，即該輪次的祖先事件驰怎，節(jié)點(diǎn)可能在某個(gè)輪次中沒(méi)有見證人事件
-
知名見證人（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輪厉颤，如果某普通事件沒(méi)有被R輪所有知名見證人可見，則它的接受輪次一定晚于R輪
一個(gè)投票過(guò)程的例子
下圖已經(jīng)劃分好了各個(gè)創(chuàng)建輪次凡简，圖中的DAG圖自下而上增長(zhǎng)逼友，關(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è)選舉過(guò)程，每一個(gè)見證人都會(huì)對(duì)B2進(jìn)行投票來(lái)決定B2是否知名必怜。
A3事件可見B2肉拓，可見路徑如下黃線，我們可以說(shuō)B2是A3的祖先事件梳庆，A3是B2的兒子事件或派生事件暖途，A3可見B2，因此A3投票YES
同理其他3個(gè)見證人膏执，經(jīng)過(guò)投票后所有見證人都投YES驻售，因此我們預(yù)判B2事件將是知名見證人，但需要注意的是選舉過(guò)程并沒(méi)有結(jié)束哦更米，還有一步計(jì)票階段欺栗，計(jì)票必須由下一輪見證人完成，因此B4和D4將進(jìn)行計(jì)票征峦，雖然這幅圖中沒(méi)有A4和C4迟几，但是隨著時(shí)間推移它們一定會(huì)出現(xiàn)并且也將參與計(jì)票
在計(jì)票階段，R+2輪見證人會(huì)從自己強(qiáng)可見的R+1見證人處收集投票結(jié)果栏笆，一旦某個(gè)投票結(jié)果的計(jì)票數(shù)量超過(guò)絕對(duì)多數(shù)即認(rèn)為該結(jié)果有效类腮，也就是達(dá)成共識(shí)。根據(jù)數(shù)學(xué)理論證明蛉加，任何一個(gè)R+2輪見證人如果對(duì)投票結(jié)果做出了決定蚜枢，那么這個(gè)結(jié)果就是全網(wǎng)的結(jié)論，如果這輪見證人無(wú)法做出決定针饥，就由下一輪見證人計(jì)票決定厂抽，直到得出確切結(jié)論。具體來(lái)看個(gè)例子丁眼，B4到A3有三條可見路徑且跨越了3個(gè)節(jié)點(diǎn)筷凤，因此B4強(qiáng)可見A3事件，即B4從A3處收集到的投票結(jié)果是YES
同理可得户盯，B4強(qiáng)可見B3嵌施、C3和D3事件
通過(guò)合計(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)證可以保證所有其他見證人也做出同樣的決定族奢。
值得一提的是，假如在下一輪無(wú)法做出決定（例如2:2的投票結(jié)果）丹鸿，則將延續(xù)到下一輪越走，根據(jù)數(shù)學(xué)定理只要我們?cè)诿渴喸黾右粋€(gè)隨機(jī)輪次（coin round），則選舉過(guò)程最終一定會(huì)結(jié)束（以概率1收斂靠欢，通俗點(diǎn)說(shuō)就是幾乎必然收斂廊敌，這是概率論中的概念）。在隨機(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ù)通過(guò)該輪所有知名見證人的數(shù)字簽名進(jìn)行異或運(yùn)算得到
下面我們看一張共識(shí)算法的可視化圖，來(lái)自HashgraphDemo 應(yīng)用的運(yùn)行結(jié)果宴杀，有興趣的同學(xué)可以下載官方的SDK包運(yùn)行查看癣朗，SDK中包含若干個(gè)有趣的Demo（通過(guò)修改配置文件運(yùn)行不同的demo）:thumbsup:
$> java -jar swirlds.jar
結(jié)論
? 前段時(shí)間我曾看到一篇文章說(shuō)目前公鏈項(xiàng)目已經(jīng)扎堆得人滿為患了，是時(shí)候?qū)⒛抗饩劢沟絽f(xié)議層上旺罢，至少這里還不是那么擁擠旷余，那么Hashgraph絕對(duì)是一個(gè)值得考慮的項(xiàng)目。需要注意的是扁达，Hashrgaph目前并沒(méi)有開源正卧，整個(gè)共識(shí)系統(tǒng)由一家商業(yè)軟件公司所有（Swirlds）。通過(guò)上文的分析跪解，Hashgraph的共識(shí)過(guò)程相比于其他算法有很大的創(chuàng)新炉旷，有相當(dāng)?shù)陌踩碚撟C明，并且驗(yàn)證簡(jiǎn)單，同時(shí)其高并發(fā)低延遲的特性目前正在進(jìn)行測(cè)試中窘行。不過(guò)謠言算法真的適用于大規(guī)模公鏈環(huán)境依然值得商榷饥追，而在私有鏈場(chǎng)景，Hashgraph已經(jīng)成功應(yīng)用于不少2B系統(tǒng)中罐盔。其次但绕，在Hashgraph協(xié)議中所有節(jié)點(diǎn)必須保存全網(wǎng)數(shù)據(jù)，不知如何解決數(shù)據(jù)壓縮問(wèn)題惶看。不過(guò)總體來(lái)說(shuō)壁熄，Hashgraph項(xiàng)目非常值得期待，在目前的測(cè)試數(shù)據(jù)來(lái)看碳竟，在許多場(chǎng)景下效果吊打大部分共識(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ì)獲得了來(lái)自NEA的300萬(wàn)美元的種子投資
- 2017年10月有償授權(quán)美國(guó)信用聯(lián)盟使用hashgraph技術(shù)
社區(qū)熱度：
- Twitter: 2.1 W
- 電報(bào)：2.7 W
- Medium: 1.1 K
- YouTube: 7.2 K
最后說(shuō)一句诈泼，目前官方只允許合格投資者參與預(yù)售懂拾，這意味門檻非常高哦。開發(fā)人員和用戶可以參與到社區(qū)建設(shè)獲得代幣铐达，具體信息關(guān)注官方渠道岖赋。
更多信息敬請(qǐng)關(guān)注公眾號(hào) BlockGeeks
