キャパシティオラクル

原文

Capacity oracles — mbahrani (2026-04-23)

キャパシティオラクル

by maryam and mike; april 23, 2026.

要するに; ブロックチェーンプロトコル設計における新たなパターンは、委任検証 (delegation-verification) です。これは、一連の専門ノードが計算集約的なタスクを実行し、はるかに大規模なパーティのセットがその出力を検証するというものです。このパターンは、作業を実行するコストと、それが正しく行われたことを検証するコストの非対称性を利用しています。ZKプルーフ (ZK proofs) はその明白な例ですが、他のより一般的なワークロードもこのパラダイムに適合します。例えば、AI推論 (AI inference) を実行するTEE (Trusted Execution Environment) は、ハードウェアによって生成されたアテステーション (attestation) を検証することで確認できます。これらのシステムは情報抽出の問題に直面します。潜在的なユーザーは、自分のワークロードに対して十分な追加キャパシティがあることを知りたいかもしれませんが、ワーカーの利用可能なスループットを把握できません。特に、チェーン上のノードのキャパシティを示す唯一のシグナルは、実行されたワークロードの事後的なビューであり、どれだけの追加作業が処理できたかについては何も語りません。この投稿では、この問題を捉えるシンプルなモデルを提示します。

目次

(1) はじめに \quad(1.1) ネットワークキャパシティの理解 (2) モデル \quad(2.1) モデルに関するコメント \quad(2.2) 非Sybil環境における素朴な解決策 (3) Sybil攻撃 \quad(3.1) アプローチ1：支払いの相関付け \quad(3.2) アプローチ2：ステーキングとスラッシングの追加 (4) Sybil攻撃、スラッシング、そして真実の価格 \quad(4.1) 線形報酬は依然として脆弱 \quad(4.2) 凸型報酬 (5) まとめ

1. はじめに

次世代のブロックチェーンプロトコルで提案されている一般的な設計パターンは、すべてのノードが状態更新の履歴をリプレイする元のレプリケートされたステートマシン (replicated state machine) を、「レプリケートされた検証者 (replicated verifier)」モデルに置き換えるものです。このモデルでは、タスクは一度実行され、何度も検証されます。これは、多くのタスクの検証がそれらを実行するよりも簡単であるという事実を利用しています。この典型的な例は、イーサリアムメインネット向けに提案されているZK-EVMスケーリング (ZK-EVM scaling) です。ここでは、ネットワーク内の各ノードが各ブロックを再実行する代わりに、ブロックには、トランザクションの全リストを再実行することなく、内容の正確性を簡潔に検証するプルーフが付属します。

組み込み型ZK-EVMの素朴な実装では、各ブロックの完全なプルーフが、12秒のイーサリアムスロット内で単一のプロバー (prover) によって生成されることを要求します。これには2つの根本的な制限があります。第一に、複数のプロバーのリソースを集合的に活用しない（つまり、勝者総取りである）こと。第二に、単一のスロット内で実行と証明が可能なワークロードしか対応できないこと。より一般的なアプローチでは、複数のプロバーが異なるタスクを並行して処理できるようにし、理想的には、タスク完了までのタイムラインをスロット時間に制約されるのではなく、ユーザーが設定できるように拡張します。

これがなぜ必要かを見るために、オンチェーンでのAI推論 (AI inference) を可能にするという目標を考えてみましょう。その世界では、各トランザクションが異なる要件を持つ高価なAI操作を呼び出す可能性があります。ブロック内のすべてを一括で証明するために単一のパーティに依存するのではなく、それはビルダー市場 (builder market) のさらなる中央集権化につながるでしょうが、タスクの実行を広範なサプライヤーノード (supplier nodes) に非同期で分散させ、最終的にオンチェーンで検証する方がより自然です。

これはRitualが採用しているアプローチです。彼らは、異なるリソース要件（例：ハードウェア、モデルアクセス、帯域幅、レイテンシなど）を持つタスクを想定し、タスクとサプライヤーの効率的なマッチングを見つけながら、最終的なオンチェーン検証 (Symphony) を通じて正確性の保証を提供する両面市場 (two-sided marketplace) (Resonance) を提案しています。

このブロックチェーンスケーリングの進化が私たちのモデルを触発しています。

1.1 ネットワークキャパシティの理解

複数のサプライヤーモデルでは、ユーザーが抱く自然な疑問は次のとおりです。「チェーンの現在のキャパシティはどれくらいか？」この質問への回答は、ユーザーがこのプラットフォーム（集中型クラウドプロバイダーと比較して）を選択するかどうかに影響を与える可能性があります。なぜなら、ユーザーは信頼性保証を必要とするからです。基本的な先着順調達メカニズム (first-come-first-served procurement mechanism) を考えてみましょう。タスクを最初に実行した者が支払いを受け取ります。FCFSはチェーンの真のキャパシティを把握できません。なぜなら、勝者だけが完了したタスクを納品し、敗者はすぐに処理を停止し、それ以上リソースを無駄にしないために部分的に完了したタスクを破棄するからです。[1]

あるいは、より良いキャパシティ指標 (capacity indicator) を期待してオークションを通じて入札を募ることもできますが、すべてのオークションが良い品質のシグナルをもたらすわけではありません。例えば、ファーストプライスオークション (first price auctions) が正直な報告 (truthful reporting) をもたらさないことはよく知られており、入札が真のキャパシティを誤って表す可能性があります。これが「キャパシティオラクル (capacity oracle)」というアイデアを動機付けます。ここでは、調達メカニズムがチェーンの利用可能なキャパシティのより良いシグナルを提供することを目標として設計されます。例えば、調達メカニズムが厳密に支配戦略インセンティブ互換 (DSIC) (dominant-strategy incentive compatible (DSIC)) である場合、プロトコルは完璧なオラクルを持つことになります。なぜなら、均衡入札がチェーンの総キャパシティの正確な推定値を提供するからです。

