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