上一節(jié)課我們了解了常用的幾種共識算法，今天我們詳細(xì)地分析PoW(Proof-of-Work，工作量證明)共識算法，了解其來源和優(yōu)缺點(diǎn)。

在學(xué)習(xí)課程的時候，你也可以領(lǐng)取BaaS平臺為期一個月的試用機(jī)會，免費(fèi)使用高性能區(qū)塊鏈服務(wù)（點(diǎn)擊鏈接即可免費(fèi)領(lǐng)取https://blockchain.xunlei.com/baas/try.html）。課程學(xué)習(xí)結(jié)合實(shí)踐操作，讓你迅速成為區(qū)塊鏈大牛！

*以下為第十二課的內(nèi)容~

第十二課 PoW共識算法

1. 概述

PoW(Proof-of-Work，工作量證明)是比特幣采用的共識機(jī)制。由于比特幣在加密貨幣中的重要地位，PoW也成為后續(xù)加密貨幣系統(tǒng)的主流共識機(jī)制之一。

PoW是一種針對拒絕服務(wù)攻擊的應(yīng)對方法，其要求客戶端執(zhí)行某些需要消耗資源的運(yùn)算，而其答案能被服務(wù)方快速驗(yàn)算，以耗用的時間、設(shè)備與能源做為擔(dān)保成本，以確保服務(wù)無法被惡意節(jié)點(diǎn)所濫用。

2. PoW機(jī)制的來源

這個概念由Cynthia Dwork 和Moni Naor 1993年在學(xué)術(shù)論文《 Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology》中首次提出；而“Proof of Work”一詞則是在1999年由Markus Jakobsson與Ari Juels發(fā)表的論文《Proofs of Work and Bread Pudding Protocols》中提出正式的定義；PoW技術(shù)最初在Hashcash中應(yīng)用。Hashcash是Adam Back 在1997年提出的，作為一種遏制互聯(lián)網(wǎng)系統(tǒng)資源被濫用的措施，例如反垃圾電子郵件應(yīng)用。

Hashcash要求郵件客戶端生成一個字符串，用SHA-1算法計(jì)算這個字符串得到的哈希值中，有特定數(shù)量的0前綴。SHA-1算法的碰撞非常困難，而且要求的哈希值的前綴0的數(shù)量越多，客戶端要找到符合條件的字符串需要的計(jì)算量就越大。在電子郵件的應(yīng)用中，為了給發(fā)出的消息加上戳記，只需要向電子郵件添加頭部字段即可：用于電子郵件的每一個 To: 或 Cc: 接收者的 X-Hashcash 頭。例如，某個想給adam@cypherspace.org這個郵箱發(fā)送消息的人可能會在消息中包含一個X-Hashcash消息頭：

X-Hashcash:

1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi

服務(wù)端可以通過檢查戳記的SHA-1散列來校驗(yàn)它，如下所示：

00000b7c65ac70650eb8d4f034e86d7d5cd1852f

可見，哈希結(jié)果有5個前綴字符是0，每個字符占4個比特，因此這個哈希值的前20個比特為零，即前綴0的比特?cái)?shù)量為20。

Hashcash的頭部格式為：1:bits📅resource:ext:salt:suffix，包括 7 個域：

版本號。

前綴為0的比特?cái)?shù)量。若其哈希值的0前綴數(shù)量少于此數(shù)，那么它就是非法的。

生成戳記的日期。可以認(rèn)為當(dāng)前時間之后的戳記以及那些在很久以前的戳記是非法的。

戳記為哪個資源而生成。可能是一個電子郵件地址，但是也可能是一個 URI 或者其他命名的資源。

特定應(yīng)用程序可能需要的擴(kuò)展，通常為空。

隨機(jī)因子（salt）。用于將該戳記與其他人為相同的資源在同一日期生成的戳記區(qū)別開來。

