Proof-of-work

A proof-of-work (rövidítve: PoW, magyarul: a munka bizonyítéka) a kriptográfiai bizonyítások egyik formája, amelyben az egyik fél (nevezzük bizonyítónak) bebizonyítja másoknak (az igazolóknak), hogy bizonyos célokra bizonyos mennyiségű számítási erőfeszítést elköltöttek. A hitelesítők ezt minimális erőfeszítéssel megerősíthetik. A koncepciót Cynthia Dwork és Moni Naor találta fel 1993-ban, hogy megakadályozza a szolgáltatásmegtagadási támadásokat azzal, hogy valamilyen munkát – tipikusan számítógépes feldolgozási időt – követel a szolgáltatás igénylőjétől.

A proof-of-work kifejezést először 1999-ben hozta létre és formalizálta Markus Jakobsson és Ari Juels. A proof-of-work mechanizmust később a bitcoin népszerűsítette a blokkláncok és a kriptovaluták esetén, ahol a bányászok versengenek blokkok hozzáfűzéséért, és mindegyik bányásznak sikerességi valószínűsége tapasztalható a ráfordított számítási erőfeszítéssel arányosan.^[1] A PoW és a PoS (proof-of-stake) a két legismertebb konszenzusos mechanizmus.^[2] A kriptovaluták kontextusában ezek a leggyakoribb eljárások.^[3]

Típusai

A munkavégzés igazolására kétféle protokoll létezik.

A kihívás-válasz protokollok közvetlen interaktív kapcsolatot feltételeznek az igénylő (kliens) és a szolgáltató (szerver) között. A szerver választ egy kihívást, mondjuk egy halmazelemet egy megadott tulajdonsággal, az igénylő megtalálja a megfelelő választ a halmazban, amelyet visszaküld és ellenőriz a szolgáltató. Mivel a kihívást a szerver akkor és ott választja, nehézségei az aktuális terheléshez igazíthatók. Az kliensoldalon végzett munka korlátozott lehet, ha a kihívás-válasz protokoll ismert megoldással rendelkezik, vagy ismert, hogy egy bizonyos értéktartományra szűkíthető.

A megoldás-ellenőrzési protokollok nem feltételeznek ilyen kapcsolatot: ennek eredményeként a problémát önállóan kell meghatároznia, mielőtt a kliens megoldást keresne, és a szervernek ellenőriznie kell a probléma választását és a megtalált megoldást is. A legtöbb ilyen séma korlátlan valószínűségi iteratív eljárás, például bitcoin esetében is használt Hashcash.

Ezen protokoll esetében a variancia némileg alulmarad, mint a nem korlátozott valószínűségi protokolloknál. Ennek matematikai háttere, hogy az egyenletes eloszlás varianciája alacsonyabb, mint a Poisson-eloszlásé (azonos átlaggal). A variancia csökkentésének általános technikája az, hogy több független részkihívást alkalmaz, mivel a több minta átlagának kisebb lesz a szórása.

Erőforrás szempontjából a PoW-eljárások három csoportra oszthatók:

CPU-függő, ahol a számítás a processzor sebességével fut, amely időben nagyon változik a csúcskategóriás szervertől az alacsony kategóriás hordozható eszközökig.^[4]
Memóriafüggő^[5] ^[6] ^[7] ^[8] ahol a számítási sebességet a fő memória hozzáférésekhez kötik (akár késés, akár sávszélesség), amelyek teljesítménye várhatóan kevésbé lesz érzékeny a hardver elévülésére.
Hálózatfüggő^[9] ha az ügyfélnek kevés számítást kell végrehajtania, de néhány tokent a távoli szerverekről kell gyűjtenie, mielőtt kérést intézne a végső szolgáltató felé. Ebben az értelemben a munkát valójában nem a kérelmező végzi, de az adat távolról való megszerzésének hálózati ideje miatt ez is késéssel jár.

Proof-of-work bizonyításhoz alkalmazott függvények

A proof-of-work bizonyításokhoz leggyakrabban használt algoritmusok:

Kvadratikus maradékfüggvények
Fiat-Shamir aláírások
Ong-Schnorr-Shamir aláírás
Részleges hash inverz
Hash szekvenciák
Rejtvények
Diffie-Hellman eljárás alapú rejtvény
Moderate algoritmus
Mbound algoritmus
Hokkaido algoritmus
Cuckoo Cycle algoritmus
Merkle fa alapú algoritmusok

