【搜集了CSDN的很多篇文章整理的】

共識機(jī)制

布式一致性 (distributed consensus) 是分布式系統(tǒng)中最基本的問題，用來保證一個分布式系統(tǒng)的可靠性以及容錯能力。簡單來說，分布式一致性是指多個服務(wù)器的保持狀態(tài)一致。

在分布式系統(tǒng)中，可能出現(xiàn)各種意外（斷電、網(wǎng)絡(luò)擁塞、CPU/內(nèi)存耗盡等等），使得服務(wù)器宕機(jī)或無法訪問，最終導(dǎo)致無法和其他服務(wù)器保持狀態(tài)一致。為了應(yīng)對這種情況，就需要有一種一致性協(xié)議來進(jìn)行容錯，使得分布式系統(tǒng)中即使有部分服務(wù)器宕機(jī)或無法訪問，整體依然可以對外提供服務(wù)。

復(fù)制狀態(tài)機(jī)

復(fù)制狀態(tài)機(jī)（Replicated State Machines）是指一組服務(wù)器上的狀態(tài)機(jī)產(chǎn)生相同狀態(tài)的副本，并且在一些機(jī)器宕掉的情況下也可以繼續(xù)運(yùn)行。一致性算法管理著來自客戶端指令的復(fù)制日志。狀態(tài)機(jī)從日志中處理相同順序的相同指令，所以產(chǎn)生的結(jié)果也是相同的。

復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的。每一個服務(wù)器存儲一個包含一系列指令的日志，并且按照日志的順序進(jìn)行執(zhí)行。每一個日志都按照相同的順序包含相同的指令，所以每一個服務(wù)器都執(zhí)行相同的指令序列。因?yàn)?strong>每個狀態(tài)機(jī)都是確定的，每一次執(zhí)行操作都產(chǎn)生相同的狀態(tài)和同樣的序列。

保證復(fù)制日志相同就是一致性算法的工作了。在一臺服務(wù)器上，一致性模塊接收客戶端發(fā)送來的指令然后增加到自己的日志中去。它和其他服務(wù)器上的一致性模塊進(jìn)行通信來保證每一個服務(wù)器上的日志最終都以相同的順序包含相同的請求，盡管有些服務(wù)器會宕機(jī)。一旦指令被正確的復(fù)制，每一個服務(wù)器的狀態(tài)機(jī)按照日志順序處理他們，然后輸出結(jié)果被返回給客戶端。因此，服務(wù)器集群看起來形成一個高可靠的狀態(tài)機(jī)。

?

實(shí)際系統(tǒng)中使用的一致性算法通常含有以下特性：

①安全性保證（絕對不會返回一個錯誤的結(jié)果）：在非拜占庭錯誤情況下，包括網(wǎng)絡(luò)延遲、分區(qū)、丟包、冗余和亂序等錯誤都可以保證正確。

②可用性：集群中只要有大多數(shù)的機(jī)器可運(yùn)行并且能夠相互通信、和客戶端通信，就可以保證可用。

③不依賴時序來保證一致性：物理時鐘錯誤或者極端的消息延遲只有在最壞情況下才會導(dǎo)致可用性問題。

通常情況下，一條指令可以盡可能快的在集群中大多數(shù)節(jié)點(diǎn)響應(yīng)一輪遠(yuǎn)程過程調(diào)用時完成。小部分比較慢的節(jié)點(diǎn)不會影響系統(tǒng)整體的性能。

?

一、Raft

Raft算法是目前使用最廣泛的非拜占庭容錯類共識算法。Raft算法主要依靠投票機(jī)制和日志復(fù)制機(jī)制來實(shí)現(xiàn)節(jié)點(diǎn)間的共識。節(jié)點(diǎn)通過投票選出一個leader，由leader負(fù)責(zé)處理所有請求，再將請求以日志的方式復(fù)制到其他節(jié)點(diǎn)。

Raft保證了在一個由N個節(jié)點(diǎn)構(gòu)成的系統(tǒng)中有(N+1)/2（向上取整）個節(jié)點(diǎn)正常工作的情況下的系統(tǒng)的一致性。

?

Raft 是一種為了管理日志復(fù)制的分布式一致性算法。Raft出現(xiàn)之前，Paxos一直是分布式一致性算法的標(biāo)準(zhǔn)。Paxos難以理解，更難以實(shí)現(xiàn)。Raft的設(shè)計目標(biāo)是簡化Paxos。

Raft 可以解決分布式 CAP 理論中的CP，即一致性（C：Consistency）和分區(qū)容忍性（P：Partition Tolerance），并不能解決可用性（A：Availability）的問題。

?

1、身份

每個網(wǎng)絡(luò)節(jié)點(diǎn)只能如下三種身份之一：Leader、Follower以及Candidate。

Leader：主要負(fù)責(zé)與外界交互，由Follower節(jié)點(diǎn)選舉，在每一次共識過程中有且僅有一個Leader節(jié)點(diǎn)，由Leader全權(quán)負(fù)責(zé)從交易池中取出交易、打包交易組成區(qū)塊并將區(qū)塊上鏈；

Follower：以Leader節(jié)點(diǎn)為準(zhǔn)進(jìn)行同步，并在Leader節(jié)點(diǎn)失效時舉行選舉以選出新的Leader節(jié)點(diǎn)；

Candidate：Follower節(jié)點(diǎn)在競選Leader時擁有的臨時身份。

?

2、任期

Raft算法將時間劃分為不定長度的任期Terms，Terms為連續(xù)的數(shù)字。每個Term以選舉開始，如果選舉成功，則由當(dāng)前l(fā)eader負(fù)責(zé)出塊，如果選舉失敗，并沒有選舉出新的單一Leader，則會開啟新的Term，重新開始選舉。

?

3、PRC

Raft 算法中服務(wù)器節(jié)點(diǎn)之間通信使用遠(yuǎn)程過程調(diào)用（RPC），并且基本的一致性算法只需要兩種類型的 RPC，為了在服務(wù)器之間傳輸快照增加了第三種 RPC。

【RPC有三種】：

RequestVote RPC：候選人在選舉期間發(fā)起。

AppendEntries RPC：領(lǐng)導(dǎo)人發(fā)起的一種心跳機(jī)制，復(fù)制日志也在該命令中完成。

InstallSnapshot RPC: 領(lǐng)導(dǎo)者使用該RPC來發(fā)送快照給太落后的追隨者。

?

4、leader 選舉

Raft共識模塊中使用心跳機(jī)制來觸發(fā)Leader選舉。當(dāng)節(jié)點(diǎn)啟動時，節(jié)點(diǎn)自動成為Follower且將Term置0。只要Follower從Leader或者Candidate收到有效的Heartbeat或RequestVote消息，其就會保持在Follower狀態(tài)，如果Follower在一段時間內(nèi)（這段時間稱為 Election Timeout）沒收到上述消息，則它會假設(shè)系統(tǒng)當(dāng)前的Leader已經(jīng)失活，然后增加自己的Term并轉(zhuǎn)換為Candidiate，開啟新一輪的Leader選舉流程，流程如下:

（1）Follower增加當(dāng)前的Term，轉(zhuǎn)換為Candidate；

（2）Candidate將票投給自己，并廣播RequestVote到其他節(jié)點(diǎn)請求投票；

（3）Candidate節(jié)點(diǎn)保持在Candidate狀態(tài)，直到下面三種情況中的一種發(fā)生：

①該節(jié)點(diǎn)贏得選舉，即獲得了超過半數(shù)以上的服務(wù)器投票，成為 Leader；

②在等待選舉期間，Candidate收到了其他節(jié)點(diǎn)的Heartbeat，有其他節(jié)點(diǎn)獲得了半數(shù)以上的投票；

③經(jīng)過Election Timeout后，沒有Leader被選出。

Raft算法采用隨機(jī)定時器的方法來避免節(jié)點(diǎn)選票出現(xiàn)平均瓜分的情況以保證大多數(shù)時候只會有一個節(jié)點(diǎn)超時進(jìn)入Candidate狀態(tài)并獲得大部分節(jié)點(diǎn)的投票成為Leader。

