區(qū)塊鏈共識(shí)機(jī)制之拜占庭算法

高麗芬，胡全貴

（1.中國(guó)礦業(yè)大學(xué)（北京），北京 100000；2.北京國(guó)網(wǎng)信通埃森哲信息技術(shù)有限公司，北京 100000）

共識(shí)機(jī)制是區(qū)塊鏈技術(shù)的核心，那什么是“共識(shí)”呢？對(duì)于現(xiàn)實(shí)世界，共識(shí)就是一群人對(duì)一件或者多件事情達(dá)成一致的看法或者協(xié)議。在計(jì)算機(jī)世界當(dāng)中，共識(shí)包含兩個(gè)層面，第一個(gè)層面是點(diǎn)的層面，即多個(gè)節(jié)點(diǎn)對(duì)某個(gè)數(shù)據(jù)達(dá)成一致共識(shí)。第二個(gè)層面是線的問題，即多個(gè)節(jié)點(diǎn)對(duì)多個(gè)數(shù)據(jù)的順序達(dá)成一致共識(shí)。這里的節(jié)點(diǎn)可以是任意的計(jì)算機(jī)設(shè)備，比如PC電腦，筆記本，手機(jī)，路由器等，這里的數(shù)據(jù)可以是交易數(shù)據(jù)、狀態(tài)數(shù)據(jù)等。

現(xiàn)階段的共識(shí)算法分類如下圖所示：

共識(shí)機(jī)制來(lái)源于著名的“拜占庭將軍問題”，拜占庭將軍問題是由萊斯利·蘭伯特提出的點(diǎn)對(duì)點(diǎn)通信的基本問題，主要是用于分析在分布式節(jié)點(diǎn)傳輸信息時(shí)如何保持?jǐn)?shù)據(jù)的一致。

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

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

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

如果信道不能保證可靠，那么拜占庭問題無(wú)解。關(guān)于信道可靠問題，會(huì)引出兩軍問題。

如上圖所示，白軍駐扎在溝渠里，藍(lán)軍則分散在溝渠兩邊。白軍比任何一支藍(lán)軍都更為強(qiáng)大，但是藍(lán)軍若能同時(shí)合力進(jìn)攻則能夠打敗白軍。他們不能夠遠(yuǎn)程的溝通，只能派遣通信兵穿過溝渠去通知對(duì)方藍(lán)軍協(xié)商進(jìn)攻時(shí)間。是否存在一個(gè)能使藍(lán)軍必勝的通信協(xié)議，這就是兩軍問題?？吹竭@里你可能發(fā)現(xiàn)兩軍問題和拜占庭將軍問題有一定的相似性，但是我們必須注意到是，通信兵得經(jīng)過敵人的溝渠，在這個(gè)過程中他可能被捕，也就是說(shuō)，兩軍問題中信道是不可靠的，并且其中沒有叛徒之說(shuō)，這就是兩軍問題和拜占庭將軍問題的根本性不同。

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

對(duì)于 pbft 算法，因?yàn)?pbft 算法的除了需要支持容錯(cuò)故障節(jié)點(diǎn)之外，還需要支持容錯(cuò)作惡節(jié)點(diǎn)。假設(shè)集群節(jié)點(diǎn)數(shù)為n，有問題的節(jié)點(diǎn)為f。有問題的節(jié)點(diǎn)中，可以既是故障節(jié)點(diǎn)，也可以是作惡節(jié)點(diǎn)，或者只是故障節(jié)點(diǎn)或者只是作惡節(jié)點(diǎn)。那么會(huì)產(chǎn)生以下兩種情況：

第一種情況，f個(gè)有問題節(jié)點(diǎn)既是故障節(jié)點(diǎn)，又是作惡節(jié)點(diǎn)，那么根據(jù)少數(shù)服從多數(shù)的原則，集群里正常節(jié)點(diǎn)只需要比f(wàn)個(gè)節(jié)點(diǎn)再多一個(gè)節(jié)點(diǎn)，即 f+1 個(gè)節(jié)點(diǎn)，正確節(jié)點(diǎn)的數(shù)量就會(huì)比故障節(jié)點(diǎn)數(shù)量多，那么集群就能達(dá)成共識(shí)。也就是說(shuō)這種情況支持的最大容錯(cuò)節(jié)點(diǎn)數(shù)量是（n-1）/2。

