PRO:技術入門 | 探討BFT的關鍵細節及Libra的Consensus組件_BFT幣

Libra涉及的東西比較多，我們從三條線介紹Libra的設計與實現：

通過分析Node啟動并加入到Libra網絡的過程，介紹Network組件的設計與實現；

圍繞Transaction的生命周期，分析其接收交易、打包區塊、運行上鏈的過程，介紹Libra的Mempool、Executor以及Storage、VM等核心組件；

圍繞LibraBFT，介紹Consensus組件以及區塊達成共識的過程。

前面我們講述Libra的第二條主線——Transaction的生命周期，了解了Libra核心組件大概的設計和實現。其中Consensus組件我們只是簡單介紹，在實際場景下，Consensus組件需要保證在很多分布在全球不同地區的Validator節點達成共識。在分布式的情況下，保證區塊或者說交易的順序最終一致，可以說，這是整個區塊鏈的靈魂。因此我們單獨介紹Consensus流程：

為什么需要Consensus？

目前主流的共識包含哪些？

BFT如何達成共識？

Libra的consensus組件

為什么需要Consensus？

前面介紹賬號模型的時候我們提到“按大部分人認可的順序記錄每個Address的變更過程”，這里“大部分人認可的順序”就是達成共識。但是現實中，要讓遍布全球的很多很多互相不信任的節點，對全世界所有人的Transaction的順序快速達成共識，是一件極具挑戰的事情，也是所有公鏈都在發力的地方。

主流的共識

為了解決全球共識的問題，業內很多能人志士長時間在探索，目前大概形成了3類具有代表性的共識：

這3類共識分別又衍生出各種各樣的共識：

POW、POW-DAG、NC-Max等

Pos、PoA、DPos等

PBFT、LibraBFT等

這些共識各有自己的特點，同時相互之間又可能存在一些關聯。共識是一個很廣闊的話題，感興趣的可以自己去了解一下。由于BFT本身比較復雜，接下來我們深入講述BFT，一步一步逼近我們的主題——LibraBFT。

BFT如何達成共識

BFT比較復雜，概念也很多，因此，我們分成多步講解，從簡單的場景開始，逐步擴展：

BFT的安全性與活性

能容忍的拜占庭節點數

同步與異步

PBFT和兩階段確認

現場丨中國銀行業協會首席信息官高峰：大數據、區塊鏈、5G等多種技術生態融合有利于金融深度和廣度發展:金色財經報道，在上海舉辦的外灘大會上，中國銀行業協會首席信息官高峰現場進行主題分享《生態銀行讓金融更普惠》指出，5G為生態銀行帶來了新的機遇，5G主要是為移動場景下云計算、大數據、區塊鏈這些技術的基礎提供了環境，多種技術的生態融合，有利于金融的深度和廣度發展，場景能不能做成生態，關鍵是深度有多深，有多深才會有多寬。[2020/9/26]

三階段確認的Hotstuff

鏈式Hotstuff

BFT的安全性與活性

很多講BFT或者講Paxos的文章都會講拜占庭將軍的故事，版本不一，核心思想差不多，這里我們引用百度百科：拜占庭位于如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了達到防御目的，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。在戰爭的時候，拜占庭軍隊內所有將軍和副官必須達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時，結果并不代表大多數人的意見。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協議，拜占庭問題就此形成。

以上是百度百科摘取的拜占庭將軍的故事，一句話總結，就是要讓所有的忠誠將軍行動一致，要么實力最強，要么戰斗力最強。換句話說，忠誠將軍一致行動的安全系數最高。如果出現部分忠誠的將軍去進攻，部分忠誠的將軍撤退的情況，那么后果不堪設想。

拜占庭容錯BFT就是為了解決這個問題。這里有兩個很關鍵的指標：

安全性：allcorrectnodesmustagreeonthesamevalue，就是說所有的忠誠將軍達成一致；

活性：allnodesmusteventuallydecideonanoutputvalue，可以理解為，投票一定會產生結果，也就是所有節點達成一致；

安全性是目的，活性是所有造成投票進行不下去的各種異常的一個整體概況。為了同時保證安全性和活性，很容易提出問題：

在一個確定數量的集群里，最多能容忍的拜占庭節點是多少？

在分布式的環境里，消息延遲了怎么辦？

能容忍的拜占庭節點數