?

4.1投票流程

節(jié)點(diǎn)在收到VoteReq消息后，會根據(jù)消息的內(nèi)容選擇不同的響應(yīng)策略：

（1）VoteReq的Term小于或等于自己的Term

①如果節(jié)點(diǎn)是Leader，則拒絕該投票請求，Candidate收到此響應(yīng)【拒絕】后會放棄選舉轉(zhuǎn)變?yōu)镕ollower，并增加投票超時；

②如果節(jié)點(diǎn)不是Leader：

若＜，則拒絕該投票請求，如果Candidate收到超過半數(shù)的該種響應(yīng)（被拒絕）則表明其已經(jīng)過時，此時Candidate會放棄選舉轉(zhuǎn)變?yōu)镕ollower，并增加投票超時；

若＝，則拒絕該投票請求，對于該投票請求不作任何處理。對于每個節(jié)點(diǎn)而言，只能按照先到先得的原則投票給一個Candidate，從而保證每輪選舉中至多只有一個Candidate被選為Leader。

?

（2）VoteReq的lastLeaderTerm小于自己的lastLeaderTerm

每個節(jié)點(diǎn)中會有一個lastLeaderTerm字段表示該節(jié)點(diǎn)見過的最后一個Leader的Term，lastLeaderTerm僅能由Heartbeat進(jìn)行更新。如果VoteReq中的lastLeaderTerm小于自己的lastLeaderTerm，表明Leader訪問這個Candidate存在問題，如果此時Candidate處于網(wǎng)絡(luò)孤島的環(huán)境中，會不斷向外提起投票請求，因此需要打斷它的投票請求，所以此時節(jié)點(diǎn)會拒絕該投票請求。

?

（3）VoteReq的lastBlockNumber小于自己的lastBlockNumber

每個節(jié)點(diǎn)中會有一個lastBlockNumber字段表示節(jié)點(diǎn)見到過的最新塊的塊高。在出塊過程中，節(jié)點(diǎn)間會進(jìn)行區(qū)塊復(fù)制，在區(qū)塊復(fù)制的過程中，可能有部分節(jié)點(diǎn)收到了較新的區(qū)塊數(shù)據(jù)而部分沒有，從而導(dǎo)致不同節(jié)點(diǎn)的lastBlockNumber不一致。為了使系統(tǒng)能夠達(dá)成一致，需要要求節(jié)點(diǎn)必須把票投給擁有較新數(shù)據(jù)的節(jié)點(diǎn)，因此在這種情況下節(jié)點(diǎn)會拒絕該投票請求。

?

（4）節(jié)點(diǎn)是第一次投票

為了避免出現(xiàn)Follower因?yàn)榫W(wǎng)絡(luò)抖動導(dǎo)致重新發(fā)起選舉，規(guī)定如果節(jié)點(diǎn)是第一次投票，直接拒絕該投票請求，同時會將自己的firstVote字段置為該Candidate的節(jié)點(diǎn)索引。

?

（5）1~4步驟中都沒有拒絕投票請求

同意該投票請求。

?

4.2 心跳超時

在Leader成為網(wǎng)絡(luò)孤島時，Leader可以發(fā)出心跳、Follower可以收到心跳但是Leader收不到心跳回應(yīng)，這種情況下Leader此時已經(jīng)出現(xiàn)網(wǎng)絡(luò)異常，但是由于一直可以向外發(fā)送心跳包會導(dǎo)致Follower無法切換狀態(tài)進(jìn)行選取，系統(tǒng)陷入停滯。為了避免第二種情況發(fā)生，模塊中設(shè)置了心跳超時機(jī)制，Leader每次收到心跳回應(yīng)時會進(jìn)行相應(yīng)記錄，一旦一段時間后記錄沒有更新則Leader放棄Leader身份并轉(zhuǎn)換為Follower節(jié)點(diǎn)。

?

5、Leader選舉的限制

Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)的可用性來確保集群數(shù)據(jù)的一致性。所有的日志條目都只會從Leader節(jié)點(diǎn)往Follower節(jié)點(diǎn)寫入，且Leader節(jié)點(diǎn)上的日志只會增加，絕對不會刪除或者覆蓋。

這意味著Leader節(jié)點(diǎn)必須包含所有已經(jīng)提交的日志，即能被選舉為Leader的節(jié)點(diǎn)一定需要包含所有的已經(jīng)提交的日志【Leader選舉的限制】。因?yàn)槿罩局粫腖eader向Follower傳輸，所以如果被選舉出的Leader缺少已經(jīng)Commit的日志，那么這些已經(jīng)提交的日志就會丟失，顯然這是不符合要求的。

?

6、日志復(fù)制（保證數(shù)據(jù)一致性）

6.1 日志復(fù)制的過程

當(dāng)Client向集群Leader節(jié)點(diǎn)提交數(shù)據(jù)后，Leader節(jié)點(diǎn)接收到的數(shù)據(jù)處于未提交狀態(tài)，

接著Leader節(jié)點(diǎn)會并發(fā)向所有Follower節(jié)點(diǎn)復(fù)制數(shù)據(jù)并等待接收響應(yīng)，確保至少集群中超過半數(shù)節(jié)點(diǎn)已接收到數(shù)據(jù)后再向 Client 確認(rèn)數(shù)據(jù)已接收。一旦向Client發(fā)出數(shù)據(jù)接收Ack響應(yīng)后，表明此時數(shù)據(jù)狀態(tài)進(jìn)入已提交（Committed），Leader節(jié)點(diǎn)再向Follower節(jié)點(diǎn)發(fā)通知告知該數(shù)據(jù)狀態(tài)已提交。

?

leader接受客戶端的請求 → 作為日志條目（Log entries）加入自己的日志中 → 并行向其他服務(wù)器發(fā)起AppendEntries?PRC復(fù)制日志條目 → 被大多是服務(wù)器復(fù)制 → leader將日志應(yīng)用到自己的狀態(tài)機(jī)上，并向客戶端返回執(zhí)行結(jié)果。

①客戶端的每一個請求都包含被復(fù)制狀態(tài)機(jī)執(zhí)行的指令。

②leader把這個指令作為一條新的日志條目添加到日志中，然后并行發(fā)起 RPC 給其他的服務(wù)器，讓他們復(fù)制這條信息。

③假如這條日志被安全的復(fù)制，領(lǐng)導(dǎo)人就應(yīng)用這條日志到自己的狀態(tài)機(jī)中，并返回給客戶端。

④如果follower宕機(jī)/運(yùn)行緩慢/丟包，leader會不斷的重試，直到所有的follower最終都復(fù)制了所有的日志條目。

?leader選舉的過程是：①增加term號；②給自己投票；③重置選舉超時計時器；④發(fā)送請求投票的RPC給其它節(jié)點(diǎn)。

?

6.2 日志的組成

日志由有序編號（log index）的日志條目組成。每個日志條目包含它被創(chuàng)建時的任期號（term）和用于狀態(tài)機(jī)執(zhí)行的命令。如果一個日志條目被復(fù)制到大多數(shù)服務(wù)器上，就被認(rèn)為可以提交（commit）了。

上圖顯示，共有 8 條日志，提交了 7 條。提交的日志都將通過狀態(tài)機(jī)持久化到磁盤中，防止宕機(jī)。

?

6.3 日志的一致性

（1）日志復(fù)制的兩條保證

如果不同日志中的兩個條目有著相同的索引和任期號，則它們

①所存儲的命令是相同的（原因：leader 最多在一個任期里的一個日志索引位置創(chuàng)建一條日志條目，日志條目在日志的位置從來不會改變）。

②之前的所有條目都是完全一樣的（原因：每次RPC發(fā)送附加日志時，leader會把這條日志條目的前面的日志的下標(biāo)和任期號一起發(fā)送給 follower，如果?follower 發(fā)現(xiàn)和自己的日志不匹配，那么就拒絕接受這條日志，這個稱之為一致性檢查）。

?

（2）日志的不正常情況

