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

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和兩階段確認

住建部等十三部委：在建造全過程加大區塊鏈等技術集成與創新應用:7月28日消息，住建部等十三部委印發關于推動智能建造與建筑工業化協同發展的指導意見。要求加快推動新一代信息技術與建筑工業化技術協同發展，在建造全過程加大建筑信息模型（BIM）、互聯網、物聯網、大數據、云計算、移動通信、人工智能、區塊鏈等新技術的集成與創新應用。（證券時報）[2020/7/28]

三階段確認的Hotstuff

鏈式Hotstuff

BFT的安全性與活性

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

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

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

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

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

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

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

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

能容忍的拜占庭節點數

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

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

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

動態 | 技術加持新型供應鏈金融 破解鏈條長尾端中小企融資難題:據中證網報道，多位專家和業內人士27日在第七屆中國中小企業投融資交易會·中國供應鏈金融高峰論壇上表示，隨著人工智能、區塊鏈、云計算、大數據等前沿科技在金融領域的廣泛應用，傳統意義上的銀行風控難和成本高等難題迎來曙光。尤其是通過區塊鏈打破傳統信息不對稱壁壘，有望從根本上破解鏈條長尾端的中小企業融資難題。[2019/6/27]

如果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

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

不投票

給不同的節點投不同的票

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

動態 | 電影制片人Dominique Boutonnat建議將區塊鏈技術應用于電影制作流程:據ICO Examiner消息，電影《無法觸碰》的制片人Dominique Boutonnat最近向法國電影中心（CNC）提交了一份139頁的報告。Boutonnat在報告中建議將將區塊鏈技術應用于電影制作流程，具體包括： 1. 為了保證數據的完整性以及提高處理速度，電影及視聽登記（RCA）應該轉移到基于區塊鏈的平臺上； 2. 對劇院門票征收的稅款應記錄在鏈上，以便實時收集數據，防止管理不善或出現虛假的上座率數字； 3. 將區塊鏈技術應用于傳媒行業的價格商討，確保收入在公司、平臺、演員、導演、制片人和其他工作人員之間公平分配。[2019/5/19]

同步與異步

前面我們提到了網絡延遲的問題。對分布式系統來說，網絡擁塞等異常情況，有可能導致網絡延遲非常的大，甚至沒有上限。根據協議對延遲依賴情況，將協議分成了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，這時候才表示這個結果達成了一致。這個階段比較復雜，下面會重點講。

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

聲音 | 信息發展總裁：區塊鏈技術在檔案系統的應用中大有可為:據每日經濟新聞報道，上海中信信息發展股份有限公司（300469）總裁黃海清在接受《每日經濟新聞》記者專訪時表示，檔案是大數據的基礎之一，檔案未來的發展趨勢其一包括，從技術角度出發，在檔案系統的應用中會遇到如何防止檔案被篡改、如何證明檔案的真實性等問題，那么具有去中心化和防篡改特性的區塊鏈技術在這其中就大有可為。[2019/1/13]

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

正好有那么一個時刻，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共識協議選用的?

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

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

聲音 | 清華大學柳斌杰：建議用區塊鏈技術構建知識付費保護體系:據財新網消息，在11月20日第九屆財新峰會《傳媒領袖專場：付費閱讀與媒體責任》專場，中國出版協會理事長、清華大學新聞與傳播學院院長柳斌杰就付費閱讀表示，知識付費是總的趨勢，建議用區塊鏈技術來保護新聞IP提升價值，構建自己的新聞知識付費保護體系。[2018/11/21]

首先，我們簡單的說明一下門限簽名的作用，感興趣的可以自己去研究一下。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：POSPROPROPSERPosition TokenDDDX ProtocolPROP幣SERV

中幣交易所