ピン留めされたアイテム

下記リンクを参考資料として進めていきます。

参考書

リポジトリ

https://github.com/ikmz0104/Merkle-tree

参考文献

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

参考コード

ikmzkro 2022/04/02に更新

【プログラミングビットコイン】

11.2　マークルツリー

実装に必要なこと

アイテムの順序的リスト??
暗号学的ハッシュ関数-HASH256

実装方針

好きなハッシュ関数を使って、順序的リストの要素全てをハッシュ化する
１つのハッシュになればok
ハッシュの個数が奇数なら末尾のハッシュを複製して偶数にする
２組で連結して親レベルハッシュにする
2～4を繰り返す（2を満たせば完了）

ikmzkro 4ヶ月前に更新

11.3　マークルペアレント

２つのペアとなるハッシュについてはそれぞれ左ハッシュ(L)・右ハッシュ(R)と呼び、左右のハッシュをぶつけた(H)結果できるのものを親ハッシュ(P)と呼ぶ。

P=H(L||R)　※||は連結

トーナメント形式の構造で優勝目指してどんどんハッシュどうしがぶつかって優勝者決めるみたいなイメージ（実装ではhashが一つになるまでwhileループを回す）

最下層のハッシュのリストをリーフ、リーフとマークルルート以外を内部ノードと呼ぶ。

連結したハッシュによって親ハッシュを取得する理由は包含証明の提供のため

包括証明の入り口

ブロックチェーン（DB）のデータ全件を保存するにはデバイスの容量を上げなくてはいけない。スマホなどのCPU性能が低くならざるを得ないデバイスは完全なブロックチェーンデータを瞬時に取得できない問題がある。そこでミニマムにブロックヘッダのマークルルートエリアのみをダウンロードしてビットコインの標準コンセンサスルールに従っているかを検証できる。

包括証明の意味

右ハッシュ(R)がわかれば、左ハッシュ(L)が親ハッシュ(P)によって表現できる
⇔
P の生成者がＲが誰であるかを明示することで、L が P の左の子要素出ることを証明できる
⇔
L と R を結合してハッシュ化し P を生成し、L がＰの生成に使用されたことを証明する

ikmzkro 2022/04/02に更新

11.4　マークルペアレントレベル

親ハッシュを得るための条件は３つ以上のハッシュ値：順序付きリストが与えられること。これをマークルペアレントレベルと呼ぶ。ハッシュリストの要素数が奇数ならば末尾のハッシュを複製する。このようにマークルペアレントは常に２つのハッシュ値を用いて生成される。

[H(A||B), H(C||C)]

githubにあげたソースにて、マークルペアレントレベルに対応する新しいハッシュリストを作成することができた。

ikmzkro 2022/04/02に更新

11.5　マークルルート

11.4ではまだ最高位の親ハッシュを求めることができていない、親ハッシュの数が一つになるまでwhile文でループを回す必要がある。

ikmzkro 2022/04/02に更新

11.6　ブロックのマークルルート

マークルルートの導出はここまででいったんできた。ただ、エンディアンという問題がある👀

※エンディアンとは、複数のバイトなどを並べる順序の種類のこと。「配置方式」「並び順」と解釈しておけ。

マークルツリーの最下層ハッシュ群：リーフにリトルエンディアンを用いて、マークルルートを計算後に再度リトルエンディアンを用いるという問題👀

（　＾ω＾）ふぁ？・・・

まあ与えられたハッシュリストを逆にして、マークルルートが求まった後、再度ハッシュリストを逆にする。実際に起きた事象に対して特に乖離・問題はないかとおもうけど。

ikmzkro 2022/04/02に更新

ブロック単位でマークルルートを導出

ここまでは一つのブロック内のマークルルートのみを対象にしたが、実際にはブロック内の各マークルルートを求める必要がある。トランザクションハッシュを加えブロック初期化設定のパラメータとして加える👀

ikmzkro 2022/04/02に更新

11.7　包含証明

また今度～

ikmzkro 2022/04/30に更新

時間開いちゃったので理解度チェック

