拜占庭容錯(cuò)的基本概念及實(shí)現(xiàn)方法解析

在過去的一個(gè)月里，我們一直致力于我們的視圖更改協(xié)議。這是任何區(qū)塊鏈的核心部分，我們可以從中判斷協(xié)議是經(jīng)過許可的還是無(wú)許可的，以及它是如何實(shí)現(xiàn)去中心化。

代碼在這里：harmony/consensus。

我們?cè)?月28日在4個(gè)分片上推出了Day ONE主網(wǎng)，共有600個(gè)節(jié)點(diǎn)。在過去的830，000個(gè)區(qū)塊中，它一直運(yùn)行順暢。

在我們之前的測(cè)試中，我們觀察到由于網(wǎng)絡(luò)狀況不佳而在某些分片中發(fā)生了視圖更改（即領(lǐng)導(dǎo)者更改）。我們還通過殺死領(lǐng)導(dǎo)者節(jié)點(diǎn)以及其他類型的攻擊來(lái)手動(dòng)觸發(fā)視圖更改。攻擊發(fā)生后視圖發(fā)生了變化，網(wǎng)絡(luò)按預(yù)期繼續(xù)運(yùn)行 - 耶！！

在下文中，我們將首先解釋拜占庭容錯(cuò)的基本概念，然后我們會(huì)介紹如何做出改進(jìn)使得能夠在實(shí)踐中處理大量節(jié)點(diǎn)，最后介紹一下整體的代碼結(jié)構(gòu)和一些實(shí)現(xiàn)細(xì)節(jié)。

什么是拜占庭容錯(cuò)？

一個(gè)分布式系統(tǒng)是由多個(gè)節(jié)點(diǎn)組成，其中每個(gè)節(jié)點(diǎn)都是獨(dú)立的服務(wù)器。它們通過網(wǎng)絡(luò)發(fā)送消息并根據(jù)它們遵循的協(xié)議執(zhí)行某些任務(wù)來(lái)相互通信。

這個(gè)過程中會(huì)出現(xiàn)很多類型的錯(cuò)誤的類型，但它們基本上可以分為兩大類。第一種錯(cuò)誤是節(jié)點(diǎn)崩潰、網(wǎng)絡(luò)故障、丟包等，這種錯(cuò)誤類型的節(jié)點(diǎn)是沒有惡意的，屬于非拜占庭錯(cuò)誤。

第二種類型是節(jié)點(diǎn)可能是惡意的。它們可以任意行動(dòng)，不遵守協(xié)議規(guī)則。例如，驗(yàn)證器可以延遲或拒絕中繼網(wǎng)絡(luò)中的消息、領(lǐng)導(dǎo)者可以提出無(wú)效塊、或者節(jié)點(diǎn)可以向不同的對(duì)等體發(fā)送不同的消息。在最壞的情況下，惡意節(jié)點(diǎn)可能會(huì)相互協(xié)作。這些被稱為拜占庭錯(cuò)誤。

考慮到這兩種錯(cuò)誤，我們希望系統(tǒng)始終能夠保持兩個(gè)屬性：一致性（consistency）和活性（liveness）。

在區(qū)塊鏈術(shù)語(yǔ)中，一致性意味著誠(chéng)實(shí)的節(jié)點(diǎn)必須為任何給定的塊數(shù)/高度提交相同的塊；活性意味著鏈高度必須保持增長(zhǎng)而不會(huì)停滯。

一個(gè)被許可的網(wǎng)絡(luò)中只會(huì)出現(xiàn)第一類錯(cuò)誤（非拜占庭），這比較容易解決。例如，我們可以選擇一個(gè)性能很強(qiáng)的節(jié)點(diǎn)作為領(lǐng)導(dǎo)者，所有其他節(jié)點(diǎn)將只聽取領(lǐng)導(dǎo)者廣播的內(nèi)容并信任領(lǐng)導(dǎo)者建議的任何塊。在這種情況下，我們只需要注意第一類錯(cuò)誤，特別是當(dāng)錯(cuò)誤發(fā)生在領(lǐng)導(dǎo)者身上時(shí)。

