第11講深入?yún)^(qū)塊鏈技術(shù)三共識(shí)算法與分布式一致性

下載第11講|深入?yún)^(qū)塊鏈技術(shù)下載第11講|深入?yún)^(qū)塊鏈技術(shù)（三）：共識(shí)算法與分布式一致性算2018-04-18陳浩深入淺出區(qū)塊11:44大小共識(shí)機(jī)制的概念，我們?cè)谇懊娴奈恼隆皽\說(shuō)區(qū)塊鏈共識(shí)機(jī)制”中已經(jīng)講解了一部分，但是共識(shí)算法其實(shí)是一個(gè)非常大的話題，一篇文章肯沒(méi)有辦法做到面面俱全那么今天的內(nèi)容，我會(huì)將重點(diǎn)放在梳理技術(shù)的脈絡(luò)上，詳細(xì)分析的部分會(huì)少一點(diǎn)。如果你對(duì)共識(shí)算法有興趣的話，可以自行查找相關(guān)內(nèi)容，也可以和其他的資料進(jìn)行相互補(bǔ)充的閱讀。從相親大會(huì)說(shuō)起：分布式系統(tǒng)的模 為了讓你更容 大村子因?yàn)槿丝谠鲩L(zhǎng)變成11個(gè)小村落分散在地圖各地村落之間的通信只能依靠信鴿一只信鴿可能無(wú)法完全覆蓋所有村落，需要有中繼村落代為傳輸消息相親大會(huì)的舉辦權(quán)會(huì)為村子帶來(lái)巨大收益，為了產(chǎn)生合理的舉辦者，人們約定了幾條規(guī)則大會(huì)舉辦權(quán)從A和B兩個(gè)村子中產(chǎn)生，他們每一屆都是候選村投票時(shí)所有村落僅能投A或用投票的方式產(chǎn)生舉辦者，少數(shù)服從多數(shù)所有村子會(huì)為了舉辦權(quán)都會(huì)使出渾身解數(shù)，比如延遲發(fā)送投票結(jié)果、篡改別人的投票結(jié)果、假裝沒(méi)有接收到通知等等。其實(shí)這是一個(gè)典型的分布式系統(tǒng)，可以看成是我們簡(jiǎn)化版的區(qū)塊鏈網(wǎng)絡(luò)環(huán)境，那么這個(gè)分布式系統(tǒng)會(huì)遇到什么樣的問(wèn)題呢？分布式系統(tǒng)面臨的問(wèn)題分布式系統(tǒng)面臨了幾個(gè)問(wèn)題：一致性問(wèn)題，可終止性問(wèn)題、合法性問(wèn)題可終止性可以理解為系統(tǒng)必須在有限的時(shí)間內(nèi)給出一致性結(jié)果，合法性是指提案必須是系統(tǒng)內(nèi)的節(jié)點(diǎn)提出。當(dāng)然其中面對(duì)的最重要也是最基礎(chǔ)的問(wèn)題，就是我們常說(shuō)的一致性問(wèn)題。一致性是指在某個(gè)分布式系統(tǒng)中，任意節(jié)點(diǎn)的提案能夠在約定的協(xié)議下被其他所有節(jié)點(diǎn)所認(rèn)可。需要提醒你區(qū)分的一點(diǎn)是：這里的“認(rèn)可”表示所有節(jié)點(diǎn)對(duì)外呈現(xiàn)的信息一致，而不是對(duì)息的內(nèi)容認(rèn)可。一致性也分嚴(yán)格一致性最終一致性，這些我們?cè)诤笪臅?huì)談到我們回到上面的例子，我們提到解為提案所有的村子只能投A或B，其實(shí)這個(gè)投票的動(dòng)作可以在“投票過(guò)程被大家所認(rèn)可在“投票過(guò)程被大家所認(rèn)可”這個(gè)語(yǔ)境下，“被大家所認(rèn)可”表示某個(gè)村落投票的結(jié)果已被記錄，用于最后統(tǒng)計(jì)結(jié)果，而不是認(rèn)可投給A或者投給B，這也是我在上述強(qiáng)調(diào)你要意區(qū)分的一點(diǎn)那我們這里所說(shuō)的一致性到底體現(xiàn)在那里呢主要體現(xiàn)在下面兩種類型的問(wèn)題上非人為惡意的意外投票過(guò)程。非人為惡意篡改可歸類為信鴿半路掛掉、信鴿迷路、信送錯(cuò)目的地、信鴿送信途中下雨導(dǎo)致鴿延遲送達(dá)等等。這些對(duì)應(yīng)到分布式系統(tǒng)面臨的問(wèn)題就是：消息丟包、網(wǎng)絡(luò)擁堵、消息延遲、消息內(nèi)容校驗(yàn)失敗、節(jié)點(diǎn)宕機(jī)等。人為惡意篡改包括“精神分裂式投票”，中繼篡改上一個(gè)村落的投票信息。對(duì)應(yīng)到分布式系統(tǒng)面臨的問(wèn)題就是：消息被偽造、系統(tǒng)安全攻擊等等。發(fā)生的人為惡意篡改的過(guò)程就可以稱之為系統(tǒng)發(fā)生了拜占庭錯(cuò)誤（ByzantineFault)，問(wèn)題1我們已經(jīng)有較成熟的方案了。分布式系統(tǒng)本質(zhì)上是一種并行異步操作，如果通過(guò)心化的手段將系統(tǒng)中的“并行不確定”操作變更為“同步串行”操作就能解決上述的問(wèn)題比如讓第三方機(jī)構(gòu)介入托管所有人的投票；或者構(gòu)造一個(gè)不可偽造令牌，大家輪流將投票統(tǒng)一寫(xiě)到令牌上。這些也是現(xiàn)代分布式系統(tǒng)經(jīng)常使用的方法。但是這些方法有個(gè)缺陷，如果在分布式系統(tǒng)中被過(guò)多地使用以后，系統(tǒng)便會(huì)越來(lái)越像單點(diǎn)系統(tǒng)。我們?cè)O(shè)計(jì)分布式系統(tǒng)的初衷就是為了克服單點(diǎn)系統(tǒng)的可用性不足、擴(kuò)展性不好、單點(diǎn)性能上限等缺陷，這種退化的方案可能不是我們想要的。而問(wèn)題2要求設(shè)計(jì)拜占庭容錯(cuò)系統(tǒng)，這個(gè)在IT行業(yè)并不常見(jiàn)，因?yàn)槎鄶?shù)IT系統(tǒng)是中心的，所以如果我們想要解決問(wèn)算法2，這就引出了我們今天要介紹的共識(shí)算法與分布式一致我們?cè)诮榻B具體的分布式一致性算法之前，先介紹我們?cè)诮榻B具體的分布式一致性算法之前，先介紹兩個(gè)定理，做一下鋪墊第一個(gè)是FLP不可能性，簡(jiǎn)單來(lái)說(shuō)是：即使網(wǎng)絡(luò)通信完全可靠，只要產(chǎn)生了拜占庭錯(cuò)是，不存在一個(gè)通用的共識(shí)算法可以解決所有的拜占庭錯(cuò)誤。第二個(gè)是CAP理，CAP理是分布式系統(tǒng)領(lǐng)域最重要的定理之一，這個(gè)我們?cè)凇袄斫庑浴薄翱捎眯浴薄胺謪^(qū)容忍性”三者中，我們只能選擇兩個(gè)作為主要強(qiáng)化的點(diǎn)，另外一個(gè)必然會(huì)被弱化。我們由CAP定理可以推導(dǎo)嚴(yán)格一致性最終一致性。嚴(yán)格一致性是指在約定的時(shí)內(nèi)，通常是非常短、高精度的時(shí)間內(nèi)，系統(tǒng)達(dá)到一致性的狀態(tài)，這種系統(tǒng)很難實(shí)現(xiàn)，即使現(xiàn)也很難有高的性能所以人們從工程的角度提出了最終一致性，最終一致性不要求嚴(yán)格的短時(shí)間內(nèi)達(dá)到一致。了其他兩個(gè)指標(biāo)，我 相當(dāng)于讓一致性在時(shí)間上做了妥協(xié)。區(qū)塊鏈滿足了最終一致性，且處理過(guò)程時(shí)間比較長(zhǎng)可用性其實(shí)是傳統(tǒng)技后端架構(gòu)上非常重要的指標(biāo)，從單點(diǎn)到主備模式、從主備模式到地多活 再到現(xiàn)在的Paxos和Raft協(xié)議我們從軟件架構(gòu)上也經(jīng)歷了基于ESB的模塊化SOA模式，到無(wú)狀態(tài)的微服務(wù)架構(gòu)從程的角度來(lái)看，根據(jù)業(yè)務(wù)需求達(dá)到4個(gè)9、6個(gè)9就足夠了，只100%的可用性肯定比不了區(qū)塊鏈近分區(qū)容忍性在企業(yè)內(nèi)部極少出現(xiàn)，尤其是中心化的服務(wù)性應(yīng)用，所以很少考慮。鏈的P2P網(wǎng)絡(luò)環(huán)境十分復(fù)雜，所以必須要保證很高的分區(qū)容忍性。然而區(qū)通過(guò)以上我們可以發(fā)現(xiàn)比特幣、以太坊等公鏈?zhǔn)瞧馗呖捎眯?、分區(qū)容忍性（AP），滿足最終一致性（C）且TPS較低的分布式系統(tǒng)。所以如果有人號(hào)他們的區(qū)塊鏈能夠達(dá)到媲美中心化系統(tǒng)上萬(wàn)的TPS，先別著急投資，問(wèn)問(wèn)他技術(shù)是不是知道CAP定理，再問(wèn)問(wèn)他們的去中心化程度如何這點(diǎn)我們也可以從EOS等高性能的區(qū)塊鏈身上佐證，EOS全球只這點(diǎn)我們也可以從EOS等高性能的區(qū)塊鏈身上佐證，EOS全球只有21個(gè)記賬節(jié)點(diǎn)，而太坊全球有上萬(wàn)個(gè)節(jié)點(diǎn)可以隨時(shí)參記賬，所以越想去中心化，你的TPS就不可能高這也就是為什么EOS的TPS高，而以太坊的TPS接下來(lái)我來(lái)介紹一下經(jīng)典的分布式一致性算法和區(qū)塊鏈的共識(shí)算法。經(jīng)典的分布式一致性法在多數(shù)的論文中一般被叫做共識(shí)算法，在這里，我為了與區(qū)塊鏈的共識(shí)算法做出區(qū)別，以在命名上改成了分布式一致性算法但是它們要解決的問(wèn)題一樣的1.經(jīng)典的分布式一致性算經(jīng)典分布式一致性算法有Raft協(xié)議，Raft協(xié)議是一種強(qiáng)Leader的一致性算法，它的吞吐量基本就是Leader的吞吐量，它無(wú)法抵御節(jié)點(diǎn)惡意篡改數(shù)據(jù)的攻擊。稍微復(fù)雜一點(diǎn)的就是Paxos協(xié)議，Paxos能提供不同場(chǎng)合不同種類的一致性算法，所Paxos有很多變種，經(jīng)典Paxos是Leaderless的，有變種是強(qiáng)Leader型的，叫做有關(guān)Paxos的文獻(xiàn)非常豐富，這里就不贅述了以上兩種都是不提供拜占庭容錯(cuò)的系統(tǒng)，下面介紹一種具有拜占庭容錯(cuò)的一致性算法PBFT全稱實(shí)用性拜占庭容錯(cuò)系統(tǒng)（PracticalByzantineFaultTolerance,PBFT)，PBFT是一種狀態(tài)機(jī)，要求所有節(jié)點(diǎn)共同維護(hù)一個(gè)狀態(tài)，所有節(jié)點(diǎn)采取的行動(dòng)一致，PBFT常適合聯(lián)盟鏈等對(duì)性能具有較高要求的場(chǎng)合，超級(jí)賬本項(xiàng)目中的Fabric框架默認(rèn)采用的就是PBFT的修改版本2.區(qū)塊鏈共識(shí)算區(qū)塊鏈的共識(shí)算法，我在某些場(chǎng)合直接稱作基于經(jīng)濟(jì)學(xué)的博弈算，以區(qū)別于經(jīng)典分布一致性算法思路，它的整體思路就是讓攻擊者的攻擊成本遠(yuǎn)遠(yuǎn)大于收益區(qū)塊鏈中的共識(shí)算法目前具有工業(yè)成熟度的是PoW，另外兩種比較成熟的是PoSDPoS，其次還有一些變種和單一幣種使用的共識(shí)算法，例如Ripple共識(shí)、PoC共識(shí)（念性證明）、PoE共識(shí)（存在性證明）在使用PoW共識(shí)算法的情況下，容錯(cuò)閾值是50%，而PBFT及其變種的容錯(cuò)閾值是左右，這里的百分比是指作弊節(jié)點(diǎn)占全網(wǎng)節(jié)點(diǎn)比例PoX類的算法其實(shí)都延續(xù)了PoWPoX類的算法其實(shí)都延續(xù)了PoW的設(shè)計(jì)理念，相比較經(jīng)典分布式一致性算法，PoX類算法通概率選擇記賬者降低了潛在的提案者，另外是延長(zhǎng)了達(dá)成最終一致性的時(shí)間第一條降低了系統(tǒng)通信復(fù)雜度，每次記賬系統(tǒng)的確定性其實(shí)是概率確定的又由于被選需要付出成本，此處才提高了記賬成本閾值，結(jié)合區(qū)塊鏈的基礎(chǔ)代幣設(shè)計(jì)，是一個(gè)非常天的想法有關(guān)PoW、PoS、DPoS的內(nèi)容，我在后面會(huì)有專文介紹今天我們從相親大會(huì)開(kāi)始說(shuō)起，介紹了分布式系統(tǒng)所面臨的問(wèn)題，之后，我們又引出了區(qū)鏈所要解決的拜占庭容錯(cuò)問(wèn)題，并重點(diǎn)介紹了分布式系統(tǒng)的基本定理，最后我還介紹了經(jīng)共識(shí)算法和區(qū)塊鏈算法區(qū)塊鏈并沒(méi)有逃離分布式系統(tǒng)這個(gè)理論框架，希望今天的內(nèi)容能夠幫助你分辨出真實(shí)的區(qū)鏈項(xiàng)目。最后給你留一個(gè)思考題，區(qū)塊鏈行業(yè)有哪些公司使用了如PBFT、Paxos這樣的典共識(shí)算法呢？你可以給我留言，我們一起討論感謝你的收聽(tīng)，我們下期再見(jiàn)?版權(quán)歸極客邦科技所有，未經(jīng)許可不得傳播售賣(mài)。頁(yè)面已增加防盜追蹤，如有侵權(quán)極客邦將依法追究其法律責(zé)任上?版權(quán)歸極客邦科技所有，未經(jīng)許可不得傳播售賣(mài)。頁(yè)面已增加防盜追蹤，如有侵權(quán)極客邦將依法追究其法律責(zé)任上一第10|深入?yún)^(qū)塊鏈技術(shù)（二）：P2P網(wǎng)下一第12|深入?yún)^(qū)塊鏈技術(shù)（四）：PoW共精選留言阿2018-04-據(jù)我個(gè)人總結(jié)，聯(lián)盟鏈基本上使用PBFT及其變種，而公有鏈大多采用PoX算法，對(duì)嗎8作者回復(fù)