簡介

分布式數(shù)據(jù)庫通常要求具有拜占庭容錯的狀態(tài)機復(fù)制。一些人定義“Byzantine”這個術(shù)語時會加一些假設(shè)，例如假設(shè)攻擊者不會串通，或者通信是弱異步即非完全異步。在本文中，按照嚴格意義上的“Byzantine“含義來定義：

• 只有不到1/3的成員可以成為攻擊者
• 攻擊者可以相互勾結(jié)
• 攻擊者可以刪除或無限延遲誠實成員之間的信息轉(zhuǎn)發(fā)
• 攻擊者可以控制網(wǎng)絡(luò)來延遲和刪除任何消息
• 在任何時候，如果一個誠實的成員多次向另一個成員發(fā)送消息，攻擊者最終必須允許其中一個通過（注：不是太理解該句的含義）
• 假設(shè)存在安全的數(shù)字簽名，使得攻擊者不能篡改消息數(shù)據(jù)
• 假定存在安全hash函數(shù)，對于這些散列函數(shù)永遠不會發(fā)生沖突。

本文提出并描述了Swirlds hashgraph的共識算法，并遵守上面嚴格的定義下證明了拜占庭容錯性。

非確定性的拜占庭系統(tǒng)可以是完全異步的（注：例如比特幣以太坊的PoW），消息可以無限時延，達成共識的方式是不斷共識出新的數(shù)據(jù)，對之前的數(shù)據(jù)進行’確認‘，使得前面的數(shù)據(jù)被篡改的概率越來越低（注：永遠不會最終確定，只是概率無限趨于0）。hashgraph的共識也是完全異步的，非確定性的。

完全異步的系統(tǒng)肯定會產(chǎn)生分叉，不管是攻擊者故意分叉，還是正常節(jié)點剛好同時產(chǎn)生新數(shù)據(jù)，因為大家都在獨立生成最新的數(shù)據(jù)，那么選擇哪一份數(shù)據(jù)作為主干留下來，哪一份作為分支修剪掉。因為數(shù)據(jù)分叉后還是會廣播給全網(wǎng)， 假設(shè)分叉數(shù)據(jù)是A、B，一些節(jié)點先收到A，就基于A去解一個數(shù)學(xué)難題，一些節(jié)點先收到B，就基于B去解一個數(shù)學(xué)難題，根據(jù)各個節(jié)點的計算算力決定誰能解出來的概率大小， 注意是概率， 不是算力越大就一定是它先解出來。而計算機越多，算力越分散，就越不容易被控制計算結(jié)果（當然現(xiàn)在礦池的存在導(dǎo)致了算力集中化），這樣在一個相對公平的條件下誰先解出難題就決定A還是B作為主干，例如節(jié)點N基于A接觸來了，得到數(shù)據(jù)是C，那么C被廣播出來后， 任何基于數(shù)據(jù)B的節(jié)點都會拋棄之前的計算，重新根據(jù)數(shù)據(jù)C進行下一輪計算。PoW對應(yīng)上述描述中的數(shù)據(jù)即區(qū)塊， 計算即挖礦。當然這種分叉解決方式也會降低出塊速率， 并浪費大量的無效計算。

而傳統(tǒng)拜占庭協(xié)議沒有分叉問題， 因為節(jié)點之間對每一輪都要通過交互消息來投票選擇哪個是主干，哪個是分支，hashgraph也采用這種思想，但使用了本地虛擬投票的方案解決了節(jié)點之間消息交互的問題，節(jié)約帶寬，提高吞吐量。

核心概念

