區(qū)塊鏈快速入門（四）——BFT（拜占庭容錯(cuò)）共識(shí)算法

區(qū)塊鏈快速入門（四）——BFT（拜占庭容錯(cuò)）共識(shí)算法

一、BFT簡(jiǎn)介

1、拜占庭將軍問(wèn)題簡(jiǎn)介

拜占庭將軍問(wèn)題（Byzantine Generals Problem）是Leslie Lamport（2013年的圖靈獎(jiǎng)得主）用來(lái)為描述分布式系統(tǒng)一致性問(wèn)題（Distributed Consensus）在論文中抽象出來(lái)一個(gè)著名的例子。
拜占庭將軍問(wèn)題簡(jiǎn)易的非正式描述如下：
拜占庭帝國(guó)想要進(jìn)攻一個(gè)強(qiáng)大的敵人，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊?；谝恍┰?，這10支軍隊(duì)不能集合在一起單點(diǎn)突破，必須在分開(kāi)的包圍狀態(tài)下同時(shí)進(jìn)攻。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無(wú)勝算，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國(guó)。他們分散在敵國(guó)的四周，依靠通信兵相互通信來(lái)協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問(wèn)題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下，拜占庭將軍們能否找到一種分布式的協(xié)議來(lái)讓他們能夠遠(yuǎn)程協(xié)商，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問(wèn)題。
拜占庭將軍問(wèn)題中并不去考慮通信兵是否會(huì)被截獲或無(wú)法傳達(dá)信息等問(wèn)題，即消息傳遞的信道絕無(wú)問(wèn)題。Lamport已經(jīng)證明了在消息可能丟失的不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的。所以，在研究拜占庭將軍問(wèn)題的時(shí)候，假定信道是沒(méi)有問(wèn)題的，然后去做一致性和容錯(cuò)性相關(guān)研究。

2、兩將軍問(wèn)題

拜占庭問(wèn)題前，就已經(jīng)存在兩將軍問(wèn)題(Two Generals Paradox):兩個(gè)將軍要通過(guò)信使來(lái)達(dá)成進(jìn)攻還是撤退的約定，但信使可能迷路或被敵軍阻攔(消息丟失或偽造)，如何達(dá)成一致?
根據(jù)FLP不可能原理，兩將軍問(wèn)題無(wú)通用解。

3、BFT簡(jiǎn)介

BFT（Byzantine Fault Tolerance），即拜占庭容錯(cuò)，是分布式計(jì)算領(lǐng)域的容錯(cuò)技術(shù)，拜占庭容錯(cuò)來(lái)源于拜占庭將軍問(wèn)題。拜占庭將軍問(wèn)題是對(duì)現(xiàn)實(shí)世界的模型化，由于硬件錯(cuò)誤、網(wǎng)絡(luò)擁塞或中斷以及遭到惡意***等原因，計(jì)算機(jī)和網(wǎng)絡(luò)可能出現(xiàn)不可預(yù)料的行為。拜占庭容錯(cuò)技術(shù)被設(shè)計(jì)用來(lái)處理現(xiàn)實(shí)存在的異常行為，并滿足所要解決的問(wèn)題的規(guī)范要求。
區(qū)塊鏈網(wǎng)絡(luò)環(huán)境符合拜占庭將軍問(wèn)題模型，有運(yùn)行正常的服務(wù)器（忠誠(chéng)的拜占庭將軍），有故障的服務(wù)器，還有破壞者的服務(wù)器（叛變的拜占庭將軍）。共識(shí)算法的核心是在正常的節(jié)點(diǎn)間形成對(duì)網(wǎng)絡(luò)狀態(tài)的共識(shí)。
通常，發(fā)生故障的節(jié)點(diǎn)被稱為拜占庭節(jié)點(diǎn)，而正常的節(jié)點(diǎn)為非拜占庭節(jié)點(diǎn)。
拜占庭容錯(cuò)系統(tǒng)是一個(gè)擁有n臺(tái)節(jié)點(diǎn)的系統(tǒng)，整個(gè)系統(tǒng)對(duì)于每一個(gè)請(qǐng)求，滿足以下條件：
　　A、所有非拜占庭節(jié)點(diǎn)使用相同的輸入信息，產(chǎn)生同樣的結(jié)果；
　　B、如果輸入的信息正確，那么所有非拜占庭節(jié)點(diǎn)必須接收這個(gè)信息，并計(jì)算相應(yīng)的結(jié)果。
拜占庭系統(tǒng)普遍采用的假設(shè)條件包括：
　　A、拜占庭節(jié)點(diǎn)的行為可以是任意的，拜占庭節(jié)點(diǎn)之間可以共謀；
　　B、節(jié)點(diǎn)之間的錯(cuò)誤是不相關(guān)的；
　　C、節(jié)點(diǎn)之間通過(guò)異步網(wǎng)絡(luò)連接，網(wǎng)絡(luò)中的消息可能丟失、亂序并延時(shí)到達(dá)，但大部分協(xié)議假設(shè)消息在有限的時(shí)間里能傳達(dá)到目的地；
　　D、服務(wù)器之間傳遞的信息，第三方可以嗅探到，但是不能篡改、偽造信息的內(nèi)容和驗(yàn)證信息的完整性。
原始的拜占庭容錯(cuò)系統(tǒng)由于需要展示其理論上的可行性而缺乏實(shí)用性。另外，還需要額外的時(shí)鐘同步機(jī)制支持，算法的復(fù)雜度也是隨節(jié)點(diǎn)增加而指數(shù)級(jí)增加。

