區(qū)塊鏈原理與實踐- 課件 第4章共識層

第4章共識層課程簡介01.分布式一致性問題03.CFT類型算法詳解02.共識算法概述04.BFT類算法05.新型區(qū)塊鏈共識算法07.共識算法演進(jìn)06.目前共識機(jī)制存在的問題08.思考與練習(xí)1分布式一致性問題一分布式一致性問題分布式系統(tǒng)的特性：①資源受限：節(jié)點(diǎn)間的通信需要通過網(wǎng)絡(luò)，而網(wǎng)絡(luò)存在帶寬限制和時延，節(jié)點(diǎn)也無法做到瞬間響應(yīng)和高吞吐。②故障的獨(dú)立性：系統(tǒng)的任何一個模塊都可能發(fā)生故障，如節(jié)點(diǎn)之間的網(wǎng)絡(luò)通訊是不可靠的，隨時可能發(fā)生網(wǎng)絡(luò)故障或任意延遲；節(jié)點(diǎn)的處理可能是錯誤的，甚至節(jié)點(diǎn)自身隨時可能宕機(jī)。③不透明性：構(gòu)成分布式系統(tǒng)中任意節(jié)點(diǎn)在任意時刻的位置、性能、狀態(tài)、是否故障等信息對于其它分布式系統(tǒng)節(jié)點(diǎn)來說都是不可見的、也是無法預(yù)知的。④并發(fā)：分布式系統(tǒng)的目的是為了更好的共享資源，允許并發(fā)的訪問資源才能體現(xiàn)分布式系統(tǒng)的意義。⑤缺乏全局時鐘：當(dāng)多個程序協(xié)作時需要通過交換消息來協(xié)同彼此的動作，而緊密的協(xié)調(diào)經(jīng)常要求這些程序?qū)σ幌盗袆幼靼l(fā)生時間的共識。然而，由于網(wǎng)絡(luò)狀況的復(fù)雜性，分布式系統(tǒng)中的節(jié)點(diǎn)對網(wǎng)絡(luò)中同步時鐘的準(zhǔn)確性是很難達(dá)成共識的，即沒有一個一致的全局時間的概念。一分布式一致性問題故障類型節(jié)點(diǎn)故障：

崩潰故障（故障停止、崩潰、故障恢復(fù)）信道故障：

遺漏故障（發(fā)送故障、信道故障、接收故障）時序故障（針對同步系統(tǒng)）：

崩潰故障（時鐘故障（時鐘漂移）、節(jié)點(diǎn)性能故障(進(jìn)程執(zhí)行)、信道性能故障（消息傳遞））拜占庭故障：隨機(jī)故障（惡意、錯誤）一分布式一致性問題1.FLP不可能定理

異步系統(tǒng)中，不存在協(xié)議能夠保證所有進(jìn)程達(dá)成一致。

