Bitcoin: sistema di cassa elettronico peer-to-peer

Astratto. Una versione puramente peer-to-peer della moneta elettronica consentirà di inviare pagamenti online direttamente da una parte all’altra, bypassando l’istituto finanziario. Le firme digitali forniscono parte della soluzione, ma i vantaggi principali vengono persi se è ancora necessaria una terza parte fidata per evitare la doppia spesa. Proponiamo una soluzione al problema della doppia spesa utilizzando una rete peer-to-peer. La rete contrassegna le transazioni eseguendo l'hashing in una catena continua di prove di lavoro basate su hash, creando un record che non può essere modificato senza rieseguire la prova di lavoro. La catena più lunga serve non solo come prova della sequenza degli eventi osservati, ma anche come prova che proviene dalla più grande potenza del processore. Finché la maggior parte della potenza della CPU è controllata da nodi che non sono coinvolti nell’attacco alla rete, genereranno la catena più lunga e supereranno gli aggressori. La rete stessa richiede una struttura minima. I messaggi vengono trasmessi nel miglior modo possibile e i nodi possono lasciare e ricongiungersi alla rete a piacimento, prendendo la catena di prova di lavoro più lunga come prova di ciò che è accaduto mentre erano lontani.

Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org

1. Introduzione

Il commercio online è arrivato a fare affidamento quasi esclusivamente su istituti finanziari che agiscono come terze parti fidate per elaborare i pagamenti elettronici. Sebbene il sistema funzioni abbastanza bene per la maggior parte delle transazioni, presenta ancora gli svantaggi inerenti a un modello basato sulla fiducia. In realtà, transazioni completamente irreversibili non sono possibili perché gli istituti finanziari non possono evitare di mediare le controversie. Il costo di intermediazione aumenta i costi di transazione limitando la dimensione minima pratica di una transazione ed eliminando la possibilità di piccole transazioni casuali, e i costi più ampi sono associati alla perdita della capacità di effettuare pagamenti irreversibili per servizi irreversibili. Con la possibilità di inversione, il bisogno di fiducia si diffonde. I commercianti devono diffidare dei propri clienti chiedendo loro più informazioni di quelle di cui potrebbero altrimenti aver bisogno. Una certa percentuale di frode è considerata inevitabile. Questi costi e l’incertezza dei pagamenti possono essere evitati di persona utilizzando la valuta fisica, ma non esiste alcun meccanismo per effettuare pagamenti tramite un canale di comunicazione senza una parte fidata.

Ciò che serve è un sistema di pagamento elettronico basato sulla prova crittografica piuttosto che sulla fiducia, che consenta a due parti qualsiasi di effettuare transazioni direttamente tra loro senza la necessità di una terza parte fidata. Le transazioni che sono computazionalmente impossibili da annullare proteggeranno i venditori dalle frodi e i meccanismi convenzionali di deposito a garanzia possono essere facilmente implementati per proteggere gli acquirenti. In questo articolo, proponiamo una soluzione al problema della doppia spesa utilizzando un server di timestamp distribuito peer-to-peer per generare una prova computazionale dell'ordine cronologico delle transazioni. Il sistema è sicuro finché i nodi onesti controllano collettivamente più potenza della CPU rispetto a qualsiasi gruppo cooperante di nodi aggressori.

2. Transazioni

Definiamo una moneta elettronica come una catena di firme digitali. Ogni proprietario passa la moneta al successivo firmando digitalmente l'hash della transazione precedente e la chiave pubblica del proprietario successivo e aggiungendoli alla fine della moneta. Il beneficiario può verificare le firme per confermare la catena di proprietà.

Il problema, ovviamente, è che il beneficiario non può verificare che uno dei proprietari non abbia speso la moneta due volte. Una soluzione comune è quella di creare un’autorità centrale fidata, o zecca, che controlli ogni transazione per eventuali doppie spese. Dopo ogni transazione, la moneta deve essere restituita alla zecca per emetterne una nuova, e solo le monete emesse direttamente dalla zecca hanno la garanzia di non essere spese due volte. Il problema di questa soluzione è che il destino dell’intero sistema monetario dipende dalla società che gestisce la zecca, e ogni transazione deve passare attraverso di essa, proprio come in una banca.

