• Crittografia e algoritmo ECDSA
  
  • Generazione di una chiave pubblica da una chiave privata
  • Firma digitale di un messaggio mediante una chiave privata
  • Verifica della firma digitale mediante la chiave pubblica
  • Esempio pratico di firma di un messaggio e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1
  • Libreria micro_ecdsa
  • Esempio pratico di firma di una transazione bitcoin

Crittografia e algoritmo ECDSA

La crittografia viene utilizzata per rendere possibili uno dei due seguenti scenari:

1.   A vuole mandare un messaggio segreto a B, in modo che solo B possa leggerne il contenuto (A deve codificare un messaggio mediante una chiave pubblicata da B e quindi nota a tutti, inviarlo a B che lo decodifica mediante la chiave privata che "inverte" l'azione di quella determinata chiave pubblica; in tutto questo processo il messaggio rimane segreto al resto del mondo)

2.   A  vuole inviare un messaggio pubblico a B; poichè il messaggio è pubblico A deve tutelare se stesso (e B) dal fatto che qualcun altro si interponga tra A e B e possa modificare il nome del mittente del messaggio o qualunque altra parte del messaggio stesso (A firma il messaggio con la sua chiave privata, lo invia a B che verifica a sua volta con la chiave pubblica relativa che il messaggio sia stato effettivamente firmato da chi possiede la chiave privata relativa e non sia stato modificato, in tutto questo processo il messaggio è sempre visibile al resto del mondo)

Nel sistema Bitcoin i messaggi si chiamano transazioni (perchè spostano del valore - rappresentato dalla moneta Bitcoin - da un utente a un altro). Quindi d'ora in poi considereremo i termini "messaggi" e "transazioni" come sinonimi.   Poichè tutte queste transazioni devono essere pubbliche, la crittografia nel sistema Bitcoin viene utilizzata per rispondere alle esigenze evidenziate nello scenario 2, cioè viene utilizzata per certificare di fronte a tutto il mondo che una transazione sia stata effettivamente effettuata dall'autore dichiarato nel messaggio e che la transazione non sia stata manomessa in alcuna sua parte.

Il metodo crittografico scelto per certificare le transazioni nel mondo dei Bitcoin si basa su un algoritmo di firma digitale che lavora con curve ellittiche detto ECDSA (Elliptic Curve Digital Signature Algorithm).

Le curve ellittiche entrano in scena nelle seguenti tre situazioni:

•   GENERAZIONE DI UNA CHIAVE PUBBLICA A PARTIRE DA UNA CHIAVE PRIVATA: quando si genera un indirizzo di un portafoglio; l'algebra delle curve ellittiche è alla base del meccanismo che permette di ricavare da una chiave privata una chiave pubblica; la chiave pubblica viene poi trasformata con un ulteriore passaggio (vedi http://gobittest.appspot.com/Address) in un indirizzo Bitcoin

•   FIRMA DIGITALE DI UNA TRANSAZIONE/MESSAGGIO CON LA CHIAVE PRIVATA: quando A deve effettuare un pagamento; A deve firmare mediante la propria chiave privata la transazione/messaggio di pagamento, per certificare in modo visibile a tutti la validità di questo atto di pagamento; la firma di A è necessaria per muovere dei fondi da un certo indirizzo, questa firma è ottenuta applicando in modo appropriato la chiave privata alla transazione (o meglio: al doppio hash della transazione) da eseguire

•   VERIFICA DELLA FIRMA DIGITALE MEDIANTE LA CHIAVE PUBBLICA: quando un nodo della rete, addetto alla convalida delle transazioni, alla trasmissione di quest'ultime alla rete e alla loro registrazione in un registro pubblico detto "block chain", deve verificare mediante la chiave pubblica che la transazione sia stata firmata effettivamente dalla chiave privata corrispondente (pur senza conoscerla) e che la transazione non sia stata modificata in alcuna sua parte



Generazione di una chiave pubblica a partire da una chiave privata


Si fissa un punto G della curva (che nel caso della secp256k1 è stato fissato dalla SEC), si sceglie un numero casuale d tra 1 e n - 1 (dove n è l'ordine di G), e si ottiene così la chiave pubblica P = d*G.

Facciamo un esempio nel caso semplificato di

E(F_11 )={(2,2),(2,-2),(3,1),(3,-1),(4,4),(4,-4),(5,0),(6,5),(6,-5),(7,3),(7,-3)}  ∪ {O}

Scegliamo un punto base. Proviamo con A = (2,2)

Osserviamo che o(A) = 4  (l'ordine di A) infatti

A+A=2*A=D    (vedi calcolo effettuato in precedenza,  D(5,0) )

A+A+A=3*A=2*A+A=D+A=A'



A+A+A+A= 4*A = 3*A+A = A'+A = O

Poichè A ha ordine un numero non primo, non è un buon candidato per essere scelto come punto base. (NB: in questo caso o(A) = 4, quindi il cofattore o(E) : o(A) sarebbe uguale a 3 )

Proviamo con B = (3,1). Si può verificare che esso ha periodo 12, cioè B genera tutto E(F_11) (<B> = E(F_11)) (NB: in questo caso il cofattore è 1, così come succede per la curva secp256k1, da ciò si deduce che E(F_11) è un gruppo ciclico, anche se non ha un numero primo di elementi).

Quindi:

E = E(F_11)  

G (il punto base della curva) = B

d (la chiave privata) = 4 (numero scelto a caso tra 1 e 11)

P (la chiave pubblica corrispondente a d=4) = 4*B = 2*(2*B) = (3,-1) .

---

Firma digitale di un messaggio mediante una chiave privata




Che cos'è una firma? E' una coppia di numeri r , s  (entrambi di lunghezza max 256 bit, minori di n) che si ottengono a partire da:

il messaggio m** , la chiave privata d, un numero casuale k

**ciò che si firma realmente non è il messaggio originale, ma una sua "impronta digitale" (detta "message digest", una stringa di 256 bit), impronta che è il risultato di un doppio hash del messaggio originale; nel caso particolare in cui si firma non un messaggio qualunque ma una transazione è da sottolineare come si effettua il doppio sha256 della transazione quando essa è ancora in una forma incompleta e non definitiva (è chiaro che nel momento in cui si firma una transazione la firma stessa non può essere già presente nella transazione stessa! Quindi a rigore in quel caso non si firma neanche tutto il messaggio, messaggio che però deve alla fine contenere anche la firma come sua parte essenziale --> a sottolineare la natura "spuria" della firma rispetto al resto della transazione è recentemente intervenuto il soft fork "segregated witness" (firma separata), dove di fatto la firma viene considerata una parte a se stante della transazione ed è trattata in modo particolare.



Osservazioni:

tutte le operazioni (a parte il passaggio 2) si fanno sugli scalari, quindi si lavora sempre modulo n (non p!)

r è  la coordinata x di un punto del tutto casuale della curva che si ottiene moltiplicando G per uno scalare k generato al momento (scalare che si può vedere come un'altra chiave privata "usa e getta" generata al volo per l'occasione); r è la prima parte della firma

s è ottenuto a partire dalla coordinata r che viene moltiplicata per la chiave privata d; a questo prodotto viene poi aggiunta l'informazione e che dipende dal messaggio m (e = sha256(sha256(m))); il tutto è moltiplicato per l'inverso di k modulo n;  

s è ottenuto quindi a partire da r, per mezzo del messaggio m e della chiave privata d  
la verifica consiste nel procedimento inverso:  si parte da s e si ricostruisce r usando il messaggio m e la chiave pubblica P corrispondente alla chiave privata d (nella verifica non si utilizza mai nè la chiave privata d nè il numero casuale k, che devono rimanere sconosciuti!)


Nota bene:

firmare due transazioni con lo stesso numero k casuale (che produce quindi lo stesso valore di r) rende immediatamente ricavabile dalla chiave pubblica la chiave privata: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
problemi legati a cattive firme: https://bitcointalk.org/index.php?topic=271486.msg2907468#msg2907468

---

Verifica della firma digitale mediante la chiave pubblica


VERIFICA DELLA FIRMA DIGITALE MEDIANTE LA CHIAVE PUBBLICA


------------------------------------------------------------------------------------------------------------
Dimostriamo perchè questa verifica è corretta:

Notiamo innanzitutto che k = u1+u2*d, infatti:

k = s^-1 * (e + r*d)  (vedi punto 4 dell'algoritmo di firma)
  = s^-1*e + s^-1 * r*d = u1 + u2*d  mod n  (ricordiamo che   u1=s^-1*e ,  u2=s^-1*r )

Quindi X = u1*G + u2*P = u1*G + u2*d*G = (u1+u2*d)*G = k*G = X1  (ricordiamo che P = d*G ,  X1 = k*G),     ovvero X = X1
-------------------------------------------------------------------------------------------------------------

Nota bene: chi verifica non calcola mai esplicitamente nè k nè d, queste due informazioni rimangono sempre ignote;
chi verifica spezza il percorso che lo porta a X in due parti, cioè decompone k che non conosce in due parti:  k = u1 + u2*d  (il verificatore calcola solo u1 e u2, non conosce d e quindi nemmeno k!)

u1 = s^-1*e (termine che usa il contributo del messaggio e serve  per muoversi dal generatore G verso X)
u2 = s^-1 * r (questa parte serve per muoversi da P invece che da G sempre per raggiungere X; in questo modo il risultato corretto è ottenuto pur non conoscendo la chiave privata d)

Il verificatore grazie a s, che condensa diverse informazioni, riesce a determinare i seguenti due punti,
                                                           A = u1*G    e    B = u2*P
la somma di questi due punti deve dare finalmente X

Alla fine si ottiene quindi che il verificatore ha ricostruito con le informazioni in suo possesso l'identità del punto X che coincide con il punto X1 da cui è partito colui che ha fatto la firma, quindi x0 = x1  ( v = r   mod n )

Riassumendo:

chi fa la firma determina un punto X casuale e fornisce pubblicamente la posizione di X (prima parte della firma), il messaggio, la chiave pubblica e un valore s (seconda parte della firma) che dipende dalla posizione di X, dal messaggio e dalla chiave privata d

chi verifica l'autenticità del messaggio, verifica se, partendo dalla seconda parte della firma s, riesce a invertire il processo per riottenere la prima parte della firma r (che corrisponde alla posizione di X, già nota); per invertire questo processo deve utilizzare due informazioni base: il messaggio m e la chiave pubblica P.



Note finali:

1) quando si firma un messaggio vero e proprio (non una transazione) con un client bitcoin tipo Bitcoin Core viene richiesto esplicitamente di inserire l'indirizzo di chi sta firmando. Bitcoin Core infatti provvede a recuperare la chiave privata associata all'indirizzo in automatico (NB: è possibile firmare solo con un indirizzo di cui si possiede la chiave privata!).
Anche nel caso della verifica, però, viene richiesto solo l'indirizzo, non la chiave pubblica. Ma come è possibile recuperare la chiave pubblica dall'indirizzo? In generale non è possibile. Però nel caso in cui si abbiano a disposizione, oltre all'indirizzo, la firma e il messaggio stesso allora si può ricostruire la chiave pubblica, infatti:

               X = u1*G + u2*P -->  X = s^-1*e*G + s^-1*r*P  

in quest'ultima equazione il destinatario del messaggio che deve effettuare la verifica ha a disposizione tutti i valori tranne uno,  P, che costituisce quindi l'incognita dell'equazione e che si ricava quindi in funzione degli altri dati:

s*X = e*G + r*P
r*P = s*X - e*G
                                P = r^-1 (s*X - e*G)

A questo punto chi verifica si limita a trasformare la chiave pubblica P nell'indirizzo corrispondente e a controllare infine se quest'ultimo coincide con l'indirizzo che gli è stato trasmesso.

Quindi nel caso di un messaggio normale firmato con una chiave bitcoin la verifica non consiste più nel ricavare r a partire da s e da P (oltre che da m), ma invece consiste nel ricavare la chiave pubblica P dalla firma r,s (e dal messaggio m) e nel confrontare quindi l'indirizzo che P genera con quello inviato in chiaro dal firmatario.

2) se (r,s) è una firma valida per il messaggio m, lo è anche (r,-s)  (sostanzialmente il verificatore che parte da -s trova -X1, ma due punti opposti X1 e -X1 hanno sempre la stessa ascissa, quindi anche da -s si riottene sempre r).

Questo fatto consentiva, fino a qualche tempo fa, di prendere una transazione che arrivava nella mempool (quindi una transazione non ancora confermata) e modificare il segno di s. Questa modifica non cambiava di una virgola address di partenza, importo e address di arrivo della transazione, ma provocava un cambio del TXID (cioè del codice identificativo della transazione), che è un hash della transazione intera, firma compresa. In questo caso si parla di "Transaction Malleability".

Bitcoin Core dalla versione 0.11.1 non consente più questa flessibilità che poteva portare problemi:


quindi all'algoritmo della firma, per precisione, va aggiunto adesso un ulteriore passaggio:


le versioni più recenti di Bitcoin Core non propagano più quindi transazioni nelle quali le firme presentano una s maggiore di (n+1)/2.

---

Esempio pratico di firma e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1

Addizione tra 2 punti in E(F_11): esempio


Vediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.

Proviamo tutti i casi possibili:

x   x^3+7   x^3+7 mod 11    Sqrt(x^3+7) mod 11   
0   7                   7      
1   8                   8      
2   15                   4                     2 o 9        2 o -2   --> (2,2), (2,-2)
3   34                   1                    1 o 10      1 o -1  -->  (3,1), (3, -1)
4   71                   5                    4 o 7        4 o -4  -->  (4,4),(4,-4)        
5   132                   0                        0               0      -->  (5,0)
6   223                   3                    5 o 6        5 o -5   -->  (6,5),(6,-5)
7   350                   9                    3 o 8        3 o -3   --> (7,3),(7,-3)
8   519                   2      
9   736                  10      
10   1007                  6      

Abbiamo quindi trovato che
 
E(F_11 )={(2,2),(2,-2),(3,1),(3,-1),(4,4),(4,-4),(5,0),(6,5),(6,-5),(7,3),(7,-3)}  ∪{O}

Si noti che in questo caso particolare l'ordine del gruppo E(F_11) è 12 ed è superiore al numero degli elementi di F_11, mentre con la curva secp256k1 l'ordine di E(K) è minore (seppur dello stesso ordine di grandezza) del numero degli elementi di K.  

Viene comunque rispettata la stima di Hasse:    |#E (Fp) - (p + 1)| < 2rad(p)
infatti                                                                                      
                                                                                     |12-12|<2*sqrt(11)

Visualizzazione nel piano cartesiano di E(F_11 ):




Si noti come E(F_11) non costituisca visivamente un sottoinsieme di E(R), poichè bisogna tenere conto anche del modulo 11.

Nel grafico si è scelto di rappresentare gli 11 valori possibili per la coordinata y tra -5 e +6 anzichè tra 0 e 10 per mantenere visivamente la simmetria rispetto all'asse x. Si noti come questo insieme di punti non costituisca affatto un sottoinsieme dei punti della curva a coefficienti reali che soddisfa la stessa equazione; infatti il campo di "gioco" adesso è costituito da una griglia di punti a coordinate intere (11 valori possibili per le x, 11 per le y), e ogni volta che il calcolo di x^3+7 fa "sforare" una coordinata da un lato del quadrato si ricomincia dal lato opposto - questo vuol dire lavorare in modulo 11.

Da questo grafico si evince inoltre come l'operazione di "addizione" tra punti perda il significato geometrico originale in questa situazione (non ci sono curve con secanti e tangenti nel senso classico di questi termini), anche se sorprendemente l'operazione algebrica sulle coordinate determina ancora una struttura di gruppo per l'insieme E(F_11)

Addizione tra 2 punti in E(F_11)

A=(2,2)  B=(3,1)  A+B = ?
 


Quindi A+B=F

In questo caso particolare il risultato era facilmente prevedibile per via geometrica, poichè per passare da A, B, F' e F  non si  "rimbalza" mai sui lati di questo particolare biliardo quadrato.




Ma se volessimo addizionare A e F, cosa otterremmo?
A=(2,2) e F=(7,3);  A+F=?



(La pendenza sarebbe 1:5, cioè l'inverso di 5 che in F_11 corrisponde a 9 (poichè 9*5=45=1 modulo 11)

Quindi A+F=E'



Come si può notare, in questo particolare biliardo se si tocca un lato si riparte dalla parte opposta (oppure se preferite potete pensare di stare avvolgendo uno spago intorno a un rocchetto a forma di ciambella, con "pendenza" del filo costante uguale a quella del tratto iniziale AF, e lo scopo è di continuare così fino a intercettare un altro punto del gruppo che si trova sulla superficie della ciambella. A priori non è noto quanti avvolgimenti (diagonali) bisogna fare intorno al rocchetto prima di raggiungere un altro punto, in questo caso è bastato solo 1 avvolgimento.) E' proprio il tipo di relazione non banale tra il punto di partenza e quello di arrivo (pur essendo nota la "direzione" iniziale) a rendere crittograficamente interessanti le curve ellittiche.


Infine calcoliamo un "multiplo" di un punto, per esempio 2*A, utilizzando le formule appropriate:

A=(2,2)      2*A=



Quindi 2*A = D.





La creazione di una chiave pubblica (individuare un punto della curva) procede proprio in questo modo: si parte da un punto G (detto generatore del gruppo), lo si moltiplica per uno scalare random d (la chiave privata) e quindi si ottiene la chiave pubblica d*G (un punto della curva). Pur essendo noti a tutti sia il punto G che la chiave pubblica d*G, è computazionalmente intrattabile il problema di ricavare il legame tra G e d*G, cioè di fatto è impossibile ricavare la chiave privata d che corrisponde al numero di volte in cui bisogna sommare G a se stesso per ottenere la chiave pubblica.

Addizione tra 2 punti in E(R): definizione


Per capire meglio la struttura di E(K) dobbiamo però definire meglio l'operazione di addizione tra punti che caratterizza questo gruppo ciclico.


Visualizziamo la curva di equazione y^2=x^3+7 (per ora lasciamo "libere" le coordinate di assumere valori reali, quindi per adesso lavoriamo in E(R)):



Cosa vuol dire "sommare" due punti A e B di questa curva?
Si definisce C := A+B il punto della curva che si ottiene nel seguente modo:
1)   si considera la terza intersezione della retta che passa per A e B con la curva (questa retta interseca quasi* sempre la curva in un terzo punto)
2)   si prende il simmetrico del punto così ottenuto rispetto all'asse x (che appartiene ancora alla curva, in quanto essa stessa è simmetrica rispetto all'asse x)



In questo modo si definisce un'operazione "somma" tra i punti della curva che dà come risultato sempre un altro punto della curva; bisogna poi verificare che questa operazione sia anche associativa (e lo è, inoltre è anche evidentemente commutativa), che esista l'elemento neutro* e che ogni elemento abbia il suo inverso. Si ha quindi che E(R)** è un gruppo abeliano (vuol dire commutativo).

Alcune note:

*se si considerano due punti simmetrici rispetto all'asse x, in quel caso la retta che li unisce è parallela all'asse y; poichè la somma di due punti deve dare come risultato sempre un altro punto del gruppo, si deve aggiungere ai punti della curva un punto O all'infinito che diventa lo zero (l'elemento neutro) di questo gruppo;  ne consegue che due punti che sono simmetrici rispetto all'asse x sono uno l'opposto dell'altro, poichè la loro somma dà O come risultato
                                          
                                                                  O=A+B