對(duì)于去中心化的網(wǎng)絡(luò)，我們不能信任任何節(jié)點(diǎn)，因?yàn)榈诙N錯(cuò)誤可能發(fā)生在任何節(jié)點(diǎn)中。這樣我們只能基于一個(gè)基本假設(shè)，即惡意節(jié)點(diǎn)無(wú)法偽造其他節(jié)點(diǎn)的簽名。密碼學(xué)理論證明偽造簽名的難度非常高，以至于今天的計(jì)算機(jī)在任何的實(shí)際時(shí)間長(zhǎng)度內(nèi)都無(wú)法破解。當(dāng)量子計(jì)算機(jī)準(zhǔn)備就緒時(shí)，情況可能會(huì)改變。但那時(shí)，我們將使用量子抗性加密算法。

拜占庭容錯(cuò)協(xié)議是一種即使系統(tǒng)中存在惡意節(jié)點(diǎn)也能保證分布式系統(tǒng)的一致性和活性的協(xié)議。所有這些協(xié)議都有一個(gè)基本假設(shè)，即惡意節(jié)點(diǎn)的數(shù)量小于某個(gè)閾值。這很容易理解，如果有超過50％的惡意節(jié)點(diǎn)，那么網(wǎng)絡(luò)完全由惡意節(jié)點(diǎn)控制。

比特幣的工作量證明（PoW）要求不到50％的節(jié)點(diǎn)（在計(jì)算能力意義上）是惡意的。然而，自私挖礦（selfish mining）將基本假設(shè)降低到25％。當(dāng)只有少于在總計(jì)算能力小于25％的節(jié)點(diǎn)（是惡意的，PoW系統(tǒng)才是安全的。

在傳統(tǒng)的分布式系統(tǒng)中有著對(duì)拜占庭容錯(cuò)協(xié)議深入的研究。事實(shí)證明，在Lamport的經(jīng)典論文中，惡意節(jié)點(diǎn)應(yīng)少于網(wǎng)絡(luò)的33％。后來(lái)，著名的實(shí)用拜占庭容錯(cuò)（PBFT）論文讓這種系統(tǒng)變得可實(shí)用化。

但是，依然還有兩個(gè)問題。首先，這樣的系統(tǒng)是經(jīng)過許可的，不允許任意節(jié)點(diǎn)加入和離開。其次，它不能擴(kuò)展到超過數(shù)百個(gè)節(jié)點(diǎn)。第一個(gè)問題源于女巫攻擊（Sybil Attack），惡意用戶可以輕松創(chuàng)建許多假身份并接管大部分網(wǎng)絡(luò)。不過，這個(gè)問題首先在中本村的比特幣白皮書中被解決了，主要是從經(jīng)濟(jì)效應(yīng)的角度考量。在工作量證明（PoW）之后，有許多新的設(shè)計(jì)，例如股權(quán)證明（PoS），權(quán)威證明（PoA）等。我們不計(jì)算節(jié)點(diǎn)的數(shù)量，而是計(jì)算投票權(quán)的數(shù)量。在PoS中，節(jié)點(diǎn)的投票能力與其放樣量（staking）成比例。第二個(gè)問題可以通過使用BLS簽名方案的聚合簽名解決，這在FBFT部分中有解釋。

實(shí)用拜占庭容錯(cuò)

像Raft和Paxos這樣的協(xié)議主要用于處理第一類系統(tǒng)錯(cuò)誤。實(shí)用拜占庭容錯(cuò)算法（PBFT）是現(xiàn)實(shí)世界里首批能夠同時(shí)處理第一類和第二類錯(cuò)誤的拜占庭容錯(cuò)協(xié)議之一。

