封印入札オークション — 設計空間

Sealed-Bid Auction Design Space | 1961–2025 | 7 Papers

「入札額を互いに秘匿したまま落札者と価格を決定する」プロトコル群。MEV対策・プライバシーDEXの注文マッチングと数学的に同一の問題構造を持つ。

歴史タイムライン（1961–2025）

封印入札オークション理論・実装の系譜
1961 Vickrey 理論 1993–96 最初の 暗号実装 2009 MPC 本番稼働 2014 Bitcoin +MPC 2020 SEAL 2022 FAST 2023 Riggs 2024 CryptoBazaar 2025 Jigsaw ★ 世界初MPC本番 構造的abort不可 二重プライバシー

3つの中心的設計軸

軸 1: 競売人の扱い
信頼必要 → 中間 → 完全不要

従来型オークションは競売人が全bid情報を見る。MPCとZKで段階的に信頼を排除してきた歴史。

軸 2: 公平性 (Fairness)
なし (abort可) → → 強制開示

負けた参加者が結果を見てからプロトコルを中断できる「戦略的abort」をどう防ぐかが中核問題。

軸 3: 価格形式
第1価格 → 第2価格 → (p+1)価格一般形

Vickrey型(第2価格)は正直入札が支配戦略。実用はfirst-priceとのトレードオフが続く。

Vickrey (1961) — 理論的基盤

Second-Price Auction Theory
William Vickrey, 1961 | ノーベル経済学賞 (1996)
主定理: 第2価格オークションでは、自分の真の評価額をそのまま入札することが支配戦略（他の参加者の行動によらず最適）
  • 落札者 = 最高入札者、支払い = 第2位の入札額
  • 入札者には「真の評価額より高く入札する」インセンティブも「低く入札する」インセンティブもない
  • 数学的証明: 真の評価額 v、入札 b、第2位入札 b₂ とすると、b=v が b≠v を支配
  • 社会的余剰最大化: 最も高く評価する人が落札するため効率的
課題: 理論は正直入札を保証するが、「競売人が本当に第2価格を使っているか」は外部から検証できない。暗号実装の動機はここ。

問題の難しさ: なぜ単純な暗号化では不十分か

基本的な難しさ

  • 全参加者がbidをコミットし、開示フェーズで一斉公開
  • 負けた人は開示を「しない」ことでabort可能
  • Fairnessを達成するには経済的罰則か強制開示機構が必要

理想的なプロトコルの要件

  • Correctness: 正しい落札者・価格を決定
  • Bid Privacy: 非落札者の入札額は漏れない
  • Fairness: 誰もプロトコルを戦略的に中断できない
  • Verifiability: 結果が正しいことを誰でも検証可能

MPC Goes Live — FC 2009

世界初の本番MPC: デンマーク砂糖大根オークション
Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielsen, Jakob Pagter, Michael Schwartzbach, Tomas Toft | FC 2009
世界初MPC本番
1,228農家
2008年実施
歴史的意義: 学術上の概念だったMPCが初めて実運用環境で使われた事例。ゼロ知識のまま市場価格を発見。

背景・文脈

  • デンマークの砂糖大根農家1,228名が参加
  • 従来: 中央集権的競売人がすべての入札を閲覧
  • 農家は競合他社に入札額を知られたくない
  • 開催: Aarhus大学 + GASA (Danish Sugar Factory)

技術仕様

  • Shamir (2,3)-Secret Sharing
  • 3ノード構成 → 2ノードが正直なら安全
  • MPC over Commitments
  • 取引量・参加者情報を一切漏洩せずに価格発見

3ノードMPCアーキテクチャ

農家の入札がSecretShareで3ノードに分散され、MPCで市場価格のみが出力される
農家A (bid: 45) 農家B (bid: 52) 農家C (bid: 38) ...1,228 農家... MPC Node 1 (Aarhus Univ.) MPC Node 2 (GASA) MPC Node 3 (独立機関) share₁ share₂ share₃ Secure Computation 市場価格のみ 個別入札額: 非開示 2ノードが正直なら安全 | Shamir (2,3)-Secret Sharing

MPC on Bitcoin — S&P 2014

Bitcoin Script + 経済罰則でMPC Fairnessを実現
Iddo Bentov, Ranjit Kumaresan | IEEE S&P 2014
S&P 2014
Collateral設計の確立

核心的アイデア

  • Bitcoin Scriptにタイムロック機能を組み込み
  • 参加者がプロトコルを中断→deposit没収
  • Collateral: 参加前にBTCを担保として預ける
  • 不正検出時: 被害者がcollateralを受け取る

設計パターン

  • Penalty Deposit: プロトコル開始前に供託
  • Timed Commitment: 時間が来れば強制開示
  • Lottery Protocol: 全員が入力するとincentive
  • Forfeit: abort = depositを失う
