區塊鏈共識算法

1、分布式系統案例：售票系統

分布式系統的共識算法

在一個分布式系統中，如何保證集群中的所有節點中的數據完全相同且能夠對某個提案（proposal）達成一致是分布式系統正常工作的核心問題，而共識算法就是用來保證分布式系統一致性的方法。

2、區塊鏈和共識算法的關系

數字貨幣->雙花問題->線性賬目（區塊鏈）->共識

3、分布式系統一致性

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

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

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

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

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

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

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

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

2、存在惡意節點的分布式網絡，我們稱為“拜占庭錯誤”。

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

4、分布式系統的同步和異步

同步系統：消息不丟失且秒到

異步系統：消息有延誤且可能丟失

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

1、PAXOS

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

2、Raft

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

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

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

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

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

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

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

PBFT算法在區塊鏈中的應用

步驟：

1.從全網節點選舉出一個主節點（Leader），新區塊由主節點負責生成；

2.Pre-Preare：每個節點把客戶端發來的交易向全網廣播，主節點0將從網絡收集到需放在新區快內的多個交易排序后存入列表，并將該列表向全網廣播，擴散至1 2 3；

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

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

5.Reply：如果一個節點收到2f+1條commit的消息，即可提交新區塊及其他交易到本地的區塊鏈和狀態數據庫。

2、中本聰共識（POW）

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

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

3、POS共識

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

Native POS的面臨的問題：nothing_to_stake

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

現在以太坊用的共識算法是CASPER，CASPER是改進版的POS。

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

Native POS：

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

POW:

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

CASPER：

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

4、DPOS共識：Delegated Proof of Stake

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

DPOS對Nothing_to_stake的應對方案：讓生產者被淘汰?！癕iners”are now generally public,known individuals rather than anonymous individuals.

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

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

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