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

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

俄羅斯將采用區塊鏈技術來創建平臺替代SWIFT支付系統:金色財經報道，來自俄羅斯圣彼得堡國立大學國家技術計劃能力中心的專家宣布，他們正準備試用一種新的銀行間支付系統，以替代SWIFT。由于莫斯科決定入侵烏克蘭而實施的金融限制，俄羅斯主要銀行現在無法進入后者。

該大學在一份聲明中說：“去中心化銀行間金融信息系統的試點版本已準備好進行測試，并可在銀行中使用。” 該中心的技術總監亞歷山大·基里耶夫說，初步測試顯示出良好的效果。目前在一個節點的傳輸速度超過每秒 25,000 條消息，未來網絡的容量可以增加。（news.bitcoin）[2022/7/13 2:10:45]

三階段確認的Hotstuff

鏈式Hotstuff

BFT的安全性與活性

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

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

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

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

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

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

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

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

能容忍的拜占庭節點數

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

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

Tether首席技術官：Tether Gold是一個時代產生共鳴的產品:Tether首席技術官Paolo Ardoino表示，在不確定的時期，人們希望有機會獲得黃金。而Tether Gold顯然是一個在這個時代產生共鳴的產品。而近期黃金價格屢創新高，Tether Gold穩定幣價格也隨之上漲。（Cointelegraph）[2020/7/27]

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

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

不投票

給不同的節點投不同的票

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

金財互聯：利用區塊鏈等技術經驗 打造廣州南沙數字化基礎建設平臺:金色財經報道，金財互聯（002530）發布公告稱，公司與廣州南沙經濟技術開發區商務局簽訂協議，將充分利用在區塊鏈、大數據、云計算等互聯網先進技術方面積累的經驗，擬在南沙打造面向新零售、新商業、新業態泛電商從業群體的數字化基礎建設平臺，助力南沙打造新商業服務與數字化監管平臺。[2020/5/10]

同步與異步

前面我們提到了網絡延遲的問題。對分布式系統來說，網絡擁塞等異常情況，有可能導致網絡延遲非常的大，甚至沒有上限。根據協議對延遲依賴情況，將協議分成了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節點給1節點發送了投票消息之后，成為了拜占庭節點。2節點雖然是非拜占庭節點，但是還沒發起投票。這時候，1節點收到了3票，分別是0、1、3，所以1節點有理由覺得所有誠實節點達成了共識。但實際上并沒有達成一致，這時候2節點可能會由于超時，發起要求重新投票的請求，并且0和3有可能同意這個請求。所以，只有一輪投票有可能沒有達成一致。

聲音 | 東北證券：區塊鏈技術具有提升多中心的協作效率 行業應用前景廣泛:據第一財經今日消息，東北證券表示，區塊鏈技術具有提升多中心的協作效率、去中介，提升多方信任、數據難以篡改，可追溯，可審計等優點，可實現在多方間達成可信記錄和可新合約，行業應用前景廣泛。1）在可信記錄方面，目前基于電子簽名、可信時間戳、哈希校驗值、區塊鏈存證四項技術的證據均可被在我國互聯網法庭中被認可，其中哈希校驗值與區塊鏈存證均基于區塊鏈技術，互聯網法庭有助于極大提升法院處理效率。2）多方可信合約方面，區塊鏈技術由于其難以篡改性，未來有望廣泛應用于多方合同的簽訂，單獨一方難以對于已簽訂合同進行修改，有助于提升合作各方之間的結算效率。[2019/10/28]

為了解決上面的問題，所以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階段，為什么多一輪投票就能解決消息復雜度的問題呢？

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

政策 | 上海市將利用區塊鏈等技術培育智慧供應鏈生態圈:8月30日，上海市人民政府印發了《關于本市積極推進供應鏈創新與應用的實施意見》， 指出上海市將聚焦大宗商品、消費品、醫藥、物流等重點領域，推廣應用云計算、大數據、物聯網、人工智能、區塊鏈等先進技術，培育形成整合供應鏈各環節、掌握行業大數據的智慧供應鏈生態圈。并研究利用區塊鏈、人工智能等新興技術，建立基于供應鏈的信用評價機制。[2018/9/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：POSPROPROPBFTCPOS價格Fixed Rate Protocolprops幣還會上架嘛BFT幣

USDT