二、PBFT算法

1、PBFT算法簡(jiǎn)介

PBFT（Practical Byzantine Fault Tolerance），即實(shí)用拜占庭容錯(cuò)算法，由Miguel Castro和Barbara Liskov在1999年發(fā)表的論文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。PBFT算法可以工作在異步環(huán)境中，并且通過(guò)優(yōu)化解決了原始拜占庭容錯(cuò)算法效率不高的問(wèn)題，將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行，目前已得到廣泛應(yīng)用。PBFT算法可以在失效節(jié)點(diǎn)不超過(guò)總數(shù)1/3的情況下同時(shí)保證Safety和Liveness。
PBFT 算法采用密碼學(xué)相關(guān)技術(shù)(RSA 簽名算法、消息驗(yàn)證編碼和摘要)確保消息傳遞過(guò)程無(wú)法被篡改和破壞。

2、PBFT算法原理

PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，即服務(wù)作為狀態(tài)機(jī)進(jìn)行建模，狀態(tài)機(jī)在分布式系統(tǒng)的不同節(jié)點(diǎn)進(jìn)行副本復(fù)制。每個(gè)狀態(tài)機(jī)的副本都保存了服務(wù)的狀態(tài)，同時(shí)也實(shí)現(xiàn)了服務(wù)的操作。將所有的副本組成的集合使用大寫字母R表示，使用0到|R|-1的整數(shù)表示每一個(gè)副本。為了描述方便，通常假設(shè)故障節(jié)點(diǎn)數(shù)為f個(gè)，整個(gè)服務(wù)節(jié)點(diǎn)數(shù)為|R|=3f+1個(gè)，f是有可能失效的副本的最大個(gè)數(shù)。盡管可以存在多于3f+1個(gè)副本，但額外的副本除了降低性能外不能提高可靠性。
所有的副本在一個(gè)被稱為視圖（View）的輪換過(guò)程中運(yùn)作。在某個(gè)視圖中，一個(gè)副本作為主節(jié)點(diǎn)（primary），其它的副本節(jié)點(diǎn)作為備份節(jié)點(diǎn)（backups）。視圖是連續(xù)編號(hào)的整數(shù)。主節(jié)點(diǎn)由公式p = v mod |R|計(jì)算得到，v是視圖編號(hào)，p是副本編號(hào)，|R|是副本集合的個(gè)數(shù)。當(dāng)主節(jié)點(diǎn)失效的時(shí)候就需要啟動(dòng)視圖輪換過(guò)程。
PBFT算法實(shí)現(xiàn)流程如下：

（1）REQUEST
客戶端C向主節(jié)點(diǎn)p發(fā)送

<REQUEST, o, t, c>

請(qǐng)求。
o:請(qǐng)求的具體操作
t:請(qǐng)求時(shí)客戶端追加的時(shí)間戳
c：客戶端標(biāo)識(shí)。
REQUEST: 包含消息內(nèi)容m，以及消息摘要d(m)。
客戶端對(duì)請(qǐng)求進(jìn)行簽名。
（2）PRE-PREPARE
主節(jié)點(diǎn)收到客戶端的請(qǐng)求，需要對(duì)客戶端請(qǐng)求消息簽名是否正確進(jìn)行校驗(yàn)。
非法請(qǐng)求則丟棄。正確請(qǐng)求，分配一個(gè)編號(hào)n，編號(hào)n主要用于對(duì)客戶端的請(qǐng)求進(jìn)行排序。然后廣播一條

<<PRE-PREPARE, v, n, d>,? m>

消息給其它副本節(jié)點(diǎn)。
v：視圖編號(hào)
d客戶端消息摘要
m：消息內(nèi)容

<PRE-PREPARE, v, n, d>

