SEZIONE 04.03 – Dividere e distribuire le chiavi

WEEK 4
Come gestire e usare i Bitcoin

This week we’ll explore how using Bitcoins works in practice: different ways of storing Bitcoin keys, security measures, and various types of services that allow you to trade and transact with bitcoins.
Questa settimana esamineremo come funziona in pratica l’uso dei Bitcoin: diversi modi di memorizzare chiavi Bitcoin, misure di sicurezza e vari tipi di servizi che consentono di negoziare e negoziare con bitcoin.

Edward W. Felten – Professor of Computer Science and Public Affairs Princeton University

Sezione 4.3 – Dividere e distribuire le chiavi
In segment 4.3, we’ll talk about how to share and split keys. Up to now, we’ve talked about different ways of storing and managing the secret keys that control BitCoins, but we’ve always put a key in a single place. Whether that’s locked in a safe, or in software, or on paper, it’s in one place. And storing the key in one place leaves us with a single point of failure. So that if something goes wrong with that single storage place, then we’re in trouble. So here, what we’d like to do now is be able to take a key and split it up into pieces and share those pieces around so that we avoid the single point of failure problem.
Nel segmento 4.3 parleremo di come condividere e dividere le chiavi. Fino ad ora, abbiamo parlato di diversi modi di archiviare e gestire le chiavi segrete che controllano BitCoin, ma abbiamo sempre messo una chiave in un unico posto. Che sia chiuso in una cassaforte, o nel software o sulla carta, è in un unico posto. E memorizzare la chiave in un posto ci lascia con un singolo punto di errore. In modo che se qualcosa va storto con quel singolo spazio di archiviazione, allora siamo nei guai. Quindi, quello che vorremmo fare ora è essere in grado di prendere una chiave e dividerla in pezzi e condividerle in modo da evitare il problema del single point of failure.
04.03.01
And so we’re gonna introduce a cryptographic trick called Secret sharing. The idea is we’re gonna take some secret, in our case, a secret key, and we’re gonna divide it up into some number N of pieces. And we’re gonna do that in such a way that, if we’re given any K of those pieces, then we’ll be able to reconstruct the original secret. But if we’re given fewer than K pieces, then we won’t be able to learn anything about the original secret. So for example, we might have N=2 and K=2. That means we’re dividing the secret into two pieces, and you need both pieces to put them together. And a specific way of getting N=2, K=2
E quindi introdurremo un trucco crittografico chiamato Secret sharing. L’idea è che prenderemo qualcosa di segreto, nel nostro caso, una chiave segreta, e la suddivideremo in un numero N di pezzi. E lo faremo in modo tale che, se ci viene dato un K di quei pezzi, allora saremo in grado di ricostruire il segreto originale. Ma se avremo meno di K pezzi, allora non saremo in grado di imparare qualcosa sul segreto originale. Ad esempio, potremmo avere N = 2 e K = 2. Ciò significa che dividiamo il segreto in due parti, e hai bisogno di entrambi i pezzi per metterli insieme. E un modo specifico per ottenere N = 2, K = 2
04.03.02
Secret sharing like this is as illustrated here. That first we’re going to generate a number P which is a large prime number. Doesn’t need to be secret or anything, just really big.
S is gonna be the secret and the secret has to be between 0 and P minus one inclusive. And then we’re gonna generate a random value R, secretly, which is also within the range between zero and P minus one.
And now we’re gonna split our secret into two pieces, X1 and X2. Piece X1 is gonna be (S+R) mod P and remember that modulo is the operation that’s sometimes written with the percent sign in programming languages. It just means, take this value S+R, and divide it by P, and keep the remainder, when we do that division. That’s S+R mod P. So that’ll be X1, our first share and the other share, X2, is gonna be S+2R mod P.
La condivisione segreta come questa è come illustrato qui. Per prima cosa genereremo un numero P che è un numero primo grande. Non ha bisogno di essere segreto o altro, solo davvero grande.
S sarà il segreto e il segreto deve essere tra 0 e P meno uno compreso. E poi genereremo un valore casuale R, segretamente, che è compreso nell’intervallo tra zero e P meno uno.
E ora dividiamo il nostro segreto in due parti, X1 e X2. Il pezzo X1 sarà (S + R) mod P e ricorda che il modulo è l’operazione che a volte viene scritta con il segno di percentuale nei linguaggi di programmazione. Significa semplicemente prendere questo valore S + R e dividerlo per P, e mantenere il resto, quando facciamo quella divisione. Questo è S + R mod P. Quindi sarà X1, la nostra prima condivisione e l’altra condivisione, X2, sarà S + 2R mod P.
04.03.03
Okay, and now if we have both of these shares X1 and X2 we can combine them to reconstruct the secret S. What we do is we compute two times X1 minus X2 mod P. So two times X1 is 2S plus 2R and X2 which we’re subtracting off is S plus 2R. And so we have 2S minus S, that leaves us with an S. We have 2R minus 2R, and so the 2Rs cancel out, and we’re left with just S mod P, which is equal to S because S is less than P. And so we can reconstruct the secret in this way. So given two shares we can reconstruct but given only one of the shares, it turns out we don’t learn anything. And to see why that is, consider X1 we took S which is the secret, but we added to it a random number which could take on any value between zero and P minus 1 with equal likelihood. And if you think about it, you can convince yourself that the result of S plus R modulo P is equally likely to take on any value between zero and P minus 1, and that’s true regardless of what S was. And so this share by itself just looks like a purely random number and doesn’t convey anything about what the value of S might have been. Similarly this share by itself is also equally likely to take on any value between zero and P minus one. And therefore doesn’t convey any information about S. So that’s N=2, K=2. Given both shares, we can get back the secret given one share, we can’t.
Okay, e ora se abbiamo entrambe queste condivisioni X1 e X2 possiamo combinare loro per ricostruire il segreto S. Quello che facciamo è calcolare due volte X1 meno X2 mod P. Quindi due volte X1 è 2S più 2R e X2 che stiamo sottraendo è S più 2R. E quindi abbiamo 2S meno S, che ci lascia con un S. Abbiamo 2R meno 2R, e quindi i 2R si cancellano, e restiamo solo con S mod P, che è uguale a S perché S è minore di P E così possiamo ricostruire il segreto in questo modo. Quindi, date due condivisioni che possiamo ricostruire, ma date solo una delle azioni, risulta che non impariamo nulla. E per capire perché, consideriamo X1 che abbiamo preso S, che è il segreto, ma abbiamo aggiunto ad esso un numero casuale che potrebbe assumere qualsiasi valore compreso tra zero e P meno 1 con uguale probabilità. E se ci pensate, potete convincervi che il risultato di S + R modulo P è altrettanto probabile che assuma qualsiasi valore compreso tra zero e P meno 1, e questo è vero indipendentemente da ciò che S era. E quindi questa condivisione di per sé sembra solo un numero puramente casuale e non trasmette nulla su quale potrebbe essere stato il valore di S. Allo stesso modo questa stessa azione ha anche la stessa probabilità di assumere qualsiasi valore compreso tra zero e P meno uno. E quindi non trasmette alcuna informazione su S. Quindi questo è N = 2, K = 2. Con entrambe le azioni, possiamo recuperare il segreto dato una quota, non possiamo.
04.03.04
Okay, now in general we can talk about how to get higher values of N and K. For example, let’s talk about how to get higher values of N, where K equals two. That is, we’re going to want to require two shares to be put together to reconstruct the secret, but we’re gonna make more than two shares that are eligible for use in this way. And so the way we’ll do that is to draw our x standard, x and y axis here. And we’re gonna add a point here at (0, S), where S is the secret.
And so obviously if somebody can learn what this point is, then they will have reconstructed the secret. Okay, now we’re gonna draw a line and we’re gonna draw a line that has a random slope R.
R is gonna be generated randomly and so we get a line like this. And now, we can give out shares. The first share is this point here at x=1 and y is S+R. The second share is here at, x=2 and y turns out to be S+2R. The third share is here, x=3, and y is S+3R and so on. We can go as far up this line as we want, and generate as many shares as we want. Okay, now if you think about it, you can convince yourself that given any two points you can interpolate and find S, right? That’s a property of a line. Given any two points on a line, you can interpolate the line. Imagine setting down a ruler that exactly touches say these two points, and then you can draw a straight line along that ruler. So given any two points we can reconstruct what this line is. You can see where the line crosses the Y axis, that would be 0,S and that would give you back the secret. But given just one point you don’t really know anything. Because if you have, say, this point well the line might be sloped like this, but equally likely it might be sloped like this, it could be sloped any way at all. And so given just this point, you don’t really know anything about where this line might cross the y axis, so you don’t know anything about S. And in fact, you can prove that if you do this arithmetic, modulo large prime P, like we did before in the previous slide. Then in fact, you can prove that any two points are sufficient to interpolate and find S and fewer than two points don’t tell you anything about S. And so this gives us N equals any value, and K=2. All right, but now what if we wanted to require more than two points? Well for two points we drew a line because any two points are sufficient to uniquely specify a line. If we wanna require three points, what we’re going to do is use a quadratic function. Because any three points are sufficient to reconstruct a quadratic function.
Ok, ora in generale possiamo parlare di come ottenere valori più alti di N e K. Per esempio, parliamo di come ottenere valori più alti di N, dove K è uguale a due. Cioè, vorremmo richiedere due azioni da mettere insieme per ricostruire il segreto, ma faremo più di due azioni che possono essere utilizzate in questo modo. E quindi il modo in cui lo faremo è disegnare qui il nostro asse x standard, xey. E aggiungeremo un punto qui a (0, S), dove S è il segreto.
E quindi, ovviamente, se qualcuno può imparare che cos’è questo punto, allora avrà ricostruito il segreto. Ok, ora disegneremo una linea e disegneremo una linea che ha una pendenza casuale R.
R sarà generato casualmente e così otteniamo una linea come questa. E ora, possiamo distribuire le condivisioni. La prima condivisione è questo punto qui in x = 1 ey è S + R. La seconda condivisione è qui a, x = 2 e y risulta essere S + 2R. La terza condivisione è qui, x = 3 e y è S + 3R e così via. Possiamo andare così lontano come vogliamo, e generare il numero di condivisioni che vogliamo. Ok, ora se ci pensi, puoi convincerti che dato due punti puoi interpolare e trovare S, giusto? Questa è una proprietà di una linea. Dati due punti su una linea, puoi interpolare la linea. Immagina di posizionare un righello che tocchi esattamente i due punti, quindi puoi disegnare una linea retta lungo quel righello. Quindi, dati due punti qualsiasi, possiamo ricostruire cos’è questa linea. Puoi vedere dove la linea attraversa l’asse Y, che sarebbe 0, S e che ti restituirebbe il segreto. Ma dato solo un punto, non sai davvero nulla. Perché se hai, diciamo, questo punto, la linea potrebbe essere inclinata in questo modo, ma altrettanto probabilmente potrebbe essere inclinata in questo modo, potrebbe essere in qualche modo inclinata. E così, dato solo questo punto, non sai nulla su dove questa linea potrebbe attraversare l’asse y, quindi non sai nulla di S. E infatti, puoi dimostrare che se fai questa aritmetica, modulo grande primo P, come abbiamo fatto prima nella diapositiva precedente. Quindi, in effetti, puoi dimostrare che due punti sono sufficienti per interpolare e trovare S e meno di due punti non ti dicono nulla su S. E quindi questo ci dà N = valore uguale a e K = 2. Va bene, ma ora se volessimo richiedere più di due punti? Bene per due punti abbiamo tracciato una linea perché ogni due punti sono sufficienti per specificare in modo univoco una linea. Se vogliamo richiedere tre punti, quello che faremo è usare una funzione quadratica. Perché ogni tre punti sono sufficienti per ricostruire una funzione quadratica.
04.03.05
And so, we can use this table to understand what’s going on. So, if use the equation S+RX mod P with the random parameter R. That’s the slope that we saw in the previous slide. Then you need two points to recover S because you need two points to interpolate a line. If on the other hand, if then you use a quadratic, that is S plus some random value R1 times X, plus some other random value R2 times X squared. Then there are two random parameters, R1 and R2, and with any three points you can uniquely interpolate a quadratic, and get back S. And we can just go up the ladder here, if we use a cubic function. There are three random parameters, we need four points. And in any case you can generate as many points as you want on the line or the quadratic or the cubic. And therefore you can get any value of N. And you see how you can get any value of K by just going to higher and higher order polynomials. And so this scheme will let you take any secret and split it onto N shares, such that K shares or more are needed to reconstruct. And that turns out to be a really useful thing, because now you can take a secret key or other secret information, and split it up in this way. Support K-out-of-N splitting, for any K and N.
E così, possiamo usare questa tabella per capire cosa sta succedendo. Quindi, se usi l’equazione S + RX mod P con il parametro casuale R. Questa è la pendenza che abbiamo visto nella diapositiva precedente. Quindi hai bisogno di due punti per recuperare S perché hai bisogno di due punti per interpolare una linea. Se d’altra parte, se poi usi una quadratica, vale S più un valore casuale R1 volte X, più qualche altro valore casuale R2 volte X al quadrato. Poi ci sono due parametri casuali, R1 e R2, e con qualsiasi tre punti puoi interpolare in modo univoco un quadratico, e tornare indietro. E possiamo semplicemente salire la scala qui, se usiamo una funzione cubica. Ci sono tre parametri casuali, abbiamo bisogno di quattro punti. E in ogni caso puoi generare quanti punti vuoi sulla linea o il quadratico o il cubo. E quindi puoi ottenere qualsiasi valore di N. E vedi come puoi ottenere qualsiasi valore di K semplicemente andando a polinomi di ordine sempre più alto. E così questo schema ti permetterà di prendere qualsiasi segreto e dividerlo su azioni N, in modo tale che siano necessarie o necessarie azioni K per ricostruire. E questo risulta essere una cosa molto utile, perché ora puoi prendere una chiave segreta o altre informazioni segrete e dividerlo in questo modo. Supporta la divisione K-out-of-N, per qualsiasi K e N.
04.03.06
So let’s talk about the good and bad that we get out of this process. The good part is that we can store the shares separately, and the adversary needs to be able to recover K shares in order to get back what the secret was. And that’s the good news, right? That means that if we use, say, K equals three, N equals four, the adversary needs to get break into three separate places. And if we’re clever about storing those separate shares in places that are far apart and independently secured, then we could make the adversary’s job much more difficult. And indeed, if we’ve noticed that the adversary is compromised one of those places, we can then raise out and try to recover the other shares and address the problem. The other thing that’s good about this, is that we can afford to lose some of the shares. If we do three out of four secret splitting, then we can lose one share and we’ll still have three left. And so we can put those three remaining ones together and still get back the key. So even though we are spreading out the information, there are more places where information might be lost. We can also tolerate the loss of some of those. In general we can tolerate the loss of N-K of them. Now that’s the good news. The bad news is that if we take a key and we split it up in this way, and we then wanna go back and use the key to sign something, we still need to bring the shares together and recalculate the initial secret in order to be able to sign with that key. And that point where we bring all the shares together and recombine them is still a single point of vulnerability. Where an adversary might be able to attack us, and that’s the bad news. So although this is useful it’s not a panacea and there’s something else that we like which is the ability to generate separate shares, and use those shares separately in order to sign.
Quindi parliamo del bene e del male che otteniamo da questo processo. La parte buona è che possiamo archiviare le azioni separatamente, e l’avversario deve essere in grado di recuperare le azioni K per recuperare ciò che era il segreto. E questa è la buona notizia, giusto? Ciò significa che se usiamo, diciamo, K è uguale a tre, N è uguale a quattro, l’avversario ha bisogno di entrare in tre punti separati. E se siamo intelligenti nello stoccare quelle parti separate in luoghi distanti e garantiti indipendentemente, allora potremmo rendere il lavoro dell’avversario molto più difficile. E in effetti, se abbiamo notato che l’avversario è compromesso in uno di quei posti, possiamo sollevarlo e provare a recuperare le altre azioni e affrontare il problema. L’altra cosa che va bene è che possiamo permetterci di perdere parte delle azioni. Se facciamo tre divisioni segrete su quattro, allora possiamo perdere una condivisione e ne resteranno ancora tre. E così possiamo mettere insieme quei tre rimanenti e tornare comunque la chiave. Quindi, anche se stiamo diffondendo le informazioni, ci sono più posti in cui le informazioni potrebbero andare perse. Possiamo anche tollerare la perdita di alcuni di quelli. In generale possiamo tollerare la perdita di N-K. Questa è la buona notizia. La cattiva notizia è che se prendiamo una chiave e la dividiamo in questo modo, e poi vogliamo tornare indietro e usare la chiave per firmare qualcosa, dobbiamo ancora riunire le condivisioni e ricalcolare il segreto iniziale per essere in grado di firmare con quella chiave. E quel punto in cui riuniamo tutte le condivisioni e ricombiniamo è ancora un singolo punto di vulnerabilità. Dove un avversario potrebbe essere in grado di attaccarci, e questa è la cattiva notizia. Quindi, anche se questo è utile, non è una panacea e c’è qualcos’altro che ci piace, che è la capacità di generare condivisioni separate, e di usare quelle condivisioni separatamente per firmare.
04.03.07
And that’s what’s behind the concept of Multi-sig that we saw earlier in Lecture 3. So, if you recall Multi-sig in Lecture 3, it lets you keep the shares or the different pieces that need to sign a particular transaction apart and to allow them to approve the transaction separately without needing to reassemble the key at any point.
Ed è questo ciò che sta dietro al concetto di Multi-sig che abbiamo visto prima in Lezione 3. Quindi, se richiama Multi-sig in Lecture 3, ti consente di mantenere le condivisioni o le diverse parti che devono firmare una particolare transazione e di consentire loro di approvare la transazione separatamente senza dover ricomporre la chiave in nessuna point.
04.03.08
So just as an example of application of that, suppose that Andrew, Arvind, Ed, and Joseph are co-workers. Let’s say they’re cofounders of a company and the company has a lot of bitcoins. Hey, you know, we can dream. Now, what we might want to do is use multi-sig to protect our large store of BitCoins. So what we’re going to do is have each of the four of us generate a key pair, and we’re going to for, our company’s cold storage, store the coins so that we require multi-sig, with three out of the four keys signing. Now the result of that is that we know that we’re relatively secure if the four of us keep our keys separately and secure them differently. But someone would have to compromise three out of the four keys that, if some employee or even two employees go rogue, those rogue employees can’t steal all of the company’s coins, because you would need a conspiracy of three out of four to do that. And we also know that if something goes wrong, if one of us loses our key, or if one of us gets run over by a bus and our brain wallet is lost, the others can still get the coins back and transfer them over to a new place. And so multi-sig allows you, or helps you, to manage large bodies of cold-stored coins in a way that’s relatively secure and that requires action by multiple people before anything drastic happens.
Quindi come esempio di applicazione di questo, supponiamo che Andrew, Arvind, Ed e Joseph siano collaboratori. Diciamo che sono co-fondatori di un’azienda e che la compagnia ha molti bitcoin. Ehi, lo sai, possiamo sognare. Ora, quello che vorremmo fare è usare multi-sig per proteggere il nostro grande archivio di BitCoin. Quindi, quello che faremo è che ognuno di noi quattro generi una coppia di chiavi, e noi lo faremo, il magazzino frigorifero della nostra azienda, immagazzineremo le monete in modo che richiediamo il multi-sig, con tre delle quattro chiavi di firma. Ora il risultato è che lo sappiamo mantieni le nostre chiavi separatamente e fissale in modo diverso. Ma qualcuno dovrebbe scendere a compromessi su tre delle quattro chiavi che, se alcuni dipendenti o addirittura due impiegati diventano dei ladri, quegli impiegati disonesti non possono rubare tutte le monete della compagnia, perché avresti bisogno di una cospirazione di tre su quattro per fare quella. E sappiamo anche che se qualcosa va storto, se uno di noi perde la chiave, o se uno di noi viene investito da un autobus e il nostro portafoglio cerebrale è perso, gli altri possono ancora recuperare le monete e trasferirle a un nuovo posto. E così multi-sig ti permette, o ti aiuta, di gestire grandi corpi di monete immagazzinate a freddo in un modo relativamente sicuro e che richiede l’intervento di più persone prima che accada qualcosa di drastico.
[top]
© Edward W. Felten – Professor of Computer Science and Public Affairs Princeton University
SEZIONE 04.02
Deposito caldo e freddo
SEZIONE 04.04
Portafogli online e cambi