區(qū)塊鏈入門系列文章

區(qū)塊鏈基本概念和名詞解釋
P2P
共識算法
梅克爾-帕特里夏樹
從零開始搭建區(qū)塊鏈

前言

前文已經(jīng)說過，區(qū)塊鏈從本質(zhì)上來說就是基于P2P網(wǎng)絡(luò)的分布式系統(tǒng)，而對于分布式系統(tǒng)來說，如何維護各節(jié)點之間的狀態(tài)尤其重要，需要所有節(jié)點步調(diào)一致，這就需要設(shè)計相應(yīng)的算法或者協(xié)議來進(jìn)行管理。對于一個分布式系統(tǒng)來說，一定是遵從CAP定理的

• C: Consistency即一致性，全部節(jié)點在同一時間下數(shù)據(jù)是一致的
• A: Availability即可用性，整個分布式系統(tǒng)總是可用能提供正常服務(wù)的
• P: Partition tolerance即分隔容錯性，系統(tǒng)中某些節(jié)點故障時不影響整體的運行
  對于目前大部分的公鏈系統(tǒng)來看，他們都犧牲掉哪個特性了？明顯是一致性，它不要求數(shù)據(jù)實時一致，但最終都會一致，實現(xiàn)的是最終一致性。雖然犧牲了強一致性，但是AP兩塊板就被加到非常非常長，因為其節(jié)點數(shù)量可能比其他任何分布式系統(tǒng)的都要多，所以公鏈系統(tǒng)的可用性和容錯性是非常之高的。總之，數(shù)據(jù)是否一致對于區(qū)塊鏈來講不是最重要的，重要的是數(shù)據(jù)必須要按照固定的增量內(nèi)容和順序去一步步實現(xiàn)更改。
  這里還有個小問題，我覺得有必要再補充說明下。在接觸區(qū)塊鏈之前，如果有小伙伴對分布式系統(tǒng)已經(jīng)比較熟悉了的，肯定是知道一個名詞叫一致性算法，和區(qū)塊鏈中的共識算法有什么區(qū)別呢？我個人認(rèn)為是要實現(xiàn)一致性，必然需要經(jīng)歷共識的過程，所以共識算法可以簡單看作是一致性算法的一個步驟。
  本文就針對核心的共識部分，通過列舉一些常用的共識算法思想來幫助大家理解。

POW

全稱是Proof Of Work，即工作量證明。前文我們已經(jīng)講過了POW簡單來說就是解數(shù)學(xué)題，通過不斷地計算，最終得出正確答案的過程。

輸入數(shù)據(jù)是 “自增數(shù)+該區(qū)塊的Hash”，由于沒辦法預(yù)測輸出結(jié)果，且區(qū)塊的Hash是定值，所以只能不斷的用自增數(shù)去試，直到試出這個答案來

僅僅是這樣就能實現(xiàn)POW算法了嗎？其實上面計算nonce只是算法的一部分，該算法還約定了所有節(jié)點總是傾向于選擇更長鏈，即使用更長鏈的hash作為previousHash的區(qū)塊，以及只要這幾個條件都滿足了要無條件接受。只有以上幾點同時滿足，POW算法才能正常工作。
接下來再針對幾個維度看看POW算法的表現(xiàn)如何

• 安全性
  假設(shè)存在攻擊者且如果攻擊者節(jié)點的總算力是大于忠實節(jié)點的總算力，則攻擊者總會攻擊成功。為什么呢？不論忠實節(jié)點怎么出塊，都趕不上攻擊節(jié)點的篡改速度，因為攻擊節(jié)點算力高，算出nonce的速度更快，這也是常說的51%算力攻擊。攻擊者可能達(dá)到全網(wǎng)51%的算力嗎？不能說不可能，但絕對可以說很難，退一萬步看即便真達(dá)到51%算力了，那是多么恐怖的資源，攻擊區(qū)塊鏈帶來的收益恐怕無法填補收集這些資源帶來的損益。所以也從經(jīng)濟層面上制約了該情況的產(chǎn)生，而這也正是比特幣能穩(wěn)定運行十多年的原因。
  還有說POW算法不抗量子攻擊，因為量子計算機在做hash運算時效率非常高，所以傳統(tǒng)計算機要算很久的nonce對于量子計算機分分鐘就算出來了，所以不安全。論據(jù)沒錯，但是結(jié)論錯了，因為POW算法只是一種思想，并沒有非要綁定hash算法，如果量子計算真普及了，完全可以設(shè)計一種抗量子的數(shù)學(xué)模型來替代計算hash。
