Doklad o práci

Proof of work ( anglicky  proof-of-work, POW, PoW ) je princip ochrany síťových systémů před zneužitím služeb (například před DoS útoky nebo organizováním spamových e- mailů ), založený na potřebě vykonávat poměrně dlouhou práci na na straně klienta (hledání řešení problému), jehož výsledek lze snadno a rychle zkontrolovat na straně serveru (viz jednosměrná funkce ). Hlavním rysem použitých výpočtů je asymetrie časových nákladů - jsou významné pro nalezení řešení a velmi malé pro ověření [1] . Taková schémata jsou také známá jako klientská hádanka ( funkce klientské hádanky ),výpočetní hádanka nebo funkce stanovení cen CPU .

Tento způsob ochrany nelze zaměňovat s captchas , které nabízejí úkoly pro člověka snadné, ale pro počítač obtížné nebo zcela neřešitelné. Důkaz práce je zpočátku zaměřen na nalezení řešení pomocí dříve známého algoritmu v určitém konečném čase, ale k ověření výsledného řešení je potřeba relativně malý počet operací [1] . Technologie POW dosáhly největšího rozšíření a rozvoje v systémech kryptoměn.

Historie

Požadavek na prokázání práce byl poprvé uveden v článku „Pricing via Processing or Combatting Junk Mail“ [1] v roce 1993. Autoři navrhli následující myšlenku: pro přístup ke sdílenému zdroji musí uživatel vypočítat nějakou funkci, která je velmi složitá a náročná na zdroje, ale dá se vyřešit v rozumném čase. Výpočet funkce na straně klienta by měl být mnohem obtížnější než kontrola výsledku na straně serveru. Jedním z povinných požadavků na funkci je její neamortizace — pokud by se našlo několik řešení, byl by čas potřebný úměrně jejich počtu. Podle autorů takové dodatečné výpočty nevytvářejí překážky pro odesílání několika běžných dopisů z počítače běžného uživatele, ale nutnost neustálých výpočtů činí odesílání spamu velmi náročným na zdroje. Podle nezávislých odhadů takové systémy ve skutečnosti vedou k výraznému omezení počtu dopisů, které lze za den odeslat z jednoho počítače [2] .

V roce 1997 spustil Adam Back projekt Hashcash věnovaný ochraně proti spamu. Úloha byla formulována následovně: „Najděte hodnotu x takovou, aby hash SHA(x) obsahoval N úvodních nulových bitů.

V roce 1999 se objevuje termín proof of work  - byl použit v článku "Proofs of Work and Bread Pudding Protocols" (autoři - Markus Jacobsson a Ari Jewels) v časopise Communications and Multimedia Security [3] .

16. srpna 2004 Hal Finney ve svém dopise cypherpunkovému fóru navrhl používat znovu použitelný důkaz práce ( RPOW  , RPoW ) k uspořádání elektronické měny [4] .

Satoshi Nakamoto brzy navrhl kryptoměnu bitcoin , kde se používá proof-of-work, aby se značně zkomplikovalo dvojí utrácení . Bylo navrženo najít hash bloku informací pomocí funkce SHA-256 s výběrem parametrů tak, aby výsledek měl daný počet vysokých bitů nula. Následně se v dalších kryptoměnách (například Litecoin ) místo SHA-256 začal používat KDF , jako scrypt , bcrypt , PBKDF2 a další [5] .

Příklady použitelných funkcí

Seznam nejběžnějších funkcí používaných v systémech proof-of-work:

• Částečné inverzní hašování . Nejznámější aplikací je systém Hashcash [6] , který při odesílání emailem využívá hašování částečné inverze. Pro výpočet záhlaví jednoho písmene je potřeba asi 252 hašovacích výpočtů, které je nutné přepočítat pro každé nové písmeno. Kontrola správnosti vypočítaného kódu je přitom rychlá – používá se jediný výpočet SHA-1 s předem připraveným štítkem [7] [8] [9] .
• Funkce založené na Merkle stromech [10] . Nejznámější příklad této varianty lze nalézt v systému bitcoinů , kde se jako důkaz práce používá víceúrovňové hashování – hash předchozího bloku se stává prvkem dalšího bloku. Neexistuje tedy způsob, jak změnit blok bez změny hash ve všech následujících blocích. Kontrola integrity celého řetězce je přitom omezena na jediný výpočet hashů aktuálního a předchozího bloku. Hash je uznán jako pravdivý pouze v případě, že hodnota jakékoli charakteristiky hash součtu splňuje zvolené kritérium, například v bitcoinu - počet úvodních nul hash součtu je větší nebo roven hodnotě speciálního parametru, který určuje obtížnost těžby potřebnou v tuto chvíli k udržení plánované rychlosti vzhledu nových bloků. Pro vyhledání takového hash součtu je nutné jej vícenásobně přepočítat s výčtem libovolných hodnot parametru nonce [11] .
• Kvadratický zbytek modulo velké prvočíslo [12]
• Podpis protokolu Fiat - Shamira [12]
• Funkce založená na protokolu Diffie-Hellman [13]
• Funkce Memory bound ( en:Memory bound function ) [14]
• kukaččí hašování [15]

Potenciální zranitelnosti a útoky na informační systémy založené na POW

Odborníci pokračují v debatě, zda je ochrana POW dostatečně účinná proti DoS útokům a spamu [16] [17] .

Útok 51 %

Bitcoin , stejně jako mnoho jiných kryptoměn, může být potenciálně vystaven „51% útoku“: pokud útočník ovládá více než polovinu veškerého výpočetního výkonu sítě, pak má možnost potvrdit pouze své vlastní bloky, zatímco ostatní ignoruje. . To mu umožňuje nejen přijímat všechny současně emitované kryptoměny, ale také blokovat všechny nebo vybrané transakce, což může potenciálně vést k „zmizení“ z účtů kryptoměny přijaté z těch transakcí, které nebudou zahrnuty do nová verze blockchainu [11] .

Dvojité výdaje

Dvojité utrácení (dvojité utrácení) je opakovaný převod stejného majetku. Tento útok je rozdělen do několika podtypů.

• Závodní útok __ _ _  Útočník provede transakci X, zaplatí za nákup zboží a zároveň tytéž peníze převede na svůj druhý účet s transakcí Y. Pokud prodávající nepočkal na potvrzení transakce a zboží odeslal, podstoupil velké riziko , protože existuje 50% šance, že se transakce Y dostane do skutečného řetězce, a tato pravděpodobnost se zvyšuje, pokud útočník cíleně vybere síťové uzly k provedení té či oné operace [18] .

• Finneyho útok je následující: útočník se pokusí najít blok, který obsahuje jeho transakci Y. Jakmile je však blok nalezen, útočník odešle transakci X, po které koupí zboží. Prodejce čeká na potvrzení transakce X a zboží odešle. Pokud se v tuto chvíli objeví blok s transakcí Y, pak se vytvoří situace fork, ve které si těžaři musí vybrat jeden ze dvou bloků, aby pokračovali v blockchainovém řetězci. Soustředěním velkého množství výpočetních zdrojů do rukou útočníka může výrazně zvýšit pravděpodobnost výběru bloku s operací Y. Potvrzená transakce tak není zaručena jako platná [19] .

Sobecké dolování

Při sobecké těžbě je cílem útočníka  ovládnout síť, přestože má výpočetní zdroje s celkovou kapacitou menší než 50 %. Toho je dosaženo tím, že útočník tvrdí, že jeho pool je pro těžbu výhodnější než jiné pooly, což přitahuje těžaře třetích stran. Útočník publikuje bloky takovým způsobem, že dochází k plýtvání výpočetními zdroji ostatních těžařů a poolů. Přibližný průběh algoritmu je následující:

