實用拜占庭容錯演算法與區塊鏈技術

最近經常看到這樣的話「區塊鏈技術很好的解決了拜占庭將軍問題」，那麼什麼是拜占庭將軍問題，由於東羅馬帝國的國土遼闊，其首都是拜占庭，基於防禦目的，每個軍隊都相隔遙遠，因此將軍間只能靠通信兵傳遞消息。在戰爭時，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍，因為唯有達成一致的行動才能獲致勝利。但將軍中若存在叛徒，叛徒可以採取修改消息以欺騙某些將軍進行進攻或防守行動，或致使他們無法做出決定，缺乏一致行動的結果則將註定戰事的失利，這就是產生了拜占庭將軍問題。

區塊鏈上分散式網路中節點所出現的任何錯誤（如，偽造簽名、惡意破壞系統的一致性、超時、重複發送消息等）都會導致數據的一致性問題，這就是區塊鏈中存在的拜占庭將軍問題。但是，拜占庭將軍問題中並不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問題。而在消息可能丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。所以拜占庭將軍問題是在假定信道沒問題的前提下進行一致性和容錯性相關研究的，若考慮信道的穩定性問題，就轉移到了另一個著名問題「兩軍」問題上來了，這裡姑且不表。

無論是Bitcoin的POW還是Ethereum的POS或者Hyperledger的PBFT，共識演算法作為區塊鏈技術的核心機制，是無論幣圈還是鏈圈都形成的共識，各共識演算法各有優缺點，總體上隨著區塊鏈技術的深入以及更多應用和基礎平台的湧現，共識演算法正處於不斷完善和優化的過程中，無所謂優劣，只是適用的場景不同。 這裡重點分析一下Hyperledger fbric中的PBFT共識演算法。

PBFT(PracticalByzantine Fault Tolerance)又稱實用拜占庭容錯演算法，前面說了，拜占庭將軍問題的解決是建立在通信兵可以正確的傳達信息的基礎上的，即信道絕對可信，由「兩軍」問題可以證明理論上可信通道是可以實現的。由拜占庭問題的定義，各方行動的一致性決定了戰爭的成敗，要麼一致進攻，要麼一致防守，那是否可以理解成拜占庭將軍問題本質上是一致性問題呢？答案是否定的，因為可能存在忠誠的將軍因為通信兵的叛變而在有利的條件進行沒有進行一致性進攻或者在不利條件下都一致沒有進攻，所以除了一致性還應考慮正確性的問題。而正確性該如何定義？每一個將軍的判斷可能都不同，到底誰是正確的呢？這個問題可以轉化成每個忠誠的將軍都不會因為別的將軍因叛徒的干擾而對其忠誠產生懷疑從而不採用他傳達的消息，也就是說每個忠誠的將軍都能正確的表達自己的意思。所以拜占庭將軍問題可以被簡化成所有忠誠的將軍都能夠讓別的將軍接收到自己的真實意圖，並最終一致行動，本質上就是「一致性」和「正確性」的問題。PBFT演算法針對的是忠誠的將軍，因為叛徒可以做出超出約定的判斷，在叛徒的干擾下找到一個抗干擾的演算法即是PBFT演算法誕生的初衷。

確保拜占庭將軍問題的一致性和正確性主要有三個步驟，預備、準備和確認。

C為發送請求端，0123為服務端節點，0為主節點，其它為備份節點，3為宕機的服務端節點：

1. Request：請求端C發送請求到任一服務端節點，假設是0

2. Pre-Prepare：服務端節點0收到C的請求後進行全網廣播，擴散至123

3. Prepare：123收到廣播後記錄並再次廣播，1廣播到023，2廣播到013，3因為宕機無法記錄也無法廣播

4. Commit：0123節點在Prepare階段，若收到超過一定數量的相同請求，則進入Commit階段，並廣播Commit請求

5.Reply：0123節點在Commit階段，若收到超過一定數量（2F+1【包括自身】）的相同請求，則對C進行反饋

上述步驟驗證了一個公式即R≥3F+1的時候可以確保一致性和正確性，其中R為服務端節點數量，F為有問題的服務端節點數量。只是為什麼是3而不是其它數字？筆者從數學角度做了一些簡單推演。

假設有三個將軍（R=3），其中將軍3是叛徒（F=1），將軍1發送進攻的消息給將軍2和將軍3，將軍3為了破壞一致性，向將軍2發送了撤退的消息，那麼將軍2將無法判斷將軍1是叛徒還是將軍3是叛徒而無法準確做出是進攻還是撤退的判斷。可以看出將軍1的身份和將軍2,3有所不同，類似於司令的角色了，三者的地位等價性被破壞，所以有必要在此前提下做進一步推演。見下圖：

假設將軍1是叛徒，他分別向將軍2和將軍3發出了進攻和撤退的命令，這時將軍2和將軍3也會凌亂，二者無法判斷將軍1是叛徒還是對方是叛徒，行動無法達成一致。這個推演中3

現在把維度提升一階，令R=4，F=1，R如下圖，如果將軍4是叛徒，他在收到將軍1的進攻消息後為了破壞一致性向將軍2和將軍3發出了撤退的消息，忠誠的將軍2和將軍3則分別向對方傳達了將軍1的進攻消息，那麼將軍2和將軍3均收到2個進攻1個撤退的消息，根據少數服從多數原則，可以判斷將軍4為叛徒，並做出進攻的一致性行動。見下圖：

假設作為司令員的將軍1是叛徒，分別向將軍2,3,4發出的指令，那麼將軍2,3,4最終收到的消息為2次進攻，1次撤退，根據少數服從多數原則，最終採取進攻的行動，將軍4可以判讀出將軍1為叛徒，而將軍2和將軍3則會把將軍4誤認為叛徒。這會損壞一些正確性，但是能確保行動的一致性和行動的正確性。

這個推演4=3*1+1,恰好滿足R≥3F+1的邊界，繼續增加維度的推演同理，有興趣的朋友可以試一試。至此可以證明係數為3是合理的，其實這個公式符合四模冗餘系統的原則，相對於三模冗餘系統只能容已知錯誤結果的靜態化情形，四模冗餘系統滿足了在叛徒做出各種判斷的情況下的動態容錯要求。就是把自己的命令告訴其他人，並對通過遞歸演算法從其他將軍傳來的命令取多數的方法來得到自己的結論，可以保證在叛徒數量少於1/3的情況下，忠誠的將軍可以實現一致性和正確性要求，據此解決拜占庭將軍問題。

題外話：上圖是以二維表的方式展示的實用拜占庭容錯演算法的部分推算結果，①~③完美表現了R≥3F+1情況下拜占庭容錯能夠容納將近1/3的錯誤節點誤差，但是④並不滿足R≥3F+1，卻仍然達到了最終的一致性和正確性，假設按這種推理的思路，只要F/R小於1/2，結合少數服從多數的原則就可以達到一致性了，這豈不是和PBFT的賴以成立的數學理論基礎相悖？！也無筆者把自己繞到溝里了，還請到訪的高人指點。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！