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]

Előzmények módosítása

A blokklánchoz hozzáadott minden egyes blokkot, kezdve a szóban forgó tranzakciót tartalmazó blokkal, tranzakció-visszaigazolásnak neveznek, amely valójában egy azonosító kulcs a következő, még meg nem nyitott blokkhoz, ami a blokkláncot hamisíthatatlanná teszi.^[12][13] Lehetetlen megváltoztatni az adatokat egy összegyűjtött blokkban anélkül, hogy a blokklánc összes többi blokkját törölnénk.^[14][15] Ideális esetben a kriptovaluta-fizetést fogadó kereskedőknek és szolgáltatásoknak meg kell várniuk legalább egy visszaigazolás terjedését a hálózatban, mielőtt feltételeznék, hogy a fizetés megtörtént.^[16] Minél több megerősítésre számít egy kereskedő, annál nehezebb egy támadónak sikeresen visszacsinálni egy tranzakciót a blokkláncon - kivéve, ha a támadó a hálózat összteljesítményének több mint felét ellenőrzi, ebben az esetben 51%-os támadásról beszélünk.^[17]