• 環(huán)保性
  不知道當(dāng)時中本聰選用該算法時有沒有預(yù)料到，若干年后竟然滋生出專門的“礦產(chǎn)業(yè)鏈”，當(dāng)中涉及了挖礦機房、礦卡、挖礦能源、礦機、挖礦木馬等，非常的em…。在越來越提倡環(huán)保的現(xiàn)代社會下，還存在消耗大量能源去挖礦的事情，怎么看都是很魔幻的。所以監(jiān)管的利劍也是可預(yù)見地?fù)]了下來，大力整治挖礦這種白白消耗能源地投機活動。所以POW算法在這個維度上看，算是飽受詬病的，這也為后來的更加環(huán)保的算法催生提供了前提條件。
• 穩(wěn)定性
  在談安全性的時候說了算法簡單，攻擊困難是比特幣能夠穩(wěn)定運行的前提，及必要條件，那要達(dá)到穩(wěn)定運行的效果是不是僅滿足安全性就好了呢？答案當(dāng)然是否定的。根據(jù)摩爾定律集成電路上可以容納的晶體管數(shù)目在大約每經(jīng)過18個月到24個月便會增加一倍。也就說，處理器的性能大約每兩年翻一倍，算力提升速度非常之快。十年前的計算機算力和十年后的相比就更是天差地別了，所以算hash的速度也是不一樣的，這就需要一定的規(guī)則去控制解題時間。比特幣的做法是動態(tài)調(diào)參計算位數(shù)，如果普遍計算時間大于10min則減少位數(shù)，反之則增加位數(shù)，使用讓計算時間保持在10min上下小范圍波動。這也是其能穩(wěn)定運行的重要原因。

POS

正如上面提到POW算法由于非常的不環(huán)保，催生了很多更加環(huán)保的共識算法，其中就有POS，Proof Of Stake，即權(quán)益證明算法。這個算法也沒有過多的數(shù)學(xué)論證，更多的是一種設(shè)計思想上的創(chuàng)新。既然POW是率先算出答案的才有絕對話語權(quán)，會讓參與區(qū)塊鏈的用戶陷入無盡的算力之爭，那就讓你直接不用算了，而是通過 “購買股份” 的方式來決定你的相對話語權(quán)。
可以想象成現(xiàn)實生活中我們使用金錢去購買某家公司的股權(quán)，占的股比越高在股東大會上的話語權(quán)也就越高。而放在區(qū)塊鏈的世界中，其典型的實踐就是通過質(zhì)押代幣來實現(xiàn)購買股份的目的，誰購買的代幣越多誰的話語權(quán)就更高，也就更容易被推選出來作為記賬者。如果被選舉成為記賬者，但是被發(fā)現(xiàn)作惡時，則會按照其行為扣除其質(zhì)押的代幣，來一定程度上遏制作惡行為的產(chǎn)生。
正是這樣簡單的機制，就避免了前面提到的能源浪費問題。但是POS也有一些缺點，比如在區(qū)塊鏈運行前期少數(shù)人才能挖礦，因為代幣都集中在少數(shù)人手里。還有很容易造成礦工囤積代幣，以期獲得更多的記賬權(quán)，進(jìn)而造成代幣越來越向更多持有者集中（有點像現(xiàn)實生活中的馬太效應(yīng)，錢越來越向少數(shù)富人集中）。

PBFT