目前已經(jīng)證明同步通信中各節(jié)點(diǎn)保證一致性是可以達(dá)到的，但利用算法解決異步環(huán)境的一致性問題依然十分困難。即在網(wǎng)絡(luò)可靠，存在節(jié)點(diǎn)失效（即便只有一個）的最小化異步模型系統(tǒng)中，不存在一個可以解決一致性問題的確定性算法。一分布式一致性問題2.CAP定理CAP定理即描述了分布式系統(tǒng)中關(guān)于一致性和可用性的關(guān)系：一個分布式系統(tǒng)最多只能同時滿足（強(qiáng)）一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（基本要求）（Partitiontolerance）這三項要素中的兩項。一分布式一致性問題3.BASE理論BASE理論是由三個詞組組成：①BasicallyAvailable：即基本可用性，如對于存儲系統(tǒng)來說，需要保證存取服務(wù)在大多數(shù)情況下是可用的。②SoftState：柔性狀態(tài)，指為了得到更好的擴(kuò)展性，是允許中間狀態(tài)可見的，如NoSQL、MySQL集群的異步模型的數(shù)據(jù)復(fù)制過程。③EventualConsistency：最終一致性，也是分布式一致性模型中的一種弱一致性模型。要求停止往系統(tǒng)中寫入數(shù)據(jù)后，過一段時間，所有節(jié)點(diǎn)擁有了同一份數(shù)據(jù)副本。4.拜占庭將軍問題在分布式對等網(wǎng)絡(luò)中需要遵從一致的策略來協(xié)作的成員計算機(jī)即為問題中的將軍，而各成員計算機(jī)賴以進(jìn)行通訊的網(wǎng)絡(luò)鏈路即為信使。拜占庭將軍問題描述的就是某些成員計算機(jī)或網(wǎng)絡(luò)鏈路出現(xiàn)錯誤、甚至被蓄意破壞者控制的情況下成員之間存在的一致性問題。一分布式一致性問題5.區(qū)塊鏈中的DSS猜想：DSS猜想是指，在區(qū)塊鏈系統(tǒng)中，去中心化（Decentralization），安全性（Security）和可擴(kuò)展性（Scalability）這三個屬性，系統(tǒng)最多只能三選其二。1共識算法概述二共識算法概述共識算法性質(zhì)：共識算法是能使網(wǎng)絡(luò)中的各非錯誤節(jié)點(diǎn)對于交易的順序達(dá)成共識，并總能在規(guī)定時間內(nèi)對外提供輸出的算法，并且要求共識算法能保持在系統(tǒng)在不存在全球統(tǒng)一的時鐘、各節(jié)點(diǎn)可能獨(dú)立出錯以及網(wǎng)絡(luò)中傳送的消息并不總是可靠這三個條件下依然正?？煽康墓ぷ鳌１M管算法多種多樣，可以根據(jù)需要采用各種策略，但大家公認(rèn)的理想的共識算法應(yīng)該滿足的條件包括：①可終止性（Termination）：一致的結(jié)果在有限時間內(nèi)能完成。②共識性（Consensus）：不同節(jié)點(diǎn)最終完成決策的結(jié)果應(yīng)該相同。③合法性（Validity）：決策的結(jié)果必然是其它進(jìn)程提出的提案。二共識算法概述共識算法分類：共識算法可以分為CFT（CrashFaultTolerance）類和BFT（ByzantineFaultTolerance）類共識算法。CFT共識算法只保證分布式系統(tǒng)中節(jié)點(diǎn)發(fā)生宕機(jī)錯誤時整個分布式系統(tǒng)的可靠性，而當(dāng)系統(tǒng)中節(jié)點(diǎn)違反共識協(xié)議的時候?qū)o法保障分布式系統(tǒng)的可靠性.采用BFT共識算法的分布式系統(tǒng)，即使系統(tǒng)中的節(jié)點(diǎn)發(fā)生了任意類型的錯誤，只要發(fā)生錯誤的節(jié)點(diǎn)少于一定比例，整個系統(tǒng)的可靠性就可以保證。二共識算法概述共識算法評價標(biāo)準(zhǔn)：①共識算法的容錯性能，比如Raft只能支持節(jié)點(diǎn)故障錯誤。而在區(qū)塊鏈中，特別公有鏈中，由于節(jié)點(diǎn)間存在利益博弈，同時又是一個非中心化的網(wǎng)絡(luò)狀態(tài)，其共識算法必須支持節(jié)點(diǎn)作惡的容錯，所以區(qū)塊鏈的共識算法必然是BFT算法。②共識算法終局性性能，指區(qū)塊鏈網(wǎng)絡(luò)對一個候選區(qū)塊完成終局一致性所需要的時間，這決定了區(qū)塊鏈系統(tǒng)的響應(yīng)時間，對于面向用戶的去中心化應(yīng)用是非常重要的參數(shù)。③共識算法擴(kuò)展性，指隨著區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目與共識算法性能的相關(guān)關(guān)系，比如PBFT算法隨著節(jié)點(diǎn)數(shù)目增加，完成一輪共識需要在網(wǎng)絡(luò)中傳播的消息數(shù)目呈平方比例增加，因此PBFT算法的天然特性無法支持大規(guī)模網(wǎng)絡(luò)。④共識算法的網(wǎng)絡(luò)模型性能對其容錯性能和終局性能都有很大的影響。在區(qū)塊鏈大規(guī)模網(wǎng)絡(luò)條件下，同步共識算法要求所有節(jié)點(diǎn)在規(guī)定時間內(nèi)響應(yīng)對其他節(jié)點(diǎn)的消息，否則將被認(rèn)為是故障節(jié)點(diǎn)，因此受網(wǎng)絡(luò)波動影響較大，從而進(jìn)一步導(dǎo)致算法容錯性能的降低；而由于FLP不可能定理，異步共識算法無法給出確定的終局性性能，所以當(dāng)前主流區(qū)塊鏈共識算法都是基于半同步模型。3CFT類型算法詳解三CFT類型算法詳解Paxos算法：Paxos算法是一種基于消息傳遞且具有高度容錯特性的一致性算法。Paxos算法的前提假設(shè)是不存在拜占庭將軍問題，即發(fā)出的信號不會被篡改，因為Paxos算法是基于消息傳遞的。解決的問題就是在以上分布式環(huán)境下實現(xiàn)“多個進(jìn)程對某個變量的取值達(dá)成一致”。Paxos算法適用于異步網(wǎng)絡(luò)和非拜占庭的崩潰重啟（Crash-Recover）失效模型，它們具有如下特點(diǎn)：①首先進(jìn)程能夠按照程序邏輯執(zhí)行，并返回正確結(jié)果（不會是拜占庭式的任意錯誤）；②進(jìn)程處理事件的速度不可預(yù)測，甚至?xí)罎ⅲ–rash）；③進(jìn)程崩潰之后能夠重啟，并接著之前的狀態(tài)繼續(xù)提供服務(wù)；④進(jìn)程可以訪問一個不受崩潰影響的持久化存儲（即日志可以保存下來）；⑤消息傳送速度同樣不可預(yù)測，消息可能被丟失，也可能被重發(fā)，但內(nèi)容不會損壞或篡改。三CFT類型算法詳解Paxos算法流程：Paxos將系統(tǒng)中的角色分為提議者(Proposer)，決策者(Acceptor)，和最終決策學(xué)習(xí)者(Learner)，其中：①Proposer:提出提案(Proposal)。Proposal信息包括提案編號(ProposalID)和提議的值(Value)。②Acceptor：參與決策，回應(yīng)Proposers的提案。收到Proposal后可以接受提案，若Proposal獲得多數(shù)Acceptors的接受，則稱該P(yáng)roposal被批準(zhǔn)。③Learner：不參與決策，從Proposers/Acceptors學(xué)習(xí)最新達(dá)成一致的提案（Value）。Paxos有兩種類型，一種是Single-DecreePaxos，負(fù)責(zé)決策單個Value；另一種是Multi-Paxos，負(fù)責(zé)連續(xù)決策多個Value并且保證每個節(jié)點(diǎn)上的順序完全一致。下面介紹簡單的只決策一個value的Paxos算法。三CFT類型算法詳解Paxos算法流程：階段一（prepare階段）：①Proposer選擇一個提案編號N，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求Pareper（N）；②如果一個Acceptor收到一個編號為N的Prepare請求，如果小于它已經(jīng)響應(yīng)過的請求，則拒絕，不回應(yīng)或回復(fù)error。若N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請求的編號（maxN），那么它就會將它已經(jīng)接受過（已經(jīng)經(jīng)過第二階段accept的提案）的編號最大的提案作為響應(yīng)反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案。階段二（accept階段）：①如果一個Proposer收到半數(shù)以上Acceptor對其發(fā)出的編號為N的Prepare請求的響應(yīng)，那么它就會發(fā)送一個針對[N，V]提案的Accept請求給半數(shù)以上的Acceptor。注意：V就是收到的響應(yīng)中編號最大的提案的value（某個acceptor響應(yīng)的它已經(jīng)通過的{acceptN，acceptV}），如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定。②如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應(yīng)，它就接受該提案。如果N小于Acceptor之前響應(yīng)的prepare請求，則拒絕，不回應(yīng)或回復(fù)error，當(dāng)proposer沒有收到過半的回應(yīng)，那么他會重新進(jìn)入第一階段，遞增提案號，重新提出prepare請求。三CFT類型算法詳解在Paxos算法中，采用了“過半”理念，也就是少數(shù)服從多數(shù)，這使Paxos算法具有很好的容錯性。Paxos是基于消息傳遞的具有高度容錯性的分布式一致性算法。Paxos算法引入了過半的概念使算法具有了很好的容錯性，另外Paxos算法支持分布式節(jié)點(diǎn)角色之間的輪換，這極大避免了分布式單點(diǎn)的出現(xiàn)，因此Paxos算法既解決了無限等待問題，也解決了腦裂問題，是目前來說最優(yōu)秀的分布式一致性算法。三CFT類型算法詳解Raft算法：