一般情況下，Leader和Followers的日志保持一致，因此AppendEntries一致性檢查通常不會失敗。然而，Leader崩潰可能會導(dǎo)致日志不一致：舊的Leader可能沒有完全復(fù)制完日志中的所有條目。

下圖闡述了一些Followers可能和新的Leader日志不同的情況。一個Follower可能會丟失掉Leader上的一些條目，也有可能包含一些Leader沒有的條目，也有可能兩者都會發(fā)生。丟失的或者多出來的條目可能會持續(xù)多個任期。

Leader通過強(qiáng)制Followers復(fù)制它的日志來處理日志的不一致，F(xiàn)ollowers上的不一致的日志會被Leader的日志覆蓋。

Leader會從后往前試，每次AppendEntries失敗后嘗試前一個日志條目，直到成功找到每個Follower的日志一致位置點(diǎn)（基于上述的兩條保證），然后向后逐條覆蓋Followers在該位置之后的條目。這樣就實(shí)現(xiàn)了主從日志的一致性。

?

7、安全性

Raft增加了如下兩條限制以保證安全性：

①擁有最新的已提交的log entry的Follower才有資格成為leader。

②Leader只能推進(jìn)commit index來提交當(dāng)前term的已經(jīng)復(fù)制到大多數(shù)服務(wù)器上的日志，舊term日志的提交要等到提交當(dāng)前term的日志來間接提交（log index小于commit index的日志被間接提交）。

?上圖：解釋了為什么 Leader 無法對舊 Term 的日志條目進(jìn)行提交。

(a)：S1是Leader，且S1寫入日志條目為 (Term 2，日志索引 2），只有S2復(fù)制了這個日志條目。

(b)：S1下線，S5被選舉為Term3的Leader。S5 寫入日志條目為 (Term 3，日志索引 2）。

(c)：S5下線，S1被選舉為 Term4 的 Leader。此時，Term 2的那條日志條目已經(jīng)被復(fù)制到了集群中的大多數(shù)節(jié)點(diǎn)上，但是還沒有被提交。

(d)：S1下線，S5被重新選舉為 Term3 的 Leader。然后S5覆蓋了日志索引2處的日志。

(e)：若?(d) 還未發(fā)生，即S1再次下線之前，S1把自己主導(dǎo)的日志條目復(fù)制到了大多數(shù)節(jié)點(diǎn)上，則后續(xù)Term里這些新日志條目就會被提交。這樣在同一時刻就同時保證了之前的所有舊日志條目就會被提交。

?

8、日志壓縮

在實(shí)際的系統(tǒng)中，不能讓日志無限增長，否則系統(tǒng)重啟時需要花很長的時間進(jìn)行回放，從而影響可用性。Raft采用對整個系統(tǒng)進(jìn)行snapshot來解決，snapshot之前的日志都可以丟棄（以前的數(shù)據(jù)已經(jīng)落盤了）。

每個副本獨(dú)立的對自己的系統(tǒng)狀態(tài)進(jìn)行snapshot，并且只能對已經(jīng)提交的日志記錄進(jìn)行snapshot。

【Snapshot中包含以下內(nèi)容】：

①日志元數(shù)據(jù)，最后一條已提交的log entry的log index和term。這兩個值在snapshot之后的第一條log entry的AppendEntries RPC的完整性檢查的時候會被用上。

②系統(tǒng)當(dāng)前狀態(tài)。

?

當(dāng)Leader要發(fā)給某個日志落后太多的Follower的log entry被丟棄，Leader會將snapshot發(fā)給Follower。或者當(dāng)新加進(jìn)一臺機(jī)器時，也會發(fā)送snapshot給它。發(fā)送snapshot使用InstalledSnapshot RPC。

推薦當(dāng)日志達(dá)到某個固定的大小做一次snapshot。

①太頻繁，消耗磁盤帶寬；

②太不頻繁，節(jié)點(diǎn)重啟需要回放大量日志，影響可用性。??

做一次snapshot可能耗時過長，會影響正常日志同步?？梢酝ㄟ^使用copy-on-write技術(shù)避免snapshot過程影響正常日志同步。

?

9、成員變更

9.1 常規(guī)處理成員變更存在的問題

我們先將成員變更請求當(dāng)成普通的寫請求，由領(lǐng)導(dǎo)者得到多數(shù)節(jié)點(diǎn)響應(yīng)后，每個節(jié)點(diǎn)提交成員變更日志，將從舊成員配置（Cold）切換到新成員配置（Cnew）。但每個節(jié)點(diǎn)提交成員變更日志的時刻可能不同，這將造成各個服務(wù)器切換配置的時刻也不同，這就有可能選出兩個領(lǐng)導(dǎo)者，破壞安全性。

考慮以下這種情況：集群配額從3臺機(jī)器變成了5臺，可能存在這樣的一個時間點(diǎn)，兩個不同的領(lǐng)導(dǎo)者在同一個任期里都可以被選舉成功（雙主問題），一個是通過舊的配置，一個通過新的配置。

簡而言之，成員變更存在的問題是增加或者減少的成員太多了，導(dǎo)致舊成員組和新成員組沒有交集，因此出現(xiàn)了雙主。

?

9.2 解決方案之一階段成員變更

Raft解決方法是每次成員變更只允許增加或刪除一個成員（如果要變更多個成員，連續(xù)變更多次）。

10、問題

①Raft主要是分為leader選舉、日志復(fù)制、日志壓縮、成員變更等。

?

②Raft網(wǎng)絡(luò)分區(qū)下的數(shù)據(jù)一致性怎么解決？

發(fā)生了網(wǎng)絡(luò)分區(qū)或者網(wǎng)絡(luò)通信故障，使得Leader不能訪問大多數(shù)Follwer了，那么Leader只能正常更新它能訪問的那些Follower，而大多數(shù)的Follower因?yàn)闆]有了Leader，他們重新選出一個Leader，然后這個 Leader來接受客戶端的請求，如果客戶端要求其添加新的日志，這個新的Leader會通知大多數(shù)Follower。如果這時網(wǎng)絡(luò)故障修復(fù)了，原先的Leader就變成Follower，在失聯(lián)階段這個老Leader的任何更新都不能算commit，都回滾，接受新的Leader的新的更新（遞減查詢匹配日志）。

③Raft和Paxos的區(qū)別和優(yōu)缺點(diǎn)？

Raft的leader有限制，擁有最新日志的節(jié)點(diǎn)才能成為leader，multi-paxos中對成為Leader的限制比較低，任何節(jié)點(diǎn)都可以成為leader。

Raft中Leader在每一個任期都有Term號。

?

④Raft prevote機(jī)制？
??Prevote（預(yù)投票）是一個類似于兩階段提交的協(xié)議，第一階段先征求其他節(jié)點(diǎn)是否同意選舉，如果同意選舉則發(fā)起真正的選舉操作，否則降為Follower角色。這樣就避免了網(wǎng)絡(luò)分區(qū)節(jié)點(diǎn)重新加入集群，觸發(fā)不必要的選舉操作。

?

⑤Raft里面怎么保證數(shù)據(jù)被commit，leader宕機(jī)了會怎樣，之前的沒提交的數(shù)據(jù)會怎樣？

leader會通過RPC向follower發(fā)出日志復(fù)制，等待所有的follower復(fù)制完成，這個過程是阻塞的。

老的leader里面沒提交的數(shù)據(jù)會回滾，然后同步新leader的數(shù)據(jù)。

?

⑥Raft里面的lease機(jī)制是什么，有什么作用？

租約機(jī)制確保了一個時刻最多只有一個leader，避免只使用心跳機(jī)制產(chǎn)生雙主的問題。中心思想是每次租約時長內(nèi)只有一個節(jié)點(diǎn)獲得租約、到期后必須重新頒發(fā)租約。

?假設(shè)我們有租約頒發(fā)節(jié)點(diǎn)Z，節(jié)點(diǎn)0、1和z競選leader，租約過程如下:

(a).節(jié)點(diǎn)0、1、2在Z上注冊自己，Z根據(jù)一定的規(guī)則(例如先到先得)頒發(fā)租約給節(jié)點(diǎn)，該租約同時對應(yīng)一個有效時長；這里假設(shè)節(jié)點(diǎn)0獲得租約、成為leader

