解析共識算法的分類（上）

—— Part1 共識的分類——

從早期的分佈式一致性算法的緩慢發展到現如今區塊鏈共識的百花齊放，共識算法的發展已經走過了四十年左右的時光。不同的共識算法的側重點不同，因此它們所面臨的問題、環境也不一樣。本文將從如下幾個不同角度對共識算法進行分類：

▲容錯類型

根據是否容忍拜占庭錯誤，可以將共識算法分為兩類。

1）拜占庭容錯共識算法：PBFT、PoW、PoS、DPoS

2）非拜占庭容錯共識算法：Paxos、Raft

是否容忍拜占庭標誌著該算法是否能夠應用到低信任的網絡當中。通常來說，公有鏈環境中必須使用拜占庭容錯算法，而聯盟鏈中可以根據聯盟參與方之間的信任程度進行選擇。

▲算法確定性

根據算法的確定性，可以將共識算法分為兩類。

1）確定性共識算法：Paxos、Raft、PBFT

2）概率性共識算法：PoW、部分PoS

確定性共識指的是共識決策一旦達成，就不存在回退的可能性，這一類通常是傳統的分佈式一致性算法及其改進版本。而概率性指的是已經達成的共識決策在未來有一定的概率會被回退，雖然這個概率隨著時間的推移會趨於為0，這一類通常是應用在公有鏈上的區塊鏈共識算法。

▲選主策略

根據選主的策略，可以將共識算法分為兩類。

1）選舉類共識算法：Raft、PBFT

2）證明類共識算法：PoW、PoS

選舉類共識指的是通過投票選擇出塊節點，同一個節點可以連續多輪作為出塊節點存在，這一類通常是傳統的分佈式一致性算法及其改進版本。證明類共識算法指的是出塊節點需要通過某種方式證明自己具備某種能力，從而獲得出塊權，這一類的共識算法通常每一輪的出塊節點都不相同，從而保證了出塊權的公平性，通常應用在公有鏈上。

—— Part2 非拜占庭容錯共識算法——

Paxos

圖片描述

圖片描述

正文

正文

Raft

Paxos誠然是一個非常有影響力的共識算法，可以說奠定了分佈式一致性算法的基礎，但是由於其難以理解以及實現難度非常之大，想要實現一個完整的Paxos算法非常的困難。因此，出現了非常多的Paxos變體，其中最著名的當屬Raft共識算法。

Raft是一種用來管理日誌複製的一致性算法，旨在易於理解。它具備了Paxos的容錯性和性能，不同之處在於它將一致性問題分解為相對獨立的三子問題，分別是領導選取（leader election），日誌複製（log replication）和安全性（safety）。這使得Raft更好理解並且更容易應用到實際系統的建立中。

在Raft中，每一個節點一定會處於以下三種狀態中的一個：Leader(主節點)、Candidate（候選節點）、Follower（從節點）。在正常情況下，只有一個節點是Leader，剩下的節點是Follower。 Leader負責處理所有來自客戶端的請求（如果一個客戶端與Follower進行通信，Follower會將信息轉發給Leader），生成日誌數據（對應在區塊鏈中即負責打包）並廣播給Follower節點。 Follower是被動的：他們不會主動發送任何請求，只能單向接收從Leader發來的日誌數據。 Candidate是在選舉下一任Leader的過程中出現的過渡狀態，任何一個節點在發現主節點故障之後都可以成為Candidate並競選成為Leader。

正文

圖片描述

正文

總結

正文

正文

  PoW

工作量證明（Proof of Work，PoW）最早在1993年由Cynthia Dwork與Moni Naor在學術論文[3]中提及，並於同年由Markus Jakobsson與Ari Juels正式提出了“工作量證明”這個概念[ 4]。起初，PoW主要用於防止垃圾郵件的產生。 2008年，PoW作為共識算法應用在比特幣系統中。 PoW有以下3個基本屬性：