我們將始終假設(shè)有N個(gè)節(jié)點(diǎn)最多有f個(gè)惡意節(jié)點(diǎn)，其中N = 3f+1。PBFT中有兩種模式，即普通共識(shí)（簡(jiǎn)稱正常）模式和視圖更改模式。正常模式看起來(lái)像這樣（在區(qū)塊鏈中，可以忽略客戶端請(qǐng)求和回復(fù)）：

在一個(gè)視圖中（一個(gè)視圖是類似一輪的概念），有3個(gè)步驟/階段：預(yù)先準(zhǔn)備（或宣布）、準(zhǔn)備和提交。

1. 在預(yù)準(zhǔn)備（宣布）階段，領(lǐng)導(dǎo)者將向其他節(jié)點(diǎn)（稱為驗(yàn)證者）廣播宣布消息（announce message）（例如，包含最新交易的區(qū)塊）。當(dāng)驗(yàn)證者收到宣布消息時(shí)，它進(jìn)入準(zhǔn)備階段。

2. 在準(zhǔn)備階段，在驗(yàn)證者接收到宣布消息之后，它將向每個(gè)節(jié)點(diǎn)廣播準(zhǔn)備消息（例如，在blockhash上的簽名）。當(dāng)驗(yàn)證者（包括領(lǐng)導(dǎo)者）收到足夠的（即≥2f+1）準(zhǔn)備消息時(shí)，它將進(jìn)入提交階段。

3. 在提交階段，驗(yàn)證者（包括領(lǐng)導(dǎo)者）將發(fā)送提交消息（例如在| blockNum | blockHash |上的簽名）當(dāng)驗(yàn)證者收到足夠的（≥2f+ 1）提交消息時(shí)。它可以安全地提交區(qū)塊。這結(jié)束了一輪正常的共識(shí)過程。

請(qǐng)注意，一般PBFT和區(qū)塊鏈PBFT之間存在一些差異。主要區(qū)別在于區(qū)塊鏈在兩個(gè)區(qū)塊之間是“同步的”，即我們不能在提交h（區(qū)塊號(hào)）之前繼續(xù)提交區(qū)塊h+1。在傳統(tǒng)的PBFT中，我們可以在請(qǐng)求h之前提交客戶請(qǐng)求h+1。PBFT將保證所有節(jié)點(diǎn)的一致性。

從這個(gè)意義上說(shuō)，區(qū)塊鏈?zhǔn)构沧R(shí)過程更簡(jiǎn)單。確切地說(shuō)，PBFT中有一個(gè)被稱為“檢查點(diǎn)過程”的步驟。檢查點(diǎn)（checkpoint）是一個(gè)證書，其中序列號(hào)（在區(qū)塊鏈中，即是區(qū)塊號(hào)）小于或等于檢查點(diǎn)的區(qū)塊都被視作已經(jīng)最終確定，不可更改。在區(qū)塊鏈中，每個(gè)已經(jīng)確定的區(qū)塊，都可以被視為檢查點(diǎn)。

當(dāng)驗(yàn)證者在共識(shí)超時(shí)（ΔT≥T0）之前，如果還沒有提交新塊，驗(yàn)證器將開始發(fā)送視圖更改信息（v→v+1），每個(gè)驗(yàn)證者都會(huì)選擇一樣的新的領(lǐng)導(dǎo)者。如果視圖更改無(wú)法在超時(shí)（ΔT≥T1）之前完成，則驗(yàn)證者將建議另一個(gè)新的視圖更改（v+1→v+2，同時(shí)視圖更改超時(shí)間隔增加到2*T1）。

視圖更改模式有兩個(gè)步驟/階段：

1. 驗(yàn)證者通過向新領(lǐng)導(dǎo)者發(fā)送包含≥2f+ 1個(gè)準(zhǔn)備消息的視圖更改消息來(lái)啟動(dòng)視圖更改。如果它并沒有收到足夠的準(zhǔn)備消息，它只需發(fā)送空的視圖更改消息，給新的領(lǐng)導(dǎo)者。

