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

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

代碼在這里：harmony/consensus。

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

在我們之前的測(cè)試中，我們觀察到由于網(wǎng)絡(luò)狀況不佳而在某些分片中發(fā)生了視圖更改(即領(lǐng)導(dǎo)者更改)。我們還通過(guò)殺死領(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ù)器。它們通過(guò)網(wǎng)絡(luò)發(fā)送消息并根據(jù)它們遵循的協(xié)議執(zhí)行某些任務(wù)來(lái)相互通信。

這個(gè)過(guò)程中會(huì)出現(xiàn)很多類型的錯(cuò)誤的類型，但它們基本上可以分為兩大類。第一種錯(cuò)誤是節(jié)點(diǎn)崩潰、網(wǎng)絡(luò)故障、丟包等，這種錯(cuò)誤類型的節(jié)點(diǎn)是沒(méi)有惡意的，屬于非拜占庭錯(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)將只聽(tīng)取領(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è)閾值。這很容易理解，如果有超過(guò)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è)問(wèn)題。首先，這樣的系統(tǒng)是經(jīng)過(guò)許可的，不允許任意節(jié)點(diǎn)加入和離開。其次，它不能擴(kuò)展到超過(guò)數(shù)百個(gè)節(jié)點(diǎn)。第一個(gè)問(wèn)題源于女巫攻擊(Sybil Attack)，惡意用戶可以輕松創(chuàng)建許多假身份并接管大部分網(wǎng)絡(luò)。不過(guò)，這個(gè)問(wèn)題首先在中本村的比特幣白皮書中被解決了，主要是從經(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è)問(wèn)題可以通過(guò)使用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í)過(guò)程。

請(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í)過(guò)程更簡(jiǎn)單。確切地說(shuō)，PBFT中有一個(gè)被稱為“檢查點(diǎn)過(guò)程”的步驟。檢查點(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)之前，如果還沒(méi)有提交新塊，驗(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)證者通過(guò)向新領(lǐng)導(dǎo)者發(fā)送包含≥2f+ 1個(gè)準(zhǔn)備消息的視圖更改消息來(lái)啟動(dòng)視圖更改。如果它并沒(méi)有收到足夠的準(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ò)的活性。在視圖更改過(guò)程中，我們需要確保提交的區(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í)過(guò)程的計(jì)時(shí)器(具有T0超時(shí))和用于視圖更改過(guò)程的計(jì)時(shí)器(具有k*T1超時(shí)，其中k是在驗(yàn)證器可以切換回正常模式之前發(fā)生了多少視圖更改)。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，節(jié)點(diǎn)將通過(guò)增加一個(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)行多簽名的簽名過(guò)程以在O(1)大小的多簽名中收集驗(yàn)證者的投票，然后廣而播之。因此，和接收O(N)簽名不同，每個(gè)驗(yàn)證器僅接收一個(gè)多簽名，從而將通信復(fù)雜度從O(N²) 減小到O(N)。通過(guò)對(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)在我們可以看到如何通過(guò)聚合公鑰來(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(N²)。這是因?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))。通過(guò)使用BLS簽名方案，我們將2f+1個(gè)簽名聚合成一個(gè)簽名，這樣，準(zhǔn)備和提交階段的消息大小為O(1)，從而將總大小從O(N²)減少到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í)過(guò)程如何與狀態(tài)同步進(jìn)行交互。

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

驗(yàn)證程序啟動(dòng)視圖更改過(guò)程有兩個(gè)原因。一個(gè)原因是當(dāng)驗(yàn)證器檢測(cè)到領(lǐng)導(dǎo)者在一個(gè)視圖中提出兩個(gè)不同的宣布消息時(shí)，它將立即開始視圖更改。另一個(gè)原因是驗(yàn)證者在超時(shí)后沒(méi)有任何進(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)。

視圖更改模式

視圖更改過(guò)程如下：

1. 當(dāng)共識(shí)定時(shí)器超時(shí)，節(jié)點(diǎn)通過(guò)向新的領(lǐng)導(dǎo)者發(fā)送包括視圖ID(viewID)和準(zhǔn)備好(prepared message)的消息(包含≥2f+1個(gè)聚合簽名)的視圖更改消息來(lái)開始視圖更改。如果它沒(mé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)同步才能趕上。

基本過(guò)程很簡(jiǎn)單。節(jié)點(diǎn)通過(guò)將其當(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í)的過(guò)程，因?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)過(guò)時(shí)。在這種情況下，新節(jié)點(diǎn)在收到提交的消息時(shí)通過(guò)更新領(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)。(Chao Ma)

關(guān)鍵詞： 拜占庭容錯(cuò)協(xié)議 分布式系統(tǒng)