1）數學難題：PoW共識算法設計了一個數學難題（Mathematical Puzzle），要求節點在生成新區塊之前，需要消耗一定的計算資源才能獲得難題的解，從而將區塊廣播到網絡，並且其他節點可以輕易驗證這個解的有效性。

2）哈希算法：哈希算法（Hash Algorithm）是一種能夠把任意長度的輸入變換成固定長度的輸出的算法，可被記為y = hash(x)，不同的輸入x得到的輸出y各不相同。除此之外，在已知x時可以快速計算得到y，但是在已知y的情況下，通常只能通過窮舉法才能逆推出x。由於哈希算法具有正向快速、逆向困難的特性，常使用哈希算法來設計PoW的數學難題。

3）生成區塊：在一輪區塊生成中，系統通過對輸出值設定條件來調整數學問題的難度值，節點在成功解出問題並通過驗證上鍊後，將會獲得相應的獎勵。

在生成新的區塊之前，PoW會預設目標值，要求出塊節點計算出的哈希值小於該目標值，以此來表示PoW的難度。為了生成區塊並獲得獎勵，出塊節點首先收集一組交易打包成一個區塊，並開始嘗試解決數學問題進行出塊。

在此期間，出塊節點需要生成隨機數，同當前區塊數據與前一個區塊的哈希進行多輪哈希運算，計算當前區塊的哈希值：

正文

圖片描述

正文

PoS

前面提到的工作量證明共識算法，就是通過算力來爭奪“領導者”的資格，但是工作量證明過程中的大量資源浪費，導致其很難被更大規模的應用接受。對此，有人開始嘗試直接使用“股權（Stake）”作為標準進行“領導者”資格的競選，並隨之產生了權益證明（Proof of Stake，PoS）共識算法。

PoS的思想來源於社會：一個人擁有的股份量越多，其獲得的股息和分紅就會越高。如果區塊鏈系統也採用這種方法進行維護，不需要過多的資源消耗，也能夠使得區塊鏈資產有自然的通脹。節點通過投入一定量的通證參與共識，根據通證持有情況獲得打包新區塊的權利並獲得獎勵。目前，以太坊也有轉向PoS的以太坊2.0計劃。

為了描述通證持有情況，PoS共識算法引入了“幣齡”的概念。幣齡（Coin-age）表示節點持有部分通證的時長，當節點將通證作為“股份”投入後，這部分通證就開始積累幣齡，幣齡的計算方式如下：

在使用了這部分通證後，無論是用來進行區塊生成或者簡單的交易，這部分通證對應的幣齡將被銷毀。在最初的PoS共識算法中，幣齡是進行評判的重要標準，節點在區塊生成時所使用的幣齡越高就越容易產生區塊，這可以在一定程度上製約短期投機行為。

PoS共識算法在進行區塊生成時，將同時考慮幣齡與哈希運算難度，使得節點只需要消耗很少的計算資源就可以完成區塊生成。

DPoS

委託權益證明（Delegated Proof of Stake，DPoS）共識算法[5]中，選舉人通過選舉產生代表，由代表進行直接的區塊產生，選舉人通過選舉代表人間接行使競爭出塊的權利。委託權益證明共識算法，實際上就是通過一系列選拔規則對候選人進行製約，並製定一套投票規則。普通參與者通過投票的方式從候選者中選拔出委託人，並由委託人進行出塊，不滿足要求的委託人將會被取消權限，並重新選舉產生新的委託人。

DPoS保留了一定的中心化特性，因此能夠保證高效率的交易吞吐，速率可以比肩常見的中心化機構，例如Visa、Mastercard等。在該算法中，去中心化的特性主要體現在對於生成區塊的權利可控。即股東通過投票，選擇自己信任的代表節點，並由代表節點進行區塊鏈數據的維護。

—— Part4 總結——

參考文獻

作者簡介

作者簡介

參考文獻

參考文獻

參考文獻

[1]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.

[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.

[5]Delegated Proof of Stakehttps://github.com/dacplayproject/cpp-play/wiki/Delegated-Proof-of-Stake