Bevis for arbejde

Proof of work ( engelsk  proof-of-work, POW, PoW ) er princippet om at beskytte netværkssystemer mod misbrug af tjenester (f.eks. mod DoS-angreb eller organisering af spam - mails ), baseret på behovet for at udføre noget ret langt arbejde på klientsiden (finder problemløsning), hvis resultat nemt og hurtigt kontrolleres på serversiden (se envejsfunktion ). Hovedtræk ved de anvendte beregninger er asymmetrien af ​​tidsomkostninger - de er væsentlige for at finde en løsning og meget små for verifikation [1] . Sådanne ordninger er også kendt som klientpuslespil , beregningspuslespil eller CPU - prissætningsfunktion .

Denne beskyttelsesmetode må ikke forveksles med captchas , som tilbyder opgaver, der er nemme for en person, men vanskelige eller fuldstændig uløselige for en computer. Beviset for arbejdet er i første omgang fokuseret på at finde en løsning ved hjælp af en tidligere kendt algoritme i en begrænset tid, men et relativt lille antal operationer er påkrævet for at verificere den resulterende løsning [1] . POW-teknologier har modtaget den største distribution og udvikling inden for kryptovalutasystemer.

Historie

Kravet om bevis for arbejde blev først fremsat i artiklen "Prissætning via behandling eller bekæmpelse af uønsket post" [1] i 1993. Forfatterne foreslog følgende idé: For at få adgang til en delt ressource skal brugeren beregne en eller anden funktion, som er meget kompleks og ressourcekrævende, men som kan løses inden for rimelig tid. At beregne en funktion på klientsiden burde være meget vanskeligere end at kontrollere resultatet på serversiden. Et af de obligatoriske krav til en funktion er, at den ikke afskrives - hvis der findes flere løsninger, vil tiden kræves i forhold til deres antal. Ifølge forfatterne skaber sådanne yderligere beregninger ikke forhindringer for at sende flere almindelige breve fra en almindelig brugers computer, men behovet for konstante beregninger gør det meget ressourcekrævende at sende spam. Ifølge uafhængige skøn fører sådanne systemer faktisk til en betydelig begrænsning af antallet af breve, der kan sendes om dagen fra én computer [2] .

I 1997 lancerede Adam Back Hashcash- projektet , dedikeret til spambeskyttelse. Opgaven blev formuleret som følger: "Find en værdi x, således at SHA(x)-hashen ville indeholde N foranstillede nulbit."

I 1999 dukker begrebet bevis på arbejde op  - det blev brugt i artiklen "Proofs of Work and Bread Pudding Protocols" (forfattere - Markus Jacobsson og Ari Jewels) i tidsskriftet Communications and Multimedia Security [3] .

Den 16. august 2004 foreslog Hal Finney i sit brev til cypherpunk- forumet at bruge genanvendelige proof-of-work ( RPOW  , RPoW ) til at organisere elektronisk valuta [4] .

Satoshi Nakamoto foreslog snart bitcoin -kryptovalutaen , hvor proof-of-work bruges til i høj grad at komplicere dobbeltudgifter . Det blev foreslået at finde hashen af ​​en informationsblok ved hjælp af SHA-256- funktionen med valg af parametre, så resultatet har et givet antal høje bits på nul. Efterfølgende begyndte man at bruge KDF i andre kryptovalutaer (for eksempel Litecoin ) i stedet for SHA-256, såsom scrypt , bcrypt , PBKDF2 og andre [5] .

Eksempler på anvendelige funktioner

Liste over de mest almindelige funktioner, der bruges i proof-of-work-systemer:

• Delvis inversion hashing . Den mest kendte applikation er Hashcash -systemet [6] , som bruger delvis inversion- hash , når det sendes via e-mail. For at beregne overskriften på ét bogstav kræves der omkring 252 hash-beregninger, som skal genberegnes for hvert nyt bogstav. Samtidig er det hurtigt at kontrollere rigtigheden af ​​den beregnede kode - en enkelt SHA-1- beregning bruges med en forudklaret etiket [7] [8] [9] .
• Funktioner baseret på Merkle-træer [10] . Det mest berømte eksempel på denne variant kan findes i Bitcoin -systemet , hvor multilevel hashing bruges som bevis på arbejdet - hashen fra den forrige blok bliver et element i den næste. Der er således ingen måde at ændre en blok uden at ændre hasherne i alle efterfølgende blokke. Samtidig er kontrol af hele kædens integritet begrænset til en enkelt beregning af hasherne for den aktuelle blok og den forrige. En hash genkendes kun som sand, hvis værdien af ​​en hvilken som helst karakteristik af hashsummen opfylder det valgte kriterium, for eksempel i bitcoin - antallet af foranstillede nuller af hashsummen er større end eller lig med værdien af ​​en speciel parameter, der bestemmer den vanskelighed , der kræves i øjeblikket for at opretholde den planlagte hastighed for nye blokke. For at søge efter en sådan hash-sum er det nødvendigt at genberegne den flere gange med opregning af vilkårlige værdier af nonce- parameteren [11] .
• Kvadratisk rest modulo et stort primtal [12]
• Fiat protokol signatur - Shamira [12]
• Funktion baseret på Diffie-Hellman-protokollen [13]
• Hukommelsesbundet funktion ( en:Memory bound function ) [14]
• Gøghashing [15]

Potentielle sårbarheder og angreb på informationssystemer baseret på POW

Eksperter diskuterer fortsat, om POW-beskyttelse er tilstrækkelig effektiv mod DoS-angreb og spam [16] [17] .

Angreb 51%

Bitcoin , som mange andre kryptovalutaer, kan potentielt være genstand for et "51% angreb": hvis en angriber kontrollerer mere end halvdelen af ​​al computerkraften på netværket, så har han mulighed for kun at bekræfte sine egne blokeringer, mens han ignorerer andre . Dette giver ham ikke kun mulighed for at modtage al den kryptovaluta, der udsendes på samme tid, men også blokere alle eller udvalgte transaktioner, hvilket potentielt kan føre til "forsvinden" fra kontoen for kryptovalutaen modtaget fra de transaktioner, der ikke vil blive inkluderet i ny version af blockchain [11] .

Dobbelt forbrug

Dobbelt forbrug (dobbelt forbrug) er den gentagne overførsel af de samme aktiver. Dette angreb er opdelt i flere undertyper.

• Race angreb .  _ _ Angriberen foretager transaktion X, betaler for køb af varer, mens han samtidig overfører de samme penge til sin anden konto med transaktion Y. Hvis sælgeren ikke ventede på bekræftelsen af ​​transaktionen og sendte varerne, så tog han en stor risiko , da der er 50 % chance for, at transaktion Y kan komme ind i den sande kæde, og denne sandsynlighed øges, hvis angriberen målrettet vælger netværksknuderne til at udføre denne eller hin operation [18] .

• Finneys angreb er som følger: angriberen forsøger at finde en blok, der indeholder hans transaktion Y. Men når blokken er fundet, sender angriberen transaktion X, hvorefter han køber varerne. Sælger venter på bekræftelse af transaktion X og sender varerne. Hvis der i dette øjeblik dukker en blok med transaktion Y op, så skabes der en gaffelsituation, hvor minearbejdere skal vælge en af ​​de to blokke for at fortsætte blockchain-kæden. Ved at koncentrere en stor mængde computerressourcer i hænderne på en angriber, kan han markant øge sandsynligheden for at vælge en blok med operation Y. En bekræftet transaktion er således ikke garanteret at være gyldig [19] .

Selvisk minedrift

I selvisk minedrift er angriberens mål  at kontrollere netværket, på trods af at han har computerressourcer med en samlet kapacitet på mindre end 50%. Dette opnås ved, at angriberen hævder, at hans pool er mere rentabel til minedrift end andre pools, hvilket tiltrækker tredjeparts minearbejdere. Angriberen udgiver blokke på en sådan måde, at andre minearbejderes og puljers computerressourcer er spildt. Det omtrentlige forløb af algoritmen er som følger:

1. Poolen miner i hemmelighed sin private kæde fra alle.
2. Hvis poolen finder en ny blok til sin private kæde, så:
   1. Hvis den oprindelige kæde er splittet, så offentliggør angriberen sin blok, således bliver hans kæde længere og bliver sand, og kæden af ​​ærlige minearbejdere kasseres.
   2. Hvis der ikke er nogen gaffel endnu, så fortsætter poolen med at mine sin private kæde i hemmelighed, hvilket øger dens forspring.
3. Hvis den offentlige kæde finder en blok til den offentlige kæde, så:
   1. Hvis den offentlige kæde er foran den hemmelige, så kasserer angriberens pulje sine upublicerede blokke og begynder at mine fra den nye offentlige blok.
   2. Hvis kæderne er ens, så udgiver angriberens pulje alle sine blokke og går dermed ind i hullet i sin kæde.
   3. Hvis den offentlige kæde er nogle (N) blokke bag den private kæde, så udgiver puljen en blok mere (N+1), som isolerer en ny ærlig blok.

I næsten alle udfald er ærlige minearbejdere taberne, hvilket tvinger dem til at slutte sig til den kriminelle pulje [20] .

Kritik af informationssystemer baseret på POW

Modstandere af POW-tilgangen fremhæver, ud over en række potentielle sikkerhedsproblemer , følgende ulemper:

• Sandsynligheden for vellykket oprettelse af den næste blok af minearbejderen er direkte proportional med den computerkraft, den har, hvilket fører til en konstant stigning i mængden og kvaliteten af ​​udstyr for hvert netværksmedlem. Minedrift ved hjælp af POW-algoritmer kræver således en ekstrem stor mængde elektricitet. Derfor er POW-tilgangen ikke den bedste løsning med hensyn til energieffektivitet [21] [22] .
• Resultaterne af computerhash- funktioner er ikke nødvendige andre steder end i selve netværket. Siden fremkomsten af ​​teknologien har samfundet forsøgt at finde på en måde at dirigere alle netværkets computerressourcer til at løse et eller andet nyttigt matematisk eller industrielt problem, men dette er ikke blevet implementeret i sin rene form [23] .

Forsøg på at slippe af med manglerne ved POW har ført til fremkomsten af ​​POS ( engelsk  proof-of-stake , proof of stake) og adskillige hybride muligheder.

Eksempler på hybridteknologier

Eksempler på hybride ordninger, der kombinerer ideerne om POS og POW, kan findes i mange kryptovalutaer. I dem består blockchain af blokke af begge typer, hvilket gør omskrivning af transaktionshistorier til en vanskelig opgave, da POW-blokke fungerer som checkpoints i betragtning af den samlede kompleksitet af arbejdet i hele kæden. I sådanne algoritmer tjener POW-blokke typisk som indikatorer for virkeligt arbejde, hvilket giver en yderligere garanti for pålidelighed for handlende, når de arbejder med transaktioner. POW-blokke kan bruges til at udstede valuta, og POS-blokke kan betragtes som potentiel indtægt fra indskuddet [24] .

Bevis for aktivitet

En algoritmeprototype, der endnu ikke er implementeret, som består i, at indehavere først går ind i den generelle proces efter noget arbejde er blevet udført af POW-deltagere, hvilket reducerer chancerne for et 51% angreb, da majoritetsejeren ikke vil være i stand til udelukkende at kontrollere oprettelsen af ​​nye blokke [25] .

Sådan fungerer algoritmen:

1. POW-minearbejderen leder efter en hash med passende sværhedsgrad.
2. Den fundne hash sendes til netværket, mens den ikke er en blok, men kun det første trin, en slags skabelon, der er nødvendig for dens oprettelse.
3. En hash bestående af 256 pseudo-tilfældige bit tolkes som N tal, som hver er tildelt en satoshi.
4. Der etableres et en-til-en-forhold mellem hver satoshi og den nuværende ejers offentlige nøgle.
5. Så snart alle N-ejere sætter deres signaturer på denne blok, er outputtet en fuldgyldig blok.
6. Hvis en af ​​indehaverne ikke er tilgængelig eller ikke deltager i minedrift, fortsætter resten af ​​minearbejderne med at generere skabeloner med forskellige kombinationer af kandidatindehavere.
7. På et tidspunkt vil den påkrævede blok blive underskrevet det nødvendige antal gange. Blokbelønningen fordeles mellem POW-minearbejderen og alle N-indehavere.