Ma per sommare invece un punto A a se stesso, come scegliere la direzione della retta passante per A?
Basta prendere la tangente alla curva proprio in A:



**una caratteristica notevole delle curve ellittiche è che anche se i valori delle coordinate appartengono a un sottocampo di R, i punti così ottenuti costituiscono ancora un gruppo utilizzando la stessa operazione somma definita in precedenza (E(K) è quindi un sottogruppo di E(R)). Nel caso di E(K), come abbiamo già visto in precedenza, esso è un gruppo ciclico (quindi abeliano) e ha inoltre un numero primo di elementi, si tratta cioè di un gruppo i cui elementi si possono tutti generare a partire da un qualsiasi suo elemento G ≠ 0:

G                              = 1*G              
G+G                          = 2*G
G+G+G                     =  3*G
G+G+G+G                 =  4*G
............
G+G+G+......+G        = (n-1)*G
G+G+G+.....+G+G    =  n*G  = 0 (che è come dire che (n-1)*G è l'opposto di G!)



L'operazione "somma", che ha in origine una costruzione puramente geometrica, si può tradurre nelle seguenti formule utilizzando la geometria analitica:




NB: giova ricordare che tutte le operazioni sopra indicate vanno fatte modulo p nel caso della curva secp256k1 poichè le coordinate in quel caso sono elementi di Fp.
Dovevo specificare che:

NB2:
se A è diverso da B, e xA = xB allora A+B = 0 (punto all'infinito), quindi in tal caso non si applica la formula della somma di due punti (semplicemente una retta verticale non ha coefficiente angolare, quindi è inutile tentare di dividere per 0)

se A = B, e yA=0 allora A+B=2A = 0 (punto all'infinito), quindi in tal caso non si applica la formula di duplicazione (questo caso può essere visto come un caso particolare del caso precedente)

Osservazione:

A e B sono opposti se e solo se A=m*G e B=(n-m)*G, in tal caso infatti A+B = m*G + (n-m)*G = n*G = zero

ma A e B sono opposti, per costruzione geometrica, anche se e solo se hanno stessa x e y opposta (o y=0)

da ciò si deduce che se m è la chiave privata relativa al punto A(x,y), allora n-m è la chiave privata relativa al punto simmetrico A'(x,-y).

Teoremi sulle curve ellittiche


Per le curve ellittiche in generale, valgono i seguenti tre teoremi:

1) Sia K un campo e supponiamo che sia data una curva ellittica E di equazione:


Sia E(K) l'insieme dei punti della curva E a coordinate in K

Allora E(K) è un sottogruppo del gruppo di tutti i possibili punti di E (dove con E possiamo pensare a E(R) con R insieme dei numeri reali)  (teorema di Poincarè, intorno al 1900)


2) Se Fp è un campo finito, allora il gruppo dei punti E(Fp) è sempre o ciclico o prodotto di due gruppi ciclici.


3) Sia E l'insieme dei punti della curva ellittica

