Closed jollen closed 6 years ago
Merkle tree 用來存放交易資訊(transactions),為了要討論更詳細的 Merkle tree 生成過程,假設現在有 2 筆交易正在等候「處理」。這 2 筆交易資訊,分別以 Tx0 與 Tx1 來表示。
Tx0
Tx1
圖 1 生成 Merkle tree
Merkle tree 節點存放的是 double SHA-256 運算結果。如何將這 2 筆交易資訊,以 Merkle tree 來表示呢?以下是這一顆 Merkle tree 的生成過程。
將 Tx0 的本文(content)以 double SHA-256 進行雜湊運算,並將結果儲存在 HA,表示方法如下:
HA
HA = SHA256( SHA256(Tx0) )
同理,再將 Tx1 進行 double SHA-256 運算,結果儲存於 HB:
HB
HB = SAH256( SHA256(Tx1) )
SHA-256 的運算結果,是一個 64 bytes 的 HEX(十六進位)字串。在得到 HA 與 HB 後,就將這二個字串連接(concat)在一起,成為一個 64*2=128 bytes 的字串,這裡以 HA + HB 來表示。
HA + HB
再將 HA + HB 進行 double SHA-256 運算,結果儲存於 `HAB:
`HAB
HAB = SAH256( SHA256( HA + HB ) )
HAB 就是 HA 與 HB 的父節點,這就是一個 3 個節點的 binary Merkle tree。
HAB
如果現在有 Tx0、Tx1、Tx2 與 Tx3 共 4 筆交易呢?完整的 double SHA-256 運算過程就是:
Tx2
Tx3
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 演算法,網路上能找到開放源碼的實作。在 GitHub 上可以找到 Merkle 模組,這是 JavaScript 的 Merkle tree 實作,並且支援 SHA-256 在內的多種 hash algorithm。
先安裝 Merkle 模組:
$ npm install merkle --save
接著引入 merkle 模組:
merkle
var merkle = require('merkle');
建立 root node,並指定使用 SHA-256 演算法:
var merkleRoot = merkle('sha256');
宣告幾筆交易資訊,例如:
// 建立一筆新的交易紀錄 var tx = ['Created by Jollen'];
交易的內容,現階段可任意填寫。例如,如果有 4 筆交易資訊:
// 建立 4 筆新的交易紀錄 var tx = ['a', 'b', 'c', 'd'];
現在只是練習 Merkle tree 的生成,暫時還沒有定義交易的資料結構,所以填寫任意內容即可。
呼叫 async 函數,傳入所有交易資訊來建立 Merkle tree:
async
merkleRoot.async(tx, function(err, tree){ });
透過 Callback 函數來取得 Merkle tree。根據 Merkle 官方文件的說明,可以呼叫 tree`` 物件的root``` 函數,來取得 Merkle root 的 Hash 值。以下是完整的範例列表:
tree`` 物件的
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
如圖 2 所示,Merkle tree 是 binary tree(二元樹),以 4 筆交易量來看,總計會有 6 個節點(nodes),並且「高度」為 3。這個高度稱為 level。
圖 2 Merkle Tree 的 depth 為 2
這是一個 levels 為 3 的 Merkle tree,排除 leaf nodes 後的高度稱為 depth。所以:
延續上述範例,取得該 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 的所有節點,例如:
level
merkleRoot.async(tx, function(err, tree){ console.log( tree.level(1) ); });
輸出結果:
[ '6A20F2EE7789E6BB7F404CC2DD729FF308B724D904F6A455B74D4851ADE5AECB', 'A99E82F486656840A790C0EF6024D2C02359DE7674A587562FEB81C8970F24DD' ]
如圖 2 所示:
如果要顯示所有的節點,要怎麼修改程式碼呢?答案如下:
merkleRoot.async(tx, function(err, tree){ // 印出所有節點 for (i = 0; i < tree.levels(); i++) { console.log( tree.level(i) ); } });
實際撰寫程式,來觀察 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 的結構。
closed by http://www.jollen.org/blog/2016/12/blockchain-developer-merkle-tree.html
建立 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
,表示方法如下:同理,再將
Tx1
進行 double SHA-256 運算,結果儲存於HB
:SHA-256 的運算結果,是一個 64 bytes 的 HEX(十六進位)字串。在得到
HA
與HB
後,就將這二個字串連接(concat)在一起,成為一個 64*2=128 bytes 的字串,這裡以HA + HB
來表示。再將
HA + HB
進行 double SHA-256 運算,結果儲存於`HAB
:HAB
就是HA
與HB
的父節點,這就是一個 3 個節點的 binary Merkle tree。更多交易
如果現在有
Tx0
、Tx1
、Tx2
與Tx3
共 4 筆交易呢?完整的 double SHA-256 運算過程就是:最後得到的 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 模組:
接著引入
merkle
模組:建立 root node,並指定使用 SHA-256 演算法:
Step 2:準備交易資訊
宣告幾筆交易資訊,例如:
交易的內容,現階段可任意填寫。例如,如果有 4 筆交易資訊:
現在只是練習 Merkle tree 的生成,暫時還沒有定義交易的資料結構,所以填寫任意內容即可。
Step 3:建立完整 Merkle Tree
呼叫
async
函數,傳入所有交易資訊來建立 Merkle tree:透過 Callback 函數來取得 Merkle tree。根據 Merkle 官方文件的說明,可以呼叫
tree`` 物件的
root``` 函數,來取得 Merkle root 的 Hash 值。以下是完整的範例列表:結出結果:
更多 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 與 levels:
結出結果:
此外,呼叫
level
函數,可以取得指定 level 的所有節點,例如:輸出結果:
如圖 2 所示:
如果要顯示所有的節點,要怎麼修改程式碼呢?答案如下:
視覺化 Merkle Tree
實際撰寫程式,來觀察 4 筆交易資訊的 Merkle tree:
輸出結果:
為了幫助學習,圖 3 以視覺化的方式,來呈現這個範例的結果。
圖 3 視覺化 Merkle Tree
小結
現在,你學會了如何使用 Node.js 來生成 Merkle tree,並且也更進一步了解 Merkle tree 的結構。