鯨准研究院 Hashgraph技術解析

新聞 06-13

JINGDATA REPORT

Hashgraph是一種全新的分散式賬本共識機制技術和數據結構，與以區塊為核心的區塊鏈技術相比，其更快、更公平和更安全。Hashgraph更像一個底層的出塊層而非一個完整的系統。

————————————————————

作者：

鯨准研究院譚瑩王帆陳泓伊

Node Capital研究中心林婕茵郎瀚威

（本報告由鯨准研究院 X Node Capital 聯合發布）

. 01 .

概述

1.1 區塊鏈的概念

傳統意義的區塊鏈是由一根鏈以線性方式鏈接一系列的區塊，這些區塊中記錄著一個時間段內發生的交易。礦工通過各種機制競爭這個時間段內交易的記賬權，對於一筆交易來說，需要足夠幸運或付出足夠多的手續費才能被礦工選中。如在比特幣網路中每10分鐘才出一個塊，平均每秒進行7次交易，以太坊雖然大大加快了出塊時間，但也需要十幾秒才能確認出一個塊。由於一筆交易的確認需要等待十幾秒甚至十分鐘，效率很低，因此區塊鏈1.0和2.0的項目對於大規模商用還有很長一段距離。

1.2 DAG的概念

如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，那麼這個圖就是一個有向無環圖（簡稱DAG）。有向無環圖打破了「區塊」的概念，其中的每一筆交易跳過了等待打包入塊的步驟，直接以單筆交易為單位計入鏈中。

然而，DAG網路面臨著控制網路寬度的問題，如果每一筆新的交易都鏈接到網路中比較老的某個交易節點上，那麼DAG網路就會從這一老節點突然變寬，效率變低。因此，最理想的狀態是，每一筆新交易都均勻的連接在鏈的新老節點上，將網路控制在一定的寬度內，包括IOTA在內的DAG網路都是這樣解決寬度問題的。

現有DAG項目的問題：

IOTA：

1. MIT報告指出，IOTA使用了自己開發的哈希演算法curl，但是curl演算法的哈希值極易發生碰撞，於是就能偽造數字簽名。

2. 因為共識是由全網交易確定的，那麼理論上來說，如果有人能夠產生1/3的交易量，他就可以將無效交易變成有效交易。另一方面，由於IOTA無手續費，所以沒有礦工激勵，IOTA面臨著拒絕服務攻擊和垃圾信息攻擊可能，就像不收物業費的小區，靠業主自治很難掃清不法份子。

3. IOTA引入閉源的中心化組件Coordinator來對全網交易進行檢查（例如雙花），如何有效移除Coordinator並建立一個具有良性激勵機制的去中心化「Coordinator群體」，IOTA還沒有給出解決方案。

Byteball：

由於主鏈演算法和見證人發布頻率有關係，交易確認的時間是不確定的；由於Byteball基於關係資料庫來存儲數據，SQL語言過於緊耦合演算法邏輯，在一定程度上限制了Byteball目前的擴展能力和速度。

NANO：

沒有被充分測試、缺乏同行評議，共識演算法可能有嚴重缺陷的風險。例如，如果沒有足夠的法定人數投票來解決網路衝突會發生什麼？如果NANO網路的某些部分長時間分離，當分離的網路重新加入時會發生什麼？重新加入的網路是否會在不可避免發生的投票過程中癱瘓？這些問題都有待測試驗證。

1.3 Hashgraph的概念

Hashgraph是以基於DAG網路來搭建的一種數據結構和共識演算法，但Hashgraph有著自己的控制寬度的方式，而且每個點可以有兩個父節點。在Hashgraph網路中，只有獲得准入的節點才有發起事件（Event）的權利，事件即為交易數據的容器，所有發起新事件的工作都需由這些節點完成，通過非鏈式結構無需競爭即可同步出塊，實現大規模低成本共識，大大提高了工作效率，控制了帶寬的同時，做到了真正的「Blockless」。據稱能夠實現超過25萬TPS，是低交易費、去中心化、無需挖礦的互聯網底層信任網路。

Hashgraph的數據結構示意圖如下，其中，Alice、Bob、Carol、Dave、Ed分別是五個有發起事件權力的節點，每個圓圈是一個事件，由節點在接收到八卦時創建，越靠近下方的越早發起的事件，越靠近上方是越新的事件。

Hashgraph開創性地在公鏈環境下做非同步BFT共識，傳統BFT的一大問題是消息複雜度太高，大量消耗系統的網路帶寬，無法很好的應對動態網路。這裡Hashgraph引入了傳統Gossip Protocol，並加以獨特的創新，另外再加上虛擬投票機制，這樣在需要共識的時候不會引起突發大規模消息傳遞風暴。

區塊鏈與Hashgraph的對比：

區塊鏈技術vs Hashgraph

. 02 .

Hashgraph技術

Hashgrapgh的共識機制包括兩個部分，Gossip about Gossip和Virtual Voting，以下將分別解釋二者的工作流程與總體共識機制的工作流程，並說明Hashgraph的優點和存在的問題。