Allora |#E (Fp) - (p + 1)|< 2rad(p)
(stima sul numero di punti di E(Fp) di Hasse, 1922)

Il primo teorema ci assicura un fatto notevole, e cioè che l'insieme dei punti di una qualsiasi curva ellittica a coordinate in un campo finito costituisce sempre un gruppo (vedremo rispetto a quale operazione di "addizione" particolare)  

Questo fatto è sensazionale, cioè se definisco un'operazione algebrica su E(R) (cioè sulla classica curva nel piano cartesiano), poi con la stessa operazione su E(K), dove K è un qualsiasi sottocampo di R, sono sicuro di trovare ancora un sottogruppo di E(R),  cioè sono sicuro ad esempio che la somma di 2 punti sulla curva a coordinate in F7 è ancora un punto a coordinate in F7 che sta sulla curva !

Il secondo teorema ci dice qualcosa di importante sulla struttura algebrica di E(Fp) (nel caso specifico della secp256k1, i punti della curva costituiscono proprio un gruppo ciclico)

Il terzo teorema ci fornisce una stima sul numero degli elementi di questo gruppo, stima che si basa sul numero degli elementi del campo delle coordinate. In sostanza esso ci dice che la differenza tra il numero n dei punti della curva e il numero p degli elementi del campo è trascurabile rispetto al numero p degli elementi del campo. Quindi dal momento che il nostro campo Fp ha p elementi, allora anche la curva E(Fp) dovrà avere un numero n di elementi che è all'incirca pari a p più o meno 2 radice di p.
 