關于能容忍的最大拜占庭節點數，Lamport大神有數學推導，感興趣的可以去看看，但是我看了一個更通俗易懂的推導版本。

我們來簡化一下問題：假設有一個n個人的部門，準備春游，從A、B兩個地方進行選擇，哪個地方票數最多，就去哪。其中有f個人很宅，哪都不想去。而剩下的所有h個人都是想去旅行的。這里，不管是誠實還是不誠實節點，都有可能不投票。那么可能會出現這樣的結果，A和B的票數一樣多，部門行政就不知道該怎么辦了，卡住了。而不誠實節點恰恰就希望卡住，為此不誠實的節點可能視情況而投票：

工商銀行加快區塊鏈技術在金融領域的研發應用:3月31日，雄安區塊鏈實驗室正式揭牌，中國工商銀行作為實驗室籌備組成員，通過線上方式參加了揭牌儀式。據悉，該實驗室是雄安新區成立的首個科技實驗室，將推動區塊鏈技術自主創新，促進區塊鏈技術與產業協同，探索“政產學研用”五位一體的新型實驗室經濟模式。

自雄安區塊鏈實驗室計劃提出以來，工商銀行積極參與實驗室建設規劃，以及自主可控的區塊鏈底層研發、區塊鏈應用課題研究、實驗室技術創新中心運營等工作。期間，還參與多項行業及地方標準制定。近年來，工商銀行加快區塊鏈技術在金融領域的研發應用，積極探索區塊鏈與AI、大數據、5G、物聯網等技術深度融合。其中，創建了雄安征遷資金區塊鏈管理平臺，在業界首次將區塊鏈技術應用于征拆遷資金管理場景，實現政府拆遷資金管理線上化、透明化，已累計完成資金撥付100多億元。（新浪財經）[2020/4/1]

如果A和B的票一樣多，那么不誠實節點就不投票

如果A和B的票相差不多，那么不誠實節點會根據自身利益，不約而同選少的一方，最終讓A和B的票一樣多

總之，不誠實節點希望出現“得不出結論”的尷尬局面。為了避免出現這種“達不成共識”的情況，最多那個的選票最少要達到x，才能形成絕對優勢而勝出。

回到拜占庭將軍問題上，不管是進攻還是撤退，忠誠的將軍只能收取大部分將軍傳過來的命令之后，統計出一個票數最多的命令，并且執行這個命令。為了讓所有忠誠的將軍的命令一致，勝出的命令最少應該達到x個，忠誠的將軍才能放心大膽的執行這條命令，因為他知道這個命令達到了x個，其他忠誠的將軍也是執行同樣的命令。

拜占庭將軍的例子要比上面部門旅游的例子更復雜一些：部門旅游的選票是給部門行政一個人統計，統一公布；而拜占庭將軍的例子是所有將軍給其他將軍發消息，每個將軍自己統計自己收到的消息。那么會存在這樣的情況，叛徒將軍給A將軍發的進攻，給B將軍發的撤退。所以做決策的時候，x>n/2+1是不夠的，這種情況會有下面表達式3體現出來。

我們用將隱含的重要信息摘出來：

1.總人數

2.最少票數不應該比誠實節點數多，否則不誠實節點只要全部不投票，投票就將進行不下去

3.如果一個結果要代表所有誠實節點，那么起碼有一半以上的誠實節點投了這個結果

4.對于不誠實節點，可能給不同的人的投票信息不一樣

我們將這些信息轉化成表達式：

1=>n=f+h

2=>h>=x

3+4=>x>h/2+f

根據上面的3個不等式，進行推導

=>h>h/2+f

=>1.5h>h+f

=>1.5h>n

=>h>2/3*n=>f<1/3*n

上海金融科技企業運用區塊鏈等技術支持疫情防控和經濟社會發展:記者3月10日從上海市金融工作局獲悉，上海金融科技企業充分發揮金融與科技融合發展的特有優勢，積極支持疫情防控和經濟社會發展工作。其中，萬向區塊鏈和萬向信托利用區塊鏈技術打造了“萬向慈善信托賬戶管理平臺”，對捐贈人賬戶的關鍵文件和資產進行存證，并可對事件發生時間進行歷史溯源。此外，中國銀聯結合疫情期間復工復產場景，通過數字簽名、時間戳、區塊鏈等技術，向實體企業提供合同在線締約、審批、簽署的綜合解決方案，已推廣到上海住房租賃協會、深圳住建局等單位試點使用。（中國證券網）[2020/3/10]