(b).leader宕機(jī)時，只有租約到期(timeout)后才重新發(fā)起選舉，這里節(jié)點(diǎn)1獲得租約、成為leader

?

?

二、PBFT

結(jié)論：時間復(fù)雜度是O(n^2)，可解決拜占庭問題。PBFT算法可以容忍小于1/3個無效或者惡意節(jié)點(diǎn)。如果系統(tǒng)內(nèi)有n臺機(jī)子，那么系統(tǒng)最多能容忍的作惡/故障節(jié)點(diǎn)為(n-1)/3個。系統(tǒng)的總節(jié)點(diǎn)數(shù)為：|R| = 3f + 1。

優(yōu)點(diǎn)： 算法的可靠性有嚴(yán)格的數(shù)學(xué)證明，具備（n-1)/3容錯性。

缺點(diǎn)：當(dāng)有1/3或以上記賬人停止工作后，系統(tǒng)將無法提供服務(wù)。

?

證明過程：我們知道有f個作惡節(jié)點(diǎn)，且無法預(yù)測這f個作惡節(jié)點(diǎn)做了什么（錯誤消息/不發(fā)送），并不知道這n-f個里面有幾個是作惡節(jié)點(diǎn)，我們必須保證正常的節(jié)點(diǎn)大于作惡節(jié)點(diǎn)數(shù)。所以有 n-f-f > f，從而得出了n > 3f。

?

主節(jié)點(diǎn)確定機(jī)制：主節(jié)點(diǎn)通過視圖編號以及節(jié)點(diǎn)數(shù)集合來確定，即：主節(jié)點(diǎn) p = v mod |R|。v：視圖編號，|R|節(jié)點(diǎn)個數(shù)，p：主節(jié)點(diǎn)編號。

?

PBFT算法有兩個限定條件：

①所有節(jié)點(diǎn)必須是確定性的，即：在給定狀態(tài)和參數(shù)相同的情況下，操作執(zhí)行的結(jié)果必須相同。

②所有節(jié)點(diǎn)必須從相同的狀態(tài)開始執(zhí)行。

在這兩個限定條件下，即使失效的副本節(jié)點(diǎn)存在，PBFT算法對所有非失效副本節(jié)點(diǎn)的請求執(zhí)行總順序達(dá)成一致，從而保證安全性。

?

1、角色劃分

Client： 客戶端節(jié)點(diǎn)，負(fù)責(zé)發(fā)送交易請求。

Primary: 主節(jié)點(diǎn)，負(fù)責(zé)將交易打包成區(qū)塊和區(qū)塊共識，每輪共識過程有且僅有一個。

Replica: 副本節(jié)點(diǎn)，負(fù)責(zé)區(qū)塊共識，每輪共識過程中有多個Replica節(jié)點(diǎn)。

其中，Primary和Replica節(jié)點(diǎn)都屬于共識節(jié)點(diǎn)。

?

2、基本流程

請求階段：客戶端將交易信息向全網(wǎng)節(jié)點(diǎn)廣播，生成主節(jié)點(diǎn)負(fù)責(zé)驗(yàn)證請求信息，并生成預(yù)準(zhǔn)備消息

預(yù)準(zhǔn)備階段：主節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息

準(zhǔn)備階段：每個節(jié)點(diǎn)接收到消息后進(jìn)行驗(yàn)證，并將驗(yàn)證結(jié)果消息發(fā)送給全部其他的節(jié)點(diǎn)

確認(rèn)階段：若系統(tǒng)承受的最大惡意節(jié)點(diǎn)數(shù)為f，則當(dāng)某節(jié)點(diǎn)收到2f條來自其他節(jié)點(diǎn)的確認(rèn)消息后，加上自己的確認(rèn)消息，總數(shù)達(dá)到（2f+1）條時，可以向全網(wǎng)發(fā)送一條廣播消息。

響應(yīng)階段：PBFT算法是強(qiáng)一致性算法，每次區(qū)塊的產(chǎn)出都是由唯一的主節(jié)點(diǎn)主導(dǎo)生成，不存在分叉的可能性，但容錯率顯著低于比特幣的51%可靠性；

?

3、核心流程

算法的核心三個階段：pre-prepare （預(yù)準(zhǔn)備），prepare （準(zhǔn)備）， commit （提交）。

圖中的C代表客戶端，0，1，2，3 代表節(jié)點(diǎn)的編號，其中0 是主節(jié)點(diǎn)primary，打×的3代表故障或作惡節(jié)點(diǎn)，這里表現(xiàn)的就是對其它節(jié)點(diǎn)的請求無響應(yīng)。整個過程大致是如下：

?

首先，客戶端向主節(jié)點(diǎn)0發(fā)起請求<<REQUEST,o,t,c>>其中t是時間戳，o表示操作，c是這個client，主節(jié)點(diǎn)收到客戶端請求，會向其它節(jié)點(diǎn)發(fā)送 pre-prepare 消息，其它節(jié)點(diǎn)就收到了pre-prepare 消息，就開始了這個核心三階段共識過程了。

?

（1）Pre-prepare 階段

副本節(jié)點(diǎn)replica收到 pre-prepare 消息<<PRE_PREPARE,v,n,d>,m>后，判斷是否接收該消息。其中，v 代表視圖編號，n代表消息序號（主節(jié)點(diǎn)收到客戶端的每個請求都以一個編號來標(biāo)記），d代表消息摘要，m代表原始消息數(shù)據(jù)。消息里的 v 和 n 在之前收到的消息里出現(xiàn)過的，但d和m卻和之前的消息不一致，或者請求編號n不在高低水位之間，這時候就會拒絕請求。拒絕的邏輯就是主節(jié)點(diǎn)不會發(fā)送兩條具有相同的v和n，但d和m卻不同的消息。

Replia節(jié)點(diǎn)接收到pre-prepare消息，進(jìn)行以下消息驗(yàn)證：

①消息m的簽名合法性，并且消息摘要d和消息m相匹配：d=hash(m)

②節(jié)點(diǎn)當(dāng)前處于視圖v中

③節(jié)點(diǎn)當(dāng)前在同一個(view v ，sequence n)上沒有其它pre-prepare消息，即不存在另外一個m’和對應(yīng)的d’ ，d’=hash(m’)

④h<=n<=H，H和h代表序號n的高低水位。

?

（2）Prepare 階段

當(dāng)前節(jié)點(diǎn)同意請求后會向其它節(jié)點(diǎn)發(fā)送 prepare 消息<PREPARE,v,n,d,i>同時將消息記錄到log中，其中?i表示當(dāng)前節(jié)點(diǎn)的身份。同一時刻可能有 n 個節(jié)點(diǎn)也在進(jìn)行這個過程。因此節(jié)點(diǎn)是有可能收到其它節(jié)點(diǎn)發(fā)送的 prepare 消息的，當(dāng)前節(jié)點(diǎn)i驗(yàn)證這些prepare消息和自己發(fā)出的prepare消息的v，n，d三個數(shù)據(jù)是否都是一致的。驗(yàn)證通過之后，當(dāng)前節(jié)點(diǎn)i將prepared(m，v，n) 設(shè)置為true，prepared(m，v，n) 代表共識節(jié)點(diǎn)認(rèn)為在(v，n)中針對消息m的Prepare階段是否已經(jīng)完成。在一定時間范圍內(nèi)，如果收到超過 2f 個其他節(jié)點(diǎn)的prepare 消息，就代表 prepare 階段已經(jīng)完成。最后共識節(jié)點(diǎn)i發(fā)送commit消息并進(jìn)入Commit階段。

?

（3）Commit 階段

