Bitcoin: Peer-to-peer sistem elektronskog novca

Satoshi Nakamoto
[email protected]
www.bitcoin.org

Translated in Serbian from bitcoin.org/bitcoin.pdf by ECD

Sažetak. Potpuna peer-to-peer verzija elektronskog novca omogućila bi slanje uplata putem interneta direktno od jedne strane ka drugoj bez posredovanja finansijskih institucija. Digitalni potpisi pružaju deo rešenja, ali se glavni benefiti gube ako je i dalje potrebna pouzdana treća strana za sprečavanje dvostruke potrošnje. Predlažemo rešenje problema dvostruke potrošnje korišćenjem peer-to-peer mreže. Mreža vremenski označava transakcije tako što ih hešuje u tekući lanac dokaza o radu (proof of work) temeljen na hešu, formirajući zapis koji se ne može promeniti bez ponovnog rada i objavljivanja dokaza o tom radu. Najduži lanac ne služi samo kao dokaz niza događaja, nego i kao dokaz da je taj niz događaja potvrđen od strane dela peer-to-peer mreže koja poseduju najveću zbirnu procesorsku snagu (CPU). Sve dok većinu procesorske snage kontrolišu čvorovi (nodes) koji ne sarađuju u napadu na mrežu, oni će generisati najduži lanac i nadmašiti napadače. Sama mreža zahteva minimalnu strukturu. Poruke kroz mrežu se prenose uz pretpostavku da svaki čvor čini maksimalan napor da poruku prenese u svom izvornom obliku i na optimalan način, a čvorovi mogu napustiti mrežu i ponovo joj se pridružiti po želji, prihvatajući najduži lanac dokaza o radu kao dokaz onoga što se dogodilo dok ih nije bilo.

1. Uvod

Trgovina na Internetu počela je da se oslanja skoro isključivo na finansijske institucije koje služe kao pouzdani posrednici pri obradi elektronskih plaćanja. Iako sistem radi dovoljno dobro za većinu transakcija i dalje trpi od inherentnih slabosti modela utemeljenog na poverenju.

Potpuno nepovratne transakcije zapravo nisu moguće, jer finansijske institucije ne mogu izbeći posredovanje u rešavanju eventualnih sporova. Troškovi posredovanja povećavaju troškove transakcija, ograničavaju minimalnu praktičnu veličinu transakcija i onemogućuju male, povremene transakcije jer postoji velika šteta zbog gubitka mogućnosti da se izvrše nepovratna plaćanja za nepovratne usluge. Uz mogućnost povraćaja transakcije, potreba za poverenjem raste. Trgovci moraju biti oprezni prema svojim kupcima i tražiti im više informacija nego što bi inače bilo neophodno. Određeni procenat prevara prihvaćen je kao neizbežan. Ovi troškovi i nepouzdanost plaćanja mogu se izbeći korišćenjem gotovine, ali ne postoji mehanizam za elektronsko plaćanje bez pouzdane treće strane.

Ono što je potrebno je elektronski sistem plaćanja zasnovan na kriptografskom dokazu umesto na poverenju, koji omogućava da bilo koje dve strane direktno i dobrovoljno međusobno trguju bez potrebe za posrednikom. Transakcije koje su nepovratne bi zaštitile prodavce od prevara, a escrow mehanizmi mogli bi se lako implementirati radi zaštite kupaca. U ovom dokumentu predlažemo rešenje problema dvostruke potrošnje korišćenjem peer-to-peer distribuiranog servera vremenskih oznaka (timestamp) za generisanje računarskog dokaza o hronološkom redosledu transakcija. Sistem je siguran sve dok pošteni čvorovi zajedno kontrolišu više procesorske snage procesora nego bilo koja udružena grupa napadačkih čvorova.

2. Transakcije

Elektronski novčić definišemo kao lanac digitalnih potpisa. Svaki vlasnik prenosi novčić na sledećeg digitalnim potpisivanjem heša prethodne transakcije i javnog ključa sledećeg vlasnika, dodajući ih potom na kraj novčića. Primalac transakcije može da verifikuje potpise, a time i lanac vlasništva.

Problem je naravno u tome što primalac ne može potvrditi da jedan od prethodnih vlasnika nije dva puta poslao isti novčić. Uobičajeno rešenje je uvođenje pouzdanog centralizovanog posrednika, kreatora novčića koji proverava sve transakcije. Nakon svake transakcije, novčić se mora vratiti kreatoru kako bi se izdao novi novčić i veruje se da samo za novčiće izdate direktno od kreatora možemo biti sigurni da nisu dva puta potrošeni. Problem sa ovim rešenjem je što sudbina čitavog novčanog sistema zavisi od kompanije koja kreira novčiće, jer svaka transakcija mora da prođe kroz nju, baš kao što je slučaj sa bankom.