しかし、ブロックチェーンの文脈でDSICオークションを実行することは非常に困難です。なぜなら、古典的なオークション設計とは異なり、多くの偽のIDを作成するなどの逸脱行為に陥りやすいためです。例えば、「On Sybil Proof Auctions」では、Panらはフォワードオークション (forward auction) の設定において、唯一のSybil耐性 (Sybil proof) かつDSICなメカニズムは標準的なセカンドプライスオークション (second price auction) であることを示しています。これは、オークション主催者が信頼できず、偽の入札を注入する可能性があるため、オンチェーンで実行するのが困難です。リバースオークション (reverse auctions)（私たちの設定に近い）では、「Beyond Winner-Take-All Procurement Auctions」がDSICだがSybil耐性ではない調達メカニズム、およびSybil耐性だがDSICではないメカニズムを設計していますが、両方の特性を満たすものはありません。

この投稿では、ブロックチェーン調達設定でキャパシティオラクルを構築する方法を探ります。セクション2では、基本的なモデルを導入し、固定されたIDセットの下でDSICである素朴なメカニズムを提案しますが、単純なSybil攻撃 (Sybil attack) に苦しみます。セクション3では、モデルを拡張してSybil攻撃を含め、Sybil攻撃に対抗する2つの異なるアプローチ（3.1の相関支払いと3.2のスラッシング (slashing)）を提示します。セクション4では、キャパシティオラクルの実用的な実装を研究し、プロトコルコストとオラクル精度間のトレードオフを数値的に示し、実務家向けのプロットと具体的な考察を提供します。

2. モデル

n個のサプライヤー (suppliers) のセットを考えます。それぞれが同じ線形単位生産コストと、プライベートキャパシティ (private capacity) $c_i\in {\mathbb{R}}_{+},i\in [n]$ を持ちます。キャパシティベクトルを $\mathbf{c}$ と表記します。各サプライヤーは、自分が持つと主張するキャパシティの量を示す入札 (bid) $b_i$ をプロトコルに提出します。プロトコルは、入札ベクトル $\mathbf{b}$ を割り当てベクトル $\mathbf{x}$ にマッピングする割り当てルール (allocation rule) $x:{\mathbb{R}}_{+}^n\mapsto {\mathbb{R}}_{+}^n$ を定義します。プロトコルが行うことができる割り当て量に制約はなく、割り当ては分数でも可能です。これは、プロトコルが常に「偽の」作業を作成してサプライヤーに割り当て、主張されたキャパシティがあることを証明するオプションを持っていると考えることができます。割り当てに基づいて、サプライヤーは割り当てられた作業を「納品 (deliver)」するかどうかを決定します。サプライヤーiが納品した作業量を $d_i\in [0,c_i]$ とします（真のキャパシティ $c_i$ を超えて納品することはできないため）。$\mathbf{d}$ は納品の完全なベクトルを表します。プロトコルはまた、入札 $\mathbf{b}$ と納品 $\mathbf{d}$ のベクトルを支払いベクトル $\mathbf{p}$ にマッピングする支払いルール (payment rule) $p:{\mathbb{R}}_{+}^n\times {\mathbb{R}}_{+}^n\mapsto {\mathbb{R}}_{+}^n$ を定義します。完全なメカニズムはタプル $(x,p)$ によって定義されます。各サプライヤーiは、単位生産コスト (per-unit cost of production) が1に正規化された準線形効用 (quasi-linear utility) を持ちます。

$u_i(\mathbf{b},\mathbf{d})=p_i(\mathbf{b},\mathbf{d})-d_i.$

サプライヤーの均衡入札行動 (equilibrium bidding behavior) は、キャパシティオラクルを構築するために使用できます。キャパシティオラクルは、均衡入札および納品ベクトルから実数への関数 $F:{\mathbb{R}}_{+}^n\times {\mathbb{R}}_{+}^n\mapsto {\mathbb{R}}_{+}$ であり、サプライヤーの利用可能な総キャパシティを定量化しようとします。完璧なキャパシティオラクルFは ${\sum }_{i\in [n]}{c}_i$ に等しくなります。私たちの目標は、小さな期待支払い ${\sum }_{i\in [n]}{p}_i$ で完璧なキャパシティオラクルを実装するメカニズムを設計することです。[2]

2.1 モデルに関するコメント

いくつか明示的に指摘すべき点があります。まず、私たちは共通価値設定 (common value setting) を検討しています。ここでは、誰もが同じ生産コストを持ちますが、プライベートなキャパシティを持っています。これは、調達オークション (procurement auctions) に関する標準的な文献からの逸脱です。通常、プライベートな情報はサプライヤーのみが知る「コスト」としてモデル化されます（例：「Truthful Mechanisms for One-Parameter Agents」）。私たちのドメインでは、コストではなくネットワークのキャパシティを引き出すことに関心があるため、扱いやすさのためにコストは公開情報として固定しています。

