什麼是Hashgraph演算法?Hashgraph演算法最早是由 Leemon Baird 博士在 2016 年發表的一篇論文“The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance”(https://swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf)”上公開，根據其介紹，Hashgraph 演算法實現了非同步拜占庭容錯(ABFT)，因而能容納非常高的吞吐量並能非常快速的處理交易(官網提供的資料顯示，在真實環境下可以達到驚人的 250k TPS)。
Hashgraph演算法簡介
Hashgraph 是一種非同步拜占庭容錯演算法(ABFT)，它跟我們目前常見的 PBFT 演算法最大的不同就是它是完全非同步的。我們知道 PBFT 演算法能支撐的網路規模是非常有限的最大原因就 PBFT 模型的通訊複雜度是 O(N^2)，隨著節點數量的增加，需要通訊的訊息數量呈指數級別的上升。而 Hashgraph 突破性的拋棄 PBFT 中使用的訊息同步機制，使用非同步 BFT，透過保證最終確定性來確保演算法的高效和安全。
Hashgraph 採用的是 DAG 資料結構，這跟當前的很多開源鏈(比如 Iota，byteball, nano 等)是類似的，因為它們都採用 DAG 作為底層資料結構模型。但是 Hashgraph 最特別的一點是，它無需中心權威節點，而是依靠獨特的 Gossip about Gossip 和 Virtual Vote 兩大機制來保證了演算法可以在純非同步的環境中高效執行，並且透過絕對多數(超過 2/3 節點)強可見(強引用)機制來保證了共識結果的正確性(安全)。
Hashgraph 演算法是一種拜占庭容錯演算法，它要求節點數量是相對固定的(總量為 N 需要預先設定)，這樣的話，它就可以透過大於 2/3 忠誠節點的比例原則來達到拜占庭容錯。這跟當前公鏈模型下(比如 DAG 主鏈，POW，POS 等)這些演算法在達到共識的條件上有一些區別，所以更適用於私鏈(或聯盟鏈)。但是，由於其獨特的性質(在保證去中心化的同時不需要繁重的工作量證明)，Hashgraph 在未來的公鏈也有相當潛在的使用價值。
最後，再介紹一下 Hashgraph 跟其他開源專案在運作模式上的區別。
根據原作者釋出的白皮書介紹，Hashgraph 僅是一個演算法的名字，它既不是區塊鏈專案(比如比特幣，以太坊這種完整的可執行的系統)，也不是開源的。它是由發明它的 Leemon Baird 博士所建立的Swirlds, Inc公司負責掌控，並運營在 Hedera 專案(https://www.hedera.com)之下。Swirlds 公司對該演算法申請了專利並進行了很強的技術保護，它致力於在企業之間以合作的方式來運作和使用基於 Hashgraph 開發的應用。
從這裡我們可以大致看到，Hashgraph 是按照一個相對傳統的方式在運作。雖然其核心演算法的原始碼並不公開，它還是做出了一定程度的開放來使得整個區塊鏈社羣和開發者受益，比如對外提供 SDK(https://dev.hashgraph.com/)。由於 Hashgraph 演算法是用 Java 和 LISP 實現的，因此很多基於 JVM 的語言都可以在其之上構建應用程式。當然，社羣的開發者也基於 Hashgraph 公開的演算法(論文)實現了許多其他語言的版本(比如 Go，Python, Javascript 等)，由於演算法的簡潔和優雅，已經有越來越多的開發者被吸引。
Hashgraph演算法原理
介紹完了 Hashgraph 的相關背景，我們接下來進入主題，也即演算法原理。
實際上，演算法的大部分內容在論文中都有介紹，不過，畢竟論文發表的時間早，其中難免缺失許多細節。因此，Leemon 博士在其發表之後的數年時間內又不斷對該演算法做了更多更細緻的描述和改進。在 Youtube 上也有它對該演算法的一個長篇介紹，不過很多人看完仍然表示似懂非懂，不好理解。因此，這篇文章致力於把演算法用更易懂的方式解釋得更通透一些。
在介紹演算法之前，先了解論文中所提出的一些概念，Event，這個是 Hashgraph 中最基本的元素和概念。
在 Hashgraph 中，使用一種叫Event的資料結構來代替我們常見的區塊鏈(比如比特幣)中的 Block 概念。Event 由每個節點自行建立，它主要包含四類元素：交易集合，時間戳，以及對兩個 Parent Events 的引用雜湊。
在傳統的區塊鏈中，新產生的區塊只能是隻能有一個先導區塊的，在 Hashgraph 中，每個 Event 必須要連結兩個 parent Events，其中一個必須是自己，而另一個則可以是任何一個從其他節點發來的 Event。
我們來對比一下傳統區塊鏈的結構和 Hashgraph 的結構之間的區別，如下：
Hashgraph 演算法的核心技術點是兩個部分：謠言演算法(Gossip about Gossip)和虛擬投票(Virtual Voting)。
接下來，我會一步一步詳細介紹!
Gossip About Gossip
Hashgraph 共識的機制和 hashgraph 結構的構建是透過 Gossip 過程來完成的(更多關於 Gossip 機制的介紹，可以參考我這篇文章：“P2P 網路核心技術：Gossip 協議”)。
Gossip 簡單來說就是，節點隨機選擇一個可以連線的鄰節點，向其傳送一條資訊(Event)。而 Gossip about Gossip 則是，收到 gossip 資訊的節點，對該 gossip 資訊進行簽名，並且再把該簽名打包進一個新的資訊中，並隨機傳送給網路中的任一節點。這樣，每個節點發出的 Gossip 資訊都包含了對其收到的前一個 Gossip 資訊的簽名驗證，實際上就是做了一個見證(Witness)工作。
注意這裡的 Gossip 過程是非常簡單的，收到 Event 資訊的節點可以向任意一個或多個節點繼續 Gossip 新的 Event。每一次 Gossip 都是對前一次資訊的背書和見證。
Local hashgraph copy
我們用小寫的 hashgraph 表示該演算法底層使用的資料結構，參與共識的每個節點都會儲存一份完整的 hashgraph 副本圖，初始時(genesis)，每個節點上的這個副本圖都是空的，當開始有節點產生 Event 之後，就會在自己的 hashgraph 副本圖上進行記錄。
比如，每個節點都建立第一個 Event 時，他們各自的副本圖如下：
當 A 收到 C 發來的 Event 時，A 就會更新本地的 hashgraph 副本，如下：
同時，A 還會基於 Event_a1 和 Event_c1 建立一個新的 Event，並 Gossip 出去，如下：
假設剛才在 A 收到 C 的 Event 時，C 也收到了 D 的 Event，那麼各個節點的 hashgraph 副本圖則會顯示如下：
某個時間點之後，大家都收到了彼此發給對方的訊息
可見，在節點相互 Gossip 通訊的過程中，它們各自 hashgraph 副本的內容都不盡相同，但是有一點非常重要的就是，每個節點都會忠實的記錄自己所建立的所有 Events。
比如上圖中的節點 A 和 B，A 記錄了自己所建立的所有 Events，即 a1 和 a2.而 B 同樣記錄了自己所有的 Events，b1 和 b2.但是 A 缺少 B 的所有 Events，而 B 則缺少 A 的最新 Event a2.
當 A 準備把 a2 發給(gossip)給 B ，如下：
並且，A 準備更新自己副本上 B 這部分的資料時，發現自己缺少 B 這部分前序的資料，因此，B 會把它的歷史資料同步(Sync)給 A。而 B 的副本上由於已經有 a1 了，因此在收到 a2 之後無需再同步。
最終，hashgraph 就會更新成如下狀態：
現在，我們對於 Gossip 過程和副本結構有了一個初步的認識，接下來，我們來了解 Hashgraph 演算法中定義了哪些狀態
可見
由於 hashgraph 中，所有 events 都會引用兩個 parent events，因此，如果一個 child event y 可以回溯到某個 ancestor event x，那麼就說 y 可見 x。
而且，同一個節點產生的事件，後續事件總是可見先前所有事件，實際上，它們還是強可見的。
如下：
強可見
當事件 Y 能找到事件 X 的所有路徑中跨越了絕對多數的節點，那麼事件 Y 強可見事件 X。白皮書中提到經過數學論證可以保證兩個強可見的節點在虛擬投票時能獲得一致的結果
比如下圖，想要判斷 b5 是否強可見 c1.
我們需要做的就是，把所有從 b5 能可見 c1 的路徑都找出來，如果這些路徑集合中，能夠包含超過 2/3 的節點(也就是要包含至少 4 個節點)，那麼就說 b5 強可見 c1.
如下：
可以看到，b5 有 3 條路徑都能可見 c1.這 3 天路徑經過的節點分別是，path2: (B, C)，path2:(B, D, C), path3(B, E, C)，
一共經過了 B, C, D, E 4 個節點，滿足超過 2/3 節點的要求，因此，可以確認事件 b5 強可見事件 c1.
輪次 Round
在 Hashgraph 中，根據事件所處的可見狀態，把他們分為不同的輪次(Round)。
當一個事件強可見絕對多數節點上的先前事件時，我們就說該事件在一個新的輪次上，記為 R。
我們透過一個示意圖來理解輪次的概念
上圖中，事件 a5 強可見了 R 輪的 a1. b1. c1. d1 共 4 個事件，也就是說強可見了絕對多數節點的第R 輪的事件，因此，a5 就在一個新的輪次 R + 1 上。
注：這裡的絕對多數是指 Supermajoiry，即超過 2/3.文章後續內容有使用絕對多數的地方均表示超過 2/3 的意思。
建立輪
所謂的建立輪(Creation Round)，就是當一個事件被建立時，它所在的輪次。通常，一個事件被建立時，它會被立即賦予一個輪次號，跟其父事件是在同一個輪次一樣。也就是說，如果同節點的父事件是 R 輪，那該事件被建立時也是在第 R 輪，它的建立輪就是 R 輪。
比如，上圖中，初始(Genisis)情況下，所有節點的狀態都是相同的，把它定義為定義而第 R 輪，並且 R = 1.後續建立的事件都是在第 R 輪的。
接收輪(Receive Round)很好理解，就是當某個事件強可見超過 2/3節點的本輪或者上一輪的事件時，這個事件就達到了一個新的輪次，這個輪次就是他的接收輪。如下圖：
從上圖中，我們可以看到，當 a5 和 d5 被建立時，它們的建立輪是第 R 輪，而當它們能夠強可見絕對多數節點的第 R 輪的見證人事件(即 a1. b1. c1. d1)時，它的接收輪就變為 R + 1 輪，也就是說，a5 和 d5 都變成 R + 1 輪的事件了，並且，在它們之後建立的子孫事件都在 R + 1 輪。
這裡需要注意的是：如果事件 a5 只能強可見 R 輪某節點的見證人時，a5 的輪次是不會增加的，依然為此在 R 輪。只有當其強可見絕對多數節點的第R 輪的見證人，它的輪次才變為 R + 1 輪。
見證人和知名見證人
見證人(Witness)，就是第 R 輪所建立的第一個事件。比如上圖的 a1.b1.c1. d1 和 e1.它們都是各自節點的見證人事件。
知名見證人(Famous Witness)，當 R 輪的見證人事件被 R + 1 輪的多數(超過 2/3)見證人強可見時，它就是知名見證人事件。
由上圖我們可以看到，c1 被 R +1 輪的大部分見證人事件強可見，因此 c1 就是知名見證人。
我們注意到這裡暗含了一個強約束條件，就是 R + 1 輪的見證人事件，這意味著 [a5. b5. c5. d5] 這幾個事件必然是強可見大部分節點的第R 輪見證人事件的，但不必然強可見 c1(比如他們都強可見 [a1. b1. d1. e1] 這 4 個見證人事件。所以，要判斷 c1 是否是知名見證人，就必須要求 R + 1 輪的大部分事件都強可見 c1.一旦滿足，說明 c1 就是知名見證人了，知名見證人意味著不可更改，這時候系統就可以對該事件進行 commit。
虛擬投票(Virtual Vote)
上述 Event 狀態變遷和系統狀態變遷的過程其實也包含了投票的過程，投票是在上述狀態變遷過程中完成的。
根據上述的演算法介紹，我們知道一個 Event 的狀態變遷過程是這樣的：
可見 -> 強可見某祖先 Event -> 強可見絕對多數節點的祖先 Events -> 輪次增加(即 Round + 1) -> 大多數 R+1 輪 Witness 強可見 R 輪某個 witness -> R 輪該 Witness 成為 famous witness-> commit。
如圖：
虛擬投票實際上就是指上述兩個黃色部分。它主要是分為兩個步驟來進行的，① 處相當於 Pre-Vote 過程，這裡其實是確定投票委員會成員，如果一個事件強可見大多數 witness，那麼它對某 witness 的票就有效。而② 處則是 Pre-Commit 過程，收集投票委員會對某個祖先 Event 所投的票，如果票數超過 2/3.那麼就可以把該 Event 標記為 Famous，也就是不可更改了。接下來只需要 commit 就行了。
注：R + 1 輪的 Witness 只會對 R 輪的 Witness 投票，R 輪 Witness 後續的 Events 不會收到投票。 Witness 是指 R 輪第一個建立的 Event，如下：
我們來看一下想要把 R 輪的 c1 標記為 Famous 需要經過哪些步驟：
1)判斷每個節點滿足 R + 1 輪的 Event
這是一個對當前節點的各 Event 進行不斷回溯驗證的過程。
2)判斷每個節點中，R + 1 的 Event 是否強可見 c1.如果強可見，那就相當於 Vote Yes。
3)計算 Vote 數量，如果超過 2/3 的 Event 都投票 Yes。就把 c1 標記為 Famous。
實際上，計票過程是在 R + 2 輪進行的。因為即使 R + 1 輪所有 Event 都強可見 c1.它們彼此之間也互相不知道對方的投票情況。因此，必須由下一輪的 Event 來收集大家的
投票結果。
由上圖可見，R + 1 輪的 [a5. b5. c5. d5] 以絕對多數的比例對 c1 形成了強可見狀態，使得 c1 滿足知名見證人人條件。R+2 輪上的每個見證人則對 R+1 輪進行收集投票。如圖，a9 強可見了 R+1 輪的這 4 個強可見 c1 的事件，因為已經超過絕對多數，因此 a9 可以立即確認 c1 事件，也就是 c1 已經達到全網共識而且不可更改。
注：Hashgraph 根據數學理論證明，任何一個 R+2 輪見證人如果對投票結果做出了決定，那麼這個結果就是全網的結論，如果這輪見證人無法做出決定，就由下一輪見證人計票決定，直到得出確切結論。
事實上，R + 2 輪這個收集投票的過程只是一個學習共識結果並進行 commit 的過程，因為一旦知名見證人被確定，剩下的過程就是各個節點把這個結果進行提交了。
接收輪次和共識時間戳
一旦某個輪次確定了所有的(or 絕對多數)知名見證人，就可以為這一輪次中的其他普通事件(非 witness)確定接收輪次和共識時間戳(consensus timestamp)。
如果一個事件被某輪的所有知名見證人(知名見證人數量必須超過 2/3)都可見，就說它的接收輪為這些知名見證人所在的輪次。
比如，第 R + 1 輪的所有知名見證人都已經得到確認，如果這些知名見證人都可見某個祖先事件，那麼就說這個祖先事件的接收輪為 R + 1.
比如下圖，假定 a5. b5. c5. d5 都是 R = 2 輪的知名見證人，它們都可見 a3 事件，我們就說 a3 在 R = 2 輪被接受。而對於 b4 來說，只有 b5 可見它，其他見證人並不可見它，因此，它的接收輪還不確定，只能等待後續輪次的見證人滿足可見的條件，才能確定它的接收輪。
現在假定我們有一個 Event x，其接收輪為 R + 1.我們想要確定其在所有 event 中的 timestamp。
Hashgraph 採用的方法是，先確定各個節點中的可見 Event x的最早 Event，然後把它們的 timestamps 集合取中位數作為 x 最終的 timestamp。比如，找到節點 A 中最早可見 x 的 Event，樣，找到節點 B，C， D 中最早可見 x 的 Event 。對於 A 來說，最早可見 x 的就是 x 自己，而對 B， C， D 來說，最早可見可以是任意 Event。
為了便於理解，我畫了一個示意圖來描述，如下：
想要確定 a3 的 timestamp，我們從各個可見它的見證人節點中，查詢最早可見 a3 的 events。
如上圖，A 節點最早可見 a3 的時間就是 a3 自己，而 B 節點最早可見 a3 的則是 b3.同理得到 c4 和 d4.
這樣，我們就得到一個 timestamp 集合：[a3. b3. c4. d4]，取它們的中位數，就得到一個基準 timestamp，把它作為 a3 的真實 timestamp。
根據相同的做法，我們可以得到其他所有 Events 的 timestamp，也就是說我們可以得到一個 Total order。
Tie breaker
當然，僅有 timestamp 可能還無法確定 Event 的先後順序，因為很有可能兩個 events 會有相同的 timestamp。所以還需要一些其他條件和規則來約定順序，在Hashgraph中，是按照如下規則來排序的。