前面提到的算法都是有效適用于海量節(jié)點的，也就是公鏈很適合使用的，但是忽略了一個使用場景就是聯(lián)盟鏈和私鏈。這種場景的節(jié)點數(shù)一般較少，且一般需要進(jìn)行身份驗證，所以對于共識算法來說就可以不依賴現(xiàn)實生活中的資源（如算力、代幣）作為因素來進(jìn)行，可以通過節(jié)點間純通信來實現(xiàn)強一致性。這種類型的算法往往需要全節(jié)點協(xié)商參與共識，就必然涉及到節(jié)點間的通信，在通信過程中如果節(jié)點數(shù)過多通信的次數(shù)過多，則很容易出現(xiàn)網(wǎng)絡(luò)風(fēng)暴進(jìn)而造成整個網(wǎng)絡(luò)癱瘓。
PBFT即Practical Byzantine Fault Tolerance，意為實用拜占庭容錯算法，在將這個算法前有必要先說一下什么是拜占庭容錯，而這就是為了解決著名的拜占庭將軍問題

拜占庭是一個地名，位于如今的土耳其的伊斯坦布爾，在古代是東羅馬帝國的首都。由于當(dāng)時拜占庭羅馬帝國國土遼闊，為了達(dá)到防御目的，每個軍隊都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭的時候，拜占庭軍隊內(nèi)所有將軍和副官必須達(dá)成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內(nèi)有可能存有叛徒和敵軍的間諜，左右將軍們的決定又?jǐn)_亂整體軍隊的秩序。在進(jìn)行共識時，結(jié)果并不代表大多數(shù)人的意見。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達(dá)成一致的協(xié)議，拜占庭問題就此形成。

而拜占庭容錯，是由Leslie Lamport在其論文中提出的分布式對等網(wǎng)絡(luò)通信容錯問題。在分布式計算中，不同的計算機通過通訊交換信息達(dá)成共識而按照同一套協(xié)作策略行動。但有時候，系統(tǒng)中的成員計算機可能出錯而發(fā)送錯誤的信息，用于傳遞信息的通訊網(wǎng)絡(luò)也可能導(dǎo)致信息損壞，使得網(wǎng)絡(luò)中不同的成員關(guān)于全體協(xié)作的策略得出不同結(jié)論，從而破壞系統(tǒng)一致性。
首先來看一看PBFT算法的幾個步驟示意圖

簡單解釋下，C代表客戶端，0、1、2、3代表服務(wù)節(jié)點（其中0表示主節(jié)點）。整個算法執(zhí)行過程中共產(chǎn)生5個狀態(tài)躍遷，request -> pre-prepare -> prepare -> commit -> reply，有點類似于分布式事務(wù)中的二階段提交。接下來分別對每個階段展開說明：

• request : 即客戶端向服務(wù)集群發(fā)送請求
• pre-prepare : 主節(jié)點收到請求后，會對本次請求生成一個唯一的編號n，然后把請求和編號n組合生成pre-prepare報文并廣播給所有成員節(jié)點（圖中表示3就是拜占庭節(jié)點，收到廣播后不響應(yīng)）
• prepare : 所有成員節(jié)點在收到pre-prepare報文后，首先需要驗證消息的正確性，即是否由主節(jié)點簽發(fā)，如果正確無誤，則將編號n由本節(jié)點簽名后生成prepare報文，再廣播給其他所有節(jié)點（包括主節(jié)點）
• commit : 所有節(jié)點收到prepare報文，首先校驗簽名是否由對應(yīng)節(jié)點簽發(fā)。然后統(tǒng)計收到的正確報文數(shù)量，若超過全部節(jié)點數(shù)量的2/3-1，則認(rèn)為請求是達(dá)成一致了的，即對所有節(jié)點廣播簽名后的commit報文
• reply : 所有節(jié)點收到commit報文，首先還是得校驗簽名是否由對應(yīng)節(jié)點簽發(fā)。其次統(tǒng)計收到的正確報文數(shù)量是否超過全部節(jié)點的2/3，是則說明請求已完成，構(gòu)建reply報文響應(yīng)給客戶端。客戶端則是判斷是否收到超過1/3+1的正確回復(fù)來判斷請求是否完成。

這里面涉及幾個問題：

• 為什么在判斷prepare報文的條件為是否超過2/3-1？
  因為PBFT算法規(guī)定在拜占庭節(jié)點（即非正常節(jié)點）不能超過所有節(jié)點的三分之一，否則無法完成共識。假設(shè)所有拜占庭節(jié)點在該階段均不正確響應(yīng)，也最多影響三分之一的數(shù)量，所以超過三分之二時則表示所有正常節(jié)點均已正常響應(yīng)。之所以還要減一是因為主節(jié)點在prepare階段沒有進(jìn)行廣播，所以減去主節(jié)點即可。
