アルゴリズム-マークルツリー

---

マークルツリー概要

マークルツリー(Merkle tree)とは

マークルツリーとは、データの要約結果を格納するツリー状のデータ構造です。

要約にはハッシュ関数が利用されていることからハッシュ木(Hash tree, ハッシュツリー)とも呼ばれます。

マークルツリーは、公開鍵暗号の開発者でもある「ラルフ・マークル」によって1979年に発明されました。

マークルルート(Merkle root)とは

マークルルートとは、マークルツリの頂点に位置するハッシュ値です。

ツリーを構成する各データ要素の真正性を保証するために利用できる値です。

トップハッシュ、ルートハッシュ、マスターハッシュなどと呼ばれることもあります。

マークルパスとは

マークルパスとは、データを検証する際に用いるハッシュ値の組み合わせです。

マークルルートを算出できるだけのハッシュ値を保持します。

計算方法

マークルツリーの作成

１．データからハッシュ値を計算する。

２．２つのハッシュ値を加算して、ハッシュ値を計算する。（結合）

３．最終的に１つのハッシュ（マークルルート）が計算されるまで結合を繰り返します。

                         [Hash1234]
                             |
              -------------------------------
              |                              |
          [Hash12]                       [Hash34]
              |                              |
       ----------------              ----------------
       |              |              |              |
    [Hash1]        [Hash2]        [Hash3]        [Hash4]
       |              |              |              |
    [Data1]        [Data2]        [Data3]        [Data4]

マークスパスとマークルルート

上図においてData1を検証する場合、「Hash2」と「Hash34」の２つのハッシュ値を用いることでマークルルートを計算できます。

予め算出したマークルルートと比較して、一致していれば真正性を保証できます。

(備考)データ数が奇数の場合

マークルツリーを構築する際に、要素データ数が奇数の場合は「末尾データを複製して２つの組み合わせにする」処理を行います。

例えば要素数が 9 個の場合、ツリーの右側は末尾データを複製し続けた値になります。

                        [1234567899999999]
             [12345678]                    [99999999]
       [1234]         [5678]          [9999]        (9999)
    [12]   [34]    [56]    [78]    [99]    (99)
  [1] [2] [3] [4] [5] [6] [7] [8] [9] (9)

Pythonによるマークルツリー

ソースコード

from hashlib import sha256

class Leaf:
    def __init__(self, index, data):
        self.parent   = None
        self.sibling  = None # 対になる要素
        self.position = None
        self.index    = index
        self.data     = data
        self.hash = sha256(data.encode()).hexdigest()

class Branch:
    def __init__(self, data):
        self.left    = None
        self.right   = None
        self.parent  = None
        self.data    = data
        self.hash = sha256(data.encode()).hexdigest()