Abbiamo bisogno di un modo in cui il beneficiario possa sapere che i precedenti proprietari non hanno approvato alcuna transazione precedente. Per i nostri scopi, viene conteggiata la prima transazione, quindi non ci interessano i successivi tentativi di doppia spesa. L'unico modo per confermare l'assenza di una transazione è essere a conoscenza di tutte le transazioni. Nel modello basato sulla zecca, la zecca conosceva tutte le transazioni e decideva quali arrivavano per prime. Per raggiungere questo obiettivo senza una parte fidata, le transazioni devono essere annunciate pubblicamente [1] e abbiamo bisogno di un sistema che consenta ai partecipanti di concordare un’unica cronologia dell’ordine in cui sono state ricevute. Il beneficiario ha bisogno della prova che durante ogni transazione la maggioranza dei nodi abbia concordato che sia stata ricevuta per prima.

3. Server di marcatura temporale

La nostra soluzione proposta inizia con un server timestamp. Un server di timestamp funziona prendendo un hash di un blocco di elementi che devono essere contrassegnati con data e ora e pubblicando tale hash su vasta scala, ad esempio in un giornale o in un post su Usenet [2-5]. Il timestamp dimostra che i dati dovevano ovviamente esistere in quel momento per essere inclusi nell'hash. Ogni timestamp include il timestamp precedente nel suo hash, formando una catena, dove ogni timestamp aggiuntivo amplifica quello precedente.

4. Prova del lavoro

Per implementare un server di marcatura temporale peer-to-peer distribuito, dovremmo utilizzare un sistema di prova del lavoro simile a Hashcash di Adam Back [6], piuttosto che i post sui giornali o Usenet. La prova di lavoro prevede la scansione di un valore che, quando sottoposto ad hashing con, ad esempio, SHA-256, il codice hash inizia con una serie di bit zero. Il lavoro medio richiesto dipende in modo esponenziale dal numero di bit zero richiesti e può essere verificato eseguendo un singolo hash.

Per la nostra rete timestamp, implementiamo una prova di lavoro incrementando il nonce in un blocco finché non viene trovato un valore che fornisce all'hash del blocco i bit zero necessari. Una volta che lo sforzo della CPU è stato speso per corrispondere alla prova del lavoro, il blocco non può essere modificato senza rieseguire il lavoro. Poiché i blocchi successivi vengono allegati dopo di esso, il lavoro di modifica di un blocco comporterà la rielaborazione di tutti i blocchi successivi.

La prova del lavoro risolve anche il problema di determinare la rappresentanza nel processo decisionale a maggioranza. Se la maggioranza si basasse sul principio "un indirizzo IP, un voto", chiunque potrebbe attribuire molti indirizzi IP potrebbe smentirlo. La prova del lavoro è essenzialmente "un processore, un voto". La soluzione maggioritaria è rappresentata dalla catena più lunga che richiede il maggiore sforzo per dimostrare il lavoro. Se la maggior parte della potenza della CPU è controllata da nodi onesti, la catena onesta crescerà più velocemente e supererà qualsiasi catena concorrente. Per modificare un blocco precedente, un utente malintenzionato dovrebbe rifare la prova di lavoro del blocco e di tutti i blocchi successivi, quindi recuperare e battere il lavoro dei nodi onesti. Mostreremo in seguito che la probabilità che un attaccante più lento raggiunga il livello diminuisce esponenzialmente man mano che vengono aggiunti i blocchi successivi.

Per compensare l'aumento della velocità dell'hardware e il cambiamento dell'interesse nell'esecuzione dei nodi nel tempo, la prova della difficoltà di lavoro viene determinata utilizzando una media mobile che prende di mira il numero medio di blocchi all'ora. Se vengono generati troppo velocemente, la difficoltà aumenta.

5. Rete

I passaggi per avviare la rete sono i seguenti:

1. Le nuove transazioni vengono trasmesse a tutti i nodi.
2. Ogni nodo raccoglie nuove transazioni in un blocco.
3. Ogni nodo lavora per trovare una prova di lavoro complessa per il suo blocco.
4. Quando un nodo trova una prova di lavoro, trasmette il blocco a tutti i nodi.
5. I nodi accettano un blocco solo se tutte le transazioni in esso contenute sono valide e non sono state ancora spese.
6. I nodi esprimono la loro accettazione di un blocco lavorando per creare il blocco successivo nella catena, utilizzando l'hash del blocco accettato come hash precedente.

