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

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

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

環境

  • macOS Sierra
  • oracle jdk version 1.8.0_77
  • IntelliJ IDEA 2017.3

難易度

中級者向け

サンプルコード

crypt

Merkle tree(Hash tree)

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

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

Merkle tree利用例

  • Bitcoin
  • Ethereum
  • Git
  • Amazon's Dynamo
  • Cassandra

最近は、BitcoinやEthereumといった仮想通貨で頻繁に用いられています。

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

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

ビットコインのブロック

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

Merkle treeのrootを用いる理由は、あるトランザクションがブロックに含まれているかを確認するためです。

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

merkle treeのノード計算
   

生成されたハッシュをroot, もしくは merkle root と呼びます。

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

ハッシュ実装

実際にコードを実装していきます。

まず最初に、ハッシュの生成や左のリーフ(葉)と右のリーフ(葉)のハッシュを結合するMerkleHashクラスを実装します。

BitcoinやEthereumで利用するなら、BitcoinHash、EthereumHashと命名し、暗号化の方法を各仮想通貨の仕様に変更します。

{project_folder}/app/src/main/MerkleHash.java
public class MerkleHash {

    private byte[] bytes;

    /**
     * バイト配列を設定するコンストラクタ
     *
     * @param bytes バイト配列
     */
    public MerkleHash(final @NotNull byte[] bytes) {
        this.bytes = bytes;
    }

    /**
     * 文字列をバイト配列にするコンストラクタ
     *
     * @param str 文字列
     */
    public MerkleHash(final @NotNull String str) {
        // 1. 文字列をバイト配列に変換
        this.bytes = str.getBytes();
    }