class Tree:
    def __init__(self):
        self.leaves = []
        self.branches = []
        self.root   = None
        self._index = 0
        self._layer = None

    def count_leaf(self):
        return len(self.leaves)

    def add_leaf(self, data):
        self.leaves.append(Leaf(self._index, data))
        self._index += 1

    def add_leaves(self, data_array):
        for data in data_array:
            self.add_leaf(data)

    def build(self):
        if self.count_leaf() < 1:
            return False

        self._layer = self.leaves
        while len(self._layer) > 1:
            self._build_layer()

        self.root = self._layer[0].hash
        return True

    def _build_branch(self, left, right):
        # ２つのハッシュ値を結合する
        branch = Branch(left.hash + right.hash)
        branch.left = left
        branch.right = right

        left.parent = branch
        left.sibling = right
        left.position = "left"

        right.parent = branch
        right.sibling = left
        right.position = "right"

        return branch

    def _build_layer(self):
        new_layer = []

        # 2つの要素を組み合わせる
        for i in range(0, len(self._layer) - 1, 2):
            branch = self._build_branch(self._layer[i], self._layer[i+1])
            self.branches.append(branch)
            new_layer.append(branch)

        # 要素数が奇数の場合は、末尾要素を複製して枝を作成する。
        if len(self._layer) % 2 == 1:
            branch = self._build_branch(self._layer[-1], self._layer[-1])
            self.branches.append(branch)
            new_layer.append(branch)

        self._layer = new_layer

    def search_branch(self, hashcode):
        for branch in self.branches:
            if branch.hash == hashcode:
                return branch
        return None

    def search_leaf(self, data):
        target = None
        hash_value = sha256(data.encode()).hexdigest()
        for leaf in self.leaves:
            if leaf.hash == hash_value:
                target = leaf
        return target

    def get_path(self, data):
        markle_path = []

        target = self.search_leaf(data)
        if not(target):
            return markle_path

        markle_path.append(target.hash)
        while target.parent:
            sibling = target.sibling
            markle_path.append((sibling.hash, sibling.position))
            target = target.parent
        return markle_path

    def show_leaf(self, index):
        try:
            leaf = self.leaves[index]
            print("index   = " + str(leaf.index))
            print("hash    = " + leaf.hash)
            print("data    = " + leaf.data)
            print("position= " + str(leaf.position))

            if leaf.parent is not None:
                print("parent  = " + leaf.parent.hash)
            if leaf.sibling is not None:
                print("sibling = " + leaf.sibling.hash)
        except Exception as e:
            print("Invalid index = " + str(index))
            print(e)

    def show_leaves(self):
        for i in range(len(self.leaves)):
            print("---")
            self.show_leaf(i)
        print("")

    def _print_branch(self, indent, val, isLeft = True):
        for i in range(indent):
            if self.treeIndent[i]:
                print("|   ", end="")
            else:
                print("    ", end="")

        if isLeft:
            print("|--[left] :" + val)
        else:
            print("`--[right]:" + val)

    def show_tree(self, indent=0, hashcode=""):
        if indent == 0:
            self.treeIndent = []
            branch = self.search_branch(self.root)
            print("[root] :" + branch.hash)
        else:
            branch = self.search_branch(hashcode)

        if branch is None:
            return

        if len(self.treeIndent) <= indent:
            self.treeIndent.append(True)
        else:
            self.treeIndent[indent] = True

        if branch.left is not None:
            self._print_branch(indent, branch.left.hash)
            self.show_tree(indent + 1, branch.left.hash)
            self.treeIndent[indent] = False

        if branch.right is not None:
            self._print_branch(indent, branch.right.hash, False)
            self.show_tree(indent + 1, branch.right.hash)
            self.treeIndent[indent] = False

class Calculator:
    def __init__(self, merkle_path):
        self.merkle_path = merkle_path
        self.hash = merkle_path[0]

    def get_merkle_root(self):
        for leaf in self.merkle_path[1:]:
            sib = leaf[0]
            pos = leaf[1]
            if pos == "right":
                self.hash = sha256(self.hash.encode() + sib.encode()).hexdigest()
            else:
                self.hash = sha256(sib.encode() + self.hash.encode()).hexdigest()
        return self.hash

    def prove(self, merkle_root):
        result = self.get_merkle_root()
        if merkle_root != result:
            return False
        return True

if __name__ == '__main__':
    tree = Tree()
    tree.add_leaf("Bass drum")
    tree.add_leaf("Snare drum")
    tree.add_leaf("Hi-hat")
    tree.add_leaves(["Tom-tom left", "Tom-tom right", "Floor tom"])
    tree.add_leaves(["Ride cymbal", "Crash cymbal", "Splash cymbal"])

    tree.build()
    tree.show_leaves()
    tree.show_tree()

    print("=========================")
    print("MerkleRoot : " + tree.root)
    merkle_path = tree.get_path("Snare drum")
    print("MerklePath : ", end="")
    print(merkle_path)

    calc = Calculator(merkle_path)
    print(calc.prove(tree.root))