雖然上面的推導是圍繞勝出的票數x，但是得出的結論是最多能容忍的拜占庭節點數f。也就是說，要達成共識，拜占庭節點數f必須小于總節點數的n/3，n=3f+1而且x=2f+1。為什么要算這個呢？因為后面會用到。同時，我們也知道了拜占庭節點可能的操作：

不投票

給不同的節點投不同的票

對于第2種操作，可以通過消息簽名的方式避免。那只有拜占庭節點不投票或者leader不發起投票的情況了，這種情況被稱為弱中止條件下的拜占庭將軍問題。

同步與異步

前面我們提到了網絡延遲的問題。對分布式系統來說，網絡擁塞等異常情況，有可能導致網絡延遲非常的大，甚至沒有上限。根據協議對延遲依賴情況，將協議分成了3類：

同步：網絡延遲有上限且上限是已知的；

異步：消息延遲沒有上限；

部分異步：網絡延遲有上限但是上限是未知的；

同步模型適合對網絡延遲特別敏感的場景；部分異步模型可以理解為覆蓋了一般情況下的網絡異常，比較接近日常的一般場景，最實用。

部分異步模型下，投票通常會由leader發起，由于leader可能是拜占庭節點，為了保證活性，會對多個節點進行排序，輪流當leader。一旦出現leader為拜占庭節點的情況，導致一定延遲內，不能達成一致，則換下一個leader維持投票過程。Libra實現的LibraBFT共識，使用了Hotstuff作為拜占庭容錯算法，屬于部分異步模型。

PBFT和兩階段確認

BFT是圍繞投票進行的，其中PBFT最常見。

下面是PBFT算法的大概流程，我們先看一下每個階段所代表的意思：

request：觸發leader發起提案

pre-prepare：leader準備提案，并把提案廣播給所有節點

prepare：節點要把自己的vote廣播給其他節點，所以消息復雜度是O(N^2)，同時會對收到的所有vote進行統計

commit：當這個提案達到2f+1的vote時，節點會認為這個提案取得了認可，這時候，當前節點會通知所有其他節點他打算提交這個提案，commit消息不但要表明自己接收提案，還必須包含自己收集到的2f+1個vote。如果當前節點收到了2f+1個針對這個提案的commit，這時候才表示這個結果達成了一致。這個階段比較復雜，下面會重點講。

聲音 | 臺灣“立法委”委員：區塊鏈的去中心化技術是未來民主的方向:據工商時報報道，3月31日，在金融科技論壇上，臺灣“立法委”委員何志偉則翻出近期的Apple Card議題，認為這是監管與鼓勵創新的對立，要找到平衡非常不容易，而且新興的區塊鏈的去中心化技術，是未來民主的方向，大家的聲音都能進入而且紀錄，越是公開越是透明，就能越快速找到平衡點。[2019/4/1]

上面等于發起了兩輪投票，為什么要進行兩輪投票才能最終達成一致呢？

我們來設想一下只有一輪投票的場景：

正好有那么一個時刻，3節點給1節點發送了投票消息之后，成為了拜占庭節點。2節點雖然是非拜占庭節點，但是還沒發起投票。這時候，1節點收到了3票，分別是0、1、3，所以1節點有理由覺得所有誠實節點達成了共識。但實際上并沒有達成一致，這時候2節點可能會由于超時，發起要求重新投票的請求，并且0和3有可能同意這個請求。所以，只有一輪投票有可能沒有達成一致。

為了解決上面的問題，所以PBFT協議設計中又進行了一輪投票，解決第一輪投票不能達成一致的情況，這就是commit階段。但是細想一下，第二輪投票也會出現達不成一致的情況：

雖然解決了第一輪投票的問題，但是好像第二輪投票又出現了第一輪同樣的問題？實際上PBFT對第二輪投票進行了優化：

所有節點在發送確認消息的時候，不但要告訴其他節點自己的狀態，還需要帶上證明，也就是需要帶上其他節點發給自己的2f+1個vote的簽名消息。

在區塊鏈的應用場景里，后一個塊是基于前一個塊的。如果以BFT作為共識，那么出塊順序是確定的，后面出塊的節點不僅要構建新的區塊，還需要在提案中給出前一個區塊的證明，要么2f+1簽名的commit，要么2f+1的超時簽名，否則，該出塊節點就是拜占庭節點，將發起超時投票給下一個出塊節點。