當(dāng)前節(jié)點(diǎn)i接收到2f個來自其他共識節(jié)點(diǎn)的commit消息<COMMIT,v,n,d,i>同時將該消息插入log中（算上自己的共有2f+1個），驗(yàn)證這些commit消息和自己發(fā)的commit消息的v，n，d三個數(shù)據(jù)都是一致后，共識節(jié)點(diǎn)將committed-local(m，v，n)設(shè)置為true，committed-local(m，v，n)代表共識節(jié)點(diǎn)確定消息m已經(jīng)在整個系統(tǒng)中得到至少2f+1個節(jié)點(diǎn)的共識，而這保證了至少有f+1個non-faulty節(jié)點(diǎn)已經(jīng)對消息m達(dá)成共識。于是節(jié)點(diǎn)就會執(zhí)行請求，寫入數(shù)據(jù)。

?

（4）Reply階段

處理完畢后，節(jié)點(diǎn)會返回消息<<REPLY,v,t,c,i,r>>給客戶端，其中v是視圖編號，t是時間戳，i是副本的編號，r是請求執(zhí)行的結(jié)果。當(dāng)客戶端收集到f+1個消息后，共識完成。

?

prepare和commit階段為何都要2f+1個節(jié)點(diǎn)反饋確認(rèn)?（這2f+1并不一定是相同的）

考慮最壞的情況：我們假設(shè)收到的有f個是正常節(jié)點(diǎn)發(fā)過來的，也有f個是惡意節(jié)點(diǎn)發(fā)過來的，那么，第2f+1個只可能是正常節(jié)點(diǎn)發(fā)過來的。由此可知，“大多數(shù)”正常的節(jié)點(diǎn)還是可以讓系統(tǒng)工作下去的。所以2f+1這個參數(shù)和n>3f+1的要求是邏輯自洽的。

?

client為何只需要f+1個相同的回復(fù)就可確認(rèn)？

?考慮最壞的情況，我們假設(shè)這f+1個相同的reply中，有f個都是惡意節(jié)點(diǎn)。

所以至少有一個rely是正常節(jié)點(diǎn)發(fā)出來的，因?yàn)樵趐repare階段，這個正常的節(jié)點(diǎn)已經(jīng)可以保證prepared(m,v,n,i)為真，所以已經(jīng)能代表大多數(shù)的意見，所以，client只需要f+1個相同的reply就能保證他拿到的是整個系統(tǒng)內(nèi)“大多數(shù)正常節(jié)點(diǎn)“的意見，從而達(dá)到一致性。

?

總結(jié)： 如果順利的話，一個節(jié)點(diǎn)收到1個pre-prepare消息和2f個和prepare消息進(jìn)入commit階段，2f+1個commit消息后可以reply給client，client收到f+1個回復(fù)就可以確認(rèn)提交成功。

?

4、垃圾回收

根據(jù)前面的算法部分可以發(fā)現(xiàn)，我們需要不斷地往log中插入消息，在view change時恢復(fù)需要用到。當(dāng)某一request已經(jīng)被f+1個正常節(jié)點(diǎn)執(zhí)行完畢后，并當(dāng)view change可以向其他節(jié)點(diǎn)證明當(dāng)前狀態(tài)的正確性，與該request相關(guān)的message就可以刪除了。

當(dāng)request的序號n % C (某一定值) =0時，產(chǎn)生一個checkpoint，節(jié)點(diǎn)i多播消息<<CHECKPOINT,n,d,i>>給其他節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)接收2f+1個消息時，該checkpoint變?yōu)閟table checkpoint，也就是這2f+1個節(jié)點(diǎn)可以證明該狀態(tài)的正確性，同時可以刪除序號≤n的消息相關(guān)的log信息和checkpoint信息。

checkpoint：當(dāng)前節(jié)點(diǎn)處理的最新請求序號。

stable checkpoint （穩(wěn)定檢查點(diǎn)）：是大部分節(jié)點(diǎn) （2f+1個） 已經(jīng)共識完成的最大請求序號。

高低水位：低水位就是stable checkpoint的序號n，高水位是n + K，其中K是定值，一般是C（上面提及到的某一定值）的整數(shù)倍。

?

具體過程：

執(zhí)行K條請求后再向全網(wǎng)發(fā)起廣播，告訴大家它已經(jīng)將這K條執(zhí)行完畢；如果大家反饋說這K條執(zhí)行完畢，那就可以刪除這K條的信息了；再執(zhí)行K條，完成后再發(fā)起一次廣播，即每隔K條發(fā)起一次全網(wǎng)共識，這個概念叫checkpoint，即每隔K條去征求一下大家的意見，要是獲得了大多數(shù)的認(rèn)同，就形成一個stable checkpoint（記錄在第K條的編號）。

這是理想的情況，實(shí)際上當(dāng)副本i向全網(wǎng)發(fā)出checkpoint共識后，其他節(jié)點(diǎn)可能沒有執(zhí)行完這K條請求，所以副本i不會立即得到響應(yīng)，它還要繼續(xù)自己的事情，那這個checkpoint在它那里就不是stable的。

這里有一個處理策略：對該副本來說，它的低水位h等于它上一個stable checkpoint的編號，高水位H=h+L（一般我們設(shè)置L是K的倍數(shù)，例如2倍），這樣即使該副本處理速度很快，它處理的請求編號達(dá)到高水位H后也得停一停自己的腳步，直到它的stable checkpoint發(fā)生變化，它才能繼續(xù)向前。

?

5、視圖更換（view change）：選舉主節(jié)點(diǎn)的過程

當(dāng)主節(jié)點(diǎn)出錯或成為惡意節(jié)點(diǎn)時，就需要進(jìn)行視圖更換(view change)，也就是選擇（輪換法）下一個replica節(jié)點(diǎn)作為主節(jié)點(diǎn)，視圖編號v進(jìn)行+1操作，共識過程進(jìn)入下一個view。

view change 會有三個階段：view-change，view-change-ack ，new-view。

?

5.1觸發(fā)條件

視圖改變由以下兩個條件之一觸發(fā)：

①replica從一個client得知，primary存在不正當(dāng)行為（例如：偽造數(shù)據(jù)等）

②replica不能收到primary發(fā)出的消息

View Change由replica發(fā)起，它們向其他副本發(fā)送IHatePrimary消息以啟動一個視圖改變。注意：View Chage不能由拜占庭節(jié)點(diǎn)發(fā)起。

?

5.2?VIEW-CHANGE的條件

Replica持續(xù)接收IHatePrimary消息，直到遇到下面兩個條件之一：

①接收到超過f+1個IHatePrimary消息

②收到了其他節(jié)點(diǎn)的ViewChange消息。

將會將廣播一條<VIEW-CHANGE, v+1, n, C, P, i>消息。

v：上一個視圖編號

n：節(jié)點(diǎn)i的stable checkpoint的編號

C：2f+1個節(jié)點(diǎn)的有效checkpoint信息的集合

P：節(jié)點(diǎn)i中的上一個視圖中編號大于n并且達(dá)到prepared狀態(tài)的請求消息的集合

i：節(jié)點(diǎn)的編號

?

5.3.?NEW-VIEW的條件

當(dāng)前存活的節(jié)點(diǎn)編號最小的節(jié)點(diǎn)將成為新的主節(jié)點(diǎn)。當(dāng)新的主節(jié)點(diǎn)收到 2f 個其它節(jié)點(diǎn)的 view-change 消息，則證明有足夠多人的節(jié)點(diǎn)認(rèn)為主節(jié)點(diǎn)有問題，于是就會向其它節(jié)點(diǎn)廣播 new-view 消息<<NEW-VIEW,v+1,V,O>>

v：上一個視圖編號

V：新的主節(jié)點(diǎn)接收到的有效的視圖編號為v+1的view-change消息集合

O：pre-prepare消息的集合。假設(shè) O 集合里消息的編號范圍：（min～max）， Min 為 V 集合最小的 stable checkpoint ， Max 為 V 集合中最大序號的 prepare 消息。最后一步執(zhí)行 O 集合里的 pre-preapare消息，每條消息會有兩種情況: 若max-min>0，產(chǎn)生消息 <<pre-prepare,v+1,n,d>> ；若=0，產(chǎn)生消息 <<pre-prepare,v+1,n,d(null)>>

?