歴史的位置付け: スマートコントラクトのcollateral/forfeit設計の原型。SEAL・FAST・Riggsへの直接的先祖。「経済的罰則でMPC fairnessを代替する」アプローチを確立。
限界: Bitcoin Script自体の表現力制限。より複雑な計算はEVMが必要。また、collateral = 参加コストが高い場合、小規模入札者が参加できなくなる問題。

SEAL — TIFS 2020

Smart Contract Auctioneer-Free Sealed-Bid Auction
Samiran Bag, Feng Hao, Siamak F. Shahandashti, Indranil Ghosh Ray | IEEE TIFS 2020
競売人不要
O(c) 計算量
第1価格・Vickrey両対応

Bit-by-Bit ZK コミットメント

  • 各入札者がbidをビット分解してZKでコミット
  • 例: bid=5 → bits=[1,0,1,0,...] をそれぞれZKP付きでコミット
  • 全参加者のビットのXORで最大入札者を特定
  • 公開ブロードキャストのみ → 第三者不要
  • c = 価格レンジのビット数 → O(c)のZKP

動作フロー

  • Phase 1: 各入札者がビットコミットをブロードキャスト
  • Phase 2: 全員がZKPを検証
  • Phase 3: 開示 → XOR演算で勝者決定
  • スマートコントラクトがルール執行
  • 完全公開検証可能 (verifiable)

Bit-by-Bit コミットメントの仕組み

5入札者 × 3ビット: XORで最大入札者を特定する
入札者 Bit₂ (4) Bit₁ (2) Bit₀ (1) bid値 Alice 1 0 1 5 Bob 0 1 1 3 Carol 1 1 0 6 ★ XOR 0 0 1 XOR=0のビット位置は「全員が同じ値」→ 最上位1のビットから勝者を特定 Bit₂=1を持つ = Alice(5), Carol(6) → さらに下位ビットで Carol(6)が最高

SEALの欠点: Fairness保証なし

結果が最初に判明した参加者（勝者）がその時点でabort可能。「勝ったが支払いたくない」攻撃者は意図的にプロトコルを中断し、入札情報を晒さずに終わらせることができる。

FAST — ACNS 2022

Fairness with Accountable Secret Transfer
Samiran Bag, Feng Hao, Siamak F. Shahandashti, Jie Xu | ACNS 2022
Fairness達成
SEALの拡張
Secret Deposit
核心的改善: SEALにSecret Depositを追加してFairnessを達成。abortすると経済的罰則を受ける。

なぜ「Secret」Depositが必要か

Public Depositの問題
  • deposit額をオンチェーンで公開する場合
  • deposit = bid額に連動させると bid額が露呈
  • 全員が同額depositすると差別化不可
  • deposit金額からbidを推測される
Secret Depositの解決
  • depositをbidに依存させたまま暗号化
  • 通常時: depositの中身は非公開
  • 詐欺検出時のみ: depositを強制公開
  • cheating verifiable = 公開検証可能

動作フロー

  • 入力フェーズ: bid + secret depositを同時にコミット（depositはbidと暗号的にバインド）
  • 計算フェーズ: SEALのXORプロトコルで勝者決定
  • 通常終了: 勝者が支払い → depositを返却
  • abort時: abort者のdepositが公開され、罰則として没収
  • 公開検証: 誰でも不正を検証可能
オンチェーン効率: 通常時はdepositの詳細をオンチェーンに保存不要。詐欺発生時のみ追加データをpublishする設計でガスコスト最小化。

Riggs — 2023

Non-Malleable Timed Commitment + Shared Collateral
Zachary Miti, Phil Daian, Ari Juels, Ben Dautrich | 2023
構造的abort不可
Shared Collateral Pool
Range Proof

Non-Malleable Timed Commitment

鍵アイデア: コミットメントに時間制限を設定。時間が経過すると、コミッターが開示しなくても誰でも強制的に開示できる。これにより戦略的abortが構造的に不可能になる。
  • 入力フェーズ: bidをTimed Commitmentでコミット
  • 待機フェーズ: タイムロック期間が経過
  • 開示フェーズ: 自発的に開示しなくても、タイムロック解除後に誰でも強制解読可能
  • Non-Malleable: コミットメントを後から改ざん不可能

Timed Commitmentの動作フロー

Non-Malleable Timed Commitment: 構造的にabort不可能な仕組み
コミット bid → TC(bid, T) オンチェーンに提出 待機 (T 秒) タイムロック進行 abort試みても... 強制開示可能 コミッター以外でも タイムロック解除→開示 勝者決定 最高bid = 落札 公開・検証済み ✗ abort → 無意味 (誰でも強制開示可能) Non-Malleableにより改ざん不可 | タイムロック後は第三者が開示代行
Range Proof: 支払い能力の秘密証明