Per l'uso crittografico però non è sufficiente la stima ma bisogna conoscere il numero esatto degli elementi (e in generale non è affatto banale riuscire a calcolare questo numero).

Nel caso della curva secp256k1 i suoi punti costituiscono un gruppo ciclico e il numero dei suoi elementi (è sempre un numero primo) è  

n=115792089237316195423570985008687907852837564279074904382605163141518161494337
  
Se confrontiamo n con p

n=115792089237316195423570985008687907852837564279074904382605163141518161494337  (numero di punti, compreso il punto all'infinito)
p=115792089237316195423570985008687907853269984665640564039457584007908834671663  (valori possibili per le coordinate dei punti)

osserviamo che il numero di punti della curva è dello stesso ordine di grandezza del numero degli elementi del campo (un po' inferiore, la differenza è dell'ordine di radice di p).
Il numero di punti è importantissimo, poichè ci fornisce il periodo del gruppo che è lo "spazio" all'interno del quale girano gli algoritmi di firma digitale. Da notare che n (come p) è rappresentabile mediante una stringa di 256 bit (da qui il nome secp256k1), misura comoda per l'implementazione nel calcolatore.
Il numero di elementi di questo gruppo è quindi all'incirca simile al numero degli elementi del campo.


A questo punto potremmo anche chiederci quanti sono i diversi valori che effettivamente sono assunti dalle coordinate x e y dei punti della curva.

Per stabilire quanti sono gli elementi x che vengono mappati in y dalla funzione:

y = sqrt(x^3 + 7)

dobbiamo prendere il numero n - 1 (il numero dei punti che hanno effettivamente le coordinate in Fp e che corrisponde quindi al massimo numero di potenziali valori distinti sia per x che per y) e dividerlo per 2 : per ogni valore effettivamente assunto dalla coordinata x di un punto infatti ci sono due possibili valori di y, y = sqrt(x^3 + 7) e y = - sqrt(x^3 + 7) , ricordiamo che l'equazione da soddisfare è y^2 = x^3 + 7 mod p, ovvero per ogni x tale che x^3 + 7 ammetta la radice quadrata in Fp ci sono 2 radici quadrate (2 valori possibili di y).

Quindi avremo (n - 1) / 2 valori distinti per x (si noti che questo equivale a dire che all'incirca poco meno della metà dei valori di Fp sono assunti dalla coordinata x dei punti della curva dal momento che p è poco più grande di n).

Per quanto riguarda invece il numero dei diversi valori assunti dalla coordinata y, bisogna prendere n - 1 e dividerlo per 3 (per dettagli sul motivo si veda questo post)

Definizioni di algebra


Un campo è un insieme di elementi (numeri) per i quali sono definite due operazioni matematiche - addizione e moltiplicazione - ciascuna delle quali applicata a ogni coppia di elementi dell'insieme dà come risultato un elemento dell'insieme stesso.

Le due operazioni devono soddisfare la proprietà associativa e commutativa, deve valere la proprietà distributiva della moltiplicazione rispetto all'addizione, infine per ogni elemento del campo deve essere presente nel campo stesso il suo opposto (un numero che sommato al primo dà come risultato il numero 0, elemento neutro dell'addizione) e per ogni elemento del campo (tranne lo 0) deve essere presente anche il suo inverso (un numero che moltiplicato al primo dà come risultato 1, l'elemento neutro della moltiplicazione). In sostanza l'esistenza degli opposti e degli inversi è un po' come dire che sono implicitamente definite anche le operazioni di sottrazione (a - b = a + (-b)) e di divisione per un elemento diverso dallo zero ( a / b = a * b^(-1)).

Per fare degli esempi, l'insieme dei numeri naturali con le usuali operazioni di addizione e moltiplicazione non è un campo, poichè nessun altro numero naturale a parte lo 0 ha il suo opposto all'interno di quell'insieme (in maniera equivalente, l'insieme dei naturali non è chiuso rispetto alla sottrazione); l'insieme dei numeri interi relativi non è un campo perchè a parte il numero 1 nessun altro numero ha il suo reciproco (non è chiuso rispetto alla divisione). L'insieme dei numeri razionali è invece un campo infinito, così come lo è l'insieme dei numeri reali.

Un'ultima osservazione sul numero di elementi che compongono il campo finito K a cui appartengono le coordinate dei punti della curva secp256k1; questo numero è
  
                                              
dove p sta a indicare che si tratta di un numero primo; per la teoria dei campi ogni campo finito deve avere un numero di elementi che sia primo (p) o potenza di un primo (p^n).
Nel caso della secp256k1, E = E(Fp), Fp è il campo delle coordinate, dove p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1, quindi siamo nel primo caso.


Un gruppo è un insieme in cui è definita una sola operazione che soddisfa la proprietà associativa, è presente l'elemento neutro rispetto a quella operazione e inoltre il gruppo contiene l'inverso di ogni suo elemento.

Quindi per quanto detto in precedenza:

1) un campo K  è un gruppo commutativo rispetto all'operazione di addizione
2)  K - {l'elemento neutro dell'addizione} è un gruppo commutativo rispetto all'operazione di moltiplicazione


Ordine di un gruppo

Sia G un gruppo. L'ordine di G è il numero (finito o infinito) degli elementi di G e si indica con o(G).

Ordine di un elemento di un gruppo

Sia G un gruppo con elemento neutro "e".  Sia "a" un elemento di G diverso da "e".
L'ordine (additivo) di a è il più piccolo intero positivo n tale che a+a+a+a+....+a = n*a= e, se tale intero n non esiste si dice che a ha ordine infinito. L'ordine di a (finito o infinito) si indica con o(a).

(l'espressione "ordine di un elemento a" deriva dal fatto che scegliere un punto a di partenza (un generatore) equivale di fatto a imporre un ordine con cui descrivere tutti gli altri elementi del gruppo: 2*a, 3*a, 4*a, 5*a, ... ordine che dipende quindi dal punto di vista particolare di a; l'insieme dei punti della curva secp256k1 costituisce un gruppo additivo, e gli scalari 2, 3, 4, 5, ... rappresentano l''ordine' con cui si ottengono i vari punti a partire da un punto particolare chiamato "g", il generatore della curva scelto dalla SEC. I 'numeri d'ordine' 2, 3, 4, 5,... corrispondono alle chiavi private dei punti/chiavi pubbliche: 2*g, 3*g, 4*g, 5*g, ...).

NB: se invece consideriamo un gruppo G moltiplicativo, allora l'ordine (moltiplicativo) di un elemento a è per analogia il più piccolo intero positivo m tale che a*a*a*...*a = a^m = e , dove 'e = 1' in questo caso è l'elemento neutro della moltiplicazione.


