摘要：哈?，F(xiàn)金哈?，F(xiàn)金是一種工作量證明機(jī)制，在比特幣之前，哈?，F(xiàn)金被用于垃圾郵件的過(guò)濾。與郵件應(yīng)用程序中的相比，比特幣加密電子貨幣網(wǎng)絡(luò)采用了不同的基于哈希的工作量證明，以實(shí)現(xiàn)比特幣的競(jìng)爭(zhēng)挖掘。

工作量證明(Proof Of Work，簡(jiǎn)稱POW)，簡(jiǎn)單來(lái)講就是證明你完成了某一項(xiàng)工作。
維基百科的解釋：工作量證明系統(tǒng)是一種防止服務(wù)攻擊及其它服務(wù)濫用的經(jīng)濟(jì)方式，它要求服務(wù)請(qǐng)求方完成某些工作——通常意味著需要請(qǐng)求方計(jì)算機(jī)完成一定計(jì)算量。這種方案的一個(gè)關(guān)鍵特征是不對(duì)成性：對(duì)請(qǐng)求方來(lái)說(shuō)，所需要做的工作有較大難度；但對(duì)于服務(wù)提供方來(lái)說(shuō)，工作量的驗(yàn)證卻比較容易。
工作量證明中包含了兩層含義:

工作者需要完成的工作必須有一定的量，這個(gè)量由工作驗(yàn)證者給出；

驗(yàn)證者可以迅速的檢驗(yàn)工作量是否達(dá)標(biāo)，注意這里的檢驗(yàn)完成過(guò)程必須簡(jiǎn)單；

區(qū)塊鏈的一個(gè)關(guān)鍵點(diǎn)就是，一個(gè)人必須經(jīng)過(guò)一系列困難的工作，才能將數(shù)據(jù)放入到區(qū)塊鏈中。正是這種困難的工作，才使得區(qū)塊鏈?zhǔn)前踩鸵恢碌摹４送?，完成這個(gè)工作的人也會(huì)獲得獎(jiǎng)勵(lì)（這也就是通過(guò)挖礦獲得幣）。

在比特幣中，這個(gè)工作的目的是為了找到一個(gè)塊的哈希，同時(shí)這個(gè)哈希滿足了一些必要條件。這個(gè)哈希，也就充當(dāng)了證明的角色。因此，尋求證明（尋找有效哈希），就是實(shí)際要做的事情。

工作量證明最常用的技術(shù)原理是哈希函數(shù)。哈希有以下幾個(gè)關(guān)鍵特性：

無(wú)法從一個(gè)哈希值恢復(fù)原始數(shù)據(jù)

對(duì)于特定的數(shù)據(jù)，只能有一個(gè)哈希，并且這個(gè)哈希是唯一的

即使是僅僅改變輸入數(shù)據(jù)中的一個(gè)字節(jié)，也會(huì)導(dǎo)致輸出一個(gè)完全不同的哈希

由于輸入散列函數(shù)H()的任意值n，會(huì)對(duì)應(yīng)到一個(gè)H(n)結(jié)果，而n只要變動(dòng)一個(gè)比特，就會(huì)引起雪崩效應(yīng)(avalanche effect)，所以幾乎無(wú)法從H(n)反推回n，因此借由指定查找H(n)的特征，讓用戶進(jìn)行大量的窮舉運(yùn)算，就可以達(dá)成工作量證明。

在區(qū)塊鏈中，哈希被用于保證一個(gè)塊的一致性。哈希算法的輸入數(shù)據(jù)包含了前一個(gè)塊的哈希，因此使得不太可能去修改鏈中的一個(gè)塊：因?yàn)槿绻粋€(gè)人想要修改前面一個(gè)塊的哈希，那么他必須要重新計(jì)算這個(gè)塊以及后面所有塊的哈希。

我們?nèi)糁付℉(n)的16進(jìn)制值的前四值，求n，這樣統(tǒng)計(jì)上平均約要運(yùn)行16的4次方次H(n)散列運(yùn)算，才會(huì)得到答案，但驗(yàn)算只要進(jìn)行一次就可以了。如果想要增加難度，那就增加指定的位數(shù)即可。以SHA256函數(shù)舉例，假設(shè)我們要處理數(shù)據(jù)Hello World，并找出H(n)前四值為0000的n，如果從Hello World0開始加上一個(gè)十進(jìn)制數(shù)ASCII進(jìn)行窮舉猜測(cè)，到Hello World107105時(shí)才會(huì)得到匹配條件的H(n)：