従来: 高bid → 高額支払い能力を証明するには bid額を公開する必要がある

Riggsの解決: Range Proof (例: Bulletproofs) を使い「私の残高はbid額以上」をbid額を秘匿したまま証明
bid ∈ [0, balance] を 0-knowledge で証明 → bid額非公開のまま → 支払い能力は保証済み
Shared Collateral Pool

問題: 複数オークションに参加するたびにcollateralを個別にロック → 資本効率が悪い

解決: 1つのcollateral poolを複数オークションで共有。「どれか1つで不正をしない」ならpool全体を担保として有効に使える

CryptoBazaar — 2024

Unary Encoded Bids + Logical-OR分散計算
Zhiyi Ke, Deepak Maram, Jonathan Katz et al. | 2024
128入札者対応
<0.5秒・32KB
Sequential対応

Unary Encoded Bids の仕組み

価格レンジ: [1, 2, 3, 4, 5, 6, 7, 8 ] bid = 3 → [0, 0, 0, 1, 0, 0, 0, 0 ] bid = 4 → [0, 0, 0, 0, 1, 0, 0, 0 ] bid = 7 → [0, 0, 0, 0, 0, 0, 0, 1 ] Logical-OR: [0, 0, 0, 1, 1, 0, 0, 1 ] ↑ 最大インデックス = 7 → 落札者 = bid=7の入札者

主要特性

  • 落札者以外の入札額は一切開示しない
  • Logical-ORは各入札者が分散協調で計算
  • 128入札者 × 1024価格レンジ → 0.5秒以下
  • 各入札者のデータ量: 32KB
  • 信頼不要な1者が調整者として機能

対応オークション形式

  • First-Price Sealed-Bid
  • Second-Price (Vickrey)
  • Sequential First-Price: NFT連続競売等
  • 複数商品の同時オークション

Unary Encoding + Logical-OR ビジュアル

4入札者: Logical-ORで最高入札を特定
入札者 p=1 p=2 p=3 p=4 p=5 p=6 p=7 p=8 bid Alice 0 0 1 0 0 0 0 0 3 Bob 0 0 0 0 1 0 0 0 5 Carol 0 0 0 0 0 0 1 0 7 ★ Dave 0 0 0 1 0 0 0 0 4 OR 0 0 1 1 1 0 1 0 → p=7

Jigsaw — 2025

Collaborative zkSNARK による二重プライバシー
Matteo Campanelli, Mario Ciampi, Zachary Schul-Gober, Victor Shoup | 2025
二重プライバシー
colSNARK 40-50x高速化
ZEXE拡張

問題の明確化: 従来のプライバシーDEXの盲点

// 従来のプライバシーDEXアーキテクチャ ユーザー → [暗号化された注文] ↓ オフチェーンマッチングエンジン ← ここが全データを「平文で」見る ↓ ZK証明でオンチェーンに提出 オンチェーン決済 (オンチェーン観察者からは秘匿) // 結果: オンチェーンからは秘匿されているが... マッチングエンジン自体は注文サイズ・価格・身元を完全に把握 // → 内部不正・データ漏洩・規制当局への開示リスクが残る

Jigsawの解決: 二重プライバシー

// Jigsawアーキテクチャ ユーザー → [暗号化された注文] ↓ 分散配布 【分散サーバー群 S₁, S₂, ..., Sₙ】 各サーバーは秘密シェアのみ保持 → 単独では注文情報を知ることができない ↓ Collaborative zkSNARK (colSNARK) サーバー群が協調してZK証明を生成 (データも身元も不明のまま) ↓ 証明をオンチェーンに提出 オンチェーン決済 (オンチェーン観察者からも秘匿) // 結果: オンチェーン + オフチェーン両方からプライバシーを達成

技術的詳細: colSNARK

Collaborative zkSNARK (colSNARK)
  • ZEXEのDPC (Decentralized Private Computation)を拡張
  • 複数の証明者が協調してSNARKを生成
  • 各証明者は自分のシェアのみから部分証明を生成
  • 部分証明を集約 → 完全な証明が完成
  • 個々のサーバーはwitness (入力) を知らない
40-50x 高速化の意味
  • 従来のcolaborative ZKプロトコルに比べて証明生成が40-50倍高速
  • 通信ラウンド数の削減
  • サーバー間の証明集約を効率化
  • 実用的な応答時間に近づく
注: 40-50x改善後でも実用閾値(例: <1秒)に達するかは未検証。大規模応用では更なる最適化が必要。

二重プライバシーの意義

