區(qū)塊鏈技術(shù)筆記第二彈

共識機(jī)制學(xué)習(xí)筆記

干貨一

從核心認(rèn)識到區(qū)塊鏈出現(xiàn)根本目的是降低信用成本，目的是讓大家最快速度互相信任并且產(chǎn)生成功一致的決定和結(jié)果。通過共識機(jī)制出來的統(tǒng)一意志來撰寫賬本，從而達(dá)到所有人都信任的地步。

（其實非技術(shù)人員看懂這戲就夠了，往下想搞清楚技術(shù)的接著看。對了，關(guān)于共識機(jī)制非技術(shù)人員也可以了解一下，尤其是想投資的親）

參考書籍《區(qū)塊鏈原理設(shè)計與應(yīng)用》

問題提出：拜占庭將軍問題是Leslie Lamport（2013年的圖靈講得?。┯脕頌槊枋?b>分布式系統(tǒng)一致性問題（Distributed Consensus）在論文中抽象出來一個著名的例子。拜占庭帝國想要進(jìn)攻一個強(qiáng)大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵御5支常規(guī)拜占庭軍隊的同時襲擊。這10支軍隊在分開的包圍狀態(tài)下同時攻擊。他們?nèi)我恢к婈爢为氝M(jìn)攻都毫無勝算，除非有至少6支軍隊（一半以上）同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵騎馬相互通信來協(xié)商進(jìn)攻意向及進(jìn)攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時間。在這種狀態(tài)下，拜占庭將軍們才能保證有多于6支軍隊在同一時間一起發(fā)起進(jìn)攻才可以保持順利。（問題提出不考慮失效和通訊失敗的情況）

問題分析：先看在沒有叛徒情況下，假如一個將軍A提一個進(jìn)攻提議（如：明日下午1點進(jìn)攻，你愿意加入嗎？）由通信兵通信分別告訴其他的將軍，如果幸運中的幸運，他收到了其他6位將軍以上的同意，發(fā)起進(jìn)攻。如果不幸，其他的將軍也在此時發(fā)出不同的進(jìn)攻提議（如：明日下午2點、3點進(jìn)攻，你愿意加入嗎？），由于時間上的差異，不同的將軍收到（并認(rèn)可）的進(jìn)攻提議可能是不一樣的，這是可能出現(xiàn)A提議有3個支持者，B提議有4個支持者，C提議有2個支持者等等。

再加一點復(fù)雜性，在有叛徒情況下，一個叛徒會向不同的將軍發(fā)出不同的進(jìn)攻提議（通知A明日下午1點進(jìn)攻， 通知B明日下午2點進(jìn)攻等等），一個叛徒也會可能同意多個進(jìn)攻提議（即同意下午1點進(jìn)攻又同意下午2點進(jìn)攻）。

叛徒發(fā)送前后不一致的進(jìn)攻提議，被稱為“拜占庭錯誤”，而能夠處理拜占庭錯誤的這種容錯性稱為「Byzantine fault tolerance」，簡稱為BFT。

摘自：https://learnblockchain.cn/2018/02/05/bitcoin-byzantine/

問題主要提出了如何在最快速度達(dá)成一致，并且保證信息不出錯。

干貨二

共識機(jī)制簡介與學(xué)習(xí)

出現(xiàn)了問題之后就要解決，并在生活實際上有所作用。目前比較流行的就是POW（利用了沉沒成本，就是所有人消耗大量算力共同來解出或者說蒙出正確答案，不斷將成本累加，讓之后想要修改的人得不償失）。

POS機(jī)制簡單來說，就是根據(jù)你持有貨幣的量和時間，給你發(fā)利息的一個制度，POS主要是利用了持有幣天的多少來決定的POW解的，只有長期持有大量幣的人才有話語權(quán)，這部分人是不愿意系統(tǒng)產(chǎn)生巨大破壞的，破壞的人既要消耗大量的資源又要耗費大量的錢，從而做好了制約。

DPOS機(jī)制，簡單來說就是個董事會投票的過程，將提交和認(rèn)證分開，節(jié)點提交區(qū)塊信息，由股東完成認(rèn)證記賬。