2.1 Gossip about Gossip

Hashgrapgh的核心通信協議是「八卦八卦協議」（Gossip about Gossip），靈感來自辦公室八卦，這裡的八卦指的是一段我知道但是另一個人不知道的信息，只要兩個人之間八卦一下，在有限的時間內，所有的人都會知道該八卦的信息。

在Hashgraph中，每一個節點都在傳播經過簽名的新交易以及從臨近節點接收到的交易信息。當某個節點收到包含新交易信息的數據後，會組合併可能添加自己所知道的交易成為一個新的事件（Event，類似於區塊的概念，是一個包含有兩個哈希指針的數據結構，並且可以包括0個或若干交易信息）傳播出去，並且這個事件包含兩個哈希，一個指向該節點上次最新的事件，另一個指向該節點所收到的另一個節點的最新事件，然後對整個事件加上時間戳並簽名，整個循環不斷進行直到所有節點都獲得相同的信息。

如下圖所示，當 Bob 隨機找到了 Alice 八卦的時候，就會把自己當前所知道的一切都原原本本地告訴 Alice。然後 Alice 這裡會出一個新事件（紅點），這個新事件里除了加入新的交易事務的同時，還會加上兩個指向父事件的 hash 值，一個指向自己的最新事件（深藍），一個指向 Bob 和自己聊天時候最新的事件（天藍）。

本質上八卦演算法是一個帶冗餘的容錯演算法，更進一步，八卦是一個最終一致性演算法或提供一致性演算法的手段。雖然無法保證在某個時刻所有節點狀態一致，但可以保證在最終某個時刻，所有節點一致對某個時間點前的所有歷史達成一致。

Hashgraph的節點之間進行八卦的內容還包括節點間互相八卦的歷史記錄，於是每個節點都可以通過八卦維護一個哈希圖，這樣在節點計算共識投票的時候就可以發起虛擬投票，也就是計算其他節點在給定的哈希圖中會怎麼投票，從而不需要在網路上再做大量雙向同步通信去進行真實的投票。用Hashgraph發明者的話來說就是：「Hashgraph具備投票演算法的一切優點，然而避開了它的最大缺陷。」

由於Gossip協議迅速的收斂性(convergence propperty)，每條新的信息能夠以更快的方式到達每個節點，讓每個節點都維護著所有節點跟其他節點的通信歷史。

2.2 Virtual Voting

上面我們看到了Hashgraph如何在節點之間通信，在通過執行八卦演算法後，所有節點都是全節點，存儲了完整的網路歷史，在需要對某一提案達成共識時並不需要大規模的消息通信，每個節點可以獨立執行虛擬投票機制（Virtual Voting），並且所有節點一定會得出相同的共識結果。下面我們可以看到虛擬投票機制的詳細名詞定義與虛擬投票過程的演示範例，引用自《Hashgraph —— 或許是目前最為優秀的共識協議》一文。

名詞定義：

事件（event）

在上面的八卦演算法中我們已經接觸到了這個概念，類似於比特幣中的區塊，事件是一個包含有兩個哈希指針的數據結構，並且可以包括0個或若干交易信息，節點在創建事件的同時會加上時間戳並且對整個事件數字簽名。

絕對多數（supermajority）

超過2/3以上節點的數量，在很多DPoS系演算法上也有這個概念。

可見（seeing）

當事件B可以沿著哈希指針找到事件A，那麼事件B就可見事件A。

強可見（ strongly seeing）

當事件B能找到事件A的所有路徑中跨越了絕對多數的節點，那麼事件B強可見事件A。白皮書中提到經過數學論證可以保證兩個強可見的節點在虛擬投票時能獲得一致的結果。

見證人（witness）

每個節點在每個輪次中創建的第一個事件就是見證人事件，即該輪次的祖先事件，節點可能在某個輪次中沒有見證人事件。

知名見證人（famous witness）

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

創建輪次（round created）

一個事件的創建輪次是R或者R+1，其中R是該事件父節點的最大輪次。當且僅當事件能強可見絕對多數的R輪見證人，則該事件的創建輪次為R+1。

接受輪次（round received）

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

一個虛擬投票過程的例子：

下圖已經劃分好了各個創建輪次，圖中的DAG圖自下而上增長，關於如何劃分創建輪次後面會詳細談到，每個節點在同步到新事件後，可以立刻開始計算創建輪次。

按照見證人的定義標記每輪次的見證人事件，如下：

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

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

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

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

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

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

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

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

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

現在我們確定了10個接受輪次為2的事件，我們將為其排序得到全網公認的順序，即共識順序，按照以下優先順序進行排序：

接受輪次

共識時間戳

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

2.3 共識機制總結

Hashgraph由八卦協議和虛擬投票機制構成的共識機制，總體來說可以概括如以下步驟：

1. 每個節點都在試圖隨機找到其他節點，把自己所知的信息通過八卦協議傳遞給對方；

2. 每個節點同時也在接受其他節點通過八卦協議傳遞過來的信息，接受信息時節點需要進行一系列的運算，包括：

a. 接受和處理接收的八卦信息

