merkletree の素振り
下記リンクを参考資料として進めていきます。
参考書
リポジトリ
参考文献
- bitocoin
https://bitcoin.org/bitcoin.pdf - マークルツリー
https://alis.to/mozk/articles/3PYokoOWP7XY - ハッシュ
https://alis.to/tag/ハッシュ - 他必須知識
https://alis.to/tag/魔法使いオズモン - ブロックチェーンの中身
https://alis.to/yoshihiro/articles/KmQY7vAQPJo7
https://alis.to/JimiVD/articles/KmQYmJzyolO5
参考コード
【プログラミングビットコイン】
11.2 マークルツリー
実装に必要なこと
- アイテムの順序的リスト??
- 暗号学的ハッシュ関数-HASH256
実装方針
- 好きなハッシュ関数を使って、順序的リストの要素全てをハッシュ化する
- 1つのハッシュになればok
- ハッシュの個数が奇数なら末尾のハッシュを複製して偶数にする
- 2組で連結して親レベルハッシュにする
- 2~4を繰り返す(2を満たせば完了)
11.3 マークルペアレント
2つのペアとなるハッシュについてはそれぞれ左ハッシュ(L)・右ハッシュ(R)と呼び、左右のハッシュをぶつけた(H)結果できるのものを親ハッシュ(P)と呼ぶ。
P=H(L||R) ※||は連結
トーナメント形式の構造で優勝目指してどんどんハッシュどうしがぶつかって優勝者決めるみたいなイメージ(実装ではhashが一つになるまでwhileループを回す)
最下層のハッシュのリストをリーフ
、リーフとマークルルート以外を内部ノード
と呼ぶ。
連結したハッシュによって親ハッシュを取得する理由は包含証明
の提供のため
包括証明の入り口
ブロックチェーン(DB)のデータ全件を保存するにはデバイスの容量を上げなくてはいけない。スマホなどのCPU性能が低くならざるを得ないデバイスは完全なブロックチェーンデータを瞬時に取得できない問題がある。そこでミニマムにブロックヘッダのマークルルートエリアのみをダウンロードしてビットコインの標準コンセンサスルールに従っているかを検証できる。
包括証明の意味
右ハッシュ(R)がわかれば、左ハッシュ(L)が親ハッシュ(P)によって表現できる
⇔
P の生成者が R が誰であるかを明示することで、L が P の左の子要素出ることを証明できる
⇔
L と R を結合してハッシュ化し P を生成し、L が P の生成に使用されたことを証明する
11.4 マークルペアレントレベル
親ハッシュを得るための条件は3つ以上のハッシュ値:順序付きリストが与えられること。これをマークルペアレントレベル
と呼ぶ。ハッシュリストの要素数が奇数ならば末尾のハッシュを複製する。このようにマークルペアレントは常に2つのハッシュ値を用いて生成される。
[H(A||B), H(C||C)]
githubにあげたソースにて、マークルペアレントレベルに対応する新しいハッシュリストを作成することができた。
11.5 マークルルート
11.4ではまだ最高位の親ハッシュを求めることができていない、親ハッシュの数が一つになるまでwhile文でループを回す必要がある。
11.6 ブロックのマークルルート
マークルルートの導出はここまででいったんできた。ただ、エンディアンという問題がある👀
※エンディアンとは、複数のバイトなどを並べる順序の種類のこと。「配置方式」「並び順」と解釈しておけ。
マークルツリーの最下層ハッシュ群:リーフにリトルエンディアンを用いて、マークルルートを計算後に再度リトルエンディアンを用いるという問題👀
( ^ω^)ふぁ?・・・
まあ与えられたハッシュリストを逆にして、マークルルートが求まった後、再度ハッシュリストを逆にする。実際に起きた事象に対して特に乖離・問題はないかとおもうけど。
ブロック単位でマークルルートを導出
ここまでは一つのブロック内のマークルルートのみを対象にしたが、実際にはブロック内の各マークルルートを求める必要がある。トランザクションハッシュを加えブロック初期化設定のパラメータとして加える👀
11.7 包含証明
また今度~
時間開いちゃったので理解度チェック
- マークルツリー(ハッシュツリー)って何?
- 効率的な包含証明のために設計されたCSにおける1つの
データ構造
のこと- アイテムの順序付きリスト(ブロック内のトランザクション)と暗号学的ハッシュ関数(hash256)が必要
- 効率的な包含証明のために設計されたCSにおける1つの
- アルリズムはどんなの?
- アイテムの順序付きリストを暗号学的ハッシュ関数でハッシュ化していき、ただ一つの一意なハッシュに定まるまで2つのハッシュをペアにして連結させていく処理を繰り返す。この過程で大切なことは1ループ単位のハッシュの個数は必ず偶数でなければならないこと。つまり、任意のループでハッシュのペアが存在しない場合、末尾のハッシュを複製しそのハッシュ同士を連結させて新たな親ハッシュを作成する。具体的に言うと各ペアの親ハッシュを計算できるようになるには少なくとも3つ以上の順序付きのハッシュリストが必要になる。この条件を
マークルペアレントレベル
と呼ぶ。言い換えればマークルルートを求めるためにはこのハッシュの個数が1になるまでマークルペアレントレベルを計算する。
- アイテムの順序付きリストを暗号学的ハッシュ関数でハッシュ化していき、ただ一つの一意なハッシュに定まるまで2つのハッシュをペアにして連結させていく処理を繰り返す。この過程で大切なことは1ループ単位のハッシュの個数は必ず偶数でなければならないこと。つまり、任意のループでハッシュのペアが存在しない場合、末尾のハッシュを複製しそのハッシュ同士を連結させて新たな親ハッシュを作成する。具体的に言うと各ペアの親ハッシュを計算できるようになるには少なくとも3つ以上の順序付きのハッシュリストが必要になる。この条件を
- なぜハッシュ同士を連結して親ハッシュを求めるの?
- 包含証明を提供できるため
- ハッシュツリーの構成単位はどんなの?
- ハッシュツリーの最下層には位置する順序付きハッシュリストを
リーフ
と呼びこれがマークルルートを求める過程で初期値となるリストである。リーフ以外のハッシュツリーのノード群を内部ノード
と呼び、各過程でのハッシュのペアは順序的なアイデンティティを持つことから左ハッシュ
、右ハッシュ
と呼ばれる。そして、全ハッシュの親レベルをマークルルート
と呼ぶ。このマークルルートを求めることで各ブロック内のトランザクションの情報にアクセスするキーを保持できるというような印象でよいのだろうか?少し曖昧で不安な理解。
- ハッシュツリーの最下層には位置する順序付きハッシュリストを
包含証明
P = H (L || R)
:親ハッシュは左ハッシュと右ハッシュを連結させてハッシュ化したもの
ココで言うと、Rの値を公開すればLがPで表されるということ。
Pを作るためにLとRを連結させてハッシュ化させる過程を持つことで、Pが子ハッシュのいずれかを提供しさえすれば片方のハッシュが生成に用いられたという証明になる。
親ハッシュを求める
def merkleParent(leftHash, rightHash):
return hash256(leftHash + rightHash)
マークルペアレントレベルを求める
def merkleParentLevel(hashes):
if len(hashes) == 1: # マークルペアレントレベルはここまで求める
raise RuntimeError('Cannot take a parent level with only 1 item')
if len(hashes) % 2 == 1: # 奇数
hashes.append(hashes[-1])
parentLevel = []
for i in range(0, len(hashes), 2): # ハッシュを2つずつ取得してペアを作り親ハッシュを作成
parent = merkleParent(hashes[i], hashes[i + 1])
parentLevel.append(parent)
return parentLevel
マークルルートを求める
def merkleRoot(hashes):
currentLevel = hashes
while len(currentLevel) > 1:
currentLevel = merkleParentLevel(currentLevel)
print(currentLevel[0]) # インデックスは最上位からの深さであるので[0]とすればルートハッシュとなる
11.7 マークルツリーの使用
マークルツリーの構築が終了した。
では逆にどのようなメリットがあるのかというと、軽量クライアントと呼ばれる大雑把にまとめるとスペックの低い低用量なデバイスはブロックチェーンというデータベース情報を全て保存・処理・受信・検証することができないという問題点がある。ビットコインの送受信をスマホで行う場合を考える。ネットワークに接続し完全なブロックチェーンのデータを保持したデバイスであれば仮にトランザクションが十分にネストの深いブロックに取り込まれた場合でも送金が行われたかどうかを確認する受信者は早急に対応できる一方で、スマホのような軽量デバイスの場合は完全なブロックチェーンのデータを保持できないため、ブロックヘッダに書き込まれたマークルルートフィールドを確認して情報を得る。
フローとしてはそのブロックヘッダーをダウンロードしてビットコインのコンセンサス(合意形成基準)を満たすかどうか検証する。つまり、マークルルートを用いると完全なブロックチェーンデータを保持せずとも特定のトランザクション(送受信等の履歴)が指定のブロック内に存在するかという証明が可能?
軽量クライアントが任意のトランザクションを保持している場合・・・
リーフにトランザクション1, 2を持ちm他のトランザクション3~10が未知の場合、3~10のトランザクションハッシュを全て送信することで包含証明を作成することができる。つまりループ分でハッシュ値が1になるまでマークルペアレントレベルを求めてマークルルートを導出しさえすれば、もともと保持していたリーフのトランザクションを指定すればペアとなったトランザクションがマークルルート導出に用いられた証明になる。
11.8 マークルブロック
軽量クライアントがブロックチェーン上のデータを取得するには、ハッシュツリーの構造とどのハッシュがどのノードに存在するかという2つの情報が必要である、フルノードがそれらの情報を軽量クライアントを送信する際、マークルブロック
を利用する。そのための理解として必要なのがバイナリツリー(二分木)がどのように走査するかという過程への理解で、ノードの二分木上での走り方は下記2つが挙げられる。
- 幅優先
- 深さ優先
11.8-幅優先
縦方向:ルートからリーフ
横方向:親レベルごとに左から右に調査する
11.8-深さ優先
縦方向:ルートからリーフ
横方向:各ノードで子の左ハッシュを優先して調査する。最下層の左ハッシュが取得できて初めて右ハッシュを取得し、その後も相変わらず各親レベルにおいて左ハッシュを優先して調査する。
11.8.1 マークルツリー構造
軽量クライアントが情報取得のために初めに行うことはマークルツリーの構造把握することであり、初期値となるリーフの情報(数、ハッシュ値)を取得すればその後は親ハッシュを生成しツリーを構築できる。特に必須とされるのがリーフの数であり、この数され分かれば空のマークルツリーを生成することができる。
※ポイント
- リーフ数のlog2がマークルツリーレベルになる(減少関数)
- マークルツリーのインデックスは頂上からの深さを意味する
- マークルツリーは2次元配列
リーフ数を指定し空のマークルツリーを作成する
練習問題5はリーフ数を27に指定する
def validateMerkleRoot(self):
hashes = [h[::-1] for h in self.tx_hashes]
root = merkleRoot(hashes)
return root[::-1] == self.merkleRoot
11.8.2 マークルツリーのコーディング
空のマークルツリーが作成できたため、リーフをインプットすることでマークルルートを求めることができるはず。
hex_hashes = [
"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
"38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51",
]
マークルルートを求めるクラス
class MerkleTree:
def __init__(self, total):
def __repr__(self):
現状のロジックではこのような結果(マークルツリー)が得られる。
597c4baf...
6382df3f..., 87cf8fa3...
3ba6c080..., 8e894862..., 7ab01bb6..., 3df760ac...
272945ec..., 9a38d037..., 4a64abd9..., ec7c95e1..., 3b67006c..., 850683df..., d40d268b..., 8636b7a3...
9745f717..., 5573c8ed..., 82a02ecb..., 507ccae5..., a7a4aec2..., bb626766..., ea6d7ac1..., 45774386..., 76880292..., b1ae7f15..., 9b74f89f..., b3a92b5b..., b5c0b915..., c9d52c5c..., c555bc5f..., f9dbfafc...
しかしながら、実際のネットワーク通信においてはすべてのリーフを受信できるとは限らないばかりか、受信するメッセージにはリーフ以外の内部ノードを含む場合もある。そこで提案されるのが二分木探査の深さ優先走査であり、その際はマークルツリー走査メソッドを複数用意してクラスを定義することになる。
ツリーの内容を埋める方法(深さ優先)
11.8.3 マークルブロックコマンド
指定したトランザクションをAとする。
マークルブロック(マークルツリーマーク内の全ノード??)を伝えるフルノードは、トランザクションAが指定ブロックのマークルツリーフィールドに存在することを検証するために必要な全ての情報を送信する。
mercleblockコマンド
mercleblockコマンドはこの全ての情報
を伝達できるネットワークコマンドである。
ブロックヘッダーに存在するマークルルート
mercleblockをパースした結果得られるトランザクション数はマークルツリー構築に必要なリーフ数に対応します。これによって軽量クライアントが情報を取得すると空のマークルツリーを構築できるようになる。ハッシュフィールドにはmercleblockをパースした結果得られるハッシュの個数(0a...
)をセットする。フラグフィールドはハッシュリストの内の各ハッシュがマークルツリー内のどこに存在するかの情報を提供する。
※詳しくは「プログラミング・ビットコイン」の沼2 ブロック で説明したい
11.8.4 フラグビットとハッシュの使用
また今度~
マークルツリーとは何か
マークルツリーとは、効率的な包含証明のために設計されたデータ構造の一つです。
完全なブロックチェーンデータを保持できないスマホのような軽量クライアントは、このマークルツリーを用いてブロックヘッダのマークルルートフィールドを確認することで、トランザクションの整合性を確認し、取引の安全性を確認できます。
マークルツリーを構築するうえで必要なものは以下の2点です。
- アイテムの順序付きリスト
- 暗号学的ハッシュ関数
アイテムはブロック内のトランザクションで、こちらが今回使用する順序付きリストです。暗号学的ハッシュ関数は hashlib.sha256 を使用します。
hex_hashes = [
"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
]
マークルツリーを構築するために以下のアルゴリズムを利用します。
- ハッシュ関数を使用して、順序付きリストのアイテム全てをハッシュ化します
- 1つのハッシュになれば、処理を完了します
- 2とならない場合、ハッシュの個数が奇数なら末尾のハッシュを複製して偶数にします
- ハッシュを順番にペアにして、連結したものをハッシュ化して親レベルのハッシュを生成します。※親レベルのハッシュの個数は半分になります
- 2に戻ります
つまり、マークルツリーはアイテムの順序付きリスト全体をただ1つのハッシュにするというアイデアです。
マークルツリーの構成はサトシナカモトの論文が分かりやすいです。
マークルツリーに関する用語を整理します。
- リーフ:最下位のハッシュリスト
- 内部ノード:それ以外のハッシュリスト
- マークルルート:最高位のハッシュ
- マークルペアレント: ハッシュを順番にペアにして、連結したものをハッシュ化したもの
- マークルペアレントレベル: 各ペアの親ハッシュを得るための条件 (ex: 順序付きハッシュリストが3つ以上存在すること)
- マークルパス: マークルルートを求める最短経路
オンチェーンでやるか普通