マークルツリー（ハッシュツリー）って何？
- 効率的な包含証明のために設計されたCSにおける１つのデータ構造のこと
  - アイテムの順序付きリスト（ブロック内のトランザクション）と暗号学的ハッシュ関数（hash256）が必要
アルリズムはどんなの？
- アイテムの順序付きリストを暗号学的ハッシュ関数でハッシュ化していき、ただ一つの一意なハッシュに定まるまで２つのハッシュをペアにして連結させていく処理を繰り返す。この過程で大切なことは１ループ単位のハッシュの個数は必ず偶数でなければならないこと。つまり、任意のループでハッシュのペアが存在しない場合、末尾のハッシュを複製しそのハッシュ同士を連結させて新たな親ハッシュを作成する。具体的に言うと各ペアの親ハッシュを計算できるようになるには少なくとも３つ以上の順序付きのハッシュリストが必要になる。この条件をマークルペアレントレベルと呼ぶ。言い換えればマークルルートを求めるためにはこのハッシュの個数が１になるまでマークルペアレントレベルを計算する。
なぜハッシュ同士を連結して親ハッシュを求めるの？
- 包含証明を提供できるため
ハッシュツリーの構成単位はどんなの？
- ハッシュツリーの最下層には位置する順序付きハッシュリストをリーフと呼びこれがマークルルートを求める過程で初期値となるリストである。リーフ以外のハッシュツリーのノード群を内部ノードと呼び、各過程でのハッシュのペアは順序的なアイデンティティを持つことから左ハッシュ、右ハッシュと呼ばれる。そして、全ハッシュの親レベルをマークルルートと呼ぶ。このマークルルートを求めることで各ブロック内のトランザクションの情報にアクセスするキーを保持できるというような印象でよいのだろうか？少し曖昧で不安な理解。

ikmzkro 2022/04/30

包含証明

P = H (L || R)　：親ハッシュは左ハッシュと右ハッシュを連結させてハッシュ化したもの

ココで言うと、Rの値を公開すればLがPで表されるということ。
Pを作るためにLとRを連結させてハッシュ化させる過程を持つことで、Ｐが子ハッシュのいずれかを提供しさえすれば片方のハッシュが生成に用いられたという証明になる。

ikmzkro 2022/05/01に更新

親ハッシュを求める

helper.py

def merkleParent(leftHash, rightHash):
    return hash256(leftHash + rightHash)

ikmzkro 2022/05/01に更新

マークルペアレントレベルを求める

helper.py

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): # ハッシュを２つずつ取得してペアを作り親ハッシュを作成
        parent = merkleParent(hashes[i], hashes[i + 1])
        parentLevel.append(parent)
    return parentLevel

ikmzkro 2022/05/01に更新

マークルルートを求める

helper.py

def merkleRoot(hashes):
    currentLevel = hashes
    while len(currentLevel) > 1:
        currentLevel = merkleParentLevel(currentLevel)
    print(currentLevel[0]) # インデックスは最上位からの深さであるので[0]とすればルートハッシュとなる

ikmzkro 2022/04/30に更新

11.7　マークルツリーの使用

マークルツリーの構築が終了した。

では逆にどのようなメリットがあるのかというと、軽量クライアントと呼ばれる大雑把にまとめるとスペックの低い低用量なデバイスはブロックチェーンというデータベース情報を全て保存・処理・受信・検証することができないという問題点がある。ビットコインの送受信をスマホで行う場合を考える。ネットワークに接続し完全なブロックチェーンのデータを保持したデバイスであれば仮にトランザクションが十分にネストの深いブロックに取り込まれた場合でも送金が行われたかどうかを確認する受信者は早急に対応できる一方で、スマホのような軽量デバイスの場合は完全なブロックチェーンのデータを保持できないため、ブロックヘッダに書き込まれたマークルルートフィールドを確認して情報を得る。
フローとしてはそのブロックヘッダーをダウンロードしてビットコインのコンセンサス（合意形成基準）を満たすかどうか検証する。つまり、マークルルートを用いると完全なブロックチェーンデータを保持せずとも特定のトランザクション（送受信等の履歴）が指定のブロック内に存在するかという証明が可能?

