引言：共識(shí)問(wèn)題的來(lái)源區(qū)塊鏈平臺(tái)在設(shè)計(jì)和開發(fā)去中心化應(yīng)用程序和系統(tǒng)方面取得了令人難以置信的進(jìn)展，從加密貨幣到企業(yè)供應(yīng)鏈等領(lǐng)域，都已被
引言：共識(shí)問(wèn)題的來(lái)源
區(qū)塊鏈平臺(tái)在設(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)成，其中交易通過(guò)默克爾樹進(jìn)行哈希與編碼，且每個(gè)區(qū)塊會(huì)記錄其前一個(gè)區(qū)塊的加密哈希值。這確保了區(qū)塊鏈的完整性，同時(shí)允許對(duì)每個(gè)區(qū)塊以及區(qū)塊鏈中的交易進(jìn)行相對(duì)低成本的驗(yàn)證和獨(dú)立審計(jì)。區(qū)塊鏈本質(zhì)上是公開且防篡改的，這意味著任何方式都無(wú)法更改現(xiàn)有的區(qū)塊。
區(qū)塊鏈的核心是分類賬本模型，分類賬本是一個(gè)不可更改的、只可追加的、發(fā)生在不同實(shí)體間的交易日志。為了保持分類賬本的完整性，各實(shí)體需要通過(guò)某種方式就是否將一組增量交易(或區(qū)塊)附加到分類賬本上達(dá)成協(xié)議或者共識(shí)。
共識(shí)問(wèn)題是多實(shí)體系統(tǒng)協(xié)調(diào)與控制中的一個(gè)著名而基礎(chǔ)的計(jì)算機(jī)科學(xué)問(wèn)題。一種簡(jiǎn)單的方法當(dāng)然是讓所有實(shí)體就多數(shù)達(dá)成一致。然而，一個(gè)或多個(gè)故障實(shí)體可能會(huì)對(duì)結(jié)果造成影響，從而導(dǎo)致共識(shí)無(wú)法達(dá)成或不正確。
本文將探討區(qū)塊鏈共識(shí)這一主題，并分享一個(gè)真實(shí)的基于.NET Core平臺(tái)的C#實(shí)現(xiàn)方案，C#是Neo區(qū)塊鏈、幣安交易所以及其他一些項(xiàng)目實(shí)體所使用的編程語(yǔ)言。
區(qū)塊鏈平臺(tái)&分布式系統(tǒng)
首先先了解一下區(qū)塊鏈平臺(tái)，它們是可編程的區(qū)塊鏈，使開發(fā)人員能夠構(gòu)建真正去中心化的應(yīng)用程序。其中可以涉及多種市場(chǎng)領(lǐng)域，包括金融市場(chǎng)、游戲、企業(yè)聯(lián)盟、體育、醫(yī)療保健網(wǎng)絡(luò)、主權(quán)身份、房地產(chǎn)和其他資產(chǎn)市場(chǎng)等等。以太坊和Neo等區(qū)塊鏈平臺(tái)作為去中心化的應(yīng)用平臺(tái)，為開發(fā)人員提供了新的應(yīng)用模型基礎(chǔ)。
區(qū)塊鏈平臺(tái)的核心是分布式系統(tǒng)，該技術(shù)建立在數(shù)十年計(jì)算機(jī)科學(xué)研究的理論和實(shí)踐基礎(chǔ)之上。雖然有許多重復(fù)出現(xiàn)的模式和原則，但區(qū)塊鏈平臺(tái)在我們?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ī)方法
通過(guò)對(duì)理論計(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ú)立故障。
無(wú)全局時(shí)間 ：多個(gè)執(zhí)行流可以與空間獨(dú)立的本地時(shí)鐘對(duì)齊。即使這些時(shí)鐘最初是同步的，最后也會(huì)產(chǎn)生時(shí)鐘偏差。這意味著時(shí)間和事件順序是分布式系統(tǒng)的核心挑戰(zhàn)。
通信延遲 ：事件及其影響在分布式系統(tǒng)中的傳播存在固有延遲。
不一致狀態(tài) ：并發(fā)、獨(dú)立故障模式和通信延遲的存在意味著任一狀態(tài)的視圖在整個(gè)分布式系統(tǒng)中會(huì)出現(xiàn)不一致。
總的來(lái)說(shuō)，這些特性要求分布式系統(tǒng)具有容錯(cuò)性，以便在一個(gè)或多個(gè)子系統(tǒng)發(fā)生一個(gè)或多個(gè)故障(或完全故障)時(shí)能夠繼續(xù)運(yùn)行。
狀態(tài)機(jī)方法是通過(guò)復(fù)制服務(wù)和跨服務(wù)副本協(xié)調(diào)客戶端交互來(lái)實(shí)現(xiàn)容錯(cuò)分布式系統(tǒng)的一般方法。復(fù)制狀態(tài)機(jī)是確定性的，因?yàn)樗梢唤M狀態(tài)變量組成，這些變量會(huì)對(duì)其狀態(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á)成共識(shí))。
復(fù)制狀態(tài)機(jī)之間的共識(shí)
正式而言，共識(shí)算法的目標(biāo)是滿足三個(gè)關(guān)鍵特性。分別是：
終止性 ：系統(tǒng)中的所有非故障服務(wù)最終會(huì)決定某些輸出值。這通常被稱為活性。
完整性 ：如果所有非故障服務(wù)都提出相同的輸出值，那么任何非故障服務(wù)都必須決定相同的輸出值。一種較弱的完整性形式是輸出值必須等于某個(gè)非故障服務(wù)(不一定是所有服務(wù))提出的值。
一致性 ：系統(tǒng)中所有非故障服務(wù)最終會(huì)決定相同的輸出值。這通常被稱為安全性。
分布式系統(tǒng)理論在共識(shí)算法的理解上已經(jīng)取得了巨大的飛躍，但是在一個(gè)完全異步的分布式系統(tǒng)中，即使只存在單一的故障服務(wù)，共識(shí)也不可能實(shí)現(xiàn)。這被稱為FLP不可能性，以研究人員(Michael J. Fischer, Nancy Lynch 和Mike Patterson)命名，他們對(duì)異步環(huán)境中分布式進(jìn)程可能實(shí)現(xiàn)的目標(biāo)設(shè)定了一個(gè)確定的上限。
FLP不可能性催生了針對(duì)兩種創(chuàng)新方法的研究。一組算法依賴于所謂的中本共識(shí)。它采用了一種非傳統(tǒng)的方法，這種方法依賴于非決定性來(lái)解決在分布式系統(tǒng)中試圖產(chǎn)生共識(shí)時(shí)固有的規(guī)模挑戰(zhàn)。中本共識(shí)的精髓在于，算法關(guān)注的不是每一個(gè)服務(wù)在某個(gè)值上達(dá)成一致，而是所有服務(wù)就該值正確的概率上形成共識(shí)。
然而，這會(huì)導(dǎo)致概率一致性，也就是說(shuō)，在每一個(gè)狀態(tài)轉(zhuǎn)換時(shí)，無(wú)法確定性地得到一個(gè)最終值，這就造成了無(wú)法保證真正的終局性的情況。這會(huì)導(dǎo)致分布式系統(tǒng)中所謂的分叉場(chǎng)景。因此，在下文我們將不再討論中本共識(shí)。
第二組實(shí)用的容錯(cuò)共識(shí)算法作了一定程度的同步性假設(shè)以取得進(jìn)展。這意味著部分協(xié)議被設(shè)計(jì)成在不可靠的網(wǎng)絡(luò)中運(yùn)行，比如說(shuō)，在因特網(wǎng)上發(fā)生丟包并可能導(dǎo)致任意延遲，而其他協(xié)議則是為高度可靠的網(wǎng)絡(luò)信道而優(yōu)化的。這些協(xié)議據(jù)說(shuō)是在不同的同步假設(shè)下運(yùn)行的。例如，通過(guò)依賴于領(lǐng)導(dǎo)人選舉算法，同步假設(shè)可以是顯式的，也可以是隱式的?；陬I(lǐng)導(dǎo)人選舉的共識(shí)算法稱為Paxos算法。
拜占庭容錯(cuò)共識(shí)
拜占庭故障給基于領(lǐng)導(dǎo)人的共識(shí)算法帶來(lái)了挑戰(zhàn)。當(dāng)分布式系統(tǒng)的組件或子組件發(fā)生故障時(shí)，就會(huì)出現(xiàn)這些故障，并且組件(或子組件)是否實(shí)際發(fā)生故障的信息是不完整的?，F(xiàn)有的算法證明表明，惡意領(lǐng)導(dǎo)者不會(huì)導(dǎo)致不一致狀態(tài)，但分布式系統(tǒng)理論尚未證明惡意領(lǐng)導(dǎo)者無(wú)法阻止算法進(jìn)一步運(yùn)作。
Castro 和Liskov 提出的所謂實(shí)用BFT(pBFT)算法是首次嘗試描述一種算法，通過(guò)該算法，系統(tǒng)可以檢測(cè)到進(jìn)度停滯并選擇出新的領(lǐng)導(dǎo)者。pBFT的設(shè)計(jì)是為了解決先前嘗試中的兩個(gè)缺陷，要么算法運(yùn)行太慢而無(wú)法在實(shí)際中使用，要么必須假設(shè)同步性以滿足“一致性”的屬性。
pBFT算法證明，只要分布式系統(tǒng)中出現(xiàn)故障的服務(wù)數(shù)不超過(guò)(n-1)/3，pBFT算法就可以同時(shí)提供活性和安全性。pBFT通過(guò)一系列“視圖”進(jìn)行循環(huán)，每個(gè)視圖都有一個(gè)主服務(wù)作為議長(zhǎng)，其余服務(wù)作為備份(議員)。在概念層面，pBFT算法的工作原理如下：
1. 客戶端向主(議長(zhǎng))服務(wù)發(fā)送請(qǐng)求。
2. 主(議長(zhǎng))服務(wù)將請(qǐng)求廣播到所有備份服務(wù)。
3. 主服務(wù)和備份服務(wù)處理請(qǐng)求，然后將回復(fù)發(fā)送回客戶端。
4. 當(dāng)客戶端從跨分布式系統(tǒng)的不同服務(wù)接收到m+1響應(yīng)并得到相同的結(jié)果時(shí)，請(qǐng)求即被成功地得到處理，其中m是允許的最大故障服務(wù)數(shù)。
主(議長(zhǎng))服務(wù)在每一個(gè)視圖(共識(shí)輪次)期間都會(huì)更改，并且如果議長(zhǎng)沒有在預(yù)定的時(shí)間閾值內(nèi)向議員廣播請(qǐng)求，則可以替換主(議長(zhǎng))服務(wù)。只要議長(zhǎng)沒有發(fā)生故障，pBFT就可以正常運(yùn)作;但是，更換故障的議長(zhǎng)這一過(guò)程的效率是很低的。
pBFT在現(xiàn)有理論的基礎(chǔ)上進(jìn)行了改進(jìn)，但在實(shí)際應(yīng)用中由于其固有的可擴(kuò)展性挑戰(zhàn)以及無(wú)法對(duì)惡意行為和瞬時(shí)通信故障進(jìn)行區(qū)分，因此不適合于真實(shí)場(chǎng)景。
委托拜占庭容錯(cuò)
委托拜占庭容錯(cuò)(dBFT)是2014年NEO區(qū)塊鏈創(chuàng)始人張錚文提出的。dBFT將pBFT的概念擴(kuò)展到狀態(tài)機(jī)復(fù)制場(chǎng)景，并提供了對(duì)快速單區(qū)塊數(shù)據(jù)終局性(大約15秒)的第一個(gè)實(shí)用的公開訪問(wèn)。dBFT目前正被NEO區(qū)塊鏈、幣安交易所和全球其他主要平臺(tái)所使用。
張錚文提案的關(guān)鍵創(chuàng)新在于區(qū)分共識(shí)節(jié)點(diǎn)(可以參與共識(shí)算法以提出新的狀態(tài)更改和投票的服務(wù))和普通節(jié)點(diǎn)(可以執(zhí)行原子交易和狀態(tài)轉(zhuǎn)換的服務(wù)，但不參與共識(shí)算法，也不能發(fā)起新的狀態(tài)變更)。通過(guò)這樣做，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í)間來(lái)澄清術(shù)語(yǔ)和涉及的算法步驟。
N：活躍的共識(shí)節(jié)點(diǎn)數(shù)
f：拜占庭(即惡意)節(jié)點(diǎn)數(shù)，f不大于(N-1)/3
v:當(dāng)前視圖編號(hào)(每個(gè)視圖都是新一輪或嘗試達(dá)成共識(shí))
b:包含原子交易的提案塊，其執(zhí)行將系統(tǒng)轉(zhuǎn)換到下一個(gè)有效狀態(tài)
P:議長(zhǎng)索引，即該視圖下發(fā)起提案塊的節(jié)點(diǎn)。議長(zhǎng)和其余議員一起構(gòu)成N個(gè)共識(shí)節(jié)點(diǎn)。
在概念層次上，dBFT包括以下步驟：
1. 加密簽名的交易由客戶端“廣播”到分布式系統(tǒng)中的節(jié)點(diǎn)。
2. N個(gè)共識(shí)節(jié)點(diǎn)接收交易并將其加入內(nèi)存中的交易池中。
3. 對(duì)于當(dāng)前視圖，唯一的議長(zhǎng)p將來(lái)自內(nèi)存池的交易打包到新的提案塊b中。圖1說(shuō)明了MakePrepareRequest 方法，圖2說(shuō)明了SendPrepareRequest 方法。
4. 剩余的N-1個(gè)議員接收新的提案塊b，對(duì)其進(jìn)行驗(yàn)證并對(duì)驗(yàn)證結(jié)果進(jìn)行廣播。為簡(jiǎn)潔起見，其余步驟的代碼片段將不再列舉，可訪問(wèn)前面所提供的GitHub的鏈接進(jìn)行查看。
5. 任意共識(shí)節(jié)點(diǎn)在接收到至少(N-f)個(gè)驗(yàn)證后達(dá)成共識(shí)，然后發(fā)布新的區(qū)塊。
6. 任意節(jié)點(diǎn)在接收到新的區(qū)塊時(shí)，都會(huì)從內(nèi)存池中刪除所有交易，如果是共識(shí)節(jié)點(diǎn)，則開始下一個(gè)視圖(一輪共識(shí))。
所有這些都解決了，讓我們回到dBFT算法的三個(gè)階段。它們分別是：
預(yù)準(zhǔn)備 ：本次視圖的議長(zhǎng)負(fù)責(zé)向議員廣播Prepare-Request消息，并發(fā)起新的交易提案塊。
準(zhǔn)備 ：在接收到Prepare-Request消息時(shí)，如果成功驗(yàn)證了提案塊，則議員廣播Prepare-Response消息。當(dāng)接收到(N-f)條區(qū)塊成功驗(yàn)證的消息時(shí)，共識(shí)節(jié)點(diǎn)進(jìn)入下一階段。
持久化 ：節(jié)點(diǎn)發(fā)布新塊并進(jìn)入下一輪共識(shí)。
在某一輪(視圖)未達(dá)成共識(shí)的情況下，共識(shí)節(jié)點(diǎn)可以發(fā)起視圖更換提案，在收到至少(N-f)個(gè)具有完全相同視圖編號(hào)的視圖更改提案后，重新選舉議長(zhǎng)節(jié)點(diǎn)(領(lǐng)導(dǎo)者)并重啟達(dá)成共識(shí)的活動(dòng)。發(fā)起新一輪視圖的等待時(shí)間呈指數(shù)增長(zhǎng)，以避免頻繁的視圖變更，并確保在實(shí)際時(shí)間范圍內(nèi)達(dá)成共識(shí)。
由于在某些邊緣情況下出現(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è)共識(shí)節(jié)點(diǎn)沒有超時(shí)，并且該節(jié)點(diǎn)已經(jīng)收到2f條 PrepareResponse 消息，那么它將生成一個(gè)有效的區(qū)塊，而其他共識(shí)節(jié)點(diǎn)將轉(zhuǎn)移到下一個(gè)視圖。在該視圖上，這些共識(shí)節(jié)點(diǎn)理論上可以達(dá)成共識(shí)，并在同一高度對(duì)另一個(gè)交易區(qū)塊進(jìn)行簽名。雖然該場(chǎng)景可以在不阻塞共識(shí)的情況下發(fā)生，但一個(gè)或多個(gè)節(jié)點(diǎn)可能會(huì)接受到分叉的區(qū)塊而停止運(yùn)行。
dBFT 2.0通過(guò)新增一個(gè)commit提交階段解決了這個(gè)問(wèn)題。為了防止可能出現(xiàn)的運(yùn)作停止，dBFT 2.0還使用一個(gè)恢復(fù)消息實(shí)現(xiàn)方案來(lái)增強(qiáng)共識(shí)算法。這種恢復(fù)機(jī)制的另一個(gè)好處是，在由于網(wǎng)絡(luò)受損而導(dǎo)致網(wǎng)絡(luò)延遲降級(jí)的情況下，可以顯著改善出塊時(shí)間。
結(jié)語(yǔ)
分布式系統(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)中的既定原則和范例，并在這樣做的過(guò)程中推動(dòng)了一股創(chuàng)新浪潮，這股浪潮繼續(xù)在開發(fā)人員如何構(gòu)建下一代軟件應(yīng)用程序方面開辟新的天地。
本文我們重點(diǎn)討論了共識(shí)問(wèn)題，并用dBFT共識(shí)算法說(shuō)明了一種開創(chuàng)性的新方法。當(dāng)我們使用C#來(lái)說(shuō)明dBFT共識(shí)算法時(shí)，我們也實(shí)現(xiàn)了c++、python、typescript和go的dBFT算法。我們希望本文能讓開發(fā)人員更好地理解區(qū)塊鏈共識(shí)，并使他們能夠使用并基于領(lǐng)先的dBFT算法進(jìn)行開發(fā)。
張錚文
張錚文是NEO的創(chuàng)始人和核心開發(fā)人員，dBFT共識(shí)機(jī)制的創(chuàng)作者，區(qū)塊鏈技術(shù)和計(jì)算機(jī)安全專家，以及注冊(cè)信息系統(tǒng)審計(jì)師(CISA)。此前，他在盛大游戲和火幣工作，專門從事信息安全和數(shù)字貨幣研發(fā)。
John deVadoss
John deVadoss領(lǐng)導(dǎo)NGD在西雅圖的開發(fā)。此前，他創(chuàng)建了Microsoft Digital、.NET 模式與實(shí)踐和.NET體系結(jié)構(gòu)戰(zhàn)略。在微軟工作時(shí)孵化了微軟的Azure。最近，他創(chuàng)辦了兩家機(jī)器學(xué)習(xí)初創(chuàng)公司。deVadoss在機(jī)器學(xué)習(xí)方面取得了博士學(xué)位，專門研究遞歸神經(jīng)網(wǎng)絡(luò)。（NEO）
