引言：共識問題的來源

區塊鏈平臺在設計和開發去中心化應用程序和系統方面取得了令人難以置信的進展，從加密貨幣到企業供應鏈等領域，都已被廣泛應用。雖然應用非常廣泛，但它們都是基于一組核心的設計模式，正是這些設計模式推動了分布式系統理論和實踐的發展。

區塊鏈是使用加密技術將記錄（或區塊）鏈接而成的單調遞增的列表。區塊由一組有效交易構成，其中交易通過默克爾樹進行哈希與編碼，且每個區塊會記錄其前一個區塊的加密哈希值。這確保了區塊鏈的完整性，同時允許對每個區塊以及區塊鏈中的交易進行相對低成本的驗證和獨立審計。區塊鏈本質上是公開且防篡改的，這意味著任何方式都無法更改現有的區塊。

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

共識問題是多實體系統協調與控制中的一個著名而基礎的計算機科學問題。一種簡單的方法當然是讓所有實體就多數達成一致。然而，一個或多個故障實體可能會對結果造成影響，從而導致共識無法達成或不正確。

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

區塊鏈平臺&分布式系統

首先先了解一下區塊鏈平臺，它們是可編程的區塊鏈，使開發人員能夠構建真正去中心化的應用程序。其中可以涉及多種市場領域，包括金融市場、游戲、企業聯盟、體育、醫療保健網絡、主權身份、房地產和其他資產市場等等。以太坊和Neo等區塊鏈平臺作為去中心化的應用平臺，為開發人員提供了新的應用模型基礎。

區塊鏈平臺的核心是分布式系統，該技術建立在數十年計算機科學研究的理論和實踐基礎之上。雖然有許多重復出現的模式和原則，但區塊鏈平臺在我們如何處理信任方面徹底顛覆了分布式系統的理論。在下一節，我們將進一步深入研究分布式系統及其使用計算機科學中著名的狀態機模型的相關實現。

分布式系統與狀態機方法

通過對理論計算機科學領域的探索，我們發現各類分布式系統均共享以下核心特性：

并發 ：分布式系統中的多個活動可以同時獨立地執行。這意味著需要在不同的執行流間進行協調。

獨立故障模式 ：分布系統中的多個組件可能發生獨立故障。

無全局時間 ：多個執行流可以與空間獨立的本地時鐘對齊。即使這些時鐘最初是同步的，最后也會產生時鐘偏差。這意味著時間和事件順序是分布式系統的核心挑戰。

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

不一致狀態 ：并發、獨立故障模式和通信延遲的存在意味著任一狀態的視圖在整個分布式系統中會出現不一致。

總的來說，這些特性要求分布式系統具有容錯性，以便在一個或多個子系統發生一個或多個故障（或完全故障）時能夠繼續運行。

狀態機方法是通過復制服務和跨服務副本協調客戶端交互來實現容錯分布式系統的一般方法。復制狀態機是確定性的，因為它由一組狀態變量組成，這些變量會對其狀態和交易進行編碼。這些狀態變量可能引起計算機從一個有效狀態轉換到下一個有效狀態。每個交易都是確定執行的（即，交易具有原子性）。從本質上講，復制狀態機是一組分布式服務，其中所有服務都從相同的初始狀態開始，然后在隨后的每個狀態轉換上達成一致（即，達成共識）。

復制狀態機之間的共識

正式而言，共識算法的目標是滿足三個關鍵特性。分別是：

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

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

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

分布式系統理論在共識算法的理解上已經取得了巨大的飛躍，但是在一個完全異步的分布式系統中，即使只存在單一的故障服務，共識也不可能實現。這被稱為FLP不可能性，以研究人員（Michael J. Fischer， Nancy Lynch 和Mike Patterson）命名，他們對異步環境中分布式進程可能實現的目標設定了一個確定的上限。

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

