區(qū)塊鏈共識算法

1、分布式系統(tǒng)案例：售票系統(tǒng)

分布式系統(tǒng)的共識算法

在一個(gè)分布式系統(tǒng)中，如何保證集群中的所有節(jié)點(diǎn)中的數(shù)據(jù)完全相同且能夠?qū)δ硞€(gè)提案（proposal）達(dá)成一致是分布式系統(tǒng)正常工作的核心問題，而共識算法就是用來保證分布式系統(tǒng)一致性的方法。

2、區(qū)塊鏈和共識算法的關(guān)系

數(shù)字貨幣->雙花問題->線性賬目（區(qū)塊鏈）->共識

3、分布式系統(tǒng)一致性

強(qiáng)一致性：任何時(shí)刻保持一致

順序一致性(Sequential Consistency)：Leslie Lamport1979年經(jīng)典論文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出，是一種比較強(qiáng)的約束，保證所有進(jìn)程看到的全局執(zhí)行的順序（total order）一致，且每個(gè)進(jìn)程看自身的執(zhí)行（total order）跟實(shí)際發(fā)生順序一致。例如某進(jìn)程先執(zhí)行A，后執(zhí)行B，則實(shí)際得到的全局結(jié)果中就應(yīng)該為A在B前面，而不能反過來。同時(shí)所有其他進(jìn)程在全局上也應(yīng)該看到這個(gè)順序。順序一致性實(shí)際上限制了各進(jìn)程內(nèi)的偏序關(guān)系，但不在進(jìn)程間按照物理時(shí)間進(jìn)行全局排序。

線性一致性(Linearizability Consistency )：Maurice P.Herlihy與Jeannette M.Wing在1990年經(jīng)典論文《Linearizability:A Correctness Condition for Concurrent Objects》中共同提出，在順序一致性前提下加強(qiáng)了進(jìn)程間的操作順序。形成唯一的全局順序（系統(tǒng)等價(jià)于是順序執(zhí)行，所有進(jìn)程看到的所有操作的順序都一致，并且跟實(shí)際發(fā)生順序一致），是很強(qiáng)的原子性保證。但是比較難實(shí)現(xiàn)，目前基本上要么依賴于全局的時(shí)鐘或鎖，要么通過一些復(fù)雜算法實(shí)現(xiàn)，性能往往不高。

弱一致性：某一時(shí)刻保持一致

強(qiáng)一致性的系統(tǒng)往往比較難實(shí)現(xiàn)。很多時(shí)候，人們發(fā)現(xiàn)實(shí)際需求并沒有那么強(qiáng)，可以適當(dāng)放寬一致性要求，降低系統(tǒng)實(shí)現(xiàn)的難度。例如在一定約束下實(shí)現(xiàn)所謂最終一致性（Eventual Consistency），即總會存在一時(shí)刻（而不是立刻），系統(tǒng)達(dá)到一致的狀態(tài)，這對于大部分的Web系統(tǒng)來說已經(jīng)足夠。這一類弱化的一致性，被籠統(tǒng)稱為弱一致性（Weak Consistency）。

不能達(dá)成一致性的兩種情況

我們假設(shè)通訊是可靠的。那么我們把照成不能達(dá)成一致性的故障情況分為兩種：

1、節(jié)點(diǎn)只是故障狀態(tài)，不存在惡意節(jié)點(diǎn)，那么我們稱“非拜占庭錯(cuò)誤”。

2、存在惡意節(jié)點(diǎn)的分布式網(wǎng)絡(luò)，我們稱為“拜占庭錯(cuò)誤”。

我們區(qū)塊鏈面臨的一致性問題為“拜占庭將軍問題”。

4、分布式系統(tǒng)的同步和異步

同步系統(tǒng)：消息不丟失且秒到

異步系統(tǒng)：消息有延誤且可能丟失

5、非拜占庭錯(cuò)誤的兩種解決方案

1、PAXOS

核心思想：Paxos解決這一問題利用的是選舉，少數(shù)服從多數(shù)的思想，只要2N+1個(gè)節(jié)點(diǎn)中，有N個(gè)以上同意了某個(gè)決定，則認(rèn)為系統(tǒng)達(dá)到了一致，并且按照Paxos原則，最終理論上也達(dá)到一致，不會再改變。這樣的話，客戶端不必與所有服務(wù)器通信，選擇與大部分通信即可；也無需服務(wù)器都全部處于工作狀態(tài)，有一些服務(wù)器掛掉，只有保證半數(shù)以上存活著，整個(gè)過程也能持續(xù)下去。

2、Raft

相比paxos的優(yōu)點(diǎn)是容易理解，容易實(shí)現(xiàn)。它強(qiáng)化了leader的地位，把整個(gè)協(xié)議可以清楚的分割成兩部分，并利用日志的連續(xù)性做了一些簡化。

（1）Leader在時(shí)，由Leader同步日志。

（2）Leader掛掉了，選一個(gè)新Leader選舉算法。

6、拜占庭將軍的解決方案

對于可以容忍拜占庭錯(cuò)誤的算法：PBFT、中本聰共識（POW）、POS和DPOS四種算法。

1、PBFT：更加實(shí)用的拜占庭容錯(cuò)方法。早期的BFT的缺陷：1、假定是同步場景；2、性能太慢（超過100個(gè)節(jié)點(diǎn)則不可用）。

PBFT算法的核心理論是n>=3f+1 : n是系統(tǒng)中的總節(jié)點(diǎn)數(shù)，f是允許出現(xiàn)故障的節(jié)點(diǎn)數(shù)。換句話說，如果這個(gè)系統(tǒng)允許出現(xiàn)f個(gè)故障，那么這個(gè)系統(tǒng)必須包括n個(gè)節(jié)點(diǎn)，才能解決故障。

PBFT算法在區(qū)塊鏈中的應(yīng)用

步驟：

1.從全網(wǎng)節(jié)點(diǎn)選舉出一個(gè)主節(jié)點(diǎn)（Leader），新區(qū)塊由主節(jié)點(diǎn)負(fù)責(zé)生成；

2.Pre-Preare：每個(gè)節(jié)點(diǎn)把客戶端發(fā)來的交易向全網(wǎng)廣播，主節(jié)點(diǎn)0將從網(wǎng)絡(luò)收集到需放在新區(qū)快內(nèi)的多個(gè)交易排序后存入列表，并將該列表向全網(wǎng)廣播，擴(kuò)散至1 2 3；

3.Preepare：每個(gè)節(jié)點(diǎn)接收到交易列表后，根據(jù)排序模擬執(zhí)行這些交易。所有交易執(zhí)行完后，基于交易結(jié)果計(jì)算新區(qū)快的哈希摘要，并向全網(wǎng)廣播，1->023, 2->013，3為宕機(jī)無法廣播；

4.Commit：如果一個(gè)節(jié)點(diǎn)收到的2f(f為可容忍的拜占庭節(jié)點(diǎn)數(shù))個(gè)其他節(jié)點(diǎn)發(fā)來的摘要都和自己相等，就向全網(wǎng)廣播一條commit消息。

5.Reply：如果一個(gè)節(jié)點(diǎn)收到2f+1條commit的消息，即可提交新區(qū)塊及其他交易到本地的區(qū)塊鏈和狀態(tài)數(shù)據(jù)庫。

2、中本聰共識（POW）

POW：一組通過算法生成的數(shù)據(jù)，難于生成而易于驗(yàn)證。1993年由Cynthia Dwork and Moni NAOR提出。

比特幣使用的Hashcash proof of work由Adan Back在1997年發(fā)明，用于防止垃圾郵件和拒絕服務(wù)器攻擊。Hashcash proof of work被中本聰用于比特幣的挖礦。挖礦的過程是選擇一個(gè)節(jié)點(diǎn)作為區(qū)塊鏈生產(chǎn)者。

3、POS共識

POS：最早是由網(wǎng)名為“QuantumMechanic”的網(wǎng)友在比特幣論壇中提出。其核心思想為擁有幣權(quán)的人可以進(jìn)行選舉，選舉出來大家最終誰來生成區(qū)塊。

Native POS的面臨的問題：nothing_to_stake

就如桌上有十個(gè)文件，每個(gè)人會在一個(gè)文件上簽名，最后選出簽名最多的一個(gè)文件，誰在簽名最多的文件上簽名就給誰發(fā)幣。但有些作弊的人，在十個(gè)文件上都簽字，最終不管哪個(gè)文件簽名最多，它都能拿到幣，這就nothing_to_stake。

現(xiàn)在以太坊用的共識算法是CASPER，CASPER是改進(jìn)版的POS。

CASPER算法 、Native POS、POW對無力攻擊的解決辦法：

Native POS：

POS鏈上產(chǎn)生了分叉，不投票什么也沒有，在A分支上投票得到的利益是0.9，在B分支上投票獲得的利益是0.1，如果在兩個(gè)分支上都投票獲得的利益=0.1+0.9=1。

POW:

pow鏈上產(chǎn)生了分叉，不投票什么也沒有，在A分支上投票得到的利益是0.9，在B分支上投票獲得的利益是0.1，如果在兩個(gè)分支上都投票獲得的利益=0.1/2+0.9/2=0.5，因?yàn)镻OW要分散算力。

CASPER：

CASPER鏈上產(chǎn)生了分叉，不投票什么也沒有，在A分支上投票得到的利益是0.9，在B分支上投票獲得的利益是0.1，如果在兩個(gè)分支上都投票獲得的利益=0.1+0.9 -5 = -4，兩邊都投票會扣取你的5個(gè)保證金。還有一種更嚴(yán)格的方法，雖然你沒有在兩個(gè)分支上都投票，但你只有在短的分支上投票就扣你5個(gè)保證金。

4、DPOS共識：Delegated Proof of Stake

DPOS由BM提出：由代幣持有者選擇見證人節(jié)點(diǎn)，由一組見證人通過round-robi的方式輪流產(chǎn)生區(qū)塊。在15/21個(gè)人對一個(gè)區(qū)塊進(jìn)行簽名，然后區(qū)塊得到確認(rèn)。

DPOS對Nothing_to_stake的應(yīng)對方案：讓生產(chǎn)者被淘汰?！癕iners”are now generally public,known individuals rather than anonymous individuals.

為什么是15/21個(gè)人可以達(dá)到共識？(n-(n-1)/3) 所以(21-(21-1)/3)=15

DPOS的理念：由持有者進(jìn)行投票，最大化的分散持有者的規(guī)模，最小化的代價(jià)來加固網(wǎng)絡(luò)（無需挖礦），最大化網(wǎng)絡(luò)性能（超級節(jié)點(diǎn)），最小化運(yùn)行網(wǎng)絡(luò)成本（EOS每年會曾發(fā)代幣的5%平分給超級節(jié)點(diǎn)）。

而DPOS就像一個(gè)公司一樣運(yùn)行，股東選舉出董事會，董事會成員輪流生成區(qū)塊，驗(yàn)證通過后上鏈。區(qū)塊生產(chǎn)者既沒有創(chuàng)造無效的區(qū)塊的權(quán)力，也沒有改變社區(qū)共識的權(quán)利。