Treba nam način da primalac bude siguran da prethodni vlasnici nisu potpisali nikakve ranije transakcije kojim bi potrošili taj novčić. Za naše potrebe, računamo transakciju koja se prva desila i ne zanimaju nas naredni pokušaji da se isti novčić ponovo pošalje. Jedini način da sa sigurnošću potvrdimo da taj novčić nije prethodno bio poslat je da imamo informacije o svim transakcijama koje su se ikada desile. U modelu baziranom na centalizovan kreatoru, taj kreator je imao informacije o svim transakcijama i odlučivao koja transakcija je prva stigla. Da bismo to postigli bez pouzdanog posrednika, transakcije moraju biti javno objavljene [1] i potreban nam je sistem u kojem učesnici mogu da se dogovore o jedinstvenoj istoriji redosleda kojim su transakcije primljene. Primaocu je potreban dokaz da se u trenutku dešavanja svake od transakcija većina čvorova složila oko toga da je baš ta transakcija bila ona koja je prva primljena.

3. Server vremenskih oznaka

Rešenje koje predlažemo počinje serverom vremenskih oznaka. Server vremenske oznake radi tako što uzima heš bloka podataka kojem će se dodeliti vremenska oznaka i objavi taj heš svima u mreži, slično kao u novinama ili kao post na Usenet mreži [2-5]. Vremenska oznaka očigledno dokazuje da su podaci morali postojati u to vreme kako bi ušli u haš. Svaka vremenska oznaka sadrži prethodnu vremensku oznaku u svom hešu, formirajući tako lanac, pri čemu svaka dodatna vremenska oznaka pojačava potvrde onih pre nje.

4. Dokaz o radu (Proof-of-Work)

Da bismo implementirali distribuirani server vremenskih oznaka na peer-to-peer principu, moraćemo da koristimo sistem dokaza o radu sličan Hashcash-u Adama Back-a [6], umesto Uneset postova ili novinskih objava. Dokaz o radu uključuje traženje vrednosti koja će, kada se hešuje, na primer pomoću SHA-256 heš funkcije, stvarati heš čiji binarni zapis započinje određenim brojem nula. Prosečna količina potrebnog rada eksponencijalno raste sa brojem potrebnih početnih nula, a može se proveriti izvršavanjem samo jedne heš fuknkcije.

Za našu mrežu vremenskih oznaka implementiramo dokaz o radu povećavajući nonce broja u bloku sve dok se ne pronađe ona vrednost nonce-a koja daje hešu bloka potreban broj početnih nula. Jednom kada se procesorska snaga utroši kako bi se zadovoljio dokaz o radu, blok se ne može izmeniti bez ponovljenog rada. Kako se kasniji blokovi vežu na taj blok, rad potreban da se on izmeni uključivao bi i ponovno obrađivanje svih blokova nakon njega.

Dokaz o radu takođe rešava problem utvrđivanja većine pri odlučivanju. Ako bi se ​​većina zasnivala na principu jednog glasa po IP adresi, mogao bi je narušiti svako ko je u stanju da glasa sa više IP adresa odjednom. Dokaz o radu u osnovi predstavlja jedan glas po jedinici procesorske snage. Većinska odluka je predstavljena najdužim lancem u čije je stvaranje zapravo investirano najviše rada prilikom dokazivanja. Ako većinu procesorske snage kontrolišu pošteni čvorovi, pošten lanac će rasti najbrže i nadmašiće sve konkurentske lance. Da bi izmenio neki od prethodnih blokova, napadač bi morao da ponovi dokaz o radu za taj blok i sve blokove nakon njega, a zatim da sustigne i nadmaši količinu rada poštenih čvorova. Kasnije ćemo pokazati da se dodavanjem novih blokova eksponencijalno smanjuje verovatnoća da će sporiji napadač uspeti da sustigne pošteni lanac.

Da bi se kompenzovalo povećanje brzine hardvera i promenljivo interesovanje ljudi za vođenje čvorova tokom vremena, težina obavljanja dokaza o radu (proof-of-work difficulty) određuje se prema prosečnom broju blokova krairanih za sat vremena. Ako se blokovi stvaraju prebrzo, težina se povećava.

5. Mreža

Koraci za vođenje mreže su sledeći:

1) Nove transakcije se prosleđuju svim čvorovima u mreži.
2) Svaki čvor prikuplja nove transakcije u blok.
3) Svaki čvor radi na pronalaženju dokaza o radu dovoljnog nivoa težine za svoj blok.
4) Kada čvor pronađe dokaz o radu, on emituje taj blok ka svim čvorovima.
5) Čvorovi prihvataju blok samo ako su sve transakcije u njemu ispravne i nisu već potrošene.
6) Čvorovi izražavaju prihvatanje bloka radeći na stvaranju sledećeg bloka u lancu, koristeći heš prihvaćenog bloka kao prethodni heš.

Čvorovi uvek smatraju da je najduži lanac ispravan i nastaviće da rade na njegovom produžavanju. Ako dva čvora istovremeno emituju različite verzije sledećeg bloka, neki čvorovi prvo mogu primiti jedan ili drugi blok. U tom slučaju svaki čvor radi na prvom koji je dobio, ali čuvaju drugu kariku lanca u slučaju da ona postane duža. Dilema će biti rešena kada se pronađe sledeći dokaz o radu i jedna karika postane duža; čvorovi koji su radili na drugoj karici lanca će se prebaciti na dužu kariku.

Emitovanje novih transakcija ne mora nužno doći do svih čvorova. Sve dok stižu do velikog broja čvorova, te transakcije će ući u blok. Slično važi i za blokove, ni oni ne moraju doći odmah do svih čvorova. Ako neki čvor propusti da primi informaciju o bloku, kada mu stigne sledeći blok,primetiće da je propustio jedan, pa će ga tražiti naknadno.

6. Podsticaj

Po pravilu, prva transakcija u bloku je posebna transakcija koja kreira novi novčić u vlasništvu kreatora bloka. Ovo daje podsticaj čvorovima da podrže mrežu i pruža način za početnu ubacivanje novčića u opticaj, budući da ne postoji centralno telo koje ih izdaje. Stalno dodavanje konstantne količine novih novčića liči na rudarenje zlata, gde rudari ulažu resurse kako bi izrudarili nove količine zlata i ubacili ih u opticaj. U našem slučaju ulaže se procesorsko vreme i električna energija.

Podsticaj se takođe može finansirati i transakcionim naknadama. Ako je iznos izlaznog dela transakcije manji od ulaznog, razliku čini naknada za transakciju koja se dodaje iznosu nagrade za kreatora bloka koji sadrži tu transakciju. Nakon što predefinisani broj novčića uđe u opticaj, podsticaj mogu u potpunosti činiti transakcione naknade, čime se sistem oslobađa inflacije.

Čvorovi su na ovaj način podstaknuti da ostanu pošteni. Ako je pohlepni napadač u stanju da angažuje više procesorske snage od svih poštenih čvorova zajedno, morao bi da bira između toga da poništi svoje izvršene transakcije i time prevari ljude ili da procesorsku snagu koristi za stvaranje novih novčića. On bi trebalo bi uvidi da je isplativije igrati po pravilima koja ga nagrađuju sa više novih novčića od svi drugi zajedno, nego da potkopava sistem i vrednost sopstvenog bogatstva.

7. Oslobađanje prostora na hard disku

Kada je dovoljno blokova dodato nakon poslednje transakcije novčića, prethodne transakcije tog novčića se mogu odbaciti kako bi se uštedeo prostor na hard disku. Kako bi se to ostvarilo bez razbijanja heša bloka, transakcije su hešovane u Merkleovo stablo (Merkle Tree) [7] [2] [5], gde je samo koren uključen u heš bloka. Stari blokovi se tada mogu sabiti uklanjanjem nepotrebnih grana drveta. Unutrašnji heševi ne moraju biti skladišteni.

Zaglavlje bloka bez transakcija bilo bi oko 80 bajtova. Ako pretpostavimo da su blokovi generisani svakih 10 minuta, 80 bajtova * 6 * 24 * 365 = 4,2 MB godišnje. Imajući u vidu činjenicu da se u 2008. godini računari uglavnom prodaju sa oko 2 GB RAM-a i Murov zakon koji predviđa trenutni rast od 1,2 GB godišnje, skladištenje ne bi trebalo da predstavlja problem čak i ako se zaglavlja bloka moraju čuvati u memoriji.

8. Pojednostavljena verifikacija plaćanja

Moguće je verifikovati plaćanja bez vođenja čitavog mrežnog čvora. Korisnik samo treba da sačuva kopiju zaglavlja blokova najdužeg lanca dokaza o radu, do koje može doći upitom ka mrežnim čvorovima dok se ne uveri da je dobio najduži lanac i dobije Merkleova granu

