Tag Archives: bitcoin

Bitcoin. Come funziona? (II)

Il funzionamento di Bitcoin (II) — prove e conoscenza comune

di Dusty,  il Portico Dipinto ( 17/07/2011)
In un post precedente sono stati esposti alcuni dei concetti crittografici che sono alla base del funzionamento di Bitcoin.

In questo vedremo invece una panoramica del funzionamento ad un livello più alto.

E’ necessario prima di tutto inquadrare i problemi da affrontare per implementare un sistema di transazioni monetarie completamente decentralizzato ed anonimo (o meglio, pseudoanonimo). Il problema principale è quello di riuscire ad avere una “conoscenza comune” delle proprietà della moneta. In particolare tutti devono sapere chi è il proprietario corrente di ogni unità monetaria (per evitare che qualcuno “spenda” del denaro che non gli appartiene), ma bisogna anche sapere che tutti abbiano le stesse informazioni. Ed è necessario sapere che gli altri sappiano che io so che loro sanno… e così via. Più formalmente questo tipo di conoscenza è definito in letteratura come “conoscenza comune1.

In altre parole non mi basta sapere di conoscere i proprietari di ogni moneta ma devo anche contare sul fatto che gli altri siano d’accordo con me, e sapere che io sono d’accordo con loro. Se si riesce ad arrivare ad una tale situazione allora è possibile fare in modo che facciamo tutti riferimento alla stessa storia (delle transazioni) risolvendo quindi il problema di una discordanza su chi è il proprietario di cosa, ma senza fidarsi di nessuno in particolare. Questo è il problema principale che per la prima volta Bitcoin ha risolto in maniera brillante senza dover fare affidamento ad una autorità centrale di cui fidarsi, come normalmente era sempre avvenuto.

L’innovazione chiave per risolvere questa problematica è stata quella di poter dimostrare quante operazioni si sono impiegate per produrre un certo risultato, altrimenti definito come “dimostrazione di lavoro2. In un sistema che implementa questa caratteristica è possibile avere una archivio di transazioni che dimostra avere alle spalle una certa mole di lavoro. A quel punto è sufficiente che la maggior parte degli utenti del sistema accettino come “buono” l’archivio che ha alle spalle il numero maggiore di calcoli che sono stati fatti su di esso. Questo permette di conoscere quale sia il “libro mastro”, e possiamo essere sicuri che è lo stesso usato da tutti gli altri.

Ed in definitiva questo permette di avere una prova di proprietà senza una autorità centrale.

Avendo chiaro questo concetto, una buona parte della complessità di Bitcoin comincia a diventare accessibile.

In un articolo precedente si era accennato al fatto che dei Bitcoin vengono dati in premio a chi riesce a risolvere un particolare problema matematico. Questo problema non serve solo per permettere una distribuzione iniziale delle monete, anzi, non è nemmeno il suo scopo principale. Il suo obiettivo principale invece è quello di dimostrare che un certo elenco di transazioni porta con se il maggior numero di calcoli eseguiti. Quindi se noi cominciamo a lavorare sull’ultima soluzione conosciuta (che ha un elenco di transazioni fino ad un preciso punto nel tempo) partiamo da una documentazione che al momento ha il numero maggiore di calcoli eseguiti su di essa. Il protocollo di Bitcoin specifica che è necessario utilizzare la più “grande” (cioè quella con più calcoli alle spalle), ma come si vedrà questo è nel nostro stesso interesse.

Se pubblichiamo un “aggiornamento”, cioè l’ultimo elenco delle transazioni più quelle più recenti, assieme ad una soluzione allora gli altri utenti sanno che il nostro “libro mastro” porta con se tutto l’elenco dei conti precedenti fino all’ultima soluzione più tutti quelli che abbiamo fatto noi. Di conseguenza se vogliamo reclamare il bonus (in bitcoin) per l’ultima soluzione è bene partire dal “libro mastro” che contiene l’ultima soluzione.

