ビットマップ Merkle

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

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

概要

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

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

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 / seenBitmapRoot"]
  end

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

ビットマップの構造

ビットマップの定義

ビットマップは、ツリーサイズ（投票数）と同じ長さのブール配列です。現行実装では同じエンコーディング規則を持つ 2 種類のビットマップを扱います。

includedBitmap[i] = true: インデックス i の投票が正常に検証され、集計に含まれた
includedBitmap[i] = false: インデックス i の投票が除外された
seenBitmap[i] = true: インデックス i の投票が prover に提示された
seenBitmap[i] = false: インデックス i の投票が prover に提示されなかった

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

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

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>&kind=included|seen のレスポンスは、以下の要素で構成されます:

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

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

kind は省略可能で、既定値は included です。

kind=included: includedBitmapRoot に対する証明を返す
kind=seen: seenBitmapRoot に対する証明を返す

この endpoint はセッション ID と capability token によるセッションスコープ認証を前提とした証明材料 API であり、公開 API ではありません。

ビット抽出

投票者は受け取ったチャンクから、自分が指定した 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

kind=included で included = true なら、自分の投票がカウントされたことを意味します。kind=seen で included = true なら、自分の投票が prover に提示されたことを意味します。

検証手順

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

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

zkVM ゲストとの連携

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

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

各投票に対してコミットメントの再計算と包含証明の検証を実施
prover に提示された投票インデックスを seenBitmap に記録
検証に成功して集計対象になった投票インデックスを includedBitmap に記録
それぞれのビットマップを LSB-first でパッキングし、32 バイトチャンクに分割
CT スタイルのハッシュ規則で Merkle ルートを計算
seenBitmapRoot と includedBitmapRoot をジャーナルにコミット

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

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

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

現行実装では、sync finalize でも async finalize でも、zkVM 実行から includedBitmap が得られた場合にのみ証明用データを保存します。seenBitmap と seenBitmapRoot が得られた場合は、それも private artifact として保存します。validVotes から簡易ビットマップを推定する fallback は現在の実装にはありません。

安全性ゲート

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

そのため、zkVM 出力に基づく bitmap データが存在しない場合や、保存済みデータの root がジャーナルと一致しない場合は、証明を提供せず counted_my_vote_included は not_run 相当になります。

さらに現行実装では、counted_my_vote_included の評価には信頼できる voteReceipt.bulletinIndex が必要です。この値は、store から cast-time 証跡（voteReceipt / userVote.proof）を再構成できた場合にのみ得られます。bitmap データが保持されていても cast-time 証跡を復元できなければ bitmap proof は実行されず、counted_my_vote_included は not_run（証拠不足による fail-closed）となります。

async finalize 経路でも、prover 出力の *-bitmap.json と *-seen-bitmap.json は private な included-bitmap.json / seen-bitmap.json として保持されます。これらは public bundle.zip には含めず、必要に応じて S3 上の sibling object から復元されます。

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

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

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

seenBitmapRoot が利用可能な場合は、このチェックが「prover に提示されたが無効化された」と「そもそも提示されなかった」も区別して説明します。

各チェックの判定ロジックはチェック一覧 > Counted-as-Recorded を参照してください。

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

STARK Ballot Simulator Public Docs