如何使用Node.js来生成Merkle tree

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。

使用 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 以视觉化的方式，来呈现这个范例的结果。