I nodi considerano sempre la catena più lunga quella corretta e continuano a lavorare per espanderla. Se due nodi trasmettono simultaneamente versioni diverse del blocco successivo, alcuni nodi potrebbero ricevere prima l'una o l'altra. In questo caso, lavorano con il primo ramo che ottengono, ma ne tengono un altro nel caso in cui diventi più lungo. Il collegamento verrà interrotto quando verrà trovata la successiva prova di lavoro e un ramo si allungherà; i nodi che lavorano sull'altro ramo passeranno a quello più lungo.

Non è necessario che la trasmissione di nuove transazioni raggiunga tutti i nodi. Una volta raggiunti molti nodi, finiranno presto in un blocco. Le trasmissioni in blocco tollerano anche i messaggi persi. Se un nodo non ha ricevuto un blocco, ne richiederà uno quando riceve il blocco successivo e si rende conto di averne mancato uno.

6. Stimolo

Per convenzione, la prima transazione in un blocco è una transazione speciale che lancia una nuova moneta di proprietà del creatore del blocco. Ciò aggiunge un incentivo per i nodi a mantenere la rete e rende possibile la distribuzione iniziale delle monete in circolazione poiché non esiste un’autorità centrale che le emetta. L’aggiunta costante di un numero costante di nuove monete è simile al modo in cui i minatori d’oro spendono risorse aggiungendo oro alla circolazione. Nel nostro caso, il tempo del processore e l'elettricità vengono sprecati.

L’incentivo potrebbe anche essere finanziato attraverso commissioni di transazione. Se il valore di output di una transazione è inferiore al valore di input, la differenza è una commissione di transazione che viene aggiunta al valore di incentivo del blocco contenente la transazione. Una volta che un numero predeterminato di monete entra in circolazione, l’incentivo può spostarsi interamente sulle commissioni di transazione ed essere completamente privo di inflazione.

Un incentivo può aiutare i nodi a rimanere onesti. Se un avido aggressore riesce a raccogliere più potenza della CPU di tutti i nodi onesti, dovrà scegliere tra usarla per truffare le persone rubando i suoi pagamenti o usarla per generare nuove monete. Dovrebbe trovare più redditizio rispettare le regole, regole che gli permettono di ottenere più nuove monete di tutti gli altri messi insieme, piuttosto che minare il sistema e la validità della sua stessa ricchezza.

7. Liberare spazio su disco

Una volta che l'ultima transazione in una moneta è nascosta sotto un numero sufficiente di blocchi, le transazioni spese prima possono essere scartate per risparmiare spazio su disco. Per facilitare ciò senza violare l'hash del blocco, le transazioni vengono sottoposte ad hashing in un albero Merkle [7] [2] [5], con solo la radice inclusa nell'hash del blocco. I vecchi blocchi possono quindi essere compattati tagliando i rami degli alberi. Non è necessario salvare gli hash interni.

L'intestazione del blocco senza transazioni avrà una dimensione di circa 80 byte. Se assumiamo che i blocchi vengano generati ogni 10 minuti, allora 80 byte * 6 * 24 * 365 = 4,2 MB all'anno. Poiché nel 2008 i sistemi informatici venivano generalmente venduti con 2 GB di RAM e la legge di Moore prevede una crescita attuale di 1,2 GB all'anno, lo storage non dovrebbe rappresentare un problema, anche se le intestazioni dei blocchi devono essere archiviate in memoria.

8. Verifica semplificata dei pagamenti

Puoi confermare i pagamenti senza avviare un nodo di rete completo. L'utente deve solo conservare una copia delle intestazioni del blocco della catena di prova più lunga che può ottenere interrogando i nodi della rete finché non è sicuro di avere la catena più lunga e ottenere il ramo Merkle che collega la transazione al blocco . ha un timestamp. Non può verificare personalmente la transazione, ma collegandola a un punto della catena, può vedere che un nodo della rete l'ha accettata e i blocchi aggiunti dopo confermano ulteriormente che la rete l'ha accettata.

Pertanto, la verifica è affidabile finché i nodi onesti controllano la rete, ma diventa più vulnerabile se la rete è sotto il controllo di un utente malintenzionato. Sebbene i nodi della rete possano verificare le transazioni da soli, un metodo di scelta rapida può essere ingannato dalle transazioni fabbricate da un utente malintenzionato fintanto che l'utente malintenzionato continua a sopraffare la rete. Una strategia per proteggersi da ciò sarebbe quella di accettare avvisi dai nodi di rete quando rilevano un blocco non valido, richiedendo al software utente di scaricare l’intero blocco e avvisando le transazioni per confermare la discrepanza. Le aziende che ricevono pagamenti frequenti probabilmente vorranno comunque gestire i propri nodi per una sicurezza più indipendente e una verifica più rapida.

