ブロックチェーンのデータ構造 - データサイエンス関連+αのメモ

暗号学的ハッシュ関数¶

ブロックチェーンのデータ構造はほぼすべて 暗号学的ハッシュ関数（cryptographic hash function） の性質に依存している。

ハッシュ関数 $H$ は任意長の入力を固定長の出力（ハッシュ値、ダイジェスト）に写す関数。暗号学的ハッシュ関数は次の性質を満たす。

性質	内容
原像計算困難性（preimage resistance）	ハッシュ値 $y$ から $H(x) = y$ となる $x$ を求めるのが困難
第二原像計算困難性（second preimage resistance）	$x$ が与えられたとき、 $H(x') = H(x)$ となる別の $x' \neq x$ を求めるのが困難
衝突困難性（collision resistance）	$H(x) = H(x')$ となる任意の組 $x \neq x'$ を求めるのが困難

加えて、入力が1ビットでも変わると出力が予測不能に大きく変わる（雪崩効果）。

BitcoinではSHA-256（多くの箇所で2回適用する SHA256(SHA256(x))）、EthereumではKeccak-256が使われる。

import hashlib

for s in ["あいうえお", "あいうえこ", "あいうおえ"]:
    print(s, hashlib.sha256(s.encode()).hexdigest())

あいうえお fdb481ea956fdb654afcc327cff9b626966b2abdabc3f3e6dbcb1667a888ed9a
あいうえこ 59d9b0d8d3e1262bd220ebc58989569c064b48df22c28dfcc3fd2186b484af34
あいうおえ a762518a8b8eff0175e1e0e9493594db95b23aba9f04dae7f52621c1dafddea9

入力の長さにかかわらず出力は256bit（16進数で64桁）になるので、大きなデータの「要約」としても使える。

ハッシュチェーン¶

各ブロックは ブロックヘッダー に直前のブロックのハッシュ値（previous block hash）を持つ。これにより、ブロックが鎖状に連結される。

あるブロックの中身を改ざんすると、そのブロックのハッシュ値が変わり、次のブロックが持つ prev hash と一致しなくなる。整合性を保つには以降のすべてのブロックを作り直す必要がある。後述のProof of Workと組み合わせると、ブロックの作り直しには莫大な計算コストがかかるため、過去の記録の改ざんが事実上不可能になる。

なお、各ブロックヘッダーには自分自身のハッシュ値は入っていない（自己言及になるため）。

以下は単純なハッシュチェーンの実装例。

import hashlib
import json
from dataclasses import dataclass, field


def sha256d(data: bytes) -> str:
    """SHA-256を2回適用する（Bitcoin方式）"""
    return hashlib.sha256(hashlib.sha256(data).digest()).hexdigest()


@dataclass
class Block:
    prev_hash: str
    transactions: list[str]

    def hash(self) -> str:
        payload = json.dumps({"prev": self.prev_hash, "txs": self.transactions}, ensure_ascii=False)
        return sha256d(payload.encode())


@dataclass
class Chain:
    blocks: list[Block] = field(default_factory=list)

    def append(self, transactions: list[str]):
        prev = self.blocks[-1].hash() if self.blocks else "0" * 64
        self.blocks.append(Block(prev, transactions))

    def is_valid(self) -> bool:
        return all(self.blocks[i].prev_hash == self.blocks[i - 1].hash() for i in range(1, len(self.blocks)))


chain = Chain()
chain.append(["coinbase -> Alice: 50"])
chain.append(["Alice -> Bob: 10"])
chain.append(["Bob -> Carol: 3"])
print("改ざん前:", chain.is_valid())

chain.blocks[1].transactions[0] = "Alice -> Bob: 1000"
print("改ざん後:", chain.is_valid())

改ざん前: True
改ざん後: False

マークルツリー¶

ブロック内の全トランザクションの要約は マークルツリー（Merkle tree） で作る。トランザクションのハッシュ値（txid）を葉として、隣り合う2つを連結してハッシュ化する操作をトーナメント表のように繰り返し、最後に残った1つの値を マークルルート（Merkle root） と呼ぶ。

ブロックヘッダーにはマークルルート（32バイト）だけを入れる。トランザクションが1件でも100万件でもサイズは同じ
どれか1つのトランザクションの内容や順番が変わると、マークルルートがまったく別の値になる
Bitcoinでは、葉が奇数個のときは最後のハッシュ値を複製してペアを作る

マークルプルーフ¶

単にトランザクションを全部連結してハッシュ化しても要約にはなる。わざわざ木構造にするのは、ある1件のトランザクションがブロックに含まれていることを、少ないデータで証明できるからである。

トランザクション $K$ がブロックに含まれることを示すには、 $K$ から根までの経路上にある「兄弟ノード」のハッシュ値だけがあればよい。これを マークルプルーフ（Merkle proof, inclusion proof） と呼ぶ。

$N$ 個の葉に対してプルーフのサイズは $O(\log_2 N)$ で、全件連結方式の $O(N)$ に比べて非常に小さい。一般に $k$ 分木では必要なハッシュ数は $(k-1)\log_k N$ で、 $k=2$ のとき最小になる。

この性質は、ブロックヘッダーだけを持つ軽量ノード（SPVノード、ライトクライアント）が、フルノードから受け取ったプルーフで自分宛ての取引を検証するのに使われる。

def h(data: bytes) -> bytes:
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()


def merkle_levels(leaves: list[bytes]) -> list[list[bytes]]:
    """葉から根までの各階層のハッシュ値を返す"""
    levels = [leaves]
    while len(levels[-1]) > 1:
        cur = levels[-1]
        if len(cur) % 2 == 1:
            cur = cur + [cur[-1]]  # 奇数個なら末尾を複製
        levels.append([h(cur[i] + cur[i + 1]) for i in range(0, len(cur), 2)])
    return levels


def merkle_proof(levels: list[list[bytes]], index: int) -> list[tuple[bytes, str]]:
    """index番目の葉の包含証明（兄弟ハッシュと、それが左右どちらにあるか）"""
    proof = []
    for level in levels[:-1]:
        if len(level) % 2 == 1:
            level = level + [level[-1]]
        sibling = index ^ 1
        proof.append((level[sibling], "left" if sibling < index else "right"))
        index //= 2
    return proof


def verify(leaf: bytes, proof: list[tuple[bytes, str]], root: bytes) -> bool:
    cur = leaf
    for sibling, side in proof:
        cur = h(sibling + cur) if side == "left" else h(cur + sibling)
    return cur == root


txs = [f"tx{i}".encode() for i in range(16)]
leaves = [h(tx) for tx in txs]
levels = merkle_levels(leaves)
root = levels[-1][0]

proof = merkle_proof(levels, 10)
print("マークルルート:", root.hex())
print("プルーフに必要なハッシュ数:", len(proof), "（葉の数:", len(leaves), "）")
print("tx10 の検証:", verify(leaves[10], proof, root))
print("偽の tx の検証:", verify(h(b"fake"), proof, root))

マークルルート: 552d2da993a20ea1a79aac3570a81c10fdb40173bd9d6c0dc9e1b5ead0885d80
プルーフに必要なハッシュ数: 4 （葉の数: 16 ）
tx10 の検証: True
偽の tx の検証: False

ブロックの構造（Bitcoin）¶

Bitcoinのブロックは、80バイトのブロックヘッダーとトランザクションのリストからなる。

サイズ	フィールド	内容
4 bytes	version	プロトコルのバージョン
32 bytes	previous block hash	前ブロックのブロックハッシュ
32 bytes	merkle root	ブロック内の全トランザクションのマークルルート
4 bytes	timestamp	ブロックの生成時刻（Unix時間）
4 bytes	difficulty target (bits)	PoWの難易度
4 bytes	nonce	マイニングで探索する値

ブロックハッシュはこのヘッダーのダブルSHA-256。ヘッダーにマークルルートが含まれるので、トランザクションを1つでも改ざんすると

txidが変わる → マークルルートが変わる → ブロックハッシュが変わる → 次のブロックの prev hash と不一致

となり、すぐに検出できる。

台帳のモデル：UTXOとアカウント¶

ブロックに記録する「取引」の表現方法には大きく2つの流儀がある。

UTXOモデル¶

Bitcoinが採用する UTXO（Unspent Transaction Output）モデル では、残高という概念を直接持たない。各トランザクションは

入力（input）：過去のトランザクションの未使用出力（UTXO）を参照して消費する
出力（output）：金額と、それを使うための条件（宛先）を指定して新しいUTXOを作る

からなる。あるアドレスの残高は、そのアドレス宛のUTXOの合計として計算される。現金の紙幣・硬貨に近い。

UTXOは分割して使えないため、一部だけ支払いたいときは自分宛の「おつり」出力を作る。入力の合計と出力の合計の差額が手数料になる。

アカウントモデル¶

Ethereumが採用する アカウントモデル では、各アカウントの残高や状態（state）をグローバルな状態として管理し、トランザクションはその状態を遷移させる命令として扱う。銀行口座に近い。

観点	UTXOモデル	アカウントモデル
管理するもの	取引の流れ（フロー）のみ	各アカウントの状態（ストック）
残高	UTXOを合計して算出	状態として直接保持
並列処理	異なるUTXOを使う取引は独立に検証しやすい	同じアカウントに触れる取引は逐次処理が必要
プライバシー	取引ごとにアドレスを変えやすい	同じアドレスを使い続けがち
プログラマビリティ	限定的（使用条件のスクリプトのみ）	汎用的なプログラム（スマートコントラクト）と相性がよい
二重支払い防止	UTXOが未使用かを確認	アカウントごとのnonce（取引の通し番号）で確認
採用例	Bitcoin, Cardano（拡張UTXO）	Ethereum, Solana