1. Bazén ode všech tajně těží svůj soukromý řetězec.
2. Pokud fond najde nový blok pro svůj soukromý řetězec, pak:
   1. Pokud je původní řetěz rozvětvený, pak útočník zveřejní svůj blok, tím se jeho řetěz prodlouží a stane se pravdivým a řetěz poctivých horníků je zahozen.
   2. Pokud ještě žádný fork neexistuje, pak pool pokračuje v tajné těžbě svého soukromého řetězce a zvyšuje svůj náskok.
3. Pokud veřejný řetězec najde blok pro veřejný řetězec, pak:
   1. Pokud je veřejný řetězec před tajným, pak útočníkův fond zahodí své nepublikované bloky a začne těžit z nového veřejného bloku.
   2. Pokud jsou řetězce stejné, pak útočníkův fond zveřejní všechny své bloky, čímž se dostane do mezery ve svém řetězci.
   3. Pokud je veřejný řetězec několik (N) bloků za soukromým řetězcem, pak fond zveřejní jeden další blok (N+1), který izoluje nový poctivý blok.

Téměř v každém výsledku prohráli poctiví horníci, což je nutí vstoupit do zločinecké skupiny [20] .

Kritika informačních systémů založených na POW

Odpůrci přístupu POW kromě řady potenciálních bezpečnostních problémů zdůrazňují následující nevýhody:

• Pravděpodobnost úspěšného vytvoření dalšího bloku těžařem je přímo úměrná výpočetnímu výkonu, který má, což vede k neustálému zvyšování množství a kvality zařízení pro každého člena sítě. Těžba pomocí POW algoritmů tedy vyžaduje extrémně velké množství elektřiny. Proto přístup POW není nejlepším řešením z hlediska energetické účinnosti [21] [22] .
• Výsledky výpočetních hashovacích funkcí nejsou potřeba nikde kromě samotné sítě. Od nástupu technologie se komunita snažila přijít na způsob, jak nasměrovat všechny výpočetní zdroje sítě k vyřešení nějakého užitečného matematického nebo průmyslového problému, ale tento nebyl implementován v čisté podobě [23] .

Pokusy zbavit se nedostatků POW vedly ke vzniku POS ( anglicky  proof-of-stake , proof of stake) a četných hybridních opcí.

Příklady hybridních technologií

Příklady hybridních schémat, která kombinují myšlenky POS a POW, lze nalézt v mnoha kryptoměnách. V nich se blockchain skládá z bloků obou typů, což činí přepisování transakční historie obtížným úkolem, protože POW bloky slouží jako kontrolní body vzhledem k celkové složitosti práce v celém řetězci. V takových algoritmech obvykle POW bloky slouží jako indikátory skutečné práce, což poskytuje další záruku spolehlivosti pro obchodníky při práci s transakcemi. POW bloky lze použít k emisi oběživa a POS bloky lze považovat za potenciální příjem z vkladu [24] .

Doklad o činnosti

Prototyp algoritmu, který ještě nebyl implementován, který spočívá v tom, že držitelé vstupují do obecného procesu až poté, co odvedou nějakou práci účastníky válečného zajatce, což snižuje šance na 51% útok, protože většinový vlastník nebude schopen pouze řídit vytváření nových bloků [25] .

Jak algoritmus funguje:

1. POW miner hledá hash příslušné obtížnosti.
2. Nalezený hash je odeslán do sítě, přičemž není blokem, ale pouze prvním krokem, jakousi šablonou nutnou pro jeho vytvoření.
3. Hash sestávající z 256 pseudonáhodných bitů je interpretován jako N čísel, z nichž každému je přiřazeno jedno satoshi.
4. Mezi každým satoshi a veřejným klíčem jeho aktuálního vlastníka je vytvořen vztah jedna ku jedné.
5. Jakmile se na tento blok podepíší všichni vlastníci N, je výstupem plnohodnotný blok.
6. Pokud jeden z držitelů není dostupný nebo se neúčastní těžby, pak zbytek těžařů pokračuje ve generování šablon s různými kombinacemi kandidátů na držitele.
7. V určitém okamžiku bude požadovaný blok podepsán požadovaným počtem opakování. Bloková odměna je rozdělena mezi POW horníka a všech N držitelů.

