ビットコインの技術 Merkle tree(Hash tree)

2016年05月11日(編集2016年05月11日)
このエントリーをはてなブックマークに追加

この記事は、ビットコインで利用されているMerkle tree(マークル木)の説明をします。コードを通して、Merkle tree(マークル木)の仕様と実装方法を理解します。

javaはoracle jdk 1.8.0_77を利用します。

環境

  • Windows8.1
  • oracle jdk version 1.8.0_77
  • Eclipse version Luna Service Release 2 (4.4.2)

Merkle tree利用例

  • ビットコイン
  • Git
  • Amazon's Dynamo
  • Cassandra

内容

中級者向け

Merkle tree(Hash tree)

Merkle tree(Hash tree)は、コンピュータで保存・処理・転送される任意のデータの検証処理に使われるデータ構造です。

主な用途として、Peer to Peerネットワークで他のピアから受信したデータブロックが破損したり改竄されたりしていないか、あるいは他のピアが偽のデータブロックを送信していないかといった検証処理に用いられています。

ビットコインの他にも、git、Amazon's Dynamo、Cassandra等で利用されています。

ビットコインでの使用方法

ビットコインブロックチェーンのそれぞれのブロックは、Merkle treeを使って、ブロック中の全てのトランザクションの概要を含んでいます。

ビットコインのブロック

Merkle treesは、ビットコイン内で、ブロック内の全てのトランザクションをまとめるために使われています。 全体のトランザクションセットのデジタルフィンガープリントを生成し、トランザクションがブロック内に含まれるかどうかを検証するための効率的なプロセスを提供します。

大切なことは、あるトランザクションがブロックに含まれていることを確認するためMerkle treesのrootを用いています。

Merkle treesは一つのハッシュになるまで、ノードペアの再帰的なハッシュによって生成されます。

merkle treeのノード計算
   

この処理で生成されたハッシュをroot, もしくはmerkle root.と呼びます。

トランザクションのハッシュがMerkle treesに含まれていることを確認するときは、二分木なので、およそ log2(N) の計算量で探索可能です。

アルゴリズムと実装

では、実際にコードを実装します。
実装しながら考え方を理解しましょう。

{project_folder}/src/main/java/{package}/MerkleTrees.java
public class MerkleTrees {

  // トランザクション一覧
  List<String> txList;
  // Merkle Root
  String root;
  
  /**
   * コンストラクタ
   * @param txList
   */
  public MerkleTrees(List<String> txList) {
    this.txList = txList;
    root = "";
  }
   
  /**
   * merkle_treeを実行してrootを設定
   */
  public void merkle_tree() {
    
    List<String> tempTxList = new ArrayList<String>();
    
    for (int i = 0; i < this.txList.size(); i++) {
      tempTxList.add(this.txList.get(i));
    }
    
    List<String> newTxList = getNewTxList(tempTxList);
    while (newTxList.size() != 1) {
      newTxList = getNewTxList(newTxList);
    }
    
    this.root = newTxList.get(0);
  }
  
  /**
   * Nodeを結合したhashのListを返す
   * @param tempTxList
   * @return
   */
  private List<String> getNewTxList(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);
      }

      // sha2 hex value
      String sha2HexValue = getSHA2HexValue(left + right);
      newTxList.add(sha2HexValue);
      index++;
      
    }
    
    return newTxList;
  }
  
  /**
   * 引数の文字列をSHA-256で暗号化して16進数文字列を返す
   * @param str
   * @return
   */
  public String getSHA2HexValue(String str) {
        byte[] cipher_byte;
        try{
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            md.update(str.getBytes());
            cipher_byte = md.digest();
            StringBuilder sb = new StringBuilder(2 * cipher_byte.length);
            for(byte b: cipher_byte) {
              sb.append(String.format("%02x", b&0xff) );
            }
            return sb.toString();
        } catch (Exception e) {
                e.printStackTrace();
        }
        
        return "";
  }
  
  /**
   * rootを取得する
   * @return
   */
  public String getRoot() {
    return this.root;
  }
    
}
        

■ 実装手順

  • トランザクションデータの用意
  • リーフ(葉)のleftとrightのトランザクションを結合し、hashデータにする。
  • 最後の1件(root)になるまで処理を繰り返す
  • トランザクションデータの用意

merkle treeのリーフの部分であるa, b, c, d, eの5つのトランザクションを用意します。

トランザクションデータ

5つのトランザクションをリストに格納します。

List<String> tempTxList = new ArrayList<String>();
tempTxList.add("a");
tempTxList.add("b");
tempTxList.add("c");
tempTxList.add("d");
tempTxList.add("e");
        

リストの中は、index(0):a:左、index(1):b:右、index(2):c:左、index(3):d:右、index(4):e:左 です。

  • リーフ(葉)のleftとrightのトランザクションを結合する

上記のリーフを順番にleft, rightと取り出してデータを結合し、hashデータを作成します。

merkle treeの葉の計算
// left
String left = tempTxList.get(index);
index++;

// right
String right = "";
if (index != tempTxList.size()) {
  right = tempTxList.get(index);
}

// sha2 hex value
String sha2HexValue = getSHA2HexValue(left + right);
        
  • 最後の1件(root)になるまで処理を繰り返す

新たに生成されたハッシュListでleft, rightの結合処理を繰り返します。

while (index < tempTxList.size()) {
  // something
}
        

データが最後の1件(root)になるまで結合処理を繰り返します。この処理で作成されたハッシュがmerkle rootです。

this.root = newTxList.get(0);
        

実行

上記で実装したコードをmainメソッドに記載します。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {
    List<String> tempTxList = new ArrayList<String>();
    tempTxList.add("a");
    tempTxList.add("b");
    tempTxList.add("c");
    tempTxList.add("d");
    tempTxList.add("e");
    
    MerkleTrees merkleTrees = new MerkleTrees(tempTxList);
    merkleTrees.merkle_tree();
    System.out.println("root : " + merkleTrees.getRoot());
  }
}
        

実行します。

terminal
root : 3b7e1e6ba3b82975d7802511d8c7fabbe7a5d112d0dd112fbcfbb7e6417a3214
        

rootが取得できました。

まとめ

Merkle treeは、多くのアプリケーションで利用されている技術です。

巨大データの要約結果を格納してデータの検証を行えるので、今後のビックデータ時代ではさらに使われていくことでしょう。

関連記事

タグ検索で調べてみよう

ビットコイン