実行結果

> python merkle_tree.py
---
index   = 0
hash    = fe8a968b69f5a844f88fbc6ba8a0357c82009d8386af1a1205a4da61f1dec72d
data    = Bass drum
position= left
parent  = f2ff9ccf51bd697c4c2700fd500def48807ea6bc70d0b074e319259ab593bb35
sibling = 196c7d7ab9a90540e865257a111af978879cfe09a36674e5ee3704060fccf887
---
index   = 1
hash    = 196c7d7ab9a90540e865257a111af978879cfe09a36674e5ee3704060fccf887
data    = Snare drum
position= right
parent  = f2ff9ccf51bd697c4c2700fd500def48807ea6bc70d0b074e319259ab593bb35
sibling = fe8a968b69f5a844f88fbc6ba8a0357c82009d8386af1a1205a4da61f1dec72d
---
index   = 2
hash    = d8a4e418bac67a483210266d5f64f572eb7fdb6bc0f50bca92490514ee393321
data    = Hi-hat
position= left
parent  = 9a897238a9ff60176afdbf9226ae34f4daa9d41aec47a2fe8ff6a0e4b522829c
sibling = 19eac10f96ca7af77f0aa10ea5c492d42e76b92e6f03841260216db88a8133c5
---
index   = 3
hash    = 19eac10f96ca7af77f0aa10ea5c492d42e76b92e6f03841260216db88a8133c5
data    = Tom-tom left
position= right
parent  = 9a897238a9ff60176afdbf9226ae34f4daa9d41aec47a2fe8ff6a0e4b522829c
sibling = d8a4e418bac67a483210266d5f64f572eb7fdb6bc0f50bca92490514ee393321
---
index   = 4
hash    = ee5ad525c70b15f26b701bb5f003841a323a3669edd1ee7678e8c397b7320bb7
data    = Tom-tom right
position= left
parent  = 7f1945df87c346650bc96710a7af19415d6fbbd037028b36608325ec53098e39
sibling = 067059b04b662cd497013b33d110ac6b261ee7374ef563741f55fd628a9d4428
---
index   = 5
hash    = 067059b04b662cd497013b33d110ac6b261ee7374ef563741f55fd628a9d4428
data    = Floor tom
position= right
parent  = 7f1945df87c346650bc96710a7af19415d6fbbd037028b36608325ec53098e39
sibling = ee5ad525c70b15f26b701bb5f003841a323a3669edd1ee7678e8c397b7320bb7
---
index   = 6
hash    = 8a63c1f0c3fc987c187af10d1c60561ae1c5c0964f2c40e52f31c47a4376b812
data    = Ride cymbal
position= left
parent  = c5ccccf806aecef27bd5b3524271ddc712aaf0d580d38912abae0d7e1dc6877f
sibling = 6379b8c802b3ca03757786fe828f7ecfc8d0f7d1dea115f09c0fbccb0eb55fec
---
index   = 7
hash    = 6379b8c802b3ca03757786fe828f7ecfc8d0f7d1dea115f09c0fbccb0eb55fec
data    = Crash cymbal
position= right
parent  = c5ccccf806aecef27bd5b3524271ddc712aaf0d580d38912abae0d7e1dc6877f
sibling = 8a63c1f0c3fc987c187af10d1c60561ae1c5c0964f2c40e52f31c47a4376b812
---
index   = 8
hash    = f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
data    = Splash cymbal
position= right
parent  = c5a63afb2338da8e6b4ecb2fc0c06e7217705f1ac8616b2f6a2e7d1bc7d781db
sibling = f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2

