Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org
Rezumat: O versiune pur peer-to-peer a numerarului electronic ar permite plăților online să fie trimise direct de la o parte la alta, fără a trece printr-o instituție financiară. Semnăturile digitale oferă o parte a soluției, dar principalele beneficii se pierd dacă este încă necesară o terță parte de încredere pentru a preveni dublarea cheltuielilor. Vă propunem o soluție la problema dublei cheltuieli folosind o rețea peer-to-peer. Rețeaua amplifică tranzacțiile prin hashing-ul într-un lanț continuu de dovezi de lucru bazate pe hash, formând o înregistrare care nu poate fi modificată fără a reface dovada de lucru. Cel mai lung lanț nu servește doar ca dovadă a secvenței evenimentelor asistate, ci și ca dovadă că provine din cel mai mare bazin de putere CPU. Atâta timp cât majoritatea puterii CPU este controlată de noduri care nu cooperează pentru a ataca rețeaua, acestea vor genera cel mai lung lanț și vor depăși atacatorii. Rețeaua în sine necesită o structură minimă. Mesajele sunt difuzate pe baza celor mai bune eforturi, iar nodurile pot părăsi și reîntragi rețeaua după bunul plac, acceptând cel mai lung lanț de dovezi de lucru ca dovadă a ceea ce s-a întâmplat în timp ce nu erau.
1. Introducere
Comerțul pe Internet a ajuns să se bazeze aproape exclusiv pe instituțiile financiare care servesc ca terți de încredere pentru a procesa plățile electronice. Deși sistemul funcționează suficient de bine pentru majoritatea tranzacțiilor, acesta suferă în continuare de slăbiciunile inerente ale modelului bazat pe încredere. Tranzacțiile complet ireversibile nu sunt cu adevărat posibile, deoarece instituțiile financiare nu pot evita medierea litigiilor. Costul medierii crește costurile de tranzacție, limitând dimensiunea minimă practică a tranzacției și eliminând posibilitatea unor mici tranzacții ocazionale și există un cost mai larg în pierderea capacității de a efectua plăți ireversibile pentru serviciile ireversibile. Cu posibilitatea de inversare, nevoia de încredere se răspândește. Comercianții trebuie să fie atenți la clienții lor, frământându-i pentru mai multe informații decât ar avea nevoie altfel. Un anumit procent de fraudă este acceptat ca inevitabil. Aceste costuri și incertitudini de plată pot fi evitate personal prin utilizarea monedei fizice, dar nu există niciun mecanism pentru a efectua plăți printr-un canal de comunicații fără o parte de încredere.
Este necesar un sistem de plată electronic bazat pe dovezi criptografice în loc de încredere, care să permită oricăror două părți dispuse să tranzacționeze direct între ele, fără a fi nevoie de o terță parte de încredere. Tranzacțiile care nu pot fi inversate din punct de vedere computațional ar proteja vânzătorii de fraudă, iar mecanismele de escrow de rutină ar putea fi implementate cu ușurință pentru a proteja cumpărătorii. În această lucrare, propunem o soluție la problema cheltuirii duble folosind un server de marcaj temporal distribuit peer-to-peer pentru a genera dovezi computaționale ale ordinii cronologice a tranzacțiilor. Sistemul este sigur atâta timp cât nodurile cinstite controlează în mod colectiv mai multă putere CPU decât orice grup cooperant de noduri atacatoare.
2. Tranzacții
Definim o monedă electronică ca un lanț de semnături digitale. Fiecare proprietar transferă moneda la următorul semnând digital un hash al tranzacției anterioare și cheia publică a următorului proprietar și adăugându-le la sfârșitul monedei. Un beneficiar poate verifica semnăturile pentru a verifica lanțul de proprietate.
Problema este desigur că beneficiarul nu poate verifica dacă unul dintre proprietari nu a cheltuit dublu moneda. O soluție comună este introducerea unei autorități centrale de încredere, sau a unei monetări, care verifică fiecare tranzacție pentru dubla cheltuieli. După fiecare tranzacție, moneda trebuie returnată la monetărie pentru a emite o nouă monedă, iar numai monedele emise direct de la monetărie sunt de încredere să nu fie cheltuite dublu. Problema cu această soluție este că soarta întregului sistem monetar depinde de compania care conduce monetăria, fiecare tranzacție trebuind să treacă prin ele, la fel ca o bancă. Avem nevoie de o modalitate prin care beneficiarul plății să știe că proprietarii anteriori nu au semnat tranzacții anterioare. Pentru scopurile noastre, cea mai devreme tranzacție este cea care contează, așa că nu ne pasă de încercările ulterioare de a cheltui dublu. Singura modalitate de a confirma absența unei tranzacții este să fii la curent cu toate tranzacțiile. În modelul bazat pe monetărie, monetăria era la curent cu toate tranzacțiile și a decis care a sosit primul. Pentru a realiza acest lucru fără o parte de încredere, tranzacțiile trebuie anunțate public [1] și avem nevoie de un sistem pentru ca participanții să convină asupra unui istoric unic al ordinii în care au fost primite. Beneficiarul are nevoie de dovada că, la momentul fiecărei tranzacții, majoritatea nodurilor au fost de acord că este primul primit.
3. Server de marcaj de timp
Soluția pe care o propunem începe cu un server de marcaj temporal. Un server de marcaj de timp funcționează prin preluarea unui hash dintr-un bloc de articole pentru a fi marcat temporal și publicarea pe scară largă a hash-ului, cum ar fi într-un ziar sau într-o postare Usenet [2-5]. Marca temporală dovedește că datele trebuie să fi existat la momentul respectiv, evident, pentru a intra în hash. Fiecare marcaj de timp include marcajul de timp anterior în hash-ul său, formând un lanț, fiecare marca de timp suplimentară întărindu-i pe cele dinaintea sa.
4. Dovada de lucru
Pentru a implementa un server de marcaj temporal distribuit pe o bază peer-to-peer, va trebui să folosim un sistem de dovadă a muncii similar cu Hashcash al lui Adam Back [6], mai degrabă decât postările din ziare sau Usenet. Dovada de lucru implică scanarea pentru o valoare care, atunci când este indexată, cum ar fi SHA-256, hash-ul începe cu un număr de zero biți. Munca medie necesară este exponențială în numărul de biți zero necesari și poate fi verificată prin executarea unui singur hash.
Pentru rețeaua noastră de marcaj de timp, implementăm dovada de lucru prin incrementul unui nonce în bloc până când este găsită o valoare care oferă hash-ului blocului biții zero necesari. Odată ce efortul CPU a fost cheltuit pentru ca acesta să satisfacă dovezile de lucru, blocul nu poate fi schimbat fără a reface munca. Deoarece blocurile ulterioare sunt înlănțuite după el, munca de schimbare a blocului ar include refacerea tuturor blocurilor după el.
Proba de lucru rezolvă și problema determinării reprezentării în luarea deciziilor majoritare. Dacă majoritatea s-ar baza pe o adresă IP-un vot, aceasta ar putea fi subminată de oricine poate să aloce mai multe IP-uri. Dovada muncii este, în esență, o CPU-un vot. Decizia majoritară este reprezentată de cel mai lung lanț, care are cel mai mare efort proof-of-work investit în el. Dacă majoritatea puterii procesorului este controlată de noduri oneste, lanțul cinstit va crește cel mai rapid și va depăși orice lanțuri concurente. Pentru a modifica un bloc trecut, un atacator ar trebui să refacă dovada de lucru a blocului și a tuturor blocurilor de după acesta și apoi să ajungă din urmă și să depășească munca nodurilor cinstite. Vom arăta mai târziu că probabilitatea ca un atacator mai lent să ajungă din urmă scade exponențial pe măsură ce se adaugă blocurile ulterioare.
Pentru a compensa creșterea vitezei hardware și interesul variabil pentru rularea nodurilor de-a lungul timpului, dificultatea dovezii de lucru este determinată de o medie mobilă care vizează un număr mediu de blocuri pe oră. Dacă sunt generate prea repede, dificultatea crește.
5. Rețea
Pașii pentru a rula rețeaua sunt următorii:
1) Tranzacțiile noi sunt difuzate către toate nodurile.
2) Fiecare nod colectează noi tranzacții într-un bloc.
3) Fiecare nod lucrează la găsirea unei dovezi de lucru dificile pentru blocul său.
4) Când un nod găsește dovada de lucru, acesta transmite blocul către toate nodurile.
5) Nodurile acceptă blocul numai dacă toate tranzacțiile din acesta sunt valide și nu au fost deja cheltuite.
6) Nodurile își exprimă acceptarea blocului lucrând la crearea următorului bloc din lanț, folosind hash-ul blocului acceptat ca hash anterior.
Nodurile consideră întotdeauna că cel mai lung lanț este cel corect și vor continua să lucreze la extinderea acestuia. Dacă două noduri difuzează versiuni diferite ale blocului următor simultan, unele noduri pot primi una sau alta mai întâi. În acest caz, lucrează la prima pe care au primit-o, dar salvează cealaltă ramură în cazul în care devine mai lungă. Legatura se va rupe când se va găsi următoarea dovadă de muncă și o ramură devine mai lungă; nodurile care lucrau pe cealaltă ramură vor trece apoi la cea mai lungă.
Noile transmisii de tranzacții nu trebuie neapărat să ajungă la toate nodurile. Atâta timp cât ajung la multe noduri, vor intra într-un bloc în curând. Transmisiile blocate sunt, de asemenea, tolerante cu mesajele abandonate. Dacă un nod nu primește un bloc, îl va solicita atunci când primește următorul bloc și își dă seama că a ratat unul.
6. Stimulent
Prin convenție, prima tranzacție dintr-un bloc este o tranzacție specială care începe o nouă monedă deținută de creatorul blocului. Acest lucru adaugă un stimulent pentru nodurile să susțină rețeaua și oferă o modalitate de a distribui inițial monede în circulație, deoarece nu există o autoritate centrală care să le emită. Adăugarea constantă a unei cantități constante de monede noi este analogă cu minerilor de aur care cheltuiesc resurse pentru a adăuga aur în circulație. În cazul nostru, timpul CPU și energia electrică sunt cheltuite.
Stimulentul poate fi finanțat și cu taxe de tranzacție. Dacă valoarea de ieșire a unei tranzacții este mai mică decât valoarea de intrare, diferența este o taxă de tranzacție care se adaugă la valoarea de stimulare a blocului care conține tranzacția. Odată ce un număr predeterminat de monede a intrat în circulație, stimulentul poate trece în întregime la comisioane de tranzacție și poate fi complet lipsit de inflație.
Stimulentul poate ajuta la încurajarea nodurilor să rămână sincere. Dacă un atacator lacom este capabil să adune mai multă putere CPU decât toate nodurile cinstite, ar trebui să aleagă între a o folosi pentru a frauda oamenii, furându-i plățile înapoi sau să o folosească pentru a genera noi monede. Ar trebui să găsească mai profitabil să joace după reguli, astfel de reguli care îl favorizează cu mai multe monede noi decât toți ceilalți la un loc, decât să submineze sistemul și valabilitatea propriei sale bogății.
7. Recuperarea spațiului pe disc
Odată ce cea mai recentă tranzacție dintr-o monedă este îngropată sub suficiente blocuri, tranzacțiile cheltuite înainte de a putea fi aruncate pentru a economisi spațiu pe disc. Pentru a facilita acest lucru fără a sparge hash-ul blocului, tranzacțiile sunt hashing într-un Merkle Tree [7][2][5], cu doar rădăcina inclusă în hash-ul blocului. Blocurile vechi pot fi apoi compactate prin tăierea ramurilor copacului. Nu este necesar să se depoziteze hashurile din interior.
Un antet de bloc fără tranzacții ar avea aproximativ 80 de octeți. Dacă presupunem că blocurile sunt generate la fiecare 10 minute, 80 de octeți 6 24 * 365 = 4,2 MB pe an. Cu sistemele informatice care se vând de obicei cu 2 GB de RAM din 2008, iar Legea lui Moore prevede o creștere actuală de 1,2 GB pe an, stocarea nu ar trebui să fie o problemă, chiar dacă anteturile blocurilor trebuie păstrate în memorie.
8. Verificare simplificată a plății
Este posibil să verificați plățile fără a rula un nod de rețea complet. Un utilizator trebuie doar să păstreze o copie a antetelor de bloc ale celui mai lung lanț de dovadă a lucrului, pe care o poate obține interogând nodurile de rețea până când se convinge că are cel mai lung lanț și să obțină ramura Merkle care leagă tranzacția de bloc. este marcat de timp. Nu poate verifica tranzacția pentru el însuși, dar legând-o la un loc din lanț, poate vedea că un nod de rețea a acceptat-o și blocurile adăugate după ce confirmă în continuare că rețeaua a acceptat-o.
Ca atare, verificarea este fiabilă atâta timp cât noduri cinstite controlează rețeaua, dar este mai vulnerabilă dacă rețeaua este depășită de un atacator. În timp ce nodurile de rețea pot verifica tranzacțiile singure, metoda simplificată poate fi păcălită de tranzacțiile fabricate de un atacator atâta timp cât atacatorul poate continua să domine rețeaua. O strategie de protejare împotriva acestui lucru ar fi acceptarea alertelor de la nodurile rețelei atunci când detectează un bloc invalid, determinând software-ul utilizatorului să descarce blocul complet și să alerteze tranzacțiile pentru a confirma inconsecvența. Companiile care primesc plăți frecvente vor dori probabil să își ruleze propriile noduri pentru o securitate mai independentă și o verificare mai rapidă.
9. Combinarea și împărțirea valorii
Deși ar fi posibil să se gestioneze monede individual, ar fi greu să se facă o tranzacție separată pentru fiecare cent dintr-un transfer. Pentru a permite ca valoarea să fie împărțită și combinată, tranzacțiile conțin mai multe intrări și ieșiri. În mod normal, va exista fie o singură intrare dintr-o tranzacție anterioară mai mare, fie intrări multiple care combină sume mai mici și cel mult două ieșiri: una pentru plată și una care returnează schimbarea, dacă există, înapoi către expeditor.
Trebuie remarcat faptul că fan-out-ul, în care o tranzacție depinde de mai multe tranzacții, iar acele tranzacții depind de multe altele, nu este o problemă aici. Nu este niciodată necesar să extrageți o copie autonomă completă a istoricului unei tranzacții.
10. Confidențialitate
Modelul bancar tradițional atinge un nivel de confidențialitate prin limitarea accesului la informații la părțile implicate și la terțul de încredere. Necesitatea de a anunța public toate tranzacțiile exclude această metodă, dar confidențialitatea poate fi totuși menținută prin întreruperea fluxului de informații în alt loc: prin păstrarea cheilor publice anonime. Publicul poate vedea că cineva trimite o sumă altcuiva, dar fără informații care să lege tranzacția de nimeni. Acesta este similar cu nivelul de informații eliberat de bursele de valori, unde timpul și dimensiunea tranzacțiilor individuale, „banda”, este făcută publică, dar fără a se spune cine au fost părțile.
Ca firewall suplimentar, o nouă pereche de chei ar trebui să fie utilizată pentru fiecare tranzacție pentru a le împiedica să fie conectate la un proprietar comun. Unele legături sunt încă inevitabile în cazul tranzacțiilor cu mai multe intrări, care dezvăluie în mod necesar că intrările lor au fost deținute de același proprietar. Riscul este ca dacă proprietarul unei chei este dezvăluit, conectarea ar putea dezvălui alte tranzacții care au aparținut aceluiași proprietar.
11. Calcule
Luăm în considerare scenariul unui atacator care încearcă să genereze un lanț alternativ mai rapid decât lanțul cinstit. Chiar dacă acest lucru este realizat, sistemul nu deschide sistemul la schimbări arbitrare, cum ar fi crearea de valoare din aer sau luarea de bani care nu au aparținut niciodată atacatorului. Nodurile nu vor accepta o tranzacție nevalidă ca plată, iar nodurile cinstite nu vor accepta niciodată un bloc care le conține. Un atacator poate încerca doar să schimbe una dintre propriile tranzacții pentru a-și lua înapoi banii pe care i-a cheltuit recent. Cursa dintre lanțul cinstit și lanțul atacatorului poate fi caracterizată ca o plimbare aleatorie binomială. Evenimentul de succes este lanțul cinstit care este extins cu un bloc, crescându-și avansul cu +1, iar evenimentul de eșec este lanțul atacatorului extins cu un bloc, reducând decalajul cu -1.
Probabilitatea ca un atacator să ajungă din urmă dintr-un anumit deficit este analogă cu o problemă Ruina jucătorului. Să presupunem că un jucător de noroc cu credit nelimitat începe de la un deficit și joacă potențial un număr infinit de încercări pentru a încerca să atingă pragul de rentabilitate. Putem calcula probabilitatea ca el să ajungă vreodată la pragul de rentabilitate sau ca un atacator să ajungă vreodată din urmă cu lanțul onest, după cum urmează [8]:
p = probabilitatea ca un nod sincer să găsească următorul bloc
q = probabilitatea ca atacatorul să găsească următorul bloc
qz = probabilitatea ca atacatorul să ajungă vreodată din urmă din z blocuri în spate
qz= { 1 dacă p≤q
(q/ p)^z dacă p>q}
Având în vedere ipoteza noastră că p > q, probabilitatea scade exponențial pe măsură ce crește numărul de blocuri pe care atacatorul trebuie să le recupereze. Cu șansele împotriva lui, dacă nu face un pas norocos înainte devreme, șansele lui devin extrem de mici pe măsură ce rămâne mai în urmă.
Acum luăm în considerare cât timp trebuie să aștepte destinatarul unei noi tranzacții înainte de a fi suficient de sigur că expeditorul nu poate schimba tranzacția. Presupunem că expeditorul este un atacator care dorește să-l facă pe destinatar să creadă că l-a plătit pentru o perioadă, apoi îl schimbă pentru a-și plăti înapoi după ce a trecut ceva timp. Receptorul va fi avertizat când se întâmplă acest lucru, dar expeditorul speră că va fi prea târziu.
Destinatorul generează o nouă pereche de chei și dă cheia publică expeditorului cu puțin timp înainte de a semna. Acest lucru îl împiedică pe expeditor să pregătească din timp un lanț de blocuri lucrând la el în mod continuu până când are norocul să ajungă suficient de departe, apoi executând tranzacția în acel moment. Odată ce tranzacția este trimisă, expeditorul necinstit începe să lucreze în secret pe un lanț paralel care conține o versiune alternativă a tranzacției sale.
Destinatarul așteaptă până când tranzacția a fost adăugată la un bloc și blocurile z au fost legate după acesta. El nu știe cât de exact a progresat atacatorul, dar presupunând că blocurile cinstite au luat timpul mediu așteptat per bloc, progresul potențial al atacatorului va fi o distribuție Poisson cu valoarea așteptată:
Se convertesc în cod C...
Rulând unele rezultate, putem vedea că probabilitatea scade exponențial cu z.
q=0,1
z=0 P=1,0000000
z=1 P=0,2045873
z=2 P=0,0509779
z=3 P=0,0131722
z=4 P=0,0034552
z=5 P=0,0009137
z=6 P=0,0002428
z=7 P=0,0000647
z=8 P=0,0000173
z=9 P=0,0000046
z=10 P=0,0000012
q=0,3
z=0 P=1,0000000
z=5 P=0,1773523
z=10 P=0,0416605
z=15 P=0,0101008
z=20 P=0,0024804
z=25 P=0,0006132
z=30 P=0,0001522
z=35 P=0,0000379
z=40 P=0,0000095
z=45 P=0,0000024
z=50 P=0,0000006
Rezolvarea pentru P mai mic de 0,1%...
P < 0,001
q=0,10 z=5
q=0,15 z=8
q=0,20 z=11
q=0,25 z=15
q=0,30 z=24
q=0,35 z=41
q=0,40 z=89
q=0,45 z=340
12. Concluzie
Am propus un sistem de tranzacții electronice fără a ne baza pe încredere. Am început cu cadrul obișnuit de monede realizate din semnături digitale, care oferă un control puternic asupra proprietății, dar este incomplet fără o modalitate de a preveni dublarea cheltuielilor. Pentru a rezolva acest lucru, am propus o rețea peer-to-peer care folosește dovada de lucru pentru a înregistra un istoric public al tranzacțiilor, care devine rapid impracticabil din punct de vedere computațional pentru ca un atacator să-l schimbe dacă nodurile cinstite controlează majoritatea puterii CPU. Rețeaua este robustă prin simplitatea sa nestructurată. Nodurile funcționează dintr-o dată cu puțină coordonare. Nu trebuie să fie identificate, deoarece mesajele nu sunt direcționate către niciun loc anume și trebuie să fie livrate doar pe baza celor mai bune eforturi. Nodurile pot părăsi și se pot alătura rețelei după bunul plac, acceptând lanțul de dovadă a lucrului ca dovadă a ceea ce s-a întâmplat în timp ce nu erau. Ei votează cu puterea CPU, exprimându-și acceptarea blocurilor valide lucrând la extinderea acestora și respingând blocurile invalide refuzând să lucreze la ele. Orice reguli și stimulente necesare pot fi aplicate cu acest mecanism de consens.
Referințe
[1] W. Dai, „b-money”, http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila și J.-J. Quisquater, „Proiectarea unui serviciu de marcare temporală sigură cu minim
cerințele de încredere”, în cel de-al 20-lea simpozion privind teoria informației din Benelux, mai 1999.
[3] S. Haber, W.S. Stornetta, „Cum să marcați un document digital”, în Journal of Cryptology, vol. 3, nr.
2, paginile 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, „Îmbunătățirea eficienței și fiabilității marcajului digital de timp”,
În Secvențe II: Metode în Comunicare, Securitate și Informatică, paginile 329-334, 1993.
[5] S. Haber, W.S. Stornetta, „Nume sigure pentru șirurile de biți”, în lucrările celei de-a patra conferințe ACM
privind securitatea computerelor și comunicațiilor, paginile 28-35, aprilie 1997.
[6] A. Înapoi, „Hashcash – o contra-măsură de refuzare a serviciului”,
http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, „Protocoale pentru criptosistemele cu cheie publică”, În Proc. 1980 Simpozion de securitate și
Confidențialitate, IEEE Computer Society, paginile 122-133, aprilie 1980.
[8] W. Feller, „An introduction to probability theory and its applications”, 1957.
