ビットマップ Merkle

投票カウント証明のためのビットマップ Merkle ツリーの設計を解説します。

zkVM ゲスト内で計算されるビットマップにより、各投票インデックスが集計に含まれたかどうかを個別に検証可能にします。Merkle 証明により、自分の投票が含まれていることをサーバーを信頼せずに確認できます。

概要

Counted-as-Recorded 段階の検証では、「全体として正しい集計が行われた」ことは STARK 証明で保証されますが、**個々の投票者にとって「自分の票が集計に含まれたか」**を直接確認する手段が別途必要です。

ビットマップ Merkle ツリーは、この「個別のカウント証明」を提供します。zkVM ゲストが検証した各投票のカウント状況をビットマップとしてエンコードし、そのMerkle ルート（includedBitmapRoot）をジャーナルにコミットします。投票者は自分のインデックスに対応するビットの Merkle 証明を取得し、「自分の票がカウントされた」ことを独立に検証できます。

flowchart TD
  subgraph "zkVM ゲスト内"
    BM["ビットマップ<br/>[true, true, false, true, ...]"] --> PK[ビットパッキング<br/>LSB-first]
    PK --> CH[32 バイトチャンク分割]
    CH --> LH["リーフハッシュ<br/>SHA-256(0x00 || tag || chunk)"]
    LH --> MT[Merkle ツリー構築]
    MT --> ROOT[includedBitmapRoot]
  end

  ROOT --> JNL[ジャーナルにコミット]

ビットマップの構造

ビットマップの定義

ビットマップは、ツリーサイズ（投票数）と同じ長さのブール配列です。

bitmap[i] = true: インデックス i の投票が正常に検証され、集計に含まれた
bitmap[i] = false: インデックス i の投票が除外された（無効、欠損、または検証失敗）

本 PoC では 64 票を扱うため、ビットマップは 64 ビット（= 8 バイト）です。

LSB-first ビットパッキング

ブール配列は LSB-first（Least Significant Bit first）方式でバイト列にパッキングされます。

ビット配列: [b₀, b₁, b₂, b₃, b₄, b₅, b₆, b₇, b₈, ...]

バイト 0 = b₀ | (b₁ << 1) | (b₂ << 2) | ... | (b₇ << 7)
バイト 1 = b₈ | (b₉ << 1) | ...

ビット位置	バイトインデックス	バイト内ビット位置
0	0	0 (LSB)
1	0	1
7	0	7 (MSB)
8	1	0 (LSB)
63	7	7 (MSB)

64 ビットのビットマップは 8 バイトにパッキングされます。

32 バイトチャンク分割

パッキングされたバイト列は 32 バイト（256 ビット）単位のチャンクに分割されます。各チャンクが Merkle ツリーの 1 つのリーフとなります。

1 チャンク = 32 バイト = 256 ビット分の投票カウント状態
最後のチャンクが 32 バイトに満たない場合はゼロパディング

本 PoC の 64 票は 8 バイトであるため、1 つのチャンク（24 バイトのゼロパディング付き）に収まります。

Merkle ツリーの構築

ハッシュ規則

ビットマップ Merkle ツリーは、CT Merkle ツリーと同一のハッシュ規則を使用します。

リーフハッシュ:

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

内部ノードハッシュ:

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

ドメイン分離プレフィックス（0x00 / 0x01）と使用タグ（"stark-ballot:leaf|v1"）は、CT Merkle ツリーの章で解説したものと同一です。

ツリー構築アルゴリズム

各 32 バイトチャンクにリーフハッシュを適用
ボトムアップでペアを結合し、内部ノードハッシュを計算
奇数ノードがある場合は、そのまま次のレベルに昇格（ハッシュなし）
ルートに到達するまで繰り返す

graph TD
  subgraph "3 チャンクの場合"
    R["ルート<br/>SHA-256(0x01 || N1 || C2)"]
    N1["ノード<br/>SHA-256(0x01 || C0 || C1)"]
    C2["リーフ 2<br/>SHA-256(0x00 || tag || chunk₂)"]
    C0["リーフ 0<br/>SHA-256(0x00 || tag || chunk₀)"]
    C1["リーフ 1<br/>SHA-256(0x00 || tag || chunk₁)"]

    R --> N1
    R --> C2
    N1 --> C0
    N1 --> C1
  end