[root] :1a8ee051aa7aee7f507409c3150ec9b1abef65abede333f8c5481e906c54aeef
|--[left] :ffedee1edff874a73a90f844ff25a388a56d4cae2917d45334bccedabda1372b
|   |--[left] :f0e4942b8f1299f28d6430e70b0fd70f76f857b58c4d4ab040562ad2daf764bb
|   |   |--[left] :f2ff9ccf51bd697c4c2700fd500def48807ea6bc70d0b074e319259ab593bb35
|   |   |   |--[left] :fe8a968b69f5a844f88fbc6ba8a0357c82009d8386af1a1205a4da61f1dec72d
|   |   |   `--[right]:196c7d7ab9a90540e865257a111af978879cfe09a36674e5ee3704060fccf887
|   |   `--[right]:9a897238a9ff60176afdbf9226ae34f4daa9d41aec47a2fe8ff6a0e4b522829c
|   |       |--[left] :d8a4e418bac67a483210266d5f64f572eb7fdb6bc0f50bca92490514ee393321
|   |       `--[right]:19eac10f96ca7af77f0aa10ea5c492d42e76b92e6f03841260216db88a8133c5
|   `--[right]:c7f20cf30ec3c3a54504ba0e071772ea76b352f9d9373a9e6d05e7e33c40c2f6
|       |--[left] :7f1945df87c346650bc96710a7af19415d6fbbd037028b36608325ec53098e39
|       |   |--[left] :ee5ad525c70b15f26b701bb5f003841a323a3669edd1ee7678e8c397b7320bb7
|       |   `--[right]:067059b04b662cd497013b33d110ac6b261ee7374ef563741f55fd628a9d4428
|       `--[right]:c5ccccf806aecef27bd5b3524271ddc712aaf0d580d38912abae0d7e1dc6877f
|           |--[left] :8a63c1f0c3fc987c187af10d1c60561ae1c5c0964f2c40e52f31c47a4376b812
|           `--[right]:6379b8c802b3ca03757786fe828f7ecfc8d0f7d1dea115f09c0fbccb0eb55fec
`--[right]:bdf5f328e71e2795feebd6c37dc40a9bbf91e5dd4e8f2a25d9e479883417894b
    |--[left] :c4e9716b547cedf5bdd56749804d11eec46aa03f26698c445e5fe4652773c181
    |   |--[left] :c5a63afb2338da8e6b4ecb2fc0c06e7217705f1ac8616b2f6a2e7d1bc7d781db
    |   |   |--[left] :f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
    |   |   `--[right]:f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
    |   `--[right]:c5a63afb2338da8e6b4ecb2fc0c06e7217705f1ac8616b2f6a2e7d1bc7d781db
    |       |--[left] :f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
    |       `--[right]:f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
    `--[right]:c4e9716b547cedf5bdd56749804d11eec46aa03f26698c445e5fe4652773c181
        |--[left] :c5a63afb2338da8e6b4ecb2fc0c06e7217705f1ac8616b2f6a2e7d1bc7d781db
        |   |--[left] :f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
        |   `--[right]:f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
        `--[right]:c5a63afb2338da8e6b4ecb2fc0c06e7217705f1ac8616b2f6a2e7d1bc7d781db
            |--[left] :f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
            `--[right]:f90346887d2889e2b23d007cdd4792dad18df6608a31bae22b8e67b235affdc2
=========================
MerkleRoot : 1a8ee051aa7aee7f507409c3150ec9b1abef65abede333f8c5481e906c54aeef
MerklePath : ['196c7d7ab9a90540e865257a111af978879cfe09a36674e5ee3704060fccf887', 
('fe8a968b69f5a844f88fbc6ba8a0357c82009d8386af1a1205a4da61f1dec72d', 'left'), 
('9a897238a9ff60176afdbf9226ae34f4daa9d41aec47a2fe8ff6a0e4b522829c', 'right'), 
('c7f20cf30ec3c3a54504ba0e071772ea76b352f9d9373a9e6d05e7e33c40c2f6', 'right'),
('bdf5f328e71e2795feebd6c37dc40a9bbf91e5dd4e8f2a25d9e479883417894b', 'right')]
True

関連ページ

• C言語アルゴリズム