注意：replica節(jié)點(diǎn)不會發(fā)起new-view事件。對于主節(jié)點(diǎn)，發(fā)送new-view消息后會繼續(xù)執(zhí)行上個視圖未處理完的請求，從pre-prepare階段開始。其它節(jié)點(diǎn)驗(yàn)證new-view消息通過后，就會處理主節(jié)點(diǎn)發(fā)來的pre-prepare消息，這時執(zhí)行的過程就是前面描述的PBFT過程。到這時，正式進(jìn)入v+1（視圖編號加1）的時代了。

PBFT共識算法：BFT類算法，可容忍≤三分之一的故障和作惡節(jié)點(diǎn)，可達(dá)到最終一致性;

Raft共識算法：CFT類算法，可容忍—半故障節(jié)點(diǎn)，不能防止節(jié)點(diǎn)作惡，可達(dá)到一致性。

?

?

三、POW：(Proof of Work)工作量證明機(jī)制

基本原理：付出多少工作量，就會獲得多少報酬（比特幣等加密貨幣）?！皠趧印本褪悄銥榫W(wǎng)絡(luò)提供的計算服務(wù)（算力*時長），提供這種服務(wù)的過程就是“挖礦”。

?

優(yōu)點(diǎn)：

①機(jī)制很復(fù)雜，但有很多細(xì)節(jié)：挖礦難度自動調(diào)整、區(qū)塊獎勵逐步減半等。

②理想狀態(tài)，可以吸引很多用戶參與其中，特別是越先參與的獲得越多，會促使加密貨幣的初始階段發(fā)展迅速，節(jié)點(diǎn)網(wǎng)絡(luò)迅速擴(kuò)大。

③通過“挖礦”的方式發(fā)行新幣，把比特幣分散給個人，實(shí)現(xiàn)了相對公平。

?

缺點(diǎn)：

①算力是計算機(jī)硬件（CPU、GPU等）提供的，要耗費(fèi)電力，是對能源的直接消耗。

②算力的提供已經(jīng)不再是單純的CPU了，而是逐步發(fā)展到GPU、FPGA，乃至ASIC礦機(jī)。用戶也從個人挖礦發(fā)展到大的礦池、礦場，算力集中越來越明顯。這與去中心化的方向背道而馳，網(wǎng)絡(luò)的安全逐漸受到威脅。

③比特幣區(qū)塊獎勵每４年將減半，當(dāng)挖礦的成本高于挖礦收益時，人們挖礦的積極性降低，會有大量算力減少，比特幣網(wǎng)絡(luò)的安全性進(jìn)一步堪憂。

?

工作量證明系統(tǒng)主要特征是客戶端需要做一定難度的工作得出一個結(jié)果，驗(yàn)證方卻很容易通過結(jié)果來檢查出客戶端是不是做了相應(yīng)的工作?！静粚ΨQ】

舉個例子，給定的一個基本的字符串"Hello, world!"，給出的工作量要求是，在這個字符串后面添加一個叫做nonce的整數(shù)值，對變更后（添加nonce)的字符串進(jìn)行SHA256哈希運(yùn)算，如果得到的哈希結(jié)果（以16進(jìn)制的形式表示）是以"0000"開頭的，則驗(yàn)證通過。為了達(dá)到這個工作量證明的目標(biāo)。需要不停的遞增nonce值，對得到的新字符串進(jìn)行SHA256哈希運(yùn)算。按照這個規(guī)則，需要經(jīng)過4251次計算才能找到恰好前4位為0的哈希散列。

?

比特幣網(wǎng)絡(luò)中任何一個節(jié)點(diǎn)，如果想生成一個新的區(qū)塊并寫入?yún)^(qū)塊鏈，必須解出比特幣網(wǎng)絡(luò)出的工作量證明的迷題。

SHA是安全散列算法（Secure Hash Algorithm）的縮寫，是一個密碼散列函數(shù)家族。主要適用于數(shù)字簽名標(biāo)準(zhǔn)。SHA256是輸出值為256位的哈希算法。到目前為止，還沒有出現(xiàn)對SHA256算法的有效攻擊。

?

1、區(qū)塊

區(qū)塊頭的大小為80字節(jié)：

4字節(jié)的版本號

32字節(jié)的上一個區(qū)塊的散列值

32字節(jié)的Merkle Root Hash

4字節(jié)的時間綴（當(dāng)前時間）

4字節(jié)的當(dāng)前難度值

4字節(jié)的隨機(jī)數(shù)

區(qū)塊包含的交易列表則附加在區(qū)塊頭后面，其中的第一筆交易是coinbase交易，這是一筆為了讓礦工獲得獎勵及手續(xù)費(fèi)的特殊交易。

區(qū)塊頭，是用于比特幣工作量證明的輸入字符串。為了使區(qū)塊頭能體現(xiàn)區(qū)塊所包含的所有交易，在區(qū)塊的構(gòu)造過程中，需要將該區(qū)塊要包含的交易列表，通過Merkle Tree算法生成Merkle Root Hash，作為交易列表的摘要存到區(qū)塊頭中。

?

2、難度值

難度值（difficulty）是礦工們在挖礦時候的重要參考指標(biāo)，它決定了礦工大約需要經(jīng)過多少次哈希運(yùn)算才能產(chǎn)生一個合法的區(qū)塊。難度值必須根據(jù)全網(wǎng)算力的變化進(jìn)行調(diào)整。難度的調(diào)整是在每個完整節(jié)點(diǎn)中獨(dú)立自動發(fā)生的。每2016個區(qū)塊，所有節(jié)點(diǎn)都會按統(tǒng)一的公式自動調(diào)整難度。

這個公式是由最新2016個區(qū)塊的花費(fèi)時長與期望時長比較得出的。

新難度值 = 舊難度值 * ( 過去2016個區(qū)塊花費(fèi)時長 / 20160 分鐘 )

【撇開舊難度值，按比特幣理想情況每10分鐘出塊的速度，過去11個塊的總花費(fèi)接近110分鐘，這樣，這個值永遠(yuǎn)趨近于1?！?/p>

?

工作量證明需要有一個目標(biāo)值。比特幣工作量證明的目標(biāo)值（Target）的計算公式如下：

目標(biāo)值 = 最大目標(biāo)值 / 難度值

【最大目標(biāo)值為一個恒定值】

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

目標(biāo)值的大小與難度值成反比。比特幣工作量證明的達(dá)成就是礦工計算出來的區(qū)塊哈希值必須小于目標(biāo)值。

?

?

3、工作量證明的過程：

生成Coinbase交易，并與其他所有準(zhǔn)備打包進(jìn)區(qū)塊的交易組成交易列表，通過Merkle Tree算法生成Merkle Root Hash

把Merkle Root Hash及其他相關(guān)字段組裝成區(qū)塊頭，將區(qū)塊頭的80字節(jié)數(shù)據(jù)（Block Header）作為工作量證明的輸入

不停的變更區(qū)塊頭中的隨機(jī)數(shù)即nonce的數(shù)值【在0到232之間取值】，并對每次變更后的的區(qū)塊頭做雙重SHA256運(yùn)算（即SHA256(SHA256(Block_Header))），將結(jié)果值與當(dāng)前網(wǎng)絡(luò)的目標(biāo)值做對比，如果小于目標(biāo)值，則解題成功，工作量證明完成。

?

【Coinbase交易+其他交易 → 交易列表 → Merkle Root Hash →組裝塊頭 → 作為工作量證明的輸入 → 變更nonce → 雙重SHA256運(yùn)算 → 與目標(biāo)值對比 → 小于，則成功?！?/p>

?

比特幣PoW的過程，可以簡單理解成就是將不同的nonce值作為輸入，嘗試進(jìn)行SHA256哈希運(yùn)算，找出滿足給定數(shù)量前導(dǎo)0的哈希值的過程。而要求的前導(dǎo)0的個數(shù)越多，代表難度越大。

?

?

一般說來， PoW 共識的隨機(jī)數(shù)搜索過程如下：

①搜集當(dāng)前時間段的全網(wǎng)未確認(rèn)交易, 并增加一個用于發(fā)行新比特幣獎勵的 Coinbase 交易, 形成當(dāng)前區(qū)塊體的交易集合;