Raft是一個用于日志復(fù)制、同步的一致性算法。它與Paxos的算法結(jié)構(gòu)不同，這使得Raft相比Paxos更好理解，并且更容易構(gòu)建實際的系統(tǒng)。為了強(qiáng)調(diào)可理解性，Raft將一致性算法分解為選主、日志復(fù)制和安全三個大模塊。Raft算法也具有如下特征：①強(qiáng)leader語義：相比其他一致性算法，Raft使用增強(qiáng)形式的leader語義。舉個例子，日志只能由leader復(fù)制給其它節(jié)點(diǎn)。這簡化了日志復(fù)制需要的管理工作，使得Raft易于理解。②leader選擇：Raft使用隨機(jī)計時器來選擇leader，它的實現(xiàn)只是在任何一致性算法中都必須實現(xiàn)的心跳機(jī)制上多做了一點(diǎn)工作，不會增加延遲和復(fù)雜性。③動態(tài)擴(kuò)容：Raft使用了一個稱為聯(lián)合共識（jointconsensus）的新機(jī)制允許集群動態(tài)在線擴(kuò)容，保障Raft的可持續(xù)服務(wù)能力。三CFT類型算法詳解在Raft協(xié)議中，任何一個節(jié)點(diǎn)任一時刻處于以下三個狀態(tài)之一：leader、follower、candidate。三CFT類型算法詳解Raft將時間分解成任意長度的時間段，這里稱作terms，如下圖所示：

