資訊專欄INFORMATION COLUMN
摘要：實用拜占庭容錯系統(tǒng)降低了拜占庭協(xié)議的運行復雜度，從指數(shù)級別降低到多項式級別，使拜占庭協(xié)議在分布式系統(tǒng)中應用成為可能。
拜占庭容錯系統(tǒng)簡介
原始的拜占庭容錯系統(tǒng)由于需要展示理論上的可行性而缺乏實用性。另外，算法的復雜度也是隨節(jié)點的增加而呈指數(shù)級增加。實用拜占庭容錯系統(tǒng)（Practical Byzantine Fault Tolerance, PBFT）降低了拜占庭協(xié)議的運行復雜度，從指數(shù)級別降低到多項式級別，使拜占庭協(xié)議在分布式系統(tǒng)中應用成為可能。
什么是實用拜占庭容錯系統(tǒng)實用拜占庭容錯系統(tǒng)是一類“狀態(tài)機”拜占庭系統(tǒng)（這里的狀態(tài)機可以理解為“系統(tǒng)狀態(tài)”，以區(qū)塊鏈記賬為例，系統(tǒng)每新增一個區(qū)塊，賬本就更新到一個新的狀態(tài)。前面講過，拜占庭容錯系統(tǒng)是一個強一致性協(xié)議，每次記賬后系統(tǒng)都會達成新的狀態(tài)。），要求系統(tǒng)所有節(jié)點共同維護一個狀態(tài)，所有節(jié)點采取的行動一致。
實用拜占庭容錯系統(tǒng)需要運行三類基本協(xié)議：
一致性協(xié)議：解決如何達成共識
檢查點協(xié)議：類似于操作系統(tǒng)的還原點
視圖更換協(xié)議：系統(tǒng)的每個服務器節(jié)點在同樣的配置信息下工作，該配置信息被稱為“視圖”。配置信息由主節(jié)點確定，主節(jié)點更換，視圖也隨之變化。
我們主要關注支持系統(tǒng)日常運行的一致性協(xié)議。
PBFT 的 一致性協(xié)議一致性協(xié)議至少包含請求（request）、序號分配（pre-prepare）、響應（reply）三個階段。根據(jù)協(xié)議設計的不同，可能包含相互交互(prepare) 、序號確認(commit)等階段。
PBFT系統(tǒng)通常假設故障節(jié)點個數(shù)為m個，而整個服務節(jié)點數(shù)為3m+1個。
上圖顯示了一個簡化的 PBFT 的協(xié)議通信模式，其中C為客戶端，N0~N3為服務節(jié)點，N0為主節(jié)點，N3為故障節(jié)點。協(xié)議的節(jié)本過程如下：
Request：客戶端發(fā)送請求，激活主節(jié)點的服務操作
當主節(jié)點接收請求后，啟動三階段的協(xié)議以向各從節(jié)點廣播請求
Pre-Prepare：主節(jié)點給請求賦值一個序列號n，廣播序號分配消息和請求消息，并構造PRE-PREPARE消息給各從節(jié)點
Prepare：從節(jié)點接收PRE-PREPARE消息，并向其他服務節(jié)點廣播PREPARE消息
Commit：各節(jié)點對視圖內(nèi)的請求和次序進行驗證后，廣播COMMIT消息，執(zhí)行收到的客戶端的請求并給客戶端以響應
Reply：客戶端等待來自不同節(jié)點的響應，若有m+1個響應相同，則該響應即為運算的結果
PBFT 演示在 n ≥ 3m + 1 的情況下一致性是可能解決的，其中，n為總節(jié)點數(shù)，m為惡意節(jié)點總數(shù)。我們模擬一下PBFT：
n = 4, m = 0
| 節(jié)點 | 得到數(shù)據(jù) | 最終結果 |
|---|---|---|
| A | 1111 | 1 |
| B | 1111 | 1 |
| C | 1111 | 1 |
| D | 1111 | 1 |
n = 4, m = 1
| 節(jié)點 | 得到數(shù)據(jù) | 最終結果 |
|---|---|---|
| A | 1110 | 1 |
| B | 1101 | 1 |
| C | 1011 | 1 |
| D | 0111 | 1 |
n = 4，m = 2
| 節(jié)點 | 得到數(shù)據(jù) | 最終結果 |
|---|---|---|
| A | 1100 | NA |
| B | 1001 | NA |
| C | 0011 | NA |
| D | 0110 | NA |
由此可以看出，實用拜占庭容錯系統(tǒng)能夠容納將近1/3的拜占庭節(jié)點。
實用拜占庭容錯系統(tǒng)在很多場景都有應用，在區(qū)塊鏈應用中，一般適合于對強一致性有要求的私有鏈和聯(lián)盟鏈場景。例如，在IBM主導的區(qū)塊鏈超級賬本項目中，實用拜占庭容錯系統(tǒng)是一個可選的共識協(xié)議。
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://www.ezyhdfw.cn/yun/24192.html
摘要：課程概述本課程適合希望開發(fā)自己的專有區(qū)塊鏈的語言工程師，課程內(nèi)容如下第一章課程簡介簡單介紹的定位特點以及對于開發(fā)者而言與以太坊的區(qū)別。課程地址區(qū)塊鏈開發(fā)詳解 簡介 tendermint是一個開源的完整的區(qū)塊鏈實現(xiàn)，可以用于公鏈或聯(lián)盟鏈，其官方定位 是面向開發(fā)者的區(qū)塊鏈共識引擎： showImg(https://segmentfault.com/img/remote/1460000016...
摘要：拜占庭故障是最嚴重最難處理的。在飛機發(fā)動機系統(tǒng)核電站和幾乎所有行為取決于大量傳感器結果的系統(tǒng)都需要拜占庭容錯。前面提到的算法，只要叛徒的數(shù)量不超過將軍的三分之一，就是拜占庭容錯。 showImg(https://segmentfault.com/img/bV6WtE?w=1080&h=870);區(qū)塊鏈本質上是去中心化的系統(tǒng)，由不同的成員計算機組成，這些成員的行為取決于它們的動機和它們可...
摘要：區(qū)塊鏈系統(tǒng)首先是一個分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性共識一致性問題一致性問題是分布式領域最為基礎也是最重要的問題。算法與算法問題是指分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點的場景即可能消息丟失或重復，但無錯誤消息下的共識達成問題。 區(qū)塊鏈系統(tǒng)首先是一個分布式系統(tǒng)，分布式系統(tǒng)的核心問題包括一致性、共識 一致性問題 一致性問題是分布式領域最為基礎也是最重要的問題。如果分布式系統(tǒng)能實...
摘要：以太坊基金和以及在一起積極研究一個安全的去中心化的股權證明協(xié)議?？偨Y在本文中，我們討論了工作量證明和股權證明，它們是實現(xiàn)了拜占庭容錯的共識算法，并在當今的區(qū)塊鏈系統(tǒng)中得到實際應用。 在第一部分中，我們討論了拜占庭將軍問題、如何實現(xiàn)拜占庭容錯以及他們與區(qū)塊鏈的關系。 在上一篇文章中提到的算法實際上就是實現(xiàn)拜占庭容錯的解決方案。但是，那個解決方案還不夠有效率，它的變型也是有限制的，即不到三...
摘要：比特幣和以太幣屬于一類區(qū)塊鏈，我們將其歸類為公共無許可的區(qū)塊鏈技術。例如，在單個企業(yè)中部署時，或由受信任的權威機構運作，完全拜占庭容錯的共識可能被認為是不必要的，并且對性能和吞吐量造成過度的拖累。 介紹 一般而言，區(qū)塊鏈是一個不可變的交易分類賬，維護在一個分布式對等節(jié)點網(wǎng)絡中。這些節(jié)點通過應用已經(jīng)由共識協(xié)議驗證的交易來維護分類帳的副本，該交易被分組為包括將每個塊綁定到前一個塊的散列的塊...
閱讀 2792·2023-04-25 17:33
閱讀 809·2021-11-23 09:51
閱讀 3148·2021-07-30 15:32
閱讀 1587·2019-08-29 18:40
閱讀 2121·2019-08-28 18:19
閱讀 1613·2019-08-26 13:48
閱讀 2401·2019-08-23 16:48
閱讀 2434·2019-08-23 15:56