Důkaz o popálení

Peníze se zasílají na adresu, která je hashem náhodného čísla, je zaručeno, že je z této adresy nelze utratit, protože pravděpodobnost vyzvednutí klíčů k ní bývá nulová. Na oplátku získá těžař trvalou šanci najít blok PoB a získat za něj odměnu. Těžba je v tomto případě uspořádána tak, že šance na úspěch závisí na počtu spálených mincí. Analogicky je vypalování jako nevratná záloha na POS nebo investice do virtuálního hardwaru pro těžbu POW. Z ekonomického hlediska je tento algoritmus vhodnější pro pozdější fáze vývoje kryptoměny, kdy je většina peněžní zásoby již vytvořena [26] .

Doklad o způsobilosti

Algoritmus důkazu kapacity (nebo proof of space ) je následující: pro těžbu je nutné alokovat značné množství paměti v počítači, načež se z veřejného klíče a náhodných čísel vytvoří velké množství velkých datových bloků opakovaným hašováním . V každém datovém bloku získáme index z poslední hlavičky, načež vybereme malý kousek bloku s tímto indexem , chunk .  Čím více paměti je přiděleno, tím více kusů získáme. Musí být splněna podmínka, že hash bloku a poslední hlavičky musí být menší než cíl. Každý megabajt paměti je tedy použit jako analog losu a zvyšuje šanci na úspěch těžby [27] .

Důkaz výzkumu

Algoritmus proof of research byl vyvinut projektem GridCoin s cílem nasměrovat výpočetní výkon sítí PoW k řešení vědeckých problémů na platformě BOINC . Proof of research současně používá důkaz práce k odměňování účastníků za dokončené výpočty a důkaz o sázce k podpoře dlouhodobé účasti na projektu [28] .

Energetická nehospodárnost

Systémy založené na POW jsou extrémně náročné na zdroje.

• V roce 2013 celkový výpočetní výkon vynaložený na POW v bitcoinové síti překonal 256krát více než 500 nejvýkonnějších superpočítačů na světě toho roku dohromady [29] .
• V roce 2017 bylo k dokončení jedné transakce v systému bitcoinů zapotřebí průměrně 163 kWh energie . S tímto množstvím energie je možné plně pokrýt potřeby tříčlenné rodiny žijící v malém jednopatrovém domě na pět a půl dne. Těžba kryptoměn v sítích Bitcoin a Ethereum vzala celkem více energie, než spotřebovala celá populace Sýrie [21] [22] .

Viz také

• captcha
• Bitová zpráva
• Kryptosystém s veřejným klíčem
• Jednosměrná funkce

Poznámky