進(jìn)行主節(jié)點(diǎn)簽名。
n是要在某一個(gè)范圍區(qū)間內(nèi)的[h, H]。
（3）PREPARE
副本節(jié)點(diǎn)i收到主節(jié)點(diǎn)的PRE-PREPARE消息，需要進(jìn)行以下校驗(yàn)：
A、主節(jié)點(diǎn)PRE-PREPARE消息簽名是否正確。
B、當(dāng)前副本節(jié)點(diǎn)是否已經(jīng)收到了一條在同一v下并且編號(hào)也是n，但是簽名不同的PRE-PREPARE信息。
C、d與m的摘要是否一致。
D、n是否在區(qū)間[h, H]內(nèi)。
非法請(qǐng)求則丟棄。正確請(qǐng)求，副本節(jié)點(diǎn)i向其它節(jié)點(diǎn)包括主節(jié)點(diǎn)發(fā)送一條

<PREPARE, v, n, d, i>

消息, v, n, d, m與上述PRE-PREPARE消息內(nèi)容相同，i是當(dāng)前副本節(jié)點(diǎn)編號(hào)。

<PREPARE, v, n, d, i>

進(jìn)行副本節(jié)點(diǎn)i的簽名。記錄PRE-PREPARE和PREPARE消息到log中，用于視圖輪換過(guò)程中恢復(fù)未完成的請(qǐng)求操作。
PREPARE階段如果發(fā)生視圖輪換會(huì)導(dǎo)致丟棄PREPARE階段的請(qǐng)求。
（4）COMMIT
主節(jié)點(diǎn)和副本節(jié)點(diǎn)收到PREPARE消息，需要進(jìn)行以下校驗(yàn)：
A、副本節(jié)點(diǎn)PREPARE消息簽名是否正確。
B、當(dāng)前副本節(jié)點(diǎn)是否已經(jīng)收到了同一視圖v下的n。
C、 n是否在區(qū)間[h, H]內(nèi)。
D、d是否和當(dāng)前已收到PRE-PPREPARE中的d相同
非法請(qǐng)求則丟棄。如果副本節(jié)點(diǎn)i收到了2f+1個(gè)驗(yàn)證通過(guò)的PREPARE消息，表明網(wǎng)絡(luò)中的大多數(shù)節(jié)點(diǎn)已經(jīng)收到同意信息，則向其它節(jié)點(diǎn)包括主節(jié)點(diǎn)發(fā)送一條

<COMMIT, v, n, d, i>

消息，v, n, d,? i與上述PREPARE消息內(nèi)容相同。

<COMMIT, v, n, d, i>

進(jìn)行副本節(jié)點(diǎn)i的簽名。記錄COMMIT消息到日志中，用于視圖輪換過(guò)程中恢復(fù)未完成的請(qǐng)求操作。記錄其它副本節(jié)點(diǎn)發(fā)送的PREPARE消息到log中。
COMMIT階段用來(lái)確保網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)都已經(jīng)收到足夠多的信息來(lái)達(dá)成共識(shí)，如果COMMIT階段發(fā)生視圖輪換，會(huì)保存原來(lái)COMMIT階段的請(qǐng)求，不會(huì)達(dá)不成共識(shí)，也不會(huì)丟失請(qǐng)求編號(hào)。

（5）REPLY
主節(jié)點(diǎn)和副本節(jié)點(diǎn)收到COMMIT消息，需要進(jìn)行以下校驗(yàn)：
A、副本節(jié)點(diǎn)COMMIT消息簽名是否正確。
B、當(dāng)前副本節(jié)點(diǎn)是否已經(jīng)收到了同一視圖v下的n。
C、d與m的摘要是否一致。
D、n是否在區(qū)間[h, H]內(nèi)。
非法請(qǐng)求則丟棄。如果副本節(jié)點(diǎn)i收到了2f+1個(gè)驗(yàn)證通過(guò)的COMMIT消息，說(shuō)明當(dāng)前網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)已經(jīng)達(dá)成共識(shí)，運(yùn)行客戶端的請(qǐng)求操作o，并返回

<REPLY, v, t, c, i, r>

給客戶端，r：是請(qǐng)求操作結(jié)果，客戶端如果收到f+1個(gè)相同的REPLY消息，說(shuō)明客戶端發(fā)起的請(qǐng)求已經(jīng)達(dá)成全網(wǎng)共識(shí)，否則客戶端需要判斷是否重新發(fā)送請(qǐng)求給主節(jié)點(diǎn)。記錄其它副本節(jié)點(diǎn)發(fā)送的COMMIT消息到log中。

3、PBFT算法的垃圾回收