koja povezuje transakciju sa blokom u koji je uneta vremenska oznaka za tu transakciju. Ne može samostalno proveriti transakciju, ali povezujući je sa mestom u lancu može videti da je prihvaćena od strane čvora mreže i da su na njen blok dodati naknadni blokovi što dalje potvrđuje da ju je mreža prihvatila.

Kao takva, verifikacija je pouzdana sve dok pošteni čvorovi kontrolišu mrežu, ali je ranjiva ako napadač nadjača ostatak mreže. Čvorovi mreže mogu sami proveriti transakcije, ali napadačeve lažne transakcije mogu zavarati one koji koriste pojednostavljenu metodu verifikacije transakcija sve dok je on u stanju da nadjačava ostatak mreže. Jedna od strategija zaštite bila bi prihvatanje upozorenja čvorova mreže kada otkriju nevažeći blok, pri čemu bi korisnikov softver morao da preuzme ceo blok i sporne transakcije kako bi potvrdio nepravilnost. Biznisi koji primaju česte uplate će verovatno želeti da pokrenu i vode sopstvene čvorove radi brže verifikacije i potrebe da im sigurnost ne zavisi od drugih.

9. Kombinovanje i deljenje vrednosti

Iako bi bilo moguće pojedinačno rukovati novčićima, bilo bi nezgrapno kreirati zasebnu transakciju za svaki cent u toj transferu. Da biste dozvolili podelu i kombinovanje vrednosti, transakcije sadrže više ulaza i izlaza. Obično će postojati ili jedan ulaz iz veće prethodne transakcije ili više unosa koji kombinuju manje iznose, a najviše dva izlaza: jedan za samo plaćanje, a jedan koji vraća kusur, ako ga ima, nazad pošiljaocu.

Treba napomenuti da situacija u kojoj transakcija zavisi od nekoliko drugih transakcija, a te transakcije zavise od još mnogo više, ovde nije problem. Nikada ne postoji potreba za izdvajanjem istorije pojedinačne transakcije.

10. Privatnost

Tradicionalni bankarski model postiže odgovarajući nivo privatnosti ograničavanjem pristupa informacijama na strane uključene u transakciju i posrednika. Neophodnost javnog objavljivanja svih transakcija isključuje mogućnost primene pomenutog modela, ali privatnost se i dalje može zadržati na drugi način: čuvanjem javnih ključeva (public keys) anonimnim. Javnost može videti da neko šalje iznos nekom drugom, ali bez informacija koje povezuju transakciju sa bilo kim. Ovo je slično količini informacija koje objavljuju berze, gde se vreme i veličina pojedinačnih trgovina čine javnim, ali bez navođenja ko su stranke uključene u tu trgovinu.

Kao dodatni zaštitni zid, preporučljivo je koristiti novi par ključeva za svaku transakciju, kako ne bi bili povezane sa zajedničkim vlasnikom. Neka povezivanja su i dalje neizbežna kod transakcija sa više ulaza, koje nužno otkrivaju da su njihovi ulazi bili u vlasništvu istog vlasnika. Rizik je taj da bi se otkrivanjem vlasnik ključa mogle otkriti i ostale transakcije koje su pripadale tom vlasniku.

11. Proračuni

Razmatramo scenario u kome napadač pokušava da generiše alternativni lanac brže od poštenog lanca. Čak i ako se to postigne, to ne omogućuje proizvoljne promene u sistemu, poput stvaranje vrednosti ni iz čega ili uzimanje novca koji nikada nije pripadao napadaču. Pošteni čvorovi neće prihvatiti nevažeće transakcije kao uplatu i nikada neće prihvatiti blok koji ih sadrži. Napadač može samo pokušati da promeni jednu od svojih transakcija kako bi vratio novac koji je nedavno potrošio.

Trka između poštenog lanca i lanca napadača može se predstaviti kao binomska distribucija slučajne diskretne varijable (Binomial Random Walk). Uspešni ishod je da se pošten lanac produži za jedan blok, povećavajući svoje vođstvo za +1, a neuspešni ishod je da se napadačev lanac produži za jedan blok, smanjujući zaostatak za -1.

Verovatnoću da napadač nadoknadi određeni deficit možemo izraziti kroz problem kockareve propasti (Gambler’s Ruin Problem). Pretpostavimo da kockar sa neograničenim iznosom novca počinje sa zaostatkom i igra potencijalno beskonačan broj ponovljenih igara u pokušaju da nadoknadi zaostatak. Možemo izračunati verovatnoću za nadoknađivanje zaostatka ili da će napadač stići pošten lanac, na sledeći način [8]:

p= verovatnoća da pošten čvor pronađe sledeći blok
q= verovatnoća da napadač pronađe sledeći blok
q_z= verovatnoća da će napadač ikada dostići z blokova zaostatka

