Merkle Tree：Bitcoin・Git・IPFS が使う改ざん検出のハッシュツリー

import hashlib
def sha256(s):    return hashlib.sha256(s.encode() if isinstance(s, str) else s).hexdigest()
def merkle_root(leaves):    '''葉のリストから Merkle root を計算'''    if not leaves:        return None    h = [sha256(l) for l in leaves]    while len(h) > 1:        if len(h) % 2:            h.append(h[-1])  # 奇数個なら末尾を複製        h = [sha256(h[i] + h[i+1]) for i in range(0, len(h), 2)]    return h[0]
# 4 トランザクションのブロックtxs = ['Alice→Bob: 1 BTC', 'Carol→Dave: 0.5 BTC',       'Eve→Frank: 2 BTC', 'Grace→Henry: 0.1 BTC']root = merkle_root(txs)print(f'Merkle root: {root}')
# 1 文字でも変えると root が変わるtxs_tampered = ['Alice→Bob: 1 BTC', 'Carol→Dave: 0.5 BTC',                'Eve→Frank: 2 BTC', 'Grace→Henry: 0.2 BTC']  # 0.1 → 0.2root_t = merkle_root(txs_tampered)print(f'改ざん後 root: {root_t}')print(f'検出: {root != root_t}')
# 実機実行結果:# Merkle root: <ハッシュ># 改ざん後 root: <別のハッシュ># 検出: True

def build_tree(leaves):    '''全レベルのハッシュを保持'''    levels = [[sha256(l) for l in leaves]]    while len(levels[-1]) > 1:        cur = levels[-1]        if len(cur) % 2: cur = cur + [cur[-1]]        levels.append([sha256(cur[i]+cur[i+1]) for i in range(0, len(cur), 2)])    return levels
def merkle_proof(levels, index):    '''葉 index に対する Merkle proof を生成'''    proof = []    for level in levels[:-1]:        sibling = index ^ 1  # 兄弟は最下位 bit 反転        if sibling >= len(level): sibling = index        proof.append((sibling > index, level[sibling]))  # (right?, hash)        index //= 2    return proof
def verify_proof(leaf, proof, root):    '''proof を使って root に到達するか検証'''    h = sha256(leaf)    for is_right, sibling in proof:        h = sha256(h + sibling) if is_right else sha256(sibling + h)    return h == root
txs = [f'tx{i}' for i in range(8)]levels = build_tree(txs)root = levels[-1][0]
# tx3 の proof を作って検証proof = merkle_proof(levels, 3)print(f'proof 長: {len(proof)} (= log₂ 8 = 3)')print(f'検証: {verify_proof("tx3", proof, root)}')print(f'偽装検証: {verify_proof("tx3_fake", proof, root)}')