三CFT類型算法詳解Raft的三個主要模塊的具體工作流程詳述如下：

①leader選舉流程 Raft使用心跳機(jī)制來觸發(fā)選舉。當(dāng)server啟動時，初始狀態(tài)都是follower。每一個server都有一個定時器，超時時間為electiontimeout，如果某server沒有超時的情況下收到來自leader或者candidate的任何RPC，定時器重啟，如果超時，它就開始一次選舉。如果某個candidate獲得了大多數(shù)人的選票，它就贏得了選舉成為新leader。每個server在某個term周期內(nèi)只能給最多一個人投票，按照先來先給的原則。新leader要給其他人發(fā)送心跳，阻止新選舉。 在等待選票過程中，一個candidate，假設(shè)為A，可能收到它人的聲稱自己是leader的AppendEntriesRPC，如果對方的term號大于等于A的，那么A承認(rèn)對方是leader，自己重新變成follower，否則，A拒絕該RPC，繼續(xù)保持candidate狀態(tài)。 在leader選舉過程中還有第三種可能性就是candidate既沒選舉成功也沒選舉失敗。如果多個followers同時成為candidate去拉選票，導(dǎo)致選票分散，任何candidate都沒拿到大多數(shù)選票，這種情況下Raft使用超時機(jī)制來解決。三CFT類型算法詳解②日志復(fù)制流程

一旦選舉出了一個leader，它就開始負(fù)責(zé)服務(wù)客戶端的請求。每個客戶端的請求都包含一個要被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。leader首先要把這個指令追加到日志中形成一個新的記錄，然后通過AppendEntriesRPCs并行的把該記錄發(fā)給其他servers，其他server如果發(fā)現(xiàn)沒問題，復(fù)制成功后會給leader一個表示成功的ACK，leader收到大多數(shù)ACK后應(yīng)用該日志，返回客戶端執(zhí)行結(jié)果。如果followers崩潰或者丟包，leader會不斷重試AppendEntriesRPC。Logs按照下圖組織：三CFT類型算法詳解在正常情形下，leader和follower的日志肯定是一致的，所以AppendEntries一致性檢查從不失敗。然而，如果leader崩潰，那么它們的日志很可能出現(xiàn)不一致。這種不一致會隨著leader或者followers的崩潰變得非常復(fù)雜。下圖展示了所有日志不一致的情形：三CFT類型算法詳解③安全性Raft選主和進(jìn)行日志復(fù)制的操作還不足以保證不同節(jié)點(diǎn)能執(zhí)行嚴(yán)格一致的指令序列，需要額外的一些安全機(jī)制。Raft的安全機(jī)制包括以下三種：選舉限制提交早期terms的entries一個leader不能也認(rèn)為一個早于當(dāng)前term的entry如果存在大多數(shù)節(jié)點(diǎn)，那么也是可以commit的。下圖展示了這樣一種狀況，一個老的log存儲在大多數(shù)節(jié)點(diǎn)上，但是仍有可能被新leader覆蓋掉，如下如所示：三CFT類型算法詳解調(diào)解過期leader為了在任何異常情況下系統(tǒng)不出錯，即滿足safety屬性，對leaderelection，logreplication兩個子問題有諸多約束。其中l(wèi)eaderelection約束包括：同一任期內(nèi)最多只能投一票，先來先得;選舉人必須比自己知道的更多（比較term，logindex）logreplication約束；一個log被復(fù)制到大多數(shù)節(jié)點(diǎn)后即被確認(rèn)，保證不會回滾；leader一定包含最新的committedlog，因此leader只會追加日志，不會刪除覆蓋日志;不同節(jié)點(diǎn)，某個位置上日志相同，那么這個位置之前的所有日志一定是相同的。4BFT類算法四BFT類算法

