マークルツリーとは、データの要約結果を格納するツリー状のデータ構造です。
要約にはハッシュ関数が利用されていることからハッシュ木(Hash tree, ハッシュツリー)とも呼ばれます。
マークルツリーは、公開鍵暗号の開発者でもある「ラルフ・マークル」によって1979年に発明されました。
マークルルートとは、マークルツリの頂点に位置するハッシュ値です。
ツリーを構成する各データ要素の真正性を保証するために利用できる値です。
トップハッシュ、ルートハッシュ、マスターハッシュなどと呼ばれることもあります。
マークルパスとは、データを検証する際に用いるハッシュ値の組み合わせです。
マークルルートを算出できるだけのハッシュ値を保持します。
1.データからハッシュ値を計算する。
2.2つのハッシュ値を加算して、ハッシュ値を計算する。(結合)
3.最終的に1つのハッシュ(マークルルート)が計算されるまで結合を繰り返します。
[Hash1234] | ------------------------------- | | [Hash12] [Hash34] | | ---------------- ---------------- | | | | [Hash1] [Hash2] [Hash3] [Hash4] | | | | [Data1] [Data2] [Data3] [Data4]
上図においてData1を検証する場合、「Hash2」と「Hash34」の2つのハッシュ値を用いることでマークルルートを計算できます。
予め算出したマークルルートと比較して、一致していれば真正性を保証できます。
マークルツリーを構築する際に、要素データ数が奇数の場合は「末尾データを複製して2つの組み合わせにする」処理を行います。
例えば要素数が 9 個の場合、ツリーの右側は末尾データを複製し続けた値になります。
[1234567899999999] [12345678] [99999999] [1234] [5678] [9999] (9999) [12] [34] [56] [78] [99] (99) [1] [2] [3] [4] [5] [6] [7] [8] [9] (9)
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): # 2つのハッシュ値を結合する 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