后綴字符串。是算法真正起作用的部分。由于在特定的時間，A給B發(fā)郵件，前 6 個域就已經(jīng)是固定的，為了生成一個通過期望數(shù)目的前導(dǎo)零進(jìn)行散列的的戳記，客戶端必須嘗試很多連續(xù)的后綴值。

通過讓郵件客戶端做這樣的計(jì)算，能有效防止垃圾郵件的泛濫。生成一個 20比特0前綴哈希的字符串只需要幾秒鐘的時間，當(dāng)你一天中只發(fā)送幾十封電子郵件時，這個代價(jià)并不大。但是，對那些想要發(fā)送數(shù)百萬消息的垃圾郵件制造者來說，這就是無法承受的消耗。

在比特幣出現(xiàn)之前，Hashcash的PoW算法也被Hal Finney以可重復(fù)使用的工作量證明（RPOW）的形式用于一種比特幣之前的加密貨幣實(shí)驗(yàn)中。另外，Wei Dai的B-money、Nick Szabo的Bit-Gold這些數(shù)字貨幣的先行者，都是基于Hashcash的PoW機(jī)制下進(jìn)行挖礦的。

3. 比特幣的PoW共識機(jī)制

比特幣網(wǎng)絡(luò)于2009年上線。比特幣網(wǎng)絡(luò)的PoW共識機(jī)制使用基于Hashcash的PoW來挖礦，挖礦節(jié)點(diǎn)發(fā)布自己的計(jì)算結(jié)果，由比特幣P2P網(wǎng)絡(luò)上的去中心化節(jié)點(diǎn)負(fù)責(zé)驗(yàn)證。比特幣的PoW計(jì)算難度會被周期性的調(diào)整，以保證出塊時間的穩(wěn)定。

3.1. 哈希函數(shù)的選擇

由于SHA-1已被證明不安全，比特幣采用了SHA-2系列的SHA-256算法作為哈希函數(shù)。使用SHA-256作為哈希函數(shù)時，無論輸入長度為多少，輸出總有一個固定的256位（32字節(jié)）長度。

由于PoW嚴(yán)重依賴于哈希算法，因此哈希算法的安全性至關(guān)重要。若使用了不安全的哈希算法，則惡意節(jié)點(diǎn)能付出遠(yuǎn)小于其它誠實(shí)節(jié)點(diǎn)的計(jì)算量，就能找到符合要求的字符串，這樣惡意節(jié)點(diǎn)就可能承包所有的出塊，獲得所有的獎勵，并能隨意篡改數(shù)據(jù)。

理論上進(jìn)行暴力破解SHA-1至少需要2的80次方（哈希循環(huán)的一個周期）才能碰撞破解。但是在2005年，中國密碼學(xué)家王小云院士提出哈希函數(shù)的碰撞攻擊理論，只用了2的69次方次就完成了SHA-1的循環(huán)碰撞周期。

不容忽視的是，SHA-1和SHA-2使用了相同的Merkle-Damgard引擎，這意味著對SHA-1的成功攻擊行為會影響到SHA-2的安全，即使還沒有宣布一個全輪回的SHA-2被成功攻破，但毫無疑問，攻擊機(jī)制正被私下的研發(fā)。這也是NIST贊助SHA-3競賽的一個原因，NIST感覺需要一個與之前算法不同的哈希算法。

NIST設(shè)置的篩選SHA-3的標(biāo)準(zhǔn)為：

l 候選散列函數(shù)必須好實(shí)現(xiàn)。它應(yīng)該消耗最少的資源即使散列大量的消息文本。許多候選算法實(shí)際上無法達(dá)到這個要求。

l 候選算法在安全性方面必須是保守的。它應(yīng)該抵御已知的攻擊，同時保持一個大的安全系數(shù)。它應(yīng)該同SHA-2相同的四個散列大小(224bit、256bit、384bit或512bit)，但如果需要能夠支持更長的散列位寬。

l 候選算法必須接受密碼分析。源代碼和分析結(jié)果公開為感興趣的第三方審查和評論。在分析過程中發(fā)現(xiàn)的任何缺陷都需要解決，通過調(diào)整或通過重新設(shè)計(jì)。