PBFT機(jī)制就是多次和老大確認(rèn)的過程，多次握手，就像是行政機(jī)要的發(fā)送。PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，即服務(wù)作為狀態(tài)機(jī)進(jìn)行建模，狀態(tài)機(jī)在分布式系統(tǒng)的不同節(jié)點進(jìn)行副本復(fù)制。每個狀態(tài)機(jī)的副本都保存了服務(wù)的狀態(tài)，同時也實現(xiàn)了服務(wù)的操作。

Paxos機(jī)制就是國會的抽象了。

（以下，是技術(shù)人員的話看看）

參考書籍《區(qū)塊鏈技術(shù)指南》

其實當(dāng)分布式的思想被提出來時，人們就開始根據(jù)FLP定理和CAP定理設(shè)計共識算法。規(guī)范的說，理想的分布式系統(tǒng)的一致性應(yīng)該滿足以下三點：

1.可終止性（Termination）：一致性的結(jié)果可在有限時間內(nèi)完成。

2.共識性(Consensus)：不同節(jié)點最終完成決策的結(jié)果應(yīng)該相同。

3.合法性(Validity)：決策的結(jié)果必須是其他進(jìn)程提出的提案。

但是在實際的計算機(jī)集群中，可能會存在以下問題:

1.節(jié)點處理事務(wù)的能力不同，網(wǎng)絡(luò)節(jié)點數(shù)據(jù)的吞吐量有差異

2.節(jié)點間通訊的信道可能不安全

3.可能會有作惡節(jié)點出現(xiàn)

4.當(dāng)異步處理能力達(dá)到高度一致時，系統(tǒng)的可擴(kuò)展性就會變差（容不下新節(jié)點的加入）。

在分布式場景下達(dá)成完全一致性是不可能的。但是工程學(xué)家可以犧牲一部分代價來換取分布式場景的一致性，上述的兩大定理也是這種思想，所以基于區(qū)塊鏈設(shè)計的各種公式機(jī)制都可以看作犧牲那一部分代價來換取多適合的一致性，我的想法是可以在這種思想上進(jìn)行一個靈活的變換，即在適當(dāng)?shù)臅r間空間犧牲一部分代價換取適應(yīng)于當(dāng)時場景的一致性，可以實現(xiàn)靈活的區(qū)塊鏈系統(tǒng)，即可插拔式的區(qū)塊鏈系統(tǒng)。今天就介紹一下我對各種共識機(jī)制的看法和分析，分布式系統(tǒng)中有無作惡節(jié)點分為拜占庭容錯和非拜占庭容錯機(jī)制。下面先介紹拜占庭容錯的共識算法：

POW:比特幣萊特幣等貨幣型區(qū)塊鏈（公有鏈）(proof of work)

在比特幣等貨幣型區(qū)塊鏈中讓各節(jié)點達(dá)成一致性的共識機(jī)制為工作量證明，也是我們說的挖礦。

工作量證明是礦工在處理交易數(shù)據(jù)（對數(shù)據(jù)也是進(jìn)行哈希）的同時不斷的進(jìn)行哈希計算，求得一位前23位為0的哈希值，這個值成為nonce黃金數(shù)。當(dāng)全網(wǎng)有一位礦工哈希出nonce時，他就會把自己打包的區(qū)塊公布出去，其他節(jié)點收到區(qū)塊驗證區(qū)塊后就會一致性認(rèn)為這個區(qū)塊接到了區(qū)塊鏈上，就繼續(xù)進(jìn)行下一個區(qū)塊的打包和哈希計算。在這個過程中，中本聰大神是通過算力的比拼犧牲了一部分最終一致性（因為會有分叉的產(chǎn)生）并且需要等待多個確認(rèn)，但是這種簡單暴力的方法卻保證了整個區(qū)塊鏈系統(tǒng)的合法性，而且把區(qū)塊鏈系統(tǒng)的健壯性提升到極致，就算全網(wǎng)只剩下一個節(jié)點運行，這個區(qū)塊鏈系統(tǒng)還是會繼續(xù)運行下去。最后POW也充分提高了區(qū)塊鏈系統(tǒng)的安全性，依靠51%攻擊理論去破壞區(qū)塊鏈系統(tǒng)是只有政府或者瘋子才會采取的方法。