Dato un elemento 'a' di ordine m, l'insieme {a^0 = 1, a^1, a^2, ...., a^(m-1)} è a sua volta un sottogruppo di G.  Se esiste almeno un elemento 'a' il cui ordine coincide con l'ordine del gruppo, allora 'a' si dice generatore del gruppo, poichè il sottogruppo di G generato dalle potenze di 'a' coincide con G stesso. Notazione: <a> = G.
In questo caso G si dice gruppo ciclico. I gruppi ciclici sono tutti isomorfi a Zp (o a Z se hanno ordine infinito).

Nel caso del gruppo G dei punti della curva secp256k1, esso è un gruppo ciclico di ordine n rispetto all'operazione di addizione, e l'elemento g scelto dalla SEC si chiama appunto generatore della curva perchè <g> = G (il generato di g coincide con G e per costruzione tutti i generati sono gruppi ciclici perchè ottenuti appunto facendo il 'ciclo' su tutte le potenze/multipli di un elemento dato).

 <g> = {g, g+g, g+g+g, 4*g, 5*g, ....., (n-1)*g} = G = E(Fp)   (si noti in questo caso la notazione additiva anzichè quella moltiplicativa)

Ma n è primo, e questo fatto conferisce un'ulteriore importante proprietà algebrica a questa curva: poichè n è primo si può dedurre che ogni elemento di G escluso lo 'zero' (il punto all'infinito) genera mediante tutti i suoi multipli tutto G.

Questo fatto in generale non è vero per tutti i gruppi ciclici, ovvero un gruppo per essere ciclico deve avere almeno un elemento il cui ordine coincide con quello del gruppo stesso, ma non è detto che tutti gli altri elementi del gruppo diversi dall'elemento neutro abbiano questa proprietà.

Si può dimostrare però una relazione interessante (e banale a livello aritmetico) tra l'ordine di un gruppo finito e l'ordine possibile di un qualsiasi suo elemento (ovvero: c'è una relazione precisa tra l'ordine del gruppo finito e l'ordine di un suo qualsiasi sottogruppo).


Teorema di Lagrange

Il teorema di Lagrange è un teorema basilare nello studio dei gruppi finiti. Esso afferma che ogni sottogruppo di un gruppo finito ha ordine (cioè ha un numero di elementi) che divide l'ordine del gruppo (cioè il numero di elementi del gruppo).

|G|=|A| * |G:A|  per ogni sottogruppo A di G (|A| indica il numero di elementi di A, per G:A vedere qui  e qui ma si tratta di dettagli non importanti al fine della comprensione del nostro discorso).

NB:
Tecnicamente si dice che l'ordine del sottogruppo deve dividere l'ordine del gruppo, e il risultato del rapporto ordine del gruppo / ordine del sottogruppo (numero elementi del gruppo / numero elementi del sottogruppo) è un numero intero detto "cofattore". Se si va qui (https://en.bitcoin.it/wiki/Secp256k1 si osservi il parametro h nell'ultima riga) si vedrà che nella secp256k1 il cofattore del gruppo generato dal punto base è uguale a 1, cioè l'ordine del punto base scelto dalla SEC è esattamente uguale all'ordine di E(Fp), entrambi sono n.


Ma questo fatto non è un caso: la curva secp256k1 infatti costituisce un gruppo finito con un numero primo n di elementi, e ora grazie al teorema di Lagrange possiamo dedurre da questo fatto che

1) G è ciclico poichè un suo elemento diverso da 0 deve avere ordine maggiore di 1 (altrimenti non genera un sottogruppo) e l'unico ordine maggiore di 1 che sia anche divisore di 'n' primo è 'n' stesso.

2) l'ordine di ogni suo elemento (a parte lo 0) deve coincidere per forza con l'ordine del gruppo (che essendo primo non ha altri divisori all'infuori di se stesso), cioè è possibile generare ogni elemento del gruppo a partire da un qualsiasi altro suo elemento (elemento neutro escluso). La scelta del punto base della SEC quindi è del tutto arbitraria (qualsiasi altro punto sarebbe andato bene).

3) per ogni elemento a di G vale che a^ordine(G) = 'e'  (elemento neutro). Questo fatto è la traduzione del punto 2) e si ottiene applicando semplicemente la definizione di ordine di un elemento.

quest'ultima equazione nel caso della curva G si declina osservando che n*a = punto all'infinito per ogni a di G, nel caso del campo Fp delle sue coordinate diventa in notazione moltiplicativa a^(p-1) = 1 mod p (si vedano le prossime righe per la spiegazione, e qui per le ricadute pratiche a livello di calcoli)


Teoria dei campi finiti

Nel caso dei campi, che ripetiamo sono gruppi commutativi rispetto all'operazione di addizione e, tolto lo zero, sono anche gruppi commutativi rispetto alla moltiplicazione, è sempre bene specificare quando si parla di ordine di un elemento se si intende ordine additivo o ordine moltiplicativo.

Nel caso di Fp, il campo delle coordinate della nostra curva, l'ordine additivo di ogni elemento 'a' è p, mentre l'ordine moltiplicativo è p - 1.
Questo implica che

1) a+a+a+....+a = p*a = 0  mod p

2) a*a*a*a*...*a = a^(p-1) = 1  mod p

Dall'ultima uguaglianza si ricava anche che a^(p-2) = a^-1 mod p, ovvero si ricava un modo pratico (anche se computazionalmente oneroso) per calcolare l'inverso di ogni elemento. Per un metodo più efficiente si veda l'identità di Bezout (pagg. 43 -45, soprattutto l'esempio pratico 3.35) e l'algoritmo che implementa il tutto.

Per la teoria dei campi ogni campo finito deve avere un numero di elementi che sia primo (p) o potenza di un primo (p^n).