ikmzkro 2022/04/30

軽量クライアントが任意のトランザクションを保持している場合・・・

リーフにトランザクション１, 2を持ちｍ他のトランザクション3～10が未知の場合、3～10のトランザクションハッシュを全て送信することで包含証明を作成することができる。つまりループ分でハッシュ値が１になるまでマークルペアレントレベルを求めてマークルルートを導出しさえすれば、もともと保持していたリーフのトランザクションを指定すればペアとなったトランザクションがマークルルート導出に用いられた証明になる。

ikmzkro 2022/04/30に更新

11.8　マークルブロック

軽量クライアントがブロックチェーン上のデータを取得するには、ハッシュツリーの構造とどのハッシュがどのノードに存在するかという２つの情報が必要である、フルノードがそれらの情報を軽量クライアントを送信する際、マークルブロックを利用する。そのための理解として必要なのがバイナリツリー（二分木）がどのように走査するかという過程への理解で、ノードの二分木上での走り方は下記２つが挙げられる。

幅優先
深さ優先

ikmzkro 2022/04/30に更新

11.8-幅優先

縦方向：ルートからリーフ
横方向：親レベルごとに左から右に調査する

ikmzkro 2022/05/01に更新

11.8-深さ優先

縦方向：ルートからリーフ
横方向：各ノードで子の左ハッシュを優先して調査する。最下層の左ハッシュが取得できて初めて右ハッシュを取得し、その後も相変わらず各親レベルにおいて左ハッシュを優先して調査する。

ikmzkro 2022/05/01に更新

11.8.1 マークルツリー構造

軽量クライアントが情報取得のために初めに行うことはマークルツリーの構造把握することであり、初期値となるリーフの情報（数、ハッシュ値）を取得すればその後は親ハッシュを生成しツリーを構築できる。特に必須とされるのがリーフの数であり、この数され分かれば空のマークルツリーを生成することができる。

※ポイント

リーフ数のlog2がマークルツリーレベルになる（減少関数）
マークルツリーのインデックスは頂上からの深さを意味する
マークルツリーは２次元配列

ikmzkro 2022/05/01に更新

リーフ数を指定し空のマークルツリーを作成する

練習問題５はリーフ数を２７に指定する

helper.py

def validateMerkleRoot(self):
    hashes = [h[::-1] for h in self.tx_hashes]
    root = merkleRoot(hashes)
    return root[::-1] == self.merkleRoot

ikmzkro 2022/05/01に更新

11.8.2 マークルツリーのコーディング

空のマークルツリーが作成できたため、リーフをインプットすることでマークルルートを求めることができるはず。

hex_hashes = [
    "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
    "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
    "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
    "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
    "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
    "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
    "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
    "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
    "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
    "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
    "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
    "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
    "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
    "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
    "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
    "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
    "38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51",
]

ikmzkro 2022/05/01に更新

マークルルートを求めるクラス

main.py

class MerkleTree:
    def __init__(self, total):
    def __repr__(self):

ikmzkro 2022/05/01に更新

現状のロジックではこのような結果（マークルツリー）が得られる。

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...

しかしながら、実際のネットワーク通信においてはすべてのリーフを受信できるとは限らないばかりか、受信するメッセージにはリーフ以外の内部ノードを含む場合もある。そこで提案されるのが二分木探査の深さ優先走査であり、その際はマークルツリー走査メソッドを複数用意してクラスを定義することになる。

ikmzkro 2022/05/01に更新

ツリーの内容を埋める方法（深さ優先）

ikmzkro 2022/05/01

11.8.3 マークルブロックコマンド

指定したトランザクションをAとする。

マークルブロック（マークルツリーマーク内の全ノード??）を伝えるフルノードは、トランザクションAが指定ブロックのマークルツリーフィールドに存在することを検証するために必要な全ての情報を送信する。

ikmzkro 2022/05/01

mercleblockコマンド

mercleblockコマンドはこの全ての情報を伝達できるネットワークコマンドである。

