プルーフ・オブ・ワークシステム

プルーフ・オブ・ワーク（PoW）とは

プルーフ・オブ・ワーク（Proof-of-Work、PoW）は、サービスのリクエストに対して、一定の計算処理を要求することで、DoS攻撃やスパムなどのサービスの濫用を抑制する経済的な手段です。この概念は1993年にシンシア・ドワークとモニー・ナオールによって提唱され、1999年にマーカス・ヤコブソンとアリ・ジュルズによって「プルーフ・オブ・ワーク」という用語が作られました。初期の例としては、ソロモン諸島の貝貨が挙げられます。

PoWの重要な特徴は、その非対称性にあります。リクエスト側は一定の計算コストを必要としますが、サービス提供者側は容易にその正当性を検証できます。この仕組みは、CPUコスト関数、クライアントパズル、計算パズル、CPU価格関数などとも呼ばれます。

PoWは、人間が容易に解決できるCAPTCHAとは異なり、コンピュータによる計算処理を必要とします。また、CPU時間の代わりに、メモリやディスク容量を証明するプルーフ・オブ・スペース（PoS）、帯域幅を証明するプルーフ・オブ・バンドワイズ、データの保持を証明するプルーフ・オブ・オーナシップなど、さまざまなバリエーションが存在します。

PoWの仕組み

PoWの代表的な例として、ビットコインのマイニングやHashcashが挙げられます。Hashcashでは、電子メール送信時に、特定のハッシュ値を持つヘッダーを付与することで、作業の完了を証明します。例えば、以下のヘッダーは、252回のハッシュ計算を表しています。


X-Hashcash: 1:52:380119:[email protected]:::9B760005E92F0DAE

このヘッダーのSHA-1ハッシュ値が、先頭に13桁の0が続くことで検証されます。


0000000000000756af69e2ffbdb930261873cd71


PoWシステムがスパム対策に有効かどうかは議論の余地がありますが、スパマーにとってはスパム送信が非効率になり、正当なユーザーにとってはメッセージ送信の妨げにならないように設計される必要があります。

PoWプロトコルの種類

PoWプロトコルには、大きく分けて以下の2つのクラスが存在します。

1. チャレンジ・レスポンスプロトコル: リクエスターとプロバイダー間で直接対話を行うプロトコルです。プロバイダーはチャレンジを選択し、リクエスターは対応するレスポンスを見つけて返信します。このプロトコルでは、難易度を動的に調整できます。

2. ソリューション検証プロトコル: リクエスターが問題を自ら課し、プロバイダーは問題とソリューションの両方を確認するプロトコルです。Hashcashのように、確率的な反復手続きが用いられることが多いです。


また、PoWで使用される基本機能には、CPUバウンド、メモリバウンド、ネットワークバウンドなどがあります。さらに、秘密鍵を持つ参加者に対して、PoW生成のショートカットを提供するシステムも存在します。

PoW機能のリスト

PoW機能として、以下のようなものが挙げられます。

Integer square root modulo a large prime
フィアット-シャミールの署名を弱める
Ong–Schnorr–Shamir signature broken by Pollard
Partial hash inversion
ハッシュシーケンス
Puzzles
ディフィー・ヘルマンベースのパズル
Moderate
Mbound
Hokkaido
Cuckoo Cycle
マークル木ベース
ガイドツアーパズルプロトコル

リユーザブル・プルーフ・オブ・ワーク（RPOW）

コンピュータ科学者のハル・フィニーは、PoWのアイデアを基に、リユーザブル・プルーフ・オブ・ワーク（Reusable Proof-of-work、RPOW）システムを開発しました。RPOWは、POWトークンを再利用可能にしたもので、トークンの価値を、PoWトークンを生成するのに必要な現実世界のリソースで保証します。

RPOWでは、PoWトークンをウェブサイトで使用した後、サイトの管理者はそのトークンを新しいRPOWトークンと交換できます。このRPOWトークンは、他のウェブサイトでも使用できます。RPOWの偽造防止は、遠隔証明によって保証されており、RPOWサーバーで動作するソフトウェアを検証することで、新たなトークンの不正発行を防いでいます。

2009年までは、フィニーのシステムが唯一の実装例でしたが、経済的に重要な用途では利用されていませんでした。2009年に登場したビットコインは、HashcashのPoWをベースとしていますが、RPOWとは異なり、分散型P2Pプロトコルによって二重支出プロテクションを実現しています。

有用なプルーフ・オブ・ワーク

従来のPoWは、ハッシュ関数の逆算など、無駄な計算処理を要求するため、多くのリソースを浪費します。この問題を解決するため、一部のアルトコインでは、有用なPoWシステムを導入しています。例えば、プライムコインでは、数学的研究に役立つ特定の種類の素数を見つけることを要求しています。

関連技術

ビットコイン
暗号通貨
Bitmessage
* プルーフ・オブ・ステーク

もう一度検索