Bitcoin: Un Sistema di Denaro Elettronico Peer-to-Peer
Una versione puramente peer-to-peer di denaro elettronico consentirebbe pagamenti online da una parte all'altra senza passare attraverso un'istituzione finanziaria. Le firme digitali forniscono parte della soluzione, ma i principali benefici si perdono se è ancora necessario un terzo fidato per prevenire la doppia spesa. Proponiamo una soluzione al problema della doppia spesa utilizzando una rete peer-to-peer. La rete data e ora le transazioni hashing in una catena in corso di prova di lavoro basata su hash, formando un record che non può essere cambiato senza rifare la prova di lavoro. La catena più lunga non solo serve come prova della sequenza di eventi testimoniati, ma prova che proviene dal più grande pool di potenza CPU. Finché una maggioranza della potenza CPU è controllata da nodi che non cooperano per attaccare la rete, genereranno la catena più lunga e supereranno gli attaccanti. La rete stessa richiede una struttura minima. I messaggi vengono trasmessi su una base di massimo sforzo e i nodi possono lasciare e rientrare nella rete a piacimento, accettando la catena di prova di lavoro più lunga come prova di ciò che è successo mentre erano assenti.
1. Introduzione Il commercio su Internet è diventato quasi esclusivamente dipendente da istituzioni finanziarie che fungono da terze parti fidate per elaborare pagamenti elettronici. Sebbene il sistema funzioni abbastanza bene per la maggior parte delle transazioni, soffre ancora delle debolezze intrinseche del modello basato sulla fiducia. Transazioni completamente non reversibili non sono realmente possibili, poiché le istituzioni finanziarie non possono evitare di mediare le controversie. Il costo della mediazione aumenta i costi delle transazioni, limitando la dimensione minima pratica della transazione e interrompendo la possibilità di transazioni casuali di piccole dimensioni, e c'è un costo più ampio nella perdita della capacità di effettuare pagamenti non reversibili per servizi non reversibili. Con la possibilità di annullamento, la necessità di fiducia si diffonde. I commercianti devono essere cauti nei confronti dei loro clienti, infastidendoli per ottenere più informazioni di quanto altrimenti necessiterebbero. Una certa percentuale di frode è accettata come inevitabile. Questi costi e le incertezze nei pagamenti possono essere evitati di persona utilizzando valuta fisica, ma non esiste un meccanismo per effettuare pagamenti su un canale di comunicazione senza una parte fidata. Ciò di cui c'è bisogno è un sistema di pagamento elettronico basato su prove crittografiche anziché sulla fiducia, consentendo a qualsiasi due parti disposte di transare direttamente tra loro senza la necessità di una terza parte fidata. Transazioni che sono computazionalmente impraticabili da annullare proteggerebbero i venditori dalle frodi, e meccanismi di escrow di routine potrebbero essere facilmente implementati per proteggere gli acquirenti. In questo documento, proponiamo una soluzione al problema della doppia spesa utilizzando un server di timestamp distribuito peer-to-peer per generare prove computazionali dell'ordine cronologico delle transazioni. Il sistema è sicuro finché i nodi onesti controllano collettivamente più potenza CPU di qualsiasi gruppo cooperante di nodi attaccanti.
2. Verifica delle 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 prossimo proprietario e aggiungendo questi alla fine della moneta. Un beneficiario può verificare le firme per verificare la catena di proprietà. Transazione Verifica Chiave Pubblica del Proprietario 1 Hash Firma del Proprietario 0 Chiave Privata del Proprietario 1 Transazione Chiave Pubblica del Proprietario 2 Hash Firma del Proprietario 1 Chiave Privata del Proprietario 2 Transazione Chiave Pubblica del Proprietario 3 Hash Firma del Proprietario 2 Chiave Privata del Proprietario 3 Il problema, ovviamente, è che il beneficiario non può verificare che uno dei proprietari non abbia speso due volte la moneta. Una soluzione comune è introdurre un'autorità centrale fidata, o zecca, che controlla ogni transazione per doppia spesa. Dopo ogni transazione, la moneta deve essere restituita alla zecca per emettere una nuova moneta, e solo le monete emesse direttamente dalla zecca sono fidate per non essere spese due volte. Il problema con questa soluzione è che il destino dell'intero sistema monetario dipende dall'azienda che gestisce la zecca, con ogni transazione che deve passare attraverso di loro, proprio come una banca. Abbiamo bisogno di un modo per il beneficiario di sapere che i proprietari precedenti non hanno firmato alcuna transazione precedente. Ai fini della nostra analisi, la transazione più antica è quella che conta, quindi non ci interessa i tentativi successivi 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 prima. Per realizzare questo senza una parte fidata, le transazioni devono essere annunciate pubblicamente [1], e abbiamo bisogno di un sistema affinché i partecipanti possano concordare su una singola storia dell'ordine in cui sono state ricevute. Il beneficiario ha bisogno di prova che al momento di ogni transazione, la maggior parte dei nodi concordava che era la prima ricevuta.
3. Server di Timestamp La soluzione che proponiamo inizia con un server di timestamp. Un server di timestamp funziona prendendo un hash di un blocco di elementi da timestampare e pubblicando ampiamente l'hash, come in un giornale o in un post Usenet [2-5]. Il timestamp prova che i dati devono essere esistiti in quel momento, ovviamente, per entrare nell'hash. Ogni timestamp include il timestamp precedente nel suo hash, formando una catena, con ogni timestamp aggiuntivo che rinforza quelli precedenti. Hash Hash Blocco Oggetto Oggetto Blocco ... Oggetto Oggetto ...
4. Prova di Lavoro Per implementare un server di timestamp distribuito su base peer-to-peer, dovremo utilizzare un sistema di prova di lavoro simile a Hashcash di Adam Back [6], piuttosto che post su giornali o Usenet. La prova di lavoro comporta la scansione di un valore che, quando hashato, come con SHA-256, l'hash inizia con un certo 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 di timestamp, implementiamo la prova di lavoro incrementando un nonce nel blocco fino a trovare un valore che dia all'hash del blocco i bit zero richiesti. Una volta che lo sforzo CPU è stato speso per farlo soddisfare la prova di lavoro, il blocco non può essere cambiato senza rifare il lavoro. Poiché i blocchi successivi sono concatenati dopo di esso, il lavoro per cambiare il blocco includerebbe rifare tutti i blocchi dopo di esso. Blocco Hash Precedente Tx Blocco Nonce Tx ... Hash Precedente Nonce Tx Tx ... La prova di lavoro risolve anche il problema di determinare la rappresentanza nel processo decisionale a maggioranza. Se la maggioranza fosse basata su uno-IP-indirizzo-uno-voto, potrebbe essere sovvertita da chiunque fosse in grado di allocare molti IP. La prova di lavoro è essenzialmente uno-CPU-uno-voto. La decisione della maggioranza è rappresentata dalla catena più lunga, che ha il maggiore sforzo di prova di lavoro investito in essa. Se una maggioranza della potenza CPU è controllata da nodi onesti, la catena onesta crescerà più rapidamente e supererà qualsiasi catena concorrente. Per modificare un blocco passato, un attaccante 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 recuperi diminuisce esponenzialmente man mano che vengono aggiunti successivi blocchi. Per compensare l'aumento della velocità dell'hardware e l'interesse variabile nell'eseguire nodi nel tempo, la difficoltà della prova di lavoro è determinata da una media mobile che mira a un numero medio di blocchi all'ora. Se vengono generati troppo rapidamente, la difficoltà aumenta.
5. Rete I passaggi per gestire la rete sono i seguenti: 1) Le nuove transazioni vengono broadcastate a tutti i nodi. 2) Ogni nodo raccoglie nuove transazioni in un blocco. 3) Ogni nodo lavora per trovare una difficile prova di lavoro per il suo blocco. 4) Quando un nodo trova una prova di lavoro, la broadcasta a tutti i nodi. 5) I nodi accettano il blocco solo se tutte le transazioni in esso sono valide e non già spese. 6) I nodi esprimono la loro accettazione del blocco lavorando per creare il prossimo blocco nella 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 broadcastano versioni diverse del prossimo blocco simultaneamente, alcuni nodi potrebbero ricevere uno o l'altro per primo. In tal caso, lavorano sul primo che hanno ricevuto, ma salvano l'altro ramo nel caso diventi più lungo. Il pareggio sarà risolto quando verrà trovata la prossima prova di lavoro e un ramo diventa più lungo; i nodi che stavano lavorando sull'altro ramo passeranno poi a quello più lungo.
Le broadcast delle nuove transazioni non è necessario che raggiungano necessariamente tutti i nodi. Finché raggiungono molti nodi, entreranno in un blocco prima o poi. Anche le broadcast dei blocchi sono tolleranti ai messaggi persi. Se un nodo non riceve un blocco, ne richiederà uno quando riceve il prossimo blocco e si rende conto di averne perso uno.
6. Incentivo Per convenzione, la prima transazione in un blocco è una transazione speciale che avvia una nuova moneta posseduta dal creatore del blocco. Questo 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 un certo ammontare di nuove monete è analoga agli estrattori d'oro che spendono risorse per aggiungere oro alla circolazione. Nel nostro caso, sono il tempo CPU e l'elettricità a essere spesi. L'incentivo può anche essere finanziato con le commissioni di transazione. Se il valore di output di una transazione è inferiore al suo valore di input, la differenza è una commissione di transazione che viene aggiunta al valore dell'incentivo del blocco contenente la transazione. Una volta che un numero predeterminato di monete è entrato in circolazione, l'incentivo può passare completamente alle commissioni di transazione ed essere completamente privo di inflazione. L'incentivo può aiutare a incoraggiare i nodi a rimanere onesti. Se un attaccante avido è in grado di assemblare più potenza CPU di tutti i nodi onesti, dovrebbe scegliere tra utilizzarlo per frodare le persone rubando indietro i suoi pagamenti, o usarlo per generare nuove monete. Dovrebbe trovare più redditizio giocare secondo le regole, tali regole che lo favoriscono con più nuove monete di tutti gli altri messi insieme, piuttosto che minare il sistema e la validità della sua stessa ricchezza.
7. Recupero dello Spazio su Disco Una volta che l'ultima transazione in una moneta è sepolta sotto un numero sufficiente di blocchi, le transazioni spese prima di essa possono essere scartate per risparmiare spazio su disco. Per facilitare questo senza rompere l'hash del blocco, le transazioni sono hashate in un Albero di Merkle [7][2][5], con solo la radice inclusa nell'hash del blocco. I vecchi blocchi possono quindi essere compattati staccando rami dell'albero. Gli hash interni non devono essere memorizzati. Blocco Intestazione Blocco (Hash del Blocco) Hash Precedente Nonce Hash Radice Hash01 Hash0 Hash1 Hash23 Hash2 Tx0 Tx1 Tx2 Hash3 Tx3 Transazioni Hashate in un Albero di Merkle Blocco Intestazione Blocco (Hash del Blocco) Hash Precedente Nonce Hash Radice Hash01 Hash23 Hash2 Hash3 Tx3 Dopo la Potatura Tx0-2 dal Blocco 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.2MB all'anno. Con i sistemi informatici che tipicamente vendono con 2GB di RAM a partire dal 2008, e la Legge di Moore che prevede una crescita attuale di 1.2GB all'anno, lo stoccaggio non dovrebbe essere un problema anche se le intestazioni dei blocchi devono essere mantenute in memoria.
8. Verifica dei Pagamenti Semplificata È possibile verificare i pagamenti senza eseguire un nodo di rete completo. Un utente deve solo mantenere una copia delle intestazioni dei blocchi della catena di prova di lavoro più lunga, che può ottenere interrogando i nodi di rete fino a quando non è convinto di avere la catena più lunga, e ottenere il ramo Merkle che collega la transazione al blocco in cui è timestampato. Non può controllare la transazione da solo, ma collegandola a un punto nella catena, può vedere che un nodo di rete l'ha accettata, e i blocchi aggiunti dopo confermano ulteriormente che la rete l'ha accettata. Catena di Prova di Lavoro più Lunga Intestazione Blocco Hash Precedente Nonce Radice Merkle Intestazione Blocco Hash Precedente Radice Merkle Hash01 Hash2 Intestazione Blocco Nonce Hash Precedente Nonce Radice Merkle Hash23 Ramo Merkle per Tx3 Hash3 Tx3 Come tale, la verifica è affidabile finché i nodi onesti controllano la rete, ma è più vulnerabile se la rete è sopraffatta da un attaccante. Mentre i nodi di rete possono verificare le transazioni per conto proprio, il metodo semplificato può essere ingannato dalle transazioni fabricate di un attaccante finché l'attaccante può continuare a sopraffare la rete. Una strategia per proteggere contro questo sarebbe accettare avvisi dai nodi di rete quando rilevano un blocco non valido, spingendo il software dell'utente a scaricare il blocco completo e le transazioni avvisate per confermare l'incoerenza. Le aziende che ricevono pagamenti frequenti probabilmente vorranno ancora eseguire i propri nodi per maggiore sicurezza indipendente e verifica più rapida.
9. Combinazione e Divisione del Valore Sebbene sia possibile gestire le monete individualmente, sarebbe ingombrante effettuare una transazione separata per ogni centesimo in un trasferimento. Per consentire al valore di essere suddiviso e combinato, le transazioni contengono più input e output. Normalmente ci sarà o 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 il resto, se presente, al mittente. Transazione In In Out ... ... Si dovrebbe notare che la diffusione, dove una transazione dipende da diverse transazioni, e quelle transazioni dipendono da molte altre, non è un problema qui. Non c'è mai la necessità di estrarre una copia completa e autonoma della storia di una transazione.
10. Privacy Il modello bancario tradizionale raggiunge un certo livello di privacy limitando l'accesso alle informazioni solo alle parti coinvolte e alla terza parte fidata. La necessità di annunciare pubblicamente tutte le transazioni esclude 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 chiunque. Questo è simile al livello di informazioni rilasciato dalle borse valori, dove il tempo e la dimensione delle singole operazioni, il "nastro", viene reso pubblico, ma senza rivelare chi erano le parti. Modello di Privacy Tradizionale Identità Nuovo Modello di Privacy Identità Transazioni Terza Parte Fiducia Transazioni Controparte Pubblica Pubblica Come firewall aggiuntivo, una nuova coppia di chiavi dovrebbe essere utilizzata per ogni transazione per mantenerle non collegate a un proprietario comune. Alcuni collegamenti sono comunque inevitabili con transazioni a più input, che rivelano necessariamente che i loro input erano di proprietà dello stesso proprietario. Il rischio è che se il proprietario di una chiave viene rivelato, il collegamento potrebbe rivelare altre transazioni appartenenti allo stesso proprietario.
11. Calcoli Consideriamo lo scenario di un attaccante che cerca di generare una catena alternativa più velocemente della catena onesta. Anche se ciò viene realizzato, non apre il sistema a cambiamenti arbitrari, come creare valore dal nulla o prendere soldi che non sono mai appartenuti all'attaccante. I nodi non accetteranno una transazione non valida come pagamento, e i nodi onesti non accetteranno mai un blocco contenente tali transazioni. Un attaccante può solo cercare di cambiare una delle proprie transazioni per riprendersi i soldi che ha recentemente speso. La corsa tra la catena onesta e una catena di attaccanti può essere caratterizzata come un Cammino Casuale Binomiale. L'evento di successo è l'estensione della catena onesta di un blocco, aumentando il suo vantaggio di +1, e l'evento di fallimento è l'estensione della catena dell'attaccante di un blocco, riducendo il divario di -1. La probabilità che un attaccante recuperi da un dato deficit è analoga a un problema di Rovina del Giocatore. Supponiamo che un giocatore con credito illimitato parta da un deficit e giochi un numero potenzialmente infinito di prove per cercare di raggiungere il pareggio. Possiamo calcolare la probabilità che raggiunga mai il pareggio, o che un attaccante recuperi mai dalla catena onesta, come segue [8]: p = probabilità che un nodo onesto trovi il prossimo blocco q = probabilità che l'attaccante trovi il prossimo blocco qz = probabilità che l'attaccante recuperi mai da z blocchi dietro qz = { 1 se p≤q (q/p)z se p>q }
Data la nostra assunzione che p > q, la probabilità diminuisce esponenzialmente man mano che aumenta il numero di blocchi di cui l'attaccante deve recuperare. Con le probabilità contro di lui, se non fa una mossa fortunata in avanti all'inizio, le sue possibilità diventano sempre più piccole man mano che rimane indietro. Ora consideriamo quanto tempo deve aspettare il destinatario di una nuova transazione prima di essere sufficientemente certo che il mittente non possa cambiare la transazione. Assumiamo che il mittente sia un attaccante che vuole far credere al destinatario di averlo pagato per un po ', per poi passare a restituire a se stesso dopo che è passato un po 'di tempo. Il destinatario riceverà un avviso quando ciò accade, ma il mittente spera che sarà troppo tardi. Il destinatario genera una nuova coppia di chiavi e fornisce la chiave pubblica al mittente poco prima di firmare. Questo impedisce al mittente di preparare una catena di blocchi in anticipo lavorandoci continuamente fino a quando non ha la fortuna di avanzare abbastanza, quindi eseguendo la transazione in quel momento. Una volta che la transazione è inviata, il mittente disonesto inizia a lavorare in segreto su una catena parallela contenente una versione alternativa della sua transazione. Il destinatario aspetta fino a quando la transazione è stata aggiunta a un blocco e z blocchi sono stati collegati dopo di essa. Non conosce l'esatto ammontare dei progressi che l'attaccante ha fatto, ma assumendo 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: λ=z(q/p) Per ottenere la probabilità che l'attaccante possa ancora recuperare ora, moltiplichiamo la densità di Poisson per ciascun ammontare di progresso che potrebbe aver fatto per la probabilità che potrebbe recuperare da quel punto: ∞ λke−λ ∑ k=0 k! ⋅ { (q/p)(z−k) if k≤z 1 if k>z } Riordinando per evitare di sommare la coda infinita della distribuzione... 1−∑ k=0 z λke−λ k! (1−(q/p)(z−k)) Convertendo in codice C... #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; }
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=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 Risolvendo per P inferiore all'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 per transazioni elettroniche senza fare affidamento sulla fiducia. Abbiamo iniziato con il consueto quadro delle monete fatte di firme digitali, che fornisce un forte controllo della proprietà, ma è incompleto senza un modo per prevenire la doppia spesa. Per risolvere questo, abbiamo proposto una rete peer-to-peer utilizzando la prova di lavoro per registrare una storia pubblica delle transazioni che diventa rapidamente computazionalmente impraticabile per un attaccante cambiarla se i nodi onesti controllano la maggior parte della potenza CPU. La rete è robusta nella sua semplicità non strutturata. I nodi lavorano tutti insieme con poca coordinazione. Non è necessario identificarli, poiché i messaggi non vengono instradati in un luogo particolare e devono solo essere consegnati su base di massimo sforzo. I nodi possono lasciare e rientrare nella rete a piacimento, accettando la catena di prova di lavoro come prova di ciò che è accaduto mentre erano assenti. Votano con la loro potenza CPU, esprimendo la loro accettazione di blocchi validi lavorando per estenderli e rifiutando blocchi non validi rifiutando di lavorarci sopra. Qualsiasi regola e incentivo necessario possono essere applicati con questo meccanismo di consenso.