為了確保在視圖輪換的過(guò)程中，能夠恢復(fù)先前的請(qǐng)求，每一個(gè)副本節(jié)點(diǎn)都記錄一些消息到本地的log中，當(dāng)執(zhí)行請(qǐng)求后副本節(jié)點(diǎn)需要把之前該請(qǐng)求的記錄消息清除掉。最簡(jiǎn)單的做法是在Reply消息后，再執(zhí)行一次當(dāng)前狀態(tài)的共識(shí)同步，但成本比較高，因此可以在執(zhí)行完多條請(qǐng)求K（例如：100條）后執(zhí)行一次狀態(tài)同步。狀態(tài)同步消息就是CheckPoint消息。
副本節(jié)點(diǎn)i發(fā)送

<CheckPoint, n, d, i>

給其它節(jié)點(diǎn)，n是當(dāng)前節(jié)點(diǎn)所保留的最后一個(gè)視圖請(qǐng)求編號(hào)，d是對(duì)當(dāng)前狀態(tài)的一個(gè)摘要，該CheckPoint消息記錄到log中。如果副本節(jié)點(diǎn)i收到了2f+1個(gè)驗(yàn)證過(guò)的CheckPoint消息，則清除先前日志中的消息，并以n作為當(dāng)前一個(gè)stable checkpoint。
實(shí)際中，當(dāng)副本節(jié)點(diǎn)i向其它節(jié)點(diǎn)發(fā)出CheckPoint消息后，其它節(jié)點(diǎn)還沒(méi)有完成K條請(qǐng)求，所以不會(huì)立即對(duì)i的請(qǐng)求作出響應(yīng)，還會(huì)按照自己的節(jié)奏，向前行進(jìn)，但此時(shí)發(fā)出的CheckPoint并未形成stable，為了防止i的處理請(qǐng)求過(guò)快，設(shè)置一個(gè)上文提到的高低水位區(qū)間[h, H]來(lái)解決問(wèn)題。低水位h等于上一個(gè)stable checkpoint的編號(hào)，高水位H = h + L，其中L是指定的數(shù)值，等于checkpoint周期處理請(qǐng)求數(shù)K的整數(shù)倍，可以設(shè)置為L(zhǎng) = 2K。當(dāng)副本節(jié)點(diǎn)i處理請(qǐng)求超過(guò)高水位H時(shí)，此時(shí)就會(huì)停止腳步，等待stable checkpoint發(fā)生變化，再繼續(xù)前進(jìn)。

4、PBFT算法的視圖輪換

如果主節(jié)點(diǎn)作惡，可能會(huì)給不同的請(qǐng)求編上相同的序號(hào)，或者不去分配序號(hào)，或者讓相鄰的序號(hào)不連續(xù)。備份節(jié)點(diǎn)應(yīng)當(dāng)有職責(zé)來(lái)主動(dòng)檢查這些序號(hào)的合法性。如果主節(jié)點(diǎn)掉線或者作惡不廣播客戶端的請(qǐng)求，客戶端設(shè)置超時(shí)機(jī)制，超時(shí)的話，向所有副本節(jié)點(diǎn)廣播請(qǐng)求消息。副本節(jié)點(diǎn)檢測(cè)出主節(jié)點(diǎn)作惡或者下線，發(fā)起視圖輪換協(xié)議。
副本節(jié)點(diǎn)向其它節(jié)點(diǎn)廣播

<VIEW-CHANGE, v+1, n,?C,?P, i>

消息。n是最新的stable checkpoint的編號(hào)，C是2f+1驗(yàn)證過(guò)的CheckPoint消息集合，P是當(dāng)前副本節(jié)點(diǎn)未完成的請(qǐng)求的PRE-PREPARE和PREPARE消息集合。
當(dāng)主節(jié)點(diǎn)p = v + 1 mod |R|收到2f個(gè)有效的VIEW-CHANGE消息后，向其它節(jié)點(diǎn)廣播

<NEW-VIEW, v+1,?V,?O>

消息。V是有效的VIEW-CHANGE消息集合。O是主節(jié)點(diǎn)重新發(fā)起的未經(jīng)完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的選取規(guī)則如下：
A、選取V中最小的stable checkpoint編號(hào)min-s，選取V中prepare消息的最大編號(hào)max-s。
B、在min-s和max-s之間，如果存在P消息集合，則創(chuàng)建

<<PRE-PREPARE, v+1, n, d>, m>

消息。否則創(chuàng)建一個(gè)空的PRE-PREPARE消息，即：

<<PRE-PREPARE, v+1, n, d(null)>, m(null)>

