Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org
Riassunto: Una versione puramente peer-to-peer del contante elettronico consentirebbe di inviare pagamenti online direttamente da un soggetto all’altro senza passare attraverso un 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 timestamp delle transazioni inserendole in una catena continua di prove di lavoro basate su hash, formando un record che non può essere modificato senza rifare la prova di lavoro. La catena più lunga non serve solo come prova della sequenza di eventi a cui si è assistito, ma anche come prova che proviene dal più grande pool di potenza della CPU. Finché la maggior parte della potenza della CPU è controllata da nodi che non collaborano per attaccare la rete, genereranno la catena più lunga e supereranno gli aggressori. La rete stessa richiede una struttura minima. I messaggi vengono trasmessi sulla base del massimo sforzo e i nodi possono lasciare e ricongiungersi alla rete a piacimento, accettando la catena di prova di lavoro più lunga come prova di ciò che è accaduto mentre erano assenti.
1. Introduzione
Il commercio su Internet è arrivato a fare affidamento quasi esclusivamente su istituti finanziari che fungono da terze parti fidate per elaborare i pagamenti elettronici. Sebbene il sistema funzioni abbastanza bene per la maggior parte delle transazioni, soffre ancora delle debolezze intrinseche del modello basato sulla fiducia. Le transazioni completamente irreversibili non sono realmente possibili, poiché gli istituti finanziari non possono evitare di mediare le controversie. Il costo della mediazione aumenta i costi di transazione, limitando la dimensione pratica minima della transazione e tagliando la possibilità di piccole transazioni casuali, e c’è un costo più ampio nella perdita della capacità di effettuare pagamenti non reversibili per servizi non reversibili. Con la possibilità di inversione, il bisogno di fiducia si diffonde. I commercianti devono diffidare dei propri clienti, assillandoli con più informazioni di quelle di cui avrebbero altrimenti bisogno. Una certa percentuale di frodi è accettata come inevitabile. Questi costi e le incertezze nei pagamenti possono essere evitati di persona utilizzando la valuta fisica, ma non esiste alcun meccanismo per effettuare pagamenti su un canale di comunicazione senza una parte fidata.
Ciò che serve è un sistema di pagamento elettronico basato sulla prova crittografica anziché sulla fiducia, che consenta a due parti consenzienti di effettuare transazioni direttamente tra loro senza la necessità di una terza parte fidata. Le transazioni che sono computazionalmente impraticabili da invertire proteggerebbero i venditori dalle frodi e i meccanismi di deposito a garanzia di routine potrebbero 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 trasferisce la moneta al successivo firmando digitalmente un hash della transazione precedente e la chiave pubblica del proprietario successivo e aggiungendoli alla fine della moneta. Un beneficiario può verificare le firme per verificare la catena di proprietà.
Il problema ovviamente è che il beneficiario non può verificare che uno dei proprietari non abbia speso due volte la moneta. Una soluzione comune è quella di introdurre un’autorità centrale fidata, o zecca, che controlli ogni transazione per la doppia spesa. Dopo ogni transazione, la moneta deve essere restituita alla zecca per emettere una nuova moneta, e si ritiene che solo le monete emesse direttamente dalla zecca non vengano spese due volte. Il problema con 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 una banca. Abbiamo bisogno di un modo in cui il beneficiario possa sapere che i precedenti proprietari non hanno firmato alcuna transazione precedente. Per i nostri scopi, la prima transazione è quella che conta, 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 era a conoscenza di tutte le transazioni e decideva quale arrivava per prima. 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 al momento di ciascuna transazione, la maggior parte dei nodi ha concordato che fosse la prima ricevuta.
3. Server di marcatura temporale
La soluzione che proponiamo inizia con un server timestamp. Un server di marcatura temporale funziona prendendo un hash di un blocco di elementi a cui applicare la marcatura temporale e pubblicando ampiamente l'hash, come in un giornale o in un post su Usenet [2-5]. Il timestamp dimostra che i dati dovevano esistere in quel momento, ovviamente, per poter entrare nell'hash. Ogni timestamp include il timestamp precedente nel suo hash, formando una catena, in cui ogni timestamp aggiuntivo rinforza quelli precedenti.
4. Prova di lavoro
Per implementare un server di timestamp distribuito su base peer-to-peer, avremo bisogno di utilizzare un sistema di prova del lavoro simile a Hashcash di Adam Back [6], piuttosto che i giornali o i post di Usenet. La prova di lavoro prevede la scansione di un valore che, una volta sottoposto a hash, come con SHA-256, l'hash inizia con un numero di bit zero. Il lavoro medio richiesto è esponenziale nel numero di bit zero richiesti e può essere verificato eseguendo un singolo hash.
Per la nostra rete timestamp, implementiamo la prova di lavoro incrementando un nonce nel blocco finché non viene trovato un valore che fornisce all'hash del blocco i bit zero richiesti. Una volta che lo sforzo della CPU è stato speso per soddisfare la prova di lavoro, il blocco non può essere modificato senza rifare il lavoro. Poiché i blocchi successivi vengono concatenati dopo di esso, il lavoro per modificare il blocco includerebbe la rifacimento 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 fosse basata su un indirizzo IP, un voto, potrebbe essere sovvertita da chiunque sia in grado di assegnare molti IP. La prova del lavoro è essenzialmente una CPU, un voto. La decisione a maggioranza è rappresentata dalla catena più lunga, su cui è stato investito il maggiore sforzo di proof-of-work. 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 passato, un utente malintenzionato dovrebbe rifare la prova di lavoro del blocco e di tutti i blocchi successivi e poi recuperare e superare 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 variare dell'interesse nell'esecuzione dei nodi nel tempo, la difficoltà della prova di lavoro è determinata da una media mobile che prende di mira un numero medio di blocchi all'ora. Se vengono generati troppo velocemente, la difficoltà aumenta.
5. Rete
I passaggi per eseguire 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 difficile per il suo blocco.
4) Quando un nodo trova una prova di lavoro, trasmette il blocco a tutti i nodi.
5) I nodi accettano il blocco solo se tutte le transazioni in esso contenute sono valide e non già spese.
6) I nodi esprimono la loro accettazione del blocco lavorando alla creazione del blocco successivo della catena, utilizzando l'hash del blocco accettato come hash precedente.
I nodi considerano sempre la catena più lunga come quella corretta e continueranno a lavorare per estenderla. Se due nodi trasmettono simultaneamente versioni diverse del blocco successivo, alcuni nodi potrebbero ricevere prima l'una o l'altra. In tal caso, lavorano sul primo ramo ricevuto, ma salvano l'altro ramo nel caso in cui diventi più lungo. Il legame verrà spezzato quando verrà trovata la successiva prova di lavoro e un ramo diventerà più lungo; i nodi che stavano lavorando sull'altro ramo passeranno quindi a quello più lungo.
Le trasmissioni di nuove transazioni non devono necessariamente raggiungere tutti i nodi. Finché raggiungono molti nodi, finiranno presto in un blocco. Le trasmissioni in blocco tollerano anche i messaggi eliminati. Se un nodo non riceve un blocco, lo richiederà quando riceve il blocco successivo e si rende conto di averne mancato uno.
6. Incentivo
Per convenzione, la prima transazione in un blocco è una transazione speciale che avvia una nuova moneta di proprietà del creatore del blocco. Ciò aggiunge un incentivo per i nodi a supportare la rete e fornisce un modo per distribuire inizialmente le monete in circolazione poiché non esiste un’autorità centrale per emetterle. L’aggiunta costante di una quantità costante di nuove monete è analoga al fatto che i minatori d’oro spendono risorse per aggiungere oro alla circolazione. Nel nostro caso, vengono consumati tempo di CPU ed elettricità.
L’incentivo può anche essere finanziato con 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 è entrato in circolazione, l’incentivo può passare interamente alle commissioni di transazione ed essere completamente esente da inflazione.
L’incentivo può aiutare a incoraggiare i nodi a rimanere onesti. Se un avido aggressore fosse in grado di accumulare più potenza della CPU di tutti i nodi onesti, dovrebbe scegliere tra usarla per frodare le persone rubandogli i pagamenti o usarla per generare nuove monete. Dovrebbe trovare più redditizio rispettare le regole, regole che lo favoriscono con più monete nuove di chiunque altro messo insieme, piuttosto che minare il sistema e la validità della sua stessa ricchezza.
7. Recupero di spazio su disco
Una volta che l'ultima transazione in una moneta è sepolta sotto un numero sufficiente di blocchi, le transazioni spese prima possono essere scartate per risparmiare spazio su disco. Per facilitare ciò senza rompere l'hash del blocco, le transazioni vengono sottoposte ad hashing in un Merkle Tree [7] [2] [5], con solo la radice inclusa nell'hash del blocco. I vecchi blocchi possono quindi essere compattati tagliando i rami dell'albero. Non è necessario archiviare gli hash interni.
Un'intestazione di blocco senza transazioni sarebbe di circa 80 byte. Se supponiamo che i blocchi vengano generati ogni 10 minuti, 80 byte 6 24 * 365 = 4,2 MB all'anno. Con i sistemi informatici venduti tipicamente con 2 GB di RAM a partire dal 2008 e la Legge di Moore che prevede una crescita attuale di 1,2 GB all'anno, l'archiviazione non dovrebbe essere un problema anche se le intestazioni dei blocchi devono essere mantenute in memoria.
8. Verifica semplificata dei pagamenti
È possibile verificare i pagamenti senza eseguire un nodo di rete completo. Un 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 è convinto di avere la catena più lunga, e ottenere il ramo Merkle che collega la transazione al blocco è dotato di timestamp. Non può controllare la transazione da solo, ma collegandola a un punto della catena, può vedere che un nodo di 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 è più vulnerabile se la rete viene sopraffatta da un utente malintenzionato. Mentre i nodi della rete possono verificare le transazioni da soli, il metodo semplificato può essere ingannato dalle transazioni fabbricate da un utente malintenzionato finché quest'ultimo 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 dell'utente di scaricare il blocco completo e avvisare le transazioni per confermare l'incoerenza. Le aziende che ricevono pagamenti frequenti probabilmente vorranno comunque gestire i propri nodi per una sicurezza più indipendente e una verifica più rapida.
9. Combinazione e suddivisione del valore
Anche se sarebbe possibile gestire le monete individualmente, sarebbe scomodo effettuare una transazione separata per ogni centesimo di un trasferimento. Per consentire la suddivisione e la combinazione del valore, le transazioni contengono più input e output. Normalmente ci sarà un singolo input da una transazione precedente più grande o più input che combinano importi più piccoli e al massimo due output: uno per il pagamento e uno che restituisce l'eventuale resto al mittente.
Va notato che il fan-out, in cui una transazione dipende da diverse transazioni e tali transazioni dipendono da molte altre, non è un problema in questo caso. Non c'è mai la necessità di estrarre una copia autonoma e completa della cronologia di una transazione.
10. Privacy
Il modello bancario tradizionale raggiunge un livello di privacy limitando l’accesso alle informazioni alle parti coinvolte e alla terza parte di fiducia. La necessità di annunciare pubblicamente tutte le transazioni preclude questo metodo, ma la privacy può comunque essere mantenuta interrompendo il flusso di informazioni in un altro luogo: 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 diffuso dalle borse, dove il tempo e la dimensione delle singole operazioni, il "nastro", sono resi pubblici, ma senza dire chi fossero le parti.
Come firewall aggiuntivo, dovrebbe essere utilizzata una nuova coppia di chiavi per ogni transazione per evitare che siano collegate a un proprietario comune. Alcuni collegamenti sono ancora inevitabili con le transazioni multi-input, che rivelano necessariamente che i loro input erano di proprietà dello stesso proprietario. Il rischio è che se viene rivelato il proprietario di una chiave, il collegamento potrebbe rivelare altre transazioni appartenute allo stesso proprietario.
11. Calcoli
Consideriamo lo scenario in cui un utente malintenzionato tenta di generare una catena alternativa più velocemente della catena onesta. Anche se ciò viene realizzato, non espone 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 può solo provare a modificare una delle sue transazioni per riprendersi il denaro speso di recente. La corsa tra la catena onesta e la catena attaccante può essere caratterizzata come una passeggiata casuale binomiale. L'evento di successo è che la catena onesta viene estesa di un blocco, aumentando il suo vantaggio di +1, e l'evento di fallimento è che la catena dell'attaccante viene estesa di un blocco, riducendo il divario di -1.
La probabilità che un attaccante recuperi un dato deficit è analoga al problema della Rovina del Giocatore. Supponiamo che un giocatore con credito illimitato inizi con un deficit e giochi potenzialmente un numero infinito di prove per cercare di raggiungere il pareggio. Possiamo calcolare la probabilità che raggiunga il pareggio, o che un attaccante raggiunga la catena onesta, come segue [8]:
p = probabilità che un nodo onesto trovi il blocco successivo
q = probabilità che l'attaccante trovi il blocco successivo
qz = probabilità che l'attaccante riesca a raggiungere z blocchi dietro
qz= { 1 se p≤q
(q/ p)^z se p>q}
Dato il nostro presupposto che p > q, la probabilità diminuisce esponenzialmente all’aumentare del numero di blocchi che l’attaccante deve recuperare. Con le probabilità contro di lui, se non fa un balzo fortunato in avanti all'inizio, le sue possibilità diventano evanescenti man mano che rimane più indietro.
Consideriamo ora quanto tempo deve attendere il destinatario di una nuova transazione prima di essere sufficientemente sicuro che il mittente non possa modificare la transazione. Supponiamo che il mittente sia un utente malintenzionato che vuole far credere al destinatario di averlo pagato per un po', per poi scambiarlo per ripagare se stesso dopo che è trascorso un po' di tempo. Il destinatario verrà avvisato quando ciò accade, ma il mittente spera che sia troppo tardi.
Il destinatario genera una nuova coppia di chiavi e fornisce la chiave pubblica al mittente poco prima della firma. Ciò impedisce al mittente di preparare una catena di blocchi in anticipo lavorandoci continuamente finché non ha la fortuna di andare abbastanza avanti, per poi eseguire la transazione in quel momento. Una volta inviata la transazione, il mittente disonesto inizia a lavorare in segreto su una catena parallela contenente una versione alternativa della sua transazione.
Il destinatario attende finché la transazione non viene aggiunta a un blocco e i blocchi z vengono successivamente collegati. Non conosce l'esatto ammontare di progressi compiuti 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 valore atteso:
Conversione in codice C...
Eseguendo alcuni risultati, possiamo vedere che la probabilità diminuisce esponenzialmente con z.
q=0,1
z=0 P=1.0000000
z=1 P=0,2045873
z=2P=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
Risolvendo per P inferiore allo 0,1%...
P<0,001
q=0,10 z=5
q=0,15z=8
q=0,20 z=11
q=0,25z=15
q=0,30z=24
q=0,35z=41
q=0,40 z=89
q=0,45 z=340
12. Conclusione
Abbiamo proposto un sistema per le transazioni elettroniche senza fare affidamento sulla fiducia. Abbiamo iniziato con il consueto quadro delle monete realizzate con firme digitali, che fornisce un forte controllo della proprietà, ma è incompleto 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 pubblica delle transazioni 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 funzionano tutti insieme con poca coordinazione. Non è necessario identificarli, poiché i messaggi non vengono indirizzati verso un luogo particolare e devono essere consegnati solo con il massimo impegno. I nodi possono lasciare e ricongiungersi alla rete a piacimento, accettando la catena di prova del lavoro come prova di ciò che è accaduto mentre erano assenti. Votano con la potenza della loro CPU, esprimendo la loro accettazione di blocchi validi lavorando per estenderli e rifiutando i blocchi non validi rifiutandosi di lavorarci sopra. Tutte le regole e gli incentivi necessari possono essere applicati con questo meccanismo di consenso.
Riferimenti
[1] W. Dai, "b-money", http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila e J.‑J. Quisquater, "Progettazione di un servizio di timestamp sicuro con requisiti minimi
requisiti di fiducia", nel 20° Simposio sulla teoria dell'informazione nel Benelux, maggio 1999.
[3] S. Haber, W.S. Stornetta, "Come timbrare un documento digitale", in Journal of Cryptology, vol 3, n
2, pagine 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, "Migliorare l'efficienza e l'affidabilità della marcatura temporale digitale",
In Sequenze II: Metodi di comunicazione, sicurezza e informatica, pagine 329-334, 1993.
[5] S. Haber, W.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 contromisura per 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, "Un'introduzione alla teoria della probabilità e alle sue applicazioni", 1957.
