简单易懂的Mining算法设计

假设表1 是「最后一个Block」内容，根据先前教学的介绍，要如何挖出新区块呢...本文章采用Markdown语法撰写。

简单易懂的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 值有一定程度的「随机」性，通常是不太可预期的。