Bitcoin: Peer-to-peer elektronski keš sistem
Satoši Nakamoto
satoshin@gmx.com
www.bitcoin.org
Apstrakt
Isključivo peer-to-peer verzija elektronskog keša omogućila bi da se uplate putem interneta šalju direktno od jedne strane ka drugoj, bez posredstva finansijskih institucija. Digitalni potpisi su deo rešenja, ali glavni benefiti se gube ako je i dalje potreban pouzdani treći subjekt kako bi sprečio dvostruko trošenje. Predlažemo rešenje problema dvostrukog trošenja putem peer-to-peer mreže. Mreža vremenski obeležava transakcije tako što ih hešira u neprekidni lanac dokaza o radu (proof-of-work), što formira zapis koji se ne može menjati bez ponavljanja dokaza o radu. Najduži lanac ne samo da dokazuje redosled događaja već i da dolazi od najveće grupe CPU snage. Dokle god većina CPU snage pripada čorim čvorovima koji ne pokušavaju napad, oni će generisati najduži lanac i nadmašiti napadače. Mreža zahteva minimalnu strukturu. Poruke se šalju po principu „najboljeg truda“, a čvorovi mogu da izlaze i ulaze u mrežu po volji, prihvatajući najduži lanac kao dokaz o onome što se desilo dok su bili odsutni.
1. Uvod
Trgovina na internetu danas se gotovo u potpunosti oslanja na finansijske institucije kao pouzdane treće strane koje procesuiraju elektronske uplate. Iako sistem funkcioniše dovoljno dobro za većinu transakcija, pati od osnovnih slabosti modela zasnovanog na poverenju. Potpuno nepovratne transakcije nisu moguće, jer finansijske institucije moraju da posreduju u slučajevima spora. Trošak posredovanja povećava troškove transakcije, što ograničava minimalni iznos praktične transakcije i isključuje mogućnost malih, svakodnevnih plaćanja. Tu je i širi trošak u gubitku mogućnosti nepovratnih plaćanja za nepovratne usluge. Kada postoji mogućnost poništavanja, potreba za poverenjem se širi. Trgovci moraju da budu oprezni sa kupcima, traže im više informacija nego što bi inače bilo potrebno. Određeni procenat prevara se prihvata kao neizbežan. Sve ove troškove i neizvesnosti plaćanja može se izbeći lično korišćenjem fizičkog novca, ali ne postoji mehanizam za plaćanje preko komunikacionog kanala bez poverljive treće strane.
Potrebno je elektronsko sredstvo plaćanja zasnovano na kriptografskom dokazu, a ne na poverenju, koje omogućava bilo koje dve strane da trguju direktno, bez potrebe za pouzdanom trećom stranom. Transakcije koje je računarski neizvodljivo poništiti zaštitile bi prodavce od prevare, dok bi mehanizmi depozita mogli čak i dalje da štite kupce. U ovom radu predlažemo rešenje problema dvostrukog trošenja koristeći peer-to-peer distribuirani server za vremensko obeležavanje, kako bismo generisali računarski dokaz o hronološkom redosledu transakcija. Sistem je siguran sve dok iskreni čvorovi kolektivno kontrolišu više CPU snage nego bilo koja koordinisana grupa napadača.
2. Transakcije
Elektronski novčić definišemo kao lanac digitalnih potpisa. Svaki vlasnik prenosi novčić sledećem vlasniku tako što digitalno potpiše heš prethodne transakcije i javni ključ sledećeg vlasnika, a zatim to doda na kraj novčića. Primalac može da proveri potpise i time proveri lanac vlasništva.
Problem je što primalac ne može da proveri da neki prethodni vlasnik nije dvaput potrošio isti novčić. Uobičajeno rešenje je da se uvede pouzdana centralna institucija (menjačnica) koja proverava svaku transakciju radi dvostrukog trošenja. Nakon svake transakcije, novčić mora da se vrati menjačnici kako bi se izdao novi. Samo novčići izdati direktno iz menjačnice mogu se smatrati validnim.
Problem s ovim rešenjem je što cela monetarna infrastruktura zavisi od te jedne institucije, i sve transakcije moraju proći kroz nju, kao u banci. Nama je potreban sistem u kome primalac može da zna da prethodni vlasnici nisu potpisali nijednu raniju transakciju. Najranija transakcija je ona koja se broji, kasnije pokušaje da se potroši isti novčić možemo ignorisati. Jedini način da potvrdimo da transakcija ne postoji jeste da znamo sve transakcije.
U modelu s menjačnicom, ona je znala sve transakcije i odlučivala koja je stigla prva. Da bismo to postigli bez poverljive strane, transakcije moraju biti javno objavljene, i potreban nam je sistem kojim će svi učesnici postići konsenzus o jedinstvenoj istoriji redosleda. Primalac mora da ima dokaz da su svi čvorovi u mreži prihvatili njegovu transakciju kao prvu.
3. Server za vremensko obeležavanje
Rešenje koje predlažemo počinje sa serverom za vremensko obeležavanje. On funkcioniše tako što uzima heš bloka stavki koje treba vremenski obeležiti i javno objavljuje taj heš (npr. u novinama ili na Usenetu). Ovaj heš dokazuje da su podaci morali postojati u to vreme da bi bili uključeni u heš. Svako vremensko obeležje uključuje i prethodno u svom hešu, čime se formira lanac, gde svako novo vremensko obeležje pojačava prethodna.
4. Dokaz o radu (Proof-of-Work)
Da bismo implementirali distribuirani server za vremensko obeležavanje u peer-to-peer mreži, koristićemo sistem dokaza o radu sličan Hashcash mehanizmu Adama Beka. Dokaz o radu se sastoji od traženja vrednosti koja, kada se hešira (npr. pomoću SHA-256), daje heš koji počinje sa određenim brojem nula. Potrebni rad raste eksponencijalno u zavisnosti od broja početnih nula, dok je validacija laka jer zahteva samo jedno heširanje.
U našem slučaju, dokaz o radu se implementira tako što se u bloku inkrementira vrednost (nonce) dok se ne pronađe ona koja daje heš s potrebnim brojem početnih nula. Kada se jednom uloži CPU trud da bi se pronašao validan blok, taj blok se ne može promeniti bez ponovnog rada. Kako se novi blokovi nadovezuju, menjanje bilo kog prethodnog bloka zahtevalo bi ponovno računanje i svih nakon njega.
Dokaz o radu takođe rešava problem odlučivanja o većini. Da je odlučivanje zasnovano na broju IP adresa, bilo bi podložno zloupotrebi. Umesto toga, svaka jedinica rada (CPU vreme) predstavlja jedan glas. Većinsko mišljenje je predstavljeno najdužim lancem, odnosno onim sa najviše uloženog rada. Ako većinu CPU snage poseduju pošteni čvorovi, njihov lanac će rasti najbrže i prestići sve konkurentske lance. Napadač bi morao da ponovo izračuna sve blokove i sustigne poštene čvorove, što postaje eksponencijalno teže kako se dodaju novi blokovi.
Kako bi se kompenzovalo za rastuću brzinu hardvera i fluktuacije u broju čvorova, težina dokaza o radu se dinamički podešava tako da cilja prosečan broj blokova po satu. Ako se blokovi generišu prebrzo, težina raste.
5. Mreža
Koraci u funkcionisanju mreže su sledeći:
- Nove transakcije se emituju svim čvorovima.
- Svaki čvor skuplja transakcije u blok.
- Svaki čvor radi na pronalaženju dokaza o radu za svoj blok.
- Kada čvor pronađe dokaz, emituje blok ostalim čvorovima.
- Čvorovi prihvataju blok samo ako su sve transakcije validne i ako nisu već potrošene.
- Čvorovi izražavaju prihvatanje bloka tako što rade na sledećem bloku u lancu, koristeći heš prihvaćenog bloka kao prethodni.
Čvorovi uvek smatraju da je najduži lanac validan i nastavljaju da ga produžuju. Ako dva čvora istovremeno pošalju različite verzije sledećeg bloka, neki čvorovi mogu primiti jednu verziju, neki drugu. U tom slučaju, svaki nastavlja s radom na lancu koji je prvi primio, ali zadržava i drugu verziju. Konflikt se rešava kada se pronađe sledeći dokaz o radu, čime jedan lanac postaje duži i svi čvorovi prelaze na njega.
Poruke o novim transakcijama ne moraju da stignu do svih čvorova. Dovoljno je da stignu do većine — pre ili kasnije naći će se u nekom bloku. Blokovi su tolerantni na gubitak poruka. Ako čvor propusti neki blok, tražiće ga kada uoči da je preskočen.
6. Podsticaj
Po konvenciji, prva transakcija u svakom bloku je posebna transakcija koja kreira novi novčić, čiji je vlasnik kreator bloka. Ovo dodaje podsticaj čvorovima da podržavaju mrežu i obezbeđuje način za početnu distribuciju novčića, budući da ne postoji centralna institucija koja bi ih izdavala.
Stalno dodavanje određene količine novih novčića podseća na rudarenje zlata, gde rudari troše resurse kako bi dodali zlato u opticaj. U našem slučaju, troše se CPU vreme i električna energija.
Podsticaj se takođe može dopuniti transakcijskim naknadama. Ako je vrednost izlaza transakcije manja od ulazne, razlika predstavlja naknadu koju dobija čvor koji je kreirao blok u kojem se ta transakcija nalazi.
Kada se unapred definisana količina novčića pusti u opticaj, sistem može preći na model gde se podsticaj zasniva isključivo na naknadama za transakcije, što čini sistem potpuno bez inflacije.
Podsticaj može podstaći čvorove da ostanu iskreni. Ako pohlepni napadač uspe da prikupi više CPU snage od svih poštenih čvorova zajedno, mora da bira između korišćenja te snage za prevaru (npr. poništavanje sopstvenih uplata) ili za generisanje novih novčića. Trebalo bi da zaključi da mu je isplativije da igra po pravilima — jer mu pravila omogućavaju da zaradi više novčića od svih drugih zajedno — nego da podriva sistem i ugrozi vrednost sopstvenog bogatstva.
7. Oslobađanje diska
Kada je najnovija transakcija nekog novčića zakopana dovoljno duboko pod narednim blokovima, prethodne (potrošene) transakcije mogu se odbaciti kako bi se uštedelo na prostoru na disku. Da bi se to omogućilo bez narušavanja integriteta heša bloka, transakcije se organizuju i heširaju u Merklovo stablo (Merkle Tree), pri čemu se u heš bloka uključuje samo koreni (root) heš stabla.
Stari blokovi se mogu kompresovati tako što se uklone pojedinačne grane stabla koje više nisu potrebne. Unutrašnji heševi (hash čvorovi) se ne moraju čuvati.
Zaglavlje bloka bez transakcija imalo bi oko 80 bajtova. Ako pretpostavimo da se blokovi generišu svakih 10 minuta, dobijamo: 80 bajtova × 6 blokova po satu × 24 sata × 365 dana = ~4,2 MB godišnje.
S obzirom da su računari 2008. godine obično imali 2 GB RAM-a, i da Murov zakon predviđa rast memorije od preko 1 GB godišnje, čuvanje samo zaglavlja blokova u memoriji ne bi trebalo da predstavlja problem ni dugoročno.
8. Pojednostavljena verifikacija plaćanja
Moguće je verifikovati transakcije bez pokretanja punog čvora (noda) u mreži. Korisnik treba da čuva samo zaglavlja blokova iz najdužeg lanca, koje može pribaviti upitom ka čvorovima dok ne bude siguran da poseduje najduži lanac. Zatim može dobiti Merklovu granu koja povezuje konkretnu transakciju sa blokom u kom se nalazi.
Iako korisnik ne može sam da verifikuje celu transakciju, povezivanjem transakcije s poznatom pozicijom u lancu može videti da je neki mrežni čvor prihvatio transakciju, a dodatni blokovi nadovezani posle nje potvrđuju da je mreža takođe prihvata.
Ovakva verifikacija je pouzdana sve dok pošteni čvorovi kontrolišu mrežu. Međutim, više je ranjiva ukoliko mrežu preplavi napadač. Dok puni čvorovi mogu samostalno proveriti validnost transakcije, pojednostavljeni klijenti mogu biti prevareni falsifikovanom transakcijom ako napadač ima dovoljno snage da nadmaši mrežu.
Jedna strategija zaštite jeste da softver klijenta prihvata upozorenja od mrežnih čvorova kada oni detektuju nevalidan blok, što bi moglo podstaći korisnikov softver da preuzme ceo blok i proveri ga. Poslovni korisnici koji primaju česta plaćanja verovatno će želeti da pokreću vlastite čvorove zbog veće sigurnosti i brže verifikacije.
9. Kombinovanje i deljenje vrednosti
Iako bi bilo moguće upravljati svakim novčićem pojedinačno, to bi bilo nepraktično — bilo bi potrebno napraviti posebnu transakciju za svaki cent u jednoj uplati. Da bi se omogućilo kombinovanje i deljenje vrednosti, transakcije sadrže više ulaza i izlaza.
Uobičajeno je da postoji ili jedan ulaz iz neke veće prethodne transakcije, ili više ulaza koji kombinuju manje iznose, kao i najviše dva izlaza: jedan koji ide primalcu, i jedan koji vraća ostatak (kusur) pošiljaocu.
Važno je napomenuti da „grananje“ (engl. fan-out), gde transakcija zavisi od više prethodnih, koje same zavise od još više, nije problem. Nema potrebe za izdvajanjem celokupne nezavisne istorije transakcije, jer se verifikacija vrši putem kriptografskih heševa i Merklovih stabala.
10. Privatnost
Tradicionalni bankarski sistem postiže određeni nivo privatnosti ograničavanjem pristupa informacijama — samo strane u transakciji i pouzdana treća strana znaju detalje. U Bitcoin mreži, zbog javne objave svih transakcija, ovakav pristup privatnosti nije moguć.
Međutim, privatnost se može očuvati na drugom mestu: tako što se javni ključevi ne povezuju sa identitetom korisnika. Javnost može videti da neko šalje određeni iznos nekom drugom, ali bez povezivanja tih adresa sa konkretnim osobama. Ovo je slično načinu na koji berze objavljuju podatke o trgovanju — vreme i veličina svake trgovine su javni, ali ne i identiteti učesnika.
Kao dodatnu zaštitu, trebalo bi koristiti novi par ključeva za svaku transakciju, kako se one ne bi povezivale sa zajedničkim vlasnikom. Ipak, neka povezanost je neizbežna kod transakcija sa više ulaza, jer one otkrivaju da su svi ulazi u vlasništvu iste osobe. Rizik je da ako se identitet poveže sa jednim ključem, moguće je povezati i ostale transakcije istog korisnika.
11. Proračuni
Razmotrimo situaciju u kojoj napadač pokušava da generiše alternativni lanac brže od poštenog lanca. Čak i ako uspe, to ne znači da može praviti proizvoljne izmene, poput stvaranja novih sredstava ili krađe novca koji mu ne pripada. Čvorovi nikada neće prihvatiti nevažeću transakciju kao isplatu, niti će pošteni čvorovi prihvatiti blok koji je sadrži.
Napadač može pokušati samo da preokrene neku svoju nedavnu transakciju kako bi sebi vratio novac nakon što je već nešto kupio. Trka između poštenog lanca i napadačevog lanca može se posmatrati kao binomna slučajna šetnja. Uspešan ishod je kada pošteni lanac dobije novi blok (+1), a neuspešan kada napadačev lanac dobije blok (−1).
Verovatnoća da napadač sustigne pošteni lanac iz određenog zaostatka z slična je problemu „bankrota kockara“. Ako kockar s neograničenim kreditom počne s gubitkom i ima beskonačno mnogo pokušaja da se vrati na nulu, možemo izračunati verovatnoću da se to desi:
- p = verovatnoća da pošteni čvor pronađe sledeći blok
- q = verovatnoća da napadač pronađe sledeći blok
- q^z = verovatnoća da napadač sustigne poštene čvorove iz zaostatka z blokova
Ako je p > q, verovatnoća uspeha napadača opada eksponencijalno s brojem blokova koje mora da sustigne.
Takođe možemo izračunati koliki broj potvrda (broj blokova z) primalac treba da sačeka da bi bio dovoljno siguran da napadač ne može da poništi transakciju. Pretpostavimo da napadač počne praviti paralelni lanac čim pošalje transakciju. Primalac čeka dok transakcija ne bude uključena u blok, pa još z blokova nakon toga.
Što je z veće, to je manja verovatnoća da napadač stigne i pretekne pošteni lanac. Matematički model uključuje Poasonovu raspodelu kako bi se procenila potencijalna prednost napadača, ali rezultat uvek pokazuje da se sigurnost transakcije eksponencijalno povećava sa svakom dodatnom potvrdom.
12. Zaključak
Predložili smo sistem za elektronske transakcije koji ne zavisi od poverenja. Počeli smo sa standardnim modelom novčića zasnovanih na digitalnim potpisima, koji omogućavaju snažnu kontrolu vlasništva, ali sam po sebi ne rešava problem dvostrukog trošenja.
Da bismo ga rešili, predložili smo peer-to-peer mrežu koja koristi dokaz o radu kako bi zabeležila javnu istoriju transakcija, čiju bi izmene postale računarski neizvodljive ako pošteni čvorovi poseduju većinu CPU snage.
Mreža je robusna u svojoj jednostavnoj i nestruktuiranoj formi. Čvorovi rade paralelno s minimalnom koordinacijom. Ne moraju biti identifikovani, jer poruke nisu usmerene ka određenim mestima i dovoljno je da se prenose po principu „najboljeg truda“.
Čvorovi mogu slobodno da napuste i ponovo se priključe mreži, prihvatajući lanac dokaza o radu kao dokaz o onome što se desilo dok su bili odsutni. Glasaju svojom CPU snagom, izražavajući prihvatanje važećih blokova tako što nastavljaju da ih produžuju, a odbacujući nevažeće blokove tako što ih ignorišu.
Bilo koja pravila i podsticaji koji su potrebni za funkcionisanje sistema mogu se sprovoditi pomoću ovog mehanizma 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,“ Journal of Cryptology, vol. 3, no. 2, pp. 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, pp. 329–334, 1993.
[5] S. Haber, W.S. Stornetta, „Secure names for bit-strings,“ Proceedings of the 4th ACM Conference on Computer and Communications Security, pp. 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,“ Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pp. 122–133, April 1980.
[8] W. Feller, „An introduction to probability theory and its applications,“ 1957.