    /**
     * バイト配列をSHA-256でハッシュ化して16進数文字列にして返す
     *
     * @return 16進数文字列
     */
    public String sha256HexBinary() {
        try {
            // 2. ハッシュ関数SHA-256
            byte[] bytes = MessageDigest.getInstance("SHA-256").digest(this.bytes);
            // 3. バイト配列を16進数に変換
            return printHexBinary(bytes);
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return null;
    }


    private static final char[] hexCode = "0123456789ABCDEF".toCharArray();

    /**
     * 2. バイト配列を16進数にする(バイトを16進数にする)
     * https://github.com/openforis/android-ports/blob/master/android-jaxb/src/main/java/org/arbonaut/xml/bind/DatatypeConverterImpl.java
     *
     * @param data バイト配列
     * @return 16進数文字列に変換したバイト配列
     */
    public static String printHexBinary(byte[] data) {
        StringBuilder r = new StringBuilder(data.length * 2);
        for (byte b : data) {
            r.append(hexCode[(b >> 4) & 0xF]);
            r.append(hexCode[(b & 0xF)]);
        }
        return r.toString();
    }

    /**
     * // 4. ハッシュの結合
     * ハッシュの結合
     *
     * @param right
     * @return
     */
    public MerkleHash hashConcat(final @NotNull MerkleHash right) {
        ByteBuffer byteBuf = ByteBuffer.allocate(bytes.length + right.bytes.length);
        byteBuf.put(bytes);
        byteBuf.put(right.bytes);
        byte[] newBytes = byteBuf.array();
        return new MerkleHash(newBytes);
    }
}
      

■ 実装の解説

1. 文字列をバイト配列に変換

文字列をバイト配列に変換します。

str.getBytes()

getBytes()メソッドは、プラットフォームのデフォルトの文字セットを使用して、文字列をバイト配列に変換します。

Windows環境で利用しないのであれば、文字コードはUTF-8になるはずなので、引数を指定する必要はありません。Windowsだと、デフォルトの文字セットがUnicodeの可能性があるので、文字コードにUTF-8に指定します。

2. ハッシュ関数SHA-256

バイト配列に変換したバイト配列を、ハッシュ関数SHA-256でハッシュ化します。

MessageDigest.getInstance("SHA-256").digest(str.getBytes());

ハッシュ関数とは、任意のメッセージを入力すると、固定長の値を出力する関数です。同じハッシュ関数に同じメッセージを入力すると、必ず同じ値を返します。

上記のプログラムは、ハッシュ関数に任意のメッセージ文字列をバイト配列(str.getBytes())で入力し、固定長のバイト配列を出力します。

SHA-256は、256ビット(32バイト)長のハッシュ値を取得します。

■ ハッシュ関数

ハッシュ関数は、セキュリティ関連の実装で必ず理解する必要がある知識です。

『暗号技術のすべて』(書影をクリックするとアマゾンのサイトにジャンプします)。暗号の知識が全くない人は、暗号技術入門から読むのをオススメします。

とはいえ、OSやプログラミング言語では、色々なハッシュ関数があらかじめ用意されています。なので、ゼロから実装できるようになる必要はありません。

必要な知識は、ハッシュ関数の特性や、内部でどういった処理が行われているか、そしてどのような場面で用いられているかです。

暗号に関する本は色々と発売されていますが、暗号技術入門暗号技術のすべての2冊をオススメします。

この2冊の本の内容が理解できるようになったら、Apache Commons Codecのコードを読んでさらに理解を深めるとよいでしょう。(普通はここまでする必要はないと思いますが)

3. バイト配列を16進数に変換

javaのハッシュ関数SHA-256で返却される値はバイト配列です。なので、もう少し人間が扱いやすい16進数の文字列に変換します。

javaでは、DatatypeConverterクラスを利用すればバイト配列を16進数文字列に変換できます。しかし、AndroidではDatatypeConverterクラスが実装されていません。なので、Android環境では自分でバイト配列を16進数文字列に変換する実装をおこなう必要があります。

バイトを16進数に変換する方法は、重要な知識なので、以下で実装の説明をします。

for (byte b : data) {
    r.append(hexCode[(b >> 4) & 0xF]);
    r.append(hexCode[(b & 0xF)]);
}

for文でバイト配列をバイトで取り出します。javaのbyte型は、1バイト(8ビット)で表現できる -128 ~ 127 の範囲の値です。

16進数変換なので、上位部は右に4ビット論理シフトします。

b >> 4

右への4ビット論理シフトは、 2^-4 の計算と同じです。つまり、1/16の乗算、もしくは16の除算と同じです。

例として バイト値 90 を、右へ4ビット論理シフトしてみます。

10進数の90を2進数にして考えます。

01011010 

右に4ビット論理シフトします。まずは右に1ビットシフトします。

00101101  右に1ビットシフト

シフトで値がなくなった左端は、ゼロで埋めます。
4ビット論理シフトなので、右に4回論理シフトします。

00010110  右に2ビットシフト
00001011  右に3ビットシフト
00000101  右に4ビットシフト

2進数 00000101 になりました。2進数 00000101 は10進数で5です。16進数で表しても5です。

次に結果をマスクします。マスクはAND演算です。
AND演算は、特定のビットだけを強制的にOFFにして、その他のビットはそのままにします。この操作を「ビットをマスクする」と呼びます。RGBの計算やOpenGLの実装でよく使います。

16進数なので、0xFでマスクします。取り出す部分のビットが1になります。コードだと以下のように実装します。

(b >> 4) & 0xFb

2進数に変換してAND演算します。

   0000 | 0101 (b >> 4)
+) 0000 | 1111 (0xFb)
----------------
   0000 | 0101

結果は2進数 00000101 です。10進数にすると5です。
なので、上位部の値は5です。

続いて下位部の計算をします。

下位部は、シフトはしないで、ビットをマスクします。つまり、下位4ビットのデータだけを抜き出します。コードでは以下のように実装します。

b & 0xF

2進数に変換してAND演算します。

   0101 | 1010 (b)
+) 0000 | 1111 (0xFb)  
------------------
   0000 | 1010

結果は2進数 00001010 です。10進数だと10で、16進数に変換するとAです。

char配列hexCodeを宣言して10進数を文字列に変換します。

private static final char[] hexCode = "0123456789ABCDEF".toCharArray();
hexCode[b & 0xF]

配列indexが10なので、文字列"A"が取得できます。
上記から、10進数 90 は 16進数 5A になります。

