區塊鍊中的密碼學(3)：密碼學Hash算法和挖礦

接上文：

區塊鍊中的密碼學(1)：提升密碼學的認知

區塊鍊中的密碼學(2)：密碼學基本介紹

​談及挖礦，首選浮現在腦海中的應該是：

但區塊鍊中的挖礦其實這樣的：

機架上排滿礦機，不停地在做運算，而且是是在做Hash運算。有人稱這種挖礦為能源黑産，把電能轉化為數字貨币。那我們今天就來談談Hash算法和POW共識算法的關系。

01 Hash算法

談及Hash，我們要區分普通的Hash算法和密碼學中的Hash算法。

普通的Hash算法，一般也稱之為散清單或哈希表，屬于一種基本的資料結構。一般用于實作O(1)的查詢條件之中, 涉及哈希函數的選取和解決哈希碰撞問題。

它的應用十分廣泛，像C++标準庫中的hashmap, Java中的HashMap，Python中的dict，都采用Hash算法實作。另外想很多緩存産品， memecached, redis都是hash算法的大規模應用。

而密碼學中的Hash算法，可以用一個公式來描述：

摘要/散列值/指紋 = hash(消息)

算法的輸入是消息，或者一堆二進制内容。最終輸出的是固定長度的一個二進制串，可稱之為摘要，散列值，指紋等。hash算法也有很多種。密碼學的hash算法有五大重要特征：

1. 消息是輸入相同，輸出值相同，而且所有的輸出都是等長；
2. 不管輸入多長，運算速度快；
3. 算法具備單向性，極難通過輸出值擷取輸入值；
4. 輸入資訊一旦被修改，即使很輕微的修改，輸出值也不一樣；
5. 不存在hash碰撞。也就是很難找到兩個不同的消息，他們的輸出值是一樣的；

密碼學Hash算法很多，比如MD4， SHA。但MD5被中國的王小雲教授證明是不安全的，是以目前使用廣泛的是SHA族類算法。比特币中使用的是SHA-256算法。

我們可以示範一下Python中使用SHA-256的過程：

% python              Python 3.7.3 (default, Nov 15 2019, 04:04:52)              >>> import hashlib              >>> hashlib.sha256("hello world!".encode('utf-8')).hexdigest()              '7509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9'              >>> hashlib.sha256("hello world".encode('utf-8')).hexdigest()              'b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9'              >>> hashlib.sha256("hello world, bitcoin ethereum consusus".encode('utf-8')).hexdigest()              '39a0a566f63869830e769533c4efabd31cba7cf624cd23e67638a25354fa5c10'
           

 
密碼學的Hash算法的特性決定了它的應用範圍，經常被用于身份驗證，檔案指紋，消息防篡改等各個方面。      

下面，我們講跟區塊鍊極其相關的一種應用，HashCash。

02 HashCash

HashCash我們在文章《從區塊技術的發展曆史看區塊鍊是什麼？》中提到，由Adam Back設計，具體論文見：http://www.hashcash.org/papers/hashcash.pdf。Adam Back在今天的區塊鍊行業仍然具有巨大的影響力。他是Blockstream公司的創始人和CEO，比特币核心開發者大部分都是Blockstream公司的雇員。

HashCash最早出現是為了解決網絡中的資源被大量濫用，特别是垃圾郵件泛濫。怎麼辦呢？

HashCash的思路很簡單，在發郵件前能不能先幹點小活兒，做對了我才接收你的郵件。這個活兒不能太重，但至少要占用發送方的一些資源。

這個流程其實大家應該很熟悉：

12306占用的是人的注意力，HashCash是CPU的算力，他的方式是：

1. 在電子郵件的消息頭中，增加一個 hashcash 戳記（hashcash stamp）散列值;
2. 該散列中包含收件人位址，發送時間，salt，該散列值特别之處在于它至少前20位必須是0才是一個合法的hashcash戳記
3. 為了得到合法的散列值，發送者必須經過許多次嘗試（改變salt值）才能獲得。

 HashCash背後的設計思路就是希望基于的數學難題，希望你做一些的工作，也就是付出CPU的計算代價(這個概念很重要，比特币中這個也是關鍵)，得到正确的結果，才能擷取某些資源（比方說往你的郵箱發送垃圾郵件）。

Hash算法速度相對快，輸入資料相差一點點，都會導緻散列值千差萬别的特性，被Adam Back選中。用cash代表付出算力之後的資源回報，用詞非常精當，特别延用到比特币中作為POW共識算法的核心，才合适不過。

