CT Merkle ツリー

RFC 6962（Certificate Transparency）を参照した CT スタイルの追記専用 Merkle ツリーの設計を解説します。

リーフハッシュ（0x00 プレフィックス）とノードハッシュ（0x01 プレフィックス）の区別により、second-preimage 攻撃を防止します。包含証明と整合性証明により、投票の記録と掲示板の追記専用性を検証可能にします。

概要

本システムの掲示板（Bulletin Board）は、Certificate Transparency (CT) で実績のある追記専用ログの設計を投票に応用しています。各投票コミットメントは Merkle ツリーのリーフとして追記され、一度記録されたエントリは削除も改変もできません。

graph TD
  subgraph "8 リーフのツリー（N=8）"
    R["ルート<br/>SHA-256(0x01 || L || R)"]
    N1["ノード"]
    N2["ノード"]
    N3["ノード"]
    N4["ノード"]
    N5["ノード"]
    N6["ノード"]
    L0["リーフ 0"]
    L1["リーフ 1"]
    L2["リーフ 2"]
    L3["リーフ 3"]
    L4["リーフ 4"]
    L5["リーフ 5"]
    L6["リーフ 6"]
    L7["リーフ 7"]

    R --> N1
    R --> N2
    N1 --> N3
    N1 --> N4
    N2 --> N5
    N2 --> N6
    N3 --> L0
    N3 --> L1
    N4 --> L2
    N4 --> L3
    N5 --> L4
    N5 --> L5
    N6 --> L6
    N6 --> L7
  end

RFC 6962 参照ハッシュ規則

RFC 6962 Section 2 に従い、リーフノードと内部ノードに異なるドメイン分離プレフィックスを適用します。

リーフハッシュ

LeafHash = SHA-256(0x00 || "stark-ballot:leaf|v1" || leaf_data)

内部ノードハッシュ

NodeHash = SHA-256(0x01 || left_hash || right_hash)

ドメイン分離の安全性

0x00（リーフ）と 0x01（内部ノード）のプレフィックス区別は、second-preimage 攻撃を防止するために不可欠です。この区別がなければ、攻撃者はリーフノードを内部ノードとして解釈させる（またはその逆の）偽造データを構築できる可能性があります。

使用タグ "stark-ballot:leaf|v1" は、他システムのリーフハッシュとの偶発的な衝突を防止する追加の防御層です。

Merkle Tree Hash（MTH）アルゴリズム

RFC 6962 で定義される MTH アルゴリズムは、任意のサイズのデータセットからルートハッシュを計算します。

アルゴリズムの定義

1. 空のツリー: MTH({}) = SHA-256() （空入力のハッシュ）
2. 単一リーフ: MTH({d₀}) = LeafHash(d₀)
3. 複数リーフ: サイズ n のツリーに対し、k を n 未満の最大の 2 のべき乗とする

MTH({d₀, ..., dₙ₋₁}) = SHA-256(0x01 || MTH({d₀, ..., dₖ₋₁}) || MTH({dₖ, ..., dₙ₋₁}))

非 2 のべき乗サイズへの対応

ツリーサイズが 2 のべき乗でない場合（例: 5, 6, 7 リーフ）、MTH アルゴリズムは「n 未満の最大の 2 のべき乗」で分割を行います。これにより、左部分木は常に完全二分木（2 のべき乗サイズ）となり、右部分木にのみ不完全さが集中します。

graph TD
  subgraph "5 リーフのツリー（k=4 で分割）"
    Root["ルート"]
    Left["左部分木<br/>MTH(d₀..d₃)<br/>完全二分木"]
    Right["右部分木<br/>MTH(d₄)<br/>単一リーフ"]
    Root --> Left
    Root --> Right
  end

本システムでは固定 64 票（2⁶）を扱うため、最終的なツリーは完全二分木となります。ただし、投票が順次追加される過程では非 2 のべき乗サイズのツリーが出現するため、MTH アルゴリズムの一般的な対応が必要です。

掲示板のリーフデータ形式

掲示板に追記される各投票のリーフデータは、コミットメントの正規化された 16 進数表現（0x なし、小文字、64 文字）を 32 バイトにデコードした生バイト列です。

leaf_data = hex_decode(normalized_commitment_hex) (32 バイト)

掲示板は以下の不変条件を維持します:

• 単調増加インデックス: 各投票に 0 から始まる連番が割り当てられる
• 重複排除: 同一の投票 ID やコミットメントの二重追記を拒否する
• ルート履歴: 各追記時点のルートハッシュをタイムスタンプとともに保存する

包含証明（Inclusion Proof）

包含証明は、特定のコミットメントがツリーの特定位置に含まれていることを、ルートハッシュに対して暗号学的に証明するものです。

構造

包含証明は以下の要素で構成されます:

PATH アルゴリズム

RFC 6962 の PATH 関数に従い、監査パスを再帰的に生成します。

1. ツリーをサイズ k（n 未満の最大の 2 のべき乗）で左右に分割
2. 対象リーフが左部分木にある場合（index < k）:
   • 左部分木の PATH を再帰計算
   • 右部分木のハッシュを監査パスに追加
3. 対象リーフが右部分木にある場合（index >= k）:
   • 右部分木の PATH を再帰計算（インデックスを index - k に調整）
   • 左部分木のハッシュを監査パスに追加

検証手順

検証者は以下の手順で包含を確認します:

1. コミットメントのリーフハッシュを計算: LeafHash(commitment)
2. PATH アルゴリズムと同じ木構造に従い、監査パスのノードを順に結合
3. 計算されたルートが期待するルートハッシュと一致するか確認

監査パスのサイズは O(log n) であり、64 票のツリーでは最大 6 ノードです。

graph TD
  subgraph "インデックス 5 の包含証明"
    Root["ルート ✓"]
    N1["H(N3, N4)"]
    N2["H(N5, N6) ← 計算対象"]
    N3["H(L0,L1)<br/>監査パス"]
    N4["H(L2,L3)<br/>監査パス"]
    N5["H(L4,L5) ← 計算対象"]
    N6["H(L6,L7)<br/>監査パス"]
    L4["L4<br/>監査パス"]
    L5["L5 ← 対象リーフ"]

    Root --> N1
    Root --> N2
    N1 --> N3
    N1 --> N4
    N2 --> N5
    N2 --> N6
    N5 --> L4
    N5 --> L5
  end

  style L5 fill:#4CAF50,color:#fff
  style N3 fill:#2196F3,color:#fff
  style N4 fill:#2196F3,color:#fff
  style N6 fill:#2196F3,color:#fff
  style L4 fill:#2196F3,color:#fff

整合性証明（Consistency Proof）

整合性証明は、古いツリー状態（サイズ m）が新しいツリー状態（サイズ n）の前方互換的なプレフィックスであること、つまり追記専用性を暗号学的に証明するものです。

構造

SUBPROOF アルゴリズム

RFC 6962 の SUBPROOF 関数に基づき、整合性証明を再帰的に生成します。

1. m = n かつ古いツリーが完全部分木: 空の証明を返す
2. m = n かつ完全部分木でない: 部分木のルートハッシュを返す
3. k を n 未満の最大の 2 のべき乗とし:
   • m <= k の場合: 左部分木の SUBPROOF + 右部分木のハッシュ
   • m > k の場合: 右部分木の SUBPROOF + 左部分木のハッシュ

検証の意味

整合性証明の検証が成功することは、以下を意味します:

• 古いツリーのすべてのリーフが、新しいツリーにも同じ位置・同じ値で存在する
• 新しいツリーは古いツリーの末尾にリーフを追加しただけで構成されている
• 古いツリーのルートハッシュと新しいツリーのルートハッシュの両方が、提供された証明ノードから独立に再構成できる

これにより、サーバーが過去に記録した投票を密かに削除したり順序を変更したりする攻撃を検出できます。

検証パイプラインにおける役割

CT Merkle ツリーは、4 段階検証モデルの主に 2 段階で使用されます。

zkVM ゲストプログラムも同じハッシュ規則（0x00 リーフ、0x01 ノード、使用タグ）を用いて包含証明を検証します。ハッシュ規則の不一致は、ゲスト内での検証失敗として即座に検出されます。

RFC 6962 参照範囲

本システムはリーフハッシュに使用タグ "stark-ballot:leaf|v1" を追加しています。これは RFC 6962 の拡張であり、他システムとのリーフハッシュ衝突を防止するための措置です。標準の CT 実装との直接的な相互運用は意図していません。