共識算法
由于是完全異步的系統(tǒng)，無法保證某一時刻所有節(jié)點知道全部事件，那么如何對事件進行全局排序，進而對事件內(nèi)的交易進行排序。對于沒有l(wèi)eader的大部分拜占庭容錯協(xié)議需要通過交互投票信息來達成共識，甚至要求多輪投票。hashgraph不需要發(fā)送投票信息，每個節(jié)點根據(jù)hashgraph數(shù)據(jù)可以在本地根據(jù)確定性函數(shù)計算出事件的全局排序，并可以保證各節(jié)點得出的排序是一樣的，從而實現(xiàn)不需要發(fā)送消息達到共識的目的。
當(dāng)然，Alice和Bob在任何時刻都可能不會擁有相同的hashgraph數(shù)據(jù)，因此，通常是對較早的事件的hashgraph數(shù)據(jù)才能完全匹配，對于最近的事件節(jié)點之間可能相互看不見。還可能存在一個新事件傳播出去后被記錄在hashgraph數(shù)據(jù)中較早期的位置。對于這些問題，hashgraph通過虛擬投票來解決。
假設(shè)Alice擁有hashgraphA，Bob擁有hashgraphB，在某一時刻， 這兩個數(shù)據(jù)存在輕微差別，但最終會達到一致。一致性意味著如果A和B都包含事件x，那么必定包含x的完全相同的祖先，以及祖先之間的關(guān)系。如果Alice知道事件x，而Bob不知道，并且他倆都是誠實的，我們就期望Bob盡快通過gossip協(xié)議學(xué)習(xí)到事件x， 并且共識算法假設(shè)這最終肯定會發(fā)生的，但無法保證何時發(fā)生，因為協(xié)議是完全異步的，也不存在事件傳播的超時機制。
Alice通過對hashgraphA中的事件進行一系列的“選擇”，計算一個事件的總排序。在每個“選擇”中，A中的一些事件視為形成投票，另一些事件視為接受投票。Alice計算多個“選擇”，一個事件可能參與多個“選擇”，并在不同“選擇”中形成不同的投票。如果事件是Bob創(chuàng)建的，我們就說Bob在某個“選擇”中進行了投票。當(dāng)然該投票是虛擬的， 不是Bob發(fā)出來的，但效果跟Alice收到Bob的投票一樣。
Bob還有一種欺騙的方式創(chuàng)建事件：基于自我祖先z創(chuàng)建2個事件x、y（在正常情況下，y的自我父事件應(yīng)該是x），這意味著x，y不在一條鏈上了，形成了分叉。然后，Bob將x傳播給Alice，將y傳播給Carol，當(dāng)然他們不知道存在分叉， 所以，Alice計算Bob對事件x產(chǎn)生的虛擬投票和Carol計算Bob對事件y產(chǎn)生的虛擬投票將是不一致的。在這種情況下，存在一小段時間中Alice的hashgraph中包含x，但不包含y。Bob的hashgraph中包含y，但不包含x。
hashgraph共識算法通過一個“看見”和“強看見”（strongly seeing）的概念來解決上述分叉攻擊。首先，區(qū)分2個定義：祖先和自我祖先。祖先是指其他節(jié)點傳播過來的事件，自我祖先是最后一次收到信息而創(chuàng)建的事件。下圖中，深藍色頂點是紅色頂點的自我祖先，淺藍色頂點是祖先：
如果事件w的祖先包括事件x，但沒有包含事件y，我們叫做w可以“看見”x，不能”看見”y。
而如果x，y都是w的祖先（x，y處于分叉狀態(tài)），則w無法“看見”x或y，以及其他任何由Bob創(chuàng)建的事件。換句話說，w可以看見x，表示x的創(chuàng)建者不存在分叉。
如果全網(wǎng)存在n個節(jié)點（n>1），那么事件w可以"強看見"事件x，意思是：事件w被≥2n/3的不同節(jié)點上的事件看見，而這些事件也都可以看見事件x。舉例如下：
上面顯示了4種黃色事件可以“強看見”橘色事件的場景。黃色事件可以看見紅色事件， 紅色事件可以看見橘色事件，并且紅色事件分布于不同節(jié)點，超過了2n/3，即3個以上。
“強看見”意味著虛擬投票是可行的：分布在不同節(jié)點上的紅色事件其實就代表了該節(jié)點對該事件的簽名投票確認。
在虛擬投票中，事件x對一些YES/NO的問題進行投票（例如，某個事件是不是知名的），計算投票的依據(jù)就是事件x的所有祖先。如果w可以“強看見”x，x就會發(fā)出投票給w。例如，黃色事件發(fā)起一個提問，詢問可以“強看見”的橘色事件，請求橘色事件進行投票操作，因為黃色事件可以“強看見”橘色事件，橘色事件就將投票發(fā)給黃色事件，這個投票信息是拜占庭容錯的，保證無法造假。
進一步來說，如果hashgraphA和hashgraphB是一致的，就不可能存在一個事件在A中強看見事件x，而在B中強看見事件y。這也是拜占庭個容錯證明的理論基礎(chǔ)。這也確保了如果一個攻擊者試圖通過分叉來欺騙，他們也不能使得不同的節(jié)點得出不同的事件順序。歷史上一些拜占庭協(xié)議要求對收到的投票進行”轉(zhuǎn)發(fā)”，防止Alice向Bob和Carol發(fā)送不同的投票，這種防止攻擊的機制和“強看見”的機制是類似的。
根據(jù)上述的定義， 完整的hashgraph共識算法如下：
主流程很簡單：
并行運行2個循環(huán)：
loop：
同步所有已知的事件給隨機的節(jié)點
end loop
loop：
接收一個信息同步
創(chuàng)建一個新的事件
call divideRounds
call decideFame
call findOrder
end loop
簡單的gossip協(xié)議已經(jīng)足夠了，但還是有可以提高效率的空間。例如Alice和Bob相互告知他們所知道的全部信息，然后Alice發(fā)送她最新知道而Bob不知道的信息，協(xié)議可能要求Alice按照邏輯順序發(fā)送事件，這樣Bob可以在收到每個事件時都知道該事件的父事件，協(xié)議也可以要求Bob收到同步事件后立即發(fā)送同步事件給Alice，協(xié)議也可以要求一次和多個節(jié)點進行同步。這些優(yōu)化可以在具體實現(xiàn)時可以采用也可以不采用。
每次同步后，調(diào)用3個處理函數(shù)，最終確定事件的順序。這里沒有節(jié)點之間的交互，全部靠本地計算完成。在這些處理中， 每個for循環(huán)中以邏輯順序訪問事件：先訪問父事件，再訪問子事件。在第一個循環(huán)中（注：函數(shù)divideRounds，劃分輪次）,如果是第一個事件：設(shè)置 x.round=1，x.witness=TRUE。算法定義一個常量n（n>1），代表全部節(jié)點；定義常量c，要求≥2，例如10；
divideRounds的過程如下：
procedure divideRounds
for each event x //從最早的時間開始遍歷
r ← x的父事件中較大的輪數(shù) (沒有父事件則置為1)
if x可以“強看見”>=2n/3的r輪的見證人
x . round ← r + 1
else
x . round ← r
x . witness ← ( x 沒有自我父事件 ) //true
or ( x . round > x . selfParent . round ) //true
事件x被創(chuàng)建后，會分配一個round，再計算一個它是否是見證人的bool值。
以上圖為例，如果最底層的一行是r輪，那么圖中除了黃色事件之外剩下的所有事件都處于r輪，黃色處于r+1輪， 因為他可以“強看見”r輪的事件。歷史中的第一個事件的round是1。每個事件最終都會有一個創(chuàng)建時輪次和接收時輪次（round created 和 round received），創(chuàng)建時輪次簡稱為上面的輪次，即變量x.round。
對于任何給定的節(jié)點，每一輪中創(chuàng)建的第一個事件叫做見證人。只有見證人可以發(fā)送和接收虛擬投票。見decideFame的過程如下：
procedure decideFame
for each event x in order from 按照輪數(shù)從前往后一次排序所有事件
x.famous ← UNDECIDED // 未確定該事件是不是知名見證人
for each event y in order from 按照輪數(shù)從前往后一次排序所有事件
if x.witness and y . witness and y . round>x . round
d ← y.round - x . round //x和y的相差輪數(shù)
s ← 在 y.round-1 輪中y可以強看見的見證人事件集合
v ← s中的投票結(jié)果 (超過2/3投票：TRUE)
t ← s中的投票數(shù)量
if d = 1 // 第一次選舉
y . vote ← can y see x ? //如果y可以看見x，投票
else
if d mod c > 0 // 正常投票流程：c>=2, 即要求 至少已投過1次
if t > 2* n /3 // 絕大多數(shù)見證人投票了，表示是知名見證人，保存投票結(jié)果
x . famous ← v
y . vote ← v
break out of the y loop //y投票完成，跳出循環(huán)，
else // 直接投票， x是不是知名見證人還需要下一次繼續(xù)投票
y . vote ← v
else // this is a coin round
if t > 2* n /3 // 絕大多數(shù)贊成，進行投票
y . vote ← v
else // else flip a coin 隨機選擇
y . vote ← middle bit of y . signature y簽名的中間位置的值
對于每個見證人，需要決定是否是知名的（x . witness=true），這個決定通過虛擬投票完成。每個節(jié)點在本地運行虛擬投票的過程，它將hashgraph中的事件看做是節(jié)點間彼此發(fā)送的投票，在每一輪中，節(jié)點對見證人進行投票，直到超過2/3節(jié)點的節(jié)點都投票同意。
在見證人所在輪次的下一輪次中大部分見證人可以看見該見證人，那么就叫該見證人為知名見證人，否則只是普通見證人。
拜占庭協(xié)議對每個見證人進行一個選舉來決定它是否知名：對于在r輪次中的見證人x，每個在r+1輪次的見證人對x進行投票，表示他們能否看見見證人x（注：就是上面d=1時的第一次選舉）。超過2/3的見證人都能看見的話，全網(wǎng)就決定它為知名見證人，選舉過程結(jié)束。
如果投票需要更加平衡，那么它會根據(jù)需要繼續(xù)進行多輪投票，每個見證人可以根據(jù)大多數(shù)見證人在上一輪中可以”強看見”的情況，在正常輪次投票中進行投票。為了防止攻擊者控制網(wǎng)絡(luò)，還有一個隨機投票輪，這意味著即使攻擊者控制了所有網(wǎng)絡(luò)上的消息，使得投票分裂（keep the votes carefully split），還是有機會使得全網(wǎng)隨機達到超過2/3的票數(shù)。從而協(xié)議達到最終一致性。
如果滿足d=1，這需要繼續(xù)下一個計算，在d=2時判斷是否是知名見證人。在那個修改過的算法中，每個選舉都會開始新的一輪。如果兩者在以下混合算法中組合，它甚至?xí)^續(xù)工作。
在每一輪中，首先運行所有的選舉（d=1）。如果該輪中每個見證人是否是知名見證人都已經(jīng)確定，并且在那一輪中少于2/3的節(jié)點創(chuàng)造了知名見證人，那么選舉將全部重新運行，進入d=2。對于這個混合算法，本文中的所有理論都能成立，包括拜占庭容錯證明。
對于新的選舉，共識時間會變長，大約20%，但實際中很少發(fā)生，即使真的發(fā)生，也會增加知名見證人的數(shù)量確保公平性。
一旦達成共識，或者指定輪次中每個見證者都是知名的，那就很容易確定一個共識時間戳和對時間的全局排序。這個工作在findOrder中完成：
procedure findOrder
for each event x
if r輪或r輪之前中不存在事件y：y. witness = TRUE 和 y. famous = UNDECIDED
and x 是每個r輪唯一知名見證人的祖先
and this is not true of any round earlier than r
then
x. roundReceived ← r
s ← set of each event z such that z is
a self - ancestor of a round r unique famous
witness , and x is an ancestor of z but not
of the self - parent of z
x. consensusTimestamp ← median of the
timestamps of all the events in s
return all events that have roundReceived not UNDECIDED ,
sorted by roundReceived , then ties sorted by
consensusTimestamp , then by whitened signature
首先，計算接收輪次。 事件x有一個接收輪次r，是指所有的獨特知名見證人都是事件x的子孫輩的那個輪次，并且該輪次中每個見證人是否是知名的都在輪次≤r中確定了。 （某一輪次中獨特知名見證人的定義是：在該輪次的知名見證人集合中，去除該輪次中擁有多個知名見證人的節(jié)點）。
然后，計算接收時間。 假設(shè)事件x的接收輪次是r，并且Alice在r輪次中創(chuàng)建了一個獨特知名見證人y。 該算法就是找到這樣的事件z，它是y的自我祖先中最早學(xué)習(xí)到x的自我祖先。 設(shè)t是Alice創(chuàng)建z時放入z的時間戳。 那么t可以被認為是Alice聲稱第一次學(xué)習(xí)x的時間。 x的接收時間是r輪中唯一知名見證人的所有創(chuàng)建者的時間戳的中間數(shù)。
然后計算共識順序。 所有的事件都按他們的接收輪進行排序。 如果兩個事件有相同的接收輪，那么它們按照他們收到的時間排序。 如果仍然無法排序，那么根據(jù)簽名數(shù)據(jù)進行排序：對接收輪中所有唯一知名見證人的全部簽名進行異或。
（注： 最后的描述不是特別理解， 等加深理解后再用更通俗的語言描述）
