仕事の証明

プルーフ オブ ワーク( PoW ) は、暗号 証明の一種で、一方の当事者 (証明者) が他方の当事者 (検証者) に対して、特定の計算努力が一定量費やされたことを証明するものです。^[1] 検証者は、その後、最小限の労力でこの支出を確認できます。この概念は、サービス要求者に何らかの作業 (通常はコンピューターによる処理時間) を要求することで、ネットワーク上のスパムなどのサービス拒否攻撃やその他のサービス乱用を阻止する方法として、1993 年にMoni NaorとCynthia DworkによってHashcashに初めて実装されました。「プルーフ オブ ワーク」という用語は、Markus Jakobssonと Ari Juels によって 1999 年の論文で初めて造語され、形式化されました。^{[2] [3]}この概念は、160 ビットのセキュア ハッシュ アルゴリズム 1 (SHA-1) を使用した「再利用可能なプルーフ オブ ワーク」というアイデアを通じて、2004 年にHal Finneyによってデジタル トークンに採用されました。 ^{[4] [5]}

プルーフ・オブ・ワークは、後にビットコインによって、許可のない分散型ネットワークにおける合意形成の基盤として普及しました。このネットワークでは、マイナーがブロックを追加して新しい通貨を採掘するために競争し、各マイナーは費やした計算努力に比例した成功確率を経験します。PoWとPoS（プルーフ・オブ・ステーク）は、シビル抑止メカニズムとして最もよく知られている2つです。暗号通貨の文脈では、これらは最も一般的なメカニズムです。^[6]

プルーフ・オブ・ワーク方式の重要な特徴は、その非対称性です。つまり、作業（計算）は、証明者または要求者側では適度に困難（かつ実行可能）でなければなりませんが、検証者またはサービスプロバイダーにとっては簡単にチェックできるものでなければなりません。この考え方は、CPUコスト関数、クライアントパズル、計算パズル、またはCPU価格設定関数とも呼ばれます。もう1つの一般的な特徴は、ネットワークに計算能力を割り当てると暗号通貨という形で価値が与えられるインセンティブ構造が組み込まれていることです。 ^{[7] [8]}

プルーフ・オブ・ワークアルゴリズムの目的は、特定の作業が実行されたことや計算パズルが「解決」されたことを証明することではなく、それを可能にするために大きなエネルギーとハードウェア制御要件を確立することでデータの操作を阻止することです。^[7]プルーフ・オブ・ワークシステムは、そのエネルギー消費について環境保護論者から批判されてきました。^[9]

プルーフ・オブ・ワーク（PoW）の概念は、スパム対策とサービス拒否攻撃防止に関する初期の研究に端を発しています。PoWの最も初期の実装の1つは、 1997年に英国の暗号学者アダム・バックによって作成されたハッシュキャッシュです。 ^[10]これは、メール送信者に小さな計算タスクの実行を要求するスパム対策メカニズムとして設計され、メールを送信する前にリソース（CPU時間の形で）を費やしたことを効果的に証明します。このタスクは正当なユーザーにとっては些細なことですが、大量のメッセージを送信しようとするスパマーにとっては大きなコストを課します。

Hashcash のシステムは、特定の基準を満たすハッシュ値を見つけるという概念に基づいていました。このタスクは計算作業を必要とするため、「作業の証明」として機能します。大量の電子メールを送信するのに計算コストがかかるようにすることで、スパムが削減されるという考えでした。

Hashcash で使用されている一般的なシステムの 1 つは、部分的なハッシュ反転を使用して計算が行われたことを証明し、電子メールを送信するための善意のトークンとして使用します。たとえば、次のヘッダーは、 2038 年 1 月 19 日にメッセージを送信するために約 2 ^{52 回の}calvin@comics.netハッシュ計算が行われたことを示しています。

X-ハッシュキャッシュ: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE

これは、スタンプのSHA-1ハッシュ（コロンとそれに続く数字「1」までの空白文字を含むヘッダー名を省略X-Hashcash:）が52個の2進ゼロ、つまり13個の16進ゼロで始まることを確認することで、1回の計算で検証されます。^[1]

0000000000000756af69e2ffbdb930261873cd71

PoWシステムが実際にスパム問題のような特定のサービス拒否問題を解決できるかどうかは議論の余地がある。^{[11] [12]} システムは、スパムメールの送信をスパマーにとって目障りなほど非生産的なものにする必要があるが、正当なユーザーがメッセージを送信することを妨げてはならない。言い換えれば、正当なユーザーはメールを送信する際に何の問題も経験しないが、メールスパマーは一度に多くのメールを送信するためにかなりの量の計算能力を費やす必要がある。プルーフオブワークシステムは、ハッシュキャッシュに似たシステムを使用するビットコインなどの他のより複雑な暗号化システムでも使用されている。 ^[11]

