引言：共識問題的來源

區(qū)塊鏈平臺在設(shè)計(jì)和開發(fā)去中心化應(yīng)用程序和系統(tǒng)方面取得了令人難以置信的進(jìn)展，從加密貨幣到企業(yè)供應(yīng)鏈等領(lǐng)域，都已被廣泛應(yīng)用。雖然應(yīng)用非常廣泛，但它們都是基于一組核心的設(shè)計(jì)模式，正是這些設(shè)計(jì)模式推動(dòng)了分布式系統(tǒng)理論和實(shí)踐的發(fā)展。

區(qū)塊鏈?zhǔn)鞘褂眉用芗夹g(shù)將記錄（或區(qū)塊）鏈接而成的單調(diào)遞增的列表。區(qū)塊由一組有效交易構(gòu)成，其中交易通過默克爾樹進(jìn)行哈希與編碼，且每個(gè)區(qū)塊會記錄其前一個(gè)區(qū)塊的加密哈希值。這確保了區(qū)塊鏈的完整性，同時(shí)允許對每個(gè)區(qū)塊以及區(qū)塊鏈中的交易進(jìn)行相對低成本的驗(yàn)證和獨(dú)立審計(jì)。區(qū)塊鏈本質(zhì)上是公開且防篡改的，這意味著任何方式都無法更改現(xiàn)有的區(qū)塊。

區(qū)塊鏈的核心是分類賬本模型，分類賬本是一個(gè)不可更改的、只可追加的、發(fā)生在不同實(shí)體間的交易日志。為了保持分類賬本的完整性，各實(shí)體需要通過某種方式就是否將一組增量交易（或區(qū)塊）附加到分類賬本上達(dá)成協(xié)議或者共識。

共識問題是多實(shí)體系統(tǒng)協(xié)調(diào)與控制中的一個(gè)著名而基礎(chǔ)的計(jì)算機(jī)科學(xué)問題。一種簡單的方法當(dāng)然是讓所有實(shí)體就多數(shù)達(dá)成一致。然而，一個(gè)或多個(gè)故障實(shí)體可能會對結(jié)果造成影響，從而導(dǎo)致共識無法達(dá)成或不正確。

本文將探討區(qū)塊鏈共識這一主題，并分享一個(gè)真實(shí)的基于.NET Core平臺的C#實(shí)現(xiàn)方案，C#是Neo區(qū)塊鏈、幣安交易所以及其他一些項(xiàng)目實(shí)體所使用的編程語言。

區(qū)塊鏈平臺&分布式系統(tǒng)

首先先了解一下區(qū)塊鏈平臺，它們是可編程的區(qū)塊鏈，使開發(fā)人員能夠構(gòu)建真正去中心化的應(yīng)用程序。其中可以涉及多種市場領(lǐng)域，包括金融市場、游戲、企業(yè)聯(lián)盟、體育、醫(yī)療保健網(wǎng)絡(luò)、主權(quán)身份、房地產(chǎn)和其他資產(chǎn)市場等等。以太坊和Neo等區(qū)塊鏈平臺作為去中心化的應(yīng)用平臺，為開發(fā)人員提供了新的應(yīng)用模型基礎(chǔ)。

區(qū)塊鏈平臺的核心是分布式系統(tǒng)，該技術(shù)建立在數(shù)十年計(jì)算機(jī)科學(xué)研究的理論和實(shí)踐基礎(chǔ)之上。雖然有許多重復(fù)出現(xiàn)的模式和原則，但區(qū)塊鏈平臺在我們?nèi)绾翁幚硇湃畏矫鎻氐最嵏擦朔植际较到y(tǒng)的理論。在下一節(jié)，我們將進(jìn)一步深入研究分布式系統(tǒng)及其使用計(jì)算機(jī)科學(xué)中著名的狀態(tài)機(jī)模型的相關(guān)實(shí)現(xiàn)。