さらに、私たちのモデルではプロトコルが作業を任意に割り当てることができます。これもまた、割り当て可能な総作業量が固定されている従来の調達メカニズムとは大きく異なる設定です。物理的な世界では、割り当てが制限されるのは理にかなっています。政府が橋を建設するために請負業者から入札を募る場合、建設できる橋は1つだけなので、1単位の作業しか割り当てることができません。デジタル設定では、「作業」が計算である場合、プロトコルはサプライヤーが行うタスクを任意に構築できます。プルーフ・オブ・ワーク (Proof-of-Work) と同じ精神で、任意に困難なパズルを作成できるのと同様に、プロトコルは合成AIワークロード (synthetic AI workloads) を作成し、キャパシティを示すためのZKチャレンジ (ZK challenges) を具体的に構築できます。実際、この技術はすでにAleoによって探求されていますが、目標は初期のサプライヤーセットを引き付けるという異なるものでした。もちろん、ただで手に入るものはありません。個人の合理性 (individual rationality) により、プロトコルがk単位の作業を割り当てる場合、参加者がそもそもゲームに参加するインセンティブを確保するために、少なくともkを支払う必要があります。

私たちのモデルのベースライン解釈は、プロトコルが可用性を確保するためにのみ作業を作成するというものですが、より実用的な解釈は、自然に要求される作業を補完するだけというものです。有機的な需要 (organic demand) が十分大きく、良好なキャパシティオラクルを確保できる期間がある場合、プロトコルは追加の作業を作成したり補助したりする必要はありません。しかし、使用量が少ない期間には、プロトコルは生成するワークロードを増やすことができます。この観点から見ると、プロトコルは、高品質のキャパシティオラクルと安定したサプライヤーセットを維持するために十分な作業が存在することを保証するコントローラーと見なすことができます。

より一般的には、キャパシティオラクルを基礎として、コストのかかる度合いに基づいて異なる種類のワークロードを検討できます。一方では、有機的な需要はユーザーが支払うため「無料」です。もう一方の極端な例では、私たちが考慮する合成ワークロードは、プロトコルがそのコストを負担するため、最大限にコストがかかります。中間的なものとして、プロトコルにとってある程度有用だが、ユーザーによって完全に支払われるわけではないワークロードを想像できます。これの良い例は、Ritualのスケジュールされたトランザクションです。これらはプロトコルが事前に知っているcronのようなジョブであり、可用性オラクルの一部として事前に実行できます。ただし、その実行が新しい状態に依存する必要がある場合、一部を再実行する必要があるかもしれません。そのため、これらは安価な合成ジョブですが、まだ無料ではありません。この投稿の目的のため、これらを明示的にモデル化することはありません。

最後に、このモデルの初期バージョンはSybil報告 (Sybil reports) を捉えていないことに注意してください。私たちは、直感を構築し、Sybil報告が具体的にどこで損害を引き起こすかを示すためのウォームアップメカニズムを提示します。セクション3では、Sybil攻撃を明示的に考慮し、それらにどのように対応するかを検討し始めます。

2.2 非Sybil環境における素朴な解決策

Sybil攻撃のない環境から始め、以下の割り当ておよび支払いルールを考えます。

\begin{align*} x_i(\mathbf{b}) &= \begin{cases} b_i & \text{ w.p. } \varepsilon \\ 0 & \text{ otherwise} \end{cases}\\ p_i(\mathbf{b}, \mathbf{d}) &= \begin{cases} b_i + r(b_i) & \text{ if } x_i = b_i = d_i \\ 0 & \text{otherwise} \end{cases} \end{align*}

ここで私たちが行っているのは「ランダム監査 (random audit)」です。各サプライヤーに対して、ある小さな確率で、彼らの主張するキャパシティ $b_i$ 全体を割り当てます。もし $b_i$ が割り当てられ、割り当てられた作業を完全に納品した場合、発生した生産コストに加えて、何らかの「報酬 (reward)」 $r(b_i)$ を支払います。

$r(b_i)>0$ がすべての $b_i>0$ で成り立ち、$r$ が $b_i$ に対して単調増加 (monotone increasing) である限り、完璧な可用性オラクルが得られます。各割り当ては独立して抽選されるため、1つのサプライヤーの効用を考慮し、他のすべての行動を無視できます。そのサプライヤーは、何を提案すべきかを検討しています。彼らは次のことを知っています。

• 彼らが何を提案しても、確率 $\epsilon$ で選ばれます。
• 任意の提案 $b_i$ に対して、割り当てられた場合、完全に納品した場合にのみ支払いを受けます。つまり、$d_i=b_i$ の場合です。
• 彼らの純利益 $r(b_i)$ は、真のキャパシティ $c_i$ まで（それ以上は納品できないため支払われない）、報告および納品する量に対して単調増加します。

したがって、正直な入札は他の戦略を厳密に支配し (strictly dominates)、完璧なキャパシティオラクルが得られます。さらに、プロトコルは $\epsilon$ を任意に小さく設定できるため、この情報を実質的に無料で得ることができます。ただし、各サプライヤーの期待利益は $\epsilon r(c_i)$ にすぎず、これは小さいことに注意してください。これは、サプライヤーが選ばれる確率、ひいては報酬を得る確率を高めることができるSybil攻撃 (Sybil attack) を誘発します。

3. Sybil攻撃

上記のメカニズムは、任意の $\epsilon$ と任意の単調関数 $r$ に対して完璧に機能しますが、人々が単一の入札しか提出できない場合に限ります。 しかし、キャパシティオラクルを持つという目標を完全に損なう基本的なSybil攻撃があります。