>>> import hashlib
>>> ss = "Hello World107105".encode()
>>> hashlib.sha256(ss).hexdigest()
"0000bfe6af4232f78b0c8eba37a6ba6c17b9b8671473b0b82305880be077edd9"

而驗(yàn)算時(shí)只要將Hello World107105代入SHA256函數(shù)一次即可。

哈?，F(xiàn)金是一種工作量證明機(jī)制，在比特幣之前，哈?，F(xiàn)金被用于垃圾郵件的過(guò)濾。哈希現(xiàn)金（hashcash ）的靈感來(lái)自于這樣一個(gè)想法，即一些數(shù)學(xué)結(jié)果難于發(fā)現(xiàn)而易于校驗(yàn)。比特幣使用的原理就類似于HashCash。與郵件應(yīng)用程序中的hashcash相比，比特幣加密電子貨幣網(wǎng)絡(luò)采用了不同的基于哈希的工作量證明，以實(shí)現(xiàn)比特幣的競(jìng)爭(zhēng)挖掘。

盡管hashcash使用SHA-1散列，并且要求160個(gè)散列位中的前20個(gè)為零，但比特幣的工作證明使用兩個(gè)連續(xù)的SHA-256散列，并且最初需要至少256個(gè)散列位中的前32個(gè)為零。然而，比特幣網(wǎng)絡(luò)定期重置難度級(jí)別，以保持每小時(shí)6塊的平均創(chuàng)建速度。截至2017年8月（區(qū)塊＃478608），比特幣網(wǎng)絡(luò)已經(jīng)要求256個(gè)哈希位中的前72個(gè)必須為零。

工作量證明的算法可以大概描述為：在一個(gè)時(shí)間段同時(shí)有多臺(tái)服務(wù)器對(duì)這一段時(shí)間的交易進(jìn)行打包，打包完成后連帶區(qū)塊Header信息一起經(jīng)過(guò)SHA256算法進(jìn)行運(yùn)算。在區(qū)塊頭以及獎(jiǎng)勵(lì)交易coinbase里各有一個(gè)變量nonce，如果運(yùn)算的結(jié)果不符合難度要求，那么就調(diào)整nonce的值繼續(xù)運(yùn)算。如果有某臺(tái)服務(wù)器率先計(jì)算出了符合難度值的區(qū)塊，那么它可以廣播這個(gè)區(qū)塊。其他服務(wù)器驗(yàn)證沒(méi)問(wèn)題后就可以添加到現(xiàn)有區(qū)塊鏈上，然后大家再一起競(jìng)爭(zhēng)下一個(gè)區(qū)塊。這個(gè)過(guò)程也稱為挖礦。

比特幣網(wǎng)絡(luò)中任何一個(gè)節(jié)點(diǎn)，如果想生成一個(gè)新的區(qū)塊并寫入?yún)^(qū)塊鏈，必須解出比特幣網(wǎng)絡(luò)出的工作量證明的迷題。這道題關(guān)鍵的三個(gè)要素是工作量證明函數(shù)、區(qū)塊及難度值。工作量證明函數(shù)是這道題的計(jì)算方法，區(qū)塊決定了這道題的輸入數(shù)據(jù)，難度值決定了這道題的所需要的計(jì)算量。

和我們上節(jié)例子中用到的哈希函數(shù)一樣，比特幣系統(tǒng)中使用的工作量證明函正是SHA256。SHA是安全散列算法（Secure Hash Algorithm）的縮寫，是一個(gè)密碼散列函數(shù)家族。這一組函數(shù)是由美國(guó)國(guó)家安全局（NSA）設(shè)計(jì)，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST） 發(fā)布的，主要適用于數(shù)字簽名標(biāo)準(zhǔn)。SHA256就是這個(gè)函數(shù)家族中的一個(gè)，是輸出值為256位的哈希算法。到目前為止，還沒(méi)有出現(xiàn)對(duì)SHA256算法的有效攻擊。

比特幣的區(qū)塊由區(qū)塊頭及該區(qū)塊所包含的交易列表組成。區(qū)塊頭的大小為80字節(jié)，由4字節(jié)的版本號(hào)、32字節(jié)的上一個(gè)區(qū)塊的散列值、32字節(jié)的Merkle Root Hash、4字節(jié)的時(shí)間綴（當(dāng)前時(shí)間）、4字節(jié)的當(dāng)前難度值、4字節(jié)的隨機(jī)數(shù)組成。區(qū)塊包含的交易列表則附加在區(qū)塊頭后面，其中的第一筆交易是coinbase交易，這是一筆為了讓礦工獲得獎(jiǎng)勵(lì)及手續(xù)費(fèi)的特殊交易。區(qū)塊的大致結(jié)構(gòu)如下：