分布式系統(tǒng)與狀態(tài)機(jī)方法

通過對理論計(jì)算機(jī)科學(xué)領(lǐng)域的探索，我們發(fā)現(xiàn)各類分布式系統(tǒng)均共享以下核心特性：

并發(fā) ：分布式系統(tǒng)中的多個(gè)活動(dòng)可以同時(shí)獨(dú)立地執(zhí)行。這意味著需要在不同的執(zhí)行流間進(jìn)行協(xié)調(diào)。

獨(dú)立故障模式 ：分布系統(tǒng)中的多個(gè)組件可能發(fā)生獨(dú)立故障。

無全局時(shí)間 ：多個(gè)執(zhí)行流可以與空間獨(dú)立的本地時(shí)鐘對齊。即使這些時(shí)鐘最初是同步的，最后也會產(chǎn)生時(shí)鐘偏差。這意味著時(shí)間和事件順序是分布式系統(tǒng)的核心挑戰(zhàn)。

通信延遲 ：事件及其影響在分布式系統(tǒng)中的傳播存在固有延遲。

不一致狀態(tài) ：并發(fā)、獨(dú)立故障模式和通信延遲的存在意味著任一狀態(tài)的視圖在整個(gè)分布式系統(tǒng)中會出現(xiàn)不一致。

總的來說，這些特性要求分布式系統(tǒng)具有容錯(cuò)性，以便在一個(gè)或多個(gè)子系統(tǒng)發(fā)生一個(gè)或多個(gè)故障（或完全故障）時(shí)能夠繼續(xù)運(yùn)行。

狀態(tài)機(jī)方法是通過復(fù)制服務(wù)和跨服務(wù)副本協(xié)調(diào)客戶端交互來實(shí)現(xiàn)容錯(cuò)分布式系統(tǒng)的一般方法。復(fù)制狀態(tài)機(jī)是確定性的，因?yàn)樗梢唤M狀態(tài)變量組成，這些變量會對其狀態(tài)和交易進(jìn)行編碼。這些狀態(tài)變量可能引起計(jì)算機(jī)從一個(gè)有效狀態(tài)轉(zhuǎn)換到下一個(gè)有效狀態(tài)。每個(gè)交易都是確定執(zhí)行的（即，交易具有原子性）。從本質(zhì)上講，復(fù)制狀態(tài)機(jī)是一組分布式服務(wù)，其中所有服務(wù)都從相同的初始狀態(tài)開始，然后在隨后的每個(gè)狀態(tài)轉(zhuǎn)換上達(dá)成一致（即，達(dá)成共識）。

復(fù)制狀態(tài)機(jī)之間的共識

正式而言，共識算法的目標(biāo)是滿足三個(gè)關(guān)鍵特性。分別是：

終止性 ：系統(tǒng)中的所有非故障服務(wù)最終會決定某些輸出值。這通常被稱為活性。

完整性 ：如果所有非故障服務(wù)都提出相同的輸出值，那么任何非故障服務(wù)都必須決定相同的輸出值。一種較弱的完整性形式是輸出值必須等于某個(gè)非故障服務(wù)（不一定是所有服務(wù)）提出的值。

一致性 ：系統(tǒng)中所有非故障服務(wù)最終會決定相同的輸出值。這通常被稱為安全性。

分布式系統(tǒng)理論在共識算法的理解上已經(jīng)取得了巨大的飛躍，但是在一個(gè)完全異步的分布式系統(tǒng)中，即使只存在單一的故障服務(wù)，共識也不可能實(shí)現(xiàn)。這被稱為FLP不可能性，以研究人員（Michael J. Fischer， Nancy Lynch 和Mike Patterson）命名，他們對異步環(huán)境中分布式進(jìn)程可能實(shí)現(xiàn)的目標(biāo)設(shè)定了一個(gè)確定的上限。