アーキテクチャ オンチェーン観察者 オフチェーンエンジン 分散サーバー群
通常DEX 全公開 全公開 N/A
従来プライバシーDEX 秘匿 全公開 N/A
Jigsaw 秘匿 存在しない シェアのみ

MEVとの接点

Jigsawの二重プライバシーはMEV文脈でも重要。従来、プライバシーDEXでも「オフチェーンのシーケンサー/マッチャーはorderflow全体を見ているため、内部者によるfront-runが可能」という問題があった。Jigsawはcolaborative SNARKによりマッチャー自身もデータを見られないため、内部者MEVを構造的に防止できる。

Jigsawの位置付けと限界

達成したこと

  • 真の意味での「エンドツーエンド」プライバシー
  • オフチェーンマッチングエンジンへの信頼不要
  • colSNARKの40-50x高速化で実用性向上
  • ZEXE/ZEXEの理論を応用拡張

残る課題

  • 40-50x改善後でも実用閾値に達するか不明
  • サーバー群の分散配置コスト
  • 1サーバー以上の串通謀 (collusion) への耐性
  • Fairness保証の詳細は未記載

5論文横断比較表

論文 年 競売人 Fairness 計算量 入札者数 実行時間 二重プライバシー
SEAL 2020 不要 × (abort可) O(c) 任意 — ×
FAST 2022 調整者のみ ◎ (罰則) O(c)相当 任意 — ×
Riggs 2023 不要 ◎ (強制開示) — 任意 — ×
CryptoBazaar 2024 信頼不要な1者 ○ — 128 <0.5秒 ×
Jigsaw 2025 分散サーバー群 — 40-50x改善 — — ★

価格形式対応マトリックス

論文 第1価格 第2価格 (Vickrey) 複数価格・Sequential
SEAL ○ ○ ×
FAST ○ ○ ×
Riggs ○ △ ×
CryptoBazaar ○ ○ ○ (Sequential)
Jigsaw ○ △ △

封印入札 ⟷ ダークプール・DEXの同型性

観点 封印入札オークション プライバシーDEX / ダークプール
入力秘匿の対象 入札額 注文サイズ・価格・方向
出力 落札者・落札価格 マッチペア・執行価格
Fairness問題 戦略的abort (負けた入札者) 戦略的キャンセル (MEV攻撃者)
主要技術 MPC / ZK / Timed Commitment MPC / ZK / AMM拡張
信頼モデル 競売人の扱いが鍵 シーケンサーの扱いが鍵
価格形式 第1価格 / 第2価格 AMM価格 / CLOB マッチ
Collateral 罰則担保 (Riggs等) ポジション証拠金

技術系譜: 封印入札の設計進化

各論文の依存関係と設計継承
Vickrey 1961 MPC Goes Live FC 2009 MPC on Bitcoin S&P 2014 SEAL TIFS 2020 FAST ACNS 2022 Riggs 2023 CryptoBazaar 2024 Jigsaw 2025 理論的影響 直接拡張 部分的影響

未解決問題

スケーラビリティ

  • 大規模入札者 (1万人+) での実用化
  • CryptoBazaarの128人制限を超えるか
  • 価格レンジ拡大時の証明サイズ
  • Jigsaw: 40-50x改善後でも実用閾値に達するか

実装・運用面

  • クロスチェーン対応 (collateralの扱い)
  • オークション確定待ち中のMEVリスク
  • Timed Commitmentのタイムロック期間設定
  • 分散サーバー群の経済的持続性

論文一覧 (時系列)

# 論文 著者 会議/誌 年 主貢献
1 Counterspeculation, Auctions, and Competitive Sealed Tenders Vickrey J. Finance 1961 第2価格オークション理論・支配戦略
2 Secure Multiparty Computation Goes Live Bogetoft et al. FC 2009 世界初のMPC本番利用
3 How to Use Bitcoin to Design Fair Protocols Bentov, Kumaresan S&P 2014 Bitcoin+MPC Fairness・Collateral設計
4 SEAL: Sealed-Bid Auction without Auctioneers Bag, Hao et al. TIFS 2020 競売人不要・O(c)・bit-by-bit ZK
5 FAST: Fair Auctions via Secret Transactions Bag, Hao et al. ACNS 2022 Secret Deposit でFairness達成
6 Riggs: Decentralized Sealed-Bid Auctions Miti, Daian, Juels, Dautrich — 2023 Non-Malleable TC・Range Proof・Shared Collateral
7 CryptoBazaar: Sealed-Bid Auctions Ke, Maram, Katz et al. — 2024 Unary Encoding・Logical-OR・Sequential対応
8 Jigsaw: Doubly-Private Auctions Campanelli, Ciampi, Schul-Gober, Shoup — 2025 colSNARK・二重プライバシー・40-50x高速化