上記で説明した16進数変換処理をforループを使って全てのバイトで実行します。

4. ハッシュの結合

MerkleTreeは、左の葉と右の葉のHashを結合して新しいHashを作成します。
Hashの結合は、2つの文字列をバイト配列で結合します。

public MerkleHash hashConcat(final @NotNull MerkleHash right) {
    ByteBuffer byteBuf = ByteBuffer.allocate(bytes.length + right.bytes.length);
    byteBuf.put(bytes);
    byteBuf.put(right.bytes);
    byte[] newBytes = byteBuf.array();
    return new MerkleHash(newBytes);
}

バイト配列の結合なので、ByteBufferクラスを使います。ByteBufferは、OpenGLの頂点バッファの生成等でよく使います。

allocateメソッドで新しいbyteバッファを割り当てます。

ByteBuffer byteBuf = ByteBuffer.allocate(bytes.length + right.bytes.length);

バッファを割り当てる量は、左の葉と右の葉の文字列の結合なので、「left.bytes.length + right.bytes.length」になります。

さらに、両方のバイトをバッファへ転送し、byte配列を取得します。

byteBuf.put(bytes);
byteBuf.put(right.bytes);
byte[] newBytes = byteBuf.array();

最後に、生成したバイト配列を、ハッシュ関数SHA-256でハッシュ化して完了です。

MessageDigest.getInstance("SHA-256").digest(str.getBytes());

以上でHash処理の実装は完了です。

MerkleTreeの実装

いよいよMerkleTreeを実装します。
上記で実装したMerkleHashクラスをハッシュオブジェクトで使います。

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

    private MerkleHash merkleHash;

    public MerkleTree(@NotNull MerkleHash merkleHash) {
        this.merkleHash = merkleHash;
    }

    public static MerkleTree getMerkleTree(@NotNull List<MerkleHash> allLeavesHashes) {
        if (allLeavesHashes.isEmpty())
            throw new IllegalArgumentException("Cannot calculate Merkle root on empty hash list.");
        // 3. 2の冪条の確認
        if (!isPow2(allLeavesHashes.size())) {
            throw new IllegalArgumentException("allLeavesHashes must be Pow of 2.");
        }
        List<MerkleTree> result = allLeavesHashes.stream().map(new Function<MerkleHash, MerkleTree>() {
            @Override
            public MerkleTree apply(MerkleHash merkleHash) {
                return new Leaf(merkleHash);
            }
        }).collect(Collectors.toList());
        return buildMerkleTree(result);
    }

    private static boolean isPow2(int num) {
        return (num & (num - 1)) == 0;
    }

    private static MerkleTree buildMerkleTree(@NotNull List<MerkleTree> lastNodesList) {
        // 5. 最後のハッシュ
        if (lastNodesList.size() == 1) {
            return lastNodesList.get(0); // Root reached.
        } else {
            int n = lastNodesList.size();
            List<MerkleTree> newLevelHashes = new ArrayList<>();

            int i = 0;
            // 4. 新しいハッシュとノード作成
            while (n - 2 > i) {
                MerkleTree left = lastNodesList.get(i);
                MerkleTree right = lastNodesList.get(i + 1);
                // 結合
                MerkleHash newHash = left.merkleHash.hashConcat(right.merkleHash);
                newLevelHashes.add(new Node(newHash, left, right));
                i += 2;
            }
            return buildMerkleTree(newLevelHashes);
        }
    }
    
    /**
     * MerkleHashを取得
     *
     * @return MerkleTree
     */
    public MerkleHash getMerkleHash() {
        return merkleHash;
    }

}
        

葉の部分を扱うLeafクラス

{project_folder}/src/main/java/{package}/Leaf.java
// 1. Leafクラス
public class Leaf extends MerkleTree {
    public Leaf(@NotNull MerkleHash merkleHash) {
        super(merkleHash);
    }
}
        

ノードを扱うNodeクラス

{project_folder}/src/main/java/{package}/Node.java
// 2. Nodeクラス
public class Node extends MerkleTree {
    private MerkleTree left;
    private MerkleTree right;

