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

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/18 00:07 UTC 版)

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

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

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システムを利用しており、例えばプライムコインは素数定理など数学的研究に有用な特定の種類の未知の素数を見つけることをクライアントに要求する。

脚注

^ ^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テンプレートでは|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テンプレートでは|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テンプレートでは|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テンプレートでは|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テンプレートでは|access-date=引数が必須です。 (説明)
^ "Reusable Proofs of Work". 2007年12月22日時点のオリジナルよりアーカイブ。 Cite webテンプレートでは|access-date=引数が必須です。 (説明)