以上是對PBFT以及兩階段確認的一個大概講述。非拜占庭節點通過兩輪投票達成共識，通過多leader和超時等機制保證了協議的活性，但是，需要O(N^3)的消息復雜度。

三階段確認的Hotstuff

PBFT是一個非常經典的拜占庭容錯算法。在兩階段確認的commit階段，由于要帶上其他節點簽名的vote消息以證明自己的狀態不是說謊來的，這導致了O(N^3)的消息復雜度，因此也有明顯的瓶頸。有沒有算法能解決這個問題呢？Libra的LibraBFT共識協議選用的?

動態 | 上海農商銀行設立長三角金融科技研究院 探索區塊鏈等技術的應用:據中新網消息，上海農商銀行與新希望金融科技公司聯合發起設立長三角金融科技研究院。研究院將聚焦大數據、人工智能、云計算和區塊鏈技術，探索其在惠金融、反欺詐、智慧風控、智能運營、供應鏈金融等領域的應用。[2019/3/28]

Hotstuff?拜占庭容錯算法通過“門限簽名+三階段確認”很巧妙的解決了這個問題。

Hotstuff的第一作者是康奈爾大學的在讀博士生尹茂帆老師。對比前面的兩階段確認，我們看到，Hotstuff在prepare和commit中間多了一個pre-commit階段，為什么多一輪投票就能解決消息復雜度的問題呢？

首先，我們簡單的說明一下門限簽名的作用，感興趣的可以自己去研究一下。n個節點通過某種方式給每個節點生成了一個私鑰，但是只有一個公共的公鑰。接下來，所有的投票信息都由屬于自己的這把私鑰進行(k,n)簽名。同一條消息，只有集齊了k個節點的簽名，才能構造出一個能通過公共的公鑰驗證成功的總簽名。這樣的話，節點的提案要想達成共識，必須收集2f+1個節點對同一條“同意該提案”的消息的簽名，才能構造出一個能使用公共的公鑰驗證成功的總簽名，否則就進入了超時流程。

接下來，我們看一下使用了門限簽名之后，三階段確認大概的過程。我們來重點看一下由leader發起的4條消息：

①prepare階段：leader將包含自己的“提案+前一個commitQC”的消息msg1廣播給所有節點

②pre-commit階段：leader收到了2f+1個節點“通過msg1提案”的簽名消息，然后使用這些簽名構造一個“prepareQC總簽名”的消息msg2，并將msg2廣播給所有節點，讓他們對自己構造的prepareQC進行驗證

③commit階段：leader收到了2f+1個節點“msg2的prepareQC驗證通過”的簽名消息，然后使用這些簽名又構造成一個“pre-commitQC總簽名+提交提案”的消息msg3，并廣播給所有節點pre-commitQC進行驗證

④decide階段：leader收到了2f+1個節點“msg3的pre-commitQC驗證通過”的簽名消息，這個時候等于leader收到共識達成一致的證明，然后使用這些簽名正式構造一個commitQC總簽名的消息msg4，廣播給所有節點

以上是三階段確認的大概過程，有點繞口，從圖可以看出，與兩階段對比，主要有兩點不同：

三階段確認比兩階段確認多了一個pre-commit階段。實際上三階段確認的pre-commit階段+commit階段，就等于兩階段確認的commit階段。換句話說，兩階段確認的commit階段里包含了2f+1個節點的vote用于證明自己沒有說謊，這個證明在三階段確認中被獨立拿出來進行了一輪投票，就是上圖中的pre-commit階段。這是兩階段確認模型與三階段確認模型的主要區別，這么理解，上面的過程就不饒了。

所有節點只跟leader打交道：三階段確認巧妙的通過門限簽名，將本應該是所有節點都要收集的消息，優化成“leader統一收集，其他節點只需要對總簽名進行校驗”的過程，將消息復雜度降到了O(N)。當然，超時機制差不多，需要收集2f+1的超時簽名構造一個總簽名，替換掉commitQC。

以上就是我認為的三階段確認與兩階段確認最主要的區別，其中QC是法定節點數證書，可以理解為總的簽名。

鏈式Hotstuff

前面我們講述了三階段確認其實是BasicHotStuff，在區塊鏈的應用場景下，整個過程概括起來大概是這樣的：