Merkle 証明の生成と検証

証明の構造

GET /api/bitmap-proof?i=<bitIndex> の公開レスポンスは、以下の要素で構成されます:

フィールド	説明
leafChunk	対象ビットを含む 32 バイトチャンク（16 進数）
auditPath	ルートまでの兄弟ハッシュ配列（各要素にハッシュ値と位置）

leafIndex（floor(bitIndex / 256)）と bitOffset（bitIndex mod 256）は、クライアント側で bitIndex クエリから導出します。サーバーは返しません。

ビット抽出

投票者は受け取ったチャンクから、自分が指定した bitIndex のビットを以下の手順で抽出します:

bit_offset  = bit_index mod 256
byte_index  = bit_offset / 8    (整数除算)
bit_in_byte = bit_offset mod 8

included = (chunk[byte_index] AND (1 << bit_in_byte)) != 0

included = true であれば、自分の投票がカウントされたことを意味します。

検証手順

チャンクからビット値を抽出し、自分の投票がカウントされたか確認
チャンクのリーフハッシュを計算: SHA-256(0x00 || "stark-ballot:leaf|v1" || chunk)
監査パスに沿ってルートまで再計算:
- 兄弟の位置が left → SHA-256(0x01 || sibling || current)
- 兄弟の位置が right → SHA-256(0x01 || current || sibling)
計算されたルートがジャーナルの includedBitmapRoot と一致するか確認

flowchart TD
  CK[チャンク受信] --> EX[ビット抽出<br/>included = true/false]
  CK --> LH["リーフハッシュ計算"]
  LH --> AP[監査パスに沿って<br/>ルートを再計算]
  AP --> CMP{計算ルート =<br/>includedBitmapRoot ?}
  CMP -->|一致| V[証明有効]
  CMP -->|不一致| IV[証明無効]

zkVM ゲストとの連携

ビットマップルートは zkVM ゲストプログラム内で計算され、ジャーナルの includedBitmapRoot フィールドにコミットされます。

ゲストプログラムは以下の手順を実行します:

各投票に対してコミットメントの再計算と包含証明の検証を実施
検証に成功した投票のインデックスに対応するビットを true に設定
ビットマップを LSB-first でパッキングし、32 バイトチャンクに分割
CT スタイルのハッシュ規則で Merkle ルートを計算
ルートをジャーナルにコミット

この計算はゲスト内で行われるため、STARK 証明がビットマップの正しさも保証します。サーバーが事後的にビットマップを改ざんしても、ジャーナルのルート値と一致しなくなるため検出されます。

サーバーのビットマップデータ管理

サーバーはビットマップ Merkle 証明を提供するために、最終化時に includedBitmap データを保持します。

現行 PoC 実装では、USE_MOCK_ZKVM=true かつ mock executor が実ビットマップを保持している場合に限り、その実ビットマップを使用します。これが利用できない場合は検証統計（validVotes など）から簡易ビットマップを再構成します。その後、どの経路で得たデータでもルート照合を行い、整合性を確認します。

安全性ゲート

サーバーが保持するビットマップデータから計算したルートと、ジャーナルの includedBitmapRoot が一致しない場合、ビットマップ証明の提供は無効化されます。これにより、サーバーが不正なビットマップデータを使って偽の証明を生成することを防止します。

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

ビットマップ Merkle 証明は、Counted-as-Recorded 段階のチェックとして使用されます。

チェック ID	検証内容
`counted_my_vote_included`	ビットマップ Merkle 証明により、自分の投票インデックスがカウントされたことを確認する

チャンクサイズの縮小（より多くのリーフ、より深いツリー）
ゼロ知識証明を用いたビット開示の最小化
投票者の明示的な同意に基づく開示

STARK Ballot Simulator Public Docs