BFT類算法是可以允許拜占庭錯誤的一致性算法，這類算法也是在區(qū)塊鏈系統(tǒng)中常用的共識算法。根據(jù)算法采取的策略，BFT類算法可以被分為兩大類，即概率一致性算法和絕對一致性算法：概率一致性算法指在不同分布式節(jié)點(diǎn)之間，有較大概率保證節(jié)點(diǎn)間數(shù)據(jù)達(dá)到一致，但仍存在一定概率使得某些節(jié)點(diǎn)間數(shù)據(jù)不一致。對于某一個數(shù)據(jù)點(diǎn)而言，數(shù)據(jù)在節(jié)點(diǎn)間不一致的概率會隨時間的推移逐漸降低至趨近于零，從而最終達(dá)到一致性。例如工作量證明算法（ProofofWork，PoW）、權(quán)益證明算法（ProofofStake，PoS）和委托權(quán)益證明算法（DelegatedProofofStake，DPoS）都屬于概率一致性算法。絕對一致性算法指在任意時間點(diǎn)，一旦達(dá)成對某個結(jié)果的共識就不可逆轉(zhuǎn)，即共識是最終結(jié)果，節(jié)點(diǎn)之間的數(shù)據(jù)會保持絕對一致。以PBFT算法為代表的確定性系列算法即為絕對一致性算法。四BFT類算法

POW算法

工作量證明（ProofofWork，POW）算法起源于哈希現(xiàn)金（HASHCASH），最初被用于抵抗電子郵件的拒絕服務(wù)攻擊及垃圾郵件網(wǎng)關(guān)濫用。

PoW共識機(jī)制是一種簡單粗暴的共識算法，它不要求高質(zhì)量的P2P網(wǎng)絡(luò)資源，它可以為公鏈提供穩(wěn)定有效的記賬者篩選機(jī)制。同時它也面臨了挖礦中心化嚴(yán)重的問題，這也促使人們研究出了新的共識機(jī)制。

中本聰共識有四個組成部分：工作量證明、選擇出塊人、時間戳服務(wù)器以及激勵機(jī)制。通過這些機(jī)制，只要網(wǎng)絡(luò)上算力的50%以上沒有協(xié)同起來去攻擊網(wǎng)絡(luò)，那么共識就是可以達(dá)成的。四BFT類算法

POW算法工作流程

四BFT類算法

POW算法優(yōu)缺點(diǎn)PoW優(yōu)點(diǎn)：①完全去中心化；②節(jié)點(diǎn)自由進(jìn)出；③算法容易實現(xiàn)以及破壞系統(tǒng)花費(fèi)的成本巨大。PoW缺點(diǎn)：①對節(jié)點(diǎn)的性能和網(wǎng)絡(luò)環(huán)境要求高；②資源浪費(fèi)，效率低下；③礦場的出現(xiàn)違背了去中心的初衷;④不能確保最終一致性；⑤大量礦工因收益降低離開網(wǎng)絡(luò)可能導(dǎo)致網(wǎng)絡(luò)癱瘓。 四BFT類算法

POS算法

權(quán)益證明機(jī)制（ProofofStake，POS）于2012年被首次提出，是針對工作量證明機(jī)制存在的不足而設(shè)計出來的一種改進(jìn)型共識機(jī)制。權(quán)益證明機(jī)制的原理是：要求用戶證明自己擁有一定數(shù)量的數(shù)字貨幣的所有權(quán)，即“權(quán)益”。