Se il campo ha un numero primo di elementi allora è un gruppo ciclico (rispetto all'operazione di addizione) ed è isomorfo a  Z/pZ , cioè dal punto di vista delle sue proprietà algebriche è equivalente al campo delle classi di resto modulo p. In particolare quindi il campo Fp delle coordinate della nostra curva è isomorfo a Z/pZ.  

Ma si può dimostrare anche che Fp - {0} è un gruppo ciclico rispetto all'operazione di moltiplicazione pur avendo p-1 elementi (cioè un numero pari di elementi).



Cosa vuol dire campo delle classi dei resti delle divisioni tra interi modulo p? (per una trattazione esaustiva si veda qui)

Facciamo un esempio nel caso p=5,  Z/5Z = { [ 0], [1], [2], [3], [4]}

Perchè le parentesi quadre? Perchè 3 = 8 = -2 = 28 = 23 = 33 = -7 = --- --> tutti questi numeri sono equivalenti poichè si possono scrivere nella forma  3 + 5*k  per qualche k intero, ovvero diminuiti di 3 sono tutti multipli di 5.

Quindi poichè i resti delle divisioni di tutti questi numeri per 5 sono tutti uguali a 3 si introduce la classe di equivalenza dei numeri interi per i quali i resti della divisione per 5 coincidono appunto con 3 --> { 3, 8, 13, 18, 23, 28, 33, ....., -2, -7, -12, -17, ....} = [3]  

L'insieme di tutte queste classi di equivalenza (con i resti che possono variare quindi tra 0 e 4) si indica con Z5.


addizioni: [2]+[3] = [ 0], poichè (2 + k1*5) + (3 + k2*5) = 5 + (k1+k2)* 5 = 0 + (1+k1+k2)*5  = [ 0]

analogamente (trascuro le parentesi per comodità):  3+4=2, poichè 3+4=7 e 7 equivale a 2 modulo 5.

moltiplicazioni: 2*3=1, poichè 2*3=6 e 6 equivale a 1 in questo campo.

Indice:

• Curve ellittiche: punti, coordinate, scalari
• Definizioni di algebra
• Teoremi sulle curve ellittiche
•  Addizione tra due punti:
  
  • definizione in cioè nel continuo
  • esempio in cioè nel discreto
• Crittografia e algoritmo ECDSA
  
  • Generazione di una chiave pubblica da una chiave privata
  • Firma digitale di un messaggio mediante una chiave privata
  • Verifica della firma digitale mediante la chiave pubblica
  • Esempio pratico di firma di un messaggio e verifica utilizzando l'algoritmo ECDSA applicato alla curva secp256k1
  • Libreria micro_ecdsa
  • Esempio pratico di firma di una transazione bitcoin

---

Curve ellittiche: punti, coordinate, scalari:

Vediamo una breve trattazione matematica delle curva secp256k1 (così chiamata, secondo la classicazione "Standards for Efficient Cryptography" (SEC), vedi http://www.secg.org/sec2-v2.pdf a pagina 9), la curva impiegata nel protocollo Bitcoin.

Le curve ellittiche in generale hanno equazione ,  e poco hanno a che fare con l'ellisse, nonostante il loro nome.  

In particolare la curva ellittica secp256k1 utilizzata nel mondo Bitcoin è la curva di equazione:


cioè è l'insieme dei punti P(x,y) del "piano cartesiano" le cui coordinate x e y soddisfano quell'equazione particolare.  


Le coordinate dei punti delle curve ellittiche

I valori che può assumere la coordinata x (e di conseguenza anche la coordinata y) non sono però tutti gli infiniti valori reali (come succede invece a scuola quando si studiano le rette o le parabole ) ma sono solo i valori che corrispondono a elementi di un insieme molto particolare, detto campo, che indicheremo con . Quindi quando parliamo di "piano cartesiano" intendiamo in realtà i punti (coppie di coordinate) che appartengono al prodotto cartesiano .
Anche i numeri reali costituiscono un campo, nel caso della secp256k1 "ovviamente" è un sottoinsieme finito di , ma rimane sempre un campo ("ovviamente" nel senso che applicazioni pratiche e infinito non vanno d'accordo!)

Quindi i punti della curva secp256k1 hanno come coordinate possibili solo gli elementi del campo finito .


I punti della curva secp256k1


I punti della curva costituiscono a loro volta un insieme finito (ovviamente, visto che le coordinate possibili di questi punti sono in numero finito) detto gruppo, che indicheremo con o . Per quanto detto prima è un sottoinsieme di .
Si dimostra che E(Fp) è un gruppo ciclico; inoltre il numero di elementi di questo gruppo è a sua volta un numero primo che è all'incirca simile al numero totale degli elementi del campo (ma non è uguale, sono 2 numeri primi diversi, vedi approfondimenti)


Oltre alle coordinate (campo K) e ai punti della curva (gruppo ciclico E(K)), è presente una terza tipologia di elementi, che non hanno dietro una struttura algebrica a differenza degli elementi citati finora: gli scalari.

Gli scalari

Dove intervengono gli scalari?

Esempio: quando sommiamo un punto A con se stesso 7 volte:


possiamo indicare questa somma come 7*A.
Gli scalari quindi in questo contesto sono sostanzialmente dei semplici numeri interi che servono solo come contatori e che non hanno alcuna struttura algebrica dietro.  Gli scalari in questo caso sono importantissimi però poichè è proprio su quest'ultimi che lavora in gran parte l'algoritmo di firma digitale. In sostanza gli scalari tengono conto di quanti "movimenti" abbiamo fatto nello spazio dei punti del gruppo ciclico E(K).

Le chiavi private sono esse stesse degli scalari! (mentre le chiavi pubbliche sono punti della curva).


Nel nostro caso, i punti della secp256k1 costituiscono quindi un gruppo ciclico formato da un numero primo di elementi, da ciò si ottiene che partendo da un punto qualsiasi della curva (diverso dallo 0) si possono ottenere tutti gli altri punti della curva (vedere il post 2 sulle considerazioni matematiche).

Nella secp256k1 si è deciso di partire dal punto G = (Gx, Gy):

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
      32670510020758816978083085130507043184471273380659243275938904335757337482424)

Si osservi innanzitutto che entrambe le coordinate sono minori di p=115792089237316195423570985008687907853269984665640564039457584007908834671663

Facciamo un rapido controllo per verificare che G appartenga veramente alla curva seckp256k1, ovvero che Gx^3+7-Gy^2 sia uguale a 0 modulo p:



tutto ok!

Da G è possibile raggiungere tutti gli altri punti della curva moltiplicando il punto G stesso per uno scalare qualsiasi che va da 1 a n
(n = 115792089237316195423570985008687907852837564279074904382605163141518161494337)

G                              = 1*G              
G+G                          = 2*G
G+G+G                     =  3*G
G+G+G+G                 =  4*G
............
G+G+G+......+G        = (n-1)*G
G+G+G+.....+G+G    =  n*G  = 0  

L'espressione "moltiplicare G per uno scalare s" è solo un altro modo di dire "sommare il punto base G a se stesso s volte"

s è la chiave privata che il vostro software wallet pesca random tra 1 e n-1, s*G è la chiave pubblica relativa

NB: le chiavi private "0" o "n" non sono valori consentiti nell'ECDSA, quindi se inviate bitcoin all'indirizzo che si ottiene facendo l'hash del punto all'infinito che è associato a quegli scalari (punto che per pura convenzione si rappresenta mediante le coordinate (0,0)), nessuno sarà in grado di spendere quei bitcoin, poichè la chiave privata "0" (oppure "n") nonostante matematicamente sia associata al punto all'infinito non è considerata valida per firmare le transazioni.

Non riporta la soluzione (3,17) poichè riporta già la soluzione (3,0), che è la stessa. Anche se sembra un quadrato, quella griglia di punti non forma un quadrato. Devi pensare che sia i valori delle x che i valori delle y vanno da 0 a 16. La riga y=17 è sovrapposta idealmente alla riga y=0, tipo un cilindro ( ma anche la riga verticale x=0 e la riga verticale x=17 coincidono, quindi di fatto il quadrato è come fosse una specie di ciambella )

Se noti tutte le soluzioni sono simmetriche rispetto alla linea y="8,5" poichè ad esempio y=5 e y=12 sono uno l'opposto dell'altro, cioè 12=-5, e così funziona per tutte le altre coppie tranne proprio il caso di (3,0), poichè l'opposto di 0 è ancora 0 (e ovviamente se (x,y) è una soluzione dell'equazione, lo è anche (x,-y), quindi i punti di questa curva ellittica vanno a coppie tranne il caso del punto con ordinata nulla; questo è anche il motivo per cui una chiave pubblica, che è un punto sulla curva ellittiche secp256k1, può essere rappresentato sia mediante 2 coordinate da 256 bit ciascuna, sia mediante una sola coordinata di 256 bit - la x - più il segno della y)
Poichè p è un numero primo, osserva che, fissata la x, una coordinata y è sempre pari mentre l'altra è sempre dispari; per indicare la coordinata pari si antepone il prefisso 02 alla rappresentazione esadecimale della x, per indicare la coordinata negativa si antepone lo 03 (convenzione valida solo nelle transazioni del sistema Bitcoin)

Sì ma guarda che la nuova versione, la 0.12, esce solo tra una settimana.


Il problema è capire innanzitutto per bene che cosa vuol dire "verificare una transazione" per un full node, da lì secondo me si può dedurre poi cosa può e cosa non può fare un nodo che invece ha una chain troncata.


Non penso che sia proprio come dici tu, poichè un nodo prima di propagare una qualsiasi transazione deve verificarla; se propaga una transazione che si rivela sbagliata aumenta il lavoro della rete e potrebbe anzi essere visto come un tentativo di truffa.

Io suppongo che per un full node "verificare una transazione" consista sostanzialmente nel verificare che tutti gli input che quella transazione sta cercando di spendere siano presenti nel database degli UTXO, database che un full node si è costruito per la prima volta quando ha scaricato la blockchain dal primo blocco (il database è stato aggiornato poi ad ogni nuovo blocco scaricato e verificato).
Se un nodo invece ha solo gli ultimi 10000 blocchi, la domanda è: come si è costruito il database degli UTXO?
Secondo me così come si è fidato di qualcun altro per scaricare il primo degli ultimi 10000 blocchi (non ha verificato che tutti i blocchi precedenti al quel "primo" blocco fossero validi), così probabilmente si è dovuto scaricare anche il database degli UTXO aggiornato a quel "primo" blocco; da quel momento in poi è stato in grado di aggiornare in autonomia il database degli UTXO a ogni blocco successivo.

Ma sono solo supposizioni; riporto  qui di sotto alcuni passi di "Mastering Bitcoin" dove si spiega la cosa nella speranza che qualcuno possa capire meglio di me come funziona esattamente la verifica, almeno nel caso dei full node. Per chi si intendesse di programmazione, le funzioni del codice di Bitcoin Core che si occupano della verifica delle transazioni sono CheckTransaction e  CheckInputs.

In particolare mi sfugge il seguente criterio
 
                       "A matching transaction in the pool, or in a block in the main branch, must exist"

cioè un full node deve controllare che ci siano effettivamente le transazioni d'"origine" per la transazione attuale? Mi sembra impossibile che per ogni nuova transazione ci sia bisogno di ricontrollare a ritroso potenzialmente tutti i blocchi, ma non basta controllare il database degli UTXO?

Per chi fosse interessato, la versione 0.12 di Core ha implementato delle migliorie per chi volesse far girare un quasi full node con poche risorse -> https://github.com/bitcoin/bitcoin/blob/0.12/doc/release-notes.md

Riassumendo:

1) se si raggiunge una certa soglia si può limitare il traffico in upload dovuto in gran parte alla richiesta da parte dei nuovi nodi dei blocchi storici (vecchi più di una settimana); inoltre in tal caso si disconnetterebbero i peer SVP che chiedono di impostare un loro filtro; sempre nel caso si raggiungesse la soglia, alle cosiddette "free transaction" (dette anche "priority transaction") verrebbe negato l'accesso alla mempool; altri consigli per ridurre il traffico https://github.com/bitcoin/bitcoin/blob/0.12/doc/reduce-traffic.md

