簡單易懂的 Mining 演算法設計

Mining 演算法初體驗

表 1 是截至目前為止，範例所設計的 Block 資料結構。假設表 1 是「最後一個 Block」內容，根據先前教學的介紹，要如何挖出新區塊呢？

欄位	範例	用途說明
hash	dd0e2b79d79be0dfca96b4ad9ac85600097506f06f52bb74f769e02fcc66dec6	Block Hash
previousHash	0000000000000000000000000000000000000000000000000000000000000000	前一個 Block 的 Hash 值
timestamp	Tue Dec 06 2016 15:14:58 GMT+0800 (CST)	區塊建立的時間
merkleRoot	851AE7D7390A76384ACA2D7CC29BE820918CA900071FC22F41F5C399BE065558	區塊的 Merkle Root
difficulty	00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF	挖礦的困難度

表 1 最後一個 Block 內容

表 1 的內容，將做為「挖礦」的依據：透過最後一個 Block 的資訊，計算出新區塊的 Hash 值。

一個簡單的挖礦演算法實作步驟如下。

Step 1：建立新的 Merkle Tree

假設現在有一筆交易資訊，正等著被紀錄在區塊裡，這筆交易的狀態目前就是「待確認」。挖礦機就要先取得這筆「待確認」的交易資訊，再建立這筆交易的 Merkle tree。

多筆待確認交易的做法也相同：挖礦機先取得這些待確認的交易資訊，並建立它們的 Merkle tree。

以 Bitcoin 的網路來說，Bitcoin network 裡一個稱為「unverified pool」的地方，就是存放這些「待確認」的交易。因此，unverified pool 的設計與實作，是區塊鏈開發者的另一個課程，本教學暫不涉及 unverified pool 的介紹。

延續先前的教學，為一筆交易建立 Merkle tree 的程式碼實作如下：

// 一筆待確認的交易
var tx = [‘Created by Jollen’];

// Merkle root hash
var hashMerkleRoot;

merkleRoot.async(tx, function(err, tree){
    // 取得 Merkle Root 的 Hash
    hashMerkleRoot = tree.level(0)[0];
});

Step 2：定義本文

這裡所講的「本文」，就是用來進行 SHA-256 計算的資料內容。一個簡單的本文定義，需要 3 個項資訊：

merkleRoot：由前一個步驟產生
previousHash：最後一個區塊的 block hash，未來產生的新區塊，要往前「鏈接」到這個區塊
nonce：number once 的簡寫，在加密學裡，nonce 指的是只能使用一次的任意數

為簡化演算法的設計，可以將 nonce 定義為一個「流水號」。因為 nonce 只能使用一次，所以流水號只能「持續遞增」，不能歸零重算。

本文所需的資訊都收集齊全了，接著以 JavaScript 的物件語法，來定義本文如下：

var nonce = 0;

var header = {
    nonce: nonce,
    previousHash: ‘dd0e2b79d79be0dfca96b4ad9ac85600097506f06f52bb74f769e02fcc66dec6’,
    merkleRoot: hashMerkleRoot
};

本文的定義由區塊鏈開發者自行決定，例如：把 timestamp 也加入到本文裡。

Step 3：Double SHA-256 運算

將 header 物件 stringify（轉換為文件）後，使用這個「文件」做為本文，來進行 SHA-256 雜湊運算：

// Secret
var secret = ‘Dummy Blockchain’;

var hash1 = crypto.createHmac(‘sha256’, secret)
                    .update( JSON.stringify(header) )
                    .digest(‘hex’);

再將得到的 hash 值，做為新的 secret，進行第 2 次運算：

var hash2 = crypto.createHmac(‘sha256’, hash1)
                    .update(‘powered by flowchain’)
                    .digest(‘hex’);

現在，hash2 存放的就是 Block Hash 的「候選人」。如果 hash2 的值，確認為「success」的話，表示「挖礦成功」了：一個新的區塊被計算出來了。

Step 4：Difficulty 運算

候選人的意思是：它還不一定是成功的 hash 值。必須比對 difficulty 的條件設定，才能決定這個 hash 值是否能使用。

延續先前教學的介紹，假設困難度是「有足夠的零」時，就要進行困難度的確認：

if (hash2 < ‘00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF’) {
    console.log(‘success: ‘ + id);
}

當 hash2 不滿足目前的 difficulty 條件時，就要重新計算，直到成功為止。

以上述的範例來說，當 hash 值不滿足 difficulty 條件時，就變更 nonce 值後，再重新運算。本文範例，使用流水號的方式來產生 nonce 值。

Step 5：完整範例

根據前個的步驟，實作一段簡單的 mining 演算法如下：

var crypto = require(‘crypto’);
var merkle = require(‘merkle’);
var merkleRoot = merkle(‘sha256’);

// Secret
var secret = ‘Dummy Blockchain’;

// Unverified pool
var tx = [‘Created by Jollen’];

merkleRoot.async(tx, function(err, tree){
    // Merkle Root 的 Hash
    var hashMerkleRoot = tree.level(0)[0];
    var nonce = 0;

    var hash = function(nonce) {
        var header = {
            nonce: nonce,
            previousHash: ‘dd0e2b79d79be0dfca96b4ad9ac85600097506f06f52bb74f769e02fcc66dec6’,
            merkleRoot: hashMerkleRoot
        };

        var hash1 = crypto.createHmac(‘sha256’, secret)
                            .update( JSON.stringify(header) )
                            .digest(‘hex’);

        var hash2 = crypto.createHmac(‘sha256’, hash1)
                            .update(‘powered by flowchain’)
                            .digest(‘hex’);

        return hash2;
    };

    while (1) {
        var id = hash(nonce++);
        console.log(nonce + ‘: ‘ + id);
        if (id < ‘0000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF’) {
            console.log(‘success: ‘ + id);
            break;
        }
    }
});

輸出結果：

…
7590: 9208c185a5d218dcd1a9ce63b4609a21c9ac90e0cad65d3355ce436522ded234
7591: 766ccefa06fd97cf8b1472809e03499321fde6ba1e7341e74bd7bbcdc0a7ce01
7592: f3cb6f4f6ae187556a3ec8218453d3073958eed430155cd73d9a8d2976d30e1f
7593: 74ff8bf0695100c6cce400fde5fcbfbb0574efb79664c229a8044df0525c39ca
7594: 0002db2b239b29f52711a2629e98face0151c2020f48c94a12459a43b24a3f85
success: 0002db2b239b29f52711a2629e98face0151c2020f48c94a12459a43b24a3f85

由這個結果發現，總計 mining 了 7594 次才得到成功的 hash 值。當 difficulty 提升時，mining 所花的時間也會更多。

例如，當困難度為「前面至少 4 個零」時，mining 的次數就增加到 118432 次。挖礦的困難度在於，產生的 hash 值有一定程度的「隨機」性，通常是不太可預期的。

Step 6：難度調整

難度調整是 mining 的重要技術。本文暫不涉及這個部份，現階段，可以採用「前面有足夠的零」做為難度設定條件，並使用上述的範例進行練習。

調整後的 difficulty，以及 nonce 值，都必須儲存在新產生的區塊裡，以做為後續「挖礦」的依據。

小結

下一個階段是加入資料庫功能，並且將目前為止的區塊鏈系統實作成伺服器。

其它

Node.js Fullstack《從零到一的進擊》：初學者寫給初學者的全端軟體教材

jollen / blog

Blockchain Developer - 簡單易懂的 Mining 演算法設計 #31