mg不朽情缘是哪个国家

書名：區塊鏈底層設計Java實戰
作者名：牛冬編著
本章字數： 1634字
更新時間： 2019-07-25 11:59:22

3.3 Merkle樹

3.3.1 Merkle樹簡介

Merkle樹是Ralph Merkle于1979提出并用自己名字命名的一種數據結構。

什么是Merkle樹呢？維基百科中對Merkle樹的定義如下：

在密碼學和計算機科學中，哈希樹或Merkle樹是一種樹，其中每個葉子節點都標記有數據塊的哈希，而每個非葉子節點都標記有其子節點標簽的加密哈希。Merkle樹允許對大型數據結構的內容進行有效、安全的驗證，是散列列表和散列鏈的泛化。

Merkle樹的結構如圖3-1所示。

圖3-1 Merkle樹的結構

通過圖3-1可以看到，數據data1、data2、data3、data4和其對應的Merkle樹的映射關系。首先，對數據data1、data2、data3、data4計算哈希值，哈希計算方法可以基于SHA-2系列算法或MD5，并將哈希值放進新生成的葉子節點。

從葉子節點開始逐級構建上一級節點的哈希值，直至構建到只剩一個根節點為止。上一級節點的哈希值依賴其左右孩子節點的哈希值，一般將這兩個哈希組合后計算哈希值作為上一級節點的哈希值。

從上述Merkle樹構建的過程不難發現：Merkle樹本質上就是一種樹型結構，無論是二叉樹還是多叉樹。Merkle樹的葉子節點的value源于數據的哈希。非葉子節點的value是根據它左右孩子節點所有的葉子節點值，然后按照哈希算法計算而得出的。

目前，Merkle樹在數字貨幣、零知識證明、文件完整性校驗等領域有廣泛的應用，如在比特幣和以太坊系統中利用Merkle proofs來存儲每個區塊的交易，而我們開發中常用的文件版本管理工具Git也是通過Merkle樹來進行完整性校驗的。

在區塊鏈系統中，Merkle樹最常見的使用方式就是構建交易數據對應的Merkle樹，并計算得到Merkle樹根節點的哈希值。下面我們將展示如何計算Merkle樹根節點的哈希值及如何構建交易數據對應的Merkle樹。

3.3.2 Merkle樹Java實戰

在展示如何構建交易數據對應的Merkle樹代碼前，我們先對Merkle樹根節點哈希值的計算進行一個簡單的展示，代碼如下：

package com.niudong.demo.util;

import java.util.ArrayList;
import java.util.List;

/**
 * 簡化的Merkle樹根節點哈希值計算
 *
 * @author 牛冬
 *
 */
public class SimpleMerkleTree {

  // 按Merkle樹思想計算根節點哈希值
  public static String getTreeNodeHash(List<String> hashsList) {
    if (hashsList == null || hashsList.size() == 0) {
      return null;
    }

    while (hashsList.size() ! = 1) {
      hashsList = getMerKleNodeList(hashsList);
    }

    // 最終只剩下根節點
    return hashsList.get(0);
  }

  // 按Merkle樹思想計算根節點哈希值
  public static List<String> getMerKleNodeList(List<String>
      contentList) {
    List<String> merKleNodeList = new ArrayList<String>();

    if (contentList == null || contentList.size() == 0) {
      return merKleNodeList;
    }

    int index = 0, length = contentList.size();
    while (index < length) {
      // 獲取左孩子節點數據
      String left = contentList.get(index++);

      // 獲取右孩子節點數據
      String right = "";
      if (index < length) {
        right = contentList.get(index++);
      }

      // 計算左右孩子節點的父節點的哈希值
      String sha2HexValue = SHAUtil.sha256BasedHutool(left + right);
      merKleNodeList.add(sha2HexValue);
    }
    return merKleNodeList;
  }
}

如上述代碼所示，我們通過SimpleMerkleTree類的靜態方法getTreeNodeHash()來計算Merkle樹根節點哈希值。其中輸入內容為字符串類型的List hashsList，在檢驗hashsList的有效性后，開始依次取List相鄰元素的值，拼接后通過SHAUtil. sha256BasedHutool()計算哈希值。若List中的元素個數為奇數，則用最后一個元素和空字符串組合計算哈希值。

