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

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

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

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

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

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

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

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

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

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

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

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

POW算法

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

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

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

POW算法工作流程

四BFT類算法

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

POS算法

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

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

POS算法工作流程

四BFT類算法

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

DPoS算法

委托權(quán)益證明(DelegatedProofofStake，DPOS)是一個(gè)強(qiáng)大而靈活且具備高魯棒性的共識(shí)協(xié)議。DPOS利用利益相關(guān)方批準(zhǔn)投票的權(quán)力以公平和民主的方式解決共識(shí)問(wèn)題。DPoS機(jī)制遵從如下幾條基本原則：①持股人依據(jù)所持股份行使表決權(quán)，而不是依賴挖礦競(jìng)爭(zhēng)記賬權(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大幅縮小參與驗(yàn)證和記賬節(jié)點(diǎn)的數(shù)量，可以達(dá)到秒級(jí)的共識(shí)驗(yàn)證；②在一定程度上解決拒絕服務(wù)攻擊和潛在作惡節(jié)點(diǎn)聯(lián)合作惡?jiǎn)栴}；③但是，DPoS機(jī)制還是依賴于代幣，然而很多商業(yè)應(yīng)用是不需要代幣存在的；④另外，DPoS并沒(méi)有解決首富作惡的問(wèn)題。 四BFT類算法

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

四BFT類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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