POS中最重要的一個概念是幣齡，幣齡定義為交易的貨幣數(shù)量乘以該貨幣在錢包中儲存的時間。通俗來講，比如你有100個幣，在某個地址上9天沒有動，那么產(chǎn)生的幣齡就是900，如果你把這個地址上這100幣轉(zhuǎn)移到任意地址，包括你自己的地址，那么900個幣齡就在轉(zhuǎn)移過程中被花費(fèi)了，你的幣數(shù)量雖然還是100個，但是幣齡變更為0。幣齡在數(shù)據(jù)鏈上就可以取到，任何人都可以驗證。區(qū)塊鏈共識機(jī)制的第一步就是隨機(jī)篩選一個記賬者，PoW是通過計算能力來獲得記賬權(quán)，計算能力越強(qiáng)，獲得記賬權(quán)的概率越大。PoS則將此處的計算能力更換為財產(chǎn)證明，就是節(jié)點(diǎn)所擁有的幣齡越多，獲得的記賬的概率就越大。這有點(diǎn)像公司的股權(quán)結(jié)構(gòu)，股權(quán)占比大的合伙人話語權(quán)越重。四BFT類算法

POS算法工作流程

四BFT類算法

POS的實例Csaper協(xié)議Csaper協(xié)議為了解決因無成本利益挖礦問題，從而導(dǎo)致分叉。Csaper的具體實現(xiàn)機(jī)制如下：①驗證者押下一定比例的他們擁有的以太幣作為保證金；②然后，他們將開始驗證區(qū)塊。也就是說，當(dāng)他們發(fā)現(xiàn)一個可以他們認(rèn)為可以被加到鏈上的區(qū)塊的時候，他們將以通過押下賭注來驗證它；③如果該區(qū)塊被加到鏈上，然后驗證者們將得到一個跟他們的賭注成比例的獎勵；④但是，如果一個驗證者采用一種惡意的方式行動、試圖做“無利害關(guān)系”的事，他們將立即遭到懲罰，他們所有的權(quán)益都會被砍掉。四BFT類算法

DPoS算法

委托權(quán)益證明(DelegatedProofofStake，DPOS)是一個強(qiáng)大而靈活且具備高魯棒性的共識協(xié)議。DPOS利用利益相關(guān)方批準(zhǔn)投票的權(quán)力以公平和民主的方式解決共識問題。DPoS機(jī)制遵從如下幾條基本原則：①持股人依據(jù)所持股份行使表決權(quán)，而不是依賴挖礦競爭記賬權(quán)；②最大化持股人的盈利。③最小化維護(hù)網(wǎng)絡(luò)安全的費(fèi)用。④最大化網(wǎng)絡(luò)的效能。⑤最小化運(yùn)行網(wǎng)絡(luò)的成本，如帶寬、CPU等。四BFT類算法

DPOS算法優(yōu)缺點(diǎn)①DPoS機(jī)制相比于PoS大幅縮小參與驗證和記賬節(jié)點(diǎn)的數(shù)量，可以達(dá)到秒級的共識驗證；②在一定程度上解決拒絕服務(wù)攻擊和潛在作惡節(jié)點(diǎn)聯(lián)合作惡問題；③但是，DPoS機(jī)制還是依賴于代幣，然而很多商業(yè)應(yīng)用是不需要代幣存在的；④另外，DPoS并沒有解決首富作惡的問題。 四BFT類算法

實用拜占庭容錯協(xié)議在借鑒了分布式系統(tǒng)的狀態(tài)機(jī)復(fù)制和分布式一致算法quorum的基礎(chǔ)上設(shè)計了三階段協(xié)議來解決一致性問題，同時引入了優(yōu)化項，算法的復(fù)雜度由原來的指數(shù)級降低為多項式級別。PBFT算法本質(zhì)上是一個狀態(tài)機(jī)復(fù)制算法，能夠用于實現(xiàn)帶有狀態(tài)和特定操作的任意確定性狀態(tài)復(fù)制服務(wù)，它的目的是讓所有的可信節(jié)點(diǎn)執(zhí)行相同的序列。此外，PBFT算法使用安全的哈希函數(shù)對消息做摘要、使用公私鑰對消息進(jìn)行簽名和驗簽、同時增加了消息驗證碼，保證了消息的完整性和不可篡改性。在作惡節(jié)點(diǎn)總數(shù)不超過系統(tǒng)節(jié)點(diǎn)總數(shù)的1/3的情況下，PBFT算法能夠保證系統(tǒng)的安全性和活性。PBFT算法主要包含三類基本協(xié)議：①三階段協(xié)議：解決如何達(dá)成共識；②檢查點(diǎn)協(xié)議：類似于操作系統(tǒng)的還原點(diǎn)，主要用于垃圾回收；③視圖變更協(xié)議：用于解決主節(jié)點(diǎn)失效下不工作的情況。