第二組實用的容錯共識算法作了一定程度的同步性假設以取得進展。這意味著部分協議被設計成在不可靠的網絡中運行，比如說，在因特網上發生丟包并可能導致任意延遲，而其他協議則是為高度可靠的網絡信道而優化的。這些協議據說是在不同的同步假設下運行的。例如，通過依賴于領導人選舉算法，同步假設可以是顯式的，也可以是隱式的。基于領導人選舉的共識算法稱為Paxos算法。

拜占庭容錯共識

拜占庭故障給基于領導人的共識算法帶來了挑戰。當分布式系統的組件或子組件發生故障時，就會出現這些故障，并且組件（或子組件）是否實際發生故障的信息是不完整的。現有的算法證明表明，惡意領導者不會導致不一致狀態，但分布式系統理論尚未證明惡意領導者無法阻止算法進一步運作。

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

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

1. 客戶端向主（議長）服務發送請求。

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

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

4. 當客戶端從跨分布式系統的不同服務接收到m+1響應并得到相同的結果時，請求即被成功地得到處理，其中m是允許的最大故障服務數。

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

pBFT在現有理論的基礎上進行了改進，但在實際應用中由于其固有的可擴展性挑戰以及無法對惡意行為和瞬時通信故障進行區分，因此不適合于真實場景。

委托拜占庭容錯

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

張錚文提案的關鍵創新在于區分共識節點（可以參與共識算法以提出新的狀態更改和投票的服務）和普通節點（可以執行原子交易和狀態轉換的服務，但不參與共識算法，也不能發起新的狀態變更）。通過這樣做，dBFT成為第一個大規模運行的實用BFT算法，解決了pBFT固有的挑戰。

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

dBFT算法包括三個不同的階段：預準備、準備和持久化。在我們探索每個階段之前，讓我們花一點時間來澄清術語和涉及的算法步驟。

N：活躍的共識節點數

f：拜占庭（即惡意）節點數，f不大于（N-1）/3

v：當前視圖編號（每個視圖都是新一輪或嘗試達成共識）

b：包含原子交易的提案塊，其執行將系統轉換到下一個有效狀態

P：議長索引，即該視圖下發起提案塊的節點。議長和其余議員一起構成N個共識節點。

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

1. 加密簽名的交易由客戶端“廣播”到分布式系統中的節點。

2. N個共識節點接收交易并將其加入內存中的交易池中。

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

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

5. 任意共識節點在接收到至少（N-f）個驗證后達成共識，然后發布新的區塊。

6. 任意節點在接收到新的區塊時，都會從內存池中刪除所有交易，如果是共識節點，則開始下一個視圖（一輪共識）。

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

預準備 ：本次視圖的議長負責向議員廣播Prepare-Request消息，并發起新的交易提案塊。

準備 ：在接收到Prepare-Request消息時，如果成功驗證了提案塊，則議員廣播Prepare-Response消息。當接收到（N-f）條區塊成功驗證的消息時，共識節點進入下一階段。

持久化 ：節點發布新塊并進入下一輪共識。

在某一輪（視圖）未達成共識的情況下，共識節點可以發起視圖更換提案，在收到至少（N-f）個具有完全相同視圖編號的視圖更改提案后，重新選舉議長節點（領導者）并重啟達成共識的活動。發起新一輪視圖的等待時間呈指數增長，以避免頻繁的視圖變更，并確保在實際時間范圍內達成共識。

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

dBFT 2.0通過新增一個commit提交階段解決了這個問題。為了防止可能出現的運作停止，dBFT 2.0還使用一個恢復消息實現方案來增強共識算法。這種恢復機制的另一個好處是，在由于網絡受損而導致網絡延遲降級的情況下，可以顯著改善出塊時間。

結語

分布式系統是改革計算行業的基礎，也是我們如何在全球范圍內進行商業活動，以及我們如何作為一個社區廣泛參與的基礎。區塊鏈的出現促使開發人員研究和審查分布式系統中的既定原則和范例，并在這樣做的過程中推動了一股創新浪潮，這股浪潮繼續在開發人員如何構建下一代軟件應用程序方面開辟新的天地。
來源： NEO智能經濟?