對(duì)數(shù)據(jù)順序達(dá)成一致共識(shí)是很多共識(shí)算法要解決的本質(zhì)問題
創(chuàng)新互聯(lián)提供網(wǎng)站建設(shè)、成都做網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)，品牌網(wǎng)站制作，1元廣告等致力于企業(yè)網(wǎng)站建設(shè)與公司網(wǎng)站制作，10年的網(wǎng)站開發(fā)和建站經(jīng)驗(yàn),助力企業(yè)信息化建設(shè)，成功案例突破近1000家,是您實(shí)現(xiàn)網(wǎng)站建設(shè)的好選擇.
Fabic的pbft算法實(shí)現(xiàn)
現(xiàn)階段的共識(shí)算法主要可以分成三大類：公鏈，聯(lián)盟鏈和私鏈
私鏈，所有節(jié)點(diǎn)可信
聯(lián)盟鏈，存在對(duì)等的不信任節(jié)點(diǎn)
私鏈：私鏈的共識(shí)算法即區(qū)塊鏈這個(gè)概念還沒普及時(shí)的傳統(tǒng)分布式系統(tǒng)里的共識(shí)算法，比如 zookeeper 的 zab 協(xié)議，就是類 paxos 算法的一種。私鏈的適用環(huán)境一般是不考慮集群中存在作惡節(jié)點(diǎn)，只考慮因?yàn)橄到y(tǒng)或者網(wǎng)絡(luò)原因?qū)е碌墓收瞎?jié)點(diǎn)。
聯(lián)盟鏈：聯(lián)盟鏈中，經(jīng)典的代表項(xiàng)目是 Hyperledger 組織下的 Fabric 項(xiàng)目， Fabric0.6 版本使用的就是 pbft 算法。聯(lián)盟鏈的適用環(huán)境除了需要考慮集群中存在故障節(jié)點(diǎn)，還需要考慮集群中存在作惡節(jié)點(diǎn)。對(duì)于聯(lián)盟鏈，每個(gè)新加入的節(jié)點(diǎn)都是需要驗(yàn)證和審核的。
公鏈：公鏈不僅需要考慮網(wǎng)絡(luò)中存在故障節(jié)點(diǎn)，還需要考慮作惡節(jié)點(diǎn)，這一點(diǎn)和聯(lián)盟鏈?zhǔn)穷愃频?。和?lián)盟鏈最大的區(qū)別就是，公鏈中的節(jié)點(diǎn)可以很自由的加入或者退出，不需要嚴(yán)格的驗(yàn)證和審核。
在公有鏈中用的最多的是pow算法和pos算法，這些算法都是參與者的利益直接相關(guān)，通過利益來制約節(jié)點(diǎn)誠(chéng)實(shí)的工作，解決分布式系統(tǒng)中的拜占庭問題。拜占庭容錯(cuò)算法是一種狀態(tài)機(jī)副本復(fù)制算法，通過節(jié)點(diǎn)間的多輪消息傳遞，網(wǎng)絡(luò)內(nèi)的所有誠(chéng)實(shí)節(jié)點(diǎn)就可以達(dá)成一致的共識(shí)。
使用拜占庭容錯(cuò)算法不需要發(fā)行加密貨幣，但是只能用于私有鏈或者聯(lián)盟鏈，需要對(duì)節(jié)點(diǎn)的加入進(jìn)行權(quán)限控制；不能用于公有鏈，因?yàn)楣墟溨兴泄?jié)點(diǎn)都可以隨意加入退出，無(wú)法抵擋女巫攻擊（sybil attack）
raft 算法包含三種角色，分別是：跟隨者（ follower ），候選人（candidate ）和領(lǐng)導(dǎo)者（ leader ）。集群中的一個(gè)節(jié)點(diǎn)在某一時(shí)刻只能是這三種狀態(tài)的其中一種，這三種角色是可以隨著時(shí)間和條件的變化而互相轉(zhuǎn)換的。
raft 算法主要有兩個(gè)過程：一個(gè)過程是領(lǐng)導(dǎo)者選舉，另一個(gè)過程是日志復(fù)制，其中日志復(fù)制過程會(huì)分記錄日志和提交數(shù)據(jù)兩個(gè)階段。raft 算法支持最大的容錯(cuò)故障節(jié)點(diǎn)是（N-1）/2，其中 N 為 集群中總的節(jié)點(diǎn)數(shù)量。
國(guó)外有一個(gè)動(dòng)畫介紹raft算法介紹的很透徹，鏈接地址為： 。這個(gè)動(dòng)畫主要包含三部分內(nèi)容，第一部分介紹簡(jiǎn)單版的領(lǐng)導(dǎo)者選舉和日志復(fù)制的過程，第二部分內(nèi)容介紹詳細(xì)版的領(lǐng)導(dǎo)者選舉和日志復(fù)制的過程，第三部分內(nèi)容介紹的是如果遇到網(wǎng)絡(luò)分區(qū)（腦裂），raft 算法是如何恢復(fù)網(wǎng)絡(luò)一致的。
pbft 算法的提出主要是為了解決拜占庭將軍問題
要讓這個(gè)問題有解，有一個(gè) 十分重要的前提 ，那就是 信道必須是可靠的 。如果信道不能保證可靠，那么拜占庭問題無(wú)解。關(guān)于信道可靠問題，會(huì)引出兩軍問題。兩軍問題的結(jié)論是，在一個(gè)不可靠的通信鏈路上試圖通過通信以達(dá)成一致是基本不可能或者十分困難的。
拜占庭將軍問題最早是由 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）。
首先我們先來思考一個(gè)問題，為什么 pbft 算法的最大容錯(cuò)節(jié)點(diǎn)數(shù)量是（n-1）/3，而 raft 算法的最大容錯(cuò)節(jié)點(diǎn)數(shù)量是（n-1）/2 ？
對(duì)于raft算法，raft算法的的容錯(cuò)只支持容錯(cuò)故障節(jié)點(diǎn)，不支持容錯(cuò)作惡節(jié)點(diǎn)。什么是故障節(jié)點(diǎn)呢？就是節(jié)點(diǎn)因?yàn)橄到y(tǒng)繁忙、宕機(jī)或者網(wǎng)絡(luò)問題等其它異常情況導(dǎo)致的無(wú)響應(yīng)，出現(xiàn)這種情況的節(jié)點(diǎn)就是故障節(jié)點(diǎn)。那什么是作惡節(jié)點(diǎn)呢？作惡節(jié)點(diǎn)除了可以故意對(duì)集群的其它節(jié)點(diǎn)的請(qǐng)求無(wú)響應(yīng)之外，還可以故意發(fā)送錯(cuò)誤的數(shù)據(jù)，或者給不同的其它節(jié)點(diǎn)發(fā)送不同的數(shù)據(jù)，使整個(gè)集群的節(jié)點(diǎn)最終無(wú)法達(dá)成共識(shí)，這種節(jié)點(diǎn)就是作惡節(jié)點(diǎn)。
raft 算法只支持容錯(cuò)故障節(jié)點(diǎn)，假設(shè)集群總節(jié)點(diǎn)數(shù)為n，故障節(jié)點(diǎn)為 f ，根據(jù)小數(shù)服從多數(shù)的原則，集群里正常節(jié)點(diǎn)只需要比 f 個(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í)。因此 raft 算法支持的最大容錯(cuò)節(jié)點(diǎn)數(shù)量是（n-1）/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í)。也就是說這種情況支持的最大容錯(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ù)量加起來就是 f+1 個(gè)正確節(jié)點(diǎn)，f個(gè)故障節(jié)點(diǎn)和f個(gè)問題節(jié)點(diǎn)，即 3f+1=n。
結(jié)合上述兩種情況，因此 pbft 算法支持的最大容錯(cuò)節(jié)點(diǎn)數(shù)量是（n-1）/3
pbft 算法的基本流程主要有以下四步：
客戶端發(fā)送請(qǐng)求給主節(jié)點(diǎn)
主節(jié)點(diǎn)廣播請(qǐng)求給其它節(jié)點(diǎn)，節(jié)點(diǎn)執(zhí)行 pbft 算法的三階段共識(shí)流程。
節(jié)點(diǎn)處理完三階段流程后，返回消息給客戶端。
客戶端收到來自 f+1 個(gè)節(jié)點(diǎn)的相同消息后，代表共識(shí)已經(jīng)正確完成。
為什么收到 f+1 個(gè)節(jié)點(diǎn)的相同消息后就代表共識(shí)已經(jīng)正確完成？從上一小節(jié)的推導(dǎo)里可知，無(wú)論是最好的情況還是最壞的情況，如果客戶端收到 f+1 個(gè)節(jié)點(diǎn)的相同消息，那么就代表有足夠多的正確節(jié)點(diǎn)已全部達(dá)成共識(shí)并處理完畢了。
3.算法核心三階段流程
算法的核心三個(gè)階段分別是 pre-prepare 階段（預(yù)準(zhǔn)備階段），prepare 階段（準(zhǔn)備階段）， commit 階段（提交階段）
流程的對(duì)比上，對(duì)于 leader 選舉這塊， raft 算法本質(zhì)是誰(shuí)快誰(shuí)當(dāng)選，而 pbft 算法是按編號(hào)依次輪流做主節(jié)點(diǎn)。對(duì)于共識(shí)過程和重選 leader 機(jī)制這塊，為了更形象的描述這兩個(gè)算法，接下來會(huì)把 raft 和 pbft 的共識(shí)過程比喻成一個(gè)團(tuán)隊(duì)是如何執(zhí)行命令的過程，從這個(gè)角度去理解 raft 算法和 pbft 的區(qū)別。
一個(gè)團(tuán)隊(duì)一定會(huì)有一個(gè)老大和普通成員。對(duì)于 raft 算法，共識(shí)過程就是：只要老大還沒掛，老大說什么，我們（團(tuán)隊(duì)普通成員）就做什么，堅(jiān)決執(zhí)行。那什么時(shí)候重新老大呢？只有當(dāng)老大掛了才重選老大，不然生是老大的人，死是老大的鬼。
對(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ì)重新選擇老大。
四、結(jié)語(yǔ)
raft 算法和 pbft 算法是私鏈和聯(lián)盟鏈中經(jīng)典的共識(shí)算法，本文主要介紹了 raft 和 pbft 算法的流程和區(qū)別。 raft 和 pbft 算法有兩點(diǎn)根本區(qū)別：
raft 算法從節(jié)點(diǎn)不會(huì)拒絕主節(jié)點(diǎn)的請(qǐng)求，而 pbft 算法從節(jié)點(diǎn)在某些情況下會(huì)拒絕主節(jié)點(diǎn)的請(qǐng)求 ;
raft 算法只能容錯(cuò)故障節(jié)點(diǎn)，并且最大容錯(cuò)節(jié)點(diǎn)數(shù)為 （n-1）/2 ，而 pbft 算法能容錯(cuò)故障節(jié)點(diǎn)和作惡節(jié)點(diǎn)，最大容錯(cuò)節(jié)點(diǎn)數(shù)為 （n-1）/3 。
pbft算法是通過投票來達(dá)成共識(shí)，可以很好的解決包括分叉等問題的同時(shí)提升效率。但僅僅比較適合于聯(lián)盟鏈私有鏈，因?yàn)閮蓛晒?jié)點(diǎn)之間通信量是O(n^2)（通過優(yōu)化可以減少通信量），一般來說不能應(yīng)用于超過100個(gè)節(jié)點(diǎn)。
pbft有解的前提是 信道必須是可靠的 ，存在的問題是 可擴(kuò)展性（scalability）差
部分來自：
區(qū)塊鏈在設(shè)計(jì)上就是為了BFT
PBFT是實(shí)用拜占庭容錯(cuò)的簡(jiǎn)稱，是解決拜占庭將軍問題的一種方案。比起最開始的BFT算法，PBFT額外要求網(wǎng)絡(luò)封閉，即節(jié)點(diǎn)數(shù)目確定并提前互通，但將復(fù)雜度從指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使得BFT系列算法真正具有可行性。
與POW、POS等大家耳熟能詳?shù)墓沧R(shí)不同，BFT系列的共識(shí)不需要“Proof”，亦即不需要節(jié)點(diǎn)投入算力或其他資源來確權(quán)，因此不需要代幣激勵(lì)便可完成共識(shí)。缺點(diǎn)是原始的BFT效率太低，只能存在于理論而無(wú)法應(yīng)用。而改進(jìn)的PBFT雖然效率大大提高，卻對(duì)節(jié)點(diǎn)數(shù)量和狀態(tài)提出了要求，導(dǎo)致合格的記帳節(jié)點(diǎn)太少，并且也只能維持在少數(shù)，過多的節(jié)點(diǎn)會(huì)拖慢網(wǎng)絡(luò)速度。因此PBFT更多是用在聯(lián)盟鏈和私鏈上。公鏈也有應(yīng)用，例如NEO，便是采用了PBFT算法。
拜占庭將軍問題的實(shí)質(zhì)是在惡劣的通訊環(huán)境中，如何使各參與方達(dá)成一致意見。POW和POS等共識(shí)要求參與方投入成本，爭(zhēng)奪唯一的發(fā)言權(quán)。在某一段時(shí)間內(nèi)只有唯一的發(fā)言人，自然只會(huì)有一個(gè)意見，從而達(dá)成共識(shí)。PBFT采取不同的思路，要求各參與方相互發(fā)送及驗(yàn)證彼此的信息，最終采用多數(shù)原則達(dá)成共識(shí)。
PBFT能夠以一種低成本的方式實(shí)現(xiàn)節(jié)點(diǎn)間共識(shí)，其理念其實(shí)相當(dāng)貼近我們的生活習(xí)慣。例如在老師布置作業(yè)后，同學(xué)們總要互相問問確認(rèn)一下，才放心地把今天的作業(yè)記到本子上。當(dāng)然實(shí)現(xiàn)上還有很多細(xì)節(jié)，保證各節(jié)點(diǎn)的平等關(guān)系。在節(jié)點(diǎn)數(shù)目不多的時(shí)候，節(jié)點(diǎn)之間實(shí)現(xiàn)相互通信的成本并不高，節(jié)點(diǎn)之間可以快速發(fā)送確認(rèn)。但節(jié)點(diǎn)數(shù)目增長(zhǎng)卻會(huì)帶來整體性能的下降。PBFT可以容忍的壞節(jié)點(diǎn)數(shù)量不多于總數(shù)的三分之一，如果節(jié)點(diǎn)損壞率比較固定，提高總節(jié)點(diǎn)數(shù)量雖然能使系統(tǒng)獲得更好的冗余，卻會(huì)大大增加通訊量，造成效率下降。加上PBFT沒有激勵(lì)機(jī)制，其適合聯(lián)盟鏈和私鏈場(chǎng)景。作為公鏈不可避免地節(jié)點(diǎn)數(shù)量太少，分布過分集中，例如NEO只有七個(gè)節(jié)點(diǎn)。
PBFT要求壞節(jié)點(diǎn)數(shù)量f=(n-1)/3，這里n是總節(jié)點(diǎn)數(shù)。只要f滿足這個(gè)條件，共識(shí)總是可以達(dá)成。為什么f要滿足這個(gè)條件？簡(jiǎn)單來說，假設(shè)網(wǎng)絡(luò)中存在惡意節(jié)點(diǎn)聯(lián)盟，其控制了數(shù)量為f的節(jié)點(diǎn)，這些節(jié)點(diǎn)可以故意發(fā)布錯(cuò)誤的信息。此時(shí)網(wǎng)絡(luò)中正常節(jié)點(diǎn)數(shù)量為n-f個(gè)。將這n-f個(gè)節(jié)點(diǎn)分為兩部分，各自包含一部分節(jié)點(diǎn)。對(duì)于任一部分正常節(jié)點(diǎn)來說，只要惡意節(jié)點(diǎn)數(shù)f大于自身節(jié)點(diǎn)數(shù)，同時(shí)大于剩余的正常節(jié)點(diǎn)數(shù)，這部分正常節(jié)點(diǎn)便會(huì)與惡意節(jié)點(diǎn)聯(lián)盟達(dá)成共識(shí)。此時(shí)只要惡意節(jié)點(diǎn)聯(lián)盟先后向兩部分正常節(jié)點(diǎn)發(fā)送不同的共識(shí)信息，便可造成網(wǎng)絡(luò)分叉。因此要保證網(wǎng)絡(luò)運(yùn)行，對(duì)于每一部分正常節(jié)點(diǎn)來說，網(wǎng)絡(luò)中惡意節(jié)點(diǎn)數(shù)量不能同時(shí)大于自身節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)剩余正常節(jié)點(diǎn)數(shù)。代入計(jì)算便得到f=(n-1)/3。
?拜占庭帝國(guó)即東羅馬帝國(guó)，擁有巨大的財(cái)富，并對(duì)鄰邦垂誕已久，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊?；谝恍┰?，這10支軍隊(duì)不能集合在一起單點(diǎn)突破，必須在分開的包圍狀態(tài)下同時(shí)攻擊。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無(wú)勝算，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國(guó)。他們分散在敵國(guó)的四周，依靠通信兵相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下，拜占庭將軍們能否找到一種分布式的協(xié)議來讓他們能夠遠(yuǎn)程協(xié)商，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問題【在分布式系統(tǒng)中指的是消息不僅可以被丟失、延遲、重放，還可以被偽造】。
? ? PBFT(Practical Byzantine Fault Tolerance)算法由Miguel Castro 和Barbara Liskov在1999年提出來的，解決了原始拜占庭容錯(cuò)算法效率不高的問題，將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行。
? ? PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，一般包括三種協(xié)議:一致性協(xié)議(agreement)、檢查點(diǎn)協(xié)議(checkpoint)和視圖更換協(xié)議(view change)。該算法要滿足以下兩個(gè)性質(zhì)：? ?
? ? 安全性(safety)：safety means nothing bad happens.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 活性(liveness)：liveness means that something good eventually happens.
? ? 在一個(gè)拜占庭系統(tǒng)里面，要容忍f個(gè)拜占庭節(jié)點(diǎn)錯(cuò)誤，則replica數(shù)量至少為3f+1，這是滿足安全性的前提。因?yàn)榫W(wǎng)絡(luò)延遲或宕機(jī)，系統(tǒng)存在f個(gè)節(jié)點(diǎn)不回復(fù)響應(yīng)（f個(gè)節(jié)點(diǎn)包括拜占庭節(jié)點(diǎn)和非拜占庭節(jié)點(diǎn)，最壞情況f個(gè)節(jié)點(diǎn)全是非拜占庭節(jié)點(diǎn)），剩下2f+1個(gè)響應(yīng)中可能有f個(gè)拜占庭節(jié)點(diǎn)，從而得到n-2ff，即響應(yīng)中非拜占庭節(jié)點(diǎn)數(shù)目大于拜占庭節(jié)點(diǎn)數(shù)目（f+1f）。
? ? 算法不依賴同步提供安全性，則必須依賴同步提供活性，否則違背FLP定理(在異步通信場(chǎng)景，即使只有一個(gè)進(jìn)程失敗了，沒有任何算法能保證非失敗進(jìn)程能夠達(dá)到一致性)。在拜占庭節(jié)點(diǎn)不超過f，并且delay(t)有界的情況下就能保證系統(tǒng)活性，delay(t)表示從消息發(fā)送到接受的時(shí)間間隔。
? ? 在一個(gè)view里面，會(huì)從replicas中選擇一個(gè)primary，其余的replicas則叫backups。如果主節(jié)點(diǎn)行為發(fā)生異常，則進(jìn)行view change換主。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ?游戲從client向primary發(fā)送請(qǐng)求 開始。 狀態(tài)機(jī)操作， 時(shí)戳。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?游戲從client至少收到f+1個(gè)replicas的響應(yīng) 結(jié)束。 視圖編號(hào)， 時(shí)戳， 客戶端身份， replica編號(hào)， 請(qǐng)求結(jié)果?！緒hy f+1？因?yàn)樵?f+1個(gè)committed中有f個(gè)拜占庭節(jié)點(diǎn)表面上同意請(qǐng)求，實(shí)際上根本不會(huì)回復(fù)請(qǐng)求】
3.1 重彩大戲------三階段協(xié)議
Pre-prepare:
? ? Primary為客戶端請(qǐng)求分配一個(gè)序列號(hào)n，向所有backups發(fā)現(xiàn)預(yù)準(zhǔn)備消息 。 視圖編號(hào)， 消息 的摘要。
Prepare:
? ? 若滿足以下條件，backups接受預(yù)準(zhǔn)備消息：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.客戶端請(qǐng)求和預(yù)準(zhǔn)備消息具有正確簽名。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.當(dāng)前視圖編號(hào)是v。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3.backups從未在當(dāng)前視圖v接收過序列號(hào)為n但摘要不同的預(yù)準(zhǔn)備請(qǐng)求。? ? ? ? ? ? ? ? ? ? ? ? ? 4.hnH。【防止一個(gè)拜占庭節(jié)點(diǎn)選擇一個(gè)大的序號(hào)來消耗序號(hào)空間】
? ? 如果上述條件滿足，backups接收預(yù)準(zhǔn)備消息，進(jìn)入prepare階段，向其他節(jié)點(diǎn)廣播準(zhǔn)備消息 ，并將預(yù)準(zhǔn)備和準(zhǔn)備消息寫入日志。
commit:
? ?如果backups收到2f【包括自己】個(gè)與預(yù)準(zhǔn)備消息一致的準(zhǔn)備消息，請(qǐng)求消息和預(yù)準(zhǔn)備消息具有相同的視圖v和序列號(hào)n，并且已將相關(guān)消息寫入日志，則進(jìn)入commit階段，向其他節(jié)點(diǎn)廣播一條確認(rèn)消息 。如果各節(jié)點(diǎn)收到2f+1條相同的commits消息，則向客戶端發(fā)送一條reply消息。
3.2 垃圾回收
? PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，replicas會(huì)將執(zhí)行過消息記錄在本地日志中，為了節(jié)省內(nèi)存，需要一種機(jī)制來清理日志。何時(shí)來清理？在每次操作完后執(zhí)行是不明智的，因?yàn)楸容^耗資源?？梢远ㄆ谇謇?，比如每100次清理一次。我們將請(qǐng)求后執(zhí)行的狀態(tài)稱為檢查點(diǎn)checkpoint；帶證明的檢查點(diǎn)稱為stable certificate，當(dāng)節(jié)點(diǎn)收到2f+1個(gè)checkpoint消息時(shí)，可證明穩(wěn)定檢查點(diǎn)是正確的。穩(wěn)定檢查點(diǎn)之前的日志消息均可刪除。? ? ? ? ? ? ? ? ? ? ? ?
? 當(dāng)清理檢查點(diǎn)時(shí)replica i向其他replicas廣播一條檢查點(diǎn)協(xié)議 ， 是最近一次正確執(zhí)行請(qǐng)求序號(hào)， 是其當(dāng)前狀態(tài)摘要。如果每一個(gè)replica收到2f+1個(gè)具有相同序號(hào) 和摘要 的檢查點(diǎn)消息，這時(shí)每一個(gè)replica可以清理序列號(hào) 小于等于n的日志信息。
? ?檢查點(diǎn)協(xié)議也用來更新水平線。低水平線 等于最近穩(wěn)定檢查點(diǎn)的序號(hào)，高水平線 ， 為日志大小。
3.3 視圖更改
? ? 當(dāng)主節(jié)點(diǎn)掛掉，或者在commit階段有些節(jié)點(diǎn)收到2f+1個(gè)commit，有些沒有收到2f+1個(gè)commit，導(dǎo)致狀態(tài)不一致，這些狀況都需要更改視圖來提供系統(tǒng)活性和安全性。
? ? 當(dāng)請(qǐng)求超時(shí)，備份節(jié)點(diǎn)進(jìn)入視圖v+1，廣播視圖更改消息 。 穩(wěn)定檢查點(diǎn)序列號(hào)， 是穩(wěn)定檢查點(diǎn)證明， 是一個(gè)集合，包含對(duì)請(qǐng)求 （請(qǐng)求的序列號(hào)大于 ）相關(guān)消息集合 。 包含2f+1個(gè)相同的準(zhǔn)備消息。
? ? ?當(dāng)視圖v+1的主節(jié)點(diǎn)收到2f個(gè)相同個(gè)視圖更改消息，向其他副本廣播新視圖消息 ， 是2f+1個(gè)視圖更改消息， 的計(jì)算規(guī)則如下：? ? ? ? 1.確定序列號(hào) 和 。其中 等于 中穩(wěn)定檢查點(diǎn)序列號(hào), 等于 中最大prepare消息序列號(hào)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.主節(jié)點(diǎn)為 和 之間的每一個(gè)序列號(hào)n分配pre-prepare消息。如果 中包含n對(duì)應(yīng)的 組合，則對(duì)應(yīng)的預(yù)準(zhǔn)備消息為 （也就是說序列號(hào)n對(duì)應(yīng)的請(qǐng)求有2f+1個(gè)prepare消息，在新視圖中依然提交這個(gè)請(qǐng)求）。如果 中不包含n對(duì)應(yīng)的 組合，則提交null消息為 ，即不做任何處理。
? ? 副本收到新視圖消息后，廣播一次prepare消息，進(jìn)入v+1，視圖更換完成。
拜占庭共識(shí)算法有一個(gè)前提：
安全節(jié)點(diǎn)數(shù) R(eliable) 大于不安全節(jié)點(diǎn)數(shù) E(vil)。而且理想情況下R方希望投票結(jié)果是統(tǒng)一的。
所以結(jié)合兩個(gè)不等式
P R/2 +E
P R
得出
R R/2 + E
這就可推測(cè)出
R + R/2 R + E
(3/2) R ALL(總節(jié)點(diǎn)數(shù))
辣么 R ALL(2/3)
所以當(dāng)安全節(jié)點(diǎn)數(shù) R(eliable) 大于總節(jié)點(diǎn)的(2/3)時(shí)，投出來的票才是可靠的
然后，祭出拜占庭投票的流程，以及算法模擬流程
其中D為發(fā)送請(qǐng)求端，R0 R1 R2 R3為服務(wù)端：
最后本來想自己寫個(gè)實(shí)現(xiàn)的，但是Java實(shí)現(xiàn)太重量級(jí)了，貼個(gè)別人用Go語(yǔ)言實(shí)現(xiàn)的吧
重慶分公司
重慶分公司