②計算區(qū)塊體交易集合的Merkle根記入?yún)^(qū)塊頭, 并填寫區(qū)塊頭的其他元數(shù)據(jù), 其中隨機(jī)數(shù) Nonce 置零;

③隨機(jī)數(shù) Nonce 加 1; 計算當(dāng)前區(qū)塊頭的雙 SHA256 哈希值, 如果小于或等于目標(biāo)哈希值, 則成功搜索到合適的隨機(jī)數(shù)并獲得該區(qū)塊的記賬權(quán); 否則繼續(xù)步驟 3 直到任一節(jié)點(diǎn)搜索到合適的隨機(jī)數(shù) 為止;

④如果一定時間內(nèi)未成功, 則更新時間戳和未確認(rèn)交易集合、重新計算 Merkle 根后繼續(xù)搜索。

?

4、如何用PoW記賬？

①客戶端產(chǎn)生新的交易，向全網(wǎng)廣播

②每個節(jié)點(diǎn)收到請求，將交易納入?yún)^(qū)塊中

③每個節(jié)點(diǎn)通過pow工作量證明

④當(dāng)某個節(jié)點(diǎn)找到了證明，向全網(wǎng)廣播

⑤當(dāng)且僅當(dāng)該區(qū)塊的交易是有效的且之前未存在的，其他節(jié)點(diǎn)才認(rèn)同該區(qū)塊的有效性

⑥接受該區(qū)塊且在該區(qū)塊的末尾制造新的區(qū)塊

大概時序圖：

?

?

四、POS(Proof of Stake)：股權(quán)證明機(jī)制。

基本原理：這是點(diǎn)點(diǎn)幣（PPC）的創(chuàng)新。沒有挖礦過程，在創(chuàng)世區(qū)塊內(nèi)寫明了股權(quán)分配比例，之后通過轉(zhuǎn)讓、交易的方式（通常就是IPO），逐漸分散到用戶手里，并通過“利息”的方式新增貨幣，實(shí)現(xiàn)對節(jié)點(diǎn)的獎勵。以太坊是POW跟POS結(jié)合。

簡單來說，就是一個根據(jù)用戶持有貨幣的多少和時間（幣齡），發(fā)放利息的一個制度。【使得難度與交易輸人的幣齡成反比】如果用戶想獲得更多的貨幣，那么就打開客戶端，讓它保持在線，就能通過獲得“利息”獲益，同時保證網(wǎng)絡(luò)的安全。

?

實(shí)際上，點(diǎn)點(diǎn)幣的權(quán)益證明機(jī)制結(jié)合了隨機(jī)化與幣齡的概念,未使用至少30天的幣可以參與競爭下一區(qū)塊，越久和越大的幣集有更大的可能去簽名下一區(qū)塊。然而，一旦幣的權(quán)益被用于簽名一個區(qū)塊， 則幣齡將清為零，這樣必須等待至少30日才能簽署另一區(qū)塊。

同時，為防止非常老或非常大的權(quán)益控制區(qū)塊鏈，尋找下一區(qū)塊的最大概率在90天后達(dá)到最大值，這一過程保護(hù)了網(wǎng)絡(luò)，并隨著時間逐漸生成新的幣而無需消耗大量的計算能力。

點(diǎn)點(diǎn)幣的開發(fā)者聲稱這將使得惡意攻擊變得困難，因?yàn)闆]有中心化的挖礦池需求，而且購買半數(shù)以上的幣的開銷似乎超過獲得51%的工作量證明的哈希計算能力。

權(quán)益證明必須采用某種方法定義任意區(qū)塊鏈中的下一合法區(qū)塊，依據(jù)賬戶結(jié)余來選擇將導(dǎo)致中心化。為此，人們還設(shè)計了其他不同的方法來選擇下一合法區(qū)塊。

?

優(yōu)點(diǎn)：

①節(jié)能。不用挖礦，不需要大量耗費(fèi)電力和能源。

②更去中心化。相對于比特幣等PoW類型的加密貨幣，PoS機(jī)制的加密貨幣對計算機(jī)硬件基本上沒有過高要求，人人可挖礦（獲得利息），不用擔(dān)心算力集中導(dǎo)致中心化的出現(xiàn)（單用戶通過購買獲得51%的貨幣量，成本更高），網(wǎng)絡(luò)更加安全有保障。

③避免緊縮。PoW機(jī)制的加密貨幣，因?yàn)橛脩魜G失等各種原因，可能導(dǎo)致通貨緊縮，但是PoS機(jī)制的加密貨幣按一定的年利率新增貨幣，可以有效避免緊縮出現(xiàn)，保持基本穩(wěn)定。比特幣之后，很多新幣采用PoS機(jī)制，很多采用工作量證明機(jī)制的老幣，也紛紛修改協(xié)議，“硬分叉”升級為PoS機(jī)制。

?

缺點(diǎn)：

①純PoS機(jī)制的加密貨幣，只能通過IPO的方式發(fā)行，這就導(dǎo)致“少數(shù)人”（通常是開發(fā)者）獲得大量成本極低的加密貨幣，在利益面前，很難保證他們不會大量拋售。

②PoS機(jī)制的加密貨幣，信用基礎(chǔ)不夠牢固。

?

為解決這個問題，很多采用PoW+PoS的雙重機(jī)制，通過PoW挖礦發(fā)行加密貨幣，使用PoS維護(hù)網(wǎng)絡(luò)穩(wěn)定?；蛘卟捎肈PoS機(jī)制，通過社區(qū)選舉的方式，增強(qiáng)信任。

?

該算法與PoW算法的最大不同點(diǎn)在于區(qū)塊的記賬權(quán)由權(quán)益最高的節(jié)點(diǎn)獲得, 而不是算力最高的節(jié)點(diǎn)。

共識過程中節(jié)點(diǎn)通過消耗的幣齡來獲取記賬權(quán)，節(jié)點(diǎn)消耗的幣齡越多，獲得記賬權(quán)的機(jī)會越大。算法設(shè)定的主鏈原則為：消耗幣齡最多的鏈為系統(tǒng)中正確有效的鏈。點(diǎn)點(diǎn)幣中 PoS算法合格區(qū)塊的判定公式為：

ProofHash＜Target×CoinAge

ProofHash對應(yīng)一組數(shù)據(jù)的哈希,此處省略；

CoinAge為幣齡（coin*age）;

Target為當(dāng)前目標(biāo)值，同PoW一樣，與難度成反比。

?

Target＝PrevTarget×(1007×10×60＋２×Tgap )/1009× 10×60

PrevTarget為上一個區(qū)塊的目標(biāo)值；

２×Tgap 為前兩個區(qū)塊的間隔時間。

當(dāng)前兩個區(qū)塊時間間隔＞10 min,當(dāng)前目標(biāo)值相比于上一個區(qū)塊目標(biāo)值會提高，即當(dāng)前區(qū)塊難度會降低；

當(dāng)前兩個區(qū)塊時間間隔＜10 min，當(dāng)前目標(biāo)值相比于上一個區(qū)塊目標(biāo)值會降低，即當(dāng)前區(qū)塊難度會提高。

?

PoS將算力競爭轉(zhuǎn)化為權(quán)益競爭, 不僅節(jié)約算力, 權(quán)益的引入也能夠防止節(jié)點(diǎn)發(fā)動惡意攻擊; 同時促使所有節(jié)點(diǎn)有責(zé)任維護(hù)區(qū)塊鏈的安全穩(wěn)定運(yùn)行以保障自身權(quán)益; PoS 雖然降低了算力資源的消耗, 但是沒有解決中心化程度增強(qiáng)的問題, 新區(qū)塊的生成趨向于權(quán)益高的節(jié)點(diǎn)。PoS中需要擁有超全網(wǎng)一半的權(quán)益發(fā)動51%攻擊, 但其成本高于擁有超全網(wǎng)一半的算力，另外創(chuàng)建區(qū)塊需要消耗權(quán)益, 使得PoS持續(xù)進(jìn)行 51%攻擊的難度增加, 一定程度上降低了 安全風(fēng)險。

?

?

