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

プルーフ・オブ・ワーク (proof-of-work、POW) システム (またはプロトコルかファンクション) はサービスのリクエスターに一部の作業を要求(通常はコンピュータによる処理時間を意味する)することでDoS攻撃やネットワーク上のスパムなどの他のサービスの濫用を抑止する経済的手段。コンセプトは1993年のジャーナル記事で示されているようにシンシア・ドワークとMoni Naorによって発明された^[1] 。「プルーフ・オブ・ワーク」またはPOWという用語はマーカス・ヤコブソンとアリ・ジュルズによる1999年の論文で最初に造語され、公式化された^[2] 。ソロモン諸島の貝貨は通貨に価値を与えるためにプルーフ・オブ・ワークシステムが使われた初期の例である。

これらのスキームの重要な特徴はそれらの非対称性にある：作業はリクエスター側にとって適度に難しい(しかし実行可能)ものでなければならないが、サービスプロバイダー側にとってはチェックは容易である。このアイディアはCPUコストファンクション、クライアントパズル、計算パズルまたはCPUプライスファンクションとして知られている。PoWはコンピュータではなく人間が素早く解決することを意図したCAPTCHAとは異なる。プルーフ・オブ・スペース(Proof of space、PoS)提案はCPUタイムの代わりに専用のメモリーまたはディスクの容量を証明することで同じ原理を適用している。プルーフ・オブ・バンドワイズ(Proof of bandwidth)アプローチは暗号通貨のコンテキストで議論されてきた。プルーフ・オブ・オーナシップ(Proof of ownership)は特定のデータが証明者によって保持されていることを証明することを目的としている。

背景

ビットコインのマイニングやHashcashで使われているこの有名なシステムは電子メールを送信するための信用トークンとして作業の完了を証明する部分的なハッシュの逆算を利用している。例えば、以下のヘッダーは2038年1月19日にメッセージを calvin@comics.netへ送信するための約2⁵²のハッシュ計算を表している

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

それはスタンプのSHA-1ハッシュ(ヘッダー名 X-Hashcashを省略: コロンと余白も「1」の桁まで省略)が二進法で52桁の0、つまり十六進法で13桁の0で始まることを確認することにより1回の計算で検証される^[1]

0000000000000756af69e2ffbdb930261873cd71

POWシステムがスパム問題などの特定のサービスの拒否問題を実際に解決できるかどうかは議論になった^[3]^[4]。システムはスパマーにとってスパムメールの送信が押し付けがましく非生産的なものとしなければならないが、正当なユーザーがメッセージを送信するのを妨げてはならない。言い換えれば、本物のユーザーはメール送信時にいかなる困難にも遭遇すべきではないが、メールのスパマーは一度に大量のメールを送るために莫大な計算力を消費しなければならない。プルーフ・オブ・ワークシステムはHashcashに類似したシステムを使用するビットコインなどの他のより複雑な暗号システムがプリミティブとして使用している。

バリアント

プルーフ・オブ・ワークプロトコルには2つのクラスが存在する。

チャレンジ・レスポンス プロトコルはリクエスター(クライアント)とプロバイダー(サーバー)の間で直接対話型リンクを担う。プロバイダーはチャレンジを選択し、プロパティを持つセット内のアイテムを表示し、リクエスターはセット内の関連するレスポンスを見つけて送り返しプロバイダーによってチェックされる。チャレンジはプロバイダーによって即座に選ばれるので、難易度を現在の負荷に適合させることができる。リクエスター側での作業はチャレンジ・レスポンスプロトコルが既知のソリューション(プロバイダーが選択)を持つ場合、または限定されたサーチスペース内に存在することが知られている場合に限定される可能性がある。

ソリューション検証プロトコルはそのようなリンクを想定していない:結果として、リクエスターがソリューションを求める前に問題を自ら科さなければならず、プロバイダーは問題の選択と見つかったソリューションの両方を確認しなければならない。そのようなスキームの大半はHashcashなどの無限の確率的反復手続きである。

既知のソリューションプロトコルは、矩形分布の分散がポアソン分布の分散よりも(同じ平均で)低いことから無限の確率的プロトコルよりもわずかに低い分散を持つ傾向がある。複数サンプルの平均は低い分散を有するため分散を減らすための一般的な技術は複数の独立したサブチャレンジを使用することである。