l 候選算法必須使代碼多樣性。它不能使用Merkle-Damgard引擎產(chǎn)生消息散列。

2012年10月2日，Keccak哈希算法被選為NIST散列函數(shù)競賽的勝利者。Keccak算法（讀作為“ket-chak”）是Guido Bertoni, Joan Daemen, Michael Peters, and Giles Van Assche的工作，在2008年10月被提交作為SHA-3的一個候選算法。

Keccak采用了創(chuàng)新的的“海綿引擎”散列消息文本，它抗碰撞性好、快速、設(shè)計(jì)簡單、方便硬件實(shí)現(xiàn)。Keccak已可以抵御最少復(fù)雜度為2的n次方的攻擊，其中N為散列的大小（比特位數(shù)），具有廣泛的安全界限。至目前為止，第三方密碼分析已經(jīng)顯示出Keccak沒有嚴(yán)重的弱點(diǎn)。盡管如此，Keccak的創(chuàng)建者已經(jīng)啟動Crunchy加密比賽，挑戰(zhàn)人們?nèi)グl(fā)現(xiàn)和報(bào)告成功且可驗(yàn)證的對Keccak的攻擊方法。

2015年， NIST 批準(zhǔn)了SHA-3的標(biāo)準(zhǔn)草案，Keccak哈希算法正式成為SHA-3標(biāo)準(zhǔn)。根據(jù)wikipedia，SHA家族函數(shù)的比較情況如下：

圖1. SHA家族函數(shù)對比(資料來自wikipedia.org)

3.2. 比特幣的PoW

比特幣的PoW共識機(jī)制也常被稱為Nakamoto 共識或中本聰共識，以比特幣的發(fā)明者中本聰Satoshi Nakamoto命名。

比特幣用區(qū)塊頭部的其中6個字段作為工作量證明的輸入字符串。參與PoW計(jì)算的6個字段總大小為80字節(jié)，由4字節(jié)的版本號、32字節(jié)的上一個區(qū)塊的散列值、32字節(jié)的Merkle Root Hash、4字節(jié)的時間戳（當(dāng)前時間）、4字節(jié)的當(dāng)前難度值、4字節(jié)的隨機(jī)數(shù)組成，如下表所示：

表1. 參與哈希計(jì)算的區(qū)塊頭

比特幣的PoW，就是要求挖礦節(jié)點(diǎn)找到一個合適的 nonce, 即令nonce從0開始遞增，直到使得這區(qū)塊頭部經(jīng)過2次SHA-256計(jì)算（即SHA256(SHA256(BlockHeader))）的哈希值小于當(dāng)前區(qū)塊的目標(biāo)閾值。比特幣的nonce是一個4字節(jié)的無符號整數(shù)，若嘗試完所有的4字節(jié)無符號整數(shù)還是沒找到符合要求的值，則可以修改time，或修改coinbase交易以改變mrkl_root，然后再重新尋找滿足條件的nonce值。

由于SHA-256的哈希值是256-bit的，因此目標(biāo)閾值(target threshold)也是一個256-bit（32字節(jié)）的無符號整型，要求區(qū)塊頭的哈希值必須小于等于此值。

比特幣的難度值是動態(tài)調(diào)整的。每出2016個區(qū)塊就調(diào)整一次難度值，如果區(qū)塊產(chǎn)生的速率比10分鐘快則增加難度，比10分鐘慢則降低難度。調(diào)整公式如下：

難度值 = 舊難度值 * ( 過去2016個區(qū)塊花費(fèi)時長 / 20160 分鐘 )

而使用這個難度值來計(jì)算目標(biāo)閾值的計(jì)算公式為：

目標(biāo)閾值 = 最大目標(biāo)值 / 難度值

其中最大目標(biāo)值為一個恒定值：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