第二種情況，故障節(jié)點(diǎn)和作惡節(jié)點(diǎn)都是不同的節(jié)點(diǎn)。那么就會(huì)有 f 個(gè)故障節(jié)點(diǎn)和 f 個(gè)作惡節(jié)點(diǎn)，當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)是故障節(jié)點(diǎn)后，會(huì)被集群排除在外，剩下 f 個(gè)作惡節(jié)點(diǎn)，那么根據(jù)小數(shù)服從多數(shù)的原則，集群里正常節(jié)點(diǎn)只需要比f(wàn)個(gè)節(jié)點(diǎn)再多一個(gè)節(jié)點(diǎn)，即f+1 個(gè)節(jié)點(diǎn)，正確節(jié)點(diǎn)的數(shù)量就會(huì)比作惡節(jié)點(diǎn)數(shù)量多，那么集群就能達(dá)成共識(shí)。所以，所有類型的節(jié)點(diǎn)數(shù)量加起來(lái)就是 f+1 個(gè)正確節(jié)點(diǎn)，f個(gè)故障節(jié)點(diǎn)和f個(gè)作惡節(jié)點(diǎn)，即 3f+1=n，f=（n-1）/3。

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

這里一個(gè)核心問題就是，為什么有f個(gè)節(jié)點(diǎn)未響應(yīng)或出錯(cuò)時(shí)，為了保證系統(tǒng)的正常，需要總共有3f+1個(gè)節(jié)點(diǎn)進(jìn)行投票。

同樣用國(guó)王的例子，假設(shè)除了我（國(guó)王）一共有n個(gè)大臣，我知道其中有f個(gè)大臣是叛徒或者未響應(yīng)，所以我一定要能從n-f個(gè)大臣的回應(yīng)中進(jìn)行判斷。然而由于是飛鴿傳書，所以當(dāng)我陸續(xù)收到n-f個(gè)傳來(lái)的消息后，我并不知道之后是否還會(huì)有新的消息傳來(lái)。因?yàn)槿绻鹒個(gè)有問題的大臣都是未響應(yīng)，那么我將不會(huì)收到新的消息，如果其中有大臣是叛徒，我之后還會(huì)收到消息，但作為國(guó)王的現(xiàn)在不知道是哪種情況，卻需要立刻作出進(jìn)攻還是投降的判斷。

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

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

（1）客戶端發(fā)送請(qǐng)求給主節(jié)點(diǎn)

（2）主節(jié)點(diǎn)廣播請(qǐng)求給其它節(jié)點(diǎn)，節(jié)點(diǎn)執(zhí)行pbft 算法的三階段共識(shí)流程。

（3）節(jié)點(diǎn)處理完三階段流程后，返回消息給客戶端。

（4）客戶端收到來(lái)自 f+1 個(gè)節(jié)點(diǎn)的相同消息后，代表共識(shí)已經(jīng)正確完成。為什么收到 f+1 個(gè)節(jié)點(diǎn)的相同消息后就代表共識(shí)已經(jīng)正確完成？

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

算法的核心三個(gè)階段分別是 pre-prepare 階段（預(yù)準(zhǔn)備階段），prepare 階段（準(zhǔn)備階段），commit 階段（提交階段）。圖中的C代表客戶端，0，1，2，3 代表節(jié)點(diǎn)的編號(hào)，打叉的3代表可能是故障節(jié)點(diǎn)或者是問題節(jié)點(diǎn)，這里表現(xiàn)的行為就是對(duì)其它節(jié)點(diǎn)的請(qǐng)求無(wú)響應(yīng)。0 是主節(jié)點(diǎn)。

Pre-prepare 階段：節(jié)點(diǎn)收到 pre-prepare 消息后，會(huì)有兩種選擇，一種是接受，一種是不接受。什么時(shí)候才不接受主節(jié)點(diǎn)發(fā)來(lái)的 pre-prepare 消息呢？一種典型的情況就是如果一個(gè)節(jié)點(diǎn)接受到了一條 pre-pre 消息，消息里的 v 和 n 在之前收到里的消息是曾經(jīng)出現(xiàn)過的，但是 d 和 m 卻和之前的消息不一致，或者請(qǐng)求編號(hào)不在高低水位之間（高低水位的概念在下面會(huì)進(jìn)行解釋），這時(shí)候就會(huì)拒絕請(qǐng)求。拒絕的邏輯就是主節(jié)點(diǎn)不會(huì)發(fā)送兩條具有相同的 v 和 n，但 d 和 m 卻不同的消息。

