Ofelimos：プルーフオブユースフルワーク型コンセンサスプロトコル

プルーフオブワーク（PoW）のエネルギーコストとカーボンフットプリントの最小化は、暗号界で最も熱く議論されるテーマの1つです。ナカモトの最長チェーンプロトコルをプルーフオブユースフルワーク（PoUW）に置換することは、多くの観点から理想的な解決策として理論化されてきましたが、今日までその概念は納得のいくほどの安全な実現化に至っていません。

本日、有数の国際暗号会議Cryptoにて、Input Output Global, Inc.（IOG）は、コンセンサスメカニズムが同時に分散型最適化問題解消機能を持つ新しいPoUW型ブロックチェーンプロトコル、Ofelimos（オフェリモス）を発表しました。このコンセンサスメカニズムは「ワーク（作業）」を活用して、ブロックチェーンを維持するために実用的な利益に関する計算（コンピュテーション）の諸問題を解消します。

プルーフオブワーク対プルーフオブユースフルワーク

PoW型ブロックチェーンプロトコルは、「マイナー」と呼ばれるプロトコル参加者によって実行されるワークを利用します。PoWは、新ブロック生成の資格を得るために計算問題を解くという競争にマイナーを駆り立てることで台帳の安全性を確保します。この計算作業はプロトコルの安全性を維持しますが、膨大な電力とリソースの消費を必要とします。本稿執筆時点で、ビットコインの年間消費電力は中小規模の国家レベルに匹敵します。

プルーフオブ「ユースフル」ワークは、プロトコルの安全性を維持するために必要な計算の目的を、たとえば企業のロジスティクスやイベントスケジューリングの最適化といった複雑な現実問題を解消することに変更することで、このエネルギー効率の問題に対処します。

PoUWの課題の1つは、解決すべき問題が真に役立つ（現実世界に発する）場合、攻撃者は簡単に解決できる（または攻撃者によって解決済みの）問題インスタンスを提示するようにシステムを操作する可能性がある、というジレンマを解消することです。これにより、誠実な参加者のリソースに対して、攻撃者は同量のリソースを活用してより多くのブロックを生成できるため、ブロックチェーンの安全性は低下します。一方、攻撃者がブロック生成を活用する能力を最小限に抑えようとすると、ランダムな問題インスタンスを提示することになり、システムの計算が実際に役に立たないものになります。

Ofelimosは、安全性と有用性の形式分析によって、このジレンマを共に解消します。

Ofelimosの概要

クライアントは解決すべき問題を公開し、成功したマイナーに報酬を支払います。PoWと同様に、マイナーはブロック生成資格を決める抽選に参加するために問題に取り組みます。

純粋なPoWでは、この抽選は通常所与の目標値に対して（カウンターとともに）チャレンジを繰り返しハッシュすることで構成されます。この抽選にはハッシュ値が目標以下になることで勝利します。純粋なPoWでは、1つのクエリは高速で、目標に達する可能性は非常に小さいことに注意してください。

さまざまな理由、たとえば複数のブロックが同時に発行される可能性を最小限に抑えるためなどにより、PoUWでも1つのクエリは（比較的）高速に保つことが勧められます。一方、クライアント問題のインスタンスは解決しにくいものである必要があります。これで計算のアウトソーシングが魅力的になります。したがって、PoUWは自然と、全体として複雑であっても、小さな「均一」のステップに分割できる計算のクラスを目指すことになります。各ステップは同量である（と予想される）、純粋なPoWのクエリ1つに匹敵する作業を必要とします。

SLS（Stochastic Local Search）はこのような計算の明確なクラスです。SLSアルゴリズムは、効率的な決定論的アルゴリズムが知られていない最適化問題に適用されます。むしろ、SLSは、特定の発見手法を使うソリューションを徐々に最適化しようと試みているソリューションスペースでランダムウォークを実行します。ランダムウォークのすべての探索ステップは同じ計算の異なるインスタンスであるため、上記の要件を鑑みると、SLSはPoUWの優れた候補となります。さらにSLSは、ロジスティクス計画、イベントスケジューリングなどの分野における実体経済アプリケーションと実際に高い関連性を持ちます。

PoWからPoUWへの段階的遷移

マイナーはブロックチェーンに投稿されたクライアント問題のインスタンスをピックアップして解決します。問題の更新は、一定数の探索ステップの後、または適切な解決策が見つかった場合など、何らかの終了基準が発生するまでブロックチェーンに継続的に保存されます。

この設定で、純粋なPoWをPoUWに変換する方法を再構築します。