b. 創建一個新的事件，同時指向自己的最後一個事件和八卦來源節點的最後一個事件

c. 對所有已知的事件計算其創建輪次，確定事件是否是該輪次內的見證人事件

d. 對所有已知的見證人事件進行選舉投票，計算出是否為知名見證人

e. 通過知名見證人，確定所有事件的接受輪次

f. 通過事件的接受輪次和共識時間戳，進行虛擬投票決定共識順序

整個共識演算法，單個節點需要保存全網數據。

2.4 Hashgraph的優勢

公平：維護交易的實際順序

採用一致的時間戳，每一個事件以及事件里的每一筆交易都有順序。

沒有礦工這種角色的存在。

安全：非同步拜占庭容錯

Hashgraph是一個非同步拜占庭容錯（ABFT）系統，沒有一個節點可以阻止網路達成共識或者在達成共識之後修改數據，號稱能達到銀行級別的安全性。而且共識演算法中沒有引入任何領導的角色，從而規避了領導節點被DoS攻擊導致系統問題的風險。目前Hashgraph作為一個私有鏈，所有節點的身份已知，這種准入控制使得現階段的Hashgraph無需考慮使用假身份攻擊的危險。

快速

根據官網的測試數據，可以達到驚人的 250000 TPS。

2.5 Hashgraph目前的問題

目前為私有鏈，吞吐量參考價值存疑

目前Hashgraph是一個私有鏈，它的「運行速度快」只能跟其他私有鏈做比較，比如Hyperledger（700個交易/秒）和Red Belly（400,000個交易/秒），如果拿它的速度跟比特幣和以太坊等公鏈來比較的話，是非常不公平的，因為現在的Hashgraph不需要設置防範惡意節點攻擊的機制。此外，八卦演算法是否適用於大規模公鏈環境也仍值得探討。

能否經受惡意攻擊

女巫攻擊（Sybil attack），即攻擊者通過創建大量假身份來破壞對等網路的信譽系統，並利用它們獲得不成比例的巨大影響力。目前Hashgraph作為一個私有鏈，所有節點的身份已知，這種准入控制使得現階段的Hashgraph無需考慮女巫攻擊的危險。但如果未來Hashgraph打算往公有鏈方向發展的話，能否抵禦女巫攻擊將是Hashgraph必須思考的一個問題。

投票驗證可能花費較多時間

Hashgraph的演算法雖然很容易建立事件，但是在每個Round之後的投票驗證過程卻有可能很長。如果一直無法達到超過2/3的絕對多數，有可能要進行很多輪投票來決定誰記錄的交易有效。

外部條件不同時的公平性問題：交易順序如何決定？

Hashgraph白皮書中對公平性（Fairness）的解釋如下：

假定存在A、B兩個節點，A在B之前發出交易請求，如果最終在共識機制的判斷下，A的交易的時間戳早於B的交易，我們就說該系統是有公平性的。如果A和B同時發生交易，並且兩筆交易幾乎是同時上傳到網路並傳播，此時就可能產生分叉，但是我們也說該系統是公平的。大多數共識機制都能夠在以上兩種情況下達到公平。

但是此解釋是建立在A、B節點面臨著同樣的外部網路情況的假設前提下的。但我們考慮這樣一個情況：

如果A的帶寬是5M/s，而B的帶寬是10M/s，A確實是比B早一點在網路中上傳自己的交易信息，但是由於帶寬限制，A的消息的傳播速度會慢於B，這樣就有可能導致最終投票時大多數人都更先接收到B的消息。這就像是在學校里，B的朋友更多，影響力大於A，因此在討論八卦的時候，B可以把自己想傳播的八卦信息更快地告訴更多人。即使可能是由A先開始傳播八卦的，但因為影響力限制，大多數人都先聽到B口中的版本。

在節點的外部條件不同時，投票是否也能反應真實地交易順序，目前沒有明確說明，因此仍然存在公平性的疑慮。

代碼不開源

Hashgraph的代碼不開源，且有專利保護，開發者需要申請SDK來進行開發，這是Hashgraph變成公鏈需要面臨的一個很大障礙，這種閉源性本身與加密數字貨幣開源的理念是相違背的，所聲稱的公平、安全也無法提供確切的證據證明，可能無法得到信任。

. 03 .

總結

Hashgraph是一個創新的共識協議，已被證明在私鏈的環境中產生高吞吐量，在當前運行的許可設置內是快速、公平和安全的，但如果想在公共環境中使用，將可能無法維持其安全性和性能，並且由於當前其代碼不開源，所聲稱的安全性、公平性也不易得到信任，這些問題都尚待更進一步地完善和測試。

. 04 .

參考與引用

Hedera Hashgraph 白皮書；

20180326 共識梳理及 Hashgraph簡評作者謝駿毅碼農學習區塊鏈；

20180403 神級項目Hashgraph真的能成為區塊鏈終結者嗎？作者 Casey 貓眼財經聚焦；

20180413 Hashgraph —— 或許是目前最為優秀的共識協議作者 Eric Sun BlockGeeks；