每一輪List元素兩兩計算完哈希值后，當前數據的上一級哈希節點就產生完畢了。然后重復剛才對List的遍歷，再對新List進行類似處理，直至List中僅剩一個元素，此時該元素的哈希值就是Merkle樹根節點的哈希值。

上述代碼對應的單元測試類代碼如下：

package com.niudong.demo.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * SimpleMerkleTree的單元測試類
 *
 * @author 牛冬
 *
 */
public class SimpleMerkleTreeTest {
  @Test
  public void testGetMerKleNodeList() {
    // case1:List<String> contentList = null;
    List<String> contentList = null;
    Assert.assertEquals(SimpleMerkleTree.getMerKleNodeList
      (contentList).size(), 0);

    // case2:List<String> contentList = new ArrayList<>()；但無內容
    contentList = new ArrayList<>();
    Assert.assertEquals(SimpleMerkleTree.getMerKleNodeList
      (contentList).size(), 0);

    // case3:contentList有內容填充
    contentList = Arrays.asList("區塊鏈", "人工智能", "腦科學", "K12教育
      全球優質公司");
    Assert.assertEquals(SimpleMerkleTree.getMerKleNodeList
        (contentList).size(), 2);
  }

  @Test
  public void testGetTreeNodeHash() {
    // case1:List<String> contentList = null;
    List<String> contentList = null;
    Assert.assertEquals(SimpleMerkleTree.getTreeNodeHash
        (contentList), null);
    // case2:List<String> contentList = new ArrayList<>()；但無內容
    contentList = new ArrayList<>();
    Assert.assertEquals(SimpleMerkleTree.getTreeNodeHash
        (contentList), null);

    // case3:contentList有內容填充
    contentList = Arrays.asList("區塊鏈", "人工智能", "腦科學", "K12教育
      全球優質公司");
  Assert.assertEquals(SimpleMerkleTree.getTreeNodeHash
       (contentList),
      "f0e7e2c8716a92d1fa9909149279ea2201d488cea0278ba23033b8aed13a667d");
}
}

在IDE窗口右擊鼠標，在右鍵快捷菜單中單擊“Run As”，在彈出的下拉列表中選擇“TestNG test”，執行單元測試代碼。測試結果輸出如下：

PASSED: testGetMerKleNodeList
PASSED: testGetTreeNodeHash

===============================================
    Default test
    Tests run: 2, Failures: 0, Skips: 0
===============================================

===============================================
Default suite
Total tests run: 2, Failures: 0, Skips: 0
===============================================

[TestNG] Time taken by
    org.testng.reporters.JUnitReportReporter@2d3fcdbd: 17 ms
[TestNG] Time taken by
    org.testng.reporters.EmailableReporter2@1936f0f5: 7 ms
[TestNG] Time taken by org.testng.reporters.jq.Main@62043840: 106 ms
[TestNG] Time taken by [FailedReporter passed=0 failed=0 skipped=0]:1 ms
[TestNG] Time taken by org.testng.reporters.XMLReporter@3567135c: 24 ms
[TestNG] Time taken by
    org.testng.reporters.SuiteHTMLReporter@180bc464: 47 ms
Picked up JAVA_TOOL_OPTIONS: -Dfile.encoding=UTF-8

上面的代碼展示了如何利用Merkle樹的原理來計算輸入內容對應的Merkle樹根節點哈希值，但實際在區塊鏈系統中，不僅會用到根節點的哈希值，還需要基于Merkle樹驗證交易的有效性，因此，下面將展示如何構建真正意義上的Merkle樹。

在構建Merkle樹之前，我們先定義Merkle樹中每個節點的數據結構如下：

package com.niudong.demo.util;

/**
 * 樹節點定義
 *
 * @author 牛冬
 *
 */
public class TreeNode {
  // 二叉樹的左孩子
  private TreeNode left;
  // 二叉樹的右孩子
  private TreeNode right;
  // 二叉樹中孩子節點的數據
  private String data;
  // 二叉樹中孩子節點的數據對應的哈希值，此處采用SHA-256算法處理
  private String hash;
  // 節點名稱
  private String name;

  // 構造函數1
  public TreeNode() {

  }

  // 構造函數2
  public TreeNode(String data) {
    this.data = data;
    this.hash = SHAUtil.sha256BasedHutool(data);
    this.name = "[節點：" + data+"]";
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getData() {
    return data;
  }

  public void setData(String data) {
    this.data = data;
  }

  public TreeNode getRight() {
    return right;
  }

  public void setRight(TreeNode right) {
    this.right = right;
  }

  public TreeNode getLeft() {
    return left;
  }

  public void setLeft(TreeNode left) {
    this.left = left;
  }

  public String getHash() {
    return hash;
  }

  public void setHash(String hash) {
    this.hash = hash;
  }
}

如上述代碼所示，Merkle樹的中節點中包含左右孩子節點信息、自身的數據、基于左右孩子數據計算得到的哈希值和節點名稱。

下面基于TreeNode構建Merkle樹的代碼如下：

package com.niudong.demo.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * Merkle樹構建、生成根節點哈希值的工具類
 *
 * @author 牛冬
 *
 */
public class MerkleTree {
  // TreeNode List
  private List<TreeNode> list;
  // 根節點
  private TreeNode root;

  // 構造函數
  public MerkleTree(List<String> contents) {
    createMerkleTree(contents);
  }

  // 構建Merkle樹
  private void createMerkleTree(List<String> contents) {
    // 輸入為空則不進行任何處理
    if (contents == null || contents.size() == 0) {
      return;
    }

    // 初始化
    list = new ArrayList<>();

    // 根據數據創建葉子節點
    List<TreeNode> leafList = createLeafList(contents);
    list.addAll(leafList);

    // 創建父節點
    List<TreeNode> parents = createParentList(leafList);
    list.addAll(parents);

    // 循環創建各級父節點直至根節點
    while (parents.size() > 1) {
      List<TreeNode> temp = createParentList(parents);
      list.addAll(temp);
      parents = temp;
    }
    root = parents.get(0);
  }

  // 創建父節點列表
  private List<TreeNode> createParentList(List<TreeNode> leafList) {
    List<TreeNode> parents = new ArrayList<TreeNode>();

    // 空檢驗
    if (leafList == null || leafList.size() == 0) {
      return parents;
    }

    int length = leafList.size();
    for (int i = 0; i < length -1; i += 2) {
      TreeNode parent = createParentNode(leafList.get(i),
          leafList.get(i + 1));
      parents.add(parent);
    }

    // 奇數個節點時，單獨處理最后一個節點
    if (length % 2 ! = 0) {
      TreeNode parent = createParentNode(leafList.get(length -1),
          null);
      parents.add(parent);
    }

    return parents;
  }

  // 創建父節點
  private TreeNode createParentNode(TreeNode left, TreeNode right) {
    TreeNode parent = new TreeNode();

    parent.setLeft(left);
    parent.setRight(right);

    // 如果right為空，則父節點的哈希值為left的哈希值
    String hash = left.getHash();
    if (right ! = null) {
      hash = SHAUtil.sha256BasedHutool(left.getHash() +
          right.getHash());
    }
    // hash字段和data字段同值
    parent.setData(hash);
    parent.setHash(hash);

    if (right ! = null) {
      parent.setName("(" + left.getName() + "和" + right.getName() +
          "的父節點)");
    } else {
      parent.setName("(繼承節點{" + left.getName() + "}成為父節點)");
    }

    return parent;
  }

  // 構建葉子節點列表
  private List<TreeNode> createLeafList(List<String> contents) {
    List<TreeNode> leafList = new ArrayList<TreeNode>();

    // 空檢驗
    if (contents == null || contents.size() == 0) {
      return leafList;
    }

    for (String content : contents) {
      TreeNode node = new TreeNode(content);
      leafList.add(node);
    }

    return leafList;
  }

  // 遍歷樹
  public void traverseTreeNodes() {
    Collections.reverse(list);
    TreeNode root = list.get(0);
    traverseTreeNodes(root);
  }

  private void traverseTreeNodes(TreeNode node) {
    System.out.println(node.getName());
    if (node.getLeft() ! = null) {
      traverseTreeNodes(node.getLeft());
    }

    if (node.getRight() ! = null) {
      traverseTreeNodes(node.getRight());
    }
  }

  public List<TreeNode> getList() {
    if (list == null) {
      return list;
    }
    Collections.reverse(list);
    return list;
  }

  public void setList(List<TreeNode> list) {
    this.list = list;
  }

  public TreeNode getRoot() {
    return root;
  }

  public void setRoot(TreeNode root) {
    this.root = root;
  }

}

上述代碼對應的單元測試代碼如下：

package com.niudong.demo.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.testng.Assert;
import org.testng.annotations.Test;

/**
  * MerkleTree單元測試類
  *
  * @author 牛冬
  *
  */
 public class MerkleTreeTest {

   @Test
   public void testMerkleTree() {
    // case1:List<String> contents = null;
    List<String> contents = null;
    Assert.assertEquals(new MerkleTree(contents).getList(), null);
    Assert.assertEquals(new MerkleTree(contents).getRoot(), null);

    // case2:List<String> contents = new ArrayList<>();
    contents = new ArrayList<>();
    Assert.assertEquals(new MerkleTree(contents).getList(), null);
    Assert.assertEquals(new MerkleTree(contents).getRoot(), null);

    // case3:List<String> contents有內容
    contents = Arrays.asList("區塊鏈", "人工智能", "腦科學", "K12教育全球
        優質公司");
    Assert.assertEquals(new MerkleTree(contents).getRoot().getHash(),
        " a1e908f0d5bd38569525c1a002af3fde5b2773d94514159f1bd2e37db59
          69cc4");
    Assert.assertEquals(new MerkleTree(contents).getRoot().getName(),
        " (([節點：區塊鏈]和[節點：人工智能]的父節點)和([節點：腦科學]和[節點：
            K12教育全球優質公司]的父節點)的父節點)");

    new MerkleTree(contents).traverseTreeNodes();
   }
 }

在IDE窗口右擊鼠標，在右鍵快捷菜單中單擊“Run As”，在彈出的下拉列表中選擇“TestNG test”，執行單元測試代碼。測試結果輸出如下：

(([節點：區塊鏈]和[節點：人工智能]的父節點)和([節點：腦科學]和[節點：K12教育全球優質公司]的父節點)的父節點)

([節點：區塊鏈]和[節點：人工智能]的父節點)

[節點：區塊鏈]

[節點：人工智能]

([節點：腦科學]和[節點：K12教育全球優質公司]的父節點)

[節點：腦科學]

[節點：K12教育全球優質公司]

PASSED: testMerkleTree

===============================================
    Default test
    Tests run: 1, Failures: 0, Skips: 0
===============================================

===============================================
Default suite
Total tests run: 1, Failures: 0, Skips: 0
===============================================

[TestNG] Time taken by org.testng.reporters.
      JUnitReportReporter@2d3fcdbd: 9 ms
[TestNG] Time taken by org.testng.reporters.
      EmailableReporter2@1936f0f5: 6 ms
[TestNG] Time taken by org.testng.reporters.jq.Main@62043840: 52 ms
[TestNG] Time taken by [FailedReporter passed=0 failed=0 skipped=0]: 0 ms
[TestNG] Time taken by org.testng.reporters.XMLReporter@3567135c: 8 ms
[TestNG] Time taken by org.testng.reporters.SuiteHTMLReporter@180bc464:29 ms
Picked up JAVA_TOOL_OPTIONS: -Dfile.encoding=UTF-8

官术网_书友最值得收藏!

區塊鏈底層設計Java實戰

3.3 Merkle樹

3.3.1 Merkle樹簡介

3.3.2 Merkle樹Java實戰