FLP不可能性催生了針對兩種創(chuàng)新方法的研究。一組算法依賴于所謂的中本共識。它采用了一種非傳統(tǒng)的方法，這種方法依賴于非決定性來解決在分布式系統(tǒng)中試圖產(chǎn)生共識時(shí)固有的規(guī)模挑戰(zhàn)。中本共識的精髓在于，算法關(guān)注的不是每一個(gè)服務(wù)在某個(gè)值上達(dá)成一致，而是所有服務(wù)就該值正確的概率上形成共識。然而，這會導(dǎo)致概率一致性，也就是說，在每一個(gè)狀態(tài)轉(zhuǎn)換時(shí)，無法確定性地得到一個(gè)最終值，這就造成了無法保證真正的終局性的情況。這會導(dǎo)致分布式系統(tǒng)中所謂的分叉場景。因此，在下文我們將不再討論中本共識。

第二組實(shí)用的容錯(cuò)共識算法作了一定程度的同步性假設(shè)以取得進(jìn)展。這意味著部分協(xié)議被設(shè)計(jì)成在不可靠的網(wǎng)絡(luò)中運(yùn)行，比如說，在因特網(wǎng)上發(fā)生丟包并可能導(dǎo)致任意延遲，而其他協(xié)議則是為高度可靠的網(wǎng)絡(luò)信道而優(yōu)化的。這些協(xié)議據(jù)說是在不同的同步假設(shè)下運(yùn)行的。例如，通過依賴于領(lǐng)導(dǎo)人選舉算法，同步假設(shè)可以是顯式的，也可以是隱式的?；陬I(lǐng)導(dǎo)人選舉的共識算法稱為Paxos算法。

拜占庭容錯(cuò)共識

拜占庭故障給基于領(lǐng)導(dǎo)人的共識算法帶來了挑戰(zhàn)。當(dāng)分布式系統(tǒng)的組件或子組件發(fā)生故障時(shí)，就會出現(xiàn)這些故障，并且組件（或子組件）是否實(shí)際發(fā)生故障的信息是不完整的?，F(xiàn)有的算法證明表明，惡意領(lǐng)導(dǎo)者不會導(dǎo)致不一致狀態(tài)，但分布式系統(tǒng)理論尚未證明惡意領(lǐng)導(dǎo)者無法阻止算法進(jìn)一步運(yùn)作。

Castro 和Liskov 提出的所謂實(shí)用BFT（pBFT）算法是首次嘗試描述一種算法，通過該算法，系統(tǒng)可以檢測到進(jìn)度停滯并選擇出新的領(lǐng)導(dǎo)者。pBFT的設(shè)計(jì)是為了解決先前嘗試中的兩個(gè)缺陷，要么算法運(yùn)行太慢而無法在實(shí)際中使用，要么必須假設(shè)同步性以滿足“一致性”的屬性。

pBFT算法證明，只要分布式系統(tǒng)中出現(xiàn)故障的服務(wù)數(shù)不超過（n-1）/3，pBFT算法就可以同時(shí)提供活性和安全性。pBFT通過一系列“視圖”進(jìn)行循環(huán)，每個(gè)視圖都有一個(gè)主服務(wù)作為議長，其余服務(wù)作為備份（議員）。在概念層面，pBFT算法的工作原理如下：

1. 客戶端向主（議長）服務(wù)發(fā)送請求。

2. 主（議長）服務(wù)將請求廣播到所有備份服務(wù)。

3. 主服務(wù)和備份服務(wù)處理請求，然后將回復(fù)發(fā)送回客戶端。

4. 當(dāng)客戶端從跨分布式系統(tǒng)的不同服務(wù)接收到m+1響應(yīng)并得到相同的結(jié)果時(shí)，請求即被成功地得到處理，其中m是允許的最大故障服務(wù)數(shù)。

主（議長）服務(wù)在每一個(gè)視圖（共識輪次）期間都會更改，并且如果議長沒有在預(yù)定的時(shí)間閾值內(nèi)向議員廣播請求，則可以替換主（議長）服務(wù)。只要議長沒有發(fā)生故障，pBFT就可以正常運(yùn)作；但是，更換故障的議長這一過程的效率是很低的。

pBFT在現(xiàn)有理論的基礎(chǔ)上進(jìn)行了改進(jìn)，但在實(shí)際應(yīng)用中由于其固有的可擴(kuò)展性挑戰(zhàn)以及無法對惡意行為和瞬時(shí)通信故障進(jìn)行區(qū)分，因此不適合于真實(shí)場景。

委托拜占庭容錯(cuò)

委托拜占庭容錯(cuò)（dBFT）是2014年NEO區(qū)塊鏈創(chuàng)始人張錚文提出的。dBFT將pBFT的概念擴(kuò)展到狀態(tài)機(jī)復(fù)制場景，并提供了對快速單區(qū)塊數(shù)據(jù)終局性（大約15秒）的第一個(gè)實(shí)用的公開訪問。dBFT目前正被NEO區(qū)塊鏈、幣安交易所和全球其他主要平臺所使用。

張錚文提案的關(guān)鍵創(chuàng)新在于區(qū)分共識節(jié)點(diǎn)（可以參與共識算法以提出新的狀態(tài)更改和投票的服務(wù)）和普通節(jié)點(diǎn)（可以執(zhí)行原子交易和狀態(tài)轉(zhuǎn)換的服務(wù)，但不參與共識算法，也不能發(fā)起新的狀態(tài)變更）。通過這樣做，dBFT成為第一個(gè)大規(guī)模運(yùn)行的實(shí)用BFT算法，解決了pBFT固有的挑戰(zhàn)。

dBFT的c#實(shí)現(xiàn)可在GitHub的bit.ly/2Zl1Sem上的公共域（MIT許可證）中獲得。

dBFT算法包括三個(gè)不同的階段：預(yù)準(zhǔn)備、準(zhǔn)備和持久化。在我們探索每個(gè)階段之前，讓我們花一點(diǎn)時(shí)間來澄清術(shù)語和涉及的算法步驟。

N：活躍的共識節(jié)點(diǎn)數(shù)

f：拜占庭（即惡意）節(jié)點(diǎn)數(shù)，f不大于（N-1）/3

v：當(dāng)前視圖編號（每個(gè)視圖都是新一輪或嘗試達(dá)成共識）

b：包含原子交易的提案塊，其執(zhí)行將系統(tǒng)轉(zhuǎn)換到下一個(gè)有效狀態(tài)

P：議長索引，即該視圖下發(fā)起提案塊的節(jié)點(diǎn)。議長和其余議員一起構(gòu)成N個(gè)共識節(jié)點(diǎn)。

在概念層次上，dBFT包括以下步驟：

1. 加密簽名的交易由客戶端“廣播”到分布式系統(tǒng)中的節(jié)點(diǎn)。

2. N個(gè)共識節(jié)點(diǎn)接收交易并將其加入內(nèi)存中的交易池中。

3. 對于當(dāng)前視圖，唯一的議長p將來自內(nèi)存池的交易打包到新的提案塊b中。圖1說明了MakePrepareRequest 方法，圖2說明了SendPrepareRequest 方法。

4. 剩余的N-1個(gè)議員接收新的提案塊b，對其進(jìn)行驗(yàn)證并對驗(yàn)證結(jié)果進(jìn)行廣播。為簡潔起見，其余步驟的代碼片段將不再列舉，可訪問前面所提供的GitHub的鏈接進(jìn)行查看。

5. 任意共識節(jié)點(diǎn)在接收到至少（N-f）個(gè)驗(yàn)證后達(dá)成共識，然后發(fā)布新的區(qū)塊。

6. 任意節(jié)點(diǎn)在接收到新的區(qū)塊時(shí)，都會從內(nèi)存池中刪除所有交易，如果是共識節(jié)點(diǎn)，則開始下一個(gè)視圖（一輪共識）。