優(yōu)點：

完全去中心化

節(jié)點自由進(jìn)出，容易實現(xiàn)。

破壞系統(tǒng)花費的成本巨大

缺點：

對節(jié)點的性能網(wǎng)絡(luò)環(huán)境要求高

無法達(dá)成最終一致性

最關(guān)鍵的，浪費能源！

POS:Bitshares和qutm等合約型區(qū)塊鏈（proof of stake）

如果簡單的把POW當(dāng)作比力量大小的話，POS就是比耐力多少。

POS是根據(jù)錢包里面貨幣的多少以及貨幣在錢包里存在的天數(shù)來合成一個單位（幣天）。它根據(jù)幣天的關(guān)系對計算機(jī)進(jìn)行哈希計算降低了難度，降低了計算機(jī)的門檻，但是對計算機(jī)還是有一定要求的，它把錢包和區(qū)塊鏈系統(tǒng)的一致性綁定在一起。誰的錢包里的幣天數(shù)越大誰擁有記賬權(quán)的概率就越大。但是它和POW機(jī)制一樣解決問題的思想也導(dǎo)致了它與POW擁有一樣的缺點，也是犧牲了一部分的共識（同樣分叉），而且需要等待多個確認(rèn)。優(yōu)點：

對節(jié)點性能要求低，達(dá)成共識時間短（網(wǎng)絡(luò)環(huán)境好的話可實現(xiàn)毫秒級） 缺點：

沒有最終一致性

DPOS

是基于POS衍生出的更專業(yè)的解決方案，他是類似于董事會的投票機(jī)制，選舉出n個記賬節(jié)點，在節(jié)點中提案者提交的提案被這些記賬節(jié)點投票決定誰是正確的。

優(yōu)點：

減少記賬節(jié)點規(guī)模，屬于弱中心化，效率提高。 缺點：

犧牲了去中心化的概念，不適合公有鏈。

以太坊前三個階段即Frontier（前沿）、Homestead（家園）、Metropolis（大都會）。第四個階段，即Serenity（寧靜），將采用PoS機(jī)制。Casper：以太坊前三個階段采用的是POW共識機(jī)制，第四個階段將采用自己創(chuàng)建的POS機(jī)制，名為投注共識。這種機(jī)制增加了懲罰機(jī)制，并基于POS的思想在記賬節(jié)點中選取驗證人。詳情見以太坊紫皮書。

dBFT：小蟻區(qū)塊鏈（delegated BFT，授權(quán)拜占庭容錯機(jī)制）

用權(quán)益來選出記賬人，然后記賬人之間通過拜占庭容錯算法 達(dá)成共識。

優(yōu)點：專業(yè)化的記賬人可以容忍任何類型的錯誤記賬由多人協(xié)同完成，每一個區(qū)塊都有最終性，不會分叉算法的可靠性有

嚴(yán)格的數(shù)學(xué)證明缺點：當(dāng)三分之一或以上記賬人停止工作后，系統(tǒng)將無法提供服務(wù)當(dāng)三分之一或以上記賬人聯(lián)合作惡，且其他所有的記賬人恰好分割為兩個網(wǎng)絡(luò)孤島時，惡意記賬人可以使系統(tǒng)出現(xiàn)分叉，但是會留下密碼學(xué)證據(jù)

PBFT：Fabric使用的經(jīng)典算法（拜占庭容錯）

這是一種基于消息傳遞的一致性算法，算法經(jīng)過三個階段達(dá)成一致性，這些階段可能因為失敗而重復(fù)進(jìn)行。

假設(shè)節(jié)點總數(shù)為3f+1，f為拜占庭錯誤節(jié)點：

當(dāng)節(jié)點發(fā)現(xiàn)leader作惡時，通過算法選舉其他的replica為leader。

leader通過pre-prepare （第一個協(xié)議階段）消息把它選擇的 value廣播給其他replica節(jié)點，其他的replica節(jié)點如果接受則發(fā)送 prepare（第二個協(xié)議階段），如果失敗則不發(fā)送。

一旦2f個節(jié)點接受prepare消息，則節(jié)點發(fā)送commit（第三個協(xié)議階段）消息。

當(dāng)2f+1個節(jié)點接受commit消息后，代表該value值被確定