2) è possibile impostare direttamente un limite alla mempool (prima si faceva indirettamente variando la soglia delle fee minime per transazione) e limitare la lunghezza e lo spazio occupato dalle catene di transazioni orfane

3) è possibile utilizzare il pruning* con il wallet attivato (anche se alcuni comandi relativi al wallet non saranno abilitati)

4) il tempo di reindex dei blocchi e della validazione dei nuovi blocchi è più che dimezzato grazie alla nuova libreria libsecp256k1 che va a sostituire OpenSSL


* Riguardo al pruning, ho cercato informazioni per capire cosa si perde rispetto a un full node che mantiene copia dell'intera blockchain. A parte ovviamente non essere in grado di fornire ai nuovi peer della rete i blocchi più vecchi, da qualche discussione sul forum tipo questa -> https://bitcointalk.org/index.php?topic=1325796.msg13551728#msg13551728 mi pare di capire che per quanto riguarda la validazione dei nuovi blocchi e il controllo e trasmissione delle transazioni non dovrebbe cambiare nulla; non riesco però a capire come sia possibile verificare la validità di una certa transazione se i suoi input sono molto vecchi, basta forse verificare che appartengano all'UTXO?  

Effetti:

con il pruning si può ridurre notevolmente lo spazio occupato,
con la nuova libreria e i parametri della mempool si possono più che dimezzare i tempi di calcolo,
con i parametri relativi al traffico si potrà gestire meglio l'occupazione di banda

Direi tutte buone notizie  

Altro scambio con il buon ghibly, tutto ok 

Ciao, vorrei solo un'informazione.

La sicurezza dei nostri bitcoin sta tutta nella sicurezza delle chiavi private che controllano le autorizzazioni delle transazioni. Quindi è essenziale, quando si usa un wallet software o hardware che sia, sapere:

1) come vengono generate queste chiavi private (godono di una sufficiente entropia? L'algoritmo che li genera quanto è sicuro?)

2) se queste chiavi sono accessibili o meno dall'esterno (quindi in generale se sono su un dispositivo scollegato dalla rete è meglio).

Rispetto a questi due punti cosa puoi dire su questo hardware wallet? Secondo te è sicuro almeno quanto Bitcoin Core (o Armory) installato su un pc offline? Come fai a fidarti della gestione delle chiavi private di questo wallet? Lo usi per cifre importanti o solo per cifre modeste?

EDIT : ho trovato maggiori informazioni su questo sito: https://techcrunch.com/2015/05/04/case-is-an-insanely-secure-hardware-bitcoin-wallet/


In sostanza se perdi il case/si rompe, rischi di non avere più i tuoi bitcoin! Non c'è un modo indipendente di spostare i bitcoin, bisogna sempre affidarsi alla compagnia (che potrebbe scomparire tra qualche anno!). O forse sono io che ho capito male?

Vendere bitcoin tramite paypal è una pessima scelta, stai scambiando un mezzo di pagamento irreversibile con uno facilmente reversibile (e soprattutto quasi sempre a favore dell'acquirente). Quindi tutti i vantaggi sono da una parte sola (e soprattutto da quella parte sta la possibilità di imbrogliarti e farla franca facilmente).

Se proprio vuoi rimanere su paypal, perlomeno scambia solo con i venditori storici del forum, quelli che hanno una montagna di feedback (ma tieni conto che questi vorranno una percentuale)

Allora: dal momento che sono passate delle settimane al 99,99% i tuoi bitcoin sono al sicuro.

Il concetto è: una transazione non è nient'altro che un messaggio che dice all'incirca:
"Io possessore dell'indirizzo A autorizzo che i btc legati all'indirizzo A siano trasferiti all'indirizzo B"
Ovviamente il punto fondamentale è che il messaggio deve essere autorizzato con la firma effettuata per mezzo della chiave privata relativa all'indirizzo A.

Alcune osservazioni:

1) quel messaggio non è immediatamente leggibile da un essere umano, ma va decodificato con appositi tool (si presenta in genere come una stringa alfanumerica di 64 caratteri in formato esadecimale (32 byte) ma possono esserci delle variazioni)

2) chiunque può comporre il messaggio di sopra, anche io che non possiedo il tuo indirizzo A posso costruire quel messaggio per girare i tuoi bitcoin verso il mio indirizzo B; ma io poi non lo posso firmare (si tratta di una " unsigned transaction", chi usa Armory o altri wallet offline per firmare le transazioni sa bene di cosa parlo), quindi se la transazione rimane non firmata non è autorizzata ed è inutile (ma se tu invece me la firmi, capisci bene che poi posso trasmetterla alla rete ed è fatta)

La morale è: se qualcuno ti sottopone una stringa e non un messaggio chiaramente comprensibile a un essere umano, firmarlo non ha senso; firmare vuol dire: "io sono d'accordo/sottoscrivo questo messaggio e quindi autorizzo quello che c'è scritto qui"

Nel tuo caso, visto che il tuo indirizzo A era inizialmente vuoto, avrebbero benissimo potuto riprendersi in breve tempo almeno i bitcoin che ti avevano pagato su quell'indirizzo (se ti avessero fatto firmare una transazione ad hoc). Ma ripeto se non è successo niente fino ad oggi non c'è pericolo (anche se spostare i btc in un altro indirizzo male non fa).

Sicuramente meglio "pruned" che niente!


La sicurezza del sistema si basa sul fatto che le transazioni che arrivano ai miner e i blocchi successivamente formati a partire da essi e reimmessi nella rete siano controllati, verificati e accettati dal maggior numero di full node possibili.