總的來說就是“prepareQC->pre-commitQC->commitQC”這3個門限簽名的QC不斷的轉換，hotstuff作者們在三階段確認的基礎上，又對算法做了進一步優化，這就是ChainedHotStuff：

投票輪次和網絡消息都得到了很好的優化，將原本需要進行3輪的投票，合并到1輪了。最終的結果就成了這樣：

這是鏈式hotstuff設計巧妙的地方。

Libra的consensus組件

前面我們深入介紹了BFT的背景知識，包括拜占庭將軍的故事、拜占庭容錯算法最多能容忍的拜占庭節點數、部分同步模型；接著，我們詳細講述了兩階段確認的拜占庭容錯算法；最后，我們講述了巧妙的結合了門限簽名和三階段確認的Hotstuff，以及進一步優化后的鏈式Hotstuff。

LibraBFT共識是基于Hotstuff實現的，我們先看一下Libra的Block結構：

是不是跟鏈式Hotstuff很像？Libra在每一輪投票中，既會校驗當前Proposal的Block，同時也會對爺爺Block達成共識。這樣，爺爺Block就會被commit，并把Block包含的Transaction以及涉及的用戶狀態存儲到DB中。

所以Libra的Ledger存儲看上去總是比Block存儲低兩個高度，因為后來兩個高度的Block還沒有達成共識，分別處于pre-commitQC階段和prepareQC階段。Libra實現的共識流程大概是這樣的：

上圖有兩個需要注意的地方：

round代表了一輪投票，round的event由Pacemaker維護，Pacemaker組件主要負責算法活性，維護超時時間；

綠色表示當前round的leader，負責生成Block并發起proposal；黃色表示其他Validator節點，負責驗證和投票；紅色表示下一個round的leader，負責收集統計投票、處理commit，然后在下一個round構造Block、發起proposal；

這里有幾個關鍵的問題，在流程中沒有體現出來：

如何確定proposer

如何更新一組proposer

下面我們來逐個討論。

如何確定proposer

Libra的實現中有3種proposer策略：FixedProposer、MultipleOrderedProposers、RotatingProposer。

FixedProposer：表示指定固定節點當Proposer，一般用于測試；

RotatingProposer：表示一批節點輪流當Proposer，每個round返回一個Proposer；

MultipleOrderedProposers：復雜一些，見下圖，其中還使用了隨機數VRF算法，保障每個round所有節點得到一組相同順序的Proposer，但是每個round之間的Proposer順序不同；

所以在使用MultipleOrderedProposers的情況下，每輪投票都有一組Proposer，Proposer存在優先級，非拜占庭節點會根據Proposer的優先級，給優先級最高的Proposer投票。這樣減少了Proposer為拜占庭節點的風險，如果一組Proposer均為拜占庭節點，那么Validator投超時的票TC。

如何更新一組proposer

前面我們講述了Proposer大概的確定過程，多個round的Proposer組雖然順序不同，但是一直是相同的幾個Proposer在不停的變換順序。那如果要換掉這些Proposer呢？尤其是需要在這么多節點之間要同一時間對同一結果達成共識。

實際上，更新Proposer組需要通過transaction調用add_validator或者remove_validator的合約，transaction在打包的時候會被執行，如果存在validator更新，會把更新放到Block的block_info中，同時也會把transaction打包進Block。最后，隨著這個Block被commit，所有的Validator會根據block_info的信息更新本地的proposer組。這樣，所有的節點在同一個round把proposer組更新了，整個過程在libra中叫Reconfiguration。

總結

在Libra的第3條主線中，概念和內容比較多，我們先后介紹了這些內容：

為了保證所有賬號的數據正確，所以需要在全球范圍對transaction的順序快速達成共識；

當下主流的共識協議，例如Pow、Pos、BFT等；

Libra使用了Hotstuff算法，屬于BFT的一種，因此我們了解了很多跟BFT相關的背景知識，主要包括兩階段確認、三階段確認以及鏈式Hotstuff；

最后，我們了解了Libra的consensus組件，包括投票流程、確定proposer的流程、Reconfiguration流程等等，基本上覆蓋了LIbraBFT共識協議的主要過程。

本文作者Westar實驗室技術專家鄧啟明。這是Westar實驗室官網，歡迎大家關注?http://westar.io/

Tags：POSPROPPROBFTPOSI幣ProplandYFPRO價格BFT幣

火必