9. Mettere in comune e condividere valore

Anche se sarebbe possibile elaborare le monete individualmente, sarebbe complicato eseguire una transazione separata per ogni centesimo trasferito. Per consentire la condivisione e la messa in comune del valore, le transazioni contengono più input e output. In genere ci sarà un input da una transazione precedente più ampia o più input che combinano importi minori e non più di due output: uno per il pagamento e uno per la restituzione dell'eventuale resto al mittente.

Va notato che il fork, dove una transazione dipende da diverse transazioni e tali transazioni dipendono da molte altre, non è un problema qui. Non è mai necessario recuperare una copia offline completa della cronologia delle transazioni.

10. Privacy

Il modello bancario tradizionale fornisce un certo livello di privacy limitando l’accesso alle informazioni ai soggetti partecipanti e a terzi fidati. La necessità di annunciare pubblicamente tutte le transazioni preclude questo metodo, ma la privacy può comunque essere preservata interrompendo il flusso di informazioni altrove: mantenendo le chiavi pubbliche anonime. Il pubblico può vedere che qualcuno sta inviando un importo a qualcun altro, ma senza informazioni che colleghino la transazione a nessuno. Questo è simile al livello di informazione pubblicato dalle borse, dove i tempi e il volume delle singole operazioni, il “nastro”, sono resi pubblici, ma senza identificare le parti.

Come firewall aggiuntivo, dovrebbe essere utilizzata una nuova coppia di chiavi per ogni transazione per evitare che siano legate a un proprietario comune. Un certo accoppiamento è ancora inevitabile nelle transazioni con più input, che mostrano necessariamente che i loro input appartenevano allo stesso proprietario. Il rischio è che, qualora si scoprisse il proprietario della chiave, l'associazione potrebbe rivelare altre transazioni appartenenti allo stesso proprietario.

11. Calcoli

Consideriamo uno scenario in cui un utente malintenzionato tenta di creare una catena alternativa più velocemente della catena onesta. Anche se ciò venisse raggiunto, non aprirebbe il sistema a cambiamenti arbitrari, come la creazione di valore dal nulla o il prelievo di denaro che non è mai appartenuto all’aggressore. I nodi non accetteranno una transazione non valida come pagamento e i nodi onesti non accetteranno mai un blocco che le contenga. Un utente malintenzionato potrebbe provare a modificare solo una delle sue transazioni per recuperare il denaro speso di recente.

La corsa tra una catena onesta e una catena dannosa può essere caratterizzata come una passeggiata casuale binomiale. Un evento di successo è la catena onesta che viene estesa di un blocco, aumentando il suo vantaggio di +1, e un evento di fallimento è la catena dell'attaccante che viene estesa di un blocco, riducendo il vantaggio di -1.

La probabilità che un attaccante riesca a recuperare un dato deficit è simile al problema di un giocatore che fallisce. Diciamo che un giocatore con credito illimitato inizia con un deficit e potenzialmente gioca un numero infinito di tentativi cercando di pareggiare. Possiamo calcolare la probabilità che si raggiunga il pareggio, o che l'attaccante riesca a raggiungere la catena onesta, come segue [8]:

p = probabilità che un nodo onesto trovi il blocco successivo
q = probabilità che un utente malintenzionato trovi il blocco successivo
qz = probabilità che un utente malintenzionato riesca a raggiungere z blocchi dietro

Dato il nostro presupposto che p > q, la probabilità diminuisce esponenzialmente all’aumentare del numero di blocchi che l’attaccante deve recuperare. Date le probabilità a suo sfavore, se non riesce a effettuare un push vincente all'inizio, le sue possibilità diventeranno incredibilmente piccole man mano che resta indietro.

Vedremo ora quanto tempo deve attendere il destinatario di una nuova transazione prima di essere ragionevolmente sicuro che il mittente non sarà in grado di modificare la transazione. Supponiamo che il mittente sia un utente malintenzionato che vuole ingannare il destinatario facendogli credere di averlo pagato per un po', per poi scambiarlo per restituirgli il denaro dopo che è trascorso un po' di tempo. Quando ciò accade, il destinatario verrà avvisato, ma il mittente spera che sia troppo tardi.

