200行Go程式碼實現區塊鏈 —— 挖礦演演算法-知識星球

在本系列前兩篇文章中[1][2]，我們向大家展示瞭如何透過精煉的Go程式碼實現一個簡單的區塊鏈。包括生成塊，驗證塊資料，廣播通訊等等，這一篇讓我們聚焦在如何實現 PoW演演算法。

大家都無不驚呼比特幣、以太坊及其他加密電子貨幣的持續狂熱，特別是對於剛接觸這個領域的新手，不斷得聽到張三李四透過 GPU “挖礦”而聚集價值數萬乃至數百萬加密電子貨幣。那麼“挖礦”到底是什麼？它是如何工作的？相信對於程式員來說，沒有什麼比自己動手實踐一遍“挖礦”演演算法更好的學習辦法了。

在這篇文章中，讓我們一起逐個解讀每一個問題，並最終編寫出自己的“挖礦”演演算法。這個演演算法稱為工作證明演演算法（Proof-of-Work）[3]，它是比特幣和以太坊這兩種最流行的加密貨幣的基礎。

什麼是“挖礦”？

加密電子貨幣因為稀缺才具有價值。以現在的比特幣為例，如果任何人任何時候都可以隨意“製造”比特幣，那麼作為電子貨幣它會變得毫無價值。比特幣透過演演算法來控制產出的速率併在大約122年內達到最大量。這種隨著時間推移緩慢、穩定並逐步產出的方式有效避免了通貨膨脹。

比特幣的產出是透過給予“獲勝礦工”獎勵來實現，為了獲取比特幣獎勵礦工之間會進行競爭。這個過程之所以被稱為“挖礦”，是因為它類似於“Gold Rush”[4]時每個黃金礦工透過辛苦勞作並最終（希望）找到一點黃金。

“挖礦”是如何工作的？

如果 Google 一下這個問題，你會得到大量的結果。簡單來說，“挖礦”就是“解決一個數學難題”的過程。我們先來瞭解一些密碼學和雜湊演演算法的知識。

密碼學簡要介紹

單向加密以人類可讀的文字（明文）作為輸入，比如“Hello world”這個字串，再透過一個數學函式產生出難以辨認的輸出（密文）。這類函式或演演算法的性質和複雜性各不相同。演演算法越複雜，逆向工程就越困難。

以流行的 SHA-256 演演算法為例。透過這個網站[5]可以讓你計算任意給定輸入的輸出，也就是 SHA-256 雜湊值。比如讓我們輸入“Hello world”，看看得到了什麼：

透過不斷嘗試計算“Hello world”的雜湊值。你會發現每次的結果都完全相同。這個過程稱為冪等性。

加密演演算法一個最基本的特性是，非常難以透過反向工程來求解輸入，但是非常容易驗證輸出。比如上面的例子，你可以很容易驗證給定輸入“Hello world”的SHA-256雜湊值是否正確，但很難透過給定的雜湊值判斷它的輸入是什麼。這就是為什麼將這種型別的演演算法稱為單向加密。

比特幣使用 Double SHA-256，它將 SHA-256 求得的雜湊值作為輸入再次計算 SHA-256 雜湊值。為了簡化，我們只使用一次SHA-256。

挖礦

回到加密電子貨幣中，比特幣就是透過讓參與者利用這樣的加密演演算法求解出符合特定條件的雜湊值來實現“挖礦”過程。具體來說，比特幣要求參與者透過 double SHA-256 演演算法計算出“前導0”超過若干位的雜湊值，第一個求解出來的參與者就是“獲勝的礦工”。

比如，我們求“886”這個字串的 SHA-256 雜湊值：

可以看到，是一個“前導0”為3位的雜湊值（前三位是0）。

回憶我們前面說到的“單向加密”的特點：

任何人都可以很容易地驗證“886”是否產生3位“前導0”的雜湊值。但為了找到這樣一個能產生3位“前導0”的輸入（就是這裡的“886”），我們做了大量繁瑣的計算工作：從一個很大的數字和字母集合中逐個計算它們的雜湊值並判斷是否滿足上述條件。如果我是第一個找到“886”的人，那其他人透過驗證就能判斷我做了這樣大量繁瑣的工作。在比特幣、以太坊中這樣的過程就稱為工作證明演演算法。

“如果我運氣非常好，第一次嘗試就找到了一個符合條件的（輸入）值呢？” —— 這是非常不可能的，你可以試試隨意輸入一些字母和數字。

比特幣中實際的演演算法和約束要比上說要求複雜，當然也更難（要求更多位的“前導0”）。同時它也可以動態調整難度，標的是確保每隔10分鐘產出一次比特幣，不管參與“挖礦”的人多還是少。

差不多可以動手了

瞭解了足夠的背景知識，接著我們就用 Go 語言來編碼實踐下工作量證明（Proof-of-Work）演演算法。

建議你閱讀之前的《用200行Go程式碼實現自己的區塊鏈》系列文章，因為下麵工作證明演演算法部分會涉及之前的程式碼。

Proof-of-work

建立新塊並加入到鏈上之前需要完成“工作量證明”過程。我們先寫一個簡單的函式來檢查給定的雜湊值是否滿足要求。

雜湊值必須具有給定位的“前導0”
“前導0”的位數是由難度（difficulty）決定的
可以動態調整難度（difficulty）來確保 Proof-of-Work 更難解

下麵就是 isHashValid 這個函式：

func isHashValid(hash string, difficulty int) bool {
        prefix := strings.Repeat("0", difficulty)
        return strings.HasPrefix(hash, prefix)
}

Go 語言的 strings 包中提供了方便的 Repeat 和 HasPrefix 函式。我們定 prefix 變數，它代表“前導0”，接著檢查雜湊值是否具有滿足條件的“前導0”，然後傳回 True 或 False 。

我們修改之前生成塊的generateBlock 函式：

func generateBlock(oldBlock Block, BPM int) Block {
        var newBlock Block

        t := time.Now()

        newBlock.Index = oldBlock.Index + 1
        newBlock.Timestamp = t.String()
        newBlock.BPM = BPM
        newBlock.PrevHash = oldBlock.Hash
        newBlock.Difficulty = difficulty

        for i := 0; ; i++ {
                hex := fmt.Sprintf("%x", i)
                newBlock.Nonce = hex
                if !isHashValid(calculateHash(newBlock), newBlock.Difficulty) {
                        fmt.Println(calculateHash(newBlock), " do more work!")
                        time.Sleep(time.Second)
                        continue
                } else {
                        fmt.Println(calculateHash(newBlock), " work done!")
                        newBlock.Hash = calculateHash(newBlock)
                        break
                }

        }
        return newBlock
}

建立一個新塊 newBlock ，裡面的 PrevHash 包含前一個塊的雜湊值，Timestamp 是時間戳，BPM 是心率資料，Difficulty 就是前面提到的難度，它的值決定了“前導0”的位數。

這裡的 for 迴圈很重要：

獲得 i 的十六進製表示，將 Nonce 設定為這個值，並傳入 calculateHash 計算雜湊值。之後透過上面的 isHashValid 函式判斷是否滿足難度要求，如果不滿足就重覆嘗試。
這個計算過程會一直持續，知道求得了滿足要求的 Nonce 值，之後透過 handleWriteBlock 函式將新塊加入到鏈上。

篇幅有限，我們已經將完整程式碼釋出在 Github上，可以從這裡[6]獲得。