如下圖表示了4個節(jié)點，0為leader，同時節(jié)點3為fault節(jié)點，該節(jié)點不響應(yīng)和發(fā)出任何消息。最終節(jié)點狀態(tài)達(dá)到commited時，表示該輪共識成功達(dá)成。

注：預(yù)準(zhǔn)備階段（pre-prepare）：

主節(jié)點分配一個序列號n給收到的請求，然后向所有備份節(jié)點群發(fā)預(yù)準(zhǔn)備消息，預(yù)準(zhǔn)備消息的格式為<,m>，這里v是視圖編號，m是客戶端發(fā)送的請求消息，d是請求消息m的摘要。

準(zhǔn)備階段（prepare）：

如果備份節(jié)點i接受了預(yù)準(zhǔn)備消息<,m>，則進(jìn)入準(zhǔn)備階段。在準(zhǔn)備階段的同時，該節(jié)點向所有副本節(jié)點發(fā)送準(zhǔn)備消息，并且將預(yù)準(zhǔn)備消息和準(zhǔn)備消息寫入自己的消息日志。如果看預(yù)準(zhǔn)備消息不順眼，就什么都不做。

確認(rèn)階段（commit）：

當(dāng)(m,v,n,i)條件為真的時候，副本i將向其他副本節(jié)點廣播，于是就進(jìn)入了確認(rèn)階段。

優(yōu)點：上述其他算法都脫離不了幣的存在，幣的存在及它的獎勵機(jī)制會讓區(qū)塊鏈這一單一的世界窮者更窮，富者更富。共識效率高，可實現(xiàn)高頻交易。缺點：當(dāng)系統(tǒng)只剩下33%的節(jié)點運行時，系統(tǒng)會停止運行。

非拜占庭容錯的共識機(jī)制即不考慮有惡意節(jié)點的情況，人們考慮到1990 年由 Leslie Lamport 提出的 Paxos 共識算法，在工程角度實現(xiàn)了一種最大化保障分布式系統(tǒng)一致性（存在極小的概率無法實現(xiàn)一致）的機(jī)制。

Paxos

Paxos被用于分布式系統(tǒng)中典型的例子就是Zookeeper，他是第一個被證明的共識算法，其原理基于兩階段提交并擴(kuò)展。

Paxos算法中將節(jié)點分為三種類型：proposer：提出一個提案，等待大家批準(zhǔn)為結(jié)案。往往是客戶端擔(dān)任該角色acceptor：負(fù)責(zé)對提案進(jìn)行投票。往往是服務(wù)端擔(dān)任該角色learner：被告知結(jié)案結(jié)果，并與之統(tǒng)一，不參與投票過程?？赡転榭蛻舳嘶蚍?wù)端基本過程包括

proposer 提出提案，先爭取大多數(shù) acceptor 的支持，超過一半支持時，則發(fā)送結(jié)案結(jié)果給所有人進(jìn)行確認(rèn)。一個潛在的問題是

proposer 在此過程中出現(xiàn)故障，可以通過超時機(jī)制來解決。極為湊巧的情況下，每次新的一輪提案的 proposer

都恰好故障，系統(tǒng)則永遠(yuǎn)無法達(dá)成一致（概率很小）。Paxos 能保證在超過50%的正常節(jié)點存在時，系統(tǒng)能達(dá)成共識。

Raft

Raft算法是對Paxos算法的一種簡單實現(xiàn)。

它包括三種角色：leader、candiate 和 follower，其基本過程為：Leader 選舉：每個 candidate

隨機(jī)經(jīng)過一定時間都會提出選舉方案，最近階段中得票最多者被選為 leader同步 log：leader 會找到系統(tǒng)中 log

最新的記錄，并強(qiáng)制所有的 follower 來刷新到這個記錄，這里的log指的是各種事件的發(fā)生記錄

Pool驗證池：布比區(qū)塊鏈

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

優(yōu)點：不需要代幣也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基礎(chǔ)上，實現(xiàn)秒級共識驗證。缺點：去中心化程度不如bictoin；更適合多方參與的多中心商業(yè)模式。

以上摘自：https://blog.csdn.net/jeffrey__zhou/article/details/56672948