, m(null)為空消息，d(null)為空消息摘要。
副本節(jié)點(diǎn)收到主節(jié)點(diǎn)的NEW-VIEW消息，驗(yàn)證有效性，有效的話，進(jìn)入v+1狀態(tài)，并且開(kāi)始O中的PRE-PREPARE消息處理流程。

5、PBFT算法的優(yōu)缺點(diǎn)

PBFT算法的優(yōu)點(diǎn):
PBFT算法具有高交易通量和吞吐量，高可用性，易于理解。
PBFT算法的缺點(diǎn):
A、計(jì)算效率依賴于參與協(xié)議的節(jié)點(diǎn)數(shù)量，由于每個(gè)副本節(jié)點(diǎn)都需要和其它節(jié)點(diǎn)進(jìn)行P2P的共識(shí)同步，因此隨著節(jié)點(diǎn)的增多，性能會(huì)下降的很快，但在較少節(jié)點(diǎn)的情況下可以有不錯(cuò)的性能，并且分叉的幾率很低，不適用于節(jié)點(diǎn)數(shù)量過(guò)大的區(qū)塊鏈，擴(kuò)展性差。
B、系統(tǒng)節(jié)點(diǎn)是固定的，無(wú)法應(yīng)對(duì)公有鏈的開(kāi)放環(huán)境，只適用于聯(lián)盟鏈或私
有鏈環(huán)境。
C、PBFT算法要求總節(jié)點(diǎn)數(shù)n>=3f+1(其中，f代表作惡節(jié)點(diǎn)數(shù))。系統(tǒng)的失效節(jié)點(diǎn)數(shù)量不得超過(guò)全網(wǎng)節(jié)點(diǎn)的1/3，容錯(cuò)率相對(duì)較低。

6、PBFT算法的應(yīng)用場(chǎng)景

PBFT算法的節(jié)點(diǎn)數(shù)量是固定的，節(jié)點(diǎn)身份提前確定，無(wú)法動(dòng)態(tài)添加或刪除，只能適用于節(jié)點(diǎn)數(shù)目固定的聯(lián)盟鏈或私有鏈場(chǎng)景中。
PBFT在很多場(chǎng)景都有應(yīng)用，在區(qū)塊鏈場(chǎng)景中，一般適合于對(duì)強(qiáng)一致性有要求的私有鏈和聯(lián)盟鏈場(chǎng)景，但如果能夠結(jié)合DPOS節(jié)點(diǎn)代表選舉規(guī)則，也可以應(yīng)用于公有鏈，并且可以在一個(gè)不可信的網(wǎng)絡(luò)里解決拜占庭容錯(cuò)問(wèn)題。在Hyperledger Fabric項(xiàng)目中，共識(shí)模塊被設(shè)計(jì)成可插拔的模塊，支持像PBFT、Raft等共識(shí)算法。

三、POW算法

1、POW算法簡(jiǎn)介

POW（Proof of Work），即工作量證明，也稱挖礦。工作量證明通過(guò)計(jì)算來(lái)猜測(cè)一個(gè)數(shù)值(nonce)，使得拼湊上交易數(shù)據(jù)后內(nèi)容的Hash值滿足規(guī)定的上限。由于Hash難題在目前計(jì)算模型下需要大量的計(jì)算，可以保證在一段時(shí)間內(nèi)，系統(tǒng)中只能出現(xiàn)少數(shù)合法提案。如果能夠提出合法提案，證明提案者確實(shí)已經(jīng)付出了一定的工作量。
哈希現(xiàn)金是一種工作量證明機(jī)制，是Adam Back在1997年發(fā)明的，用于抵抗郵件的拒絕服務(wù)***及垃圾郵件網(wǎng)關(guān)濫用。

2、POW算法原理

工作量證明的主要特征是客戶端需要做一定難度的工作得出一個(gè)結(jié)果，驗(yàn)證方卻很容易通過(guò)結(jié)果來(lái)檢查出客戶端是不是做了相應(yīng)的工作。工作量證明方案的一個(gè)核心特征是不對(duì)稱性：工作對(duì)于請(qǐng)求方是適中的，對(duì)于驗(yàn)證方則是易于驗(yàn)證的。