2. 新領(lǐng)導(dǎo)者收集足夠的（≥2f+ 1）視圖更改消息并廣播接收到的所有視圖更改消息（新視圖消息）。然后新領(lǐng)導(dǎo)者切換到正常模式。驗(yàn)證在收到來(lái)自新領(lǐng)導(dǎo)者的新視圖消息時(shí)切換到正常模式，同時(shí)停止視圖更改計(jì)時(shí)器并啟動(dòng)共識(shí)計(jì)時(shí)器。如果驗(yàn)證程序在視圖更改超時(shí)之前未收到新的視圖消息，則會(huì)將viewID增加1并開始另一個(gè)新的視圖更改。

視圖更改可以確保網(wǎng)絡(luò)的活性。在視圖更改過程中，我們需要確保提交的區(qū)塊在整個(gè)視圖更改中也是一致的。簡(jiǎn)單來(lái)說(shuō)，接收2f+1準(zhǔn)備消息（prepare message）只能確保同一視圖中的一致性。接收2f+1個(gè)提交消息（commit message）可確保不同視圖之間的一致性。當(dāng)節(jié)點(diǎn)收到2f+1提交消息時(shí)，它可以安全地將塊提交到區(qū)塊鏈中。PBFT協(xié)議確保即使在視圖更改的情況下，任何誠(chéng)實(shí)節(jié)點(diǎn)都提交相同的區(qū)塊。

一致性和活性

PBFT的一個(gè)關(guān)鍵概念是法定人數(shù)。法定人數(shù)是具有至少2f+1個(gè)節(jié)點(diǎn)的任何子集。由于總共有3f+1個(gè)節(jié)點(diǎn)，因此任何兩個(gè)法定人數(shù)將至少有f+1個(gè)節(jié)點(diǎn)相交。因?yàn)樽疃嘤衒個(gè)惡意節(jié)點(diǎn)，故在兩個(gè)法定人數(shù)的交集中將至少包含一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)。這就是我們需要法定人數(shù)來(lái)采取任何行動(dòng)的原因。

一個(gè)視圖中的一致性指的是：假設(shè)一個(gè)節(jié)點(diǎn)收到2f+1準(zhǔn)備消息，這些2f+1個(gè)節(jié)點(diǎn)將形成一個(gè)法定人數(shù)。請(qǐng)注意，任何兩個(gè)法定人數(shù)中將至少有一個(gè)共同的誠(chéng)實(shí)節(jié)點(diǎn)，這意味著任何兩個(gè)這樣的法定人數(shù)在其準(zhǔn)備消息中不能包含不同的區(qū)塊哈希，否則共同的誠(chéng)實(shí)節(jié)點(diǎn)允許兩個(gè)相同高度的不同區(qū)塊，這與它誠(chéng)實(shí)的事實(shí)相矛盾。

不同視圖的一致性指的是：假設(shè)一個(gè)節(jié)點(diǎn)收到2f+1提交消息，這些2f+1個(gè)節(jié)點(diǎn)形成一個(gè)法定人數(shù)，將其表示為Q1。當(dāng)一個(gè)誠(chéng)實(shí)的節(jié)點(diǎn)開始視圖更改時(shí)，它會(huì)將準(zhǔn)備好的消息（包含2f+1準(zhǔn)備消息）發(fā)送給新的領(lǐng)導(dǎo)者。新領(lǐng)導(dǎo)者需要收集2f+1個(gè)視圖更改消息（表示為法定人數(shù)Q2）才能發(fā)送新的試圖消息。Q1和Q2再次包含至少一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)。此節(jié)點(diǎn)包含2f + 1個(gè)準(zhǔn)備消息，因?yàn)樗诎l(fā)送其提交消息之前必須先收到了足夠的準(zhǔn)備消息。這確保了不同視圖中的誠(chéng)實(shí)節(jié)點(diǎn)將提交相同的區(qū)塊。