サプライヤーが自分の真のキャパシティ $[c_i,\dots ,c_i]$ の多くのコピーを提出すると考えます。（モデルにSybil識別子表記 (Sybil identity notation) を明示的に導入すると表記が煩雑になるため、ここでは導入しませんが、Sybil攻撃者は期待通りです。単一のサプライヤーが任意の数のIDで任意のキャパシティを報告できます。）各IDは確率 $\epsilon$ で独立してサンプリングされるため、少なくとも1つのIDが割り当てられる確率が増加します。複数のIDが割り当てられた場合、1つだけが納品できますが、他のIDは納品しなかったことに対する罰則がないため、デメリットはありません。したがって、高い確率で、この戦略からの総利益は $r(c_i)$ であり、Sybil攻撃のないベースライン $\epsilon r(c_i)$ よりもはるかに大きくなります。さらに、どのIDが実際に納品するかを知ることなく、入札全体で非常に大きなキャパシティが集計されるため、キャパシティオラクルの品質は任意に悪くなります。

明らかに、この最も基本的な形式のメカニズムでは不十分であるため、これに対処するためのいくつかの方法を検討します。

3.1 アプローチ1：支払いの相関付け

次に、サプライヤーの割り当てと支払いを相関させることで何ができるかを考えてみましょう。プロトコルは依然として入札ベクトル $\mathbf{b}\in {\mathbb{R}}_{+}^n$ に対して動作し、次のメカニズムを実装します。

\begin{align*} x(\mathbf{b}) &= \begin{cases} \mathbf{b} & \text{ w.p. } \varepsilon^n \\ 0 & \text{ otherwise} \end{cases}\\ p_i(\mathbf{b}, \mathbf{d}) &= \begin{cases} b_i + r(b_i) & \text{ if } \mathbf{x} = \mathbf{b} = \mathbf{d} \\ 0 & \text{otherwise} \end{cases} \end{align*}

これは最大限に相関するメカニズム (maximally correlated mechanism) です。なぜなら、全員が完全に割り当てられ、支払いを受けるか、誰も受けないかのどちらかだからです。サプライヤーiは、他のすべてのサプライヤーも入札したものを完全に納品した場合にのみ、納品に対して支払いを受けることに注意してください。

Sybil攻撃の可能性にもかかわらず、これは完璧なキャパシティオラクルをもたらすことが判明しました。再び、単一のサプライヤーの戦略を考えてみましょう。彼らは、もし過剰報告 (overreport) した場合（つまり、彼らのID全体での総報告が $c_i$ を超える場合）、割り当てられたときに報告されたキャパシティを納品できないため、効用が0になることを保証されます。彼らの利益は、総報告キャパシティが $c_i$ になるまで単調増加します。したがって、彼らが最善を尽くせるのは、合計 $c_i$ のキャパシティを報告することです（複数のIDに分割しても損失はありません）。したがって、すべてのナッシュ均衡 (Nash equilibrium) において、結果として得られるキャパシティオラクルは完璧です。

これは魔法のようです！Sybil攻撃から身を守り、再び、任意の $\epsilon$ と任意の単調関数 $r$ を選択し、任意の価格で完璧なキャパシティオラクルを保証できます。これは巧妙なトリックですが、それがさらす明白なグリーフィングベクトル (griefing vector) を考えると、おそらく実用的ではありません。特に、サプライヤーとして、誰かが報告したものを納品できなかった場合、誰も支払いを受けられないことを知っています。したがって、単一の悪意のあるサプライヤー (malicious supplier) がこれを確実に引き起こすことができます。さらに、割り当てられることは極めて稀なイベントであり、サプライヤーの利益とプロトコルの支出の両方が非常に変動しやすくなります。

3.2 アプローチ2：ステーキングとスラッシングの追加

相関アプローチの脆い性質を考慮し、素朴なメカニズムの非相関監査 (uncorrelated auditing) に戻りましょう。元のメカニズムの何が問題だったのでしょうか？それは、納品しなかったことに対するデメリットがなかったため、誤報告するインセンティブがあったことです。これに対処する別の方法は、ステーキング (staking) を追加し、メカニズムが不正行為をするサプライヤーをスラッシング (slashing) できるようにすることです。これらの負の支払いは、過剰報告を抑制できる説明責任 (accountability) の層を追加します。

より正式には、参加を希望するすべての人がステーク額 $S$ を預ける必要があり、納品しなかった場合はスラッシングされると仮定します。私たちは、納品が全割り当て $d_i<x_i$ よりも少ない場合、担保 (collateral) を完全にスラッシングする最大限に攻撃的なペナルティ関数 (maximally aggressive penalty function) に焦点を当てます。これにより、プロトコルはステークを要求する効果を最大化できます。[3]

すると、以下の割り当ておよび支払いルールが得られます。

\begin{align*} x_i(\mathbf{b}) &= \begin{cases} b_i & \text{ w.p. } \varepsilon \\ 0 & \text{ otherwise} \end{cases}\\ p_i(\mathbf{b}, \mathbf{d}) &= \begin{cases} b_i + r(b_i) & \text{ if } x_i = b_i = d_i \\ -S & \text{ if } x_i = b_i > d_i \\ 0 & \text{otherwise} \end{cases} \end{align*}

これはサプライヤーの視点からははるかに受け入れやすいものです。相関がないため、他のサプライヤーの行動について推論する必要がなく、他者の不正行為によって支払いを失うリスクもありません。さらに、彼らは入札したものを納品できない場合にのみ負の支払いを受けます。彼らは常に正直に行動し、非負の支払いを確保できます。

サプライヤーは、十分な資本をステーキングできる限り、複数の任意の入札を提出できます。しかし、納品しない割り当てられた報告はコストがかかるため、過剰な約束と不十分な納品 (over-promise and under-deliver) をするとリスクに直面します。