給定一個(gè)基本字符串，在基本字符串后面添加一個(gè)叫做nonce的整數(shù)值，對(duì)變更后（添加nonce)的字符串進(jìn)行SHA256哈希運(yùn)算，如果得到的哈希結(jié)果（以16進(jìn)制的形式表示）是以某個(gè)字符串（如"0000"）開(kāi)頭的，則驗(yàn)證通過(guò)。為了達(dá)到工作量證明的目標(biāo)，需要不停的遞增nonce值，對(duì)得到的新字符串進(jìn)行SHA256哈希運(yùn)算。
由于給定的基本字符串在不同的場(chǎng)合并不確定，對(duì)于不同的基本字符串和nonce的組合，要使用SHA256計(jì)算得到某個(gè)字符串開(kāi)頭Hash值的計(jì)算次數(shù)并不確定，但會(huì)是一個(gè)符合統(tǒng)計(jì)學(xué)規(guī)律的概率事件。
按照規(guī)則，預(yù)期大概要進(jìn)行2^16 次嘗試（哈希值的偽隨機(jī)特性可以做概率估算），才能得到4個(gè)前導(dǎo)0的哈希散列。

3、比特幣的POW實(shí)現(xiàn)

比特幣區(qū)塊由區(qū)塊頭和該區(qū)塊所包含的交易列表組成。區(qū)塊頭大小為80字節(jié)，其構(gòu)成包括：
　　 4字節(jié)：版本號(hào)
　　 32字節(jié)：上一個(gè)區(qū)塊的哈希值
　　 32字節(jié)：交易列表的Merkle根哈希值
　　 4字節(jié)：當(dāng)前時(shí)間戳
　　 4字節(jié)：當(dāng)前難度值
　　 4字節(jié)：隨機(jī)數(shù)Nonce值
　　 80字節(jié)長(zhǎng)度的區(qū)塊頭，即為比特幣Pow算法的輸入字符串。
　　交易列表附加在區(qū)塊頭之后，其中第一筆交易為礦工獲得獎(jiǎng)勵(lì)和手續(xù)費(fèi)的特殊交易。
工作量證明過(guò)程，即為不斷調(diào)整Nonce值，對(duì)區(qū)塊頭做雙重SHA256哈希運(yùn)算，使得結(jié)果滿足給定數(shù)量前導(dǎo)0的哈希值的過(guò)程，其中前導(dǎo)0的個(gè)數(shù)，取決于挖礦難度，前導(dǎo)0的個(gè)數(shù)越多，挖礦難度越大。
每創(chuàng)建2016個(gè)塊后將計(jì)算新的難度，此后的2016個(gè)塊使用新的難度。計(jì)算步驟如下：
　　A、找到前2016個(gè)塊的第一個(gè)塊，計(jì)算生成這2016個(gè)塊花費(fèi)的時(shí)間。
即最后一個(gè)塊的時(shí)間與第一個(gè)塊的時(shí)間差。時(shí)間差不小于3.5天，不大于56天。
　　B、計(jì)算前2016個(gè)塊的難度總和，即單個(gè)塊的難度x總時(shí)間。
　　C、計(jì)算新的難度，即2016個(gè)塊的難度總和/14天的秒數(shù)，得到每秒的難度值。
　　D、要求新的難度，難度不低于參數(shù)定義的最小難度。

4、POW算法的優(yōu)缺點(diǎn)

POW算法的優(yōu)點(diǎn)：
A、完全去中心化
B、節(jié)點(diǎn)自由進(jìn)出
C、安全性高
POW算法的缺點(diǎn)：
A、記賬權(quán)向資本集中
B、挖礦造成大量的資源浪費(fèi)。
C、網(wǎng)絡(luò)性能太低，需要等待多個(gè)確認(rèn)，容易產(chǎn)生分叉，區(qū)塊的確認(rèn)共識(shí)達(dá)成的周期較長(zhǎng)，不適合商業(yè)應(yīng)用。

5、POW算法的應(yīng)用場(chǎng)景

POW共識(shí)機(jī)制用在了大部分挖礦的區(qū)塊鏈項(xiàng)目，比如BTC、ETH、LTC。

四、POS算法

1、POS算法簡(jiǎn)介

POS（Proof of Stake），即權(quán)益證明，是POW的一種升級(jí)共識(shí)機(jī)制，根據(jù)每個(gè)節(jié)點(diǎn)所占代幣的比例和時(shí)間，等比例的降低挖礦難度，從而加快找隨機(jī)數(shù)的速度。
鑒于POW的缺陷，2012年Sunny King提出了POS，并基于POW和POS的混合機(jī)制發(fā)布了點(diǎn)點(diǎn)幣PPCoin。

2、POS算法原理

POS原理的核心概念為幣齡，即持有貨幣的時(shí)間。例如有10個(gè)幣、持有90天，即擁有900幣天的幣齡。
　　使用幣即意味著幣齡的銷毀。
　　在POS中有一種特殊的交易稱為利息幣，即持有人可以消耗幣齡獲得利息，同時(shí)獲得為網(wǎng)絡(luò)產(chǎn)生區(qū)塊以及POS造幣的優(yōu)先權(quán)。
POW通過(guò)算力證明自己有資格寫區(qū)塊鏈，而PoS通過(guò)擁有的幣齡來(lái)證明自己有資格寫區(qū)塊鏈。

3、POS算法的優(yōu)缺點(diǎn)

POS算法的優(yōu)點(diǎn)：
A、不消耗大量算力挖礦，節(jié)省能耗。
B、在一定程度上縮短了共識(shí)達(dá)成的時(shí)間
C、防作弊。
POS算法的缺點(diǎn)：
A、本質(zhì)仍然需要挖礦，未解決商業(yè)應(yīng)用的痛點(diǎn)
B、極端的情況下會(huì)帶來(lái)中心化的結(jié)果

4、點(diǎn)點(diǎn)幣的POS實(shí)現(xiàn)

點(diǎn)點(diǎn)幣的POS證明計(jì)算公式為：
　　proofhash < 幣齡x目標(biāo)值
　　展開(kāi)如下：
　　hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime) < bnTarget x bnCoinDayWeight
　　其中proofhash，對(duì)應(yīng)一組數(shù)據(jù)的哈希值，即hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime)。
　　幣齡即bnCoinDayWeight，即幣天，即持有的幣數(shù)乘以持有幣的天數(shù)，此處天數(shù)最大值為90天。
　　目標(biāo)值，即bnTarget，用于衡量POS挖礦難度。目標(biāo)值與難度成反比，目標(biāo)值越大、難度越??；反之亦然。
　　因此，持有的幣天越大，挖到區(qū)塊的機(jī)會(huì)越大。

五、DPOS算法

1、DPOS算法簡(jiǎn)介

DPOS（Delegated Proof of Stake），即股份授權(quán)證明算法，是在POW及POS基礎(chǔ)上誕生的一種新型共識(shí)算法，2014年4月由Bitshares的首席開(kāi)發(fā)者Dan Larimer (現(xiàn)為EOS CTO)提出并應(yīng)用。DPOS既能解決POW在挖礦過(guò)程中產(chǎn)生的DPOS大量能源過(guò)耗的問(wèn)題，也能避免POS權(quán)益分配下可能產(chǎn)生的信任天平偏頗的問(wèn)題。
DPOS是由被社區(qū)選舉的可信賬戶（超級(jí)節(jié)點(diǎn)，比如得票數(shù)前101位可以成為）來(lái)創(chuàng)建區(qū)塊。比如選出101個(gè)超級(jí)節(jié)點(diǎn)，即101個(gè)礦池，超級(jí)節(jié)點(diǎn)之間的權(quán)利是完全相等的。普通的持幣者可以隨時(shí)通過(guò)投票更換超級(jí)節(jié)點(diǎn)（礦池），DPOS的去中心化不是每個(gè)持幣者就有直接的股份權(quán)益，而是需要間接的投票權(quán)力，來(lái)保證被推選出來(lái)的超級(jí)節(jié)點(diǎn)不作惡，同時(shí)也可以自己拉選票成為超級(jí)節(jié)點(diǎn)或者備用超級(jí)節(jié)點(diǎn)。

2、DPOS算法原理

DPOS算法的基本原則：
A、持股人依據(jù)所持股份行使表決權(quán)，而不是依賴挖礦競(jìng)爭(zhēng)記賬權(quán)。
B、最大化持股人的盈利。
C、最小化維護(hù)網(wǎng)絡(luò)安全的費(fèi)用。
D、?最大化網(wǎng)絡(luò)的效能。
E、?最小化運(yùn)行網(wǎng)絡(luò)的成本 (帶寬、CPU等)，在不浪費(fèi)大量電力的情況下實(shí)現(xiàn)網(wǎng)絡(luò)的安全穩(wěn)定。
在DPOS共識(shí)算法中，區(qū)塊鏈的正常運(yùn)轉(zhuǎn)依賴于超級(jí)節(jié)點(diǎn)，超級(jí)節(jié)點(diǎn)的職責(zé)主要有：
A、提供一臺(tái)服務(wù)器節(jié)點(diǎn)，保證節(jié)點(diǎn)的正常運(yùn)行；
B、節(jié)點(diǎn)服務(wù)器收集網(wǎng)絡(luò)里的交易；
C、節(jié)點(diǎn)驗(yàn)證交易，把交易打包到區(qū)塊；
D、節(jié)點(diǎn)廣播區(qū)塊，其它節(jié)點(diǎn)驗(yàn)證后把區(qū)塊添加到自己的數(shù)據(jù)庫(kù)；
E、帶領(lǐng)并促進(jìn)區(qū)塊鏈項(xiàng)目的發(fā)展；
DPOS算法運(yùn)行機(jī)制如下：
A、所有持幣者先選出超級(jí)節(jié)點(diǎn)負(fù)責(zé)簽署區(qū)塊
B、DPOS的規(guī)則是最長(zhǎng)鏈勝出，每個(gè)超級(jí)節(jié)點(diǎn)必須按照生產(chǎn)排程，輪流產(chǎn)生區(qū)塊。假設(shè)排程排定A、Ｂ、Ｃ分別輪流生產(chǎn)區(qū)塊，在一定時(shí)間內(nèi)產(chǎn)生的區(qū)塊如下：

C、如果惡意節(jié)點(diǎn)生產(chǎn)了分叉區(qū)塊，假設(shè)Ａ、Ｃ都是誠(chéng)實(shí)的節(jié)點(diǎn)，只有B節(jié)點(diǎn)是惡意的，由于B產(chǎn)生區(qū)塊的速度（每個(gè)周期生產(chǎn)一個(gè)區(qū)塊）慢于A、Ｃ合力產(chǎn)生區(qū)塊的速度（每個(gè)周期生產(chǎn)一個(gè)區(qū)塊），根據(jù)最長(zhǎng)鏈勝出的規(guī)則，誠(chéng)實(shí)的節(jié)點(diǎn)還是會(huì)勝出。

D、同一個(gè)節(jié)點(diǎn)要產(chǎn)生重復(fù)兩個(gè)區(qū)塊的速度也要慢于誠(chéng)實(shí)節(jié)點(diǎn)合作產(chǎn)生區(qū)塊的速度，所以最長(zhǎng)鏈勝出規(guī)則會(huì)保證誠(chéng)實(shí)節(jié)點(diǎn)的鏈會(huì)勝出。
E、如果A，B，C三個(gè)超級(jí)節(jié)點(diǎn)的網(wǎng)絡(luò)出現(xiàn)碎片化，各自為政的情況。在短期內(nèi)的確可能三鏈并行，但一旦網(wǎng)絡(luò)連接恢復(fù)，短鏈自然會(huì)向最長(zhǎng)鏈回歸。超級(jí)節(jié)點(diǎn)數(shù)量為奇數(shù)，所以兩大派系勢(shì)均力敵僵持不下的情況不會(huì)維持太久，最終勢(shì)必會(huì)有其中一方的鏈更長(zhǎng)。

3、DPOS對(duì)惡意節(jié)點(diǎn)的懲罰

注冊(cè)成為候選超級(jí)節(jié)點(diǎn)需要支付一筆保證金（約10 XTS)，通常擔(dān)任超級(jí)節(jié)點(diǎn)約兩周后才可達(dá)到損益平衡，因此促進(jìn)了受托人的穩(wěn)定性，確保至少會(huì)挖滿兩周的礦。
DPOS對(duì)惡意節(jié)點(diǎn)的懲罰為：不按排程產(chǎn)生區(qū)塊的超級(jí)節(jié)點(diǎn)將在下一輪被投票剔除，被沒(méi)收繳納的保證金。
惡意節(jié)點(diǎn)在短期內(nèi)是能夠作惡的，惡意的區(qū)塊只是短時(shí)間保留而已，很快超級(jí)節(jié)點(diǎn)之間會(huì)回歸誠(chéng)實(shí)節(jié)點(diǎn)達(dá)成的共識(shí)，制造出最長(zhǎng)鏈，向沒(méi)有作惡區(qū)塊的最長(zhǎng)鏈回歸。

4、DPOS算法的優(yōu)缺點(diǎn)

DPOS算法的優(yōu)點(diǎn)：
A、能耗優(yōu)勢(shì)，網(wǎng)絡(luò)運(yùn)行成本低。
B、理論上更加去中心化。
C、較快的確認(rèn)速度。出塊速度秒級(jí)，交易確認(rèn)分鐘級(jí)。
DPOS算法的缺點(diǎn)：
A、壞節(jié)點(diǎn)不能被及時(shí)處理，只有經(jīng)過(guò)選舉才能清除壞節(jié)點(diǎn)。
B、小散投票積極性不高。
C、依賴代幣

5、DPOS算法的應(yīng)用場(chǎng)景

比特股（Bitshare）是一類采用DPOS機(jī)制的密碼貨幣，通過(guò)引入一個(gè)技術(shù)民主層來(lái)減少中心化的負(fù)面影響。
DPOS系統(tǒng)任然存在中心化，但中心化是受到控制的，超級(jí)節(jié)點(diǎn)由普通持幣者選舉產(chǎn)生。DPOS通過(guò)保留持幣者的控制權(quán)，從而使系統(tǒng)去中心化。