作業証明

プルーフ・オブ・ワーク（プルーフ・オブ・ワークとも表記され、PoWと略される）は、ある当事者（証明者）が他の当事者（検証者）に対して、特定の計算作業の一定量が費やされたことを証明する暗号学的証明の一形態である。 ^{[ 1 ]}検証者は、その後、最小限の労力でこの支出を確認できる。この概念は、サービス要求者に何らかの作業（通常はコンピュータによる処理時間を意味する）を要求することにより、ネットワーク上のサービス拒否攻撃やスパムなどの他のサービス悪用を阻止する方法として、1993 年にMoni Naor とCynthia Dworkによって初めて提案された。Cynthia Dwork と Moni Naor の研究を拡張し、Adam Back は1997 年に電子メールスパムに対する保護としてHashcashと呼ばれるプルーフ・オブ・ワーク・システムを正式に記述した。「プルーフ・オブ・ワーク」という用語は、 Markus JakobssonとAri Juelsによる 1999 年の論文で初めて造語され、形式化された。^{[ 2 ] [ 3 ]}この概念は、 2004 年にハル・フィニーによって、160 ビットの安全なハッシュアルゴリズム 1 (SHA-1) を使用した「再利用可能なプルーフ・オブ・ワーク」のアイデアを通じてデジタル トークンに適用されました。^{[ 4 ]}

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

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

プルーフ・オブ・ワーク・アルゴリズムの目的は、特定の作業が実行されたことや計算パズルが「解決」されたことを証明することではなく、そうするために大きなエネルギーとハードウェア制御要件を確立することで、データの操作を抑止することです。^{[ 6 ]}プルーフ・オブ・ワーク・システムは、経済的および社会的利益を補償しない市場電力価格に反映されない外部性を生み出すと主張する一部の環境保護主義者から批判されています。^{[ 8 ]}プルーフ・オブ・ワーク・マイニングの中断可能な負荷特性は、需要応答サービスを提供し、特定の市場およびグリッド条件下で変動する再生可能エネルギーの統合をサポートします。^{[ 9 ]}

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

Hashcashのシステムは、特定の基準を満たすハッシュ値を見つけるという概念に基づいていた。この作業には計算コストがかかるため、「プルーフ・オブ・ワーク」として機能した。大量のメールを送信するのに計算コストがかかるようにすることで、スパムメールを減らすことができるというのがその狙いだった。

Hashcashで使用されている一般的なシステムの一つは、部分的なハッシュ反転を利用して計算が行われたことを証明し、電子メール送信の際の信頼の証としています。例えば、以下のヘッダーは、 2038年1月19日にメッセージを送信するために約²⁵²回のハッシュ計算が行われたことを示しています。calvin@comics.net

X-Hashcash: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE

スタンプのSHA-1ハッシュ（コロンとそれに続く数字「1」までの空白文字を含むヘッダー名を除く）が52個のバイナリゼロ、つまり13個の16進数ゼロで始まることを確認することでX-Hashcash:、単一の計算で検証できます。

0000000000000756af69e2ffbdb930261873cd71

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

プルーフ・オブ・ワークは、デジタル不正行為に対抗するための初期の取り組みに理論的な起源を持ち、当初のスパム対策の目的を超えて、セキュリティ、アクセシビリティ、およびより広範なアプリケーションに対応するために、時間の経過とともに大きく進化しました。このアイデアは、1993 年に迷惑メールの抑止策として初めて登場しましたが、プルーフ・オブ・ワークがブロックチェーン ネットワークの基盤となる可能性を確固たるものにしたのは、サトシ・ナカモトの 2008 年のホワイトペーパー「Bitcoin: A Peer-to-Peer Electronic Cash System」^{[ 13 ]}でした。この発展は、安全で信頼不要なシステムに対する需要の高まりを反映しています。

プルーフ・オブ・ワークが最初に登場したのは1993年で、シンシア・ドワークとモニ・ナオールが、送信者に計算負荷の高いタスクを実行させることで迷惑メールを抑制するシステムを提案した時である。彼らの論文「迷惑メール処理または対策による価格設定」^{[ 14 ]}では、解くのは困難だが検証は容易なモジュラー平方根の計算などの方法を概説し、プルーフ・オブ・ワークの非対称性の基本原理を確立した。この非対称性はプルーフ・オブ・ワークの有効性にとって極めて重要であり、スパム送信などのタスクが攻撃者にとってコストのかかるものになる一方で、正当なユーザーにとっては検証が効率的であることを保証する。