直感的には、このリスクはステーク額 $S$ の増加とともに増大します。なぜなら、過剰報告する各IDはより大きな金額をペナルティとして科されるからです。当然の疑問は、最大ステーク額が与えられた場合、設計者はどれくらいの精度のキャパシティオラクルを期待できるか？ ということです。次のセクションでは、支払った分だけ得られることを示します。オラクルの品質は、プロトコルによる過剰な割り当て (over-allocation) の量に依存します。プロトコルは、より多くの作業を割り当てることでオラクルの精度を高めることができますが、それに応じて生産コストをカバーするために支出を増やす必要があります。この投稿の残りの部分は、このトレードオフを数値的に示すことに専念します。

これは、サプライヤーが自明でない戦略 (non-trivial strategies) をとる均衡を持つ、私たちが研究する最初のメカニズムです。彼らは今、過剰報告が発覚するリスクと、割り当てられる確率を高めてより大きな報酬を得るというメリットをトレードオフしています。サプライヤーの決定は、報酬関数 $r$ の正確な形状に大きく依存するようになり、これを次のセクションで探ります。常に完全に正直であるか、最大限のSybil攻撃者であるという時代は終わりました。

4. Sybil攻撃、スラッシング、そして真実の価格

上記の議論を踏まえ、私たちは完全に非相関な[4]割り当てルールと、完全にスラッシングするペナルティ関数に限定して検討します。これにより、メカニズムの自由パラメータは報酬関数 (reward function) $r$ のみとなります。これが結果として得られる割り当ておよび支払いルールであることを思い出してください。

\begin{align*} x_i(\mathbf{b}) &= \begin{cases} b_i & \text{ w.p. } \varepsilon \\ 0 & \text{ otherwise} \end{cases}\\ p_i(\mathbf{b}, \mathbf{d}) &= \begin{cases} b_i + r(b_i) & \text{ if } x_i = b_i = d_i \\ -S & \text{ if } x_i = b_i > d_i \\ 0 & \text{otherwise} \end{cases} \end{align*}

これまでの結果は一般的であり、$r$ の単調性にのみ依存していました。しかし、今は新しいレジームにあり、均衡におけるサプライヤーの戦略的行動 (strategic behavior)、ひいては完璧なキャパシティオラクルの価格は、$r$ の形状に大きく依存します。

4.1 線形報酬は依然として脆弱

$r$ の非常に自然な選択肢の1つは、ある $\lambda >0$ に対して $r(b_i)=\lambda b_i$ という線形関数 (linear function) です。興味深いことに、これは $-S$ がどれほど大きくてもSybil攻撃に対して脆弱です！サプライヤーは、報酬の分散 (variance of their rewards) を減らすために真のキャパシティをより小さな塊に分割するだけでなく、単一の入札 $b_i=c_i$ から得られる正直な値 $\epsilon \lambda c_i$ を超えて期待報酬を増やすために過剰報告 (overreport) するインセンティブも持ちます。

より正式には、任意の有限のステーク $S$ と検査率 $\epsilon$ に対して、N, $\alpha >1$ が存在し、N個のIDで $\alpha$ 倍の過剰報告を行う収益性の高いSybil戦略が存在します。その理由を見るために、$c_i=1$ と正規化し、N個の異なるIDをそれぞれ小さな固定量 $b_i=\alpha /N$ で入札するアプローチを考えます。ここで $1<\alpha <1/\epsilon$ です。[5] 合計すると、サプライヤーは $b_{i}N=\alpha$ のキャパシティを報告しており、$\alpha >1$ なので過剰報告です。

この戦略をプレイすることで、サンプリングされるIDの数は確率変数 $X\sim \text{Binomial}(N,\epsilon )$ となり、サプライヤーに割り当てられるキャパシティの量は $\alpha /N\cdot X$ となります。Nを大きくすることで、サプライヤーは報酬分布をその平均 $\alpha \epsilon <1$ に集中させることができ、同時に過剰割り当てされる確率を任意に小さくすることができます。これは彼らにとって有利です。なぜなら、彼らは $\alpha \epsilon \lambda >\epsilon \lambda$ の報酬に近づくからです。

以下の図は、Nの増加に伴う0.97への集中を示しています。1の右側（スラッシングにつながる）の確率質量を任意に小さくできることに注意してください。

直感的には、サプライヤーは多くの小さなIDに分割することで利益を得ます。過剰報告にもかかわらず、彼らは常に、過剰報告で捕まるリスクの裾確率 (tail probability) を、誤報告する価値があるほど小さくすることができます。この結果は、ステークが実際には何の保護も提供しないため興味深いものです。攻撃者は細分化を続け、過剰報告で捕まるリスクを最小限に抑えることができます。さらに、報酬関数が正確に線形であるため、彼らの小さな報告はサイズに比例して支払われます。

この問題に対する実用的な解決策 (pragmatic solution) は、報告可能な入札の下限 (lower bound on the reportable bids) $b_i$ を設定することでしょう。これは確かに機能しますが、そのバージョンの数学はあまり面白くないため、ここでは割愛します。より原則的なアプローチは、報酬関数の凸性 (convexity) を利用して、この無限分割行動を抑制することです。

4.2 凸型報酬

$r$ を凸関数 (convex function) にした場合に何が起こるかを考えてみましょう。直感的には、これはSybil攻撃を直接抑制できるため役立ちます。例えば、サプライヤーiのキャパシティが完全に割り当てられていると仮定すると、彼らは単一のIDで $c_i$ を入札することを、2つのIDで $c_i/2$ を入札することよりも常に好むでしょう。なぜなら、$r$ の凸性により、$2r(c_i/2)<r(c_i)$ だからです。