Vediamo quindi di riepilogare e sintetizzare una semplificazione di quello che accade in una rete bitcoin:

  1. Quando un utente vuole trasferire i propri bitcoin a qualcun altro trasmette a tutti un messaggio che contiene la transazione, cioè quanti dei propri bitcoin vanno a chi, e lo firma con la propria chiave privata.
  2. Quando un utente riceve un messaggio che identifica un trasferimento di proprietà (una transazione) come prima cosa verifica che la firma sia valida (vedere l’articolo precedente3 in proposito) e che l’indirizzo di colui che “spende” i bitcoin possieda fondi a sufficienza, cosa che può verificare sul “libro mastro”. Se le verifiche sono positive allora mantiene la transazione e la distribuisce a tutti i suoi contatti.
  3. Gli utenti che vogliono reclamare il premio per una soluzione (cioè i “minatori”) raggruppano tutte le transazioni che possiedono (cioè le nuove più quelle dell’ultimo libro mastro confermato) e creano un problema matematico unico per questo insieme. Poi cominciano a cercare una soluzione ad esso.
  4. Quando qualcuno trova una soluzione la distribuisce a tutti i suoi contatti assieme all’insieme delle transazioni a lui conosciute (cioè l’ultima versione del “libro mastro”). Come per le singole transazioni, ognuno di coloro che la riceve la verifica e, se valida, la distribuisce a tutti gli altri.
  5. I minatori che ricevono una nuova soluzione valida interrompono i calcoli che stavano facendo e prendono l’ultima versione del “libro mastro” come nuovo punto di partenza per cercare una nuova soluzione. Come definito nel punto 3) aggiungono ad esso tutte le nuove transazioni di cui sono a conoscenza e costruiscono un nuovo unico problema matematico da risolvere.

Nella pratica può succedere che a volte diversi utenti troveranno simultaneamente una soluzione e che queste si propaghino all’interno delle varie parti della rete a diverse velocità. I minatori dovranno quindi tenere tutte le ultime versioni dei “libri mastri” in attesa che uno di questi diventi più “lungo” (cioè porti con se un numero di conti maggiore) e quindi definitivo. Dal canto loro gli utenti invece aspetteranno un certo numero di nuove soluzioni dopo una certa transazione è stata accettata per essere sicuri che confermata a sufficienza.

Traducendo i concetti generali sopra esposti nel lessico tipico di Bitcoin avremmo che una nuova soluzione, con il suo blocco di transazioni vecchie e nuove, viene chiamato “blocco”. Il “libro mastro”, cioè tutto l’elenco delle transazioni, con tutte le soluzioni intermedie che dimostrano come sono costruite una sull’altra, viene chiamato “catena dei blocchi” perchè ogni blocco si collega al “libro mastro” precedente, formando quindi una catena.

Ci sono ancora molti dettagli da definire, cosa che vedremo di fare in articoli successivi, ma questo dovrebbe far capire i concetti generali del funzionamento della rete Bitcoin ed alcuni degli elementi fondamentali in gioco.

Dusty


Fonte: traduzione libera dell’articolo Bitcoin overview: proofs and common knowledge

Note:

Bitcoin. Come funziona? (I)

Il funzionamento di Bitcoin (I) — concetti di base

di Dusty, Il Portico Dipinto (15/06/2011)
Questo è il primo di una serie di articoli che mi propongo di preparare per spiegare il funzionamento di Bitcoin da un punto di vista più tecnico.

Il prerequisito per comprenderne il funzionamento è conoscere le basi della crittografia a chiave pubblica per cui ne verranno qui forniti i concetti principali.

Come prima cosa è importante capire una delle cose fondamentali: nella rete Bitcoin tutto quello che avviene è pubblico e non crittografato. In particolare il sistema funziona, e funziona bene, senza una entità centrale, proprio perchè tutte le transazioni che avvengono sono pubbliche. La privacy deriva dal fatto che le entità che effettuano le transazioni sono definite per mezzo di indirizzi Bitcoin, che sono composti da una particolare sequenza di numeri e lettere (a titolo di esempio l’indirizzo per fare donazioni a questo sito: 1DHoxhPDnLNyYtpPpG4JMenF7yLPye78Mf). Cioè un sistema del tutto analogo al funzionamento di alcune banche svizzere che utiilzzano conti “cifrati”. In realtà i conti non sono cifrati ma sono definiti semplicemente dal loro numero, senza rendere pubblico chi ne è il proprietario.

Nel momento in cui si stabilisce la proprietà di un certo indirizzo (ad esempio perchè reso pubblico, come avvenuto poco sopra) è possibile ricostruire tutte le sue transazioni, ad esempio attraverso il sito blockexplorer.com. Di conseguenza più che di anonimato dovremmo parlare di pseudoanonimato.

Il motivo per cui è importante conoscere le basi della crittografia a chiave pubblica è che alcune delle sue caratteristiche sono componenti di base in Bitcoin, ma vengono sfruttate per garantire la correttezza delle operazioni e dell’integrità del sistema, non per occultarne il contenuto.

I protocolli definiti sono stati verificati con cura dai più grandi esperti di crittografia e dalla grande comunità degli hacker di tutto il pianeta.

Primo concetto: firma digitale a chiave pubblica

In un mondo digitale come è possibile firmare visto che chiunque può mettere qualunque dato su di un dispositivo di memorizzazione?