    public Node(@NotNull MerkleHash merkleHash, @NotNull MerkleTree left, @NotNull MerkleTree right) {
        super(merkleHash);
        this.left = left;
        this.right = right;
    }
}
        

■ 実装の解説

1. Leafクラス

Leafクラスは、木構造のリーフ(葉)を表すクラスです。

merkle treeのリーフ(葉)

Leaf(葉)はハッシュを持ちます。なので、Leafクラスには、ハッシュを管理するMerkleHashクラスを持たせます。

public class Leaf extends MerkleTree {
    public Leaf(@NotNull MerkleHash merkleHash) {
        super(merkleHash);
    }
}

2. Nodeクラス

Nodeクラスを作成します。Nodeクラスは、木構造の根と左右のリーフ(葉)を表すクラスです。

merkle treeのノード

Nodeは根と左右のリーフ(葉)を持ちます。なので、Nodeクラスには、ハッシュを管理するMerkleHashクラスと左右のリーフ(葉)を持たせます。

public class Node extends MerkleTree {
    private MerkleHash left;
    private MerkleHash right;

    public Node(MerkleHash merkleHash, MerkleHash left, MerkleHash right) {
        super(merkleHash);
        this.left = left;
        this.right = right;
    }

}

3. 2の冪条の確認

MerkleTreeを生成するデータ数は、2の冪条でないといけません。

merkle treeのデータ数

数が2の冪条である条件は、以下のように実装します。

private static boolean isPow2(int num) {
    return (num & (num - 1)) == 0;
}

例えばnumが 2^3=8 であれば、ビット(2進数)では 1000 になります。

1000 

num - 1 すると 7 になり 0111 となります。

   0111 

1000と0111のAND演算をします。

   1000 
+) 0111  
------------------
   0000

0になりました。
計算結果のように、2の冪数では、ちょうどAND演算のビットが 1 & 1 になるのを回避する並びになり、結果が0となります。

この実装方法は、オープンソースコードでよく見かけるので、しっかりと理解しておきましょう。

4. 新しいハッシュとノード作成

リーフ(葉)leftとリーフ(葉)rightのハッシュを結合して新しいハッシュを作成し、ノードを作成します。

MerkleTree left = lastNodesList.get(i);
MerkleTree right = lastNodesList.get(i + 1);
MerkleHash newHash = left.merkleHash.hashConcat(right.merkleHash);
newLevelHashes.add(new Node(newHash, left, right));

作成したノードはListとして保存して、さらに上の階層のハッシュの作成に利用します。
この処理を最後の1件(root)になるまで再帰処理で繰り返します。

5. 最後のハッシュ

データが最後の1件(root)になったら処理を完了します。

if (lastNodesList.size() == 1) {
    return lastNodesList.get(0); // Root reached.
}

配列インデックス0のハッシュがmerkle rootです。

実行

上記で実装したコードを実行するMainクラスを作成します。

{project_folder}/src/main/java/{package}/Main.java
public class Main {
    public static void main(String[] args) {
        List<MerkleHash> merkleHashList = new ArrayList<>();
        merkleHashList.add(new MerkleHash("L1"));
        merkleHashList.add(new MerkleHash("L2"));
        merkleHashList.add(new MerkleHash("L3"));
        merkleHashList.add(new MerkleHash("L4"));

        MerkleTree merkleTree = MerkleTree.getMerkleTree(merkleHashList);
        System.out.println("root : " + merkleTree.getMerkleHash().sha256HexBinary());
    }
}
        

実行します。

terminal
root : 37F4357AEC003A5B3DDFF3EA4A165D44E0BB543A22B7EFCD22AE8B979C3A70B1
        

rootが取得できました。

まとめ

MerkleTreeは、多くのアプリケーションで利用されています。特に、ブロックチェーンでは、色々なフレームワークで利用されています。

暗号技術、木構造、ビット演算といったIT技術の重要な基礎が詰め込まれたアルゴリズムなので、頑張って習得してください。必ず役に立ちます。

関連記事

タグ検索で調べてみよう

ビットコイン