しかし、凸性だけでは正直な入札を保証しません。なぜなら、分割して過剰報告する価値がまだあるかもしれないからです。この記事の残りの部分では、特定の凸型報酬関数 (convex reward functions) のファミリーを研究し、プロトコルが要求するステークの量、報酬関数の曲率 (curvature)、および完璧なキャパシティオラクルの結果として生じるコストを考慮する際に直面するトレードオフの種類を説明します。

私たちは、一般化された凸型単項式 (monomials) $r(x)=x^p,p>1$ のファミリーを研究します。これらの単項式の曲率は単一のパラメータ $p$ であり、分割を抑制するために増やすことができます。さらに、単項式は $r^{\prime }(0)=0$ という良い特性を持っています。したがって、無限に小さい値を提案する価値は0であることがわかります（つまり、$\epsilon \to 0$ のとき $r(\epsilon )\to 0$）。[6]

一般性を失うことなく、単位キャパシティを持つサプライヤーを考えます。サプライヤーは、自分の割り当てと支払いが他のサプライヤーに依存しないため、他のサプライヤーの行動を考慮する必要はありません。私たちは、N個の入札をそれぞれ $\alpha$ の値で提出する行動空間を考えます。これは、過剰報告する可能性がある（$1/\alpha$ 以上の入札を提出することで）が、異なるサイズの入札（${\alpha }_1,{\alpha }_2,\dots$）を提出することは考慮しない均質な戦略 (homogeneous strategy) です。これは、小さな丸め誤差を除いて一般性を失わないと信じています（例えば、最後の小さな入札が期待利益をわずかに増加させるだけであっても、$[\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{100}]$ を提出するのが最適である可能性があります）。

サンプリングされるIDの数は $X\sim \text{Binomial}(N,\epsilon )$ であり、サプライヤーはそれらのうち正確に $\lfloor 1/\alpha \rfloor$ を満たすことができ、もし $X-\lfloor 1/\alpha \rfloor >0$ であれば、残りのIDに対してスラッシングペナルティを支払います。これにより、この戦略の完全な効用関数は次のようになります。

$U(N,\alpha )={\alpha }^p\mathbb{E}[\min (X,\lfloor 1/\alpha \rfloor )]-S\mathbb{E}[\max (X-\lfloor 1/\alpha \rfloor ,0)].$

正直な行動は、$N=1,\alpha =1$ で $U(N,\alpha )$ が最大化される場合に発生します。これには閉形式がないため、数値的に計算します。私たちは、攻撃者がN個のSybilで $\alpha$ を入札する戦略に焦点を当てていることを思い出してください。ここで、$\alpha \in \{1,\frac{1}{2},\frac{1}{3},\dots \}$ のみを考慮すれば十分であることに気づきます。なぜなら、このセット内の2つの点の間にある任意の $\alpha$ に対して、サプライヤーは依然としてそれらのうち $\lfloor 1/\alpha \rfloor$ しか納品できないため、区間の右端点を選択するからです。さらに、正直な行動は $\epsilon$ の効用を得るため、私たちは $U(N,\alpha )>\epsilon$ となり得る $\alpha$ の値のみを考慮すればよいことになります。$U(N,\alpha )<{\alpha }^{p-1}$ であることに注意すると、

\begin{align} U(N,\alpha) > \varepsilon &\implies \alpha^{p-1} > \varepsilon \\ &\implies \alpha > \varepsilon^{\frac{1}{p-1}}. \end{align}

したがって、上記の条件を満たす有限個の $\alpha$ の値のみをチェックすればよいことになります。$\alpha$ の値を固定した場合、$N$ に対して効用が単峰性 (unimodal) であることを示すことができます（ただし、あまり面白くないため証明は割愛します）。直感的には、これは各 $\alpha$ に対して、攻撃者が使用する最適なIDの数を示す一意の最適な値 $N$ が存在することを意味します。したがって、与えられた $S,\epsilon$ に対して正直な報告が最適であるかどうかを判断するために、最適な $N$ と $\alpha$ の値が1であるかどうかを確認できます。

以下の図は、2つの例を数値的に示しています。

図の左側のサブプロットは $\epsilon =0.017$ を示しています。$\alpha$ の各値について、可能な各ID数 $N$ を考慮し、最大効用を点で示しています。$\alpha =1/5$ の場合、N=44のSybilを報告すると0.0245の効用が得られ、これは正直な効用0.017よりもはるかに高くなります。右側では、$\epsilon$ を増やすとこれらの効用が劇的に減少することがわかります。ここでは、$\alpha =1,N=1$ が正直な効用 $\epsilon =0.034$ を達成し、すべてのSybil戦略はそれよりも悪くなります。これは、より高い $\epsilon$ が期待通りはるかに正確なキャパシティオラクルをもたらすことを示しています。しかし、監査確率が高くなるため、多額の支払いが必要になります。

正直な報告（例：$\alpha =1,N=1$）が最適となる最小の $\epsilon$ の値を探すのは自然なことです。これは、$\epsilon$ が高いほど、補償のための支払いも高くなるためです。より正式には、固定されたステーク $S$ とべき乗 $p$ に対して、以下を解きたいと考えます。

\begin{align*} \varepsilon^* (p, S) := \inf\{\varepsilon\in [0,1] : \max_{N\geq 1, \alpha \in \{1, 1/2, \ldots\}} U(N,\alpha) \leq \varepsilon\}. \end{align*}