• 交易。任何節(jié)點在任何時候都可以創(chuàng)建一個簽名交易，所有節(jié)點收到該交易的拷貝，對所有交易生成抗拜占庭的全局排序。
• 公平性。對于小范圍內(nèi)的攻擊者，很難影響交易的排序公平性。
• gossip。每個節(jié)點隨機選擇所連的peer，并不斷傳播他們所知道的所有信息。
• hashgraph。是一個數(shù)據(jù)結(jié)構(gòu)，記錄了誰和誰之間傳播了數(shù)據(jù)，以什么順序傳播的。
• gossip的gossip。hashgraph本身的數(shù)據(jù)通過gossip傳播，也就是gossip本身的歷史記錄，這樣比每次傳播一個交易要節(jié)省很多帶寬。
• 虛擬投票。每個節(jié)點根據(jù)存儲的全局hashgraph數(shù)據(jù)，可以計算出peer預(yù)期的投票信息，這樣不用等peer將投票信息發(fā)過來， 在本地就可以一步全局共識。
• 知名見證人（famous witnesses）。全網(wǎng)對n個交易進行排序，需要相互詢問“事件x是不是在事件y前面？”，得到y(tǒng)es、no的回答，復(fù)雜度是O(n log n)。一種更快的方法是選取少數(shù)事件（hashgraph中的頂點）稱為見證人。知名見證人的定義是該事件被創(chuàng)建后很快被大多數(shù)節(jié)點收到，那么該事件就是知名的。節(jié)點對見證人按照拜占庭協(xié)議運行：詢問該見證人是否是知名見證人，得到全部明確答復(fù)之后，就很容易從hashgraph中派生出所有事件的全局順序。
• 強看見（strongly seeing）。給定2個頂點：x,y，可以很快計算出x是否可以強看見y： x和y是否通過多條直接路徑連接在一起，（注：從x回溯找到所有祖先，它們分布在超過2n/3的節(jié)點上，并最終回溯到y(tǒng)， 也可以理解為事件y被傳播到了>2n/3的節(jié)點上）。這個定義可以證明：如果A，B都可以計算C對給定問題的虛擬投票，那么A，B也會給出相同的投票。

gossip的gossip：hashgraph

hashgraph使用gissip協(xié)議：Alice隨機選擇一個已連接的peer，例如Bob，然后告訴Bob所有Alice知道的信息（注：例如新創(chuàng)建的交易），然后Alice繼續(xù)隨機選擇另一個peer， 重復(fù)發(fā)送她知道的信息。Bob和其他節(jié)點也一樣傳播出去， 知道全網(wǎng)都收到這個新的信息。

gossip協(xié)議傳播的歷史最終生成一個有向圖：

image.png

節(jié)點Alice上的每個頂點代表一個gossip事件，Alice中最上面的事件代表Bob執(zhí)行一個gossip同步信息給她，這個頂點有2條向下的邊，代表Alice和Bob之間的gossip傳播，下面的頂點代表早期事件的gossip。

在hashgraph中， 這個圖是一個數(shù)據(jù)結(jié)構(gòu)。每個事件（頂點）由創(chuàng)建者簽名后存儲在內(nèi)存中。例如紅色的頂點是Bob執(zhí)行g(shù)ossip同步后發(fā)過來的，該事件由Alice創(chuàng)建并簽名，事件中包含：

• 2個hash：就是2個藍色節(jié)點的hash
• Alice選出來的打包進來的新交易

紅色事件的其他祖先（灰色頂點）信息不包含在紅色事件中，但是決定了hash值。像這種hash圖和Git也很類似：頂點是文件樹的一個版本，邊代表修改， 只是Git存儲及誒單之間的相互通信記錄。而hashgraph則會保存。

gossip協(xié)議可以傳輸個各種各樣的信息，比如用戶標識，交易，區(qū)塊等等信息。但如果用來傳播gossip本身的傳播記錄呢？用來傳播hashgraph數(shù)據(jù)本身呢？傳播hahsgraph可以攜帶大量的信息，比如在hashgraph中攜帶新的交易，Alice不僅可以得到新的交易信息，也可以知道Bob是在何時得到該交易的，也可以知道Carol是在何時得到“”Bob在何時得到該交易“”的信息。隨著hashgraph不斷向上生長，節(jié)點可能在短時間內(nèi)會保持不同的最新的事件，當他們很快會匯集到全部下一級的hashgraph數(shù)據(jù)。進一步來說，Alice和Bob同時得到一個事件，可以確保擁有完全相同的祖先，保證所有支持拜占庭容錯的算法都在本地運行，不需要和其他接待進行交互，解決大量的通信帶寬和延時，通信信息也可以少很多：AliceU需要對每個交易進行簽名并傳播，而只需要把所有交易放在事件中，簽一次名傳播出去即可，而事件中也還需要攜帶本身的hash即可， 不用攜帶祖先的hash。