五、DPOS（Delegated Proof of Stake）：授權(quán)股權(quán)證明機(jī)制

它是PoS的一種衍生算法，算法的思想是系統(tǒng)中持有權(quán)益的節(jié)點(diǎn)投票選舉出一部分代表，再由這些代表輪流獲取區(qū)塊記賬權(quán)，某種程度上類似于股份制公司的“董事會”。

?

基本原理：無人控制的公司發(fā)行股份，產(chǎn)生利潤，并將利潤分配給股東。實(shí)現(xiàn)這一切不需要信任任何人，因?yàn)槊考露际潜挥簿幋a到軟件中的。通俗點(diǎn)講就是：公司股份制，股東持有這些公司的股份，公司為股東產(chǎn)生回報，無需挖礦。

?

每個節(jié)點(diǎn)都可將自己持有的權(quán)益轉(zhuǎn)化為選票投給自己信任的節(jié)點(diǎn)，所持的權(quán)益越多，選票所占的權(quán)重也就越高，獲得票數(shù)最多的n個節(jié)點(diǎn)當(dāng)選為見證人（代表）。見證人的名單每經(jīng)過一個固定周期都將重新選舉更換一次。見證人直接參與區(qū)塊的共識和驗(yàn)證過程，在一個規(guī)定的時間內(nèi)它們隨機(jī)排列并輪流對交易進(jìn)行打包，生成新區(qū)塊連接到最長鏈上。每生成一個區(qū)塊，見證人會獲得m％的交易手續(xù)費(fèi)，m值由見證人們提議設(shè)定并由選民們投票決議。參與見證人的競選也需繳納大量的保證金，這樣，見證人在系統(tǒng)中投入的資金最大，為保證自身的利益積極地維護(hù)系統(tǒng)安全。

?

優(yōu)點(diǎn)：

①能耗更低。DPoS機(jī)制將節(jié)點(diǎn)數(shù)量進(jìn)一步減少到101個，在保證網(wǎng)絡(luò)安全的前提下，整個網(wǎng)絡(luò)的能耗進(jìn)一步降低，網(wǎng)絡(luò)運(yùn)行成本最低。

②更加去中心化。目前，對于比特幣而言，個人挖礦已經(jīng)不現(xiàn)實(shí)了，比特幣的算力都集中在幾個大的礦池手里，每個礦池都是中心化的，就像DPoS的一個受托人，因此DPoS機(jī)制的加密貨幣更加去中心化。PoS機(jī)制的加密貨幣（比如未來幣），要求用戶開著客戶端，事實(shí)上用戶并不會天天開著電腦，因此真正的網(wǎng)絡(luò)節(jié)點(diǎn)是由幾個股東保持的，去中心化程度也不能與DPoS機(jī)制的加密貨幣相比。

③更快的確認(rèn)速度。每個塊的時間為10秒，一筆交易（在得到6-10個確認(rèn)后）大概1分鐘，一個完整的101個塊的周期大概僅僅需要16分鐘。而比特幣（PoW機(jī)制）產(chǎn)生一個區(qū)塊需要10分鐘，一筆交易完成（6個區(qū)塊確認(rèn)后）需要1個小時。點(diǎn)點(diǎn)幣（PoS機(jī)制）確認(rèn)一筆交易大概也需要1小時。

?

缺點(diǎn)：

①投票的積極性并不高。絕大多數(shù)持股人（90％+）從未參與投票。這是因?yàn)橥镀毙枰獣r間、精力以及技能，而這恰恰是大多數(shù)投資者所缺乏的。

②對于壞節(jié)點(diǎn)的處理存在諸多困難。社區(qū)選舉不能及時有效的阻止一些破壞節(jié)點(diǎn)的出現(xiàn)，給網(wǎng)絡(luò)造成安全隱患。

POI：(Proof of Importance)重要度證明共識算法

基本原理：PoI使用賬戶重要性評分來分配記賬權(quán)的概率。

優(yōu)點(diǎn)：低能耗，速度快，公平

缺點(diǎn)：缺少社區(qū)共識，賬戶重要性≠設(shè)備貢獻(xiàn)度

?

POP：(Proof?of?Participation)參與度證明

基本原理：這是標(biāo)準(zhǔn)鏈（CZR）的創(chuàng)新，POP 將 POI 和DPOS 的思想結(jié)合，既能確保對設(shè)備的公平性，又擁有社區(qū)的共識。

優(yōu)點(diǎn)：低功耗、速度更快，更加安全，既能確保公平性，又擁有社區(qū)的共識。

?

POOL驗(yàn)證池

基于傳統(tǒng)的分布式一致性技術(shù)，加上數(shù)據(jù)驗(yàn)證機(jī)制。

優(yōu)點(diǎn)：不需要代幣也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基礎(chǔ)上，實(shí)現(xiàn)秒級共識驗(yàn)證。

缺點(diǎn)：去中心化程度不如bictoin；更適合多方參與的多中心商業(yè)模式。

?

總結(jié)

POW（工作量證明機(jī)制）：“按勞分配”。

POS（股權(quán)證明機(jī)制）：持有的股票越多，權(quán)利越大 。

DPOS（授權(quán)股權(quán)證明機(jī)制）：由大家選舉產(chǎn)生董事會成員行使權(quán)利。

PBFT（實(shí)用拜占庭容錯算法）：一種基于消息傳遞的一致性算法，算法經(jīng)過三個階段：預(yù)準(zhǔn)備（pre-prepare）、準(zhǔn)備(prepare)、確認(rèn)(commit)達(dá)成一致性，這些階段可能因?yàn)槭《貜?fù)進(jìn)行。

POI（重要度證明共識算法）：本質(zhì)是POS的變種。

POP（參與證明）：前邊所有的幾種的升級。

POOL：國產(chǎn)的驗(yàn)證池

?

從機(jī)制設(shè)計上來看，POW 機(jī)制更加強(qiáng)調(diào)去中心, 更加強(qiáng)調(diào)對等。而DPOS 則是有一個明顯的中心, 通過帶來部分中心，來得到效率的提升。哪一種機(jī)制更好, 有待時間的驗(yàn)證。POW 已經(jīng)運(yùn)行快10年, 電力耗費(fèi)已經(jīng)非常嚴(yán)重。POP的出現(xiàn), 有可能讓記賬這件事情更經(jīng)濟(jì)效率, 從而支撐起更多大規(guī)模的協(xié)作體系。

根據(jù)可容忍的故障類型的不同，可以將共識算法分為兩類：

CFT類算法：容忍宕機(jī)錯誤類算法（crash fault tolerant consensus algorithm），可以容忍網(wǎng)絡(luò)丟包、時鐘漂移、部分節(jié)點(diǎn)宕機(jī)這種節(jié)點(diǎn)為良性的錯誤。常見算法有 Paxos、Raft。

BFT類算法：容忍拜占庭錯誤類算法（byzantine fault tolerant consensus algorithm），可以容忍部分節(jié)點(diǎn)任意類型錯誤，包括節(jié)點(diǎn)作惡的情況。常見算法有 PBFT、PoW、PoS等。

?

根據(jù)使用場景的不同，又可將共識算法分為公鏈共識、聯(lián)盟鏈共識兩類。

公鏈共識：公鏈的特點(diǎn)是節(jié)點(diǎn)數(shù)量多且分布分散，主要使用的共識算法有PoW和PoS，這兩種共識的優(yōu)點(diǎn)是可以支持的節(jié)點(diǎn)數(shù)量多，缺點(diǎn)是TPS較低和交易確認(rèn)時間長。

聯(lián)盟鏈共識：聯(lián)盟鏈的特點(diǎn)是節(jié)點(diǎn)之間網(wǎng)絡(luò)較為穩(wěn)定且節(jié)點(diǎn)有準(zhǔn)入要求，根據(jù)需要容忍的錯誤類型可以選擇Raft和PBFT類算法，這類算法的優(yōu)點(diǎn)是TPS較高且交易可以在毫秒級確認(rèn)，缺點(diǎn)是支持的節(jié)點(diǎn)數(shù)量有限，通常不多于100個節(jié)點(diǎn)。