この概念的な基礎は、1997年にアダム・バックのHashcashで実用化されました。Hashcashは、送信者がSHA-1アルゴリズムの部分的なハッシュ反転を計算し、一定数の先頭ゼロを持つハッシュを生成するシステムです。バックの論文「Hashcash: A Denial of Service Counter-Measure」^{[ 15 ]}で説明されているHashcashは、スパムを抑止するための計算コストを課しつつ、受信者が作業を簡単に確認できるようにすることで、暗号化とブロックチェーン技術におけるその後のプルーフ・オブ・ワーク実装の重要な基盤を築きました。

2009年にサトシ・ナカモトによって発表されたビットコインは、ハッシュキャッシュのプルーフ・オブ・ワークを暗号通貨に適用することで、画期的な転換点となりました。ナカモトのビットコインのホワイトペーパーでは、SHA-256アルゴリズムを用いたシステムが概説されており、マイナーは暗号パズルを解いてブロックチェーンにブロックを追加し、その過程で報酬を得るという仕組みになっています。ハッシュキャッシュの静的な証明とは異なり、ビットコインのプルーフ・オブ・ワークアルゴリズムは、前のエポックでブロックをマイニングするのにかかった平均時間に基づいて難易度を動的に調整し、約10分という一定のブロック生成時間を確保することで、改ざん不可能なチェーンを構築します。この革新により、プルーフ・オブ・ワークは単なる抑止力から、分散型ネットワークにおけるコンセンサス機構へと変化し、計算作業よりも金銭的なインセンティブを重視するようになりました。

当初は標準的なCPUでマイニングされていたビットコインは、急速にGPU、FPGA、そして最終的にはASICへと移行し、SHA-256パズルを解く際に一般的なハードウェアをはるかに凌駕する性能を発揮するようになった。

ビットコインが専用ハードウェアへの依存度を高めていることに対処するため、ライトコインはハッシュキャッシュのハッシュ関数をSHA-256からScryptに変更しました。コリン・パーシバルによって開発され、技術仕様「The scrypt Password-Based Key Derivation Function」^{[ 16 ]}に詳細が記載されているScryptは、メモリ集約型のアルゴリズムとして設計されており、計算には中程度のRAMが必要でした。汎用ハードウェアを持つユーザーがマイニングに容易にアクセスできるようにするというライトコインの目標は長くは続きませんでした。マイニングはCPUからGPU、FPGAを経てASICへと移行していったからです。

プルーフ・オブ・ワーク・プロトコルには2つの種類がある。

• チャレンジ・レスポンス・プロトコルは、要求者（クライアント）と提供者（サーバー）間の直接的な対話型リンクを前提としています。提供者は、例えばプロパティを持つセット内の項目など、チャレンジを選択します。要求者は、そのセット内から関連するレスポンスを見つけ、提供者に返送して検証します。チャレンジは提供者によってその場で選択されるため、難易度を現在の負荷に合わせて調整できます。チャレンジ・レスポンス・プロトコルに既知の解（提供者によって選択されたもの）がある場合、または限定された探索空間内に存在することがわかっている場合は、要求者側の処理は限定的になります。

• 解検証プロトコルは、そのような関連性を前提としていません。そのため、要求者が解を求める前に、問題自体を自ら設定する必要があり、提供者は問題の選択と見つかった解の両方を検証しなければなりません。このような方式のほとんどは、Hashcashのような、制限のない確率的反復手順です。

既知解プロトコルは、非限定確率プロトコルに比べて分散がやや低くなる傾向があります。これは、矩形分布の分散が、同じ平均値を持つポアソン分布の分散よりも低いためです。分散を低減するための一般的な手法としては、複数の独立したサブチャレンジを用いることが挙げられます。複数のサンプルの平均値は、分散が低くなるためです。

時間制限パズルなど、固定費用が発生する機能もあります。