タイムロックパズルなどの固定費関数も存在する。

更に、これらのスキームが使用する基本機能は以下のものがある:

CPUバウンド ハイエンドのサーバーからローエンドのポータブル端末まで同様に時間と共に大きく変化するプロセッサーの速度で計算がなされている^[5]
メモリーバウンド^[6]^[7]^[8]^[9] 計算速度がメインメモリーアクセス(レイテンシ(待ち時間)または帯域幅の何れか)によって制限されており、その性能はハードウェアの進化に対してあまり敏感ではないと予想されている。
ネットワークバウンド^[10] クライアントが殆ど計算を行わなくてもよい場合でも最後のサービスプロバイダーに照会する前に遠隔サーバーからトークンを収集しなければならない。この意味で作業は実際にはリクエスター側によって行われないが、必要なトークンを取得するための待ち時間が原因で遅延が発生する。

最後に、一部のPOWシステムは秘密(典型は秘密鍵)を知っている参加者に安価なPOWを生成するためのショートカット計算を提供している。その根拠としてメーリングリストの所有者は、高いコストが発生することなく全ての受信者へのスタンプを生成することができることができる点が挙げられる。そのような機能が望ましいかどうかは使用シナリオによって異なる

プルーフ・オブ・ワーク機能のリスト

以下が知られているプルーフ・オブ・ワークの機能のリストである:

Integer square root modulo a large prime^[1]
フィアット-シャミールの署名を弱める^[1]。
Ong–Schnorr–Shamir signature broken by Pollard^[1]。
Partial hash inversion^[11]^[12]^[2] This paper formalizes the idea of a proof of work (POW) and introduces "the dependent idea of a bread pudding protocol", a "re-usable proof of work" (RPOW) system.^[13] as Hashcash
ハッシュシーケンス^[14]
Puzzles^[15]
ディフィー・ヘルマンベースのパズル^[16]
Moderate^[6]
Mbound^[7]
Hokkaido^[8]
Cuckoo Cycle^[9]
マークル木ベース^[17]
ガイドツアーパズルプロトコル^[10]

電子マネーとしてのリユーザブル・プルーフ・オブ・ワーク

コンピュータ科学者のハル・フィニーはプルーフ・オブ・ワークのアイディアを基に、リユーザブル・プルーフ・オブ・ワーク(Reusable Proof-of-work、RPOW)を利用するシステムを作り出した^[18] 。プルーフ・オブ・ワークを実用目的に再利用するアイディアは1999年に既に確立されていた^[2] 。フィニーの目的はRPOWをトークンマネー(名目貨幣)とすることだった。金貨の価値が金貨の製造に必要な純金の価値に下支えされていると考えられているように、RPOWトークンの価値はPOWトークンを「鋳造」するのに必要な現実世界のリソースの価値によって保証される。フィニーのRPOW版ではPOWトークンはHashcashの一部である。

ウェブサイトはサービスと引き換えにPOWトークンを要求できる。ユーザーにPOWトークンを要求することでサービスのつまらないもしくは過度の使用を抑止し、インターネットへの帯域幅、計算、ディスク容量、電力、管理費などのサービスの基本リソースを節約する

フィニーのRPOWシステムはトークンを生成するために必要な作業を繰り返すことなくトークンのランダム交換を許可する点でPOWシステムと異なる。誰かがウェブサイトでPOWトークンを「使用」した後で、サイトの管理者は「使用された」POWトークンを新しい未使用のRPOWトークンと交換でき、その後同様にRPOWトークンの受け入れ態勢が整っている第三者のウェブサイトで使用できる。これはPOWトークンを「鋳造」するために必要なリソースを節約する別の方法である。RPOWトークンの偽造防止は遠隔証明により保証されており、使用済みのPOWかRPOWトークンを同価値の新しいトークンに交換するRPOWのサーバーは遠隔証明を利用して関係者がRPOWサーバーで動作しているソフトウェアを検証できるようにしている。フィニーのRPOWソフトウェアのソースコードは公開されている(BSDに似たライセンスの下で)ので、十分な知識のあるプログラマーはコードを調べることで、ソフトウェア(とひいてはRPOWサーバー)が同価値の使用済みトークンとの交換の場合を除いて新たなトークンの発行を決して行わないことを検証できる。

2009年までは、フィニーのシステムは実装された唯一のRPOWシステムであり、経済的に重要な用途で利用されることはなかった。2009年にネットワークがオンライン状態となったビットコインはプルーフ・オブ・ワークの暗号通貨であり、フィニーのRPOWのようにHashcashのPOWをベースとしている。しかしビットコインではRPOWで使用されていたハードウェアのトラステッド・コンピューティング機能ではなく、コインの転送トラッキング用の分散型P2Pプロトコルによって二重支出プロテクションが提供されている。ビットコインは計算によってプロテクトされているためより信頼性が高い。RPOWはTPMハードウェアに格納されている秘密鍵とTPM秘密鍵を所持するメーカーによってプロテクトされているが、TPMメーカーの秘密鍵を盗んだハッカーまたはTPMチップ自体を調査して鍵を取得する能力がある者はプロテクトを破ることが出来た。ビットコインは個々のマイナーによってHashcashのプルーフ・オブ・ワーク機能を利用して「採掘」され、P2Pビットコインネットワーク内の分散ノードによって検証される。

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

多くのPOWシステムはクライアントにハッシュ関数の逆算など無駄な作業を要求しているが、これは多大なリソース(主にクライアントのコンピュータを動作させる電力)が浪費されることを意味する。損失を軽減するために一部のアルトコインは行われた作業が実際に有用なPOWシステムを利用しており、例えばプライムコインは素数定理など数学的研究に有用な特定の種類の未知の素数を見つけることをクライアントに要求する。

注釈

1.^大半のUnixシステムではこれはコマンドで確認できる: echo -n 1:52:380119:calvin@comics.net:::9B760005E92F0DAE | openssl sha1

脚注