活性 ：每個(gè)節(jié)點(diǎn)都有一個(gè)用于正常共識(shí)過程的計(jì)時(shí)器（具有T0超時(shí)）和用于視圖更改過程的計(jì)時(shí)器（具有k*T1超時(shí)，其中k是在驗(yàn)證器可以切換回正常模式之前發(fā)生了多少視圖更改）。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，節(jié)點(diǎn)將通過增加一個(gè)視圖來(lái)啟動(dòng)視圖更改。在連續(xù)的領(lǐng)導(dǎo)者未能發(fā)送正確的新視圖消息的情況下，視圖更改計(jì)時(shí)器的超時(shí)時(shí)段將增加，以避免頻繁的視圖更改并確保最終足夠的誠(chéng)實(shí)節(jié)點(diǎn)將與誠(chéng)實(shí)的新領(lǐng)導(dǎo)者具有相同的viewID。

快速拜占庭容錯(cuò)

作為對(duì)PBFT的改進(jìn)，Harmony的共識(shí)協(xié)議在通信復(fù)雜性方面是線性可擴(kuò)展的，因此我們將其稱為快速拜占庭容錯(cuò)（FBFT）。在FBFT中，領(lǐng)導(dǎo)者不是要求所有驗(yàn)證者廣播他們的投票，而是運(yùn)行多簽名的簽名過程以在O（1）大小的多簽名中收集驗(yàn)證者的投票，然后廣而播之。因此，和接收O（N）簽名不同，每個(gè)驗(yàn)證器僅接收一個(gè)多簽名，從而將通信復(fù)雜度從O（N2） 減小到O（N）。通過對(duì)視圖更改消息的一些修改，視圖改變復(fù)雜度也可以減少到O（N）。

BLS簽名方案

在這里，我們對(duì)Boneh-Lynn-Shacham（BLS）簽名方案進(jìn)行了非常簡(jiǎn)短的數(shù)學(xué)介紹，這是FBFT和PBFT之間的主要區(qū)別。BLS簽名方案基于橢圓曲線配對(duì)。令E（Fp）為有限域Fp上的橢圓曲線，其中p為大質(zhì)數(shù)。我們?cè)诖饲€上選擇一個(gè)基本參考點(diǎn)g。私有BLS密鑰是從Fp采樣的隨機(jī)數(shù)α，公鑰是α?g，是橢圓曲線E上的一個(gè)點(diǎn)。給定一個(gè)消息m，簽名計(jì)算為σ=α?H（m），這也是E上一個(gè)點(diǎn)，其中H是哈希到E的函數(shù)。在兩條橢圓曲線E1和E2上的雙線性映射e滿足一下情況：

e（α?g1，g2）=e（g1，α?g2），g1∈E1，g2∈E2

e（g0+g1，g2）=e（g0，g2）+e（g1，g2），g0，g1∈E1，g2∈E2

e（g1，g2+g3）=e（g1，g2）+e（g1，g3），g1∈E1，g2，g3∈E2

現(xiàn)在我們可以看到如何通過聚合公鑰來(lái)驗(yàn)證k個(gè)簽名。

e（g1，σ1+?+σk）=e（g1，α1?H（m）+?+αk?H（m））

=e（α1?g1+?+αk?g1，H（m））

請(qǐng)注意，聚合簽名就是一個(gè)普通簽名，也就是橢圓曲線上的一個(gè)點(diǎn)，聚合公鑰就是一個(gè)普通公鑰，也是橢圓曲線上的一個(gè)點(diǎn)。這將2f + 1簽名簡(jiǎn)化為僅1個(gè)聚合簽名，這對(duì)于減少共識(shí)協(xié)議中的網(wǎng)絡(luò)流量至關(guān)重要。

