アルゴリズム-マークルツリー
マークルツリー概要
マークルツリー(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
関連ページ
- Python
- Python_シェルコマンドを実行する
- Python_HTML解析
- Python_jsonファイルの扱い
- Python_urllibでHTTPリクエスト
- Python_マークルツリーを実装する