區塊鏈共識機制之拜占庭算法

高麗芬，胡全貴

（1.中國礦業大學（北京），北京 100000；2.北京國網信通埃森哲信息技術有限公司，北京 100000）

共識機制是區塊鏈技術的核心，那什么是“共識”呢？對于現實世界，共識就是一群人對一件或者多件事情達成一致的看法或者協議。在計算機世界當中，共識包含兩個層面，第一個層面是點的層面，即多個節點對某個數據達成一致共識。第二個層面是線的問題，即多個節點對多個數據的順序達成一致共識。這里的節點可以是任意的計算機設備，比如PC電腦，筆記本，手機，路由器等，這里的數據可以是交易數據、狀態數據等。

現階段的共識算法分類如下圖所示：

共識機制來源于著名的“拜占庭將軍問題”，拜占庭將軍問題是由萊斯利·蘭伯特提出的點對點通信的基本問題，主要是用于分析在分布式節點傳輸信息時如何保持數據的一致。

Pbft算法的提出主要是為了解決拜占庭將軍問題。那什么是拜占庭將軍問題呢？

拜占庭位于如今的土耳其的伊斯坦布爾，是古代東羅馬帝國的首都。拜占庭羅馬帝國國土遼闊，為了達到防御目的，每塊封底都駐扎著一支由將軍統領的軍隊，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳遞消息。在戰爭的時候，拜占庭軍隊內所有將軍必須達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定影響將軍們達成一致的共識。在已知有將軍是叛徒的情況下，其余忠誠的將軍如何達成一致協議的問題，這就是拜占庭將軍問題。

應該明確的是，拜占庭將軍問題中并不去考慮通信兵是否會被截獲或無法傳遞信息等問題，即消息傳遞的信道絕無問題。

如果信道不能保證可靠，那么拜占庭問題無解。關于信道可靠問題，會引出兩軍問題。

如上圖所示，白軍駐扎在溝渠里，藍軍則分散在溝渠兩邊。白軍比任何一支藍軍都更為強大，但是藍軍若能同時合力進攻則能夠打敗白軍。他們不能夠遠程的溝通，只能派遣通信兵穿過溝渠去通知對方藍軍協商進攻時間。是否存在一個能使藍軍必勝的通信協議，這就是兩軍問題。看到這里你可能發現兩軍問題和拜占庭將軍問題有一定的相似性，但是我們必須注意到是，通信兵得經過敵人的溝渠，在這個過程中他可能被捕，也就是說，兩軍問題中信道是不可靠的，并且其中沒有叛徒之說，這就是兩軍問題和拜占庭將軍問題的根本性不同。

拜占庭將軍問題最早是由 Leslie Lamport 與另外兩人在 1982年發表的論文《The Byzantine Generals Problem 》提出的，他證明了在將軍總數大于3f，背叛者為f或者更少時，忠誠的將軍可以達成命令上的一致，即 3f+1＜=n。算法復雜度為 o（n^（f+1））。而 Miguel Castro（卡斯特羅）和 Barbara Liskov（利斯科夫）在1999年發表的論文《 Practical Byzantine Fault Tolerance 》中首次提出pbft算法，該算法容錯數量也滿足3f+1＜=n，算法復雜度為o（n^2）。

對于 pbft 算法，因為 pbft 算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為n，有問題的節點為f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那么會產生以下兩種情況：

第一種情況，f個有問題節點既是故障節點，又是作惡節點，那么根據少數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那么集群就能達成共識。也就是說這種情況支持的最大容錯節點數量是（n-1）/2。

第二種情況，故障節點和作惡節點都是不同的節點。那么就會有 f 個故障節點和 f 個作惡節點，當發現節點是故障節點后，會被集群排除在外，剩下 f 個作惡節點，那么根據小數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即f+1 個節點，正確節點的數量就會比作惡節點數量多，那么集群就能達成共識。所以，所有類型的節點數量加起來就是 f+1 個正確節點，f個故障節點和f個作惡節點，即 3f+1=n，f=（n-1）/3。

舉個例子，我是一個愚昧的國王，沒有自己的判斷力，我不知道應該對敵國進攻還是投降好。我有一些大臣，我希望聽從他們的意見做出決定，但是他們現在都離我很遠，我只能通過飛鴿傳書的方式告知他們目前的問題，得到他們的選擇。然而，可能出現大臣叛變，故意提出相反的觀點（作惡節點），也可能出現鴿子在傳輸過程中飛錯了，我沒有得到該大臣的選擇（網絡堵塞）。PBFT可以保證如果我有3f+1的大臣的話，即使其中有f個大臣叛變或者沒有響應，我依然可以得出共識的正確結果。

這里一個核心問題就是，為什么有f個節點未響應或出錯時，為了保證系統的正常，需要總共有3f+1個節點進行投票。