正常模式

在傳統(tǒng)的PBFT中，節(jié)點(diǎn)在每輪共識(shí)中發(fā)送或接收的總消息大小是O（N2）。這是因?yàn)樵跍?zhǔn)備和提交階段，每個(gè)節(jié)點(diǎn)需要收集2f+1=O（N）個(gè)簽名并將它們廣播到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)（即O（N）個(gè)節(jié)點(diǎn)）。通過使用BLS簽名方案，我們將2f+1個(gè)簽名聚合成一個(gè)簽名，這樣，準(zhǔn)備和提交階段的消息大小為O（1），從而將總大小從O（N2）減少到O（1）回合。為了從BLS方案中受益，每個(gè)驗(yàn)證器將僅向領(lǐng)導(dǎo)者發(fā)送準(zhǔn)備和提交消息，并且領(lǐng)導(dǎo)者負(fù)責(zé)收集足夠的》=2f+1個(gè)簽名并將它們聚合成一個(gè)聚合簽名，之后領(lǐng)導(dǎo)者分別在準(zhǔn)備/提交階段發(fā)送準(zhǔn)備好/已提交的消息。從領(lǐng)導(dǎo)者的角度來(lái)看，這三個(gè)階段是同步的，但從驗(yàn)證者的角度來(lái)看，他們?nèi)匀豢梢圆话错樞蚪邮障?，例如：?yàn)證者可以在宣布消息之前接收準(zhǔn)備好的消息，但是在這種情況下，其準(zhǔn)備簽名將不會(huì)在準(zhǔn)備好的消息中包含。

正常模式分為三個(gè)階段：

1. 在宣布階段，領(lǐng)導(dǎo)者將向驗(yàn)證者廣播宣布消息（例如提議塊）。當(dāng)驗(yàn)證器收到宣布消息時(shí)，它進(jìn)入準(zhǔn)備階段

2. 在準(zhǔn)備階段，驗(yàn)證器向領(lǐng)導(dǎo)者發(fā)送準(zhǔn)備消息（例如，在blockhash上簽名）。當(dāng)領(lǐng)導(dǎo)者收到足夠多的（即≥2f+1）準(zhǔn)備消息時(shí)，它會(huì)聚合從驗(yàn)證者收到的準(zhǔn)備消息上的簽名，并發(fā)出準(zhǔn)備好的消息，其中包含聚合的準(zhǔn)備簽名。然后領(lǐng)導(dǎo)者進(jìn)入提交階段。驗(yàn)證器在收到來(lái)自領(lǐng)導(dǎo)者的準(zhǔn)備好的消息時(shí)進(jìn)入提交階段。

3. 在提交階段，驗(yàn)證器向leader發(fā)送提交消息（例如|blockNum|blockHash|上的簽名）。當(dāng)領(lǐng)導(dǎo)者收到足夠的（即≥2f+ 1）提交消息時(shí)，它會(huì)聚合從驗(yàn)證器接收的提交消息的簽名，并發(fā)出提交消息，其中包含聚合的提交簽名。然后領(lǐng)導(dǎo)者完成一個(gè)視圖/回合。驗(yàn)證器在收到已提交的消息后完成一個(gè)視圖/回合。當(dāng)領(lǐng)導(dǎo)者或驗(yàn)證者完成一輪時(shí)，它將重新啟動(dòng)共識(shí)計(jì)時(shí)器。

在步驟3，也就是提交階段，驗(yàn)證者在blockNum和blockHash上發(fā)送帶有簽名的提交消息。這可用于新加入網(wǎng)絡(luò)的節(jié)點(diǎn)確認(rèn)它是否和當(dāng)前網(wǎng)絡(luò)同步，同時(shí)不至于被惡意領(lǐng)導(dǎo)者欺騙。在狀態(tài)同步模式部分中解釋了共識(shí)過程如何與狀態(tài)同步進(jìn)行交互。