さらに、これらのスキームで使用される基盤となる関数は以下のとおりです。

• CPUバウンドとは、計算がプロセッサの速度で実行されることであり、その速度は時間的にも大きく異なり、ハイエンドサーバーからローエンドの携帯機器まで様々である。^{[ 17 ]}
• メモリバウンド^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]}では、計算速度はメインメモリへのアクセス (レイテンシまたは帯域幅のいずれか) によって制限され、そのパフォーマンスはハードウェアの進化に対してあまり敏感ではないと予想されます。
• ネットワークバウンド^{[ 22 ]}とは、クライアントが計算をほとんど行わず、最終的なサービスプロバイダに問い合わせる前にリモートサーバからトークンを収集する必要がある場合を指します。この意味では、作業は要求者によって実際に実行されるわけではありませんが、必要なトークンを取得するのに遅延が発生するため、いずれにしても遅延が生じます。

最後に、一部のPoWシステムでは、秘密鍵などの秘密情報を知っている参加者が低コストでPoWを生成できるショートカット計算機能を提供しています。これは、メーリングリストの管理者が高額な費用をかけずにすべての受信者に対して切手を生成できるようにするためです。このような機能が望ましいかどうかは、使用シナリオによって異なります。

既知のプルーフ・オブ・ワーク関数の一覧を以下に示します。

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

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

最適化可能なプルーフ・オブ・ワーク（OPoW）は、ネットワークの不安定性や中央集権化を引き起こすことなく、プルーフ・オブ・ワークのアルゴリズム自体を最適化できるプルーフ・オブ・ワークの一種です。マイナーが任意の暗号パズルを解くために競い合う標準的なPoWや、計算努力を現実世界の問題に向けるPoUWシステムとは異なり、OPoWは、ブール充足可能性問題、容量制約付き車両経路問題、ナップサック問題などの計算科学の問題から抽出された複数のプルーフ・オブ・ワーク課題を統合し、ブロック報酬を比例配分する影響度計算によってそれらを結びつけます。このメカニズムは、2つのカテゴリーの参加者にインセンティブを与えます。1つは、最も効率的なアルゴリズムを採用することで報酬を得る、ソリューションを計算するマイナー、もう1つは、改良されたアルゴリズムを開発して提出し、マイナーによる採用に基づいて報酬を得るアルゴリズム貢献者です。計算問題の解決とブロック生成を切り離すことで、OPoWは1ブロックあたり多数のソリューションを見つけることを可能にし、アルゴリズムの人工的な市場を効果的に作り出します。^{[ 31 ] [ 32 ]}

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

エネルギー消費量

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

Miners compete to solve crypto challenges on the bitcoin blockchain, and their solutions must be agreed upon by all nodes and reach consensus. The solutions are then used to validate transactions, add blocks and generate new bitcoins. Miners are rewarded for solving these puzzles and successfully adding new blocks. However, the Bitcoin-style mining process is very energy intensive because the proof of work is shaped like a lottery mechanism. The underlying computational work has no other use but to provide security to the network that provides open access and has to work in adversarial conditions. Miners have to use a lot of energy to add a new block containing a transaction to the blockchain. The energy used in this competition is what fundamentally gives Bitcoin its level of security and resistance to attacks. Also, miners have to invest computer hardwares that need large spaces as fixed cost.^[47]

In January 2022 vice-chair of the European Securities and Markets Authority Erik Thedéen called on the EU to ban the proof of work model in favor of the proof of stake model due its lower energy emissions.^[48]

In November 2022 the state of New York enacted a two-year moratorium on cryptocurrency mining that does not completely use renewable energy as a power source for two years. Existing mining companies will be grandfathered in to continue mining without the use of renewable energy but they will not be allowed to expand or renew permits with the state. No new mining companies that do not completely use renewable energy will be allowed to begin mining.^[49]

• Bitcoin
• Bitmessage
• Cryptocurrency
• Proof of authority
• Proof of burn
• Proof of personhood
• Proof of space
• Proof of stake
• Proof of elapsed time
• Consensus (computer science)

• ^On most Unix systems this can be verified with echo -n 1:52:380119:calvin@comics.net:::9B760005E92F0DAE | openssl sha1