1. ↑ 1 2 3 Ceny prostřednictvím zpracování nebo boje proti nevyžádané poště Archivováno 12. prosince 2017 na Wayback Machine (1993  )
2. ↑ „Proof-of-Work“ Proves to Nefunguje Archivováno 20. ledna 2017 na Wayback Machine , 2004 „Pokud se pokusíme, aby bylo posílání spamu neekonomické, musíme odesílatele omezit na 1 750 zpráv denně“
3. ↑ Proofs of Work and Bread Pudding Protocols Archived 26. července 2017 na Wayback Machine (1999  )
4. ↑ RPOW – opakovaně použitelné doklady o práci archivované 5. října 2017 na Wayback Machine (2004  )
5. ↑ Důkaz o práci v kryptoměnách: Stručná historie. Část 1 Archivováno 5. září 2017 na Wayback Machine (2015  )
6. ↑ Hashcash - A Denial of Service Counter-Measure (2002  )
7. ↑ Zpět, Adam HashCash . Získáno 25. června 2022. Archivováno z originálu dne 29. září 2017.  (neurčitý) Populární systém proof-of-work. První oznámení v březnu 1997.
8. ↑ Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. Omezování nevyžádané pošty prostřednictvím zabezpečené klasifikace  (neopr.)  // Financial Cryptography. - 1998. - S. 198-213 .
9. ↑ Wang, Xiao-Feng; Reiter, Michaele. Obrana proti útokům denial-of-service pomocí aukcí puzzle  //  IEEE Symposium on Security and Privacy '03: journal. - 2003. - Květen.
10. ↑ Coelho, Fabien (téměř) protokol pro ověřování řešení s konstantním úsilím založený na Merkle stromech . Archiv kryptologie ePrint, zpráva . Získáno 29. října 2017. Archivováno z originálu 26. srpna 2016. (neurčitý)
11. ↑ 1 2 Bitcoin: Peer-to-Peer elektronický pokladní systém Archivováno 20. března 2014 na Wayback Machine 
12. ↑ 1 2 Dwork, Cynthie; Naor, Moni Ceny prostřednictvím zpracování, nebo boj s nevyžádanou poštou, pokroky v kryptologii  //  CRYPTO'92: Poznámky k přednáškám z informatiky č. 740: deník. - Springer, 1993. - S. 139-147 .
13. ↑ Vody, Brent; Juels, Ari; Halderman, John A.; Felten, Edward W.Nové techniky outsourcingu klientských hlavolamů pro odolnost vůči DoS  (neopr.)  // 11. konference ACM o bezpečnosti počítačů a komunikací. — 2004.
14. ↑ Dwork, Cynthie; Goldberg, Andrew; Naor, MoniO funkcích vázaných na paměť pro boj se spamem  (neopr.)  // Pokroky v kryptologii: CRYPTO 2003. - Springer, 2003. - Vol. 2729 . - S. 426-444 .
15. ↑ Tromp, John. Cyklus kukačky; teoretický důkaz práce s grafem vázaným na paměť  //  Finanční kryptografie a bezpečnost dat: BITCOIN 2015: časopis. - Springer, 2015. - S. 49-62 .
16. ↑ Laurie, Ben; Clayton, Richard. Proof-of-work dokazuje, že nefunguje  (neopr.)  // WEIS 04. - 2004. - květen.
17. ↑ Liu, Debin; Camp, L. Jean. Proof of Work může fungovat  (neopr.)  // Fifth Workshop on the Economics of Information Security. - 2006. - Červen.
18. ↑ Attacks in the World of Cryptocurrencies Archived 19. září 2016 na Wayback Machine 
19. ↑ Analýza dvojitého utrácení založeného na hashrate Archivováno 4. září 2017 na Wayback Machine (2012  )
20. ↑ Attacks in the World of Cryptocurrencies Archived 19. září 2016 na Wayback Machine (2015  )
21. ↑ 1 2 Index spotřeby energie bitcoinů Archivováno 25. ledna 2022 na Wayback Machine 
22. ↑ 1 2 Ethereum Energy Consumption Index (beta) Archivováno 11. října 2017 na Wayback Machine 
23. ↑ Důkaz o práci v kryptoměnách: Stručná historie. Část 2 Archivováno 14. března 2016 na Wayback Machine 
24. ↑ Alternativy pro Proof of Work, Část 2 Archivováno 4. března 2016 na Wayback Machine (2015  )
25. ↑ Proof of Activity: Rozšíření Bitcoin's Proof of Work prostřednictvím Proof of Stake Archivováno 17. října 2017 na Wayback Machine 
26. ↑ Peer-to-Peer kryptoměna s důkazem o vypálení „Těžba bez výkonného hardwaru“ Archivováno 10. října 2017 na Wayback Machine (2014  )
27. ↑ Proofs of Space: When Space is of the Essence Archived 5. listopadu 2017 na Wayback Machine 
28. ↑ Proof -of -Research - Gridcoin  . wiki.gridcoin.us. Získáno 4. 9. 2018. Archivováno z originálu 4. 9. 2018.
29. ↑ Globální bitcoinový výpočetní výkon nyní 256krát rychlejší než top 500 superpočítačů dohromady! Archivováno 8. června 2017 na Wayback Machine (2013  )