文章目錄
- 前言
- 一、Merkle樹簡介
- 二、java實作
- 1.代碼如下：
- 2.測驗
- 總結
前言
學習區塊鏈技術，那么Merkle樹不得不去深入了解，本文將用java手寫Merkle樹
一、Merkle樹簡介
Merkle樹是1979 年Ralph Merkle提出并用自己名字命名的一種資料結構，什么是 Merkle 樹呢？維基百科中對 Merkle 樹的定義如下：
在密碼學和計算機科學中，哈希樹或 Merkle 樹是一種樹，其中每個葉子節點 都標記有資料塊的哈希，而每個非葉子節 ，點都標記有其子節，或標簽的加 密哈希 Merkle 樹允許對大型資料結構的內容進行有效、安全的驗證，是散列串列和散列鏈的泛化！
Merkle樹的結構如圖如下圖所示：
收集一個或多個新記錄塊，對這些記錄進行散列，再將散列配對，散列，再次配對并再次散列，直到單個散列保留這個單獨的哈希被稱為merkle樹的Merkle根，在位元幣瀏覽器中如下圖所示：
圖中的1 2 3 4二二合一，最終得到了Merkle Root：f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766
有興趣的可以看看bitcoin代碼之MerkleTree這篇文章，
二、java實作
1.代碼如下：
package org.xiangbiao;
import cn.hutool.crypto.SecureUtil;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @author larry.xiang
*/
public class MerkleTrees {
// 默克根
String merkleRoot;
// 交易集合
List<String> txLst;
/**
* 初始化
*
* @param txList 交易集合
*/
public MerkleTrees(List<String> txList) {
this.txLst = txList;
merkleRoot = "";
}
/**
* 獲取Node Hash List
* @return
*/
private List<String> getNodeHashList(List<String> tempTxList) {
List<String> newTxList = new ArrayList<String>();
int index = 0;
while (index < tempTxList.size()) {
// left
String left = tempTxList.get(index);
index++;
// right
String right = "";
if (index != tempTxList.size()) {
right = tempTxList.get(index);
}
// 兩兩加密
String sha2HexValue = SecureUtil.sha256(left + right);
// 雙重hash
sha2HexValue = SecureUtil.sha256(sha2HexValue);
newTxList.add(sha2HexValue);
index++;
}
return newTxList;
}
/**
* 構造默克樹，設定默克根
*/
public void merkle_tree() {
List<String> tempTxList = new ArrayList<String>();
for (int i = 0; i < this.txLst.size(); i++) {
tempTxList.add(this.txLst.get(i));
}
List<String> newTxList = getNodeHashList(tempTxList);
//一直回圈直到只剩下一個hash值
while (newTxList.size() != 1) {
newTxList = getNodeHashList(newTxList);
}
this.merkleRoot = newTxList.get(0);
}
/**
* 獲取默克根
*
* @return
*/
public String getMerkleRoot() {
return this.merkleRoot;
}
2.測驗
代碼如下（示例）：
public static void main(String[] args) {
List<String> tempTxList = new ArrayList<String>();
tempTxList.add("80c6f121c3e9fe0a59177e49874d8c703cbadee0700a782e4002e87d862373c6");
tempTxList.add("b86f5ef1da8ddbdb29ec269b535810ee61289eeac7bf2b2523b494551f03897c");
//Collections.reverse(tempTxList);
MerkleTrees merkleTrees = new MerkleTrees(tempTxList);
merkleTrees.merkle_tree();
System.out.println("root : " + merkleTrees.getMerkleRoot());
}
}
總結
由于哈希演算法結果較長，我們用簡化版的結果來舉例，假設目前某區塊包含兩筆交易，雙重哈希之后：
在執行【兩兩一組拼接】時，簡單將111和222拼一起：111222，就完成拼接了，(實際的拼接，是需要將哈希結果解碼為計算機語言、位移、拼接、編碼、位移，最終才能得到結果，)
拼接前，所有交易假設有n個，拼接后，剩下的個數就為n/2個了，
多次【雙重哈希演算法+兩兩一組拼接】，就是多次執行上述操作，最開始總交易個數有n個，執行一次，還有n/2個，再執行一次，還有n/4個，最終執行到結果只有1個的時候停止，再對結果做兩次哈希運算，得到的結果就是merkle根值了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/188790.html
標籤：其他