Il destinatario genera una nuova coppia di chiavi e trasmette la chiave pubblica al mittente poco prima della firma. Ciò impedisce al mittente di preparare la blockchain in anticipo, di lavorarci continuamente finché non è abbastanza fortunato da andare abbastanza avanti, e quindi di eseguire la transazione a quel punto. Una volta inviata la transazione, il mittente disonesto inizia a lavorare segretamente su una catena parallela contenente una versione alternativa della sua transazione.

Il destinatario attende finché la transazione non viene aggiunta al blocco e dopo di essa vengono associati z blocchi. Non conosce l'esatto progresso compiuto dall'attaccante, ma presupponendo che i blocchi onesti abbiano impiegato il tempo medio previsto per blocco, il potenziale progresso dell'attaccante sarà una distribuzione di Poisson con il valore atteso:

Per ottenere la probabilità che un attaccante possa ancora recuperare il ritardo adesso, moltiplichiamo la densità di Poisson per ogni quantità di progressi che potrebbe fare per la probabilità che riesca a recuperare da quel punto:

Riarrangiamento per evitare la somma della coda infinita della distribuzione...

Converti in codice C...

 #include <math.h>
double AttackerSuccessProbability(double q, int z)
{
     double p = 1.0 - q;
     doppia lambda = z*(q/p);
     doppia somma = 1,0;
     intervallo i, k;
     for (k = 0; k <= z; k++)
     {
          double Poisson = exp(-lambda);
          for (i = 1; i <= k; i++)
               Poisson *= lambda / i;
          somma -= Poisson * (1 - pow(q/p, z - k));
     }
     ImportoRestituito;
}

Dopo aver eseguito alcuni risultati, possiamo vedere che la probabilità diminuisce esponenzialmente all'aumentare di 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

Soluzione per P inferiore allo 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. Conclusione

Abbiamo proposto un sistema di transazione elettronica senza fare affidamento sulla fiducia. Abbiamo iniziato con una struttura di moneta convenzionale creata utilizzando le firme digitali, che fornisce un forte controllo della proprietà, ma è incompleta senza un modo per prevenire la doppia spesa. Per risolvere questo problema, abbiamo proposto una rete peer-to-peer che utilizza la prova di lavoro per registrare una cronologia delle transazioni pubbliche, che diventa rapidamente computazionalmente poco pratica da modificare per un utente malintenzionato se i nodi onesti controllano la maggior parte della potenza della CPU. La rete è robusta nella sua semplicità non strutturata. I nodi lavorano simultaneamente con poco coordinamento. Non è necessario identificarli perché i messaggi non vengono inoltrati a una destinazione specifica ma vengono consegnati solo al livello più alto possibile. I nodi possono lasciare e ricongiungersi alla rete a piacimento, prendendo la catena di prova del lavoro come prova di ciò che è accaduto mentre erano lontani. Votano con la potenza del loro processore, accettando blocchi validi lavorando per espanderli e rifiutando blocchi non validi rifiutandosi di lavorarci sopra. Tutte le regole e gli incentivi necessari possono essere implementati attraverso questo meccanismo di consenso.

Raccomandazioni

[1] W. Dai, “b-money”, http://www.weidai.com/bmoney.txt, 1998.

[2] H. Massias, K.S. Avila e J.-J. Kiskater, "Sviluppo di un servizio di timestamp sicuro con un sovraccarico minimo."

Requisiti di fiducia”, nel 20° Simposio sulla teoria dell’informazione del Benelux, maggio 1999.

[3] S. Haber, V.S. Stornetta, "Come contrassegnare un documento digitale", Journal of Cryptology, vol 3, n.

2, pagine 99–111, 1991.

[4] D. Bayer, S. Haber, V. S. Stornetta, "Migliorare l'efficienza e l'affidabilità del timestamp digitale".

In sequenze II: metodi di comunicazione, sicurezza e scienza dell'informazione, pagine 329–334, 1993.

[5] S. Haber, V.S. Stornetta, “Nomi sicuri per stringhe di bit”, in Atti della 4a conferenza ACM.

sulla sicurezza informatica e delle comunicazioni, pagine 28–35, aprile 1997.

[6] A. Indietro, “Hashcash – una misura per contrastare la negazione del servizio”,

http://www.hashcash.org/papers/hashcash.pdf, 2002

[7] RC Merkle, "Protocolli per crittosistemi a chiave pubblica", In Proc. 1980 Simposio sulla sicurezza e

Privacy, IEEE Computer Society, pagine 122–133, aprile 1980.

[8] W. Feller, “Introduzione alla teoria della probabilità e alle sue applicazioni”, 1957.