鲸準研究院丨Hashgraph技術解析

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

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

作者：

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

鲸準研究院 譚瑩 王帆 陳泓伊

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

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

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變成公鍊需要面臨的一個很大障礙，這種閉源性本身與加密數字貨币開源的理念是相違背的，所聲稱的公平、安全也無法提供确切的證據證明，可能無法得到信任。

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

• Hedera Hashgraph 白皮書；

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

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

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

• 20180417 Hashgraph —— 可能超越區塊鍊的優秀共識協議 作者 XC 帶頭币姐；
  

• 20180424 一文看懂DAG技術的現狀與趨勢 |鍊捕手 作者 李強 鍊捕手；

• 20180507 如何十分鐘讀懂Hashgraph 作者 互聯價值 InterValue。
  

關于本文的更多讨論，歡迎留言後台

編輯: 陳文洋


【轉載須知】

1、本報告為鲸準(ID:rong36kr)旗下專業的數據研究分析機構【鲸準研究院】原創作品，受《著作權法》保護，依法享有彙編權及注釋權；

2、轉載請聯系微信：wuyaoguaiguai，取得授權後方可轉載；

3、禁止商用轉載，禁止二次編輯轉載。