• 為什么客戶端是根據(jù)是否收到1/3+1個正確回復(fù)來判斷請求是否完成？
  因為客戶端對于服務(wù)端內(nèi)部的共識過程完全不關(guān)心也無法感知到，所以只需要考慮最壞情況，所有拜占庭節(jié)點都響應(yīng)了虛假的reply報文，只要有一個正常節(jié)點響應(yīng)了也說明請求是真的成功了。
• [靈魂拷問]為什么規(guī)定拜占庭節(jié)點不能超過總節(jié)點的1/3？
  設(shè)總結(jié)點數(shù)為n，拜占庭節(jié)點數(shù)為f，也就說至少n-f個節(jié)點在每個階段會正常廣播，而收到n-f個報文時無法判斷這里面是否含有拜占庭節(jié)點發(fā)的，最壞情況是其中有f個都來自拜占庭節(jié)點也不能影響共識，所以能列出不等式n-f-f>f => n≧3f+1
• 上述步驟中很關(guān)鍵的一步是主節(jié)點需要發(fā)出pre-prepare報文才能繼續(xù)下面的操作，那主節(jié)點就是拜占庭節(jié)點，故意不發(fā)送怎么辦？
  PBFT中有一個視圖輪換機制，設(shè)視圖編號為v，節(jié)點數(shù)為n，則當(dāng)前的主節(jié)點是 v mod n = i即節(jié)點i，而v始終是自增的，所以主節(jié)點是輪換著的。那何時輪換呢？答案是當(dāng)操作沒有正確處理時。就拿該問題的場景來舉例，主節(jié)點作惡故意不發(fā)送pre-prepare報文，勢必造成客戶端一直收不到響應(yīng)。而客戶端在一定時間內(nèi)未收到正確響應(yīng)會向其他節(jié)點發(fā)出請求，其他節(jié)點收到后會將v自增構(gòu)建出view-change報文進(jìn)行廣播，共識成功后，視圖輪換成功。另外所有從節(jié)點本身也維護了一個timeout計時器，如果長時間未收到主節(jié)點的報文也會發(fā)起視圖輪換。

Raft

上面介紹的PBFT算法在消息復(fù)雜度上比較高，因為其設(shè)計的是三階段共識，那有沒有復(fù)雜度相對低一點的共識算法呢，就是本節(jié)的主角Raft。對于Raft大家應(yīng)該都熟悉，因為它常常被用作各大中間件的一致性算法，如Zookeeper、Elasticsearch、Redis等。
Raft將節(jié)點分為三種狀態(tài)，分別是Follower、Candidate、Leader

• Follower：只能被動的接受來自Leader的指令，當(dāng)超時未收到Leader的消息時則自動切換為Candidate
• Candidate：只能向其他節(jié)點廣播選舉自己成為Leader的消息，如果獲取到超過半數(shù)的投票則切換為Leader
• Leader：負(fù)責(zé)處理請求，以及定時廣播心跳信息，防止Follower認(rèn)為自己掛掉了，進(jìn)而被替代掉

設(shè)想一個場景，Leader所在的主機網(wǎng)絡(luò)突然故障了，導(dǎo)致心跳包沒能及時廣播到Follower節(jié)點，所以Follower節(jié)點們紛紛超時后切換為Candidate節(jié)點發(fā)起了競選Leader的投票并成功選出了一個新Leader，此時原Leader的網(wǎng)絡(luò)恢復(fù)了，會發(fā)生怎樣的后果呢？Raft中有個Term的概念即任期，每一個Leader都有屬于自己的任期，而任期又始終是自增的。所以回到這個場景中，原Leader的任期肯定是小于新Leader的任期的，所以當(dāng)原Leader收到新Leader的廣播消息后會自動把自己降級為Follower，有效避免了沖突。