難度值（difficulty）是礦工們?cè)谕诘V時(shí)候的重要參考指標(biāo)，它決定了礦工大約需要經(jīng)過(guò)多少次哈希運(yùn)算才能產(chǎn)生一個(gè)合法的區(qū)塊。比特幣的區(qū)塊大約每10分鐘生成一個(gè)，如果要在不同的全網(wǎng)算力條件下，新區(qū)塊的產(chǎn)生保持都基本這個(gè)速率，難度值必須根據(jù)全網(wǎng)算力的變化進(jìn)行調(diào)整。簡(jiǎn)單地說(shuō)，難度值被設(shè)定在無(wú)論挖礦能力如何，新區(qū)塊產(chǎn)生速率都保持在10分鐘一個(gè)。

難度的調(diào)整是在每個(gè)完整節(jié)點(diǎn)中獨(dú)立自動(dòng)發(fā)生的。每2016個(gè)區(qū)塊，所有節(jié)點(diǎn)都會(huì)按統(tǒng)一的公式自動(dòng)調(diào)整難度，這個(gè)公式是由最新2016個(gè)區(qū)塊的花費(fèi)時(shí)長(zhǎng)與期望時(shí)長(zhǎng)（期望時(shí)長(zhǎng)為20160分鐘即兩周，是按每10分鐘一個(gè)區(qū)塊的產(chǎn)生速率計(jì)算出的總時(shí)長(zhǎng)）比較得出的，根據(jù)實(shí)際時(shí)長(zhǎng)與期望時(shí)長(zhǎng)的比值，進(jìn)行相應(yīng)調(diào)整（或變難或變易）。也就是說(shuō)，如果區(qū)塊產(chǎn)生的速率比10分鐘快則增加難度，比10分鐘慢則降低難度。
這個(gè)公式可以總結(jié)為如下形式：

New Difficulty = Old Difficulty * (Actual Time of Last 2016 Blocks / 20160 minutes)

我們可以把比特幣礦工解這道工作量證明迷題的步驟大致歸納如下：

生成Coinbase交易，并與其他所有準(zhǔn)備打包進(jìn)區(qū)塊的交易組成交易列表，通過(guò)Merkle Tree算法生成Merkle Root Hash

把Merkle Root Hash及其他相關(guān)字段組裝成區(qū)塊頭，將區(qū)塊頭的80字節(jié)數(shù)據(jù)（Block Header）作為工作量證明的輸入

不停的變更區(qū)塊頭中的隨機(jī)數(shù)即nonce的數(shù)值，并對(duì)每次變更后的的區(qū)塊頭做雙重SHA256運(yùn)算（即SHA256(SHA256(Block_Header))），將結(jié)果值與當(dāng)前網(wǎng)絡(luò)的目標(biāo)值做對(duì)比，如果小于目標(biāo)值，則解題成功，工作量證明完成。

該過(guò)程可用下圖表示：

Hash值是由數(shù)字和大小寫字母構(gòu)成的字符串，每一位有62種可能性（可能為26個(gè)大寫字母、26個(gè)小寫字母，10個(gè)數(shù)字中任一個(gè)），假設(shè)任何一個(gè)字符出現(xiàn)的概率是均等的，那么第一位為0的概率是1/62（其他位出現(xiàn)什么字符先不管），理論上需要嘗試62次Hash運(yùn)算才會(huì)出現(xiàn)一次第一位為0的情況，如果前兩2位為0，就得嘗試62的平方次Hash運(yùn)算，以n個(gè)0開頭就需要嘗試62的n次方次運(yùn)算。

以下是區(qū)塊鏈POW部分代碼的精簡(jiǎn)展示，完整代碼可參考地址

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

...
import hashlib
...

class Blockchain(object):
    ...

    def proof_of_work(self, last_proof):
        proof = 0
        while self.valid_proof(last_proof, proof) is False:
            proof += 1
        return proof

    @staticmethod
    def valid_proof(last_proof, proof):
        guess = f"{last_proof}{proof}".encode()
        guess_hash = hashlib.sha256(guess).hexdigest()
        return guess_hash[:4] == "0000"

參考

Pricing via Processing or Combatting Junk Mail

Learn Blockchains by Building One

Proof-of-work system - Wikipedia

什么是工作量證明？

Learn Blockchains by Building One