共識算法

區(qū)塊鏈中最重要的便是共識算法，比特幣使用的是POS（Proof?of Work，工作量證明），以太幣使用的是POS（Proof of Stake，股權(quán)證明）使得算理便的不怎么重要了，而今POS的變體DPOS（Delegated Proof of Stake，股份授權(quán)證明）進一步削減算力的浪費，同時也加強了區(qū)塊鏈的安全性。不過，對于不需要貨幣體系的許可鏈或者私有鏈而言，絕對信任的節(jié)點，以及高效的需求上述共識算法并不能夠提供，因此對于這樣的區(qū)塊鏈，傳統(tǒng)的一致性算法成為首選，PBFT（拜占庭容錯）、PAXOS、RAFT。

PBFT（拜占庭容錯）

基于拜占庭將軍問題，一致性的確保主要分為這三個階段：預準備（pre-prepare）、準備(prepare)和確認(commit)。流程如下圖所示：

其中C為發(fā)送請求端，0123為服務端，3為宕機的服務端，具體步驟如下：1. Request：請求端C發(fā)送請求到任意一節(jié)點，這里是02. Pre-Prepare：服務端0收到C的請求后進行廣播，擴散至1233. Prepare：123,收到后記錄并再次廣播，1->023，2->013，3因為宕機無法廣播4. Commit：0123節(jié)點在Prepare階段，若收到超過一定數(shù)量的相同請求，則進入Commit階段，廣播Commit請求5.Reply：0123節(jié)點在Commit階段，若收到超過一定數(shù)量的相同請求，則對C進行反饋
根據(jù)上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N為總計算機數(shù)，F為有問題的計算機總數(shù)
N=4 F=0 時：

?	得到數(shù)據(jù)	最終數(shù)據(jù)
A	1 1 1 1	1
B	1 1 1 1	1
C	1 1 1 1	1
D	1 1 1 1	1

N=4 F=1 時：

?	得到數(shù)據(jù)	最終數(shù)據(jù)
A	1 1 1 0	1
B	1 1 0 1	1
C	1 0 1 1	1
D	0 1 1 1	1

N=4 F=2 時：

?	得到數(shù)據(jù)	最終數(shù)據(jù)
A	1 1 0 0	NA
B	1 0 0 1	NA
C	0 0 1 1	NA
D	0 1 1 0	NA

由此可以看出，拜占庭容錯能夠容納將近1/3的錯誤節(jié)點誤差，IBM創(chuàng)建的Hyperledger就是使用了該算法作為共識算法。

PAXOS

PAXOS是一種基于消息傳遞且具有高度容錯特性的一致性算法。
算法本身用語言描述極其精簡：phase 1
a) proposer向網(wǎng)絡內(nèi)超過半數(shù)的acceptor發(fā)送prepare消息
b) acceptor正常情況下回復promise消息
phase 2
a) 在有足夠多acceptor回復promise消息時，proposer發(fā)送accept消息
b) 正常情況下acceptor回復accepted消息

PAXOS中有三類角色Proposer、Acceptor及Learner，主要交互過程在Proposer和Acceptor之間，做成圖便如下圖所示：

其中1,2,3,4代表順序。
以下圖描述多Proposer的情況，T代表時間軸，圖中僅畫全一個Proposer與Acceptor的關(guān)系：


A3在T1發(fā)出accepted給A1，然后在T2收到A5的prepare，在T3的時候A1才通知A5最終結(jié)果(稅率10%)。這里會有兩種情況：
1. A5發(fā)來的N5小于A1發(fā)出去的N1，那么A3直接拒絕(reject)A5
2. A5發(fā)來的N5大于A1發(fā)出去的N1，那么A3回復promise，但帶上A1的(N1, 10%)
最終A5也會接受10%


上圖描述，如果已經(jīng)Promise一個更大的N，那么會直接Reject更小的N


上述描述了，即使Promise了一個N，如果在未Accepted前，再收到一個更大的N，那么依舊會Reject那個即使已經(jīng)Promise的N
總流程圖氪概括如下：


PAXOS協(xié)議用于微信PaxosStore中，每分鐘調(diào)用Paxos協(xié)議過程數(shù)十億次量級。

RAFT

RAFT核心思想很容易理解，如果數(shù)個數(shù)據(jù)庫，初始狀態(tài)一致，只要之后的進行的操作一致，就能保證之后的數(shù)據(jù)一致。由此RAFT使用的是Log進行同步，并且將服務器分為三中角色：Leader，Follower，Candidate，相互可以互相轉(zhuǎn)換。RAFT從大的角度看，分為兩個過程：1. 選舉Leader2. Leader生成Log，并與Follower進行Headbeats同步

選舉Leader

Follower自增當前任期，轉(zhuǎn)換為Candidate，對自己投票，并發(fā)起RequestVote RPC，等待下面三種情形發(fā)生；

1. 獲得超過半數(shù)服務器的投票，贏得選舉，成為Leader
2. 另一臺服務器贏得選舉，并接收到對應的心跳，成為Follower
3. 選舉超時，沒有任何一臺服務器贏得選舉，自增當前任期，重新發(fā)起選舉

同步日志

Leader接受客戶端請求，Leader更新日志，并向所有Follower發(fā)送Heatbeats，同步日志。所有Follwer都有ElectionTimeout，如果在ElectionTimeout時間之內(nèi)，沒有收到Leader的Headbeats，則認為Leader失效，重新選舉Leader
流程圖示：

安全性保證

1. 日志的流向只有Leader到Follower，并且Leader不能覆蓋日志2. 日志不是最新者不能成為Candidate
動畫演示RAFT：http://thesecretlivesofdata.com/raft/

總結(jié)

以上三種一致性算法僅僅只是核心思路而已，如果要具體實現(xiàn)當然還有很多方面需要進一步的完善。以上三種算法都可以作為區(qū)塊鏈的共識算法，并且部分公司已經(jīng)開始使用，不過最出名的還應屬IBM的Hyperledger使用的PBFT共識算法。

?	得到數(shù)據(jù)	最終數(shù)據(jù)
A	1 1 1 1	1
B	1 1 1 1	1
C	1 1 1 1	1
D	1 1 1 1	1

https://blog.csdn.net/jerry81333/article/details/74303194

總結(jié)

以上是生活随笔為你收集整理的区块链共识算法 PBFT（拜占庭容错）、PAXOS、RAFT简述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。