領(lǐng)導(dǎo)者選舉

驗(yàn)證程序啟動(dòng)視圖更改過程有兩個(gè)原因。一個(gè)原因是當(dāng)驗(yàn)證器檢測(cè)到領(lǐng)導(dǎo)者在一個(gè)視圖中提出兩個(gè)不同的宣布消息時(shí)，它將立即開始視圖更改。另一個(gè)原因是驗(yàn)證者在超時(shí)后沒有任何進(jìn)展。有兩種超時(shí)：正常共識(shí)模式下的超時(shí)和視圖更改模式下的超時(shí)。

在我們的區(qū)塊鏈中，我們有了epoch的概念。每個(gè)epoch包含X個(gè)塊（例如X = 1000）。在每個(gè)epoch的開始階段，委員會(huì)成員都是由在信標(biāo)鏈中為這個(gè)epoch下注的人決定的。委員會(huì)成員的順序由該時(shí)期的VDF隨機(jī)性唯一確定。在一個(gè)epoch中，委員會(huì)將始終保持不變。假設(shè)順序列表是［v0，…，vn］，然后在epoch一開始，領(lǐng)導(dǎo)者是v0。如果發(fā)生視圖更改，則下一個(gè)領(lǐng)導(dǎo)者是v1，依此類推。在這里，我們假設(shè)每個(gè)驗(yàn)證者具有相同的投票權(quán)。

視圖更改模式

視圖更改過程如下：

1. 當(dāng)共識(shí)定時(shí)器超時(shí)，節(jié)點(diǎn)通過向新的領(lǐng)導(dǎo)者發(fā)送包括視圖ID（viewID）和準(zhǔn)備好（prepared message）的消息（包含≥2f+1個(gè)聚合簽名）的視圖更改消息來(lái)開始視圖更改。如果它沒有收到準(zhǔn)備好的消息，那它就只是發(fā)送空的視圖更改消息，只包括viewID上的簽名但不包括準(zhǔn)備好的消息。

2. 當(dāng)新領(lǐng)導(dǎo)者收到足夠的（≥2f+1）視圖更改消息時(shí)，它會(huì)聚合viewID的簽名，并從視圖更改消息中選擇一個(gè)準(zhǔn)備好的消息。它廣播新的視圖消息，包括聚合簽名以及選擇出的準(zhǔn)備消息。然后新領(lǐng)導(dǎo)者切換到正常共識(shí)模式。驗(yàn)證者在收到來(lái)自新領(lǐng)導(dǎo)者的新視圖消息時(shí)切換到正常共識(shí)節(jié)點(diǎn)，同時(shí)停止視圖更改計(jì)時(shí)器并啟動(dòng)共識(shí)計(jì)時(shí)器。如果驗(yàn)證程序在視圖更改超時(shí)之前未收到新的視圖消息，則會(huì)將viewID增加1并開始另一個(gè)新的視圖更改。

第二步要求每個(gè)驗(yàn)證器在viewID上發(fā)送簽名。目的是用于防備惡意領(lǐng)導(dǎo)者。確切地說(shuō)，前一個(gè)領(lǐng)導(dǎo)者可以在準(zhǔn)備階段向不同的驗(yàn)證者發(fā)送不同的聚合簽名。只要聚合簽名有效，驗(yàn)證器就會(huì)接受它并在發(fā)生視圖更改時(shí)提出它。在這種情況下，每個(gè)視圖更改消息都包含不同的簽名，新領(lǐng)導(dǎo)者不能進(jìn)行簽名聚合，所以新視圖消息的大小為O（N），這是因?yàn)樾碌念I(lǐng)導(dǎo)者必須證明接收到足夠的有效視圖更改消息。如果每個(gè)人都在viewID上簽名，新的領(lǐng)導(dǎo)者很容易聚集簽名，這樣可以將新的試圖消息的大小減少到O（1）。只有這樣，我們才能在視圖更改的情況下擴(kuò)大網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。

