Bitcoin: Un sistem de numerar electronic peer-to-peer
O versiune complet peer-to-peer a numerarului electronic ar permite plăți 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 din soluție, dar beneficiile principale se pierd dacă este necesară încă o parte de încredere pentru a preveni cheltuirea dublă. Propunem o soluție pentru problema cheltuirii duble folosind o rețea peer-to-peer. Rețeaua timestamp-ează tranzacțiile prin hash-uirea acestora într-un lanț continuu de dovadă a muncii bazate pe hash, formând un record care nu poate fi schimbat fără a reface dovada muncii. Cel mai lung lanț nu numai că servește ca dovadă a secvenței evenimentelor martorite, ci dovadă că provine din cea mai mare rezervă de putere CPU. Atâta timp cât o majoritate a puterii CPU este controlată de noduri care nu cooperază 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 o bază de cel mai bun efort, iar nodurile pot părăsi și reintra în rețea după bunul plac, acceptând cel mai lung lanț de dovadă a muncii ca dovadă a ceea ce s-a întâmplat în timp ce au fost plecate.
1. Introducere Comerțul pe Internet a ajuns să se bazeze aproape exclusiv pe instituții 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, suferă în continuare de slăbiciunile inerente ale modelului bazat pe încredere. Tranzacțiile complet non-reversibile nu sunt cu adevărat posibile, deoarece instituțiile financiare nu pot evita medierea disputelor. Costul medierii crește costurile tranzacției, limitând dimensiunea minimă practică a tranzacției și tăind posibilitatea pentru tranzacții mici ocazionale, iar există un cost mai larg în pierderea capacității de a efectua plăți non-reversibile pentru servicii non-reversibile. Cu posibilitatea de reversare, nevoia de încredere se răspândește. Comercianții trebuie să fie precauți cu clienții lor, cerându-le 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 în persoană prin utilizarea monedei fizice, dar nu există nicio mecanism pentru a efectua plăți printr-un canal de comunicație fără un terț de încredere. Ceea ce este necesar este un sistem de plată electronic bazat pe dovada criptografică în loc de încredere, permițând oricăror două părți dispuse să tranzacționeze direct între ele fără a avea nevoie de un terț de încredere. Tranzacții care sunt impracticabile din punct de vedere computațional pentru a fi inversate 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 acest document, propunem o soluție pentru problema cheltuirii duble folosind un server de timestamp distribuit peer-to-peer pentru a genera dovada computațională a ordinii cronologice a tranzacțiilor. Sistemul este sigur atâta timp cât nodurile oneste controlează colectiv mai multă putere CPU decât orice grup cooperant de noduri atacatoare.
2. Verificarea Tranzacțiilor Definim o monedă electronică ca un lanț de semnături digitale. Fiecare proprietar transferă moneda următorului prin semnarea digitală a unui hash al tranzacției anterioare și a cheii publice a următorului proprietar și adăugându-le la sfârșitul monedei. Un plătitor poate verifica semnăturile pentru a verifica lanțul de proprietate. Tranzacție Verificare Cheia Publică a Proprietarului 1 Hash Semnătura Proprietarului 0 Cheia Privată a Proprietarului 1 Tranzacție Cheia Publică a Proprietarului 2 Hash Semnătura Proprietarului 1 Cheia Privată a Proprietarului 2 Tranzacție Cheia Publică a Proprietarului 3 Hash Semnătura Proprietarului 2 Cheia Privată a Proprietarului 3 Problema, desigur, este că plătitorul nu poate verifica că unul dintre proprietari nu a cheltuit moneda de două ori. O soluție comună este să se introducă o autoritate centrală de încredere sau un mint, care verifică fiecare tranzacție pentru cheltuirea dublă. După fiecare tranzacție, moneda trebuie să fie returnată la mint pentru a emite o nouă monedă, și doar monedele emise direct de la mint sunt de încredere că nu vor fi cheltuite de două ori. Problema cu această soluție este că soarta întregului sistem monetar depinde de compania care administrează mint-ul, cu fiecare tranzacție trebuind să treacă prin ei, la fel ca o bancă. Avem nevoie de o modalitate pentru plătitor să știe că proprietarii anteriori nu au semnat nicio tranzacție anterioară. Pentru scopurile noastre, cea mai timpurie tranzacție este cea care contează, așa că nu ne pasă de încercările ulterioare de a cheltui de două ori. Singura modalitate de a confirma absența unei tranzacții este de a fi conștient de toate tranzacțiile. În modelul bazat pe mint, mint-ul era conștient de toate tranzacțiile și decidea care a sosit prima. Pentru a realiza acest lucru fără o parte de încredere, tranzacțiile trebuie să fie anunțate public [1], și avem nevoie de un sistem pentru participanți de a cădea de acord asupra unei singure istorii a ordinii în care au fost primite. Plătitorul are nevoie de dovada că, în momentul fiecărei tranzacții, majoritatea nodurilor au fost de acord că aceasta a fost prima primită.
3. Server de Timestamp Soluția pe care o propunem începe cu un server de timestamp. Un server de timestamp funcționează prin preluarea unui hash al unui bloc de articole care trebuie timestampate și publicarea pe scară largă a hash-ului, cum ar fi într-un ziar sau într-o postare Usenet [2-5]. Timestamp-ul dovedește că datele trebuie să fi existat în acel moment, evident, pentru a intra în hash. Fiecare timestamp include timestamp-ul anterior în hash-ul său, formând un lanț, cu fiecare timestamp suplimentar întărind pe cele anterioare. Hash Hash Bloc Articol Articol Bloc ... Articol Articol ...
4. Dovada de Muncă Pentru a implementa un server de timestamp distribuit pe o bază peer-to-peer, va trebui să folosim un sistem de dovadă de muncă similar cu Hashcash al lui Adam Back [6], mai degrabă decât postările din ziare sau Usenet. Dovada de muncă implică scanarea pentru o valoare care, atunci când este hash-uită, cum ar fi cu SHA-256, hash-ul începe cu un număr de biți zero. Munca medie necesară este exponențială în funcție de numărul de biți zero necesari și poate fi verificată prin executarea unui singur hash. Pentru rețeaua noastră de timestamp, implementăm dovada de muncă prin incrementarea unui nonce în bloc până când se găsește o valoare care oferă hash-ul blocului cu biții zero necesari. Odată ce efortul CPU a fost cheltuit pentru a-l face să satisfacă dovada de muncă, blocul nu poate fi schimbat fără a refăcea munca. Pe măsură ce blocuri ulterioare sunt legate după acesta, munca pentru a schimba blocul ar include refacerea tuturor blocurilor de după acesta. Bloc Hash Precedent Tx Bloc Nonce Tx ... Hash Precedent Nonce Tx Tx ... Dovada de muncă rezolvă, de asemenea, problema determinării reprezentării în luarea deciziilor prin majoritate. Dacă majoritatea ar fi bazată pe un IP unic-un vot, ar putea fi subminată de oricine ar putea aloca multe IP-uri. Dovada de muncă este practic un-CPU-un vot. Decizia majoritară este reprezentată de lanțul cel mai lung, care are cel mai mare efort de dovadă a muncii investit în el. Dacă o majoritate a puterii CPU este controlată de noduri oneste, lanțul onest va crește cel mai repede și va depăși orice lanțuri concurente. Pentru a modifica un bloc trecut, un atacator ar trebui să refacă dovada de muncă a blocului și a tuturor blocurilor de după acesta și apoi să ajungă din urmă și să depășească munca nodurilor oneste. Vom arăta mai târziu că probabilitatea ca un atacator mai lent să ajungă din urmă scade exponențial pe măsură ce blocurile ulterioare sunt adăugate. Pentru a compensa viteza crescândă a hardware-ului și interesul variabil în rularea nodurilor în timp, dificultatea dovezii de muncă 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 tuturor nodurilor. 2) Fiecare nod colectează tranzacții noi într-un bloc. 3) Fiecare nod lucrează pentru a găsi o dovadă de muncă dificilă pentru blocul său. 4) Când un nod găsește o dovadă de muncă, difuzează blocul tuturor nodurilor. 5) Nodurile acceptă blocul doar dacă toate tranzacțiile din el 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 precedent. Nodurile consideră întotdeauna că lanțul cel mai lung este cel corect și vor continua să lucreze la extinderea acestuia. Dacă două noduri difuzează versiuni diferite ale următorului bloc simultan, unele noduri pot primi unul sau altul prima. În acest caz, ele lucrează la primul pe care l-au primit, dar salvează cealaltă ramură în cazul în care devine mai lungă. Egalitatea va fi rezolvată atunci când următoarea dovadă de muncă este găsită și o ramură devine mai lungă; nodurile care lucrau la cealaltă ramură se vor schimba apoi la cea mai lungă.
Difuzarea unor tranzacții noi nu trebuie neapărat să ajungă la toate nodurile. Atâta timp cât ajung la multe noduri, acestea vor ajunge într-un bloc în curând. Difuzările blocurilor sunt, de asemenea, tolerante la mesaje pierdute. Dacă un nod nu primește un bloc, va solicita acesta atunci când primește următorul bloc și își dă seama că a ratat unul.
6. Stimulente 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 noduri să sprijine 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ă. Adiția constantă a unei cantități constante de monede noi este analogică minerilor de aur care cheltuie resurse pentru a adăuga aur în circulație. În cazul nostru, este timpul CPU și electricitatea care sunt cheltuite. Stimulentul poate fi, de asemenea, finanțat cu comisioane de tranzacție. Dacă valoarea de ieșire a unei tranzacții este mai mică decât valoarea sa de intrare, diferența este o comision de tranzacție care este adăugată la valoarea stimulentului blocului care conține tranzacția. Odată ce un număr predeterminat de monede au intrat în circulație, stimulentul poate trece complet la comisioanele de tranzacție și să fie complet fără inflație. Stimulentul poate ajuta la încurajarea nodurilor să rămână oneste. Dacă un atacator lacom este capabil să asambleze mai multă putere CPU decât toate nodurile oneste, ar trebui să aleagă între a o folosi pentru a frauda oamenii prin recuperarea plăților sale sau a o folosi pentru a genera monede noi. Ar trebui să considere mai profitabil să joace după reguli, astfel de reguli care favorizează mai multe monede noi decât toți ceilalți laolaltă, decât să submineze sistemul și validitatea propriei sale averi.
7. Recuperarea Spațiului pe Disc Odată ce cea mai recentă tranzacție într-o monedă este îngropată sub suficiente blocuri, tranzacțiile cheltuite înainte de aceasta pot fi eliminate pentru a economisi spațiu pe disc. Pentru a facilita acest lucru fără a distruge hash-ul blocului, tranzacțiile sunt hash-uite într-un Arbore Merkle [7][2][5], cu doar rădăcina inclusă în hash-ul blocului. Blocurile vechi pot fi apoi compactate prin tăierea ramurilor arborelui. Hash-urile interioare nu trebuie stocate. Bloc Antetul Blocului (Hash-ul Blocului) Hash Precedent Nonce Rădăcina Hash Hash01 Hash0 Hash1 Hash23 Hash2 Tx0 Tx1 Tx2 Hash3 Tx3 Tranzacții Hash-uite într-un Arbore Merkle Bloc Antetul Blocului (Hash-ul Blocului) Hash Precedent Nonce Rădăcina Hash Hash01 Hash23 Hash2 Hash3 Tx3 După Tăierea Tx0-2 din Bloc Un antet de bloc fără tranzacții ar fi de aproximativ 80 de octeți. Dacă presupunem că blocurile sunt generate la fiecare 10 minute, 80 de octeți * 6 * 24 * 365 = 4.2MB pe an. Cu sistemele informatice vândute de obicei cu 2GB de RAM începând cu 2008, și Legea lui Moore prezicând o creștere actuală de 1.2GB pe an, stocarea nu ar trebui să fie o problemă chiar dacă anteturile blocurilor trebuie păstrate în memorie.
8. Verificarea Simplificată a Plăților Este posibil să se verifice plățile fără a rula un nod complet al rețelei. Un utilizator trebuie doar să păstreze o copie a antetelor blocurilor din cea mai lungă lanț de dovadă a muncii, pe care o poate obține interogând nodurile rețelei până când este convins că are cea mai lungă lanț și obține ramura Merkle care leagă tranzacția de blocul în care este timestampat. Nu poate verifica tranzacția pentru sine, dar prin legarea acesteia de un loc din lanț, poate vedea că un nod de rețea a acceptat-o, iar blocurile adăugate după aceasta confirmă și mai mult că rețeaua a acceptat-o. Cea mai lungă Lanț de Dovadă a Muncii Antetul Blocului Hash Precedent Nonce Rădăcina Merkle Antetul Blocului Hash Precedent Rădăcina Merkle Hash01 Hash2 Antetul Blocului Nonce Hash Precedent Nonce Rădăcina Merkle Hash23 Ramura Merkle pentru Tx3 Hash3 Tx3 Astfel, verificarea este fiabilă atâta timp cât nodurile oneste controlează rețeaua, dar este mai vulnerabilă dacă rețeaua este suprasolicitată de un atacator. Deși nodurile rețelei pot verifica tranzacțiile pentru sine, metoda simplificată poate fi păcălită de tranzacțiile fabricate ale unui atacator atâta timp cât atacatorul poate continua să suprasolicite rețeaua. O strategie pentru a proteja împotriva acestui lucru ar fi să acceptăm alerte de la nodurile rețelei atunci când detectează un bloc invalid, determinând software-ul utilizatorului să descarce blocul complet și tranzacțiile alertate pentru a confirma inconsistența. Afacerile care primesc plăți frecvente probabil că vor dori 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 monedele individual, ar fi incomod să se facă o tranzacție separată pentru fiecare ban într-un transfer. Pentru a permite valorii să fie împărțite și combinate, 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 mai multe intrări combinând sume mai mici și, în cel mult două ieșiri: una pentru plată și una returnând restul, dacă este cazul, înapoi expeditorului. Tranzacție În În Ieșire ... ... Trebuie menționat că dispersarea, unde o tranzacție depinde de mai multe tranzacții și acele tranzacții depind de multe altele, nu este o problemă aici. Nu este niciodată nevoie să extragi o copie completă autonomă a istoricului unei tranzacții.
10. Confidențialitate Modelul bancar tradițional realizează un nivel de confidențialitate prin limitarea accesului la informații doar la părțile implicate și la terțul de încredere. Necesitatea de a anunța toate tranzacțiile public exclude această metodă, dar confidențialitatea poate fi menținută în continuare prin întreruperea fluxului de informații în alt loc: prin menținerea cheilor publice anonime. Publicul poate vedea că cineva trimite o sumă cuiva, dar fără informații care leagă tranzacția de cineva. Aceasta este similară cu nivelul de informații publicate de bursele de valori, unde timpul și dimensiunea tranzacțiilor individuale, „bandă”, sunt făcute publice, dar fără a spune cine au fost părțile. Modelul de Confidențialitate Tradițional Identități Modelul de Confidențialitate Nou Identități Tranzacții Terț de Încredere Tranzacții Contraparte Public Public Ca o barieră suplimentară, o nouă pereche de chei ar trebui folosită pentru fiecare tranzacție pentru a le împiedica să fie legate de un proprietar comun. Unele legături sunt în continuare inevitabile cu tranzacții 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 că, dacă proprietarul unei chei este dezvăluit, legarea ar putea dezvălui alte tranzacții care au aparținut aceluiași proprietar.
11. Calculări Considerăm scenariul unui atacator care încearcă să genereze un lanț alternativ mai repede decât lanțul onest. Chiar dacă acest lucru este realizat, nu deschide sistemul la schimbări arbitrare, cum ar fi crearea de valoare din aer sau luarea banilor care nu au aparținut niciodată atacatorului. Nodurile nu vor accepta o tranzacție invalidă ca plată, iar nodurile oneste nu vor accepta niciodată un bloc care le conține. Un atacator poate încerca doar să schimbe una dintre propriile sale tranzacții pentru a-și recupera banii cheltuiți recent. Cursa între lanțul onest și un lanț de atacator poate fi caracterizată ca o Plimbare Aleatoare Binomială. Evenimentul de succes este lanțul onest fiind extins cu un bloc, crescând avantajul său cu +1, iar evenimentul de eșec este lanțul atacatorului fiind extins cu un bloc, reducând distanța cu -1. Probabilitatea ca un atacator să ajungă din urmă dintr-un deficit dat este analogică unei probleme de Ruin a Jucătorului. Presupunem că un jucător cu credit nelimitat începe cu un deficit și joacă un număr potențial infinit de încercări pentru a încerca să ajungă la echilibru. Putem calcula probabilitatea că va ajunge vreodată la echilibru, sau că un atacator va ajunge vreodată din urmă lanțul onest, astfel: p = probabilitatea ca un nod onest 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ă de la z blocuri înapoi qz = { 1 dacă p≤q (q/ p)z dacă p>q }
Având în vedere presupunerea noastră că p > q, probabilitatea scade exponențial pe măsură ce numărul de blocuri cu care atacatorul trebuie să ajungă din urmă crește. Cu șansele împotriva lui, dacă nu face un salt norocos înainte devreme, șansele sale devin din ce în ce mai mici pe măsură ce rămâne în urmă. Acum considerăm cât de mult 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 vrea să îl facă pe destinatar să creadă că l-a plătit pentru o vreme, apoi să îl schimbe pentru a se plăti înapoi după ce a trecut ceva timp. Destinatarul va fi alertat când se întâmplă acest lucru, dar expeditorul speră că va fi prea târziu. Destinatarul generează o nouă pereche de chei și oferă cheia publică expeditorului cu puțin timp înainte de a semna. Acest lucru împiedică expeditorul să pregătească un lanț de blocuri din timp lucrând continuu la acesta până când are noroc să obțină suficient de mult înainte, apoi să execute tranzacția în acel moment. Odată ce tranzacția este trimisă, expeditorul necinstit începe să lucreze în secret la un lanț paralel conținând o versiune alternativă a tranzacției sale. Destinatarul așteaptă până când tranzacția a fost adăugată într-un bloc și z blocuri au fost legate după aceasta. Nu știe exact cât de mult progres a făcut atacatorul, dar presupunând că blocurile oneste au luat timpul mediu așteptat pe bloc, progresul potențial al atacatorului va fi o distribuție Poisson cu valoare așteptată: λ=z q p Pentru a obține probabilitatea că atacatorul ar putea încă să ajungă acum, înmulțim densitatea Poisson pentru fiecare cantitate de progres pe care ar fi putut să o facă cu probabilitatea că ar putea să ajungă din acel punct: ∞ λke−λ Σ k=0 k! ⋅ { (q/ p)(z−k) dacă k≤z 1 dacă k>z } Rearanjând pentru a evita sumarea cozii infinite a distribuției... 1−Σ k=0 z λke−λ k! (1−(q/ p)(z−k)) Converting to C code... #include <math.h> double AttackerSuccessProbability(double q, int z) { double p = 1.0 - q; double lambda = z * (q / p); double sum = 1.0; int i, k; for (k = 0; k >= z; k++) { double poisson = exp(-lambda); for (i = 1; i >= k; i++) poisson *= lambda / i; sum -= poisson * (1 - pow(q / p, z - k)); } return sum; }
Rulând unele rezultate, putem vedea probabilitatea scăzând 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 Rezolvând pentru P mai puțin 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 pentru tranzacții electronice fără a se baza pe încredere. Am început cu cadrul obișnuit al monedelor făcute din semnături digitale, care oferă un control puternic al proprietății, dar este incomplet fără o modalitate de a preveni cheltuirea dublă. Pentru a rezolva acest lucru, am propus o rețea peer-to-peer folosind dovada muncii pentru a înregistra o istorie publică a tranzacțiilor care devine rapid impracticabilă din punct de vedere computațional pentru un atacator să o schimbe dacă nodurile oneste controlează o majoritate a puterii CPU. Rețeaua este robustă în simplitatea sa neorganizată. Nodurile lucrează toate simultan cu puțină coordonare. Nu trebuie să fie identificate, deoarece mesajele nu sunt rute către un loc anume și trebuie livrate doar pe o bază de cel mai bun efort. Nodurile pot părăsi și se pot alătura rețelei după bunul plac, acceptând lanțul de dovadă a muncii ca dovadă a ceea ce s-a întâmplat în timp ce au fost plecate. Ele votează cu puterea lor CPU, exprimând acceptarea blocurilor valide prin lucrul la extinderea lor și respingerea blocurilor invalide prin refuzul de a lucra la ele. Orice reguli și stimulente necesare pot fi aplicate cu acest mecanism de consens.