Se ci fossero anche solo 20 miner (e ti dirò che se hai letto l'articolo di Mike Hearn probabilmente siamo già in una situazione del genere) ma oltre ad essi ci fossero diverse migliaia di full node, nessun miner potrebbe imbrogliare, poichè la stragrande maggioranza della rete, avendo tutta la blockchain a disposizione, bloccherebbe sul nascere qualsiasi tentativo di double spending o qualunque altra violazione del protocollo bitcoin.

In una rete a forte prevalenza di full node il "potere" è concentrato nei nodi a scapito dei minatori, a riguardo ecco un articolo di HostFat  http://www.rischiocalcolato.it/2015/07/bitcoin-oirgini-crisi-transazioni.html :

Ricordatevi del 4 febbraio, è fra 2 giovedì

Beh, non c'è nessun rischio relativo alla sicurezza dell'indirizzo 
c'è "solo" il rischio di autorizzare una transazione che svuoti l'indirizzo con cui si sta effettuando la firma! 

E' fondamentale essere sicuri che ciò che si sta firmando non sia proprio una transazione!

Bene, così è senz'altro molto più comprensibile!
In effetti è proprio una buona idea presentare in prima battuta la firma come una funzione del software "wallet" (così fornisci subito anche 2 informazioni/precisazioni: da dove partire per firmare qualcosa e dove collocare concettualmente questa "firma", si tratta di una procedura automatizzata di un software (basata sulla crittografia) che non è quindi direttamente legata all'azione fisica di una persona come la firma fisica), se poi uno è curioso e vuole capire di più cercherà le informazioni in giro.




Ovviamente rispetto la tua opinione, forse si potrebbe chiedere a gbianchi di aggiungere un post 2 per quelli che hanno già acquisito i primi rudimenti con dei consigli per approfondimenti su argomenti di livello superiore, ma rimango della mia idea che nel primo messaggio di benvenuto la riserva frazionaria sarebbe di troppo. La riserva frazionaria è sicuramente un concetto importante, ma viene dopo. A quello aggiungerei ad esempio allora anche la questione del meccanismo dei resti (questione molto concreta che ha causato diverse perdite di fondi --> http://bitcoinedintorni.blogspot.it/2015/04/cinque-modi-di-perdere-bitcoin-con-gli.html)

Se noti nel messaggio di benvenuto ci sono soprattutto riferimenti concreti su come iniziare a utilizzare i bitcoin, l'approccio di gbianchi in quel post di benvenuto non mi sembra per nulla teorico (non ci sono particolari riferimenti ad altri aspetti economici importanti come la natura deflattiva del bitcoin ad esempio o il significato di "moneta" - da dove viene il valore del denaro - concetto che è alla base dell'idea della costruzione dei bitcoin, per non parlare di tutta la matematica che fa da sfondo al sistema con la crittografia, solo appena accennata, nè accenno alcuno alla natura p2p del sistema, che pure a lui piace tanto  ).

 

Non sono d'accordo. Sono i full node che filtrano le transazioni, le propagano fino ai miner e che in seguito controllano i blocchi e li propagano determinando quindi la blockchain. Chiaro che il lavoro dei miner è indispensabile, ma meno sono i full node, meno sicura è la rete.
Un sistema con 10 grossi miner e 5000 full node sarebbe sempre più sicuro di un sistema con 1000 miner e 20 full node.

Sì, ovviamente si tratterebbe di un hard fork (retrocompatibile con il passato, basta porre pesoA = 1 e pesoB = 0 per i blocchi vecchi)


Pensavo che a comandare fossero i full node, non i miner. Sono loro alla fine che "animano" la rete, facendovi circolare le transazioni corrette e riconoscendo o meno la validità dei vari blocchi (e stabilendo qual è la blockchain corretta).

Mi è tornata in mente questa discussione
https://bitcointalk.org/index.php?topic=976028.msg10783703#msg10783703
con picchio su come modificare il mining per rendere il sistema più decentralizzato.

L'idea di base è quella di affiancare alla soglia A classica sotto la quale deve stare l'hash del blocco da minare un'altra soglia B legata ai singoli indirizzi.

Modificare un blocco in modo che il suo hash sia sotto una certa soglia A è il task attuale che favorisce solo la potenza computazionale dei miner più attrezzati e quindi favorisce decisamente l'accentramento.

Per bilanciare questa propensione all'accentramento è necessario aggiungere una misura legata ai singoli indirizzi che distribuisca la probabilità tra i nodi della rete, diminuendo il vantaggio competitivo dei miner più grossi senza per questo rendere facile per un singolo nodo minare più blocchi consecutivi (senza intaccare insomma la sicurezza del sistema, sicurezza che si basa sul fatto che il singolo nodo è sempre più debole del resto della rete e quindi non la può ingannare, se non per un lasso di tempo brevissimo).

Quindi aggiungerei una misura di questo tipo:

la differenza tra l'indirizzo (al quale andrebbe la ricompensa nel caso il blocco fosse minato) e l'indirizzo generato dalla chiave privata costituita dall'hash del blocco precedente deve essere sotto un'altra soglia B.

Riassumendo:

soglia finale = soglia A + soglia B

Ovviamente la formula va ulteriormente perfezionata, introducendo dei pesi opportuni

soglia finale = pesoA * sogliaA + pesoB * sogliaB

Alcune osservazioni:

- aumentando il pesoB, la probabilità che un singolo nodo anche poco dotato computazionalmente possa vincere nella gara per minare il blocco aumenta (potendosi permettere una sogliaA computazionale più alta e quindi più facile da raggiungere, a patto naturalmente di avere un buon indirizzo con cui competere, una buona carta insomma con cui giocarsi la mano)

- l'indirizzo da inserire nella coinbase deve avere un output non speso da almeno x blocchi  (in sostanza ricevere una transazione bitcoin vorrebbe dire ottenere un invito a partecipare al processo di mining, spendere quel UTXO significherebbe cedere quell'invito a qualcun altro); per ovviare al fatto che un grosso miner produca una infinità di indirizzi su cui distribuire i propri bitcoin solo per aumentare le sue chance di vittoria, si potrebbe tenere conto dei bitcoin-day relativi all'UTXO, cioè anche di quanti bitcoin sono posseduti da quell'indirizzo, non solo dall'età

- nel momento in cui parte la gara per minare un nuovo blocco, anche i miner più grossi saranno limitati dal fatto di avere o meno un indirizzo che garantisca un basso valore della sogliaB (indirizzo che non può essere individuato in anticipo); qualora non avesse un "buon" indirizzo di partenza, sarebbe poi difficile per lui vincere la gara chiedendo aiuto all'esterno (la potenza computazionale la puoi anche chiedere all'esterno come si fa con le pool, ma l'indirizzo su cui riversare la ricompensa intera del blocco no; sarebbe anche rischiosa la pratica di comprare un "buon" indirizzo all'esterno, sia per questioni di tempistica, sia perchè se compri un indirizzo non puoi mai avere la sicurezza che il venditore abbia distrutto la chiave privata relativa)
 
- per quanto riguarda il valore complessivo della soglia, il sistema continuerebbe ad aggiornare quel valore dinamico ogni tot blocchi come avviene adesso in modo da perseguire l'obiettivo del tempo medio di 10 minuti; sicuramente però diventerebbe più imprevedibile di oggi il tempo di conferma di 1 blocco (inoltre va studiato con attenzione come evitare la possibilità concreta che nessuno riesca a minare il blocco)

Da notare infine che mentre la soglia complessiva rimane un dato puramente tecnico (che si autoaggiusta per ottenere i 10 minuti di media), i pesi A e B sono invece un dato più "politico" (quanto peso dare alla proof of work rispetto alla proof of stake e viceversa)

Che ne pensate?