Prepare 階段：節(jié)點(diǎn)同意請(qǐng)求后會(huì)向其它節(jié)點(diǎn)發(fā)送 prepare 消息。這里要注意一點(diǎn)，同一時(shí)刻不是只有一個(gè)節(jié)點(diǎn)在進(jìn)行這個(gè)過程，可能有 n 個(gè)節(jié)點(diǎn)也在進(jìn)行這個(gè)過程。因此節(jié)點(diǎn)是有可能收到其它節(jié)點(diǎn)發(fā)送的 prepare 消息的。在一定時(shí)間范圍內(nèi)，一個(gè)節(jié)點(diǎn)如果收到 2f 個(gè)不同節(jié)點(diǎn)的 prepare 消息，就代表prepare 階段已經(jīng)完成。

Commit 階段：于是進(jìn)入 commit 階段。向其它節(jié)點(diǎn)廣播 commit 消息，同理，這個(gè)過程可能是有 n 個(gè)節(jié)點(diǎn)也在進(jìn)行的。因此可能會(huì)收到其它節(jié)點(diǎn)發(fā)過來(lái)的 commit 消息，當(dāng)收到 2f+1 條 commit消息后（包括該節(jié)點(diǎn)本身），代表大多數(shù)節(jié)點(diǎn)已經(jīng)進(jìn)入 commit 階段，這一階段已經(jīng)達(dá)成共識(shí)，于是節(jié)點(diǎn)就會(huì)執(zhí)行請(qǐng)求，寫入數(shù)據(jù)。

圖中A節(jié)點(diǎn)的當(dāng)前請(qǐng)求編號(hào)是 1039，即checkpoint為1039，B節(jié)點(diǎn)的 checkpoint 為1133。當(dāng)前系統(tǒng) stable checkpoint 為 1034。那么1034這個(gè)編號(hào)就是低水位，而高水位 H=低水位 h+L，其中L是可以設(shè)定的數(shù)值。因此圖中系統(tǒng)的高水位為 1034+100=1134。舉個(gè)例子：如果 B 當(dāng)前的 checkpoint 已經(jīng)為 1134，而A的 checkpoint 還是 1039，假如有新請(qǐng)求給 B 處理時(shí)，B會(huì)選擇等待，等到 A 節(jié)點(diǎn)也處理到和 B 差不多的請(qǐng)求編號(hào)時(shí)，比如 A 也處理到1112 了，這時(shí)會(huì)有一個(gè)機(jī)制更新所有節(jié)點(diǎn)的 stabel checkpoint，比如可以把 stabel checkpoint 設(shè)置成 1100，于是 B 又可以處理新的請(qǐng)求了，如果 L 保持100 不變，這時(shí)的高水位就會(huì)變成 1100+100=1200 了。

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

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

NEO 代幣的持有者通過投票，可以選出其所支持的記賬人。隨后由被選出的記賬人團(tuán)體通過 BFT 算法，來(lái)達(dá)成共識(shí)并生成新的區(qū)塊。投票在 NEO 網(wǎng)絡(luò)持續(xù)實(shí)時(shí)進(jìn)行，而非按照固定任期。

DBFT 對(duì)由 n 個(gè)共識(shí)節(jié)點(diǎn)組成的共識(shí)系統(tǒng)，提供 f=（n-1）/3的容錯(cuò)能力，這種容錯(cuò)能力同時(shí)包含安全性和可用性，可以抵抗一般性故障和拜占庭故障，并適用于任何網(wǎng)絡(luò)環(huán)境。DBFT 具有良好的最終性，一個(gè)確認(rèn)即最終確認(rèn)，區(qū)塊無(wú)法被分叉，交易也不會(huì)發(fā)生撤銷或回滾。

NEO在 DBFT 共識(shí)機(jī)制下，每 15～20 秒生成一個(gè)區(qū)塊，交易吞吐量實(shí)測(cè)可達(dá)到約 1000TPS，在公有鏈中性能優(yōu)秀。通過適當(dāng)優(yōu)化，有能力到達(dá) 10000TPS，可以支持大規(guī)模的商業(yè)化應(yīng)用。