从分布式一致性算法到区块链共识机制
引言
分布式一致性是一個(gè)很“古典”的話題，即在分布式系統(tǒng)中，如何保證系統(tǒng)內(nèi)的各個(gè)節(jié)點(diǎn)之間數(shù)據(jù)的一致性或能夠就某個(gè)提案達(dá)成一致。這個(gè)問題想必對(duì)于很多技術(shù)同學(xué)而言并不陌生，幾乎在所有的分布式系統(tǒng)中都會(huì)遇到，比如hdfs、mq、zookeeper、kafka、redis、elasticsearch等。然而這個(gè)問題卻歷久彌新，隨著分布式網(wǎng)絡(luò)的蓬勃發(fā)展與復(fù)雜化，對(duì)于該問題解法的探索也一直在進(jìn)行中。
而近年來，隨著區(qū)塊鏈技術(shù)的興起，特別是開放網(wǎng)絡(luò)中的公有鏈與有權(quán)限網(wǎng)絡(luò)中的聯(lián)盟鏈的蓬勃發(fā)展，一致性問題再次得到關(guān)注，并從新的視角來審視該問題。
本文將從傳統(tǒng)的分布式一致性問題說起，再次重溫我們需要面對(duì)的問題挑戰(zhàn)、已有的理論研究、以及相應(yīng)的一致性算法，并簡(jiǎn)要分析這些一致性算法的適用性與局限性，以及這些傳統(tǒng)一致性算法與嶄新的區(qū)塊鏈技術(shù)的結(jié)合。另外，將從區(qū)塊鏈中一致性問題的全新視角“人的可信”出發(fā)，重點(diǎn)闡述公有鏈領(lǐng)域中的共識(shí)算法與機(jī)制。因此，本文圍繞“一致性”技術(shù)問題，重點(diǎn)從技術(shù)視角闡述傳統(tǒng)計(jì)算機(jī)科學(xué)中的分布式一致性算法與區(qū)塊鏈中的共識(shí)機(jī)制的關(guān)聯(lián)，以及公有鏈對(duì)于一致性問題的重新思考。
分布式一致性問題的挑戰(zhàn)
要清楚理解分布式一致性，首先需要對(duì)分布式網(wǎng)絡(luò)的特性有清晰的認(rèn)識(shí)。那么分布式網(wǎng)絡(luò)具有哪些特點(diǎn)呢？或者通俗理解，在分布式網(wǎng)絡(luò)中，可能遇到哪些問題呢？
Crash Fault
故障錯(cuò)誤（Crash Fault）很好理解，就是說分布式網(wǎng)絡(luò)中：
- 節(jié)點(diǎn)或副本可能隨時(shí)宕機(jī)、可能暫停運(yùn)行但隨后又恢復(fù)；
- 網(wǎng)絡(luò)可能隨時(shí)中斷；
- 發(fā)送的消息可能在傳遞的過程中丟失，對(duì)方一直收不到；
- 發(fā)送的消息可能出現(xiàn)延遲，過了很久對(duì)方才能收到；
- 消息在傳遞的過程中可能出現(xiàn)亂序；
- 網(wǎng)絡(luò)可能出現(xiàn)分化，如中美集群因通信不暢，而導(dǎo)致整體網(wǎng)絡(luò)分化為中美兩個(gè)子網(wǎng)絡(luò)；
這些問題，其實(shí)就是我們?cè)诜植际江h(huán)境中最常實(shí)際遇到的問題，這些問題實(shí)質(zhì)上都是由于分布式系統(tǒng)中的物理硬件的不可靠、不穩(wěn)定所帶來的必然風(fēng)險(xiǎn)，比如：網(wǎng)絡(luò)（信道）不可能是永遠(yuǎn)穩(wěn)定可靠的、物理機(jī)磁盤或CPU等不可能是永遠(yuǎn)良好的。故障錯(cuò)誤可以說是分布式系統(tǒng)中必須考慮并解決的最基本、最常見的一類錯(cuò)誤。
Byzantine Fault
上文的故障錯(cuò)誤，仍然基于一個(gè)很簡(jiǎn)單的假設(shè)：節(jié)點(diǎn)要么不正常工作或響應(yīng)，要么能正常工作或響應(yīng)，但不能口是心非、陽(yáng)奉陰違、表里不一，即可以不干事、但不能干壞事。一旦網(wǎng)絡(luò)中存在作惡節(jié)點(diǎn)，可能會(huì)隨意篡改或偽造數(shù)據(jù)，那么一致性問題的難度就大幅增加。我們常把這類存在“搗亂者”，可能會(huì)篡改或偽造數(shù)據(jù)或響應(yīng)信息的錯(cuò)誤，稱之為拜占庭錯(cuò)誤（Byzantine Fault），而前面所說的故障類錯(cuò)誤也稱之為非拜占庭錯(cuò)誤。
拜占庭這一稱呼，源于Lamport最初的論文，可以說是分布式領(lǐng)域最復(fù)雜、最嚴(yán)格的容錯(cuò)模型。簡(jiǎn)而言之，n個(gè)將軍準(zhǔn)備一起進(jìn)攻某個(gè)城堡，每個(gè)將軍都可以選擇進(jìn)攻或是撤退，但所有將軍必須行動(dòng)一致才能成功。各個(gè)將軍之間相隔很遠(yuǎn)，不能直接通訊，必須通過信使來傳遞消息。但是信使并不可靠，信使可能過了很久才送到消息、可能一直也沒有把消息送到、甚至可能會(huì)故意篡改消息；而將軍也并不可靠，里面可能存在叛徒，并不按照提案來行動(dòng)。顯然，這個(gè)故事中的信使用來代表分布式網(wǎng)絡(luò)中的不可靠信道，而將軍就是各個(gè)不可靠的節(jié)點(diǎn)。
拜占庭問題示意圖（https://lisk.io/academy/blockchain-basics/how-does-blockchain-work/byzantine-fault-tolerance-explained）
應(yīng)對(duì)風(fēng)險(xiǎn)—Fault Tolerance
如何在充滿風(fēng)險(xiǎn)與不確定的分布式網(wǎng)絡(luò)中，尋找到某種確定性與一致性，使得整個(gè)分布式網(wǎng)絡(luò)輸出穩(wěn)定可靠的一致性結(jié)果，就是分布式一致性算法要解決的核心問題。顯而易見，解決故障類錯(cuò)誤更容易一些，通常把這類一致性算法叫做故障容錯(cuò)算法（Crash Fault Tolerance）或者非拜占庭容錯(cuò)算法。而拜占庭類錯(cuò)誤，因?yàn)橛袗阂獯鄹牡目赡苄源嬖?#xff0c;復(fù)雜性更高、解決難度更大，通常把解決這類問題的算法稱作拜占庭容錯(cuò)算法（Byzantine Fault Tolerance）。
那么我們?nèi)滩蛔∫獑?#xff0c;兩類容錯(cuò)算法的界限在哪里？或者說兩類錯(cuò)誤都在什么樣的場(chǎng)景下出現(xiàn)？惡意篡改這種情況真的需要考慮嗎？問題的答案可能取決于我們所處的網(wǎng)絡(luò)環(huán)境與業(yè)務(wù)場(chǎng)景。
CFT
通常而言，如果系統(tǒng)處于可信的內(nèi)部網(wǎng)絡(luò)環(huán)境中，只需要考慮故障容錯(cuò)（CFT）可能就足夠了。比如我們經(jīng)常見到的公司內(nèi)的分布式存儲(chǔ)、消息隊(duì)列、分布式服務(wù)等各種分布式組件，其實(shí)只需要考慮故障容錯(cuò)就足夠了。因?yàn)楣緝?nèi)整個(gè)網(wǎng)絡(luò)是封閉的，又有多重防火墻的保護(hù)，外界很難接入或攻擊；各個(gè)節(jié)點(diǎn)是由公司統(tǒng)一部署的，機(jī)器或運(yùn)行的軟件遭到篡改的可能性極小；此時(shí)的分布式網(wǎng)絡(luò)環(huán)境相對(duì)“單純”，我們唯一的敵人只是：通信網(wǎng)絡(luò)與機(jī)器硬件。我們需要考慮的是網(wǎng)絡(luò)的延遲、不穩(wěn)定，以及機(jī)器隨時(shí)可能出現(xiàn)的宕機(jī)、故障。
BFT
而拜占庭類錯(cuò)誤(BFT)，是把整個(gè)分布式網(wǎng)絡(luò)放到了更大的環(huán)境中去看，除了物理硬件之外，還考慮了一些“人”的因素。畢竟，機(jī)器是不會(huì)作惡的，作惡的只有人。假如我們所處的分布式網(wǎng)絡(luò)是較為開放的網(wǎng)絡(luò)，比如行業(yè)內(nèi)幾十上百家公司組成的聯(lián)盟網(wǎng)絡(luò)；或者是完全開放的網(wǎng)絡(luò)，比如任何人都可以隨意接入到網(wǎng)絡(luò)中；而節(jié)點(diǎn)機(jī)器和上面部署的軟件也是由各個(gè)公司或個(gè)人自己提供和部署的，那么如果利益足夠大，很可能會(huì)有人對(duì)網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)發(fā)起DDoS攻擊、故意篡改軟件代碼改變其執(zhí)行邏輯、甚至可能故意篡改磁盤上持久化的數(shù)據(jù)。顯然，我們此時(shí)面臨的挑戰(zhàn)更大了，我們除了要考慮通信網(wǎng)絡(luò)和機(jī)器硬件的不可靠之外，還必須要考慮和應(yīng)對(duì)系統(tǒng)中的“搗亂者”。
不可能三角
這些實(shí)踐中遇到的問題，也引發(fā)了諸多計(jì)算科學(xué)家進(jìn)行了非常多的理論研究。這些理論研究對(duì)于工程技術(shù)人員而言或許過于抽象繁瑣，有些甚至是無趣的數(shù)學(xué)問題，但這些理論對(duì)于指導(dǎo)我們解決這些問題意義重大。這些理論相當(dāng)于是告訴了我們這類問題解法的理論極限，以及哪些方向可以探索、哪些方向是死路一條。站在前人的肩膀上，才不至于花畢生精力去研制“永動(dòng)機(jī)”。這些理論大家應(yīng)該都有所了解，這里只簡(jiǎn)單回顧。
FLP impossibility
早在1985年，Fisher、Lynch、Paterson三位科學(xué)家就發(fā)表了關(guān)于分布式一致性問題的不可能定理：在完全異步的分布式網(wǎng)絡(luò)中，故障容錯(cuò)問題無法被解決。（ We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation. ）說得更直白點(diǎn)：在異步網(wǎng)絡(luò)中，不可能存在能夠容忍節(jié)點(diǎn)故障的一致性算法，哪怕只有一個(gè)節(jié)點(diǎn)故障。并且這里并沒有考慮拜占庭錯(cuò)誤，而是假設(shè)網(wǎng)絡(luò)非常穩(wěn)定、所有的消息都能被正確傳遞、并且僅被傳遞一次，即便如此都不可能找到能容忍哪怕只有一個(gè)節(jié)點(diǎn)失效的一致性協(xié)議，可見該結(jié)論有多強(qiáng)。（ In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once. ）
當(dāng)然了，這只是理論上的。它的意義在于告訴我們此類問題的理論極限，并不意味著此類問題在實(shí)踐中也不可能被“解決”。如果我們?cè)敢夥艑捪拗啤⒆龀鰻奚?#xff0c;在工程上是可以找到切實(shí)可行的解法的。
FLP不可能定理的最大適用前提是異步網(wǎng)絡(luò)模型。何為同步、異步模型呢？
- 所謂異步模型，是說從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的消息延遲是有限的，但可能是無界的（finite but can be unbounded）。這就意味著如果一個(gè)節(jié)點(diǎn)沒有收到消息，它無法判斷消息到底是丟失了，還是只是延遲了。也就是說，我們無法通過超時(shí)時(shí)間來判斷某個(gè)節(jié)點(diǎn)是否故障。
- 所謂同步模型，是說消息傳遞的延遲是有限的，且是有界的。這就意味著我們可以通過經(jīng)驗(yàn)或采樣精確估算消息的最大可能延遲，從而可以通過超時(shí)時(shí)間來確定消息是否丟失、節(jié)點(diǎn)是否故障。
所幸的是，我們所處于的真實(shí)的網(wǎng)絡(luò)世界更接近同步模型，在很多場(chǎng)景上，我們都可以通過經(jīng)驗(yàn)或采樣確定最大超時(shí)時(shí)間。舉個(gè)通俗點(diǎn)的例子：你給朋友快遞了一本書，朋友過了3天還沒收到，此時(shí)朋友很難判斷到底是快遞延遲了，還是快遞出問題送丟了。但是如果過了一個(gè)月，朋友仍沒收到書，基本就可以斷定快遞送丟了。而背后的推論就是基于經(jīng)驗(yàn)或統(tǒng)計(jì)：通常快遞都能在1-2周內(nèi)送達(dá)。顯然，異步模型其實(shí)是反映了節(jié)點(diǎn)間通訊的最差情況、極端情況，異步模型包含了同步模型，即能在異步模型上有效的一致性協(xié)議，在同步模型上也同樣有效。而同步模型是對(duì)異步模型做了修正和約束，從而使得更接近真實(shí)世界，也使得在實(shí)踐中一致性問題有可能得到有效解。
另外，即便是在異步網(wǎng)絡(luò)模型下，FLP也并不意味著一致性永遠(yuǎn)無法達(dá)成，只是說無法保證在有界的時(shí)間（in bounded time）內(nèi)達(dá)成。在實(shí)踐上，如果放寬對(duì)bounded time的限制，仍然是有可能找到實(shí)踐中的解法的。
而根據(jù)DLS的研究（http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf ），一致性算法按照網(wǎng)絡(luò)模型可以分為三大類：
- 部分同步網(wǎng)絡(luò)模型（partially synchronous model）中的一致性協(xié)議可以容忍最多1/3的任意錯(cuò)誤。這里的部分同步模型是指網(wǎng)絡(luò)延遲是有界的，但是我們無法提前得知。這里的容錯(cuò)也包含了拜占庭類錯(cuò)誤。
- 異步網(wǎng)絡(luò)模型（asynchronous model）中的確定性協(xié)議無法容忍錯(cuò)誤。這里的異步模型即是前文所說的網(wǎng)絡(luò)延遲是無界的。該結(jié)論其實(shí)就是FLP不可能定理的含義，在完全異步網(wǎng)絡(luò)中的確定性協(xié)議不能容忍哪怕只有一個(gè)節(jié)點(diǎn)的錯(cuò)誤。
- 同步網(wǎng)絡(luò)模型（synchronous model）可以達(dá)到驚人的100%容錯(cuò)，雖然對(duì)錯(cuò)誤節(jié)點(diǎn)超過1/2時(shí)的節(jié)點(diǎn)行為有限制。這里的同步模型是指網(wǎng)絡(luò)延遲一定是有界的，即小于某個(gè)已知的常數(shù)。
從另一個(gè)角度來理解，FLP實(shí)際上考慮了分布式系統(tǒng)的3個(gè)屬性：安全(safety)、活性（liveness)、容錯(cuò)：
- 安全是說系統(tǒng)內(nèi)各個(gè)節(jié)點(diǎn)達(dá)成的值是一致的、有效的。safety其實(shí)是保證系統(tǒng)一致性運(yùn)行的最低要求，其核心是cannot do something bad，即不能干壞事、不能做錯(cuò)事。
- 活性是說系統(tǒng)內(nèi)各個(gè)節(jié)點(diǎn)最終（在有限時(shí)間內(nèi)）必須能夠達(dá)成一致，即系統(tǒng)必須能夠向前推進(jìn)，不能永遠(yuǎn)處于達(dá)不成一致的狀態(tài)。liveness其實(shí)是更高要求，意味著不能只是不干壞事，也不能一直不干事，you must do something good，即必須使得整個(gè)系統(tǒng)能良好運(yùn)轉(zhuǎn)下去。
- 容錯(cuò)是說該協(xié)議在有節(jié)點(diǎn)故障的情況下也必須能有效。
FLP不可能定理其實(shí)意味著在異步網(wǎng)絡(luò)中，不可能存在同時(shí)滿足這三者的分布式一致性協(xié)議。因?yàn)榉植际江h(huán)境中，節(jié)點(diǎn)故障幾乎是必然的，因此容錯(cuò)是必須要考慮的因素，所以FLP不可能定理就意味著一致性協(xié)議在能做到容錯(cuò)的情況下，沒辦法同時(shí)做到安全性與系統(tǒng)活性。通常在實(shí)踐中，我們可以做出部分犧牲，比如犧牲一部分安全性，意味著系統(tǒng)總能很快達(dá)成結(jié)論，但結(jié)論的可靠性不足；或者犧牲一部分系統(tǒng)活性，意味著系統(tǒng)達(dá)成的結(jié)論非常可靠，但可能長(zhǎng)時(shí)間、甚至永遠(yuǎn)都在爭(zhēng)論中，無法達(dá)成結(jié)論。所幸的是，很多時(shí)候現(xiàn)實(shí)世界的魯棒性很強(qiáng)，使一致性協(xié)議失效的倒霉事件發(fā)生的概率也很可能極低。
??
FLP不可能定理示意圖（https://www.slideshare.net/oryband/the-stellar-blockchain-and-the-story-of-the-federated-consensusblockchain-academy）
另外，FLP并未排除Las Vegas類隨機(jī)算法，許多一致性算法采用了這種隨機(jī)性來規(guī)避FLP不可能定理對(duì)于確定性異步網(wǎng)絡(luò)的限制。此類非確定性一致性算法涉及Las Vegas規(guī)則：網(wǎng)絡(luò)最終一定能達(dá)成一致，但是達(dá)成一致所需要的時(shí)間可能是無界的。此類算法每輪共識(shí)決策都有一定的概率，并且系統(tǒng)在T秒內(nèi)能夠達(dá)成一致的概率P隨著時(shí)間T的增加而指數(shù)增長(zhǎng)并趨近于1。事實(shí)上，該方法被許多成功的一致性算法所采用，是在FLP不可能定理籠罩下的安全地帶（escape hatch），后面將會(huì)講到比特幣的共識(shí)機(jī)制就是采用了這樣的方法。
CAP theorem
眾所周知、大名鼎鼎的CAP原理，從另一個(gè)維度，簡(jiǎn)單明了、直截了當(dāng)?shù)馗嬖V我們：可用性、一致性與網(wǎng)絡(luò)分區(qū)容錯(cuò)性這三者不可能同時(shí)實(shí)現(xiàn)，而只能實(shí)現(xiàn)任意其中的兩個(gè)。( "Of three properties of shared-data systems (data consistency, system availability and tolerance to network partitions) one can only achieve two at any given time".) CAP與FLP看起來有相似之處，其實(shí)二者并不盡相同，二者是從不同的維度思考問題，另外即使是很相似的概念，內(nèi)涵也并不完全一樣。比如：
- FLP面對(duì)的是分布式一致性問題，而CAP面對(duì)的是分布式網(wǎng)絡(luò)中的數(shù)據(jù)同步與復(fù)制。
- FLP是說在異步網(wǎng)絡(luò)模型中，三者不可能同時(shí)實(shí)現(xiàn)；而CAP是說在所有場(chǎng)景下，三者都不可能同時(shí)實(shí)現(xiàn)。
- FLP中的liveness強(qiáng)調(diào)的是一致性算法的內(nèi)在屬性；而CAP中的availability強(qiáng)調(diào)的是一致性算法對(duì)外呈現(xiàn)的外在屬性。
理論上，只能從CAP三者中選擇兩者，然而，這種選擇的邊界并非是非此即彼的（not binary），很多時(shí)候混合考慮不同程度的各個(gè)因素，結(jié)果可能是更好的。（ The whole spectrum in between is useful; mixing different levels of Availability and Consistency usually yields a better result.）
?
CAP理論示意圖（https://www.researchgate.net/figure/Visualization-of-CAP-theorem_fig2_282679529）
在實(shí)踐中，我們通常需要根據(jù)實(shí)際業(yè)務(wù)場(chǎng)景做折中權(quán)衡。比如：
- 傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)如mysql等多采用ACID（atomicity, consistency, isolation and durability）理論，通過同步事務(wù)操作保證了強(qiáng)一致性；因節(jié)點(diǎn)較少（一般只有主從），可用性也比較一般；網(wǎng)絡(luò)拓?fù)漭^為簡(jiǎn)單，而弱化了分區(qū)容錯(cuò)性。
- NoSQL存儲(chǔ)系統(tǒng)如hbase等多采用BASE（Basically Available、Soft state、Eventually consistent）理論，通過多節(jié)點(diǎn)多副本保證了較高的可用性；另外因節(jié)點(diǎn)數(shù)增多、網(wǎng)絡(luò)環(huán)境也更復(fù)雜，也考慮了網(wǎng)絡(luò)分區(qū)容錯(cuò)性；但一致性較弱，只能保證最終一致性。
?
ACID與BASE對(duì)比（https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf）
當(dāng)然，這些并不是定論，各個(gè)系統(tǒng)都在各自不斷的進(jìn)化完善中，今天的結(jié)論明天可能就會(huì)被打破。更好的系統(tǒng)一定是不斷探索適合自己的場(chǎng)景，找到更佳的平衡點(diǎn)。
分布式一致性算法
面對(duì)分布式環(huán)境中各種真實(shí)、復(fù)雜的問題與挑戰(zhàn)，基于理論上的指引，各種應(yīng)對(duì)現(xiàn)實(shí)問題的解法也被提出。我們這里不探究各類算法的實(shí)現(xiàn)細(xì)節(jié)與具體差異，僅做大體介紹，以便放到更大的維度，從整體上做比較。
Paxos
最大名鼎鼎的分布式一致性算法當(dāng)屬Lamport提出的paxos算法，雖然其復(fù)雜性也同樣“臭名昭著”。Lamport開創(chuàng)性地提出了一種在工程實(shí)踐上切實(shí)可行的、能夠最大程度地保證分布式系統(tǒng)一致性的機(jī)制。paxos被廣泛應(yīng)用在諸多分布式系統(tǒng)中，如Chubby、Zookeeper等。在basic paxos（單一法令，即每次僅對(duì)一個(gè)值進(jìn)行決策）中有兩種角色：proposer可以處理客戶端請(qǐng)求、主動(dòng)提出某個(gè)議案值；acceptor被動(dòng)響應(yīng)proposer發(fā)出的信息、對(duì)提案進(jìn)行投票、持久化存儲(chǔ)決策過程中的值和狀態(tài)。(為簡(jiǎn)化模型，可以忽略learner角色，不影響模型決策。)
如圖所示，共識(shí)決策過程采用了兩階段提交：
- 第1階段，廣播Prepare RPC命令，即找出協(xié)議決定的最終值、阻斷尚未完成的舊提案；
- 第2階段，廣播Accept RPC命令，即要求acceptor接受共識(shí)協(xié)商出的特定值。而multi-paxos是由多個(gè)basic paxos實(shí)例組成，可以對(duì)一系列的值進(jìn)行決議。
Paxos之所以在實(shí)踐中可行，其實(shí)也做了諸多假設(shè)和約束。從處理的問題上來看，Paxos僅能處理故障容錯(cuò)，并不難處理拜占庭錯(cuò)誤，所以屬于非拜占庭容錯(cuò)算法。從FLP的視角，Paxos做到了故障容錯(cuò)和安全性，但放棄了liveness（safe but not live）,也就是說該算法可能永遠(yuǎn)無法結(jié)束，或者說永遠(yuǎn)無法達(dá)成共識(shí)，雖然這種可能性極小。從CAP的視角，Paxos只保證了CP，即做到了分區(qū)容錯(cuò)性和一致性，但弱化了可用性。有時(shí)為了增強(qiáng)paxos系統(tǒng)的可用性，可以考慮增加learner角色的數(shù)目。
即便并不完美，Paxos在實(shí)踐中仍然是可靠、有效且久經(jīng)考驗(yàn)的。Paxos本質(zhì)上是異步系統(tǒng)的分布式一致性協(xié)議，并且在該領(lǐng)域具有支配地位。Chubby之父甚至聲稱世界上只有一種一致性算法，那就是paxos（ there is only one consensus protocol, and that’s Paxos），其他一致性算法都是paxos的broken version。Paxos之所以在實(shí)踐中有效是因?yàn)榭赡苡绊憄axos系統(tǒng)liveness和可用性的條件并不容易被觸發(fā)，即便真的出現(xiàn)，所帶來的代價(jià)也可能并非是難以接受的。
?
Basic Paxos RPC通信與決策過程（https://ongardie.net/static/raft/userstudy/paxos.pdf）
Raft
有感于Paxos的晦澀難懂，Ongaro在2014年提出了更容易理解的Raft算法。Raft把易于理解、易于工程實(shí)現(xiàn)提到了很高的重要級(jí)別，甚至是raft的初心和存在理由，因而在不影響功能性的前提下，盡可能多地做了易于理解的精細(xì)設(shè)計(jì)。
Raft算法是leader-based的非對(duì)稱模型，系統(tǒng)中的任意一個(gè)節(jié)點(diǎn)在任意時(shí)刻，只能處于leader、follower、candidate這3種狀態(tài)之一。初始狀態(tài)所有節(jié)點(diǎn)都是follower狀態(tài)，follower想變成leader必須先成為candidate，然后發(fā)起選舉投票；如果投票不足，則回到follower狀態(tài)；如果投票過半，則成為leader；成為leader后出現(xiàn)故障，若故障恢復(fù)后已有新leader，則自動(dòng)下臺(tái)，回歸follower狀態(tài)。
Raft還引入了term的概念用于及時(shí)識(shí)別過期信息，類似于zookeeper中的epoch；term值單向遞增，每個(gè)term內(nèi)至多一個(gè)leader；若不同term的信息出現(xiàn)沖突，則以term值較大的信息為準(zhǔn)。
Raft還采用了心跳包和超時(shí)時(shí)間，leader為了保持自己的權(quán)威，必須不停地向集群中的其他節(jié)點(diǎn)發(fā)送心跳包；一旦某個(gè)follow在超過了指定時(shí)間（election timeout）仍沒有收到心跳包，則就認(rèn)為leader已經(jīng)掛掉，自己進(jìn)入candidate狀態(tài)，開始競(jìng)選leader。
不難發(fā)現(xiàn)，raft的leader選舉是通過heartbeat和隨機(jī)timeout時(shí)間來實(shí)現(xiàn)的；而日志復(fù)制（log replication）階段是以強(qiáng)leadership來實(shí)現(xiàn)的：leader接收client的command，append到自身log中，并將log復(fù)制到其他follower；而raft對(duì)安全性的保證是通過只有l(wèi)eader可以決定是否commit來實(shí)現(xiàn)的。
詳細(xì)的競(jìng)選、復(fù)制等過程，這里不再贅述，有興趣的同學(xué)可以參考筆者之前的文章（https://yq.aliyun.com/articles/675031 ）。值得一提的是，raft中的leader選舉過程和leader任期內(nèi)的正常運(yùn)作過程都比較簡(jiǎn)單，復(fù)雜的其實(shí)是leader的變更過程。
然而，雖然raft的原理機(jī)制與paxos不盡相同，但二者所解決的問題，以及所采取的折中權(quán)衡策略，可以認(rèn)為是類似的。也就是說raft仍然只能解決故障錯(cuò)誤，仍然強(qiáng)調(diào)了故障容錯(cuò)與安全性、一致性，弱化了liveness和可用性。
?
Raft協(xié)議概覽（https://ongardie.net/static/raft/userstudy/raft.pdf）
PBFT
自從1982年Lamport提出拜占庭將軍問題之后，雖然有諸多關(guān)于拜占庭容錯(cuò)解決方案的討論，但長(zhǎng)期以來，此類問題的解決方案都效率低下、運(yùn)行緩慢、復(fù)雜度過高，直到1999年Castro和Liskov提出實(shí)用拜占庭容錯(cuò)算法（Practical Byzantine Fault Tolerance），首次將此類算法的復(fù)雜度從指數(shù)級(jí)降到了多項(xiàng)式級(jí)，TPS可以達(dá)到幾千，也使得節(jié)點(diǎn)故意作惡類問題在實(shí)踐中找到了可行的解法。可以證明，如果系統(tǒng)內(nèi)作惡節(jié)點(diǎn)數(shù)目不超過總節(jié)點(diǎn)數(shù)目的1/3，PBFT算法就能生效。
在PBFT中，所有的節(jié)點(diǎn)被順序編號(hào)，其中1個(gè)是leader，其余的都是backup。系統(tǒng)內(nèi)的所有節(jié)點(diǎn)間都互相通訊，依據(jù)多數(shù)原則達(dá)成一致。PBFT中的每輪共識(shí)都被稱為一個(gè)view，而在不同的view之間，leader都會(huì)發(fā)生變化；如果超過給定的時(shí)間，leader沒有廣播出消息，則leader就會(huì)通過view change協(xié)議被替換掉。通過這種replica timeout機(jī)制，保證了crashed或malicious leader會(huì)被檢測(cè)出來，從而通過重新選舉新的leader，而進(jìn)入到新的view中。
如圖所示，從客戶端發(fā)起請(qǐng)求到收到回復(fù)結(jié)果，可以分為5個(gè)階段，而共識(shí)過程采用了3階段協(xié)議。下面簡(jiǎn)要敘述5個(gè)階段的大致過程：
?
PBFT算法正常運(yùn)作過程（http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf）
PBFT基于異步網(wǎng)絡(luò)模型做到了安全性，但需要依賴消息超時(shí)時(shí)間來做周期性的同步。因?yàn)椴捎昧薼eader-based方案，消息同步過程很快，也做到了完全的順序?qū)懭搿５莑eader的重新選舉過程很困難，某些惡意leader可以在臨近timeout窗口期時(shí)才發(fā)送消息，這樣會(huì)導(dǎo)致系統(tǒng)嚴(yán)重緩慢。而利用這一不利特點(diǎn)，可以攻擊網(wǎng)絡(luò)使正確的leader看起來也出問題，從而導(dǎo)致無窮無盡的leader選舉過程。
PBFT與Paxos、Raft相比，所能處理應(yīng)對(duì)的問題更為完備，除了能應(yīng)對(duì)故障崩潰類錯(cuò)誤之外，還能處理存在“搗亂者”的惡意篡改類拜占庭錯(cuò)誤。然而，從所采取的折中權(quán)衡策略來看，PBFT仍然與Paxos、Raft很類似。從FLP的視角來看，PBFT同樣更關(guān)注容錯(cuò)性和安全性，而弱化了liveness。從CAP的角度，PBFT同樣強(qiáng)調(diào)網(wǎng)絡(luò)分區(qū)容錯(cuò)與一致性，而弱化了可用性。
即便如此，只要故障或作惡節(jié)點(diǎn)不超過總節(jié)點(diǎn)數(shù)的1/3，PBFT在實(shí)踐中還是有效可行的。而拜占庭容錯(cuò)算法（BFT）也不止PBFT一種，BFT類算法也在不斷進(jìn)化，如Lamport就提出過改進(jìn)版的Paxos算法BFT Paxos以處理拜占庭錯(cuò)誤，近來也有人結(jié)合PBFT與Raft提出了 BFT Raft 算法。但從問題領(lǐng)域與原理機(jī)制上來說，仍然與原有的思路和框架較為類似，不再一一贅述。
適用場(chǎng)景
從Paxos、Raft到PBFT，再到目前層出不窮的Paxos變種、Raft變種、BFT類混合新算法，分布式一致性算法在不斷發(fā)展、完善、進(jìn)化。甚至各大公司也在結(jié)合自己的業(yè)務(wù)實(shí)際，研發(fā)各種適合自己場(chǎng)景的分布式一致性算法。這些算法雖然并不完美，但都在適合自己場(chǎng)景的業(yè)務(wù)實(shí)踐中發(fā)揮著重大作用。那么這些算法的適用場(chǎng)景到底是什么？自身又有哪些局限性呢？
對(duì)于Paxos、Raft這類非BFT算法而言，只能處理機(jī)器硬件故障，而無法處理存在作惡節(jié)點(diǎn)的情況。顯然，這類非BFT算法只能運(yùn)行在非常可信的網(wǎng)絡(luò)環(huán)境中，比如公司內(nèi)部網(wǎng)絡(luò)中，在這樣的較為封閉的網(wǎng)絡(luò)中，訪問需要嚴(yán)格授權(quán)，從而保證各個(gè)節(jié)點(diǎn)的身份是已知的、可信的，基本排除了節(jié)點(diǎn)作惡的可能性，這類算法才能有效運(yùn)行。
而BFT類算法，對(duì)于網(wǎng)絡(luò)環(huán)境的要求不再那么苛刻，即使存在作惡節(jié)點(diǎn)，只要作惡節(jié)點(diǎn)數(shù)目不超過總節(jié)點(diǎn)數(shù)的1/3，整個(gè)系統(tǒng)依然是安全的。但問題就在于，你怎么知道網(wǎng)絡(luò)中到底有多少作惡節(jié)點(diǎn)？作惡節(jié)點(diǎn)占總節(jié)點(diǎn)的比例到底有多高？顯然，如果網(wǎng)絡(luò)的接入是需要權(quán)限控制的，那么這個(gè)問題就相對(duì)容易解決。比如10家業(yè)務(wù)關(guān)聯(lián)公司組成的聯(lián)盟網(wǎng)絡(luò)，只有這10家授權(quán)的公司才能訪問，即便里面有個(gè)別公司（少于3家）蓄意作惡、妄圖篡改數(shù)據(jù)，整個(gè)系統(tǒng)仍然是安全可靠的。在這種permissoned網(wǎng)絡(luò)中，隱含著對(duì)于網(wǎng)絡(luò)中可能作惡節(jié)點(diǎn)數(shù)目的預(yù)估，即便真的作惡了，也能方便快速地定位出其真實(shí)身份，間接提高了網(wǎng)絡(luò)的安全性。
局限性
然而，在permissonless（開放權(quán)限、無權(quán)限控制）的公有網(wǎng)絡(luò)中，BFT類算法很可能會(huì)有問題。因?yàn)?#xff0c;如果分布式網(wǎng)絡(luò)是開放的，誰(shuí)都能進(jìn)進(jìn)出出，而接入網(wǎng)絡(luò)系統(tǒng)的成本又很低，那么沒人知道網(wǎng)絡(luò)中到底可能有多少作惡節(jié)點(diǎn)，即便真有作惡，也很難定位出真實(shí)身份。比如，一種比較典型的女巫攻擊（Sybil attack）場(chǎng)景，作惡者可以通過大量偽造身份來控制集群中的大量節(jié)點(diǎn)，從而控制整個(gè)分布式網(wǎng)絡(luò)。
另外，BFT類算法最大的局限性還在于僅能協(xié)調(diào)少量的節(jié)點(diǎn)，如幾個(gè)到幾十個(gè)，若節(jié)點(diǎn)數(shù)目成千上萬(wàn)，整個(gè)系統(tǒng)的性能將會(huì)非常低下，甚至可能無法達(dá)成共識(shí)，從而影響系統(tǒng)的liveness和可用性。想必大家已經(jīng)注意到，在PBFT的三階段協(xié)議中，都需要多點(diǎn)廣播（multicast）：在pre-prepare階段，主節(jié)點(diǎn)向所有備節(jié)點(diǎn)廣播；在prepare節(jié)點(diǎn)，備節(jié)點(diǎn)向其他所有節(jié)點(diǎn)廣播；在commit階段，各個(gè)節(jié)點(diǎn)向其他所有節(jié)點(diǎn)廣播。由此可見，通訊次數(shù)的數(shù)量級(jí)是節(jié)點(diǎn)數(shù)目的平方，當(dāng)節(jié)點(diǎn)數(shù)目龐大時(shí)，這種兩兩廣播的機(jī)制將會(huì)是災(zāi)難，系統(tǒng)幾乎不可能在較短時(shí)間內(nèi)達(dá)成一致。
綜上可知，這些傳統(tǒng)的分布式一致性算法，無論是Paxos、Raft，還是PBFT，通常適用于存在權(quán)限控制的、節(jié)點(diǎn)數(shù)目較少的、較為可信的分布式網(wǎng)絡(luò)環(huán)境中。
在聯(lián)盟鏈中的應(yīng)用
事實(shí)上，這些傳統(tǒng)的一致性算法在區(qū)塊鏈時(shí)代也煥發(fā)了新的活力，得到了進(jìn)一步的認(rèn)識(shí)和使用。在網(wǎng)絡(luò)環(huán)境較為可信的聯(lián)盟鏈場(chǎng)景中，這些一致性算法得到了大量的應(yīng)用。聯(lián)盟鏈因如下特點(diǎn)而被業(yè)內(nèi)看好其應(yīng)用前景：
- 接入需授權(quán)：聯(lián)盟鏈并不完全對(duì)外開放，一般只有幾家或幾十家企業(yè)組成，只有經(jīng)過授權(quán)的公司或組織才能加入到網(wǎng)絡(luò)中，并且一般是實(shí)名認(rèn)證參與。
- 數(shù)據(jù)保護(hù)：聯(lián)盟鏈信息數(shù)據(jù)并不完全對(duì)外開放，而只有授權(quán)方可見。這對(duì)于保護(hù)行業(yè)或公司的數(shù)據(jù)安全比較重要，如跨境轉(zhuǎn)賬中的交易信息等對(duì)于銀行業(yè)至關(guān)重要、鏈上稅務(wù)系統(tǒng)中的稅務(wù)信息也很敏感。
- 可監(jiān)管：聯(lián)盟鏈中一般可以設(shè)立監(jiān)管觀察節(jié)點(diǎn)，對(duì)于敏感信息進(jìn)行審計(jì)與監(jiān)管，滿足合法性要求。
在當(dāng)前階段，聯(lián)盟鏈不失為快速落地、解決行業(yè)痛點(diǎn)的不錯(cuò)選擇，也是對(duì)區(qū)塊鏈后續(xù)發(fā)展的積極探索。因?yàn)槁?lián)盟鏈需要授權(quán)才能參與，這其實(shí)相當(dāng)于已經(jīng)提前建立了相當(dāng)程度的信任，網(wǎng)絡(luò)環(huán)境較為可信，網(wǎng)絡(luò)中的惡意行為和攻擊行為發(fā)生的可能性都非常低，并且即便發(fā)生也很容易快速追責(zé)。因此在這樣的場(chǎng)景下，傳統(tǒng)的一致性算法也可以得到應(yīng)用。比如：
- HyperLedger Fabric(https://www.hyperledger.org/projects/fabric ) 在v1.0中可以使用Solo和Kafka pubsub系統(tǒng)來實(shí)現(xiàn)ordering；在v1.4版本也引入了Raft算法（https://hyperledger-fabric.readthedocs.io/en/release-1.4/orderer/ordering_service.html ）；目前這些均是CFT類算法，而raft的引入主要也是為后期支持BFT類算法鋪平道路（ Raft is the first step toward Fabric’s development of a byzantine fault tolerant (BFT) ordering service. As we’ll see, some decisions in the development of Raft were driven by this. ）。
- R3 Corda(https://www.r3.com/corda-platform/ )也采用了可插拔式的共識(shí)算法設(shè)計(jì)，不僅可以選擇高速度、高可信環(huán)境的Raft算法，也可以選擇低速度、低可信環(huán)境的BFT類算法（https://docs.corda.net/key-concepts-notaries.html ）。
- 以太坊企業(yè)聯(lián)盟EEA(https://entethalliance.org/ )也支持BFT類算法、Raft算法，以及PoET算法（https://entethalliance.org/wp-content/uploads/2018/05/EEA-TS-0001-0-v1.00-EEA-Enterprise-Ethereum-Specification-R1.pdf ）。
- 螞蟻區(qū)塊鏈BaaS平臺(tái)（https://tech.antfin.com/blockchain )也采用了PBFT算法。
Permissionless網(wǎng)絡(luò)的挑戰(zhàn)
那么我們?nèi)滩蛔∫獑?#xff0c;如果網(wǎng)絡(luò)是完全開放的、無需權(quán)限許可的（permissionless），誰(shuí)都可以隨時(shí)進(jìn)出，那么整個(gè)系統(tǒng)還能在有限的時(shí)間內(nèi)達(dá)成一致嗎？如果網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目不再是幾十個(gè)，而是一萬(wàn)個(gè)，那么又該如何協(xié)調(diào)這些數(shù)量龐大的節(jié)點(diǎn)呢？
在回答這些問題之前，其實(shí)更應(yīng)該反問：為什么需要網(wǎng)絡(luò)是完全開放、無需許可的？什么場(chǎng)景會(huì)需要一萬(wàn)個(gè)節(jié)點(diǎn)？這到底是偽需求，還是真實(shí)存在的場(chǎng)景？這個(gè)問題的答案直接關(guān)系到區(qū)塊鏈中公有鏈的存在意義，而要回答這個(gè)問題，我們需要回到分布式系統(tǒng)的初心和目的。
去中心化的意義
我們?yōu)槭裁葱枰植际较到y(tǒng)？顯然，這個(gè)問題不難回答，通常的理解，分布式系統(tǒng)可以增強(qiáng)容錯(cuò)能力（Fault tolerance)，畢竟系統(tǒng)依賴眾多不同的節(jié)點(diǎn)，而眾多節(jié)點(diǎn)同時(shí)失敗的可能性遠(yuǎn)低于一個(gè)節(jié)點(diǎn)發(fā)生故障的可能性；另外，分布式系統(tǒng)還可以抵御攻擊（Attack resistance），畢竟攻擊或摧毀眾多節(jié)點(diǎn)的難度遠(yuǎn)大于攻擊單點(diǎn)的難度。
然而，以上這些依然是局限在物理硬件的維度，都是用來降低機(jī)器物理硬件發(fā)生故障的可能性，而沒有考慮“人”的因素。如果一個(gè)系統(tǒng)足夠重要，比如電子貨幣系統(tǒng)等，除了考慮機(jī)器故障之外，更多需要考慮的是人的因素。部署節(jié)點(diǎn)的人會(huì)不會(huì)故意作惡呢？如何防止系統(tǒng)內(nèi)不同節(jié)點(diǎn)間的腐敗串通呢？
如下圖所示，以太坊創(chuàng)始人Vitalik Buterin曾經(jīng)深入地探討過去中心化的含義。如果說傳統(tǒng)的分布式系統(tǒng)做到了architectural decentralization（系統(tǒng)有多少物理機(jī)器構(gòu)成？系統(tǒng)能夠容忍最多多少臺(tái)機(jī)器同時(shí)故障？），考慮的是fault tolerance和attack resistance；那么現(xiàn)在我們需要考慮的是如何做到political decentralization，如何能夠collusion resistance? 到底有多少人或組織最終控制了系統(tǒng)內(nèi)的節(jié)點(diǎn)？如何防止這些人之間的腐敗串通？如果說傳統(tǒng)的分布式系統(tǒng)考慮的問題是網(wǎng)絡(luò)或機(jī)器硬件的可信，那現(xiàn)在我們想考慮的是“人的可信”：是否存在這樣的技術(shù)手段來防范人的作惡？如何確保重要網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)不被一個(gè)人或一個(gè)組織惡意控制？
?
去中心化的三個(gè)維度（https://medium.com/@VitalikButerin/the-meaning-of-decentralization-a0c92b76a274）
值得一提的是，這個(gè)問題的必要性依然充滿爭(zhēng)議，很多人根本不曾想過、或者認(rèn)為根本沒有必要考慮人的腐敗串通，也可能認(rèn)為對(duì)于這個(gè)問題技術(shù)也無能為力，畢竟這與我們生活的真實(shí)世界相去甚遠(yuǎn)。我們生活在一個(gè)中心化平臺(tái)擁有極高聲譽(yù)、提供信用背書、控制一切規(guī)則流程的世界，比如極少有人擔(dān)心銀行會(huì)故意做假賬，侵吞你在銀行的資產(chǎn)，畢竟大家普遍認(rèn)為銀行是值得信賴的。如果認(rèn)為銀行都不可信，那很可能一切商業(yè)活動(dòng)都無法開展。
然而，我們只是“假設(shè)”銀行是可信的，在“信任”與“懷疑”之間，我們只是被迫選擇了信任，畢竟不信任銀行，商業(yè)活動(dòng)無法開展，經(jīng)濟(jì)也將停滯。然而實(shí)際上，并沒有切實(shí)可行的措施來向所有人“證明”銀行是可信的。
如果你認(rèn)為這個(gè)問題是必要的、有意義的，那么能否找到一種解決方案，可以讓這個(gè)世界變得更可信，讓你不再需要“被迫相信”某個(gè)陌生人，而是提供一種“證明”，足以確保與你交易的某個(gè)陌生人是可信的？Don’t Trust, Please Verify. 你不需要相信我，你也不必相信我，你只需要去驗(yàn)證我。
如果要解決這個(gè)問題，所有人的身份應(yīng)該是對(duì)等的，每個(gè)人都可以平等、自由地參與決策過程，每個(gè)人都可以自由地進(jìn)出“議會(huì)”，這事實(shí)上是一種技術(shù)上的democracy，隱含的技術(shù)要素是：網(wǎng)絡(luò)必須是permissonless的，誰(shuí)都可以隨時(shí)加入隨時(shí)離開；節(jié)點(diǎn)之間必須是對(duì)等的，可以直接通訊；無任何中間人，無任何中心權(quán)威存在，完全的點(diǎn)對(duì)點(diǎn)（peer to peer）；每個(gè)節(jié)點(diǎn)都有希望成為記賬者。
因?yàn)榫W(wǎng)絡(luò)無權(quán)限控制，完全的開放、透明、民主，所以參與的節(jié)點(diǎn)數(shù)目很可能非常眾多，節(jié)點(diǎn)作惡的可能性也很高。那如何在這種permissionless的、節(jié)點(diǎn)數(shù)目眾多、存在較大作惡可能的分布式網(wǎng)絡(luò)環(huán)境中，通過某種機(jī)制協(xié)調(diào)節(jié)點(diǎn)間的行為，保證整個(gè)系統(tǒng)的一致性呢？顯然，如前所述的一致性算法并不能做到這一點(diǎn)，我們需要尋求新的解法。
另外，去中心化可能是區(qū)塊鏈領(lǐng)域最充滿爭(zhēng)議的詞匯。一些人認(rèn)為去中心化是區(qū)塊鏈的價(jià)值觀和公有鏈的靈魂與存在前提，應(yīng)該盡可能地保證系統(tǒng)的去中心化程度；而另一些人認(rèn)為完全的去中心化過于理想、不太可能實(shí)現(xiàn)，應(yīng)該結(jié)合實(shí)際場(chǎng)景，在兼顧效率的情況下考慮弱中心化或多中心化。這里拋開價(jià)值判斷，單純從技術(shù)角度理性分析，去中心化程度越高確實(shí)系統(tǒng)的安全性會(huì)越高，所以在公有鏈的系統(tǒng)設(shè)計(jì)中確實(shí)應(yīng)該盡可能地保證系統(tǒng)的去中心化程度。不過，結(jié)合Vitalik Buterin對(duì)于去中心化含義的詮釋，在追求去中心化的過程中，我們不應(yīng)該停留在單純的表面上看起來的去中心化，而應(yīng)該綜合考慮去中心化的各個(gè)維度，結(jié)合實(shí)際情況，做出必要的trade-off。
PoW
對(duì)開放網(wǎng)絡(luò)中的分布式一致性問題比較創(chuàng)新的解法當(dāng)屬比特幣中的Proof-of-work（PoW、工作量證明）機(jī)制。
不得不提的Bitcoin
2008年10月31日，中本聰發(fā)表了比特幣白皮書《Bitcoin: A Peer-to-Peer Electronic Cash System》，天才般地為此類問題提供了創(chuàng)造性的解決思路，使得協(xié)調(diào)復(fù)雜網(wǎng)絡(luò)環(huán)境中的成千上萬(wàn)節(jié)點(diǎn)成為可能。事實(shí)上，中本聰并不是為了解決這個(gè)技術(shù)問題而發(fā)表了比特幣白皮書。相反，中本聰想象的更加宏大，他創(chuàng)造性地發(fā)明了比特幣這種完全點(diǎn)對(duì)點(diǎn)的電子現(xiàn)金系統(tǒng)，以消除傳統(tǒng)支付中需要依賴的可信第三方中間人，而在實(shí)現(xiàn)的過程中恰好依賴并解決了開放網(wǎng)絡(luò)中眾多節(jié)點(diǎn)間的一致性問題。也可以說，比特幣所解決的最核心問題是點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中電子貨幣的雙花問題。然而，比特幣的實(shí)現(xiàn)機(jī)制絕不僅僅是分布式網(wǎng)絡(luò)技術(shù)問題，還結(jié)合了密碼學(xué)、經(jīng)濟(jì)學(xué)、博弈論等思想，并以一種非確定性的概率方式實(shí)現(xiàn)了節(jié)點(diǎn)間的一致性。因此，單純地稱為算法已不太能準(zhǔn)確表達(dá)其含義，可能叫作共識(shí)機(jī)制（consensus mechanism）更為恰當(dāng)，因?yàn)槠鋵?shí)現(xiàn)的確依賴了一整套的完整策略與制度。這里我們不過多闡述比特幣的思想意義與實(shí)現(xiàn)細(xì)節(jié)，而僅聚焦在其共識(shí)機(jī)制的實(shí)現(xiàn)上。
比特幣實(shí)際上是電子簽名鏈，幣的owner可以通過對(duì)前一個(gè)交易的哈希值和下一個(gè)owner的公鑰進(jìn)行簽名，并將簽名添加到幣的末尾，從而實(shí)現(xiàn)轉(zhuǎn)賬。接受者通過校驗(yàn)簽名來驗(yàn)證幣的owner構(gòu)成的鏈。然而，問題是幣的接受者沒有辦法確保幣的owner沒有進(jìn)行雙花（double-spend），即有可能某個(gè)幣的owner將同一個(gè)幣先后轉(zhuǎn)給了兩個(gè)人。因此我們需要一種機(jī)制來讓接收者確保幣的前一個(gè)owner并沒有在此之前將幣轉(zhuǎn)給其他人，為了確保這一點(diǎn)，唯一的辦法就是讓所有人知曉所有的交易。而在無可信第三方的情況下，想實(shí)現(xiàn)這一點(diǎn)，所有的交易必須廣播給所有人。因此我們需要一個(gè)系統(tǒng)，其中的所有參與者對(duì)他們接收幣的順序達(dá)成一致，形成唯一的順序記錄歷史。不難發(fā)現(xiàn)，這其實(shí)就是分布式一致性問題。
而比特幣提供的方案就是需要一個(gè)由所有節(jié)點(diǎn)組成的時(shí)間戳服務(wù)器（timestamp server），時(shí)間戳服務(wù)器可以對(duì)交易區(qū)塊的哈希加蓋時(shí)間戳，并將該哈希廣播出去。每一個(gè)時(shí)間戳都在其哈希中包含了前一個(gè)時(shí)間戳，從而形成一條鏈，而每一個(gè)新的時(shí)間戳都是對(duì)其之前所有時(shí)間戳的確保與強(qiáng)化。為了在點(diǎn)對(duì)點(diǎn)的網(wǎng)絡(luò)中實(shí)現(xiàn)分布式的時(shí)間戳服務(wù)器，比特幣采用了工作量證明機(jī)制（proof-of-work，PoW）。PoW涉及在做哈希運(yùn)算時(shí)，需要尋找某個(gè)值，使得總體哈希值的開頭前幾位都為零，而所需要的平均工作量隨著零位數(shù)目的增多而指數(shù)增加。另外，該哈希沒有任何規(guī)律，為了保證開頭前幾位為零，只能通過暴力的方法不斷地隨機(jī)試錯(cuò)。一旦消耗了足夠的CPU的算力，找到了符合條件的哈希值，則該區(qū)塊就無法變更，除非再耗費(fèi)CPU重做一遍。
另外，PoW也解決了大多數(shù)決策問題。在比特幣中，最長(zhǎng)的那條鏈就代表了大多數(shù)的決策。因?yàn)槿绻\(chéng)實(shí)的節(jié)點(diǎn)控制了大部分的算力，則誠(chéng)實(shí)的鏈就會(huì)快速增長(zhǎng)并超過其他鏈。如果想篡改某個(gè)過去的區(qū)塊，攻擊者必須重做相應(yīng)的區(qū)塊和其后面所有區(qū)塊的PoW任務(wù)，然后追趕并趕超誠(chéng)實(shí)的節(jié)點(diǎn)。這種難度是非常巨大的，從數(shù)學(xué)上不難證明，隨著后續(xù)節(jié)點(diǎn)數(shù)目的增多，較慢的攻擊者想追趕上來的概率指數(shù)下降，一般認(rèn)為經(jīng)過6個(gè)區(qū)塊之后，想追趕上來幾乎是不可能的。另外，PoW任務(wù)的難度并不是固定的，而是用移動(dòng)平均的方法動(dòng)態(tài)調(diào)整的，這主要是考慮到硬件運(yùn)算速率的提高和挖礦人數(shù)的增減變化，算的快就加大難度、算的慢就減小難度，通過動(dòng)態(tài)調(diào)節(jié)難度使得比特幣的出塊時(shí)間大致穩(wěn)定在10分鐘左右。
整個(gè)網(wǎng)絡(luò)的運(yùn)行過程如下：
?
比特幣交易過程（https://www.giottus.com/Bitcoin）
關(guān)于交易、挖礦等細(xì)節(jié)，這里不過多闡述，有興趣的同學(xué)可以參考筆者之前的入門介紹文章（https://www.atatech.org/articles/126343 ）。簡(jiǎn)而言之，在比特幣中總是以最長(zhǎng)鏈的信息為準(zhǔn)，若某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)了比自己更長(zhǎng)的鏈會(huì)自動(dòng)切換到最長(zhǎng)的鏈工作。
我們?nèi)滩蛔∫獑?#xff0c;既然PoW成本如此之高，那如何激勵(lì)大家貢獻(xiàn)算力、成為節(jié)點(diǎn)，以保證整個(gè)比特幣網(wǎng)絡(luò)的安全呢？比特幣中提供了兩種激勵(lì)策略：
這些激勵(lì)策略也隱含地鼓勵(lì)了節(jié)點(diǎn)保持誠(chéng)實(shí)，若某個(gè)貪婪的攻擊者真的擁有了過半的CPU算力，他不得不做出選擇：到底是篡改交易記錄，把他已經(jīng)花出去的比特幣再轉(zhuǎn)回來呢？還是老老實(shí)實(shí)地挖礦賺錢新幣和手續(xù)費(fèi)呢？很可能，老老實(shí)實(shí)地挖礦是更有利的，畢竟能賺到的幣比其他所有節(jié)點(diǎn)加起來都要多；而破壞比特幣體系也將會(huì)破壞自身財(cái)富的有效性，畢竟若比特幣不再可靠，其價(jià)值也會(huì)迅速崩潰。這里多提一點(diǎn)，攻擊者并不像一般人想象的那樣可以為所欲為、任意篡改或偽造交易記錄，他能做的只可能是將其最近花出去的比特幣偷回來。
PoW為什么有效？
比特幣在沒有任何組織或團(tuán)體維護(hù)的情況下，僅僅依靠社區(qū)志愿者自發(fā)維護(hù)，穩(wěn)定運(yùn)行了10年之久，期間從未發(fā)生過重大問題，這不能不說是個(gè)奇跡，也足以證明了比特幣背后共識(shí)機(jī)制的有效性。我們?nèi)滩蛔∫獑?#xff0c;為什么比特幣能夠做到？為什么比特幣背后的共識(shí)機(jī)制能夠如此有效？bitnodes數(shù)據(jù)顯示目前比特幣節(jié)點(diǎn)數(shù)目超過1萬(wàn)（比特幣節(jié)點(diǎn)類型較多，不同口徑數(shù)量可能不一致，這里僅考慮全節(jié)點(diǎn)）。為什么比特幣能夠在permissionless的網(wǎng)絡(luò)環(huán)境中，協(xié)調(diào)上萬(wàn)的節(jié)點(diǎn)保持一致性？
筆者粗淺的認(rèn)為，可能有以下幾個(gè)原因：
- 有效的激勵(lì)策略：通過激勵(lì)策略有效地激勵(lì)了更多節(jié)點(diǎn)參與到比特幣的點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中，節(jié)點(diǎn)越多比特幣網(wǎng)絡(luò)越安全。
- PoW：挖礦出塊需要消耗CPU算力，人為地制造障礙、增加成本，提高了攻擊者的作惡成本。
- 博弈論思想：激勵(lì)策略也考慮了博弈平衡，理性節(jié)點(diǎn)保持誠(chéng)實(shí)的收益更大。
- 通訊效率：比特幣節(jié)點(diǎn)間的通訊效率并不低效，大家可能注意到其中也涉及到了交易和區(qū)塊的廣播，不過這種廣播并非是兩兩廣播，而是由某個(gè)節(jié)點(diǎn)（發(fā)生交易或算出PoW的節(jié)點(diǎn)）將信息廣播到其他所有節(jié)點(diǎn)。另外，交易廣播并不要求觸達(dá)所有節(jié)點(diǎn)，只要有許多節(jié)點(diǎn)接受，不久之后就會(huì)被打包。2014年也有Miller等人（Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin）嚴(yán)格證明，消息復(fù)雜度并不隨網(wǎng)絡(luò)大小而增大，而是一個(gè)常數(shù)。另外，區(qū)塊廣播也容許消息丟失，若某個(gè)節(jié)點(diǎn)未收到某個(gè)區(qū)塊，則當(dāng)它接收到下個(gè)區(qū)塊時(shí)，會(huì)意識(shí)到自己遺漏了上個(gè)區(qū)塊，而主動(dòng)向其他節(jié)點(diǎn)請(qǐng)求該區(qū)塊。
- 概率性的一致性：相比其他一致性算法，比特幣的共識(shí)機(jī)制最特別的是不再追求確定性的一致性，而是追求概率性的一致性。當(dāng)某個(gè)區(qū)塊剛被挖出的時(shí)候，其包含的交易信息并非被所有節(jié)點(diǎn)最終確認(rèn)、其包含的數(shù)據(jù)并非是最終一致性的結(jié)果，還是有可能被攻擊者篡改的；但是隨著后續(xù)節(jié)點(diǎn)數(shù)目的增多，這種被篡改的可能性指數(shù)下降，最終一致性的概率顯著增大；一旦后續(xù)節(jié)點(diǎn)超過6個(gè)（也就是經(jīng)過約60分鐘），這種一致性就可以被認(rèn)為是確定的、最終的。
顯然，比特幣的共識(shí)機(jī)制不再拘泥于分布式算法層面，而是包含了更多經(jīng)濟(jì)學(xué)、博弈論、概率論等思想，因此可能叫作共識(shí)機(jī)制更為恰當(dāng)。不過，我們?nèi)匀豢梢詫⒈忍貛诺腜oW共識(shí)機(jī)制放到一致性問題的框架內(nèi)來思考，從FLP和CAP的角度來看：
綜合來看，不難看出，比特幣的PoW共識(shí)機(jī)制在FLP和CAP的限制下，做到了比較好的折中權(quán)衡，在實(shí)踐中確實(shí)提供了開放復(fù)雜網(wǎng)絡(luò)中分布式一致性問題的可行解法，比特幣近十年來的穩(wěn)定可靠運(yùn)行也有力地證明了這一點(diǎn)。
另外，比特幣的PoW算法也被Miller等人（https://socrates1024.s3.amazonaws.com/consensus.pdf ：Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin）嚴(yán)謹(jǐn)?shù)胤治霾⒆C明：
- 比特幣網(wǎng)絡(luò)可以看作是由近似無窮節(jié)點(diǎn)組成的，每個(gè)節(jié)點(diǎn)貢獻(xiàn)一小部分算力，并且相應(yīng)地每個(gè)節(jié)點(diǎn)都有較小概率可以創(chuàng)造區(qū)塊。
- PoW算法依賴于同步網(wǎng)絡(luò)模型。在該模型中，若網(wǎng)絡(luò)延遲為0，則算法可以容忍50%錯(cuò)誤；而以目前真實(shí)觀測(cè)的網(wǎng)絡(luò)延遲來看，比特幣可以容忍49.5%的錯(cuò)誤；若網(wǎng)絡(luò)延遲等于區(qū)塊時(shí)間（即10分鐘），則只能容忍33%的錯(cuò)誤；若網(wǎng)絡(luò)延遲接近無窮，則算法的容錯(cuò)也趨近于0。
- 比特幣PoW算法具有擴(kuò)展性（scalable），這是因?yàn)楣沧R(shí)時(shí)間和消息復(fù)雜度都與網(wǎng)絡(luò)大小（網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目）無關(guān)，而只與錯(cuò)誤節(jié)點(diǎn)的相應(yīng)算力有關(guān)，可以認(rèn)為是一個(gè)無量綱常數(shù)。
可見，PoW算法不僅在實(shí)踐中可靠，在理論上也能經(jīng)受考驗(yàn)。PoW算法采用了同步模型與隨機(jī)概率來規(guī)避FLP的確定性異步模型不可能定理。而PoW獨(dú)立于網(wǎng)絡(luò)大小的可擴(kuò)展性，與PBFT算法O(n2)復(fù)雜度相比優(yōu)勢(shì)巨大：節(jié)點(diǎn)越多，系統(tǒng)效率并未降低，而系統(tǒng)卻更安全。
PoW到底是什么？
我們?nèi)滩蛔∫獑?#xff0c;PoW機(jī)制到底有何神奇之處呢？
其實(shí)，大家可能也意識(shí)到了，PoW的思想并不高深，事實(shí)上也并非是中本聰首創(chuàng)。早在1993年這一思想就被提出用于對(duì)抗垃圾郵件(Pricing via Processing or Combatting Junk Mail)，但直到中本聰創(chuàng)造比特幣之前，這一思想都尚未得到廣泛應(yīng)用。PoW思想的精髓就在于故意制造障礙、增加參與者的成本，以盡量降低參與者的惡意企圖。比如要求請(qǐng)求者做些額外的工作以檢測(cè)DDoS攻擊、垃圾郵件等，也比如最常見的登錄網(wǎng)站需要輸入驗(yàn)證碼，也是為了增加登錄成本，防止網(wǎng)站被攻擊。這類任務(wù)最核心的特征是非對(duì)稱：對(duì)于服務(wù)請(qǐng)求者來說，完成任務(wù)必須有一定難度；而對(duì)服務(wù)提供者來說，驗(yàn)證任務(wù)必須很簡(jiǎn)單快速。對(duì)于比特幣PoW而言，顯然符合非對(duì)稱性：不斷試錯(cuò)，尋找使哈希符合條件的nonce（隨機(jī)數(shù)）需要消耗大量算力，而驗(yàn)證尋找到的nonce是否符合條件只需要做一次簡(jiǎn)單的哈希運(yùn)算驗(yàn)證即可。
比特幣的PoW本質(zhì)上是one-CPU-one-vote，一個(gè)CPU投一票。為什么選擇CPU，而不是IP地址呢？這仍然是基于任務(wù)難度考慮，若是one-IP-one-vote，則系統(tǒng)可以被擁有大量IP地址的人（如ip供應(yīng)商）輕易控制。相對(duì)而言，至少在當(dāng)時(shí)（尚未出現(xiàn)ASIC和FPGA）CPU仍然是比較昂貴的硬件，想擁有大量的算力（CPU+電力）并不容易。當(dāng)然，這其實(shí)也隱含地為比特幣的價(jià)值提供了現(xiàn)實(shí)錨定：虛擬的貨幣體系通過算力找到了現(xiàn)實(shí)物理世界的價(jià)值錨定，雖然在很多人看來這種算力的消耗是毫無意義、浪費(fèi)能源的。
也有很多人提出如何降低比特幣的挖礦成本，當(dāng)然這種思考嘗試有其積極意義，這種工作量證明的成本需要適宜：難度過大、成本過高確實(shí)浪費(fèi)能源較多，不過比特幣網(wǎng)絡(luò)的安全性也得到了提高；難度過小、成本過低則會(huì)起不到防攻擊的目的，進(jìn)而也會(huì)降低比特幣網(wǎng)絡(luò)的安全性。這其實(shí)是一個(gè)需要做tradeoff的問題，也是一個(gè)偏主觀的價(jià)值判斷，取決于大眾對(duì)比特幣的認(rèn)識(shí)和定位。價(jià)值判斷總是充滿了主觀偏見，目前對(duì)于比特幣的爭(zhēng)論如此之大，其實(shí)也正是因?yàn)樯鐣?huì)大眾尚未達(dá)成共識(shí)，尚未構(gòu)建出對(duì)于比特幣未來共同一致的想象。
簡(jiǎn)言之，比特幣的PoW是一整套的機(jī)制，包含了技術(shù)上的權(quán)衡、經(jīng)濟(jì)和博弈的考量，這一整套的策略和機(jī)制共同保障了比特幣網(wǎng)絡(luò)的安全可靠。
PoW機(jī)制的局限性
凡事沒有完美，PoW機(jī)制也不可例外地存在局限，其實(shí)從大家對(duì)比特幣的諸多批評(píng)也可見一二，通常地大家認(rèn)為PoW機(jī)制存在以下局限性：
PoS
在這些新的解決思路中，無疑最引人注目的就是Proof-of-stake（PoS、權(quán)益證明），同樣面對(duì)開放復(fù)雜網(wǎng)絡(luò)中的一致性問題，提出了全新的解決方案。
基本思想
2011年在bitcointalk論壇一個(gè)名為QuantumMechanic的用戶率先提出了proof-of-stake的思想（https://bitcointalk.org/index.php?topic=27787.0 ），而后不斷發(fā)展完善，得到越來越多人的信賴。
PoS的基本思想大致如下：
- 所有節(jié)點(diǎn)不再同時(shí)競(jìng)爭(zhēng)挖礦，而是每次僅有1個(gè)節(jié)點(diǎn)做驗(yàn)證者：在比特幣網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都需要做PoW任務(wù)，也就是說都需要做復(fù)雜的哈希運(yùn)算而消耗大量CPU算力，而只有最先找到答案的節(jié)點(diǎn)才能獲得獎(jiǎng)勵(lì)。這種所有節(jié)點(diǎn)間的同時(shí)競(jìng)爭(zhēng)挖礦無疑需要消耗大量資源，那么是否可以每次只有一個(gè)節(jié)點(diǎn)工作呢？如果可以，那怎么選定這個(gè)幸運(yùn)兒呢？PoS中不再需要挖礦，不再有miner，而是每次只需要選出一個(gè)節(jié)點(diǎn)作為validator去驗(yàn)證區(qū)塊的有效性。如果某個(gè)節(jié)點(diǎn)被選為validator來驗(yàn)證下一個(gè)區(qū)塊，它將驗(yàn)證該區(qū)塊內(nèi)的所有交易是否有效。如果所有交易都驗(yàn)證有效，則該節(jié)點(diǎn)對(duì)該區(qū)塊進(jìn)行簽名，并添加到區(qū)塊鏈上。作為回報(bào)，該validator將會(huì)收到這些交易相關(guān)的交易費(fèi)用。顯然，在PoS中每次共識(shí)只有一個(gè)節(jié)點(diǎn)付出了勞動(dòng)，且該勞動(dòng)非常輕松，從而達(dá)到了節(jié)約資源的目的。
- 想成為validator必須提供保證金：為了防止validator作惡，想成為validator必須提前往指定賬戶存入代幣作為保證金或抵押擔(dān)保金，一旦被發(fā)現(xiàn)作惡，則保證金即會(huì)被罰沒，而誠(chéng)實(shí)工作將會(huì)得到激勵(lì)。顯然，只要作惡帶來的收益不超過保證金額度，節(jié)點(diǎn)就會(huì)老老實(shí)實(shí)地保持誠(chéng)實(shí)。
- 被選為validator并不是完全隨機(jī)的，而是被選定概率與提供的保證金金額成正比：例如Alice提供100個(gè)幣的保證金，而Bob提供500個(gè)幣的保證金，則Bob被隨機(jī)選為validator從而產(chǎn)出下一個(gè)區(qū)塊的概率是Alice的5倍。這其實(shí)就類似于股份制公司，按照出資比例來劃分發(fā)言權(quán)、最終受益權(quán)等，大股東出資多、承擔(dān)責(zé)任大、相應(yīng)的回報(bào)也大。
?
PoW與PoS對(duì)比圖（https://hackernoon.com/consensus-mechanisms-explained-pow-vs-pos-89951c66ae10）
不難發(fā)現(xiàn)，PoS也是采用了經(jīng)濟(jì)和博弈的思想，通過激勵(lì)策略和懲罰機(jī)制來確保了網(wǎng)絡(luò)的安全可靠。
PoS為什么有效？
PoS協(xié)議仍然符合傳統(tǒng)的拜占庭容錯(cuò)算法研究的結(jié)論。目前圍繞PoS的研究可以分為兩條主線：一條圍繞同步網(wǎng)絡(luò)模型、一條圍繞部分異步網(wǎng)絡(luò)模型。而基于鏈的PoS算法幾乎總是依賴于同步網(wǎng)絡(luò)模型，并且其有效性與安全性可以像PoW算法一樣被嚴(yán)格證明（https://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf ）。
另外，從CAP的角度來看，基于鏈的PoS算法與PoW算法類似，也是盡可能地做到了容錯(cuò)性，另外在可用性與一致性之間，更多地保證了可用性。
如果說傳統(tǒng)的一致性算法（Paxos、Raft和PBFT）實(shí)現(xiàn)的是確定性的最終性(finality)或一致性，那么PoS與PoW類似，轉(zhuǎn)而尋求概率性的最終一致性。從傳統(tǒng)CAP的視角，這其實(shí)是對(duì)一致性的弱化，然而從實(shí)踐可行性的視角來看，也是一種全新的思維和突破。
而從PoS的設(shè)計(jì)策略來看，也可以分為兩大陣營(yíng)（https://arxiv.org/pdf/1710.09437.pdf ）：
- 一類是如前所述的chain-based PoS，主要是模仿PoW機(jī)制，通過偽隨機(jī)地把區(qū)塊創(chuàng)造權(quán)分配給stakeholders來模擬挖礦過程，典型代表如PeerCoin、Blackcoin等。其安全性與有效性可以參考類比pow來看。
- 另一類是BFT based PoS，基于近30年來的BFT類一致性算法研究。基于BFT算法來設(shè)計(jì)PoS的思想最初在Tendermint中提出，以太坊2.0中的Casper也遵從了這一傳統(tǒng)并做了一些修改完善。這類PoS的安全性與有效性可以參考BFT類算法來看，如可以從數(shù)學(xué)上證明，只要協(xié)議參與者的2/3以上節(jié)點(diǎn)都誠(chéng)實(shí)地遵照協(xié)議，不管網(wǎng)絡(luò)延遲有多大，算法都能保證最終狀態(tài)不會(huì)出現(xiàn)沖突區(qū)塊。不過此類算法也并不完美，特別是針對(duì)51%攻擊問題，也尚未完全解決，目前該領(lǐng)域仍然處于開放探索階段。
PoS的爭(zhēng)論
PoS的思想并不復(fù)雜，而其中比較容易被詬病的恰恰就是這種與現(xiàn)實(shí)世界類似的按出資比例獲取收益的制度。大家對(duì)現(xiàn)實(shí)世界的馬太效應(yīng)已經(jīng)非常警惕，這種制度顯然容易帶來富者越富、窮者越窮的結(jié)果：擁有更多代幣的人，將會(huì)有更多機(jī)會(huì)成為validator，從而參與網(wǎng)絡(luò)并獲得更多收益。
然而，對(duì)這一問題的看法爭(zhēng)議很大，很多人提出了完全不同的看法，認(rèn)為PoS相比PoW更公平、更有助于對(duì)抗中心化趨勢(shì)。理由主要是：PoW挖礦依賴現(xiàn)實(shí)世界的物理硬件和電力資源，而這很容易帶來規(guī)模經(jīng)濟(jì)（Economies of scale）優(yōu)勢(shì)。購(gòu)買10000臺(tái)礦機(jī)的公司相比購(gòu)買1臺(tái)礦機(jī)的個(gè)人更有議價(jià)權(quán)，甚至可以自主研發(fā)成本更低的礦機(jī)；而擁有10000臺(tái)礦機(jī)的礦場(chǎng)，對(duì)電費(fèi)的議價(jià)權(quán)也更高，甚至可以搬遷到電費(fèi)便宜的國(guó)家和地區(qū)的電站旁邊，甚至可以自建成本更低的電站。由此帶來的后果就是越龐大的組織的綜合挖礦成本越低，而這正是現(xiàn)實(shí)世界真實(shí)已經(jīng)發(fā)生的事實(shí)。相比之下，PoS不需要依賴現(xiàn)實(shí)硬件，不存在規(guī)模經(jīng)濟(jì)優(yōu)勢(shì)，在不考慮價(jià)格操縱的情況下，買1個(gè)幣的價(jià)格和買10000個(gè)幣的價(jià)格是線性增加的，從這個(gè)角度理解，PoS可能更公平，更有助于去中心化。
對(duì)PoS的另一個(gè)擔(dān)憂是其安全性，畢竟PoS不再像PoW那樣做復(fù)雜的CPU運(yùn)算以證明自己。在PoW中，若想發(fā)動(dòng)攻擊，需要控制51%的算力（近來也有研究發(fā)現(xiàn)只需25%算力即有可能攻擊成功），這也就意味著需要擁有大部分的礦機(jī)和算力資源。而在PoS中，若想控制整個(gè)體系，需要擁有51%的代幣。究竟哪個(gè)更安全？其實(shí)也不太好講，不過可以從現(xiàn)實(shí)世界的例子來看，如果比特幣算法切換為PoS，則控制比特幣體系需要大約比特幣市值的一半，大概是400~1600億美金（比特幣價(jià)格區(qū)間5000~20000美金），顯然這一數(shù)字遠(yuǎn)遠(yuǎn)高于礦機(jī)成本，想擁有這么大資金量發(fā)動(dòng)攻擊幾乎是不可能的，從這個(gè)角度來講，PoS可能更安全。
除此之外，PoS因?yàn)椴渴鸪杀竞艿?#xff08;對(duì)硬件要求很低），在真實(shí)世界中會(huì)導(dǎo)致代幣非常容易分叉，從而產(chǎn)生一堆山寨幣，而PoW不存在這個(gè)問題。因?yàn)镻oW依賴硬件挖礦，若想把比特幣的某個(gè)參數(shù)改改，這很容易；但真想跑起來，則需要大量算力的支持，需要爭(zhēng)取大量miner的支持，比如bitcoin cash從bitcoin中分叉出來就歷經(jīng)波折。而PoS完全沒這個(gè)顧慮，隨便某個(gè)人都可以下載開源代碼、隨意改下，拉幾個(gè)節(jié)點(diǎn)就可以聲稱自己創(chuàng)造了一種全新的代幣，比如從EOS（代幣名）中可以輕易分叉出幾十上百個(gè)山寨兄弟幣，每個(gè)都聲稱自己很獨(dú)特。這確實(shí)是事實(shí)，不過也不太容易說孰好孰壞。
PoS的改進(jìn)優(yōu)化
PoS機(jī)制中最關(guān)鍵的當(dāng)屬下一個(gè)區(qū)塊validator或creator的選擇機(jī)制，究竟誰(shuí)來做這個(gè)幸運(yùn)兒？前文所說的根據(jù)賬戶資金按比例按概率選擇其實(shí)是最簡(jiǎn)單的一種方式，這種方式確實(shí)容易導(dǎo)致有錢人獲得一勞永逸的收益，從而損害網(wǎng)絡(luò)中其他參與者的積極性。目前有很多種思路來改善這一問題，其中比較有意思的是coin age-based方法，在選擇creator的時(shí)候，除了考慮資金量，還會(huì)考慮coin age（幣齡）。所謂的coin age指的是幣在某個(gè)賬戶上的停留時(shí)間，比如1個(gè)幣轉(zhuǎn)入指定賬戶經(jīng)過10天，可以認(rèn)為幣齡是10，而每次幣發(fā)生變動(dòng)幣齡都會(huì)從0開始重新計(jì)算。通過這樣，可以限制大資金量節(jié)點(diǎn)頻繁成為creator，比如可以設(shè)定幣齡達(dá)到30才有機(jī)會(huì)成為creator，而成為creator之后幣齡立即清零。這其實(shí)是限制了大參與者的利益，為其他中小參與者提供了更多的參與機(jī)會(huì)。
基于PoS改進(jìn)的比較有名的方案當(dāng)屬Delegated Proof-of-Stake（DPoS），其中采用了代理人委托機(jī)制。在DPoS中不再是所有節(jié)點(diǎn)都有可能成為creator，而是節(jié)點(diǎn)間相互投票，只有得票最高的一些節(jié)點(diǎn)才可能參與區(qū)塊創(chuàng)造過程。具體如下：
- 代理人的職責(zé)包含保證自身節(jié)點(diǎn)持續(xù)運(yùn)行、收集交易信息并打包到區(qū)塊中、簽名驗(yàn)證并廣播區(qū)塊、解決網(wǎng)絡(luò)中可能存在的一致性問題。
- 對(duì)于大多數(shù)DPoS鏈來說，網(wǎng)絡(luò)中的所有持幣人（token holders）都可以向代理人投票，且投票權(quán)與持幣數(shù)量成正比。用戶也可以不直接投票，而把投票權(quán)委托給其他人來代表他們投票。
- 投票是動(dòng)態(tài)的、可變的，意味著某個(gè)代理人隨時(shí)可能被選進(jìn)來或選出去。而一旦某個(gè)代理人被發(fā)現(xiàn)作惡或欺詐，就將失去收入和名譽(yù)，這就起到了激勵(lì)代理人保持誠(chéng)實(shí)、保證網(wǎng)絡(luò)安全的目的。代理人可以將收到的區(qū)塊獎(jiǎng)勵(lì)按比例分給向他投票的用戶（這其實(shí)相當(dāng)于賄選，在有些方案中不被允許）。
- 不像傳統(tǒng)的PoS，代理人不再需要持有大量的代幣，而是必須相互競(jìng)爭(zhēng)從持幣者那里爭(zhēng)取投票。
- DPoS限制了交易區(qū)塊的驗(yàn)證者人數(shù)，這相當(dāng)于犧牲了一定程度的去中心化，但卻帶來了效率的提升，因?yàn)榫W(wǎng)絡(luò)達(dá)成共識(shí)所需的工作量大幅降低。
?
DPoS選舉validator/witness過程（https://www.nichanank.com/blog/2018/6/4/consensus-algorithms-pos-dpos）
不難發(fā)現(xiàn)，DPoS通過引入投票機(jī)制，盡可能地保證了節(jié)點(diǎn)的廣泛參與；而對(duì)validator數(shù)目的限制（一般是21-101個(gè)），盡可能地提高了系統(tǒng)的運(yùn)行效率。雖然充滿很大爭(zhēng)議，DPoS仍然不失為一種可行的解法，越來越多的區(qū)塊鏈系統(tǒng)也在嘗試對(duì)其進(jìn)行改進(jìn)和探索。
在公有鏈中的應(yīng)用
在公有鏈中，眾多項(xiàng)目都采用了PoS機(jī)制，比較有名的有：
- 以太坊（Ethereum：https://www.ethereum.org/ ）：目前階段以太坊仍然采用的是PoW挖礦機(jī)制，不過作為以太坊的創(chuàng)始人和公有鏈領(lǐng)域的領(lǐng)軍人物Vitalik Buterin對(duì)于PoS機(jī)制顯然更為青睞，也多次闡述過PoS的設(shè)計(jì)哲學(xué)（https://medium.com/@VitalikButerin/a-proof-of-stake-design-philosophy-506585978d51 ），以及PoS相比PoW的優(yōu)勢(shì)（https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ#what-are-the-benefits-of-proof-of-stake-as-opposed-to-proof-of-work ）。目前以太坊正在開發(fā)基于PoS的Casper協(xié)議（https://arxiv.org/pdf/1710.09437.pdf ），預(yù)計(jì)將于今年下半年發(fā)布，這種從PoW到PoS的轉(zhuǎn)變也標(biāo)志著以太坊進(jìn)入2.0時(shí)代。如下圖所示，在以太坊2.0 phase0階段，將會(huì)發(fā)布采用Casper協(xié)議的PoS beacon chain，作為coordination layer(https://github.com/ethereum/wiki/wiki/Sharding-roadmap )。
?
以太坊2.0 layers和phases(https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/)
- EOS(https://eos.io/ )：作為DPoS思想的提出者Daniel Larimer發(fā)起了EOS公有鏈項(xiàng)目，其中眾多節(jié)點(diǎn)會(huì)一起競(jìng)爭(zhēng)，期望成為擁有記賬權(quán)的21個(gè)Supernodes中的其中一員。這種類似現(xiàn)實(shí)世界議會(huì)制度的設(shè)計(jì)引起了非常大的爭(zhēng)議，而超級(jí)節(jié)點(diǎn)的競(jìng)選也可能蘊(yùn)含著巨大的商業(yè)利益，這些都已經(jīng)超越了技術(shù)討論的范疇，在此不做過多討論。
Proof of X?
其實(shí)，PoS機(jī)制的興起除了其本身具備的低成本、高效率、去中心化等特點(diǎn)之外，還在于它打開了一扇新的大門——基于博弈論機(jī)制來設(shè)計(jì)如何降低中心化風(fēng)險(xiǎn)的一系列技術(shù)，如何預(yù)防中心化壟斷巨頭的形成，以及在已有巨頭的情況下如何防范它們損害網(wǎng)絡(luò)（ Proof of stake opens the door to a wider array of techniques that use game-theoretic mechanism design in order to better discourage centralized cartels from forming and, if they do form, from acting in ways that are harmful to the network）。
而隨著近年來區(qū)塊鏈（特別是公有鏈）的蓬勃發(fā)展，其他各種Proof of機(jī)制也層出不窮。從這里面的諸多機(jī)制中都可以看到PoS思想的影子，即如何從經(jīng)濟(jì)角度和博弈視角來設(shè)計(jì)制度盡可能地保證去中心化、安全性與高效率。下面對(duì)這些機(jī)制做簡(jiǎn)要說明：
- Leased Proof of Stake:持幣量非常低的眾多節(jié)點(diǎn)可以將代幣出租給其他節(jié)點(diǎn)，從而形成合力，增加成為validator的幾率；而一旦選舉勝出得到獎(jiǎng)勵(lì)，則按比例分配手續(xù)費(fèi)，其實(shí)與礦池的思想比較類似。
- Proof of Elapsed Time:所有節(jié)點(diǎn)都必須等待一定的時(shí)間才能成為記賬者，而等待時(shí)間是完全隨機(jī)的。而要想保證公平，核心的兩個(gè)問題是：如何保證等待時(shí)間確實(shí)是完全隨機(jī)的？如何保證某個(gè)節(jié)點(diǎn)真的等待了指定的時(shí)間？目前的解法依賴于Intel的特殊CPU硬件Intel SGX 系統(tǒng)，目前通常也僅能應(yīng)用在permissioned網(wǎng)絡(luò)環(huán)境中，如前所述的以太坊企業(yè)聯(lián)盟EEA中。
- Proof of Activity:PoA同時(shí)結(jié)合了PoW和PoS的思想。在PoA中，起始過程與PoW類似，仍然是miners間競(jìng)爭(zhēng)解題挖礦，只不過所挖的區(qū)塊僅僅包含頭信息和礦工地址。而一旦區(qū)塊被挖出，則系統(tǒng)自動(dòng)切換成PoS模式，區(qū)塊頭信息指向一個(gè)隨機(jī)的持幣者（stakeholder），由該持幣者來驗(yàn)證該pre-mined區(qū)塊。
- Proof of Importance:有感于PoS機(jī)制傾向于鼓勵(lì)人持幣而不是流通、也容易導(dǎo)致富者越富的問題，PoI在計(jì)算節(jié)點(diǎn)對(duì)系統(tǒng)的重要性上吸納了更多的維度：除了考慮幣的數(shù)量、幣在賬戶上的停留時(shí)間之外，還考慮了交易對(duì)手（與其他賬戶的凈交易越多分?jǐn)?shù)越高）以及最近30天交易數(shù)目和大小（交易越頻繁、數(shù)額越大分?jǐn)?shù)越高）。
- Proof of Capacity:也稱作Proof of Space，思想與PoW類似，只是不再以CPU算力為衡量標(biāo)準(zhǔn)，而是以存儲(chǔ)空間來衡量。
- Proof of Burn:礦工必須燒毀一定量的代幣，即將一定量的代幣轉(zhuǎn)入eater address(黑洞地址，只進(jìn)不出，即私鑰未知的地址)，以此來證明自己。本質(zhì)上與PoW的思想接近，只是工作量證明消耗了算力資源，而PoB直接消耗了代幣本身。
- Proof of Weight:PoWeight是在PoS考慮代幣量的基礎(chǔ)之上，增加考慮了更多的權(quán)重因子。比如FileCoin（IPFS分布式文件系統(tǒng)上的代幣）考慮了你擁有的IPFS數(shù)據(jù)大小；其他的一些權(quán)重因子也包含但不限于Proof-of-Spacetime、Proof-of-Reputation等。
?
一致性算法概覽（https://101blockchains.com/consensus-algorithms-blockchain/）
不難發(fā)現(xiàn)，雖然這些Proof-of機(jī)制層出不窮、不盡相同，但其要解決的核心本質(zhì)問題是相同的，即：讓誰(shuí)來成為能夠記賬的幸運(yùn)兒？這些Proof-of機(jī)制只不過是采取了各種不同的策略來制定游戲規(guī)則，讓各個(gè)節(jié)點(diǎn)盡可能公平地證明自己，從中公平地選出幸運(yùn)兒。所有這些策略，包括基于CPU算力、持有代幣數(shù)量、存儲(chǔ)空間大小、隨機(jī)等待時(shí)間、銷毀代幣數(shù)量、節(jié)點(diǎn)活躍度、節(jié)點(diǎn)貢獻(xiàn)度等，都是在特定的場(chǎng)景下對(duì)于開放網(wǎng)絡(luò)中一致性問題的探索。
一切關(guān)乎信任
從PoW到PoS，再到Proof of "Everything you can think"，對(duì)于permissionless網(wǎng)絡(luò)中的一致性問題一直在探索中。“一致性”的內(nèi)涵也在發(fā)生變化，從傳統(tǒng)的如何防范網(wǎng)絡(luò)與機(jī)器硬件的故障，保證網(wǎng)絡(luò)節(jié)點(diǎn)間的數(shù)據(jù)一致性，到開放網(wǎng)絡(luò)中，如何防范網(wǎng)絡(luò)中人的作惡，保證網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)間的真實(shí)一致。可以說是從硬件的可信，邁進(jìn)了“人的可信”，公有鏈技術(shù)也被視為“信任的機(jī)器”。不過顯然，人的可信問題過于復(fù)雜，甚至也超越了單純的技術(shù)范疇。目前階段所能做到的也遠(yuǎn)遠(yuǎn)未能保證“人的可信”，更多的仍停留在人對(duì)于機(jī)器的信任、人對(duì)于“協(xié)議”的信任。不過可喜的是，我們終于邁出了這一步，開始直面這個(gè)棘手的問題，探索創(chuàng)新性的解法。
?
信任的機(jī)器（https://www.economist.com/leaders/2015/10/31/the-trust-machine）
總結(jié)
這個(gè)世界充滿了不確定性，計(jì)算機(jī)科學(xué)也一樣。從計(jì)算機(jī)出現(xiàn)開始，我們就不得不面對(duì)機(jī)器硬件的不確定性：意外故障可能帶來的問題。從互聯(lián)網(wǎng)興起開始，我們就不得不面對(duì)網(wǎng)絡(luò)的不確定性：通訊消息可能的延遲、亂序、丟失。而應(yīng)對(duì)不確定性問題最自然的解法就是冗余，通過大量節(jié)點(diǎn)來實(shí)現(xiàn)系統(tǒng)整體的安全性，避免單點(diǎn)故障，增強(qiáng)容錯(cuò)能力和抵御攻擊的能力。正是基于此，才帶來了大型分布式網(wǎng)絡(luò)的蓬勃發(fā)展，而如何在不確定的網(wǎng)絡(luò)和節(jié)點(diǎn)間尋找到某種確定性，協(xié)調(diào)眾多節(jié)點(diǎn)間的一致性，正是分布式一致性算法需要解決的問題。能夠應(yīng)對(duì)故障類錯(cuò)誤的CFT算法包括最經(jīng)典的Paxos算法和更簡(jiǎn)單的Raft算法，可以在網(wǎng)絡(luò)中正常節(jié)點(diǎn)超過一半的情況下保證算法的有效性。這類算法通常應(yīng)用在環(huán)境可信的封閉網(wǎng)絡(luò)中，協(xié)調(diào)幾個(gè)到幾十個(gè)節(jié)點(diǎn)間的一致性，如公司內(nèi)部的分布式存儲(chǔ)、分布式服務(wù)協(xié)議、分布式消息系統(tǒng)等。另外，也可以應(yīng)用于由少數(shù)機(jī)構(gòu)組成的需要授權(quán)才能訪問的聯(lián)盟鏈網(wǎng)絡(luò)中。
然而，不確定的不止是網(wǎng)絡(luò)與機(jī)器本身，還有控制網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的人的行為。如何在可能存在搗亂者惡意篡改數(shù)據(jù)或攻擊網(wǎng)絡(luò)的情況下，保證分布式網(wǎng)絡(luò)的一致性，正是拜占庭容錯(cuò)類算法BFT需要考慮的問題。BFT類算法中最常見的就是PBFT算法，可以在網(wǎng)絡(luò)中正常節(jié)點(diǎn)超過1/3的情況下保證算法的有效性。即便如此，PBFT對(duì)于網(wǎng)絡(luò)中惡意行為的應(yīng)對(duì)能力仍然是有限的，另外其性能也會(huì)隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增多而顯著下降。這些局限性也導(dǎo)致PBFT算法僅能用于環(huán)境較為可信的、有權(quán)限控制的網(wǎng)絡(luò)中，協(xié)調(diào)幾個(gè)到幾十個(gè)節(jié)點(diǎn)間的一致性，比如聯(lián)盟鏈場(chǎng)景中。
而在無權(quán)限控制的permissionless開放網(wǎng)絡(luò)中，不確定性更加嚴(yán)峻，特別是網(wǎng)絡(luò)節(jié)點(diǎn)背后的人的行為的不確定性。如何防止網(wǎng)絡(luò)中的控制人之間通過腐敗串通組成寡頭，從而控制網(wǎng)絡(luò)中的過半節(jié)點(diǎn)，達(dá)到控制、損害、攻擊網(wǎng)絡(luò)的目的，即是開放網(wǎng)絡(luò)需要考慮的問題。從這一角度看，開放網(wǎng)絡(luò)中的一致性還隱含了安全性的前提：即不僅要求節(jié)點(diǎn)間能夠達(dá)成共識(shí)，還要求該共識(shí)確實(shí)是由節(jié)點(diǎn)眾多控制人真實(shí)表達(dá)而形成的。而為了達(dá)到這種一致性與安全性，不僅需要實(shí)現(xiàn)物理硬件節(jié)點(diǎn)在結(jié)構(gòu)上的decentralization，還需要盡可能地保證節(jié)點(diǎn)背后實(shí)際控制人的decentralization。為了實(shí)現(xiàn)這一點(diǎn)，需要保證任何人都可以隨時(shí)部署運(yùn)行網(wǎng)絡(luò)協(xié)議而成為網(wǎng)絡(luò)中的節(jié)點(diǎn)、可以隨時(shí)進(jìn)出網(wǎng)絡(luò)；節(jié)點(diǎn)之間點(diǎn)對(duì)點(diǎn)通訊，無任何中心化控制節(jié)點(diǎn)；節(jié)點(diǎn)的角色是完全對(duì)等的，按照規(guī)則有公平的可能性參與記賬。而如何協(xié)調(diào)開放網(wǎng)絡(luò)中數(shù)量龐大的上萬(wàn)個(gè)節(jié)點(diǎn)間的行為，保證網(wǎng)絡(luò)的一致性與安全性，即是公有鏈共識(shí)機(jī)制要解決的問題。其中，最典型的當(dāng)屬比特幣首創(chuàng)的基于工作量證明的PoW共識(shí)機(jī)制，以及隨后興起的基于權(quán)益證明的PoS共識(shí)機(jī)制。這些共識(shí)機(jī)制不再局限于技術(shù)上的一致性本身，而是更多地引入了經(jīng)濟(jì)學(xué)和博弈論的思想，從經(jīng)濟(jì)和博弈的角度盡可能保證網(wǎng)絡(luò)的一致性與安全性。
從傳統(tǒng)的封閉分布式網(wǎng)絡(luò)環(huán)境中的一致性，到有權(quán)限控制的聯(lián)盟鏈場(chǎng)景中的一致性，再到無權(quán)限控制的公有鏈開放網(wǎng)絡(luò)環(huán)境中的共識(shí)機(jī)制，面對(duì)的問題越來越復(fù)雜，應(yīng)對(duì)的挑戰(zhàn)也越來越嚴(yán)峻。從單純的技術(shù)視角來看，其中對(duì)于consensus的研究是一脈相承的，這些一致性算法或共識(shí)機(jī)制同樣也都受到傳統(tǒng)分布式一致性理論研究中FLP impossibility和CAP theorem的制約。Paxos、Raft和PBFT都強(qiáng)調(diào)了fault tolerance與safety/consistency，而弱化了liveness與availability。而PoW與PoS則采用了全新的視角來考慮該問題，盡可能地保證了fault tolerance，以及l(fā)iveness與availability，放棄了對(duì)于安全性與一致性確定性的追求，而僅僅以概率性的方式追求最終的safety與consistency。
另外，對(duì)于consensus的思考，也在不斷深入，從單純的節(jié)點(diǎn)間的數(shù)據(jù)一致性，到強(qiáng)調(diào)節(jié)點(diǎn)背后的人之間的共識(shí)與認(rèn)同；從保證網(wǎng)絡(luò)與硬件的可信，到盡可能地確保組成網(wǎng)絡(luò)的節(jié)點(diǎn)背后的人的可信。雖然人與人之間的可信非常復(fù)雜，也超越了單純的技術(shù)范疇，可喜的是我們已經(jīng)走在路上，而目前在該領(lǐng)域正在進(jìn)行的創(chuàng)新性的積極探索，也必將讓世界變得更加可信。
注：本文篇幅較長(zhǎng)、寫作時(shí)間跨度較長(zhǎng)、本人水平也有限，所參考資料可能有疏漏或個(gè)人理解偏差，歡迎大家指正、討論、交流、建議，后續(xù)將進(jìn)行更新。
參考資料
?
https://yq.aliyun.com/articles/702243?utm_content=g_1000057448
總結(jié)
以上是生活随笔為你收集整理的从分布式一致性算法到区块链共识机制的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux crond 每分钟，每小时，
- 下一篇： 来及Java空间的传送门2