💻 computer science

Adversarial procurement in blockchains

本論文はブロックチェーンにおける敵対的調達のためのメカニズム設計を形式化し、最適なプロトコルはしばしばフォールバック委員会を備えた単一のランダムなワーカーを採用し、その効率性の損失はライブネス障害コストと敵対的ネットワーク割合に対して対数的にスケーリングすることを示している。

原著者： Maryam Bahrani, Michael Neuder, S. Matthew Weinberg

公開日 2026-05-08

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Maryam Bahrani, Michael Neuder, S. Matthew Weinberg

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

「Adversarial procurement in blockchains」という論文を、平易な言葉と創造的な比喩を用いて解説します。

全体像：「証明」の問題

ブロックチェーン（イーサリアンのようなもの）が、絶えず更新される必要のある巨大な共有デジタル台帳だと想像してください。将来、この台帳はあまりにも複雑になり、通常のコンピュータがすべての取引をチェックするという重労働を処理できなくなります。その代わりに、ネットワークは「証明者（プロバー）」（スーパーコンピュータ）を専門的に雇い、過酷な作業を行い、「私は計算を正しく行いました」と宣言する「証明」を生成させます。

問題はここです：これらの証明者をだまされないようにして、どうやって雇えばよいのでしょうか？

朗報： 証明をチェックするのは簡単で安価です（数学の宿題の答え合わせをするようなもの）。
悲報： 証明を作成するのは難しく、高価です（宿題を解くようなもの）。
リスク： 証明者は見知らぬ人々です。彼らは怠惰であるかもしれません、ハッカーであるかもしれません、あるいは単にコンピュータの電源を切って混乱を引き起こすかもしれません。もし誰かが証明を提供しなければ、ブロックチェーン全体が停止し（「ライブネス障害」）、それは災害です。

この論文が問うのは：一部の者がシステムを破壊しようとしているとしても、作業が完了することを保証するために、これらの見知らぬ人々に支払う最も賢く、最も安価な方法は何でしょうか？

比喩：「灯台守」のコンテスト

嵐の夜だと想像してください。船が衝突しないように、灯台を点灯させておく必要があります。あなたには100人の潜在的な灯台守（証明者）がいます。そのうち少なくとも60人は誠実ですが、最大40人は船を衝突させようとする破壊工作員（貨物を盗むため、あるいは単に悪意から）である可能性があります。

あなたは支払いシステムを設計する必要があります。ここで論文が探求する選択肢を見てみましょう。

1. 「全員に支払う」アプローチ（高価すぎる）

あなたは100人すべての守に言います。「あなたが明かりを点ければ、10ドル支払います」と。

結果： もし40人の破壊工作員が明かりを消すことに決めたとしても、60人の誠実な守が残っています。明かりは点いたままです。
欠点： あなたはたった一つの明かりが必要なのに、100人に支払ってしまいました。それは莫大な金の無駄です。

2. 「くじ引き」アプローチ（リスクが高い）

あなたは全員に言います。「1,000ドルを賞金箱に入れます。あなたが明かりを点ければ、その賞金箱全体に当選するチャンスがあります」と。

結果： 全員が働くかどうかを決定するためにコインを投げます。
欠点： もし40人の破壊工作員がこのくじ引きを見て、全員がコインを投げない（働かない）と決めた場合、問題が発生します。すると、コインを投げるのは60人の誠実な人々だけになります。「誰も表（明かりを点ける）が出ない」確率が上がります。もし誰も明かりを点けなければ、船は衝突し、あなたはすべてを失います。

3. 「指名されたリーダー＋バックアップ」アプローチ（論文の解決策）

これが著者が推奨する戦略です。これは船長と救命ボートの乗組員のように機能します。

ステップ1：船長を選ぶ。 無作為に1人を選び、「あなたは明かりを点けなければならない。点けなければ、あなたは解雇される（または罰金を科される）」と言います。
ステップ2：バックアップ乗組員を選ぶ。 小さなバックアップグループ（例えば5人）を選び、「もし船長が失敗したら、あなたたちが明かりを点けるために介入する小さなチャンスがあります。もしそうすれば、支払われます」と言います。
ステップ3：ルール。
- 船長が働けば、明かりは点いています。船長に固定額を支払います。
- 船長が破壊工作員で明かりを消した場合、バックアップが事態を救うチャンスがあります。
- もし全員が失敗した場合、莫大な罰金を科します（船が衝突したため）。

なぜこれが勝者なのか

この論文は数学を用いて、「船長＋バックアップ」システムがリスクを処理する最も効率的な方法であることを証明しています。

安価である： 全員に支払う必要はありません。主に1人に支払えばよいのです。
安全である： 「船長」が破壊工作員であっても、準備のために支払われているバックアップ乗組員が事態を救う高い確率を持っています。
不正が難しい： 破壊工作員は誰が船長になるか（無作為であるため）を容易に予測できず、船長を失敗させるように賄賂を渡そうとしても、バックアップが失敗を捕捉します。

「スラッシング」の捻り（保証金）

この論文はスラッシングと呼ばれる概念についても議論しています。すべての灯台守が作業を開始する前に、安全な場所に1,000ドルの保証金を預けなければならないと想像してください。

彼らが仕事をすれば、保証金が返還され、さらに小さな報酬が得られます。
彼らが失敗した場合（またはシステム全体が彼らのせいで失敗した場合）、ネットワークは彼らの保証金を没収します。

論文は、「船の衝突」に対する罰金が巨大であればあるほど、これらの保証金を持つことが非常に役立つと発見しています。これは保険のような役割を果たします。破壊工作員が衝突を引き起こそうとすれば、ネットワークは彼らの保証金を没収して損害の支払いに充てることで、長期的にはシステム全体を運営するコストを大幅に削減できます。

実務家への主な教訓

著者は、これらのブロックチェーンシステムを構築する人々に対して、非常に明確な助言を与えています。

あまりに賢く、あるいは対称的になろうとしてはいけません。 全員に同じ確率で同じことをさせるのではなく、以下の通り行うべきです：

特定の1人を指名して、主な作業を行わせる（「指名された」リーダー）。
小さな委員会を選び、バックアップとして機能させる。
保証金（ステーキング） を用いて、失敗した場合に失うものがあることを保証する。

この構造は、多くのブロックチェーンがすでに機能している方法（「ブロック提案者」と「バリデーター委員会」を選ぶなど）を模倣しており、この論文は数学的に、信頼できず潜在的に悪意のある労働者を扱う際、コストと安全性のバランスを取る最良の方法であることを証明しています。

一文で要約

見知らぬ人々から重要な作業を引き出す際、彼らが詐欺を働こうとする可能性があるなら、最良の戦略は、特定の1人を指名してその作業を行わせ、その人が失敗した場合に飛び込む準備ができている小さなバックアップチームを保持し、全員が途中で放棄しないように保証金を預けさせることです。

技術的サマリー：ブロックチェーンにおける敵対的調達

問題定義

本論文は、計算の非対称性（タスクの実行と検証の間）を活用する新興設計（ゼロ知識証明、すなわち SNARK など）の文脈において、ブロックチェーンプロトコルにおける敵対的調達の課題に取り組む。これらのシステムでは、プロトコルは、ブロックの妥当性証明の生成など、高コストな計算タスクを、 $n$ 人の匿名かつ信頼できない証明者（provers）の集合に委託しなければならない。

核心的な問題は、以下の条件を満たすメカニズムを設計することである：

少なくとも 1 人の証明者にタスクを実行させるようインセンティブを与えること（活性を確保する）。
最大 $n-h$ 人の証明者が敵対的（ビザンチン）であり、活性障害（証明の未提供）を引き起こしたり、過剰な支払いを誘発したりするためにプロトコルから逸脱する可能性のある最悪のシナリオにおいて、経済的損失を最小化すること。
証明者に評判がなく、将来の行動に確実に関与できないため、信頼なしで動作すること。

著者らは、これをメカニズム設計の問題としてモデル化しており、プロトコル設計者は、敵対者が証明者のサブセットを支配し、プロトコルの損失を最大化するように行動すると仮定して、支払額の合計と証明が提供されなかった場合に生じるペナルティ $C$ の合計を最小化することを目的としている。

手法

著者らは、ゲーム理論的枠組みを用いて問題を形式化した：

設定： $n$ 人の証明者がおり、そのうち $h$ 人が誠実である。証明生成のコストは 1 に正規化されている。証明が生成されない場合、プロトコルは活性ペナルティ $C$ を被る。
敵対者モデル：敵対者は最大 $a = n-h$ 人の証明者を侵害できる。敵対者はメカニズムを観察し、最悪の行動（ペナルティ $C$ を発動させるために証明の提供を拒否するか、支払いを操作するために証明を提供するか）を選択する。
目的：最悪の敵対戦略下での期待総コスト（支払い＋ペナルティ）として定義される最悪ケース損失 $\ell(p, s)$ を最小化すること。ただし、メカニズムがインセンティブ両立性（誠実な証明者がプロトコルに従うことで効用を最大化する）の制約を満たすこと。

問題を扱いやすくするため、著者らは以下の手順を踏んだ：