Bevis for forbrænding

Penge sendes til en adresse, der er en hash af et tilfældigt tal; det er garanteret, at de ikke kan bruges fra denne adresse, da sandsynligheden for at hente nøgler til den har en tendens til nul. Til gengæld får minearbejderen en permanent chance for at finde en PoB-blok og modtage en belønning for den. Minedrift i dette tilfælde er arrangeret på en sådan måde, at chancerne for succes afhænger af antallet af brændte mønter. Analogt er brænding som et ikke-refunderbart POS-indskud eller en investering i virtuel hardware til POW-mining. Fra et økonomisk synspunkt er denne algoritme bedre egnet til de senere stadier af udvikling af kryptovaluta, hvor det meste af pengemængden allerede er genereret [26] .

Bevis for kapacitet

Algoritmen for bevis for kapacitet (eller pladsbevis ) er som følger: til minedrift er det nødvendigt at allokere en betydelig mængde hukommelse på computeren, hvorefter et stort antal store datablokke oprettes fra den offentlige nøgle og tilfældige tal ved gentagen hashing . I hver datablok får vi et indeks fra den sidste header, hvorefter vi vælger et lille stykke af blokken med dette indeks, en chunk .  Jo mere hukommelse der tildeles, jo flere bidder får vi. Betingelsen skal være opfyldt, at hashen af ​​chunken og den sidste header skal være mindre end målet. Hver megabyte hukommelse bruges således som en analog til en lottokupon og øger chancen for minedriftssucces [27] .

Bevis for forskning

Beviset for forskningsalgoritmen blev udviklet af GridCoin - projektet for at styre PoW-netværkets computerkraft til at løse videnskabelige problemer på BOINC-platformen . Bevis for forskning bruger samtidig bevis for arbejde til at belønne deltagere for gennemførte beregninger og bevis for indsats for at tilskynde til langsigtet deltagelse i projektet [28] .

Energiineffektivitet

POW baserede systemer er ekstremt ressourcekrævende.

• I 2013 overhalede den samlede computerkraft brugt på POW i Bitcoin-netværket 256 gange de 500 mest kraftfulde supercomputere i verden det år tilsammen [29] .
• I 2017 krævede det i gennemsnit 163 kWh energi at gennemføre én transaktion i Bitcoin -systemet. Med denne mængde energi er det muligt fuldt ud at opfylde behovene hos en familie på tre personer, der bor i et lille en-etagers hus i fem og en halv dag. Udvinding af kryptovaluta i Bitcoin- og Ethereum -netværkene tog i alt mere energi end hele Syriens befolkning forbrugte [21] [22] .

Se også

• captcha
• Bitmeddelelse
• Offentlig nøgle kryptosystem
• Envejs funktion

Noter