ikmzkro 2022/05/01に更新

ブロックヘッダーに存在するマークルルート

mercleblockをパースした結果得られるトランザクション数はマークルツリー構築に必要なリーフ数に対応します。これによって軽量クライアントが情報を取得すると空のマークルツリーを構築できるようになる。ハッシュフィールドにはmercleblockをパースした結果得られるハッシュの個数(0a...)をセットする。フラグフィールドはハッシュリストの内の各ハッシュがマークルツリー内のどこに存在するかの情報を提供する。

※詳しくは「プログラミング・ビットコイン」の沼２　ブロック　で説明したい

ikmzkro 2022/05/01

11.8.4　フラグビットとハッシュの使用

また今度～

ikmzkro 5ヶ月前

マークルツリーとは何か

マークルツリーとは、効率的な包含証明のために設計されたデータ構造の一つです。
完全なブロックチェーンデータを保持できないスマホのような軽量クライアントは、このマークルツリーを用いてブロックヘッダのマークルルートフィールドを確認することで、トランザクションの整合性を確認し、取引の安全性を確認できます。

マークルツリーを構築するうえで必要なものは以下の2点です。

アイテムの順序付きリスト
暗号学的ハッシュ関数

アイテムはブロック内のトランザクションで、こちらが今回使用する順序付きリストです。暗号学的ハッシュ関数は hashlib.sha256 を使用します。

hex_hashes = [
    "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
    "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
    "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
]

マークルツリーを構築するために以下のアルゴリズムを利用します。

ハッシュ関数を使用して、順序付きリストのアイテム全てをハッシュ化します
1つのハッシュになれば、処理を完了します
2とならない場合、ハッシュの個数が奇数なら末尾のハッシュを複製して偶数にします
ハッシュを順番にペアにして、連結したものをハッシュ化して親レベルのハッシュを生成します。※親レベルのハッシュの個数は半分になります
2に戻ります

つまり、マークルツリーはアイテムの順序付きリスト全体をただ1つのハッシュにするというアイデアです。

マークルツリーの構成はサトシナカモトの論文が分かりやすいです。

マークルツリーに関する用語を整理します。

リーフ：最下位のハッシュリスト
内部ノード：それ以外のハッシュリスト
マークルルート：最高位のハッシュ
マークルペアレント: ハッシュを順番にペアにして、連結したものをハッシュ化したもの
マークルペアレントレベル: 各ペアの親ハッシュを得るための条件 (ex: 順序付きハッシュリストが３つ以上存在すること)
マークルパス: マークルルートを求める最短経路

ikmzkro 3ヶ月前

オンチェーンでやるか普通
https://smacon.dev/posts/merkle-tree/

このスクラップは2023/08/24にクローズされました

参考書

リポジトリ

参考文献

参考コード

11.2 マークルツリー

11.3 マークルペアレント

包括証明の入り口

包括証明の意味

11.4 マークルペアレントレベル

11.5 マークルルート

11.6 ブロックのマークルルート

ブロック単位でマークルルートを導出

11.7 包含証明

時間開いちゃったので理解度チェック

包含証明

親ハッシュを求める

マークルペアレントレベルを求める

マークルルートを求める

11.7 マークルツリーの使用

軽量クライアントが任意のトランザクションを保持している場合・・・

11.8 マークルブロック

11.8-幅優先

11.8-深さ優先

11.8.1 マークルツリー構造

リーフ数を指定し空のマークルツリーを作成する

11.8.2 マークルツリーのコーディング

マークルルートを求めるクラス

ツリーの内容を埋める方法（深さ優先）

11.8.3 マークルブロックコマンド

mercleblockコマンド

ブロックヘッダーに存在するマークルルート

11.8.4 フラグビットとハッシュの使用

マークルツリーとは何か

11.2　マークルツリー

11.3　マークルペアレント

11.4　マークルペアレントレベル

11.5　マークルルート

11.6　ブロックのマークルルート

11.7　包含証明

11.7　マークルツリーの使用

11.8　マークルブロック

11.8.4　フラグビットとハッシュの使用