同樣用國王的例子，假設除了我（國王）一共有n個大臣，我知道其中有f個大臣是叛徒或者未響應，所以我一定要能從n-f個大臣的回應中進行判斷。然而由于是飛鴿傳書，所以當我陸續收到n-f個傳來的消息后，我并不知道之后是否還會有新的消息傳來。因為如果f個有問題的大臣都是未響應，那么我將不會收到新的消息，如果其中有大臣是叛徒，我之后還會收到消息，但作為國王的現在不知道是哪種情況，卻需要立刻作出進攻還是投降的判斷。

最壞的情況下，剩下的f個大臣都是好人，只是鴿子飛得慢我還沒收到消息，也就是說我收到消息的n-f的大臣中有f個大臣都是叛徒，即f個叛徒和n-2f個好人。由于多數者勝，所以只有當n-2f＞f的情況下，作為國王的我會做出正確的決定，即n＞3f，n最小需要取3f+1。

pbft 算法的基本流程主要有以下四步：

（1）客戶端發送請求給主節點

（2）主節點廣播請求給其它節點，節點執行pbft 算法的三階段共識流程。

（3）節點處理完三階段流程后，返回消息給客戶端。

（4）客戶端收到來自 f+1 個節點的相同消息后，代表共識已經正確完成。為什么收到 f+1 個節點的相同消息后就代表共識已經正確完成？

從上面的介紹里可知，無論是最好的情況還是最壞的情況，如果客戶端收到 f+1 個節點的相同消息，那么就代表有足夠多的正確節點已全部達成共識并處理完畢了。

算法的核心三個階段分別是 pre-prepare 階段（預準備階段），prepare 階段（準備階段），commit 階段（提交階段）。圖中的C代表客戶端，0，1，2，3 代表節點的編號，打叉的3代表可能是故障節點或者是問題節點，這里表現的行為就是對其它節點的請求無響應。0 是主節點。

Pre-prepare 階段：節點收到 pre-prepare 消息后，會有兩種選擇，一種是接受，一種是不接受。什么時候才不接受主節點發來的 pre-prepare 消息呢？一種典型的情況就是如果一個節點接受到了一條 pre-pre 消息，消息里的 v 和 n 在之前收到里的消息是曾經出現過的，但是 d 和 m 卻和之前的消息不一致，或者請求編號不在高低水位之間（高低水位的概念在下面會進行解釋），這時候就會拒絕請求。拒絕的邏輯就是主節點不會發送兩條具有相同的 v 和 n，但 d 和 m 卻不同的消息。

Prepare 階段：節點同意請求后會向其它節點發送 prepare 消息。這里要注意一點，同一時刻不是只有一個節點在進行這個過程，可能有 n 個節點也在進行這個過程。因此節點是有可能收到其它節點發送的 prepare 消息的。在一定時間范圍內，一個節點如果收到 2f 個不同節點的 prepare 消息，就代表prepare 階段已經完成。

Commit 階段：于是進入 commit 階段。向其它節點廣播 commit 消息，同理，這個過程可能是有 n 個節點也在進行的。因此可能會收到其它節點發過來的 commit 消息，當收到 2f+1 條 commit消息后（包括該節點本身），代表大多數節點已經進入 commit 階段，這一階段已經達成共識，于是節點就會執行請求，寫入數據。

圖中A節點的當前請求編號是 1039，即checkpoint為1039，B節點的 checkpoint 為1133。當前系統 stable checkpoint 為 1034。那么1034這個編號就是低水位，而高水位 H=低水位 h+L，其中L是可以設定的數值。因此圖中系統的高水位為 1034+100=1134。舉個例子：如果 B 當前的 checkpoint 已經為 1134，而A的 checkpoint 還是 1039，假如有新請求給 B 處理時，B會選擇等待，等到 A 節點也處理到和 B 差不多的請求編號時，比如 A 也處理到1112 了，這時會有一個機制更新所有節點的 stabel checkpoint，比如可以把 stabel checkpoint 設置成 1100，于是 B 又可以處理新的請求了，如果 L 保持100 不變，這時的高水位就會變成 1100+100=1200 了。

對于 pbft 算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人（2f+1）都認為老大的命令是對的時候，我才會去執行命令。那什么時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。

對于 pbft 算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人（2f+1）都認為老大的命令是對的時候，我才會去執行命令。那什么時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。

NEO 代幣的持有者通過投票，可以選出其所支持的記賬人。隨后由被選出的記賬人團體通過 BFT 算法，來達成共識并生成新的區塊。投票在 NEO 網絡持續實時進行，而非按照固定任期。

DBFT 對由 n 個共識節點組成的共識系統，提供 f=（n-1）/3的容錯能力，這種容錯能力同時包含安全性和可用性，可以抵抗一般性故障和拜占庭故障，并適用于任何網絡環境。DBFT 具有良好的最終性，一個確認即最終確認，區塊無法被分叉，交易也不會發生撤銷或回滾。

NEO在 DBFT 共識機制下，每 15～20 秒生成一個區塊，交易吞吐量實測可達到約 1000TPS，在公有鏈中性能優秀。通過適當優化，有能力到達 10000TPS，可以支持大規模的商業化應用。