1. ↑ 1 2 3 Prissætning via behandling eller bekæmpelse af uønsket post Arkiveret 12. december 2017 på Wayback Machine (1993  )
2. ↑ "Proof-of-Work" viser sig ikke at virke Arkiveret 20. januar 2017 på Wayback Machine , 2004 "Hvis vi forsøger at gøre det uøkonomisk at sende spam, må vi begrænse afsendere til 1.750 meddelelser om dagen"
3. ↑ Proofs of Work and Bread Pudding Protocols Arkiveret 26. juli 2017 på Wayback Machine (1999  )
4. ↑ RPOW - Genanvendelige beviser for arbejde arkiveret 5. oktober 2017 på Wayback Machine (2004  )
5. ↑ The Proof-of-Work in Cryptocurrencies: Kort historie. Del 1 Arkiveret 5. september 2017 på Wayback Machine (2015  )
6. ↑ Hashcash - A Denial of Service Counter-Measure (2002  )
7. ↑ Tilbage, Adam HashCash . Hentet 25. juni 2022. Arkiveret fra originalen 29. september 2017.  (ubestemt) Populært proof-of-work system. Første meddelelse i marts 1997.
8. ↑ Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. Bekæmpelse af uønsket e-mail via sikker klassificering  (neopr.)  // Financial Cryptography. - 1998. - S. 198-213 .
9. ↑ Wang, Xiao-Feng; Reiter, Michael. Forsvar mod denial-of-service-angreb med puslespilsauktioner  //  IEEE Symposium on Security and Privacy '03: journal. - 2003. - Maj.
10. ↑ Coelho, Fabien En (næsten) konstant-indsats løsning-verifikation proof-of-work protokol baseret på Merkle træer . Kryptologi ePrint-arkiv, rapport . Hentet 29. oktober 2017. Arkiveret fra originalen 26. august 2016. (ubestemt)
11. ↑ 1 2 Bitcoin: Et peer-to-peer elektronisk kontantsystem arkiveret 20. marts 2014 på Wayback Machine 
12. ↑ 1 2 Dwork, Cynthia; Naor, Moni Prisfastsættelse via behandling, eller, bekæmpelse af uønsket post, fremskridt inden for kryptologi  //  CRYPTO'92: Lecture Notes in Computer Science No. 740: journal. - Springer, 1993. - S. 139-147 .
13. ↑ Waters, Brent; Juels, Ari; Halderman, John A.; Felten, Edward W.Nye teknikker til outsourcing af klientpuslespil til DoS-modstand  (neopr.)  // 11th ACM Conference on Computer and Communications Security. – 2004.
14. ↑ Dwork, Cynthia; Goldberg, Andrew; Naor, MoniOm hukommelsesbundne funktioner til bekæmpelse af spam  (neopr.)  // Advances in Cryptology: CRYPTO 2003. - Springer, 2003. - Vol. 2729 . - S. 426-444 .
15. ↑ Tromp, John. Gøg cyklus; a memory bound graph-theoretic proof-of-work  //  Financial Cryptography and Data Security: BITCOIN 2015 : journal. - Springer, 2015. - S. 49-62 .
16. ↑ Laurie, Ben; Clayton, Richard. Bevis for arbejde viser sig ikke at virke  (neopr.)  // WEIS 04. - 2004. - Maj.
17. ↑ Liu, Debin; Camp, L. Jean. Proof of Work kan virke  (neopr.)  // Fifth Workshop on the Economics of Information Security. - 2006. - Juni.
18. ↑ Angreb i kryptovalutaernes verden arkiveret 19. september 2016 på Wayback Machine 
19. ↑ Analyse af hashrate-baseret dobbeltforbrug Arkiveret 4. september 2017 på Wayback Machine (2012  )
20. ↑ Angreb i kryptovalutaernes verden Arkiveret 19. september 2016 på Wayback Machine (2015  )
21. ↑ 1 2 Bitcoin Energy Consumption Index Arkiveret 25. januar 2022 på Wayback Machine 
22. ↑ 1 2 Ethereum Energy Consumption Index (beta) Arkiveret 11. oktober 2017 på Wayback Machine 
23. ↑ The Proof-of-Work in Cryptocurrencies: Kort historie. Del 2 Arkiveret 14. marts 2016 på Wayback Machine 
24. ↑ Alternativer til bevis for arbejde, del 2 Arkiveret 4. marts 2016 på Wayback Machine (2015  )
25. ↑ Bevis for aktivitet: Udvidelse af Bitcoins bevis på arbejde via bevis for indsats Arkiveret 17. oktober 2017 på Wayback Machine 
26. ↑ En peer-to-peer kryptovaluta med bevis-of-forbrænding "Mining without Powerful Hardware" Arkiveret 10. oktober 2017 på Wayback Machine (2014  )
27. ↑ Proofs of Space: When Space is of the Essence Arkiveret 5. november 2017 på Wayback Machine 
28. ↑ Proof- of -Research - Gridcoin  . wiki.gridcoin.us. Hentet 4. september 2018. Arkiveret fra originalen 4. september 2018.
29. ↑ Global Bitcoin Computing Power nu 256 gange hurtigere end Top 500 supercomputere, kombineret! Arkiveret 8. juni 2017 på Wayback Machine (2013  )