03 比特币挖礦

以比特币為代表的區塊鍊技術稱之為分布式賬本。既然是賬本，就存在非常核心的問題，賬房先生在哪裡？誰來負責記賬呢？

在傳統的中心化應用中，處理這個問題很簡單，在應用的賬戶系統系統裡面，設定不同的權限即可，把這種核心權限賦予極少部分的人來處理。

但比特币是一個純粹的P2P系統，每個節點的權限和地位都是一樣的，相當于很多人要一起決策一件事情，這個過程在區塊鍊裡面稱之為共識(Consensus)，共識的機制也就成稱之為共識算法。

中本聰在設計比特币算法的時候，受到HashCash的啟發，采取工作量證明的方式來實作記賬過程，參與記賬的節點，稱之為礦工。工作量證明在比特币白皮書中明确提到，具體見：

https://github.com/ConsensusDev/whitepaper/blob/master/bitcoin.md（整理了各種版本），有詳細的描述。

礦工合并收到的交易形成一個完整的區塊，區塊頭由一些字段構成，其中最後一個字段nonce是可變的，礦工不斷修改nonce的值，并計算整個區塊頭的hash值，當hash值小于某個目标值的時候，才算記賬成功，本區塊是一個合法區塊，廣播到全網，礦工獲得記賬獎勵。目标值跟難度值相關聯。難度值越大，目标值越小(hash值前面的0越多)，挖礦難度越高。

核心尋找nonce的過程類似于下面一段代碼：

def proof_of_work(header, difficulty_bits):                  # calculate the difficulty target                 target = 2 ** (256-difficulty_bits)                  for nonce in xrange(max_nonce):                      hash_result = hashlib.sha256(str(header)+str(nonce)).hexdigest()                      # check if this is a valid result, below the target                      if long(hash_result, 16) < target:                          print "Success with nonce %d" % nonce                          print "Hash is %s" % hash_result                          return (hash_result,nonce)                      print "Failed after %d (max_nonce) tries" % nonce                      return nonce
           

完整的代碼見：

https://github.com/ConsensusDev/code/blob/master/pow/proof_of_work.py

運算難度随難度的增加指數增加，筆者電腦為2018年款的macbook，截取一些運算結果如下：

Difficulty: 1048576 (20 bits)              Starting search...              Success with nonce 237723              Hash is 000005720acd8c7207cbf495e85733f196feb1e3692405bea0ee864104039350              Elapsed Time: 0.5485 seconds              Hashing Power: 433381 hashes per second              Difficulty: 2097152 (21 bits)              Starting search...              Success with nonce 687438              Hash is 000003a6eeee97491a9183e4c57458172edb6f9466377bf44afbd74e410f6eef              Elapsed Time: 1.5282 seconds              Hashing Power: 449829 hashes per second              Difficulty: 4194304 (22 bits)              Starting search...              Success with nonce 1759164              Hash is 0000008bb8f0e731f0496b8e530da984e85fb3cd2bd81882fe8ba3610b6cefc3              Elapsed Time: 3.9695 seconds              Hashing Power: 443166 hashes per second              Difficulty: 8388608 (23 bits)              Starting search...              Success with nonce 14214729              Hash is 000001408cf12dbd20fcba6372a223e098d58786c6ff93488a9f74f5df4df0a3              Elapsed Time: 32.6874 seconds              Hashing Power: 434868 hashes per second              Difficulty: 16777216 (24 bits)              Starting search...              Success with nonce 24586379              Hash is 0000002c3d6b370fccd699708d1b7cb4a94388595171366b944d68b2acce8b95              Elapsed Time: 55.3770 seconds              Hashing Power: 443981 hashes per second
           

我們這裡隻闡述了核心的挖礦過程，更詳細的流程描述可以見：《精通比特币》一書。随着比特币價格的一路走高，越來越多的礦工加入算力軍備競賽，目前整個算力也達到恐怖的110.18 EH/s。比特币網絡本身随着算力的變化，動态調整難度值。比特币網絡的運作10年的難度曲線如下：

當然比特币網絡也是這場算力競争中最大的收益者，算力越大，系統越安全，越能形成最大的共識，因而讓比特币的市值長期超過整個數字貨币市場的50%。

密碼學Hash算法在區塊鍊技術中運用廣泛，除了挖礦，在區塊打包中也大放異彩，區塊鍊不可篡改的算法保障就是Hash算法決定的。下次探讨這個問題，敬請期待。