本投稿は TECOTEC Advent Calendar 2022 の25日目の記事です。
こんにちは。次世代デジタル基盤開発事業部の六本木です。
今回はビットコインを始めとするブロックチェーンでとても重要な Merkle tree (Xmas tree) およびその Merkle root の計算について紹介するとともに、簡単な実装を行いましたのでシェアしたいとおもいます。
Merkle treeとは？
データを要約・検証する技術で、以下計算ルールに従って構成された2分木のことです。(より一般に Hash tree とも言います)
- データ列が存在する
- 全てのデータ列にそれぞれハッシュ関数を適用する
- 得られた結果について、左から順番にペアを作っていく
- 列の数が奇数だった場合、最後の(ハッシュされた)データはコピーしてペアとする
- 各ペアについて、単純に結合したもので再度ハッシュを適用する
- 以下同様の処理を繰り返す(列の数はどんどん半分になっていく)
- 最後に残ったひとつのデータはコピーせず、これをMerkle root (hash root, top hash)という。
さて、このMerkle rootはなにがいいのでしょうか。
Merkle rootの存在意義
p2pなどの分散型システムにおいて、取得したデータが破損していないか・改ざんされていないかをチェックするのに有用です。
例えば得られたデータについて、そのハッシュ値と計算過程のハッシュ値(Proofといいます)を使ってMerkle rootを計算した結果、信頼のおけるノードが一律管理しているMerkle rootと一致すれば、データに問題ないと言えます。 (逆に少しでも違うと、Merkle rootの値は全く違うものとなります)
またさらに、Proofは全て取得する必要はなくデータのインデックスさえ分かれば、そのデータが属するrootまでの道筋におけるペアのハッシュ値が分かり、Merkle rootを効率的に計算することが可能です。 (そのようなhash値の集合をMerkle Pathという(下図の{h3, h7, h12}）)
例えば、データd (配列0始まりの場合、インデックス3)の検証を行う際は、下図緑のハッシュ値のみ取得できればOKです。
Merkle treeはブロックチェーンの他、以下サービス・ツールでも利用されているそうです。
- DynamoDB
- git
ブロックチェーンにおいては、このMerkle rootをブロックヘッダに記録していることが多く、このお陰でスマートフォンにウォレットを入れることができるようになります。
全てのトランザクションを保持(Full node wallet)する場合と比べ、1000分の1程度の容量のみあれば、トランザクションの検証が可能になります。 この形式をSPV(Simplified Payment Verification) といいます。
Python でビットコインのMerkle root を計算してみる
今回は、 https://www.blockchain.com/explorer/api/blockchain_api を利用して、実際のトランザクションハッシュ全てからMerkle rootを計算し、実際にこのブロックのMerkle rootと一致するか見てみます。
ビットコインの実装では、ハッシュ関数はダブルハッシュsha256(sha256())が利用されています。 ※何故このような関数を利用しているのか(2重でsha256しているのか)は調べても出てきませんでした。謎です。
また注意点として、計算する際は、リトルエンディアンで行う必要があるので、リバースする必要があります。 計算は再帰的に行っています。
from hashlib import sha256 import requests, json base_url = 'https://blockchain.info/rawblock/' # block 768278 (2022/12/21 8:46に生成) block_hash = '00000000000000000001d8047b21fdb06ed35aa2a7feb99b910b8405e2404c00' end_point = base_url + block_hash # ビッグエンディアン<-> リトルエンディアンを変換する関数 # https://qiita.com/QUANON/items/e3d91a6f33536bd0de5a def reverse(hex_be): bytes_be = bytes.fromhex(hex_be) bytes_le = bytes_be[::-1] hex_le = bytes_le.hex() return hex_le # double sha256を計算する関数 def dhash(hash): bin = bytes.fromhex(hash) hash = sha256(bin).digest() hash2 = sha256(hash).hexdigest() return hash2 # 再帰的にMerkle treeを構築していく関数 def culculate_merkle(hash_list): # 要素数が1になったらそれがMerkle root if len(hash_list) == 1: return hash_list[0] # 要素数の数が奇数だったら最後の要素を複製する if len(hash_list) % 2 == 1: hash_list.append(hash_list[-1]) parent_hash_list = [] # 順番に2つずつペアを組んで処理 # https://hk29.hatenablog.jp/entry/2020/10/25/134840 it = iter(hash_list) for hash1, hash2 in zip(it, it): # hash1とhash2を単純に結合する parent_hash_list.append(hash1 + hash2) # 全ての要素に対してdhashを適用 parent_hash_list = list(map(dhash, parent_hash_list)) # 再帰的にコール return culculate_merkle(parent_hash_list) # トランザクションハッシュを取得するために # https://www.blockchain.com/explorer/api/blockchain_api を利用 data = requests.get(end_point) jsondata = json.loads(data.text) merkleroot_expected = jsondata['mrkl_root'] # transaction hashのみ抽出 # データ⇒ 初回のhashは既に実施済み tx_list = list(map(lambda tx_object: tx_object['hash'], jsondata['tx'])) # ビッグエンディアン⇒ リトルエンディアンに変換 tx_list = list(map(reverse, tx_list)) # Merkle rootを計算する output = culculate_merkle(tx_list) # リトルエンディアン⇒ ビッグエンディアンに変換 output = reverse(output) print('期待する値:',merkleroot_expected) print('計算した値:',output)
結果はこちらです。
$ python merkleTree.py 期待する値: ee021ec71f5b4b4c6307ffcda579d2147e24d1d19b24ba89a1e993b2640d384a 計算した値: ee021ec71f5b4b4c6307ffcda579d2147e24d1d19b24ba89a1e993b2640d384a
いかがでしょうか、ブロックヘッダに格納されているMerkle root と計算したMerkle rootが一致することが確認できました。
今後の課題としては、インデックスを受け取り、そのパス上のペアとなるproofを返却するgenerateProof関数と、トランザクションハッシュが正しいか検証するVerify関数を実装してみたいなと思います。
以上、クリスマスツリーではなくマークルツリーのお話でしたが、よい一日を。
参考
- https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees
- https://www.blockchain.com/explorer/api/blockchain_api
- https://trebaud.github.io/posts/merkle-tree/
- https://qiita.com/takaheraw@github/items/d731c9b425da34ca4400
- https://qiita.com/QUANON/items/e3d91a6f33536bd0de5a
- https://hk29.hatenablog.jp/entry/2020/10/25/134840
- https://stackoverflow.com/questions/72411835/how-to-correctly-do-a-double-sha256-hashing
- 特にこちらのリンクには助けられました。最初dhashの計算を下記のように行っていて、思うような結果がなかなか得られなかったので。
def dhash(hash):
return reverse(sha256(sha256(hash.encode('utf-8')).hexdigest().encode('utf-8')).hexdigest())
