非拜占庭問題掺栅,采用帕克斯算法和RUFT算法;
拜占庭問題誉帅,采用拜占庭容錯算法淀散,進一步發(fā)展了優(yōu)化PBFT算法。
PBFT算法只適用于似有鏈和聯(lián)盟鏈蚜锨,公有鏈一般采用POW算法档插、POS算法和DPOS算法。
一亚再、PBFT算法
PBFT算法指實用拜占庭容錯算法郭膛,長期以來拜占庭問題的解決方案過于復雜,缺乏實用性氛悬,直到1999年P(guān)BFT算法提出则剃,才首次將拜占庭容錯算法的復雜度從指數(shù)級降低到了多項式級,目前已得到了廣泛應(yīng)用如捅。此算法可以保證背叛節(jié)點數(shù)不超過1/3的情況下忍级,保證信息的傳遞過程無法被篡改和破壞。PBFT算法采用了例如ISA簽名算法伪朽、消息驗證編碼和摘要等密碼學技術(shù)轴咱。
PBFT算法基本過程如下:
首先通過輪換或者隨機算法選出某個節(jié)點為主節(jié)點,此后只要主節(jié)點不切換則稱為一個試圖View烈涮,在某個試圖中請求發(fā)送給主節(jié)點朴肺,主節(jié)點負責廣播請求到所有其他副本節(jié)點,所有節(jié)點處理完請求將處理結(jié)果返回給客戶端坚洽,客戶端檢查是否收到了F+1個來自不同節(jié)點的相同結(jié)果作為最終結(jié)果戈稿,這里的F是指網(wǎng)絡(luò)中存在拜占庭故障的節(jié)點數(shù)量,F(xiàn)+1個是指正常的節(jié)點數(shù)量讶舰,沒有故障的節(jié)點數(shù)量應(yīng)該要大于網(wǎng)絡(luò)中存在拜占庭故障的節(jié)點數(shù)量鞍盗。
那主節(jié)點的廣播過程包括了三個階段的處理需了,預處理階段,準備階段和提交階段般甲,預處理和準備階段確保在同一個試圖內(nèi)請求發(fā)送的順序正確肋乍,準備和提交階段則確保在不同試圖之間的確認請求是保序的。
首先看預準備階段敷存,主節(jié)點從客戶端收到了請求分配體驗編號墓造,然后發(fā)出預準備消息給各個節(jié)點,給副本節(jié)點锚烦,準備階段觅闽,副本節(jié)點收到預準備消息后檢查消息合法,如檢查通過則向其他節(jié)點發(fā)送準備消息涮俄,帶上自己的ID信息蛉拙,同時接收來自其他節(jié)點的準備消息,收到準備消息的節(jié)點對消息同樣要進行合法性檢查彻亲。
驗證通過孕锄,則把這個準備消息寫到消息日志中,集齊了至少2F+1個驗證過的消息才進入到準備狀態(tài)睹栖。提交的階段可以廣播提交信息告訴某個節(jié)點提案n在試圖v已經(jīng)處于準備狀態(tài),如果集齊了至少2F+1個驗證過的提交階段提交信息茧痕,則說明提案通過野来。
拜占庭問題之所以難解,在于任何時候系統(tǒng)中都可能存在多個提案踪旷,并且完成最終一次性確認過程十分困難曼氛,容易受到干擾。
使用拜占庭算法的主要優(yōu)點是:
第一令野,PBFT算法共識各個節(jié)點由業(yè)務(wù)的監(jiān)管方或者參與方構(gòu)成舀患,安全性與穩(wěn)定性由業(yè)務(wù)相關(guān)方來保證。
第二個它的共識時延大約在2-5秒气破,基本達到了商用的實時處理要求聊浅,所以它的共識效率比較高,可滿足高頻交易量的需求现使,PBFT算法的這些優(yōu)點非常適合聯(lián)盟鏈的應(yīng)用場景低匙,因此成為使用最多的聯(lián)盟鏈共識算法。
PBFT目前也有很多的改進碳锈,主要集中在一個修改網(wǎng)絡(luò)拓撲的要求顽冶,使用的P2P網(wǎng)絡(luò);第二個可以動態(tài)調(diào)整節(jié)點的數(shù)量售碳;第三減少協(xié)議使用的消息數(shù)量强重,不過PBFT仍然是依靠一個節(jié)點一票绞呈,少數(shù)服從多數(shù)的方式來實現(xiàn)拜占庭容錯,對于聯(lián)盟鏈而言间景,這個前提沒有問題佃声,甚至是優(yōu)點所在,但是在公有鏈中拱燃,由于節(jié)點數(shù)目廣大秉溉,這樣就會存在很大的問題。
所以我們公有鏈中沒有采用PBFT算法碗誉,一般采用的是工作量證明機制POW召嘶,權(quán)益證明機制POS和股份授權(quán)證明機制DPoS,這樣的共識算法來實現(xiàn)一致性哮缺。下面對于公有鏈中的共識機制進行介紹弄跌。
二、工作量證明機制PoW
PoW是我們最熟知的一種共識機制尝苇,它意味著工作越多收益越大铛只,這里的工作是猜測數(shù)值,誰能最快的猜出這個唯一的數(shù)字糠溜,誰就能做信息公示淳玩,或者信息記賬。這就是經(jīng)常聽到的挖礦非竿。有了這樣一個誰能第一個做出這樣的一道題蜕着,我們就有記賬的權(quán)力,那這樣的一個工作過程就是尋找nonce隨機數(shù)的過程红柱。
首先對區(qū)塊的交易信息做一個哈希值承匣,這樣就得到一個256位的字符串,我們把256位的字符串命名為A1锤悄,在A1的字符串后面加上nonce(隨機數(shù))韧骗,這個字符串叫做A2,然后對A2字符串做hash運算得到256位的字符串A3零聚,如果A3的前四位都是0袍暴,那么這個隨機數(shù)就找對了,就可以向網(wǎng)絡(luò)進行提交隶症,從而如果你是第一個提交容诬,這樣一個nonce隨機數(shù),你就具有了記賬的權(quán)力沿腰,這就是比如我們來看下面的一個例子览徒。
給定一個基本的字符串“hello world”,工作量的要求是在字符串的后面添加一個叫nonce的整數(shù)值颂龙,對變更后的字符串進行SHA256運算习蓬,如果得到的哈希結(jié)果以16位進制的哈希結(jié)果是以0000開頭的則驗證通過纽什,那么你如果是第一個獲得這樣一個nonce隨機數(shù)并且在網(wǎng)絡(luò)提交,讓大家驗證通過躲叼,則你就具有了記賬的權(quán)力芦缰。
下面具體看一下PoW協(xié)議的進行過程,開始我們講到的只是挖礦或者工作的一個過程枫慷,PoW協(xié)議首先第一個向所有的節(jié)點廣播新的交易让蕾,然后每個節(jié)點把收到的交易放到區(qū)塊鏈的塊中,在每一輪中或听,一個隨機選中的節(jié)點或者按照一定規(guī)則選出來的節(jié)點廣播它所保有的塊探孝,其它節(jié)點在驗證塊中所有的交易正確無誤后接受該區(qū)塊,其它節(jié)點將該區(qū)塊的哈希值放入下一個他們創(chuàng)建的區(qū)塊中誉裆,表示他們承認這個區(qū)塊的正確性顿颅。
剛才我們說到的這樣的一個工作或者說挖礦就是選出的節(jié)點,挖礦讓算力最快或者最幸運的一個節(jié)點被選中就可以廣播它所保有的或計算的塊足丢,其他的節(jié)點只能驗證正確的粱腻,被選中的節(jié)點就具有記賬的權(quán)力,他就可以獲得相應(yīng)的收益斩跌。
節(jié)點們總是認為最長的鏈是一個合法的鏈绍些,并且努力去擴大這條鏈,如果兩個節(jié)點同時廣播各自挖出的區(qū)塊耀鸦,其他節(jié)點以自己最先收到的區(qū)塊為準開始挖礦柬批,但同時會保留另一個區(qū)塊,所以就會出現(xiàn)一些節(jié)點先收到A的區(qū)塊揭糕,并在其上開始挖礦萝快,同時保留著B的區(qū)塊防止B的區(qū)塊所在的分支锻霎,日后成為較長的分支著角,直到其中某個分支在下一個工作量證明中變得更長,之前那些在另一條分支上工作的節(jié)點旋恼,就會轉(zhuǎn)向這條更長的鏈吏口,平均每十分鐘有一個節(jié)點找到一個區(qū)塊,如果兩個節(jié)點在同一時間找到區(qū)塊冰更,那么網(wǎng)絡(luò)將根據(jù)后續(xù)節(jié)點來決定产徊,確定以哪個區(qū)塊構(gòu)建總賬,從統(tǒng)計學角度而言蜀细,一筆交易六個節(jié)點舟铜,也就是約1個小時后,被認為是明確確認且不可逆的奠衔,然而核心開發(fā)者認為需要120個區(qū)塊谆刨,約1天的時間才能充分保護網(wǎng)絡(luò)不受來自潛在更長的新產(chǎn)生的幣被花掉的區(qū)塊鏈的威脅塘娶。
那我們的在生物學上有一個原理叫做不利原理,該原理可以幫助我們解釋工作量證明的過程痊夭,這個原理中當兩只動物有合作的動機時刁岸,他們必須很有說服力的向?qū)Ψ奖磉_善意,為了打消對方的疑慮她我,他們向?qū)Ψ奖磉_友好時虹曙,必須附上自己的代價,使得自己背叛對方時不得不付出昂貴的代價番舆。
換句話說表達方式本身必須是對自己不利的酝碳,那么這樣一種不利原則在歷史上會經(jīng)常發(fā)生,比如說在中國的歷史上合蔽,國家和國家之間簽訂盟約击敌,為了表示自己對盟約的誠意,經(jīng)常會互相送一個兒子拴事,有時候是送太子即皇位繼承人沃斤,去對方國家做人質(zhì),在這種情況下為取得信任付出的代價是君主和兒子的親戚以及十幾年的養(yǎng)育刃宵。
比特幣的工作量證明很好的利用了不利原理解決了一個網(wǎng)絡(luò)社會里面的問題衡瓶,產(chǎn)生一個新區(qū)快是建立在耗時耗力的巨大代價上,所以當新區(qū)快誕生后牲证,某個礦工要么忽視它哮针,繼續(xù)自己的新區(qū)快尋找,要么接受它坦袍,在該區(qū)塊之后繼續(xù)自己的挖礦十厢。
顯然前者是不明智的,因為在比特幣網(wǎng)絡(luò)里捂齐,以最長鏈為合法的鏈蛮放,這個礦工選擇忽視而另取爐炤,就不得不說服足夠多的其他礦工奠宜,沿著他的路線走包颁,相反要是他選擇接受,不僅不會付出額外的辛苦压真,而且照樣可以繼續(xù)進行自己更新區(qū)塊的一個挖礦娩嚼,不會再出現(xiàn)你走你的,我走我的滴肿,這樣一個情況岳悟,這樣就會形成全網(wǎng)的良性建設(shè),比特幣通過不利原理約束了節(jié)點的行為泼差。
PoW的優(yōu)點是完全的去中心化贵少,節(jié)點可以自由的進出和屎,但是依賴機器進行運算來獲取記賬權(quán),資源的消耗相比其他的共識機制要高春瞬,可監(jiān)管性弱柴信,同時共識需要全網(wǎng)共同參與運算,性能的效率比較低宽气,容錯性方面可以允許節(jié)點的50%出錯随常。從目前來看,PoW共識協(xié)議萄涯,它的缺點是挖礦會造成大量的資源浪費绪氛,而且共識達成的周期比較長,我們知道比特幣的區(qū)塊生成周期涝影,是每10分鐘生成一個區(qū)塊枣察,這個時間非常長,不適合我們在現(xiàn)實社會中很多的應(yīng)用燃逻,這個速度太慢序目。
三、權(quán)益證明機制PoS
它是股權(quán)權(quán)益證明伯襟,它類似股權(quán)憑證和投票系統(tǒng)猿涨,由持有最多的人公示最終的信息,PoS已經(jīng)有了很多的變種姆怪,最基本的概念就是選擇生成新的區(qū)塊的機會應(yīng)該和股權(quán)的大小成比例叛赚,股權(quán)可以是投入的資金也可以是預先投入的其他資源,pos算法針對pow算法的缺點來改進的稽揭,pos無論什么人買了礦機下載了軟件就可以參與俺附,pos要求參與者預先放一些代幣或者利益在區(qū)塊鏈上。類似將財產(chǎn)儲存在銀行之中溪掀,那么我們來看采用PoS的數(shù)字資產(chǎn)事镣,系統(tǒng)根據(jù)你的幣齡給你分配相應(yīng)的權(quán)益,幣齡是你持幣數(shù)量和時間的乘積膨桥。比如你持有100個幣蛮浑,總共持有了30天唠叛,那么只嚣,此時你的幣齡就為3000。
這種模式會根據(jù)你持有數(shù)字貨幣的量和時間分配給你相應(yīng)的利息艺沼,用戶只有將一些利益放進鏈里册舞,相當于一些押金,用戶才會更加關(guān)注障般,做出的決定才會更加理性调鲸,同時也可以引入獎懲機制盛杰,使節(jié)點的運行更加可控,同時更好的防止攻擊藐石。
PoS的運作機制大致如下:
第一即供,加入PoS機制的都是持幣人,也就是成為驗證者于微。第二PoS算法在這些驗證者里挑一個給予權(quán)力生成新的區(qū)塊逗嫡,挑選的順序根據(jù)持幣的幣齡來進行計算,如果在一定時間內(nèi)株依,沒有生成區(qū)塊驱证,PoS則會挑選下一個驗證者,給予生成新區(qū)塊的權(quán)益恋腕,然后以此類推抹锄,以區(qū)塊鏈中最長的鏈為準。
PoS和PoW有一個很大的區(qū)別荠藤,在PoS機制下持幣是有利息的伙单,眾所周知比特幣是有數(shù)量限制的,由于有比特幣丟失問題哈肖,總體來說车份,比特幣是減少的,也就是說比特幣是一個通縮的系統(tǒng)牡彻,而在PoS模式下引入了幣齡的概念扫沼,每個幣每天產(chǎn)生一幣齡。
比如你持有100個幣總共持有10天庄吼,那么這個時候如果你發(fā)現(xiàn)了一個Pos區(qū)塊缎除,你的幣齡就會被清空,沒被清空365幣齡总寻,將會從區(qū)塊中獲得一定的利息器罐,PoS機制下清空下不會產(chǎn)生通縮的清空,和PoW相比渐行,PoS不需要為了生成新區(qū)塊的情況下不需要損耗大量的電力轰坊,在一定程度上縮短了共識達成的時間,但是缺點是PoS還是需要挖礦祟印,而且PoS中持幣越多的收益越大肴沫,也就是更多的會產(chǎn)生財富集中,中心化的問題蕴忆,更多的沒有多少財富的中小投資者就會喪失記賬權(quán)或者說喪失它的權(quán)力颤芬,由此提到了一個新的共識算法。
四、DPoS
是股份授權(quán)證明機制站蝠,它是PoS中財富集中的汰具,越多財富的人獲得的收益越多,它的發(fā)言權(quán)也越大菱魔,這樣一個缺陷進行改進冲簿,那么也就是由股東投票選出一個董事會挡篓,董事會中的成員才有權(quán)進行代理記賬偎蘸,這樣就不是錢越多的有越多的記賬權(quán)银萍,在這里面,股東投票是每一個人或者每一個節(jié)點都有投票記賬的權(quán)力肥隆,一個節(jié)點一票來選一個董事會既荚。
所以DPoS是PoS的一個改進,它可以確保節(jié)點的財富不會因為財富的多少而導致記賬權(quán)的集中栋艳,由于DPoS采用董事會的制度恰聘,讓董事會的成員進行記賬,所以記賬的節(jié)點數(shù)量增加吸占,記賬速度提高晴叨,采用這個共識算法后,出塊的速度可以達到秒級矾屯,DPoS可以達到數(shù)千的一個數(shù)量級兼蕊,可以滿足現(xiàn)在絕大部分實行應(yīng)用的一個需求。
我們來看DPoS實例是比特股件蚕,見證人生成區(qū)塊孙技,每一個持有比特股的人都可以投票選取見證人,見證人的候選名單每個維護周期(一天更新一次)排作,見證人隨機排列牵啦,每個見證人的按序有2秒鐘的時間生成區(qū)塊,如果在這兩秒的時間內(nèi)見證人不能生成區(qū)塊妄痪,這個節(jié)點故障或者信息故障哈雏,那么區(qū)塊生成權(quán)限會交給下一個時間段對應(yīng)的見證人,DPoS充分的運用了見證人持股人的投票衫生,這樣可以用民主的方式來達成共識 裳瘪。
最后來看一下幾種共識機制的比較,POW這個共識機制的算法相對簡單罪针,容易實現(xiàn)彭羹,節(jié)點間無需交換額外的信息即可達成共識,那要破壞系統(tǒng)需要投入極大的成本站故,我們說PoW有一個51%的攻擊皆怕,這是指的想要破壞PoW想達成的共識,就必須要有超過整個系統(tǒng)50%的算力才能實現(xiàn)西篓,也就是要有51%的算力掌握在你的手上才能夠破壞PoW所達成的共識所記的一個賬愈腾,那這樣的話,如果說系統(tǒng)現(xiàn)有的算力很高的話岂津,超過現(xiàn)有系統(tǒng)51%的算力虱黄,這樣的話,你所需要付出的代價非常大吮成。
所以從這個角度而言橱乱,PoW的共識算法安全性非常高,當然PoW共識算法它的缺點也是很明顯粱甫,第一個大量的節(jié)點要進行毫無意義的隨機數(shù)的哈希碰撞計算泳叠,這種計算僅僅只是為了證明節(jié)點算力并沒有任何的意義,所以浪費了能源茶宵,浪費大量的電力危纫。
第二個,由于PoW的共識需要有大量節(jié)點的參與乌庶,區(qū)塊的確認時間難以縮短种蝶,如果說你想要縮短區(qū)塊確認的時間,那就會導致大量孤塊的產(chǎn)生瞒大,整個系統(tǒng)的安全性難以保證螃征。
第三個容易產(chǎn)生分叉,等待多個確認透敌,就是說我們在正確的記賬制度之下盯滚,有可能你記了A的節(jié)點后,A節(jié)點發(fā)出區(qū)塊后酗电,有可能B節(jié)點之后的后續(xù)節(jié)點它們增長更快淌山,那么前面記的A節(jié)點的賬相當于是一個分叉,那么在更多更長的鏈顾瞻。速度比較慢泼疑,這樣的缺點提出來的,資源消耗很小荷荤,不需要計算nonce隨機數(shù)退渗,它采用誰的幣齡長,誰持有的幣多就用誰來記賬這樣的一種方式蕴纳。
當然它的缺點實現(xiàn)較為復雜会油,中間的步驟比較多容易產(chǎn)生安全漏洞,對于流量的壓力比較大古毛,同時還有一個錢越多的人它的收益越高翻翩,他的記賬的權(quán)力越大都许,那么有悖于區(qū)塊鏈中去中心化的一個理念,DPOS是在針對PoS的缺陷提出來的嫂冻,它采用的是一個股份授權(quán)的機制胶征,資源消耗少,網(wǎng)絡(luò)資源消耗也少桨仿,共識時間少睛低,吞吐量高,可以滿足實時的交易的需求服傍,它的實現(xiàn)方法相對來說比較復雜钱雷。
看一下在現(xiàn)代比較主流的代表幣種中,比特幣吹零,達世幣罩抗,萊特幣,以太坊這些都采用的PoW機制灿椅,以太坊前面三個階段采用PoW機制澄暮,在后面階段會逐漸的轉(zhuǎn)向PoS這樣的一個機制,而量子鏈采用的是PoS阱扬,而EOS泣懊,比特股采用的是DPoS這樣的一個共識機制。
下面對共識機制進行一些思考麻惶,對于分布式的拜占庭問題馍刮,F(xiàn)LP不可能性原理與kap定律已經(jīng)告訴了我們無解,研究人員即科學家只有從其他地方來尋找求解問題的靈感窃蹋,其實可以發(fā)現(xiàn)真實的人類世界就是以一個分布式系統(tǒng)卡啰,比特幣的天才之處在于參與了人類的組織方式和運作方式,引入了共識機制警没,一個交易的成立與否匈辱,也就是分布式賬本的記賬權(quán),由記賬的共識機制達成的共識來決定杀迹。
共識本身就是一個典型的社會學概念亡脸,PoW可以看做是范進中舉,范進用了大半輩子來學習一種無用的八股文寫作树酪,就像比特幣礦工用算力來算題浅碾,算的題毫無意義,有朝一日運氣好就可以有權(quán)打包所有他認可的交易续语,并且獲得相應(yīng)的獎勵垂谢。
PoS是用戶要預先放入一些利益,很像我們一些現(xiàn)實世界中的股份制疮茄,人們把真金白銀兌換成股份開始創(chuàng)業(yè)滥朱,誰的股份多誰的話語權(quán)就更大根暑。
DPoS像我們的董事會選舉出代表,代表股東的利益徙邻,被選出的代表一般來說經(jīng)驗豐富排嫌,不但能快速的處理日常事物,同時也能很好的保護股東的利益鹃栽,而像帕克斯算法躏率,ruft算法躯畴,pbft算法民鼓,則很像我們生活中的隊列,通過相互間的口令達成一致蓬抄,每排的排頭就稱作leader丰嘉,領(lǐng)導,而每排的其他人都以排頭為leader目標調(diào)整自己的行動嚷缭。
傳統(tǒng)純正的計算法對分布式系統(tǒng)的拜占庭問題已經(jīng)無力著手了饮亏,所以在分布式系統(tǒng)的研究中,引入了一些社會學的理論和概念阅爽,我們可以把每個計算機節(jié)點想象成一個單元路幸,而計算機網(wǎng)絡(luò)就是一個個單元組成的社會,我們可以借鑒人類社會歷史上的機制付翁,激勵機制來實現(xiàn)分布式網(wǎng)絡(luò)的一致性简肴,我們有理由相信互聯(lián)網(wǎng),或者分布式網(wǎng)路系統(tǒng)與現(xiàn)實的社會運作有著千絲萬縷的聯(lián)系百侧。