効用関数は最大値の閉形式を許さないため、以下の反復的な数値手順を使用して ${\epsilon }^{\text{*}}$ を見つけることができます。

1. $p,S$ を固定し、検査率 $\epsilon$ を考慮します。
2. 各候補 $\alpha$ について、$U(N,\alpha )$ を最大化する $N$ を見つけます。
3. すべての $\alpha$ の値に対して $N$ が1であるかを確認します。そうであれば $\epsilon$ を返し、そうでなければ続行します。

この手順を使用して ${\epsilon }^{\text{*}}$ を見つけることができます。この単位コストの例では、正直な報告に対する報酬関数が単位キャパシティで $(1+1^p)\cdot {\epsilon }^{\text{*}}$ であるため、プロトコルは最終的に $2{\epsilon }^{\text{*}}$ を支払うことになります。単位キャパシティでない場合、プロトコルへのコストは ${\epsilon }^{\text{*}}$ に線形です。以下の図は、単位キャパシティの例における $S,p$ の関数としてのプロトコルコスト (protocol cost) の数値計算のヒートマップ (heatmap) を示しています。

プロトコルコストの単位はドルであり、「1単位の作業を実行するサプライヤーコスト」を示しています。例えば、$S=8$、$p=2$ の場合、プロトコルコストは0.2であり、プロトコルは完璧なキャパシティオラクルを引き出すために、総キャパシティの運用コストの20%を支払うことを期待すべきです。$S$ の単位もドルです。例えば、$S=8$ の値は、各サプライヤーが1単位の作業を行うコストの8倍をステークすることを意味します。

図に関するいくつかの注意点：

1. ある程度のスラッシング (S $\approx$ 10) が本当に必要です。 ステークが少ない場合、プロトコルコストは1に収束します。これは、完璧なオラクルを得るために最大キャパシティを支払わなければならないことを意味します。これは最悪のケースです。なぜなら、すべての入札者に完全に割り当てる自明なオラクルは完璧であり、コストは1だからです。
2. わずかな曲率 (p $\approx$ 1.5) が本当に必要です。 曲率がこれより低いと、分割攻撃が強力すぎ、プロトコルコストは約0.5とかなり高いままです。報酬関数にわずかな曲率を加えるだけで、大きな効果があります。
3. ステーク量と曲率の限界便益 (marginal benefit) は急速に減少します。 上記2つの閾値を超えると、プロトコルコストは急速には変化しません。これは、あまり多くのステークを要求したり、報酬関数の曲率を高くしすぎたりする必要がないことを意味するため、役立ちます。

上記の3番目の点が、小規模なサプライヤーにとって有利であることも注目に値します。高いステーク要件は、資本へのアクセスが少ないチームにとって不利になります。さらに、より凸型の報酬関数は、高キャパシティのサプライヤーに不釣り合いに有利であり、中央集権化の懸念 (centralization concern) となる可能性があります。そのため、比較的低いステークと低い曲率で完璧なキャパシティオラクルが得られるという事実は有望です。最低入札額 (minimum bid) を設定することで、Sybil攻撃のリスクをさらに軽減し、プロトコルコストを抑えることができます。

全体として、この分析はプロトコルが使用できる凸型支払いの一つの自然なファミリーにすぎません。この研究を拡張して、キャパシティオラクルを設計する最適な方法についてより一般的な声明を出すことは、将来の興味深い研究方向性を示します。さらに、キャパシティオラクルを実装することを検討しているチームは、ここで実行された定性分析を利用して、彼らのドメインで低コストのプロトコルを実装する方法を決定できます。

5. まとめ

多くのことをカバーしました！まとめると、私たちは分散型サプライヤーセットのキャパシティをよく把握できるプロトコルを設計することを目指しています。私たちは、作業の実行は高価だが、それが正しく行われたことを検証するのはコストがかからないという委任検証 (delegation-verification) フレームワークに関心があります。モデルは以下の仮定の下で動作します。

• 単一リソース: プロトコルは、新しいIDを自由に作成できる仮名のサプライヤー (pseudonymous suppliers) のセットから、単一タイプのリソース（例：計算）を取得しようとしています。
• 単位コスト: 各サプライヤーは、共通の、公に知られた単位生産コストを持ちます。この仮定は、取得されるリソースがコモディティ (commodity) である場合に理にかなっています。
• 無料検証: 作業が納品された場合、プロトコルはそれが正しく行われたことを無料で検証できると仮定します。
• プライベートキャパシティ: 各サプライヤーはプライベートキャパシティ（リソースの量）を持ちます。これがプロトコルがキャパシティオラクルで推定しようとしているものです。
• 任意割り当て: プロトコルは、任意の量の追加作業を割り当てることで、リソースに対する有機的な需要を増強できます。これはデジタル調達設定に固有のものです。
• 入札、割り当て、納品フェーズ: プロトコルは、チェーンの真のキャパシティを引き出すために入札を使用します。これにより、プロトコルは、納品しないキャパシティを主張するサプライヤーに説明責任を負わせることができます。
• プロトコルの目的: プロトコルは、サプライヤーへの支払いを最小限に抑えながら、完璧なキャパシティオラクルを作成しようとしています。

このモデルの下で、私たちは監査メカニズム (audit mechanisms) を研究しました。ここでは、プロトコルがサプライヤーのサブセットをランダムに選択して割り当て、完全に納品すれば支払い、納品しなければペナルティを科します。この分析から、実務家向けに多くの高レベルな考察を引き出すことができます。