四BFT類算法

三階段協(xié)議三階段協(xié)議是PBFT算法的核心流程，用于解決系統(tǒng)的一致性問題，保證所有可信節(jié)點(diǎn)在給定狀態(tài)和參數(shù)組的條件下，按照相同的順序執(zhí)行完請求后能夠取得相同的狀態(tài)。pre-prepare階段：四BFT類算法

三階段協(xié)議prepare階段：四BFT類算法

三階段協(xié)議commit階段：四BFT類算法

檢查點(diǎn)協(xié)議PBFT通過三階段協(xié)議來對請求達(dá)成共識，但是各個階段產(chǎn)生的消息如果不進(jìn)行垃圾回收的話，系統(tǒng)的存儲資源將會不堪重負(fù)。為此，PBFT算法設(shè)計了檢查點(diǎn)協(xié)議來丟棄本地的消息日志文件中的舊消息。四BFT類算法

視圖變更協(xié)議PBFT算法可以通過視圖變更協(xié)議來允許系統(tǒng)在主節(jié)點(diǎn)出故障的情況下仍能夠正常運(yùn)轉(zhuǎn)，從而保證了系統(tǒng)的活性。視圖變更協(xié)議實際上是通過超時機(jī)制觸發(fā)的，通過超時機(jī)制可以避免主節(jié)點(diǎn)不工作時副節(jié)點(diǎn)無限期等待客戶端請求被執(zhí)行的情況。a.維持計時器：副節(jié)點(diǎn)會針對視圖v維持一個計時器。當(dāng)在收到主節(jié)點(diǎn)發(fā)送過來的一個有效的請求而且沒有執(zhí)行的時候，如果是針對當(dāng)前視圖的計時器還沒有啟動的話，那么節(jié)點(diǎn)會啟動一個新的計時器。如果節(jié)點(diǎn)還在執(zhí)行其他請求的話，那么節(jié)點(diǎn)會重置該請求的計時器。如果節(jié)點(diǎn)不再等待執(zhí)行該請求的時候，會停止視圖v的計時器。四BFT類算法

視圖變更協(xié)議b.請求視圖變更四BFT類算法

視圖變更協(xié)議c.切換到新視圖5新型區(qū)塊鏈共識算法五新型區(qū)塊鏈共識算法

Algorand算法針對BFT算法在區(qū)塊鏈的去中心化、可擴(kuò)展性和安全存在的問題，Algorand算法被提出。下面我們來說說Algorand算法的幾個特點(diǎn)：①為了避免委員會暴露之后被攻擊者攻擊，Algorand要求所有委員會節(jié)點(diǎn)在這一輪投票完便失效，下一輪的委員會成員會重新選擇。②這個權(quán)重還決定了節(jié)點(diǎn)被當(dāng)選為委員會成員的概率，權(quán)重越大的節(jié)點(diǎn)，其被選中的概率越大。五新型區(qū)塊鏈共識算法

Algorand算法交易流程五新型區(qū)塊鏈共識算法

DAG共識DAG算法可以細(xì)分為兩類：一個是將區(qū)塊組織成DAG，如conflux共識；另外一個是不保留區(qū)塊的概念，而是直接將交易組織成DAG，如物聯(lián)網(wǎng)區(qū)塊鏈平臺IOTA的tangle算法。DAG共識的一個難點(diǎn)是如何對區(qū)塊或者交易進(jìn)行排序，下面我們會分別介紹基于交易和區(qū)塊的DAG共識機(jī)制是如何解決交易排序的問題的。五新型區(qū)塊鏈共識算法

DAG區(qū)塊共識Conflux共識是DAG共識的一種，它們都是將區(qū)塊組織成有向無環(huán)圖DAG，都是基于比特幣共識來解決POW問題來產(chǎn)生區(qū)塊的。五新型區(qū)塊鏈共識算法