所有這些都解決了，讓我們回到dBFT算法的三個(gè)階段。它們分別是：

預(yù)準(zhǔn)備 ：本次視圖的議長負(fù)責(zé)向議員廣播Prepare-Request消息，并發(fā)起新的交易提案塊。

準(zhǔn)備 ：在接收到Prepare-Request消息時(shí)，如果成功驗(yàn)證了提案塊，則議員廣播Prepare-Response消息。當(dāng)接收到（N-f）條區(qū)塊成功驗(yàn)證的消息時(shí)，共識節(jié)點(diǎn)進(jìn)入下一階段。

持久化 ：節(jié)點(diǎn)發(fā)布新塊并進(jìn)入下一輪共識。

在某一輪（視圖）未達(dá)成共識的情況下，共識節(jié)點(diǎn)可以發(fā)起視圖更換提案，在收到至少（N-f）個(gè)具有完全相同視圖編號的視圖更改提案后，重新選舉議長節(jié)點(diǎn)（領(lǐng)導(dǎo)者）并重啟達(dá)成共識的活動(dòng)。發(fā)起新一輪視圖的等待時(shí)間呈指數(shù)增長，以避免頻繁的視圖變更，并確保在實(shí)際時(shí)間范圍內(nèi)達(dá)成共識。

由于在某些邊緣情況下出現(xiàn)的網(wǎng)絡(luò)延遲，dBFT的第一個(gè)版本存在單區(qū)塊分叉的影響。實(shí)際上，節(jié)點(diǎn)在發(fā)送PrepareResponse 消息后可能超時(shí)，這意味著節(jié)點(diǎn)可能在稍有不同的時(shí)間發(fā)生超時(shí)和狀態(tài)轉(zhuǎn)換。如果只有一個(gè)共識節(jié)點(diǎn)沒有超時(shí)，并且該節(jié)點(diǎn)已經(jīng)收到2f條 PrepareResponse 消息，那么它將生成一個(gè)有效的區(qū)塊，而其他共識節(jié)點(diǎn)將轉(zhuǎn)移到下一個(gè)視圖。在該視圖上，這些共識節(jié)點(diǎn)理論上可以達(dá)成共識，并在同一高度對另一個(gè)交易區(qū)塊進(jìn)行簽名。雖然該場景可以在不阻塞共識的情況下發(fā)生，但一個(gè)或多個(gè)節(jié)點(diǎn)可能會接受到分叉的區(qū)塊而停止運(yùn)行。

dBFT 2.0通過新增一個(gè)commit提交階段解決了這個(gè)問題。為了防止可能出現(xiàn)的運(yùn)作停止，dBFT 2.0還使用一個(gè)恢復(fù)消息實(shí)現(xiàn)方案來增強(qiáng)共識算法。這種恢復(fù)機(jī)制的另一個(gè)好處是，在由于網(wǎng)絡(luò)受損而導(dǎo)致網(wǎng)絡(luò)延遲降級的情況下，可以顯著改善出塊時(shí)間。

結(jié)語

分布式系統(tǒng)是改革計(jì)算行業(yè)的基礎(chǔ)，也是我們?nèi)绾卧谌蚍秶鷥?nèi)進(jìn)行商業(yè)活動(dòng)，以及我們?nèi)绾巫鳛橐粋€(gè)社區(qū)廣泛參與的基礎(chǔ)。區(qū)塊鏈的出現(xiàn)促使開發(fā)人員研究和審查分布式系統(tǒng)中的既定原則和范例，并在這樣做的過程中推動(dòng)了一股創(chuàng)新浪潮，這股浪潮繼續(xù)在開發(fā)人員如何構(gòu)建下一代軟件應(yīng)用程序方面開辟新的天地。
來源： NEO智能經(jīng)濟(jì)?