A Bitcoin proof-of-work megoldása

A Bitcoin is egy proof-of-work alapú kriptovaluta, aminek a Hashcash PoW eljárás az alapja. A kettős költés vagy dupla költés^[10] elleni védelmet decentralizált P2P protokoll biztosítja a coinok átadásának nyomon követésére, nem pedig az RPoW által használt hardveres számítási függvény. A bitcoin megbízhatósága jobb, mert számítás védi. A bitcoinokat a Hashcash proof-of-work funkcióval "bányásszák" ki az egyes bányászok, és a P2P bitcoin hálózat decentralizált csomópontjai ellenőrzik.^[11]

Jegyzetek

↑ Proof of work jelentése. [2021. szeptember 23-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. március 21.)
↑ premik: Miért jobb a proof-of-work a proof-of-stake mechanizmusnál? (magyar nyelven). BitcoinBázis, 2022. december 9. (Hozzáférés: 2023. július 23.)
↑ Cryptocurrencies and blockchain. European Parliament, 2018. július 1. (Hozzáférés: 2020. október 29.) „the two best-known – and in the context of cryptocurrencies also most commonly used”
↑ How powerful was the Apollo 11 computer?, a specific comparison that shows how different classes of devices have different processing power.
↑ Abadi (2005). „Moderately hard, memory-bound functions” 5, 299–327. o.
↑ Dwork (2003). „On memory-bound functions for fighting spam”. Advances in Cryptology: CRYPTO 2003 2729, 426–444. o, Kiadó: Springer. DOI:10.1007/978-3-540-45146-4_25.
↑ Coelho (2005). „Exponential memory-bound functions for proof of work protocols”. Cryptology ePrint Archive, Report.
↑ Tromp (2015). „Cuckoo Cycle; a memory bound graph-theoretic proof-of-work”. Financial Cryptography and Data Security: BITCOIN 2015 8976, 49–62. o, Kiadó: Springer. DOI:10.1007/978-3-662-48051-9_4.
↑ Abliz (2009. december 1.). „A Guided Tour Puzzle for Denial of Service Prevention”. Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009, Honolulu, HI, 279–288. o. DOI:10.1109/ACSAC.2009.33.
↑ Blokklánc, ethereum, altcoin és bitcoin szójegyzék (magyar nyelven). BitcoinBázis. (Hozzáférés: 2023. július 23.)
↑ A blokklánc technológia. [2022. április 27-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. március 21.)

Fordítás

Ez a szócikk részben vagy egészben a Proof of work című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

[1] Proof of work jelentése. [2021. szeptember 23-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. március 21.)

[2] remik: Miért jobb a proof-of-work a proof-of-stake mechanizmusnál? (magyar nyelven). BitcoinBázis, 2022. december 9. (Hozzáférés: 2023. július 23.)

[EP-mechanisms-3] Cryptocurrencies and blockchain. European Parliament, 2018. július 1. (Hozzáférés: 2020. október 29.) „the two best-known – and in the context of cryptocurrencies also most commonly used”

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

[ABuMaWo2003-5] Abadi (2005). „Moderately hard, memory-bound functions” 5, 299–327. o.

[DwoGoNao2003-6] Dwork (2003). „On memory-bound functions for fighting spam”. Advances in Cryptology: CRYPTO 2003 2729, 426–444. o, Kiadó: Springer. DOI:10.1007/978-3-540-45146-4_25.

[Coe2005-7] Coelho (2005). „Exponential memory-bound functions for proof of work protocols”. Cryptology ePrint Archive, Report.

[Tro2014-8] Tromp (2015). „Cuckoo Cycle; a memory bound graph-theoretic proof-of-work”. Financial Cryptography and Data Security: BITCOIN 2015 8976, 49–62. o, Kiadó: Springer. DOI:10.1007/978-3-662-48051-9_4.

[Abliz09-9] Abliz (2009. december 1.). „A Guided Tour Puzzle for Denial of Service Prevention”. Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009, Honolulu, HI, 279–288. o. DOI:10.1109/ACSAC.2009.33.

[10] Blokklánc, ethereum, altcoin és bitcoin szójegyzék (magyar nyelven). BitcoinBázis. (Hozzáférés: 2023. július 23.)

[11] A blokklánc technológia. [2022. április 27-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. március 21.)

[1]