Merkle Tree 的生成过程

Merkle tree 用来存放交易资讯（transactions），为了要讨论更详细的Merkle tree 生成过程，假设现在有2 笔交易正在等候「处理」。这2 笔交易资讯，分别以 Tx0 与 Tx1 来表示。

图1 生成Merkle tree

Merkle tree 节点存放的是double SHA-256 运算结果。如何将这2 笔交易资讯，以Merkle tree 来表示呢以下是这一颗Merkle tree 的生成过程。

将 Tx0 的本文（content）以 double SHA-256 进行哈希运算，并将结果储存在 HA，表示方法如下：

HA = SHA256( SHA256(Tx0) )

同理，再将 Tx1 进行 double SHA-256 运算，结果储存于 HB：

HB = SAH256( SHA256(Tx1) )

SHA-256 的运算结果，是一个64 bytes 的HEX（十六进位）字串。在得到HAHBHA + HB

再将HA + HBHAB

HAB = SAH256( SHA256( HA + HB ) )

得到结果 HAB 就是 HA 与 HB 的父节点。这是一个 3 个节点的 binary Merkle tree。

更多交易

如果现在有 Tx0、Tx1、Tx2 与 Tx3 共 4 笔交易呢完整的 double SHA-256 运算过程就是：

HA = SHA256( SHA256(Tx0) ) HB = SAH256( SHA256(Tx1) ) HC = SAH256( SHA256(Tx2) ) HD = SAH256( SHA256(Tx3) ) HAB = SAH256( SHA256( HA + HB ) ) HCD = SAH256( SHA256( HC + HD ) ) HABCD = SAH256( SHA256( HAB + HCD ) )

最后得到的binary Merkle tree 就是图2。

使用 Node.js 打造 Merkle Tree

Node.js 开发者不一定要自行实作 Merkle tree 算法，网络上能找到开放源码的实作。在 GitHub 上可以找到 Merkle 模组，这是 JavaScript 的 Merkle tree 实作，并且支持 SHA-256 在内的多种 hash algorithm。

Step 1：安装Merkle 模组

先安装Merkle 模组：

$ npm install merkle --save

接著引入 merkle 模组：

var merkle = require('merkle');

建立root node，并指定使用SHA-256 算法：

var merkleRoot = merkle('sha256');

Step 2：准备交易资讯

宣告几笔交易资讯，例如：

// 建立一笔新的交易记录 var tx = ['Created by Jollen'];

交易的内容，现阶段可任意填写。例如，如果有4 笔交易资讯：

// 建立 4 笔新的交易记录 var tx = ['a', 'b', 'c', 'd'];

现在只是练习Merkle tree 的生成，暂时还没有定义交易的资料结构，所以填写任意内容即可。

Step 3：建立完整 Merkle Tree

呼叫 async 函数，传入所有交易资讯来建立 Merkle tree：

merkleRoot.async(tx, function(err, tree){ });

透过 Callback 函数来取得 Merkle tree。根据 Merkle 官方文件的说明，可以呼叫 tree 物件的 root 函数，来取得 Merkle root 的 Hash 值。以下是完整的范例列表：

var merkle = require('merkle'); var merkleRoot = merkle('sha256'); // 建立一笔新的交易记录 var tx = ['a', 'b', 'c', 'd']; merkleRoot.async(tx, function(err, tree){ console.log( tree.root() ); });

结出结果：

AB4587D9F4AD6990E0BF4A1C5A836C78CCE881C2B7C4287C0A7DA15B47B8CF1F

更多Merkle Tree 资讯

如图2 所示，Merkle tree 是binary tree（二元树），以4 笔交易量来看，总计会有6 个节点（nodes），并且「高度」为3。这个高度称为level。

图2 Merkle Tree 的depth 为 2

这是一个levels 为3 的Merkle tree，排除leaf nodes 后的高度称为depth。所以：

HA 与 HB 称为 leaf nodes 这个Merkle tree 的depth 为 2 这个Merkle tree 的level 为 3

延续上述范例，取得该Merkle tree 的depth 与levels：

merkleRoot.async(tx, function(err, tree){ console.log( tree.root() ); console.log( tree.depth() ); console.log( tree.levels() ); });

结出结果：

AB4587D9F4AD6990E0BF4A1C5A836C78CCE881C2B7C4287C0A7DA15B47B8CF1F 2 3

此外，呼叫 level 函数，可以取得指定 level 的所有节点，例如：

merkleRoot.async(tx, function(err, tree){ console.log( tree.level(1) ); });

输出结果：

[ '6A20F2EE7789E6BB7F404CC2DD729FF308B724D904F6A455B74D4851ADE5AECB', 'A99E82F486656840A790C0EF6024D2C02359DE7674A587562FEB81C8970F24DD' ]

如图2 所示：

level 0 是根节点（root） level 1 有2 个节点

如果要显示所有的节点，要怎么修改程序代码呢答案如下：

merkleRoot.async(tx, function(err, tree){ // 印出所有节点 for (i = 0; i < tree.levels(); i++) { console.log( tree.level(i) ); } });

视觉化Merkle Tree

实际撰写程序，来观察4 笔交易资讯的Merkle tree：

var merkle = require('merkle'); var merkleRoot = merkle('sha256'); // 4 笔交易资讯 var tx = ['a', 'b', 'c', 'd']; merkleRoot.async(tx, function(err, tree){ // 印出所有节点 for (i = 0; i < tree.levels(); i++) { console.log( tree.level(i) ); } });

输出结果：

[ 'AB4587D9F4AD6990E0BF4A1C5A836C78CCE881C2B7C4287C0A7DA15B47B8CF1F' ] [ '6A20F2EE7789E6BB7F404CC2DD729FF308B724D904F6A455B74D4851ADE5AECB', 'A99E82F486656840A790C0EF6024D2C02359DE7674A587562FEB81C8970F24DD' ] [ 'CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB', '3E23E8160039594A33894F6564E1B1348BBD7A0088D42C4ACB73EEAED59C009D', '2E7D2C03A9507AE265ECF5B5356885A53393A2029D241394997265A1A25AEFC6', '18AC3E7343F016890C510E93F935261169D9E3F565436429830FAF0934F4F8E4' ]

为了帮助学习，图3 以视觉化的方式，来呈现这个范例的结果。

图3 视觉化Merkle Tree

小结

现在，你学会了如何使用Node.js 来生成Merkle tree，并且也更进一步了解Merkle tree 的结构。