^ ^a ^b ^c ^d Dwork, Cynthia; Naor, Moni (1993). “Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology”. CRYPTO’92: Lecture Notes in Computer Science No. 740 (Springer): 139–147.
^ ^a ^b ^c Jakobsson, Markus; Juels, Ari (1999). “Proofs of Work and Bread Pudding Protocols”. Communications and Multimedia Security (Kluwer Academic Publishers): 258–272.
^ Laurie, Ben; Clayton, Richard (May 2004). “Proof-of-work proves not to work”. WEIS 04.
^ Liu, Debin; Camp, L. Jean (June 2006). "Proof of Work can work - Fifth Workshop on the Economics of Information Security". {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)
^ How powerful was the Apollo 11 computer?, a specific comparison that shows how different classes of devices have different processing power.
^ ^a ^b Abadi, Martín; Burrows, Mike; Manasse, Mark; Wobber, Ted (2005). “Moderately hard, memory-bound functions”. ACM Trans. Inter. Tech. 5 (2): 299–327.
^ ^a ^b Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). “On memory-bound functions for fighting spam”. Advances in Cryptology: CRYPTO 2003 (Springer) 2729: 426–444.
^ ^a ^b Coelho, Fabien. "Exponential memory-bound functions for proof of work protocols". Cryptology ePrint Archive, Report. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)
^ ^a ^b Tromp, John (2015). "Cuckoo Cycle; a memory bound graph-theoretic proof-of-work" (PDF). Financial Cryptography and Data Security: BITCOIN 2015. Springer. pp. 49–62. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)
^ ^a ^b Abliz, Mehmud; Znati, Taieb (December 2009). “A Guided Tour Puzzle for Denial of Service Prevention”. Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009 (Honolulu, HI): 279–288.
^ Back, Adam. "HashCash". {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明) Popular proof-of-work system. First announce in March 1997.
^ Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. (1998). “Curbing junk e-mail via secure classification”. Financial Cryptography: 198–213.
^ Wang, Xiao-Feng; Reiter, Michael (May 2003). “Defending against denial-of-service attacks with puzzle auctions”. IEEE Symposium on Security and Privacy '03.
^ Franklin, Matthew K.; Malkhi, Dahlia (1997). “Auditable metering with lightweight security”. Financial Cryptography '97. Updated version May 4, 1998.
^ Juels, Ari; Brainard, John (1999). “Client puzzles: A cryptographic defense against connection depletion attacks”. NDSS 99.
^ Waters, Brent; Juels, Ari; Halderman, John A.; Felten, Edward W. (2004). “New client puzzle outsourcing techniques for DoS resistance”. 11th ACM Conference on Computer and Communications Security.
^ Coelho, Fabien. "An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees". Cryptology ePrint Archive, Report. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)
^ "Reusable Proofs of Work". 2007年12月22日時点のオリジナルよりアーカイブ。 {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

外部リンク

Finney's system at the Wayback Machine (archived December 22, 2007)
bit gold Bit gold. Describes a complete money system (including generation, storage, assay, and transfer) based on proof of work functions and the machine architecture problem raised by the use of these functions.

[DwoNao1992-1] Dwork, Cynthia; Naor, Moni (1993). “Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology”. CRYPTO’92: Lecture Notes in Computer Science No. 740 (Springer): 139–147.

[JaJue1999-2] Jakobsson, Markus; Juels, Ari (1999). “Proofs of Work and Bread Pudding Protocols”. Communications and Multimedia Security (Kluwer Academic Publishers): 258–272.

[LauClay2004-3] Laurie, Ben; Clayton, Richard (May 2004). “Proof-of-work proves not to work”. WEIS 04.

[LiuCa2006-4] Liu, Debin; Camp, L. Jean (June 2006). "Proof of Work can work - Fifth Workshop on the Economics of Information Security". {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

[5] How powerful was the Apollo 11 computer?, a specific comparison that shows how different classes of devices have different processing power.

[ABuMaWo2003-6] Abadi, Martín; Burrows, Mike; Manasse, Mark; Wobber, Ted (2005). “Moderately hard, memory-bound functions”. ACM Trans. Inter. Tech. 5 (2): 299–327.

[DwoGoNao2003-7] Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). “On memory-bound functions for fighting spam”. Advances in Cryptology: CRYPTO 2003 (Springer) 2729: 426–444.

[Coe2005-8] Coelho, Fabien. "Exponential memory-bound functions for proof of work protocols". Cryptology ePrint Archive, Report. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

[Tro2014-9] Tromp, John (2015). "Cuckoo Cycle; a memory bound graph-theoretic proof-of-work" (PDF). Financial Cryptography and Data Security: BITCOIN 2015. Springer. pp. 49–62. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

[Abliz09-10] Abliz, Mehmud; Znati, Taieb (December 2009). “A Guided Tour Puzzle for Denial of Service Prevention”. Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009 (Honolulu, HI): 279–288.

[Ba1997-11] Back, Adam. "HashCash". {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明) Popular proof-of-work system. First announce in March 1997.

[GaJaMaMa1998-12] Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. (1998). “Curbing junk e-mail via secure classification”. Financial Cryptography: 198–213.

[WaRei2003-13] Wang, Xiao-Feng; Reiter, Michael (May 2003). “Defending against denial-of-service attacks with puzzle auctions”. IEEE Symposium on Security and Privacy '03.

[FraMa1997-14] Franklin, Matthew K.; Malkhi, Dahlia (1997). “Auditable metering with lightweight security”. Financial Cryptography '97. Updated version May 4, 1998.

[JueBrai1999-15] Juels, Ari; Brainard, John (1999). “Client puzzles: A cryptographic defense against connection depletion attacks”. NDSS 99.

[WaJueHaFe2004-16] Waters, Brent; Juels, Ari; Halderman, John A.; Felten, Edward W. (2004). “New client puzzle outsourcing techniques for DoS resistance”. 11th ACM Conference on Computer and Communications Security.

[Coe2007-17] Coelho, Fabien. "An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees". Cryptology ePrint Archive, Report. {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

[18] "Reusable Proofs of Work". 2007年12月22日時点のオリジナルよりアーカイブ。 {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)

[1]

[2]

[1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

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

背景

バリアント

プルーフ・オブ・ワーク機能のリスト

電子マネーとしてのリユーザブル・プルーフ・オブ・ワーク

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

関連

注釈

脚注

外部リンク

Read other articles:

Perea (wilayah)

Василиск

Archivo de la Diputación de Barcelona

Tom Whitlock

ذبابة مايو (جنس)

Російська рулетка

Crystal Palace Circuit

سكوت باكولا

Anjing

Megion

روث ترينغهام

Snowy Mountains Highway

Pelanduk

Lupe Fiasco discography

3D fold evolution

Katiu

Braeswood Place, Houston

Aoi Kizuki

Hawker P.1103

Neu Duvenstedt