Proof-of-Work systémy sa dostali do širšieho povedomia až s rozmachom kryptomien počas druhej dekády 21. storočia, no výskum v tejto problematike prebiehal intenzívne už roky predtým.
Prvý návrh použitia Proof-of-Work (PoW) systému prezentovali Moni Naor a Cynthia Dwork v práci „Pricing via Processing or Combatting Junk Mail“ [1] v roku 1992. Prínosom ich výskumu bola technika spočívajúca v tom, že klient, žiadajúci o pridelenie istých systémových zdrojov, je nútený vypočítať relatívne ťažký, no riešiteľný matematický problém závislý od správy a doplňujúcich informácií. Dôsledkom toho je obmedzenie zahltenia zdrojov poskytovateľa danej služby. Takto navrhnutý systém odporučili primárne ako prevenciu voči spamu – nevyžiadanej e-pošte, ale aj ako nástroj riadenia prístupu k akýmkoľvek zdielaným zdrojom vo všeobecnosti. Naor a Dwork v práci prezentovali niekoľko algoritmov, ktoré v takomto systéme možno použiť ako tzv. pricing funkciu (ďalej PoW funkcia). Všetky navrhované funkcie boli postavené na algoritmoch z teórie čísel, a to na podpisových schémach Fiat – Shamir a Ong – Schnorr – Shamir.
Nezávisle od predchádzajúcej práce publikoval Adam Back v roku 1997 návrh PoW systému s názvom Hashcash [2]. Systém je založený na hľadaní čiastočných kolízií kryptografickej hašovacej funkcie SHA1. Jeho implementácia sa zameriavala na zamedzenie nekontrolovaného posielania emailov a ochranu pred preťažením anonymných remailerov prvej generácie (tzv. Cypherpunk remailer). Od tejto publikácie sa o PoW systéme začalo uvažovať ako o istej forme elektronickej meny. Výpočtovo náročnou operáciou je vyprodukovaný overiteľný token, mikro platba, ktorou odosielateľ demonštruje svoj záujem na vykonaní transakcie. Hlavným cieľom návrhu je spraviť spam ekonomicky nerentabilný.
Počas niekoľkých rokov viacero výskumov implementovalo podobné systémy, založené na POW, s rozmanitými výsledkami. Väčšina výskumov skúmala diskutabilnú efektivitu PoW pri riešení problému so spamom. Ben Laurie a Richard Clayton publikovali v roku 2004 prácu s názvom ““Proof-of-Work“ Proves Not to Work“ [3], v ktorej s použitím údajov od veľkého poskytovateľa internetového pripojenia v Británií dospeli k záveru, že PoW sám o sebe nie je efektívnym riešením. Ak by každý e-mail používal rovnaký výpočtovo náročný PoW ekonomicky nevýhodný pre spammerov, protokol by dramaticky penalizoval aj legitímnych používateľov. Je to spôsobené rádovo vyššími nákladmi oproti spamerom, ktorý na rozposielanie nepoužívajú len vlastné zariadenia, ale aj rozsiahle botnet siete. Ako možné riešenie autori vidia hybridný systém, v ktorom by PoW bol použitý len príležitostne.
Na ich kritickú prácu nadviazal Debin Liu a L Jean Camp so štúdiou “Proof of Work can Work“ [4]. Autori v práci demonštrovali, že PoW môže byť účinný aj pri rozdielnej cene, ktorú na posielanie vynakladajú spameri a legitímni používatelia, ak sú požiadavky na náročnosť výpočtu PoW funkcie volené reputačným mechanizmom. Proof-of-Work tak v kombinácií s pokročilými anti – spamovými technológiami dokáže plniť funkciu ochrany proti spamu.
Použitie POW ako peňažného nástroja pre elektronické mikro-transakcie spopularizovali Ronald L. Rivest a Adi Shamir v práci s názvom “PayWord and MicroMint: Two simple micropayment schemes“ [5], ktorú prezentovali na RSA konferencii v roku 1996. Schéma PayWord, je založená na použití asymetrickej kryptografie a nie je pre našu prácu podstatná. Druhá schéma – MicroMint, reprezentuje token, ktorou realizujeme platbu, ako k-násobnú kolíziu kryptografickej hašovacej funkcie (pre konkrétne k rovné 4). V takomto systéme dokáže producent vyrábať tokeny relatívne lacno. Je zo spôsobené tým, že pri nájdení prvej k-násobnej kolízie sa producent nachádza na úrovni, kde sa ostatné kolízie generujú rapídnou rýchlosťou. Je tu aplikovaná z ekonómie známa úspora z rozsahu. Na druhej strane niekto, kto chce vyrobiť konkrétny token podvodom, rieši situáciu, kde je cena jej vygenerovania vyššia, ako reálna hodnota za danú službu.
Na ich prácu nadviazal v roku 1999 Markus Jakobsson a Ari Juels s publikáciou “Proofs of Work and Bread Pudding Protocols“ [6], kde demonštrovali možnosť generovať MicroMint tokeny v bezpečnostných protokoloch používajúcich POW, aj keď samotné protokoly priamo nesúvisia s platobným systémom navrhnutým kolegami z RSA. Ide o jeden z prvých experimentov s opakovane použiteľným POW.
Masovej popularizácii sa POW na báze riešenia kryptografických problémov dočkal rozšírením používania decentralizovanej kryptomeny. Prvý teoretický koncept daného návrhu s názvom “b – money“ [7] zverejnil v novembri 1998 Wei Dai v cypherpunks mailing – liste. Odporúčal v ňom použiť Hashcash PoW ako nástroj pre generovanie peňazí. V tej dobe bol protokol prakticky nepoužiteľný. Jeho ideu o desať rokov neskôr vylepšil a zrealizoval vývojár, resp. tím známy pod pseudonymom “Satoshi Nakamoto“ publikovaním práce „Bitcoin: A Peer-to-Peer Electronic Cash System“ [8].
Hlavným problémom decentralizovanej meny je realizácia, v ktorej by nebolo pre sebeckého, nedôveryhodného účastníka systému možné viacnásobne minúť, čí dokonca vygenerovať virtuálnu menu. To sa Nakamotovi podarilo zavedením efektívneho PoW systému, ktorý v takejto decentralizovanej schéme rieši tzv. Problém Byzantských Generálov [9]. Ide o problém interpretovaný v projekte Bitcoin nasledovne: „Ako vytvoriť konsenzus u sebeckých, nikomu nepodriadených entít, ak existujú pádne dôvody (obohatenie), porušovať ho?“ [10]. Ak by boli všetky entity altruistické a úprimné, problém by neexistoval. Nakoľko v decentralizovanej sieti sa informácie šíria postupne, nastáva množstvo prípadov, kedy jedna časť siete vie o transakcií, zatiaľ čo iná časť siete o nej ešte nevie. Z toho dôvodu je možné dané peniaze minúť opätovne. Satoshi Nakamoto navrhol dosiahnutie konsenzu tým, že transakcie za konkrétne krátke obdobie (~ 10 minút) odsúhlasí prvý úspešný riešiteľ aktuálneho PoW problému. Riešiteľ zároveň získa malú časť používanej kryptomeny. To je motiváciou, aby sa na riešení budúcich PoW podieľalo čo najviac entít a manipulovanie siete by tak bolo náročnejšie. Vygenerovaný PoW je ľahko overiteľný každou entitou v sieti, čím sa dosiahne konsenzus všetkých uskutočnených transakcií.
Bitcoin je v súčasnosti najpoužívanejšou kryptomenou čo z neho robí aj doposiaľ globálne najpoužívanejší aplikovaný PoW algoritmus.
Najznámejšie použitie POW, v kontexte ochrany pred zahltením peer-to-peer (P2P) siete, je projekt Bitmessage [11]. Jedná sa o decentralizovaný, distribuovaný, šifrovaný komunikačný protokol. Prvý návrh projektu publikoval softvérový vývojár Jonathan Warren v novembri 2012. Bitmessage slúži ako bezpečná náhrada e-mailovej komunikácie. Autor sa pri návrhu Bitmessage protokolu inšpiroval projektom Bitcoin z ktorého použil architektúru P2P siete.
Na záver je dobré spomenúť aj publikovanú ochranu pred DDoS útokmi s názvom “New Approach to Mitigating Distributed Service Flooding Attacks“ [12], ktorého autori Mehmud Abliz a Taieb Znati predstavili tzv. guided tour puzzles. Schéma nepoužíva na reguláciu prístupu k sieťovým zdrojom časovo náročný výpočet na strane klienta, ale latenciu sieťových prvkov. Žiadateľ o službu je pred sprístupnením zdrojov servera nútený vykonať niekoľko po sebe idúcich dopytov na rôzne sieťové uzly – sprievodcov, ktoré mu poskytnú informáciu o ďalšom kroku. Spolu s použitím kryptografických hašovacích funkcií na postupný výpočet potrebného tokenu klient nedokáže predvídať informácie, ktoré mu sprievodné uzly poskytnú. Klient je tak nútený absolvovať celú cestu bez akéhokoľvek zrýchlenia podvodom. Po jej ukončení má klient dostatok informácií, aby serveru od ktorého žiada službu dokázal, že cestu skutočne absolvoval. Výhodou takéhoto návrhu je zamedzenie diskriminácie pre výpočtovo slabšie zariadenia oproti iným používateľom. Daný prístup je účinný aj proti útočníkovi s veľkým výpočtovým potenciálom. Čas, ktorý trvajú všetky dopyty, je závislý od sieťových prvkov mimo dosahu riešiteľa puzzle.
Zdroje
1. Cynthia Dwork and Moni Naor. Pricing via processing or combatting junk mail. 1992. Springer-Verlag
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/pvp.pdf
2. Back, Adam. A partial hash collision based postage scheme. [ANNOUNCE] hash cash postage implementation [online]. 28 March 1997
http://www.hashcash.org/papers/announce.txt
3. Laurie, Ben and Clayton, Richard. Proof-of-work proves not to work
http://www.cl.cam.ac.uk/~rnc1/proofwork.pdf
4. Debin Liu and L Jean Camp. Proof of Work can Work
http://www.ljean.com/files/50.pdf
5. Ronald L. Rivest and Adi Shamir. PayWord and MicroMint: two simple micropayment schemes. V : CryptoBytes. Springer-Verlag, 1996. p. 69–87. Proceedings of the International Workshop on Security Protocols. ISBN 3-540-62494-5.
http://people.csail.mit.edu/rivest/RivestShamir-mpay.pdf
6. Markus Jakobsson and Ari Juels. Proofs of Work and Bread Pudding Protocols. V : Communications and Multimedia Security. Kluwer Academic Publishers, 1999. p. 258–272.
http://www.emc.com/emc-plus/rsa-labs/ps/breadpudding.ps
7. Wei Dai. b-money.
http://www.weidai.com/bmoney.txt
8. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2009.
http://bitcoin.org/bitcoin.pdf
9. Leslie Lamport, Robert Shostak and Marshall Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems. 1982. Vol. 4, p. 382–401.
10. The Proof-of-Work Concept. The Mises Circle, 2013
http://themisescircle.org/blog/2013/06/24/the-proof-of-work-concept/
11. Bitmessage. Bitmessage Wiki. 2012.
12. Mehmud Abliz and Taieb Znati. New Approach to Mitigating Distributed Service Flooding Attacks. V : ICONS 2012, The Seventh International Conference on Systems. Saint Gilles, Reunion, 29 February 2012. p. 13–19. ISBN 978-1-61208-184-7
taký článok v slovenčine? ďakujem, palec hore