各証明者が証明を提供する確率である戦略ベクトル $s$ をパラメータとする、最適プロトコル損失に関する下限関数 $g(s)$ を導出した。この限界は、完全に誠実に行動するか、完全に提供を拒否するかという 2 つの極端な戦略のいずれかを選択する「弱体化された」敵対者を仮定している。
この下限の最小化者を分析し、それらを指名均等委員会均衡（1 人の決定論的リーダー＋ランダム化委員会の集合）または対称委員会均衡（指名されたリーダーなしのランダム化委員会の集合）のいずれかとして特徴づけた。
実装可能性を調査した：これらの均衡を誘発し、かつ下限コストを達成する支払いルールが存在するかどうかを判断する。
証明者が攻撃を検知した際に没収される担保（ステーク）を提出する負の支払い（スラッシング/ステーキング）を含むように分析を拡張した。

主要な貢献と結果

1. 最適均衡の特性化

本論文は、下限 $g(s)$ の最小化者が厳密に以下の 2 種類のみであることを証明している：

指名均衡：1 人の証明者が確率 1 で提供するように指名され、サイズ $k$ の委員会が確率 $s \in (0, 1)$ で提供する。
対称均衡：サイズ $k$ の委員会が確率 $s$ で提供し、特定の証明者が指名されない。

2. 近似保証

加法的 1-近似：著者らは、任意の支払いルールと均衡に対して、最適損失から最大 1 単位（単一の証明のコスト）以内の損失を持つ指名均衡が存在することを証明した（定理 3.1）。
実装可能性：すべての指名均衡は、単純な支払いルールで実装可能である（補題 3.4）。これに対し、対称均衡は特定の条件下（例えば、 $C$ が $n$ や $h$ に対して十分に大きい場合）でのみ実装可能であり、実現可能にするためには複雑な支払い構造や負の支払いを必要とすることが多い。

3. 漸近的スケーリング

対数スケーリング：最適指名均衡の最悪ケース損失は、 $O(\frac{\log C}{\tau})$ としてスケーリングする。ここで $\tau = h/n$ は誠実な証明者の割合である。これは、敵対者の割合が固定されていても、プロトコルコストは活性ペナルティの重大度に対して対数的にしか増加しないことを示している。
ステーキングの影響：総ステーク $B$ （担保）を導入するとスケーリングが大幅に改善される。 $B$ が $C$ に比例する場合、損失は $O(1/\tau)$ としてスケーリングし、 $C$ に対して実質的に定数となる。

4. 遷移ダイナミクス

本論文は、 $C$ （ペナルティの大きさ）と $\tau$ （誠実さの割合）の関数としての、指名均衡と対称均衡の最適性間の遷移を分析した。

$C$ が小さい場合、または $\tau$ が高い場合、指名メカニズムが最適である。
$C$ が非常に大きい場合、下限分析において対称メカニズムが最適となる。
しかし、実装可能性の制約により、対称的な下限がより低い領域であっても、指名メカニズムが実際的な選択となることが多い。これは、対称的解が非現実的または実装が複雑な負の支払いを必要とする可能性があるためである。

意義と実践的推奨事項

本論文は、理論的結果が、特にzk-EVM（ゼロ知識イーサリアム・バーチャル・マシン）および他の検証可能なアウトソーシング市場向けのブロックチェーンプロトコル設計者に対して、実行可能な指針を提供すると主張している。

推奨事項：著者らは、最適指名均等委員会均衡の採用を強く推奨している。この設計は、証明を決定論的に生成する単一の「リーダー」（または主要ワーカー）を指名し、計算された確率 $s$ で証明を生成する「バックアップ」の委員会によって支援される。
正当性：
1. 単純性：支払いルールは直感的であり、既存のコンセンサスメカニズム（例：アテステーション委員会を備えたリーダーベースのコンセンサス）に似ている。
2. 準最適性：損失は理論的最適値から証明 1 つのコスト以内であり、現在の証明コスト（しばしば数ドルの分数）を考慮すれば無視できる。
3. 堅牢性：最悪の敵対的行動を効果的に処理し、ペナルティ $C$ に対して対数的にスケーリングする。
4. 実現可能性：最適化のために複雑な抽選型支払いや負の支払い（スラッシング）を必要とする可能性のある対称メカニズムとは異なり、指名メカニズムは常に正の支払いで実装可能である。

本論文は、対称メカニズムが特定の漸近領域において理論的に興味深く最適である一方で、指名メカニズムが理論的最適性、実装可能性、およびブロックチェーンコミュニティへの親和性の面で最良のバランスを提供すると結論づけている。著者らは、このモデルが、検証可能な AI 推論や TEE ベースの計算を含む、活性障害を伴うあらゆる権限なしの委任問題に広く適用可能であると指摘している。