Raft的處理過程并沒有引入二階段提交，甚至是三階段提交的機制，因為Raft是“一言堂”所有的事兒只需要聽大哥安排就好。具體的事務(wù)在Raft中被視為一個個的“日志”，它是通過日志復(fù)制來進(jìn)行一致性處理的。
每條日志都包含有索引號以及產(chǎn)生時的任期號，是按順序排列的，一旦某條日志以及被復(fù)制到超過半數(shù)的節(jié)點上，則表示該日志已經(jīng)被提交，即可以對客戶端進(jìn)行響應(yīng)了。分布式系統(tǒng)中突然的網(wǎng)絡(luò)中斷是不可避免地，在出現(xiàn)頻繁的復(fù)制失敗、Leader選舉之后，節(jié)點之間的日志存儲情況可能天差地別，如下圖所示。

每一個方塊表示一個日志條目，里面的數(shù)字表示任期號，按照日志索引號順序排列著的，這里面就包含了如下異常情況：

• 存在缺少一些日志的節(jié)點（a-b）
• 存在有未提交日志的節(jié)點（c-d）
• 兩種情況均有的節(jié)點（e-f）

這種情況下，Raft會怎么處理呢？Leader節(jié)點會根據(jù)自身的最大索引日志向其他所有節(jié)點進(jìn)行AppendEntry RPC操作，內(nèi)容包含最大日志的索引號，而收到的節(jié)點如果發(fā)現(xiàn)和前一日志索引號存在斷層或不匹配則拒絕響應(yīng)，Leader只要收到任意拒絕響應(yīng)則將索引號前移一位后再次重試。所以針對上述情況是按照如下邏輯進(jìn)行處理的。

• 對于缺少日志就很好處理了，在不斷地重試過后總能找到最早地日志塊然后一個一個地向后補齊，如a的10，b的5-10
• 對于比Leader多的部分日志會被直接丟棄，如c的11，d的11-12，f的11
• 對于和Leader沖突部分的日志會被直接覆蓋，如e的6-7，f的4-10

那么問題又來了，按照上圖的情況，假如當(dāng)選的Leader是b，那豈不是很多日志都要被丟棄了？ 還記得前面說過有個日志提交的概念嗎，只要被復(fù)制到超過半數(shù)的節(jié)點上，該日志就屬于提交狀態(tài)的，是不會被覆蓋的，現(xiàn)在可以講Raft是如何實現(xiàn)這一機制的。在新Leader選舉時還會有一個額外的條件，即拉票節(jié)點是否包含有最大已提交日志塊，只有是的情況下才給其投票。可以看到任期6索引9就是被提交的最大日志塊，所以這種情況下能當(dāng)選Leader的，只有a、c、d以及當(dāng)前Leader這四個幾點可能會當(dāng)選Leader，所以此情況下b不可能當(dāng)選為Leader。
總來地說，Raft相對于PBFT高效且相對簡單，但缺點是并不能容忍作惡節(jié)點。

其他共識算法

隨著區(qū)塊鏈的熱度越來越高，對于共識算法的研究也是越來越廣泛深入，發(fā)明出的共識算法種類也是種類繁多。上文提到了，PBFT、Raft等強一致性算法無法適應(yīng)海量節(jié)點數(shù)量，甚至上百個節(jié)點數(shù)性能就已嚴(yán)重受到影響，所以絕大部分還是圍繞POX方向進(jìn)行展開，因為區(qū)塊鏈最大的應(yīng)用場景還是公鏈，其節(jié)點數(shù)都是非常龐大的。目前已知的大致有：

• POC：Proof Of Capacity，容量證明，為了改進(jìn)POW能耗高的問題，方法仍然是算題，但這些題可以通過存儲一系列的中間值來簡化，存儲的越多運算速度越快，所以最終是拼容量
• POA：Proof Of Authority，權(quán)威證明，其實和權(quán)益證明差不多，改進(jìn)了因為質(zhì)押代幣而造成的一系列問題，但是引入權(quán)威的概念可能會使去中心化程度不那么高。還有諸如POWeight、POR、POET都是這個范疇。
• POR：Proof Of Weight，權(quán)重證明，這個是在POS的基礎(chǔ)上引入了權(quán)重的概念，
• …

算法種類還有很多就不一一列舉了，如果有興趣進(jìn)一步了解的，可以跳轉(zhuǎn)這篇文章進(jìn)行查看。文章來源地址http://www.zghlxwxcb.cn/news/detail-404301.html

到了這里，關(guān)于區(qū)塊鏈入門系列之共識算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！