プルーフ・オブ・ワーク プロトコルには 2 つのクラスがあります。

• チャレンジ レスポンスプロトコルは、リクエスタ (クライアント) とプロバイダ (サーバー) 間の直接的なインタラクティブ リンクを想定しています。プロバイダは、プロパティを持つセット内のアイテムなどのチャレンジを選択し、リクエスタはセット内の関連するレスポンスを見つけます。このレスポンスはプロバイダによって返送され、チェックされます。チャレンジはプロバイダによってその場で選択されるため、その難易度は現在の負荷に合わせて調整できます。チャレンジ レスポンス プロトコルに既知のソリューション (プロバイダによって選択) がある場合、または制限された検索空間内に存在することがわかっている場合は、リクエスタ側の作業が制限される場合があります。

• 解決検証プロトコルはそのようなリンクを想定していません。その結果、要求者が解決策を探す前に問題を自ら課す必要があり、提供者は問題の選択と見つかった解決策の両方を確認する必要があります。このようなスキームのほとんどは、Hashcashなどの無制限の確率的反復手順です。

既知解プロトコルは、矩形分布の分散がポアソン分布（同じ平均）の分散よりも低いため、無制限の確率プロトコルよりも分散がわずかに低くなる傾向があります。 ^{[詳細な説明が必要]} 分散を減らすための一般的な手法は、複数のサンプルの平均は分散が低くなるため、複数の独立したサブチャレンジを使用することです。

タイムロックパズルなどの固定料金機能もあります。

さらに、これらのスキームで使用される基礎となる機能は次のとおりです。

• CPUバウンドでは、計算はプロセッサの速度で実行されますが、プロセッサの速度は時間によって大きく異なり、ハイエンドのサーバーからローエンドのポータブルデバイスまでさまざまです。^[13]
• メモリバウンド^{[14] [15] [16] [17]}では、計算速度はメインメモリアクセス（レイテンシまたは帯域幅）によって制限され、そのパフォーマンスはハードウェアの進化にあまり影響されないと予想されます。
• ネットワークバウンド^[18]とは、クライアントがほとんど計算を実行せずに、最終的なサービスプロバイダーに問い合わせる前にリモートサーバーからいくつかのトークンを収集する必要がある場合です。この意味では、作業は実際にはリクエスターによって実行されませんが、必要なトークンを取得するための待ち時間のために、いずれにしても遅延が発生します。

最後に、一部の PoW システムでは、秘密 (通常は秘密鍵) を知っている参加者が安価な PoW を生成できるショートカット計算を提供しています。これは、メーリング リストの所有者が、高額なコストをかけずに受信者ごとにスタンプを生成できるというものです。このような機能が望ましいかどうかは、使用シナリオによって異なります。

既知のプルーフ・オブ・ワーク関数のリストは次のとおりです。

• 大きな素数を法とする整数平方根^{[3] [疑わしい–議論する]}
• フィアット・シャミール署名を弱める^[3]
• オング・シュノア・シャミール署名はポラードによって破られた^[3]
• 部分ハッシュ反転^{[19] [20] [2]}この論文は、プルーフ・オブ・ワークの考え方を形式化し、「ブレッドプディングプロトコルの依存的な考え方」、つまり「再利用可能なプルーフ・オブ・ワーク」（RPoW）システムを導入している。^[21]
• ハッシュシーケンス^[22]
• パズル^[23]
• ディフィー・ヘルマンベースのパズル^[24]
• 中程度^[14]
• エムバウンド^[15]
• 北海道^[16]
• カッコウサイクル^[17]
• マークルツリーベース^[25]
• ガイドツアーパズルプロトコル^[18]

IACRカンファレンスCrypto 2022で、研究者らは「有用な作業の証明」（PoUW）に基づくコンセンサスメカニズムを備えたブロックチェーンプロトコルであるOfelimosについて説明した論文を発表しました。Ofelimosは、取引を検証するために複雑だが本質的に役に立たないパズルを解くためにマイナーがエネルギーを消費するのではなく、分散型最適化問題ソルバーを提供しながらコンセンサスを達成します。このプロトコルは、PoUWコンポーネントとして使用されるローカルサーチアルゴリズムであるDoubly Parallel Local Search（DPLS）を中心に構築されています。この論文では、ブール問題を解決するローカルサーチアルゴリズムであるWalkSATのバリアントを実装する例が示されています。^[26]

2009 年、ビットコインネットワークがオンラインになりました。ビットコインは、フィニーの RPoW と同様に、ハッシュキャッシュPoW をベースにしたプルーフ オブ ワーク デジタル通貨です。ただし、ビットコインでは、コインの転送を追跡するための分散型 P2P プロトコルによって二重支払い保護が提供され、RPoW で使用されるハードウェア トラステッド コンピューティング機能ではありません。ビットコインは計算によって保護されているため、信頼性が高くなります。ビットコインは、ハッシュキャッシュ プルーフ オブ ワーク機能を使用して個々のマイナーによって「採掘」され、P2P ビットコイン ネットワークの分散型ノードによって検証されます。難易度は、ブロック タイムを目標タイム付近に保つために定期的に調整されます。^{[引用が必要]}