1.純粋なPoWでは、マイナーは新しいブロックによって最長のチェーンを拡張し、特定のターゲットに対して（ブロックに含まれるカウンターを変更することによって）新しいブロックを繰り返しハッシュする必要があります。最初のステップとして、ハッシュの反復をオンチェーンに保存された前回の探索状態S上にあるSLS探索ステップMの計算の反復に置き換えます。ここではブロックが探索ステップのランダムシードを決定します。図1（右側）を見てください。前回の探索状態Sは、ランダム化された探索ステップMによって、状態sとともにブロックのハッシュ化で得られたシードを使用して拡張され、新しい（おそらくより良い）探索状態s’が生成されます。このプロセスは、まだ特定されていない状態「?」が満たされるまで繰り返され、マイナーによるブロックの発行を可能にします。このプロセスの間、マイナーはこの反復プロセスで見つけた最良の状態s_bestを追跡します。

図1：ターゲットTに対するハッシュ（PoW、左）反復探索ステップM（PoUW、右）

2.欠落している成功条件「？」を修正します。具体的な計算によって偏りのない優れた確率的特性を実現するために、探索ステップの後に「ポストハッシュ」を探索ステップに追加することにより、ブロックの検索は計算された状態s'のクォリティから切り離されます (初期シードを再利用します) - 図2を参照 -。このハッシュ値がターゲットT₃未満の場合、ブロックは発行認定されます。現在最良のソリューションs_bestに加えて、これによりブロックと一緒に発行されるべき新しい状態s_Tが導入されます。この状態はT₃未満のハッシュへ導き、ブロック発行認定を証明します。s_bestのみが状態の更新（マイナーによってさらに探索される）として機能し、s_Tはブロック発行認定の証拠としてのみ機能することに注意してください。

図2：ランダム化されたブロック発行の認定

3.MはHよりも計算が困難であること、Mのすべてのインスタンスが同量の作業を必要とするわけではないということを考慮すると、敵対者は誠実なマイナーに比べてM計算を高速化するシードをグラインドして、ブロックをより早く生成する上で優位に立ち、システムのセキュリティを低下させる可能性があります。このリスクを、初期ハッシュがターゲットT₁未満である必要があるようにすることによって軽減させます。たとえば、探索ステップMを実行する前に、マイナーは純粋なPoWに沿ってブロックカウンターを変化させ、低いハッシュ値を見つける必要があります。図3を見てください。具体的には、T₁はターゲットT₁未満のハッシュ値を見つけるために予想される作業が、複雑なM計算にかかる時間の最悪のケースと少なくとも同じぐらいかかるように選ばれています。すなわち、簡単なインスタンスをグラインドすることが、「不便な」Mインスタンスの計算と同じくらい高くつくのです。B_ctr、s_best、s_Tの3点セットが上記の条件を満たし、PoUWを構成します。

図3：ターゲットT₁に対する事前ハッシュによりグラインドを防止

4.純粋なPoWとは対照的に、マイナーのM計算を繰り返すことによってノードにPoUWを検証させる余裕はありません。これは、計算が大量に複製されることを意味し、システムにおける真に有益な計算の割合が劇的に減少するためです。これを回避するために、発行可能なブロックを「発見」すると、マイナーにはSNARG（簡潔でノンインタラクティブな引数）を作成して成功を証明することが要求されます。これには、検証の複雑性がM計算の複雑性と無関係になるという利点があります。さらに、最良のソリューションs_bestの計算の正確性が証明されます。図4を見てください。

図4：ノンインタラクティブ証明を追加することにより分散検証を最小限に抑える

5.分散型同時マイニングを活用するために、SLSインスタンスは（たとえば、複数の探索パスを維持することによって）並列化されます。さもなければ、すべてのマイナーが同時に同じ状態を探索し、多くの（本質的に）冗長な探索ステップが導入されるためです。 セキュリティ上の理由から、標準の「ナカモト」PoWでのブロック生成は低速で、状態の更新はブロックに関連付けられていることに注意してください。一方、状態の更新は、マイナーが「廃棄された」状態を探索することを避けるために高速で処理される必要があります。したがって、ここで2種類のブロックが導入されます。1つはナカモトコンセンサスと同じ機能を持つ「見つけることが困難な」ランキングブロックで、もう1つは最終的にランキングブロックにより参照されるトランザクションのような機能を持つ「簡単に見つかる」インプットブロックです。この方法により、マイナーの最良のソリューションが比較的速く広まり、すべてのマイナーが最新情報を得ることができます。特に、これは最初に「簡単な」ターゲットT₃に対する最終ハッシュを評価することにより達成されます。下図の場合、これは発行可能なブロックとして認定されますが、ターゲットが「より困難な」ターゲットT₂を下回る場合のみ、このブロックは「コンセンサスに関連する」ランキングブロックとして認められ、そうでない場合にはインプットブロックとして定義されます。図5を見てください。

図5：T₂未満のポストハッシュは、ブロックをランキングブロックとして認定。T₂とT₃の間のポストハッシュは、ブロックをインプットブロックとして認定

プロトコルのプロパティ

プロトコルの安全性および有用性に関する詳細な分析は、本稿の範囲外となります。それでも、プロトコルがなぜ安全であるのか、その直感的な理由をここで繰り返し、プロトコルの効率を調べて結論付けることは有益でしょう。

ブロックチェーンの安全性

• グラインド：敵対者は計算が容易なMインスタンスをグラインドしても利益を得ません。これは、任意のインスタンスでMを計算することが、T₁未満の新しい事前ハッシュを見つけることと（予想上）同レベルの難易度となるように、事前ハッシュの閾値T₁を設定することにより達成できます。
• 敵対者の優位に対する抵抗：誠実な当事者よりもPoUWを高速で計算するという点において、敵対者の優位は限定的です。これは、ブロックの成功を実際の計算から切り離し、ターゲットT₁未満で事前ハッシュすることで達成できます。特に、GKL14、PSS16の標準モデルに従い、敵対者がMを誠実な当事者よりも速く計算することに利点がないと仮定すると、プロトコルは、ビットコインのように、ネットワーク専用の小規模な計算能力を制御する敵対者を容認します。対照的に、敵対者がすべてのインスタンスでコストをかけずにMを計算できる場合でも、プロトコルは、すべての計算リソースの最大3分の1を制御する敵対者を許容します。これは、それでも彼らはT₁に対する事前ハッシュのために「半分の」コストで操作することになるためです。
• 可変難易度：PoW/PoUWコンセンサスプロトコルでは、ブロックを見つける難易度を、システム専用の現在の計算力のレベルに継続的に適応させる必要があります。Ofelimosでは、探索ステップの後に実行される（1つの）ポストハッシュにターゲットT₂を適合させることで、これを簡単に実現できます。これで、ランキングブロックの発行が認定されます。

効率

• 頻繁な更新：ランキングブロックとインプットブロックの分離により、状態の更新は素早く拡散されます。
• 有用性：ここでは、SLS問題に費やされる全体的な計算作業の比率を有用性と定義します（これは単純化したものであり、詳細な定義と分析については論文を参照してください）。システム内の「役に立たない」作業の主な原因は、T₁に対する事前ハッシュの反復とSNARGの計算です。以下に注意してください。
  • ポストハッシュは、Mの呼び出しごとに1回だけ実行され、Mの複雑さと比較して、実用的な理由から無視できます。
  • SNARGは、多くのM呼び出しのうち2つ、すなわちs_T（ブロックの成功）とs_best（最良の解決策）を生成するものに関してのみ計算する必要があります。したがって、ブロックの成功を決定する閾値T₃を下げれば、状態の更新は遅くなるものの、SNARGの計算によって発生するオーバーヘッドは最小限に抑えることができます。

有用性はMの特性次第です。Mの実行時間が十分に集中している場合、事前ハッシュの難度をMの平均的なケースの複雑さに近づけるように設定できます。上記の観察を考慮すると、マイナーは時間の約半分をMの計算に費やすため、約1/2の有用性が達成されます。典型的なSLS問題の多くはここに分類されるでしょう。ただし、Mが「良いふるまい」をしない場合、有用性はゼロに近くなる可能性があります。したがって、具体的なSLSアルゴリズムとその探索ステップMの選択は、合理的な有用性を備えたPoUWを実現するために重要です。

まとめ

Ofelimosは、証明可能な安全性をもつ有用なPoUWに向けた最初のステップに過ぎません。現在の作業では、高度な腐敗のレベルに対して証明可能な安全性が容易に得られますが、高い有用性を実証できる最適化問題の適切なクラスを提供するには、アルゴリズム側でさらに多くの研究が必要です。

研究論文「Ofelimos:Combinatorial Optimization via Proof-of-Useful-Work（Ofelimos：プルーフオブユースフルワークによる組み合わせ最適化）」は2021年10月に最初に公開されました。

本稿の執筆にご協力いただいたMatthias Fitzi氏に感謝します。