Come una firma convenzionale, una firma digitale per essere tale deve soddisfare le seguenti caratteristiche:

  1. Prova d’identità: solo io posso produrre la mia firma, e quindi vedere la mia firma equivale ad una prova che avvallo quanto firmato.
  2. Non ripudiabilità: dopo aver firmato non posso più negare di averlo fatto.
  3. Non trasferibilità: la firma su di un documento non può essere messa su di un altro documento facendo finta che io abbia firmato quest’ultimo.

Questi tre obiettivi sono perfettamente raggiungibili in un mondo digitale, e, aggiungerei, anche in una maniera molto più sicura di quella convenzionale. Una firma tradizionale è relativamente facile da falsificare mentre una firma digitale è praticamente impossibile.

Vediamo ora come è possibile avere questo risultato: come prima cosa si generano una coppia di chiavi, una pubblica ed una privata. La chiave privata va mantenuta segreta, mentre si comunica a tutti la chiave pubblica. Si utilizza poi un algoritmo a chiave pubblica che fa parte di una determinata infrastruttura a chiave pubblica (PKI)1 che prende in input:

  1. Un messaggio che vogliamo firmare (chiamiamolo da ora in poi M1)
  2. La propria chiave privata, che chiameremo SK1

e fornisce in output una firma, che chiameremo SIG1. Le infrastrutture a chiave pubblica sono progettate in modo che il loro uso e la generazione della firma sia semplice e rapido.

A questo punto, se qualcuno vuole verificare se abbiamo veramente firmato il messaggio M1 deve solo verificare che esista una certa relazione matematica (che dipende dal tipo di algoritmo utilizzato) tra esso, la mia chiave pubblica (che appunto, è nota a tutti) e la mia firma SIG1. Anche questa operazione viene effettuata in maniera rapida e completamente automatico dalla PKI.

Cosa ci assicura che questo procedimento soddisfa le tre caratteristiche della firma di cui sopra?

Le prime due sono garantite dal fatto che è praticamente impossibile riuscire a produrre una firma SIG1 senza conoscere la chiave privata SK1. Allo stesso modo, dedurre la chiave privata SK1 dalla chiave pubblica sarebbe così dispendioso da un punto di vista computazionale che anche avendo la possibilità di utilizzare tutti i computer del mondo per questa operazione sarebbero necessari migliaia di anni di calcoli.

Di conseguenza il fatto di poter rapidamente calcolare SIG1 è la prova che possediamo la chiave privata corrispondente alla chiave pubblica e che abbiamo deciso di utilizzarla per firmare il documento M1.

Lo stesso procedimento soddisfa il criterio 3 (non trasferibilità) perchè la firma SIG1 è funzione del messaggio stesso che stiamo firmando. Questo implica che essa cambia per ogni messaggio che firmiamo e quindi la firma SIG1 del documento M1 non è valida per un differente documento M2 in quanto la relazione matematica prima indicata non sarà verificata per {M2, SIG1, chiave pubblica} ma solo per {M1, SIG1, chiave pubblica}.

Per poter verificare una firma dovremmo produrre una firma SIG2 tale che la relazione matematica {M2, SIG2, chiave pubblica} stia in piedi, ma questo è appunto impossibile per chiunque a meno di conoscere la mia chiave privata.

Evitiamo di entrare nel dettaglio dello specifico algoritmo che viene utlizzato per non appesantire la spiegazione ed anche perchè per poterne capire il funzionamento è necessario avere conoscenze matematiche (algebriche per la precisione) abbastanza avanzate. Come accenno possiamo dire questi algoritmi sfruttano le proprietà della aritmetica modulare2 e dei numeri primi. Possiamo aggiungere che per implementare una architettura a chiave pubblica si utilizza una classe di funzioni conosciuta come “funzioni unidirezionali3 4. Tali funzioni hanno queste caratteristiche:

  • Dato x, è facile calcolare f(x)
  • Dato un valore V uguale ad f(x) con x sconosciuto, è difficile trovare un x tale che f(x) = V. Detto in termini matematici è difficile invertire f.
  • Data una particolare informazione riguardo f (nel nostro caso rappresentata dalla chiave privata), diventa invece “facile” invertire f.

Quale è il ruolo giocato dalle firme a chiave pubblica in Bitcoin?

Vengono utilizzate per dimostrare alla rete di essere i proprietari di un indirizzo A1 (A1 corrisponde in effetti alla chiave pubblica) ha realmente autorizzato il trasferimento di una certa quantità di moneta a dei nuovi indirizzi. Tutti gli altri nodi della rete saranno in grado di verificare che tale trasferimento è stato autorizzato dal vero proprietario controllando la relazione matematica prima descritta tra la chiave pubblica di A1, il messaggio che descrive il trasferimento e la firma su quest’ultimo. E se i conti non tornano allora tutti i nodi, seguendo le specifiche del protocollo di Bitcoin, ignoreranno il trasferimento e non lo trasmetteranno agli altri nodi della rete, di fatto ignorandolo.

