區(qū)塊鏈共識算法

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

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

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

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

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

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

強一致性：任何時刻保持一致

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

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

弱一致性：某一時刻保持一致

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

不能達成一致性的兩種情況

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

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

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

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

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

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

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

5、非拜占庭錯誤的兩種解決方案

1、PAXOS

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

2、Raft

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

（1）Leader在時，由Leader同步日志。

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

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

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

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

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

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

步驟：

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

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

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

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

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

2、中本聰共識（POW）

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

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

3、POS共識

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

Native POS的面臨的問題：nothing_to_stake

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

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

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

Native POS：

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

POW:

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

CASPER：

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

4、DPOS共識：Delegated Proof of Stake

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

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

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

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

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