S obzirom na našu pretpostavku da je p > q, verovatnoća pada eksponencijalno kako se povećava broj blokova koje napadač mora da nadoknadi. Sa šansama protiv njega, ako mu se u početku ne posreći, njegove šanse postaju manje i manje sa povećanjem zaostatka.

Sada razmatramo koliko primalac nove transakcije treba da čeka pre nego što postane

dovoljno siguran da pošiljalac ne može promeniti transakciju. Pretpostavljamo da je pošiljalac napadač koji želi da natera primaoca da veruje da mu je platio, a zatim nakon nekog vremena tu transakciju preusmeri ka sebi. Primalac će primetiti kada se to dogodi, ali pošiljalac se nada da će tad već biti prekasno.

Primalac generiše novi par ključeva i daje javni ključ pošiljaocu neposredno pre potpisivanja transakcije. Ovo sprečava pošiljaoca da unapred pripremi lanac blokova radeći na njemu neprekidno dok mu se ne posreći da stekne dovoljnu prednost i u tom trenutku izvrši transakciju. Kada se transakcija pošalje, nepošteni pošiljalac počinje tajno da radi na paralelnom lancu koji sadrži alternativnu verziju njegove transakcije.

Primalac čeka dok transakcija ne bude dodata u blok, i dok z blokova nije dodato nakon tog bloka. On ne zna tačno koliko je napadač napredovao, ali pod pretpostavkom da su pošteni blokovi kreirani očekivanom dinamikom, potencijalni napredak napadača će biti prikazan kao Poasonova distribucija sa očekivanom vrednošću:

Kako bismo izračunali verovatnoću da napadač ipak može da nadoknadi zaostatak, množimo gustinu verovatnoće za svaki nivo napretka koji je mogao da ostvari sa verovatnoćom da od tog trenutka može da potpuno nadoknadi zaostatak:

Preuređujemo formulu kako bismo izbegli sabiranje beskonačnog broja sabiraka zbog repa distribucije:

I konvertujemo u programski kod u programskom jeziku C…

Kroz par primera, vidimo da verovatnoća opada eksponencijalno sa porastom z.

Rešavanje za P < 0.1%…

12. Zaključak

Predložili smo sistem za elektronske transakcije bez oslanjanja na poverenje. Počeli smo sa uobičajenim šablonom i novčićima nastalim iz digitalnih potpisa, koji pruža snažnu kontrolu nad vlasništvom, ali je nepotpun bez načina da se spreči dvostruka potrošnja. Kako bismo ovo rešili, predložili smo peer-to-peer mrežu koja koristi dokaz o radu za čuvanje javne istorije transakcija čija izmena napadačima brzo postaje računski nepraktična ako pošteni čvorovi kontrolišu većinu procesorske snage. Mreža je robusna u svojoj nestrukturiranoj jednostavnosti. Svi čvorovi rade istovremeno uz malo koordinacije. Ne treba ih identifikovati, jer se poruke ne usmeravaju na jedno određeno mesto nego samo trebaju biti prenete uz maksimalan napor od strane čvorova da se taj prenos odradi na predviđen način. Čvorovi mogu da napuste i ponovo se pridruže mreži po želji, prihvatajući lanac dokaza o radu kao dokaz onoga što se dogodilo dok ih nije bilo. Oni glasaju svojom procesorskom snagom, izražavajući svoje prihvatanje validnih blokova time što pokušavaju da ih nadgrade novim blokovima i odbacuju nevažeće blokove odbijanjem ih nadgrađuju. Sva potrebna pravila i podsticaji mogu se nametnuti ovim mehanizmom postizanja konsenzusa.

Reference:

[1] W. Dai, „b-money,“ http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila, and J.-J. Quisquater, „Design of a secure timestamping service with minimal
trust requirements,“ In 20th Symposium on Information Theory in the Benelux, May 1999.
[3] S. Haber, W.S. Stornetta, „How to time-stamp a digital document,“ In Journal of Cryptology, vol 3, no
2, pages 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, „Improving the efficiency and reliability of digital time-stamping,“
In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
[5] S. Haber, W.S. Stornetta, „Secure names for bit-strings,“ In Proceedings of the 4th ACM Conference
on Computer and Communications Security, pages 28-35, April 1997.
[6] A. Back, „Hashcash – a denial of service counter-measure,“
http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, „Protocols for public key cryptosystems,“ In Proc. 1980 Symposium on Security and
Privacy, IEEE Computer Society, pages 122-133, April 1980.
[8] W. Feller, „An introduction to probability theory and its applications,“ 1957.