Secondo concetto: funzioni hash crittografiche

In crittografia una funzione hash5 è una funzione che prende un input di qualunque dimensione e calcola in maniera deterministica un output di lunghezza fissa basato sull’input, ma tale che la relazione tra l’input e l’output sembri “casuale”. Inoltre deve essere impossibile immaginare quale sarà il risultato dell’output o avere una qualche idea della sua caratteristica senza eseguire tutti i passi della funzione stessa.

Per dire la cosa in maniera più semplice possiamo chiamare l’output della funzione hash un “sunto” dell’input (chiamato preimage in inglese), e viene comunemente denominato anche “impronta digitale” (digest in inglese).

Un esempio (semplice, non crittografico) di funzione hash con cui si ha familiarità è quello del codice fiscale: viene costruito sulla base dei nostri dati personali. Si hanno conflitti, cioè due codici fiscali uguali, quando due persone con un nome e cognome simili sono nati nella stessa città e nello stesso giorno.

In crittografia le funzioni hash devono avere caratteristiche molto più forti. Deve essere veramente difficile riuscire a trovare una relazione tra classi di input e classi di output senza dover eseguire la funzione nella sua interezza per ogni input, cioè senza “scorciatoie”. Una conseguenza è che con una funzione hash crittografica piccoli cambiamenti dell’input non devono portare a piccoli cambiamenti dell’output. Al contrario sono progettate in modo che anche minime differenza nell’input cambiano in maniera radicale il risultato. Da un punto di vista più formale le funzioni hash crittografiche devono presentare queste caratteristiche:

  1. Dato un certo digest deve essere difficile trovare un input che dato in pasto alla funzione restituisce quel digest. Questa caratteristica viene chiamata “[first] preimage resistance6. E’ importante notare che dato che l’input (preimage) può essere arbirtrario e di qualunque lunghezza mentre l’ouput (digest, o hash) ha dimensione prefissata ci sono un numero infinito di input che danno un tale output.
  2. Dato un certo input è difficile trovare un altro input che mi fa ottenere lo stesso digest. Questa caratteristica viene definita “second preimage resistance”.
  3. In genere è difficile trovare diversi input che producono lo stesso digest. Questi casi vengono definiti “collisioni”, e questa caratteristica viene quindi definita come “resistenza alle collisioni”.

Nota bene: da un punto di vista crittografico si definisce “difficile” un processo il cui numero di passi per essere eseguito è di ordine esponenziale nella dimensione dell’input. “Facile” quando invece il numero dei passi è di ordine polinomiale.

Come esercizio per il lettore verificare come il calcolo per costruire il proprio codice fiscale non soddisfi nessuno dei tre requisiti appena descritti 🙂

Uno degli usi delle funzioni hash è quello di oscurare alcuni dati in modo da limitare l’uso che se ne può fare. Ad esempio la gran parte dei siti web (questo compreso) non memorizza la password degli utenti nel suo database, ma un “hash” della password. In questo modo possono verificare lo stesso se un utente ha la password corretta ma se qualcuno riesce ad accedere al database non riesce a conoscere le password degli utenti ma solo i loro hash, inutili allo scopo di carpire le credenziali.

Nel mondo di Bitcoin è qui che entrano in gioco i “miner”: i bitcoin, cioè le monete che vengono scambiate nella rete, vengono generate di continuo e date in proprietà a chi riesce a risolvere un particolare problema matematico. Questo problema può essere definito come chi riesce a risolvere il primo problema del “preimage resistance” descritto poco sopra.

Nella fattispecie, invece di trovare un input che corrisponda perfettamente ad un certo hash, l’obiettivo è quello di trovare un risultato “parziale”, cioè un risultato che soddisfi solo in parte un particolare hash, ad esempio solo su di un sottoinsieme dei caratteri che lo compongono. Maggiore è il numero dei caratteri che deve soddisfare il requisito, maggiore è la difficoltà a trovare il particolare input. E date le caratteristiche delle funzioni hash, l’unico modo per risolvere il problema è fare tutte le prove possibili.

Qui entra quindi in gioco uno dei parametri più importanti per i miner e cioè il numero di calcoli che si riesce ad effettuare per unità di tempo: più è alto, più velocemente si troverà una soluzione e più velocemente quindi si guadagnerà il premio in palio.

Ma per ora è tutto perchè abbiamo messo fin troppa carne al fuoco: questi sono i requisiti per capire il resto del protocollo, che approfondiremo in seguito.

Dusty


Fonte: traduzione libera dell’articolo Explaining – not setting – Bitcoin straight

Note: