在過去的一個月里，我們一直致力于我們的視圖更改協(xié)議。這是任何區(qū)塊鏈的核心部分，我們可以從中判斷協(xié)議是經(jīng)過許可的還是無許可的，以及它
在過去的一個月里，我們一直致力于我們的視圖更改協(xié)議。這是任何區(qū)塊鏈的核心部分，我們可以從中判斷協(xié)議是經(jīng)過許可的還是無許可的，以及它是如何實現(xiàn)去中心化。
代碼在這里：harmony/consensus。
我們在6月28日在4個分片上推出了Day ONE主網(wǎng)，共有600個節(jié)點。在過去的830,000個區(qū)塊中，它一直運行順暢。
在我們之前的測試中，我們觀察到由于網(wǎng)絡(luò)狀況不佳而在某些分片中發(fā)生了視圖更改(即領(lǐng)導(dǎo)者更改)。我們還通過殺死領(lǐng)導(dǎo)者節(jié)點以及其他類型的攻擊來手動觸發(fā)視圖更改。攻擊發(fā)生后視圖發(fā)生了變化，網(wǎng)絡(luò)按預(yù)期繼續(xù)運行 - 耶!!
在下文中，我們將首先解釋拜占庭容錯的基本概念，然后我們會介紹如何做出改進使得能夠在實踐中處理大量節(jié)點，最后介紹一下整體的代碼結(jié)構(gòu)和一些實現(xiàn)細節(jié)。
什么是拜占庭容錯?
一個分布式系統(tǒng)是由多個節(jié)點組成，其中每個節(jié)點都是獨立的服務(wù)器。它們通過網(wǎng)絡(luò)發(fā)送消息并根據(jù)它們遵循的協(xié)議執(zhí)行某些任務(wù)來相互通信。
這個過程中會出現(xiàn)很多類型的錯誤的類型，但它們基本上可以分為兩大類。第一種錯誤是節(jié)點崩潰、網(wǎng)絡(luò)故障、丟包等，這種錯誤類型的節(jié)點是沒有惡意的，屬于非拜占庭錯誤。
第二種類型是節(jié)點可能是惡意的。它們可以任意行動，不遵守協(xié)議規(guī)則。例如，驗證器可以延遲或拒絕中繼網(wǎng)絡(luò)中的消息、領(lǐng)導(dǎo)者可以提出無效塊、或者節(jié)點可以向不同的對等體發(fā)送不同的消息。在最壞的情況下，惡意節(jié)點可能會相互協(xié)作。這些被稱為拜占庭錯誤。
考慮到這兩種錯誤，我們希望系統(tǒng)始終能夠保持兩個屬性：一致性(consistency)和活性(liveness)。
在區(qū)塊鏈術(shù)語中，一致性意味著誠實的節(jié)點必須為任何給定的塊數(shù)/高度提交相同的塊;活性意味著鏈高度必須保持增長而不會停滯。
一個被許可的網(wǎng)絡(luò)中只會出現(xiàn)第一類錯誤(非拜占庭)，這比較容易解決。例如，我們可以選擇一個性能很強的節(jié)點作為領(lǐng)導(dǎo)者，所有其他節(jié)點將只聽取領(lǐng)導(dǎo)者廣播的內(nèi)容并信任領(lǐng)導(dǎo)者建議的任何塊。在這種情況下，我們只需要注意第一類錯誤，特別是當錯誤發(fā)生在領(lǐng)導(dǎo)者身上時。
對于去中心化的網(wǎng)絡(luò)，我們不能信任任何節(jié)點，因為第二種錯誤可能發(fā)生在任何節(jié)點中。這樣我們只能基于一個基本假設(shè)，即惡意節(jié)點無法偽造其他節(jié)點的簽名。密碼學理論證明偽造簽名的難度非常高，以至于今天的計算機在任何的實際時間長度內(nèi)都無法破解。當量子計算機準備就緒時，情況可能會改變。但那時，我們將使用量子抗性加密算法。
拜占庭容錯協(xié)議是一種即使系統(tǒng)中存在惡意節(jié)點也能保證分布式系統(tǒng)的一致性和活性的協(xié)議。所有這些協(xié)議都有一個基本假設(shè)，即惡意節(jié)點的數(shù)量小于某個閾值。這很容易理解，如果有超過50%的惡意節(jié)點，那么網(wǎng)絡(luò)完全由惡意節(jié)點控制。
比特幣的工作量證明(PoW)要求不到50%的節(jié)點(在計算能力意義上)是惡意的。然而，自私挖礦(selfish mining)將基本假設(shè)降低到25%。當只有少于在總計算能力小于25%的節(jié)點(是惡意的，PoW系統(tǒng)才是安全的。
在傳統(tǒng)的分布式系統(tǒng)中有著對拜占庭容錯協(xié)議深入的研究。事實證明，在Lamport的經(jīng)典論文中，惡意節(jié)點應(yīng)少于網(wǎng)絡(luò)的33%。后來，著名的實用拜占庭容錯(PBFT)論文讓這種系統(tǒng)變得可實用化。
但是，依然還有兩個問題。首先，這樣的系統(tǒng)是經(jīng)過許可的，不允許任意節(jié)點加入和離開。其次，它不能擴展到超過數(shù)百個節(jié)點。第一個問題源于女巫攻擊(Sybil Attack)，惡意用戶可以輕松創(chuàng)建許多假身份并接管大部分網(wǎng)絡(luò)。不過，這個問題首先在中本村的比特幣白皮書中被解決了，主要是從經(jīng)濟效應(yīng)的角度考量。
在工作量證明(PoW)之后，有許多新的設(shè)計，例如股權(quán)證明(PoS)，權(quán)威證明(PoA)等。我們不計算節(jié)點的數(shù)量，而是計算投票權(quán)的數(shù)量。在PoS中，節(jié)點的投票能力與其放樣量(staking)成比例。第二個問題可以通過使用BLS簽名方案的聚合簽名解決，這在FBFT部分中有解釋。
實用拜占庭容錯
像Raft和Paxos這樣的協(xié)議主要用于處理第一類系統(tǒng)錯誤。實用拜占庭容錯算法(PBFT)是現(xiàn)實世界里首批能夠同時處理第一類和第二類錯誤的拜占庭容錯協(xié)議之一。
我們將始終假設(shè)有N個節(jié)點最多有f個惡意節(jié)點，其中N = 3f+1。PBFT中有兩種模式，即普通共識(簡稱正常)模式和視圖更改模式。正常模式看起來像這樣(在區(qū)塊鏈中，可以忽略客戶端請求和回復(fù))：
在一個視圖中(一個視圖是類似一輪的概念)，有3個步驟/階段：預(yù)先準備(或宣布)、準備和提交。
1. 在預(yù)準備(宣布)階段，領(lǐng)導(dǎo)者將向其他節(jié)點(稱為驗證者)廣播宣布消息(announce message)(例如，包含最新交易的區(qū)塊)。當驗證者收到宣布消息時，它進入準備階段。
2. 在準備階段，在驗證者接收到宣布消息之后，它將向每個節(jié)點廣播準備消息(例如，在blockhash上的簽名)。當驗證者(包括領(lǐng)導(dǎo)者)收到足夠的(即≥2f+1)準備消息時，它將進入提交階段。
3. 在提交階段，驗證者(包括領(lǐng)導(dǎo)者)將發(fā)送提交消息(例如在| blockNum | blockHash |上的簽名)當驗證者收到足夠的(≥2f+ 1)提交消息時。它可以安全地提交區(qū)塊。這結(jié)束了一輪正常的共識過程。
請注意，一般PBFT和區(qū)塊鏈PBFT之間存在一些差異。主要區(qū)別在于區(qū)塊鏈在兩個區(qū)塊之間是“同步的”，即我們不能在提交h(區(qū)塊號)之前繼續(xù)提交區(qū)塊h+1。在傳統(tǒng)的PBFT中，我們可以在請求h之前提交客戶請求h+1。PBFT將保證所有節(jié)點的一致性。
從這個意義上說，區(qū)塊鏈使共識過程更簡單。確切地說，PBFT中有一個被稱為“檢查點過程”的步驟。檢查點(checkpoint)是一個證書，其中序列號(在區(qū)塊鏈中，即是區(qū)塊號)小于或等于檢查點的區(qū)塊都被視作已經(jīng)最終確定，不可更改。在區(qū)塊鏈中，每個已經(jīng)確定的區(qū)塊，都可以被視為檢查點。
當驗證者在共識超時(ΔT≥T0)之前，如果還沒有提交新塊，驗證器將開始發(fā)送視圖更改信息(v→v+1)，每個驗證者都會選擇一樣的新的領(lǐng)導(dǎo)者。如果視圖更改無法在超時(ΔT≥T1)之前完成，則驗證者將建議另一個新的視圖更改(v+1→v+2，同時視圖更改超時間隔增加到2*T1)。
視圖更改模式有兩個步驟/階段：
1. 驗證者通過向新領(lǐng)導(dǎo)者發(fā)送包含≥2f+ 1個準備消息的視圖更改消息來啟動視圖更改。如果它并沒有收到足夠的準備消息，它只需發(fā)送空的視圖更改消息，給新的領(lǐng)導(dǎo)者。
2. 新領(lǐng)導(dǎo)者收集足夠的(≥2f+ 1)視圖更改消息并廣播接收到的所有視圖更改消息(新視圖消息)。然后新領(lǐng)導(dǎo)者切換到正常模式。驗證在收到來自新領(lǐng)導(dǎo)者的新視圖消息時切換到正常模式，同時停止視圖更改計時器并啟動共識計時器。如果驗證程序在視圖更改超時之前未收到新的視圖消息，則會將viewID增加1并開始另一個新的視圖更改。
視圖更改可以確保網(wǎng)絡(luò)的活性。在視圖更改過程中，我們需要確保提交的區(qū)塊在整個視圖更改中也是一致的。簡單來說，接收2f+1準備消息(prepare message)只能確保同一視圖中的一致性。接收2f+1個提交消息(commit message)可確保不同視圖之間的一致性。當節(jié)點收到2f+1提交消息時，它可以安全地將塊提交到區(qū)塊鏈中。PBFT協(xié)議確保即使在視圖更改的情況下，任何誠實節(jié)點都提交相同的區(qū)塊。
一致性和活性
PBFT的一個關(guān)鍵概念是法定人數(shù)。法定人數(shù)是具有至少2f+1個節(jié)點的任何子集。由于總共有3f+1個節(jié)點，因此任何兩個法定人數(shù)將至少有f+1個節(jié)點相交。因為最多有f個惡意節(jié)點，故在兩個法定人數(shù)的交集中將至少包含一個誠實節(jié)點。這就是我們需要法定人數(shù)來采取任何行動的原因。
一個視圖中的一致性指的是：假設(shè)一個節(jié)點收到2f+1準備消息，這些2f+1個節(jié)點將形成一個法定人數(shù)。請注意，任何兩個法定人數(shù)中將至少有一個共同的誠實節(jié)點，這意味著任何兩個這樣的法定人數(shù)在其準備消息中不能包含不同的區(qū)塊哈希，否則共同的誠實節(jié)點允許兩個相同高度的不同區(qū)塊，這與它誠實的事實相矛盾。
不同視圖的一致性指的是：假設(shè)一個節(jié)點收到2f+1提交消息，這些2f+1個節(jié)點形成一個法定人數(shù)，將其表示為Q1。當一個誠實的節(jié)點開始視圖更改時，它會將準備好的消息(包含2f+1準備消息)發(fā)送給新的領(lǐng)導(dǎo)者。新領(lǐng)導(dǎo)者需要收集2f+1個視圖更改消息(表示為法定人數(shù)Q2)才能發(fā)送新的試圖消息。Q1和Q2再次包含至少一個誠實節(jié)點。此節(jié)點包含2f + 1個準備消息，因為它在發(fā)送其提交消息之前必須先收到了足夠的準備消息。這確保了不同視圖中的誠實節(jié)點將提交相同的區(qū)塊。
活性 ：每個節(jié)點都有一個用于正常共識過程的計時器(具有T0超時)和用于視圖更改過程的計時器(具有k*T1超時，其中k是在驗證器可以切換回正常模式之前發(fā)生了多少視圖更改)。當計時器超時時，節(jié)點將通過增加一個視圖來啟動視圖更改。在連續(xù)的領(lǐng)導(dǎo)者未能發(fā)送正確的新視圖消息的情況下，視圖更改計時器的超時時段將增加，以避免頻繁的視圖更改并確保最終足夠的誠實節(jié)點將與誠實的新領(lǐng)導(dǎo)者具有相同的viewID。
快速拜占庭容錯
作為對PBFT的改進，Harmony的共識協(xié)議在通信復(fù)雜性方面是線性可擴展的，因此我們將其稱為快速拜占庭容錯(FBFT)。在FBFT中，領(lǐng)導(dǎo)者不是要求所有驗證者廣播他們的投票，而是運行多簽名的簽名過程以在O(1)大小的多簽名中收集驗證者的投票，然后廣而播之。因此，和接收O(N)簽名不同，每個驗證器僅接收一個多簽名，從而將通信復(fù)雜度從O(N²) 減小到O(N)。通過對視圖更改消息的一些修改，視圖改變復(fù)雜度也可以減少到O(N)。
BLS簽名方案
在這里，我們對Boneh-Lynn-Shacham(BLS)簽名方案進行了非常簡短的數(shù)學介紹，這是FBFT和PBFT之間的主要區(qū)別。BLS簽名方案基于橢圓曲線配對。令E(Fp)為有限域Fp上的橢圓曲線，其中p為大質(zhì)數(shù)。我們在此曲線上選擇一個基本參考點g。私有BLS密鑰是從Fp采樣的隨機數(shù)α，公鑰是α⋅g，是橢圓曲線E上的一個點。給定一個消息m，簽名計算為σ=α⋅H(m)，這也是E上一個點，其中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)在我們可以看到如何通過聚合公鑰來驗證k個簽名。
e(g1,σ1+?+σk)=e(g1,α1⋅H(m)+?+αk⋅H(m))
=e(α1⋅g1+?+αk⋅g1,H(m))
請注意，聚合簽名就是一個普通簽名，也就是橢圓曲線上的一個點，聚合公鑰就是一個普通公鑰，也是橢圓曲線上的一個點。這將2f + 1簽名簡化為僅1個聚合簽名，這對于減少共識協(xié)議中的網(wǎng)絡(luò)流量至關(guān)重要。
正常模式
在傳統(tǒng)的PBFT中，節(jié)點在每輪共識中發(fā)送或接收的總消息大小是O(N²)。這是因為在準備和提交階段，每個節(jié)點需要收集2f+1=O(N)個簽名并將它們廣播到網(wǎng)絡(luò)中的每個節(jié)點(即O(N)個節(jié)點)。通過使用BLS簽名方案，我們將2f+1個簽名聚合成一個簽名，這樣，準備和提交階段的消息大小為O(1)，從而將總大小從O(N²)減少到O(1)回合。
為了從BLS方案中受益，每個驗證器將僅向領(lǐng)導(dǎo)者發(fā)送準備和提交消息，并且領(lǐng)導(dǎo)者負責收集足夠的>=2f+1個簽名并將它們聚合成一個聚合簽名，之后領(lǐng)導(dǎo)者分別在準備/提交階段發(fā)送準備好/已提交的消息。從領(lǐng)導(dǎo)者的角度來看，這三個階段是同步的，但從驗證者的角度來看，他們?nèi)匀豢梢圆话错樞蚪邮障?，例如：驗證者可以在宣布消息之前接收準備好的消息，但是在這種情況下，其準備簽名將不會在準備好的消息中包含。
正常模式分為三個階段：
1. 在宣布階段，領(lǐng)導(dǎo)者將向驗證者廣播宣布消息(例如提議塊)。當驗證器收到宣布消息時，它進入準備階段
2. 在準備階段，驗證器向領(lǐng)導(dǎo)者發(fā)送準備消息(例如，在blockhash上簽名)。當領(lǐng)導(dǎo)者收到足夠多的(即≥2f+1)準備消息時，它會聚合從驗證者收到的準備消息上的簽名，并發(fā)出準備好的消息，其中包含聚合的準備簽名。然后領(lǐng)導(dǎo)者進入提交階段。驗證器在收到來自領(lǐng)導(dǎo)者的準備好的消息時進入提交階段。
3. 在提交階段，驗證器向leader發(fā)送提交消息(例如|blockNum|blockHash|上的簽名)。當領(lǐng)導(dǎo)者收到足夠的(即≥2f+ 1)提交消息時，它會聚合從驗證器接收的提交消息的簽名，并發(fā)出提交消息，其中包含聚合的提交簽名。然后領(lǐng)導(dǎo)者完成一個視圖/回合。驗證器在收到已提交的消息后完成一個視圖/回合。當領(lǐng)導(dǎo)者或驗證者完成一輪時，它將重新啟動共識計時器。
在步驟3，也就是提交階段，驗證者在blockNum和blockHash上發(fā)送帶有簽名的提交消息。這可用于新加入網(wǎng)絡(luò)的節(jié)點確認它是否和當前網(wǎng)絡(luò)同步，同時不至于被惡意領(lǐng)導(dǎo)者欺騙。在狀態(tài)同步模式部分中解釋了共識過程如何與狀態(tài)同步進行交互。
領(lǐng)導(dǎo)者選舉
驗證程序啟動視圖更改過程有兩個原因。一個原因是當驗證器檢測到領(lǐng)導(dǎo)者在一個視圖中提出兩個不同的宣布消息時，它將立即開始視圖更改。另一個原因是驗證者在超時后沒有任何進展。有兩種超時：正常共識模式下的超時和視圖更改模式下的超時。
在我們的區(qū)塊鏈中，我們有了epoch的概念。每個epoch包含X個塊(例如X = 1000)。在每個epoch的開始階段，委員會成員都是由在信標鏈中為這個epoch下注的人決定的。委員會成員的順序由該時期的VDF隨機性唯一確定。在一個epoch中，委員會將始終保持不變。假設(shè)順序列表是[v0，…，vn]，然后在epoch一開始，領(lǐng)導(dǎo)者是v0。如果發(fā)生視圖更改，則下一個領(lǐng)導(dǎo)者是v1，依此類推。在這里，我們假設(shè)每個驗證者具有相同的投票權(quán)。
視圖更改模式
視圖更改過程如下：
1. 當共識定時器超時，節(jié)點通過向新的領(lǐng)導(dǎo)者發(fā)送包括視圖ID(viewID)和準備好(prepared message)的消息(包含≥2f+1個聚合簽名)的視圖更改消息來開始視圖更改。如果它沒有收到準備好的消息，那它就只是發(fā)送空的視圖更改消息，只包括viewID上的簽名但不包括準備好的消息。
2. 當新領(lǐng)導(dǎo)者收到足夠的(≥2f+1)視圖更改消息時，它會聚合viewID的簽名，并從視圖更改消息中選擇一個準備好的消息。它廣播新的視圖消息，包括聚合簽名以及選擇出的準備消息。然后新領(lǐng)導(dǎo)者切換到正常共識模式。驗證者在收到來自新領(lǐng)導(dǎo)者的新視圖消息時切換到正常共識節(jié)點，同時停止視圖更改計時器并啟動共識計時器。如果驗證程序在視圖更改超時之前未收到新的視圖消息，則會將viewID增加1并開始另一個新的視圖更改。
第二步要求每個驗證器在viewID上發(fā)送簽名。目的是用于防備惡意領(lǐng)導(dǎo)者。確切地說，前一個領(lǐng)導(dǎo)者可以在準備階段向不同的驗證者發(fā)送不同的聚合簽名。只要聚合簽名有效，驗證器就會接受它并在發(fā)生視圖更改時提出它。
在這種情況下，每個視圖更改消息都包含不同的簽名，新領(lǐng)導(dǎo)者不能進行簽名聚合，所以新視圖消息的大小為O(N)，這是因為新的領(lǐng)導(dǎo)者必須證明接收到足夠的有效視圖更改消息。如果每個人都在viewID上簽名，新的領(lǐng)導(dǎo)者很容易聚集簽名，這樣可以將新的試圖消息的大小減少到O(1)。只有這樣，我們才能在視圖更改的情況下擴大網(wǎng)絡(luò)中的節(jié)點數(shù)量。
狀態(tài)同步模式
我們允許節(jié)點在區(qū)塊鏈中自由加入和離開。當新節(jié)點加入共識時，它必須先進行狀態(tài)同步，然后才能驗證共識消息。此外，還存在節(jié)點在視圖更改模式下卡住的情況。例如，當驗證程序網(wǎng)絡(luò)連接速度較慢時，可能無法在超時之前取得任何進展。在這種情況下，它將開始視圖更改。但是，它無法從視圖更改模式中退出，因為所有其他節(jié)點都在向前移動，視圖更改會失敗。在這種情況下，此節(jié)點需要執(zhí)行狀態(tài)同步才能趕上。
基本過程很簡單。節(jié)點通過將其當前塊高度和已提交消息中的最新塊高度進行比較，如果檢測出它不同步時，它將切換到狀態(tài)同步模式并開始執(zhí)行狀態(tài)同步。完成狀態(tài)同步后，它會切換到正常模式。
為了在狀態(tài)同步完成后加入共識，節(jié)點需要知道誰是當前的領(lǐng)導(dǎo)者以及當前的viewID是什么。一種解決方案是盲目地接受來自共識消息的領(lǐng)導(dǎo)者和viewID。這種方法使惡意領(lǐng)導(dǎo)者有機會在共識消息中發(fā)送很大的viewID，強制使得每個驗證者開始狀態(tài)同步。
更好的方法是僅在接收提交消息的時候接受領(lǐng)導(dǎo)者和viewID信息。在這種情況下，惡意領(lǐng)導(dǎo)者不能欺騙新節(jié)點。但它減緩了新節(jié)點加入共識的過程，因為在更新領(lǐng)導(dǎo)者和viewID之前，它無法驗證宣布消息和準備好的消息。我們選擇的方法是將領(lǐng)導(dǎo)者和viewID信息添加到區(qū)塊頭中。當節(jié)點完成狀態(tài)同步時，它可以從最新的區(qū)塊頭中讀取信息。如果在狀態(tài)同步期間發(fā)生視圖更改，那么來自最新塊的信息已經(jīng)過時。在這種情況下，新節(jié)點在收到提交的消息時通過更新領(lǐng)導(dǎo)者和viewID信息仍然可以得到最新的信息。
狀態(tài)轉(zhuǎn)換
下圖是驗證器的狀態(tài)轉(zhuǎn)換圖。 領(lǐng)導(dǎo)者的狀態(tài)轉(zhuǎn)換相對比較簡單在此省略。
有5種模式：3種正常模式(A：宣布 ，P：準備，C：提交)，視圖更改模式(VC)和狀態(tài)同步模式(S, Syncing)。
模式之間的轉(zhuǎn)換由不同的條件觸發(fā)，例如接收特定類型的消息或滿足某些條件，如超時。
條件列表：am(宣布消息announce message)，pm(準備好的消息prepare message)，cm(提交消息commit message)，tc(嘗試追趕成功 try catchup)，to(超時 time out)，nv(新視圖消息new view)，is(同步in sync)，os(不同步out of sync)。(Chao Ma)
關(guān)鍵詞： 拜占庭容錯協(xié)議 分布式系統(tǒng)
