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

Step 6：难度调整

难度调整是mining 的重要技术。本文暂不涉及这个部份，现阶段，可以采用「前面有足够的零」做为难度设定条件，并使用上述的范例进行练习。

调整后的 difficulty，以及 nonce 值，都必须储存在新产生的区块裡，以做为后续「挖矿」的依据。

更多Mining 观念

本节所实作的mining算法，仅只是用来测试的粗浅程序（dirty code）。但透过这30 行的程序代码，还能很快了解「如何开始设计mining 的算法」。

还有更多mining 的观念，正等待区块链开发者学习：

前面有足够的零：这意味着difficutly 会到一个极限，也就是当前面的零够多时，表示这个数字可能是最小了，再也无法算出更小的数值了，这表示区块的数量是有限的，总有一天会挖完所有的矿 挖矿机：执行这段挖矿算法的电脑（正式说法为节点：node），称为挖矿机 Proof-of-Work：这是来自Bitcoin 的观念，大略的意思就是，「大家都同意你真的挖到矿了」，此外还有很多工作要做，像是挖矿机如何彼此间更新并同步资料库等

Proof-of-work 是一个复杂的系统，除了上述提及的功能外，它还涉及Peer-to-Peer 的网络技术，这个部份，是区块链开发者的真正挑战「之一」。

小结

下一个阶段是加入资料库功能，并且将目前为止的区块链系统实作成服务器。