根據(jù)上述公式可知，目標(biāo)值的大小與難度值成反比。難度值越大，則目標(biāo)值越小，即符合要求的哈希值的前綴0的數(shù)量越多，導(dǎo)致查找隨機(jī)數(shù)(nonce)的計(jì)算時間就越長。

比特幣將這個32字節(jié)長度的目標(biāo)閾值通過類似科學(xué)計(jì)數(shù)法的方法將其壓縮為4字節(jié)的表示，結(jié)果即為區(qū)塊頭部的bits字段。比特幣規(guī)定，bits編碼由兩個部分組成：bits值的最高位的1個字節(jié)為冪（exponent），接下來3個字節(jié)為系數(shù)(coefficient)，這樣，計(jì)算目標(biāo)閾值的公式為：

Target = coefficient * 256^(exponent – 3）

3.3. 區(qū)塊頭實(shí)例解析

下面以比特幣的實(shí)際區(qū)塊為例說明區(qū)塊頭部組成和目標(biāo)閾值的計(jì)算方法。我們可以在 https://www.blockchain.com/explorer，查看區(qū)塊數(shù)據(jù)，例如區(qū)塊高度為552020的頁面顯示如下：

圖2. 552020的區(qū)塊頭

在這個頁面可以看到區(qū)塊頭的全部字段，例如區(qū)塊生成時間是“2018-11-30 09:14:39”；區(qū)塊的bits值為388648495；nonce值為2211011375；區(qū)塊的hash值為：0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e。通過 https://blockchain.info/rawblock接口可查看包含所有交易數(shù)據(jù)在內(nèi)的區(qū)塊的全部內(nèi)容：https://blockchain.info/rawblock/0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e

其中區(qū)塊頭如下：

接下來我們可以算下這個區(qū)塊的目標(biāo)閾值。從上圖可以看到，這個區(qū)塊的bits值為388648495，先將其轉(zhuǎn)換成16進(jìn)制表示為：0x172A4E2F，如前所述，這個值包含兩個部分，最高位的1個字節(jié)為冪：exponent = 0x17

接下來3個字節(jié)為系數(shù)：coefficient = 0x2A4E2F

代入目標(biāo)閾值的計(jì)算公式：

Target = coefficient * 256^(exponent – 3)= 0x2A4E2F * 256^(0x17– 3)= 0x2A4E2F0000000000000000000000000000000000000000

由于目標(biāo)閾值是32字節(jié)的，這個值為23個字節(jié)，只要在高位補(bǔ)9個字節(jié)的0，即為目標(biāo)閾值：0x0000000000000000002A4E2F0000000000000000000000000000000000000000

也就是說，552020這個區(qū)塊的哈希值要小于等于這個目標(biāo)值。區(qū)塊的實(shí)際哈希值0x0000000000000000001a8fece3de933223b7464b8467c951b65a651b2155675e，是滿足條件的。而使哈希值滿足條件而找到的nonce值為2211011375。

3.4. 交易確認(rèn)

比特幣系統(tǒng)在挖礦的過程中每10分鐘生成一個區(qū)塊，所有節(jié)點(diǎn)可以利用這10分鐘的時間，來完成接收，打包，見證的工作，同時將產(chǎn)生的交易在整個網(wǎng)絡(luò)里進(jìn)行廣播。PoW要面對的一個問題是區(qū)塊分叉，為此比特幣規(guī)定每個交易需要至少有5個驗(yàn)證過的區(qū)塊在其后面得到驗(yàn)證才能算作確認(rèn)，也就是說比特幣的共識機(jī)制認(rèn)為等待6個確認(rèn)的情況下，分叉切換的概率就足夠低了(例如按一個節(jié)點(diǎn)1%的算力來計(jì)算，6個區(qū)塊后被長度被趕超的概率是100的6次方分之1)，因此，比特幣的交易確認(rèn)時間在1小時以上。

4. 以太坊的PoW共識機(jī)制

4.1. Ethash算法

以太坊設(shè)計(jì)了ethash作為工作量證明算法，包括找到算法的隨機(jī)數(shù)輸入以使結(jié)果低于特定的難度閾值。它的特點(diǎn)是計(jì)算的效率不僅與CPU相關(guān)，還與內(nèi)存大小和內(nèi)存帶寬相關(guān)。該算法的一般流程如下：

首先根據(jù)塊信息計(jì)算一個種子。

使用這個種子，計(jì)算出一個16MB的cache數(shù)據(jù)。

通過cache，計(jì)算出一個1GB(初始大小)的數(shù)據(jù)集(DAG)。DAG可以理解為是一個完整的搜索空間，全客戶端和礦工需要存儲完整的DAG，挖礦過程中需要從DAG中重復(fù)的隨機(jī)抽取數(shù)據(jù)拿去和其他數(shù)據(jù)計(jì)算哈希值（類似于比特幣挖礦中查找合適Nonce）。

DAG中每個元素的生成只依賴于cache中的少量數(shù)據(jù)，驗(yàn)證者可以從Cache快速計(jì)算DAG指定位置的元素，以執(zhí)行哈希驗(yàn)證。

每3000個區(qū)塊的DAG完全不同，并且它的大小也隨時間線性增長，從1G開始，每年大約增長7G左右。

由于僅根據(jù)cache就可以使用少量內(nèi)存快速的計(jì)算出DAG中指定位置的數(shù)據(jù)，所以輕客戶端只需要存儲cache就可以高效的進(jìn)行校驗(yàn)。

參與哈希計(jì)算的區(qū)塊頭內(nèi)容，以太坊和比特幣之間最主要的的區(qū)別是，以太坊區(qū)塊不僅包含交易列表也包含最近狀態(tài)（merkle patricia trie結(jié)構(gòu)的根hash編碼在狀態(tài)中更精確）。除此之外，另外兩個值，區(qū)塊數(shù)和難度，也儲存在區(qū)塊中。

借助DAG結(jié)構(gòu)，Ethash工作量證明是內(nèi)存難解的，也就是需要大量的內(nèi)存用于存儲數(shù)據(jù)，并且計(jì)算過程需要頻繁訪問內(nèi)存，占用大量的內(nèi)存帶寬，這使它能抵抗類似比特幣那樣的ASIC礦機(jī) ，以支持礦工可以用電腦的CPU挖礦。但自從GPU礦工的效率高出兩個數(shù)量級，CPU挖礦就不再盈利了。

4.2. 交易確認(rèn)

與比特幣類似，以太坊的交易同樣需要等待6區(qū)塊以確認(rèn)交易。以太坊的難度調(diào)整的方式是每15秒整個網(wǎng)絡(luò)會產(chǎn)生一個區(qū)塊，這個"心跳"基本上主要強(qiáng)調(diào)系統(tǒng)狀態(tài)同步，保證不可能維持一個分叉（允許double spend）或被惡意分子重寫歷史，除非攻擊者有半數(shù)以上的網(wǎng)絡(luò)挖礦能力（即所謂的 51% 攻擊）。

5. 小結(jié)

目前業(yè)界普遍認(rèn)為PoW是最適合公鏈的共識機(jī)制，優(yōu)點(diǎn)是開放，任何人都可以參與進(jìn)來；不需要任何權(quán)威機(jī)構(gòu)的介入也能保證安全。

然而其缺點(diǎn)也同樣明顯，例如速度慢、能耗巨大、導(dǎo)致集中化的礦池等。而且從長遠(yuǎn)來看，隨著技術(shù)的發(fā)展，依靠算力的機(jī)制也終會被算力打敗，PoW共識機(jī)制將變得不再安全，例如，有人可能會制造一臺量子計(jì)算機(jī)，算力可能比其他人快百億倍，能夠在一秒鐘內(nèi)破壞比特幣或以太坊區(qū)塊鏈。因此，人們也有充足的理由和動力去研發(fā)其它的共識機(jī)制。

總結(jié)

以上是生活随笔為你收集整理的《迅雷链精品课》第十二课：PoW 共识算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。