狀態(tài)同步模式

我們?cè)试S節(jié)點(diǎn)在區(qū)塊鏈中自由加入和離開。當(dāng)新節(jié)點(diǎn)加入共識(shí)時(shí)，它必須先進(jìn)行狀態(tài)同步，然后才能驗(yàn)證共識(shí)消息。此外，還存在節(jié)點(diǎn)在視圖更改模式下卡住的情況。例如，當(dāng)驗(yàn)證程序網(wǎng)絡(luò)連接速度較慢時(shí)，可能無(wú)法在超時(shí)之前取得任何進(jìn)展。在這種情況下，它將開始視圖更改。但是，它無(wú)法從視圖更改模式中退出，因?yàn)樗衅渌?jié)點(diǎn)都在向前移動(dòng)，視圖更改會(huì)失敗。在這種情況下，此節(jié)點(diǎn)需要執(zhí)行狀態(tài)同步才能趕上。

基本過程很簡(jiǎn)單。節(jié)點(diǎn)通過將其當(dāng)前塊高度和已提交消息中的最新塊高度進(jìn)行比較，如果檢測(cè)出它不同步時(shí)，它將切換到狀態(tài)同步模式并開始執(zhí)行狀態(tài)同步。完成狀態(tài)同步后，它會(huì)切換到正常模式。

為了在狀態(tài)同步完成后加入共識(shí)，節(jié)點(diǎn)需要知道誰(shuí)是當(dāng)前的領(lǐng)導(dǎo)者以及當(dāng)前的viewID是什么。一種解決方案是盲目地接受來(lái)自共識(shí)消息的領(lǐng)導(dǎo)者和viewID。這種方法使惡意領(lǐng)導(dǎo)者有機(jī)會(huì)在共識(shí)消息中發(fā)送很大的viewID，強(qiáng)制使得每個(gè)驗(yàn)證者開始狀態(tài)同步。更好的方法是僅在接收提交消息的時(shí)候接受領(lǐng)導(dǎo)者和viewID信息。在這種情況下，惡意領(lǐng)導(dǎo)者不能欺騙新節(jié)點(diǎn)。但它減緩了新節(jié)點(diǎn)加入共識(shí)的過程，因?yàn)樵诟骂I(lǐng)導(dǎo)者和viewID之前，它無(wú)法驗(yàn)證宣布消息和準(zhǔn)備好的消息。我們選擇的方法是將領(lǐng)導(dǎo)者和viewID信息添加到區(qū)塊頭中。當(dāng)節(jié)點(diǎn)完成狀態(tài)同步時(shí)，它可以從最新的區(qū)塊頭中讀取信息。如果在狀態(tài)同步期間發(fā)生視圖更改，那么來(lái)自最新塊的信息已經(jīng)過時(shí)。在這種情況下，新節(jié)點(diǎn)在收到提交的消息時(shí)通過更新領(lǐng)導(dǎo)者和viewID信息仍然可以得到最新的信息。

狀態(tài)轉(zhuǎn)換

下圖是驗(yàn)證器的狀態(tài)轉(zhuǎn)換圖。 領(lǐng)導(dǎo)者的狀態(tài)轉(zhuǎn)換相對(duì)比較簡(jiǎn)單在此省略。

有5種模式：3種正常模式（A：宣布 ，P：準(zhǔn)備，C：提交），視圖更改模式（VC）和狀態(tài)同步模式（S， Syncing）。

模式之間的轉(zhuǎn)換由不同的條件觸發(fā)，例如接收特定類型的消息或滿足某些條件，如超時(shí)。

條件列表：am（宣布消息announce message），pm（準(zhǔn)備好的消息prepare message），cm（提交消息commit message），tc（嘗試追趕成功 try catchup），to（超時(shí) time out），nv（新視圖消息new view），is（同步in sync），os（不同步out of sync）。