1. ランダム監査は機能する: セクション4で数値的に示したように、確立された現実的なモデルと、プロトコルが要求できるステーク量に関する合理的な仮定の下では、有機的な需要がない場合でも、完璧なキャパシティオラクルをフルキャパシティで運用するコストの約20%で取得できます。真の需要が存在する場合、ユーザーの支払いがキャパシティオラクルのコストを相殺するのに役立ちます。
2. ステーク量: ステークは、プロトコルに説明責任の層を提供する点でシステムにおいて重要です。これにより、サプライヤーが真のキャパシティを誤報告するリスクが軽減されます。幸いなことに、必要なステーク量は比較的穏やかです。例えば、フルキャパシティで運用するコストの10倍を担保 (collateral) として要求できる場合、スラッシングはほとんどのレジームで過剰報告を抑制するのに十分です。
3. 報酬関数の曲率: プロトコルは、報酬関数 (reward function) 自体の形状を通じて誤報告から防御することもできます。わずかな凸性 (convexity) でさえ、完璧なキャパシティオラクルを得るためのプロトコルコストを大幅に削減できることを示しました。
4. 最低入札額: プロトコルが最低報告可能キャパシティを要求できる場合、そうすべきです。これは、サプライヤーがキャパシティをますます小さな単位に積極的に細分化するのを防ぐのに役立ちます。
5. 支払いの相関付け: 可能であれば、支払いに何らかの相関を持たせることもプロトコルに利益をもたらします。例えば、割り当てられた作業の50%が納品されなかった場合に誰も支払わないようにできる場合、攻撃者の戦略空間は大幅に制約されます。スラッシングを伴う場合、相関は非対称な方法で実装できます。つまり、割り当ては相関しているが支払いは非相関であるという形です。すべてのプレイヤーが同時に割り当てられた場合、納品した者のみが支払いを受け、納品しなかった者はスラッシングされます。これにより、スラッシングなしの相関環境に存在したグリーフィングベクトル (griefing vector) は排除されますが、スループットのバースト性 (burstiness of throughput) と報酬の大きな変動という問題は依然として残ります。
6. 中央集権化の力: もう一つの重要な考慮事項は、プロトコルが大規模なサプライヤーをどれだけ優遇するかです。明らかに、完璧なキャパシティオラクルと信頼できるプロバイダーを得る最も簡単な方法は、適格なサプライヤーのセットを明示的に制限し（例：プルーフ・オブ・オーソリティ (Proof-of-Authority)）、クラウドプロバイダーとしての評判と稼働時間に依存することです。これは面白くない解決策です。したがって、上記で説明したことは、過度なプロトコルコストなしに、パーミッションレスなサプライヤーセット (permissionless set of suppliers) のキャパシティを理解することを可能にします。それでも、設計の要素（高いステークと曲率）は、より多くの資本や計算リソースにアクセスできるパーティを優遇する可能性があり、プロトコルはこの影響を認識すべきです。

ここで提示された基礎モデルは、優れたキャパシティオラクルを設計することに関する理論的な問いに対して良い洞察を提供し、実務家は数値結果から多くの定性的なアイデアを得ることができます。投稿全体および脚注で詳述されているように、このモデルを一般化する方法は多くあります。しかし、実務家の視点からは、おそらく最も重要な問題は、キャパシティオラクルが非均質なリソース (non-homogeneous resources) に対してどのようにスケールできるかということです。委任検証モデルがサポートする計算タスクのセットは、単一の「計算」リソースよりもはるかに大きくなると予想されます。

お読みいただきありがとうございます！ -maryam & mike

---

1. ここでのプルーフ・オブ・ワーク (Proof-of-Work) との類似性に注目してください。ビットコインネットワークでは、パズルが単純で明確に定義されたタスクであり、難易度調整メカニズムが次のブロックを見つけるのに必要なハッシュ数を一次元的に測定するため、ハッシュレートキャパシティを推定できます。タスクがさまざまな計算コストを持ち（例：LLMの実行とZKプルーフの生成）、プロバイダーがさまざまな方法で専門化できる（例：TPUとFPGA）異種環境では、キャパシティ推定問題ははるかに扱いにくくなります。 ↩︎

2. この記事の読みやすさのため、完璧なオラクルのみに焦点を当てていますが、自然な次の質問は、オラクルの品質がどれだけ早く劣化するか、および/または不完全なオラクルのコストを定量化することです。 ↩︎

3. 他のスラッシング関数も合理的である可能性があります。例えば、懲罰的でないようにしたい場合、未納品の割り当て量に比例してのみスラッシングすることで、部分的な履行を奨励できます。しかし、分割を最大限に阻止する目的では、最大限に攻撃的なスラッシング関数が最も効果的です。 ↩︎

4. 相関のレベルも、より深く研究できる設計パラメータです。例えば、全員の支払いを完全に相関させる代わりに、サプライヤーの行動のサブセットに基づいて部分的に相関させることもできます（例：割り当てられた作業の少なくとも1/3が納品された場合に支払いが行われる）。ここでは、扱いやすさのために完全に非相関なバージョンに焦点を当てています。 ↩︎

5. もちろん、プロトコル内の各IDに対してステーク $S$ を預ける予算が必要です。最悪ケース分析を行っているため、攻撃者がこの戦略を価値あるものにするのに十分な資本を持っていると仮定しましょう。 ↩︎

6. 他にも潜在的に興味深い報酬関数の形状はたくさんあります。異なる条件下での最適解を特徴づけることは、この研究のもう一つの興味深い理論的拡張です。 ↩︎

2 posts - 2 participants

Read full topic