DAG交易共識Tangle是應(yīng)用于物聯(lián)網(wǎng)IOT的共識算法，目的是想解決傳統(tǒng)的區(qū)塊鏈中需要交易手續(xù)費(fèi)問題，因為IOT世界中發(fā)生的大多數(shù)是小額支付，如果直接采用以比特幣為代表的區(qū)塊鏈解決方案的話，每筆小額支付交易的手續(xù)費(fèi)明顯高于交易的轉(zhuǎn)賬金額，那么這個明顯是不合理的。但是去掉手續(xù)費(fèi)的話，區(qū)塊的產(chǎn)生就會出現(xiàn)問題，因為沒有手續(xù)費(fèi)，礦工創(chuàng)建區(qū)塊就沒有利益所得。五新型區(qū)塊鏈共識算法

基于可信硬件的共識算法PoET（逝去時間證明）的工作機(jī)制如下：網(wǎng)絡(luò)中的每位參與節(jié)點(diǎn)都必須等待一個隨機(jī)選取的時期，首個完成設(shè)定等待時間的節(jié)點(diǎn)將獲得一個新區(qū)塊。區(qū)塊鏈網(wǎng)絡(luò)中的每個節(jié)點(diǎn)會生成一個隨機(jī)的等待時間，并休眠一個設(shè)定的時間。最先醒來的節(jié)點(diǎn)，即具有最短等待時間的節(jié)點(diǎn)，喚醒并向區(qū)塊鏈提交一個新區(qū)塊，然后廣播必要的信息到整個對等網(wǎng)絡(luò)中。同一過程將會重復(fù)，以發(fā)現(xiàn)下一個區(qū)塊。TrustZone在概念上將SoC的硬件和軟件資源劃分為安全（SecureWorld）和非安全（NormalWorld）兩個世界，所有需要保密的操作在安全世界執(zhí)行（如指紋識別、密碼處理、數(shù)據(jù)加解密、安全認(rèn)證等），其余操作在非安全世界執(zhí)行（如用戶操作系統(tǒng)、各種應(yīng)用程序等），安全世界和非安全世界通過一個名為MonitorMode的模式進(jìn)行轉(zhuǎn)換，如圖所示6目前共識機(jī)制存在的問題六目前共識機(jī)制存在的問題

1.安全性證明不完備共識機(jī)制在安全性建模時需要考慮網(wǎng)絡(luò)時序性、節(jié)點(diǎn)數(shù)量拓展、在線離線切換、算力或權(quán)益的動態(tài)分布、共識難度變更、區(qū)塊鏈增長速率等多變量因素。2.安全性假設(shè)不可靠現(xiàn)代密碼體制的安全性評估依賴計算復(fù)雜性理論，常用可證明安全理論將密碼體制的安全性歸約到某個公開的數(shù)學(xué)困難問題上，如橢圓曲線上的離散對數(shù)問題。然而，采用PoW和PoS的共識機(jī)制的安全性假設(shè)并不依賴計算困難問題，而是依賴所有的誠實節(jié)點(diǎn)所擁有的算力或者權(quán)益占多數(shù)這類看似合理的假設(shè)。這些安全性假設(shè)在實際應(yīng)用中很容易被打破。3.一致性不穩(wěn)定如何保證共識機(jī)制可以持續(xù)穩(wěn)定地實現(xiàn)一致性是目前共識層的研究重點(diǎn)。一致性是衡量共識機(jī)制安全性強(qiáng)弱的重要性質(zhì)。這些合法交易的交易雙方造成利益損失。六目前共識機(jī)制存在的問題

4.擴(kuò)展性差可擴(kuò)展性是區(qū)塊鏈共識機(jī)制研究關(guān)注的重要屬性，是區(qū)塊鏈可用性必不可少的一部分。目前，如何提高區(qū)塊鏈共識機(jī)制的可擴(kuò)展性仍然是一個主流研究方向。5.初始化難問題大量研究關(guān)注共識機(jī)制實現(xiàn)一致性的過程，往往忽略了區(qū)塊鏈的初始化問題，即如何在P2P網(wǎng)絡(luò)中保證創(chuàng)世塊的安全生成。區(qū)塊鏈的初始化直接關(guān)系到后續(xù)共識機(jī)制的執(zhí)行過程是否安全可靠，是保證共識機(jī)制穩(wěn)定可靠的前提。區(qū)塊鏈一直面臨初始化困難的問題。6.重構(gòu)困難問題共識機(jī)制賦予了區(qū)塊鏈不可篡改性，提升了系統(tǒng)的可信度，但是也增加了