マークル木とデータの検証
証明に必要な値と、ルートを信頼する必要がある理由を説明します。
説明
ハッシュ木は、複数データのハッシュを段階的にまとめて一つのルートにする構造です。ある葉が含まれることは、その葉と経路上の兄弟ハッシュからルートを再計算して確かめられます。
4件の記録から木を作り、3件目の記録の証明を検証します。記録、左右の順番、兄弟ハッシュを変更し、最後に照合先のルート自体を差し替えた場合を考えます。
証明に必要な値と、ルートを信頼する必要がある理由を説明します。
1葉の前に識別バイトを付ける
RFC 6962の木のハッシュ規則を用います。葉は0x00、内部ノードは0x01を先頭に付け、両者の解釈が重ならないようにします。
from sc06 import *
records = [b"A:100",b"B:200",b"C:300",b"D:400"]
leaves = [leaf(x)0x00と各記録をハッシュする for x in records]
print("\n".join(f"{i}: {h.hex()}" for i,h in enumerate(leaves)))4個の葉ハッシュができました。葉の位置0〜3も証明経路の左右を決める情報です。
2左右の葉から親を作る
左のハッシュ、右のハッシュの順に連結します。
left = branch(leaves[0],leaves[1])左半分の親を計算する
right = branch(leaves[2],leaves[3])右半分の親を計算する
print(left.hex())
print(right.hex())二つの親ができました。順序を交換すると入力が変わり、一般に別のハッシュになります。
3ルートを保存する
二つの親から一つのルートを計算し、確認済みの値として別に保持します。
root_hash = branch(left,right)木全体のルートを計算する
trusted_root = root_hash
print(root_hash.hex())この32バイトが4件の並びに対応します。実際のログでは署名付きルートなど、値を信頼するための仕組みも必要です。
4位置2の証明経路を取り出す
C:300の兄弟はD:400の葉、その上では左半分の親です。全4件の本文は不要です。
path =葉から上へ兄弟ハッシュを並べる [leaves[3],left]
print([x.hex() for x in path])
print(proof(records[2],2,path)位置2の左右関係でルートを再計算する.hex())
print(proof(records[2],2,path) == trusted_root)二つの兄弟ハッシュとC:300から同じルートが復元できました。最下段では右へ兄弟を置き、次段では左へ置きます。
5記録の金額を変更する
証明経路をそのままにしてC:300をC:900へ変更します。
print(proof(b"C:900",2,path)変更後の葉でルートを計算する == trusted_root)Falseです。葉の変更が親からルートまで伝わり、保持していた値と一致しません。
6位置と兄弟ハッシュを変更する
同じ葉でも位置や兄弟を取り違えれば、元のルートへ到達しません。
print(proof(records[2],3,path)位置を2から3へ変える == trusted_root)
print(proof(records[2],2,[leaves[0],left])最下段の兄弟を変える == trusted_root)どちらもFalseです。証明はハッシュの集合ではなく、順番と左右の位置を含む経路です。
7ルートも作り直せる相手を考える
改変した葉に合う新しいルートを作り、その値だけを相手から受け取った場合です。
fake_root =改変に合わせたルートを作る proof(b"C:900",2,path)
print(proof(b"C:900",2,path) == fake_root)
print(fake_root == trusted_root元の信頼するルートと比較する)新しいルートとは一致しても確認済みのルートとは一致しません。包含証明だけで、ルート発行者の正当性やログ全体の追記専用性まで確認したことにはなりません。
まとめ
葉と経路上の兄弟からルートを再計算できます。
左右の順序と葉の位置も検証に必要です。
包含証明は、別途信頼するルートと照合して初めて意味を持ちます。
操作履歴と解説を振り返れます。
Python 3.15 / cryptography 50.0.2 / 公開試料と固定時刻
from sc06 import *
records = [b"A:100",b"B:200",b"C:300",b"D:400"]
leaves = [leaf(x) for x in records]
print("\n".join(f"{i}: {h.hex()}" for i,h in enumerate(leaves)))0: c623eb11f138e4cd9f47ee2e28d1b53f2dc9f949ed33513afa87758c3aa417a6 1: 35bedc36717b9e5192ccdad9bb83eb531687c7bedd91684a6eb394928361dd2c 2: 396af7e921d01b3bb5b17212f31d0ca219a65dd8f998343aee54fc4bcdda0923 3: 9bed9dfcbcd0694fd1ed4ab013c6b1a36cc0e7a1217271b0ffb7ad5681d093f0
left = branch(leaves[0],leaves[1])
right = branch(leaves[2],leaves[3])
print(left.hex())
print(right.hex())d8f6859ff609c5bfd4b7656ca3eaef71c49966f32eea901583bc776c6a1798e1 e263724a2e7611687629ca1192e94f50fd8285777d80944fe14ce55c0f01b18b
root_hash = branch(left,right)
trusted_root = root_hash
print(root_hash.hex())9948b5c2aeeea19c54ccb27112c19409b4ac0d26fe3ee7d144d44f17b7c1c17c
path = [leaves[3],left]
print([x.hex() for x in path])
print(proof(records[2],2,path).hex())
print(proof(records[2],2,path) == trusted_root)['9bed9dfcbcd0694fd1ed4ab013c6b1a36cc0e7a1217271b0ffb7ad5681d093f0', 'd8f6859ff609c5bfd4b7656ca3eaef71c49966f32eea901583bc776c6a1798e1'] 9948b5c2aeeea19c54ccb27112c19409b4ac0d26fe3ee7d144d44f17b7c1c17c True
print(proof(b"C:900",2,path) == trusted_root)False
print(proof(records[2],3,path) == trusted_root)
print(proof(records[2],2,[leaves[0],left]) == trusted_root)False False
fake_root = proof(b"C:900",2,path)
print(proof(b"C:900",2,path) == fake_root)
print(fake_root == trusted_root)True False
演習完了