ビットコインの誕生以来、プルーフ・オブ・ワークはピアツーピア暗号通貨の主な設計となっている。研究では暗号通貨マイニングの総エネルギー消費量を推定している。^{[28] PoWメカニズムには膨大な量のコンピューティングリソースが必要であり、かなりの量の電力を消費する。}ケンブリッジ大学の2018年の推定によると、ビットコインのエネルギー消費量はスイスの消費量に匹敵する。^[6]

ブロックチェーンに追加される各ブロックは、特定のトランザクションを含むブロックから始まり、そのトランザクションの確認と呼ばれます。理想的には、暗号通貨で支払いを受け取る商人やサービスは、支払いが行われたと想定する前に、少なくとも1つの確認がネットワーク上に配布されるのを待つ必要があります。商人が待つ確認が多いほど、攻撃者がブロックチェーン内のトランザクションを正常に元に戻すことが難しくなります。ただし、攻撃者がネットワーク全体のパワーの半分以上を制御している場合は除きます。その場合、51％攻撃と呼ばれます。^[29]

ビットコインコミュニティ内には、マイニングプールで協力して作業するグループがあります。^[30]一部のマイナーは、 PoWに特定用途向け集積回路（ASIC）を使用しています。 ^[31]マイニングプールと特殊なASICへのこの傾向により、最新のASIC、近くの安価なエネルギー源、またはその他の特別な利点にアクセスできないほとんどのプレイヤーにとって、一部の暗号通貨のマイニングは経済的に実行不可能になっています。^[32]

一部のPoWはASIC耐性があると主張している^[33]。つまり、ASICがGPUなどの汎用ハードウェアに対して得られる効率性の向上を1桁未満に制限する。ASIC耐性は、汎用ハードウェア上でのマイニングを経済的に実行可能な状態に保つという利点があるが、攻撃者が大量の特殊化されていない汎用処理能力へのアクセスを一時的に借りて、暗号通貨に対して51％攻撃を仕掛けることができるというリスクも伴う。^[34]

マイナーはビットコインブロックチェーン上の暗号の課題を解決するために競争し、その解決策はすべてのノードによって合意され、コンセンサスに達する必要があります。その後、その解決策はトランザクションの検証、ブロックの追加、および新しいビットコインの生成に使用されます。マイナーはこれらのパズルを解き、新しいブロックを正常に追加することで報酬を得ます。ただし、ビットコインスタイルのマイニングプロセスは、プルーフオブワークが宝くじのメカニズムのような形をしているため、非常にエネルギーを消費します。基礎となる計算作業は、オープンアクセスを提供するネットワークにセキュリティを提供する以外に用途がなく、敵対的な状況で動作する必要があります。マイナーは、トランザクションを含む新しいブロックをブロックチェーンに追加するために多くのエネルギーを使用する必要があります。この競争で使用されるエネルギーは、基本的にビットコインにそのレベルのセキュリティと攻撃に対する耐性を与えるものです。また、マイナーは固定費として大きなスペースを必要とするコンピューターハードウェアに投資する必要があります。^[35]

2022年1月、欧州証券市場監督局の副議長エリック・テディーンは、EUに対し、エネルギー排出量が少ないという理由でプルーフ・オブ・ワークモデルを禁止し、代わりにプルーフ・オブ・ステークモデルを導入するよう求めた。^[36]

2022年11月、ニューヨーク州は、再生可能エネルギーを電源として完全に使用しない暗号通貨マイニングを2年間禁止する2年間のモラトリアムを制定しました。既存のマイニング会社は、再生可能エネルギーを使用せずにマイニングを継続できますが、州からの許可の拡大や更新は許可されず、再生可能エネルギーを完全に使用しない新しいマイニング会社もマイニングを開始することは許可されません。^[37]

• ビットコイン
• ビットメッセージ
• 暗号通貨
• 権限の証明
• 火傷の証拠
• 人格の証明
• スペースの証明
• ステーク証明
• 経過時間の証明
• コンセンサス（コンピュータサイエンス）

• ^ほとんどのUnixシステムでは、これを次のように検証できます。echo -n 1:52:380119:calvin@comics.net:::9B760005E92F0DAE | openssl sha1

• Wayback Machineの Finney のシステム(2007 年 12 月 22 日アーカイブ)
• ビット ゴールドビット ゴールド。作業証明機能とこれらの機能の使用によって生じるマシン アーキテクチャの問題に基づく完全な通貨システム (生成、保管、分析、転送を含む) について説明します。
• 簡易支払い検証 (SPV) 用の Merkle Proof 標準フォーマット。