W01.01 – FUNZIONE DI HASH CRITTOGRAFICA


WEEK 1
Introduzione alla Crittografia e alle Criptovalute

Learn about cryptographic building blocks (“primitives”) and reason about their security. Work through how these primitives can be used to construct simple cryptocurrencies. Imparare a costruire blocchi di crittografici (“primitivi”) e la ragione dietro la loro sicurezza. Imparare come utilizzare questi “primitivi” per costruire semplici criptovalute.

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

Sezione 01.0 – Welcome
01.0
Welcome to the first lecture in our series on Bitcoin and Cryptocurrencies. I want to start by introducing the four lecturers who are going to be speaking in the series. The first lecturer is Joseph Bonneau. He’s a postdoctoral researcher in computer science at Princeton University. The second lecturer is me, Ed Felten. I’m a professor at Princeton in computer science and at the Woodrow Wilson School. The third lecturer is Arvind Narayanan. He’s a computer science professor at Princeton. And fourth, our special guest lecturer is Andrew Miller. He’s a PhD student in computer science at the University of Maryland. There will be 11 lectures in total.

In this lecture, number one, we’re going to do two things. First we’ll introduce some cryptographic primitives that turn out to be necessary for talking about cryptocurrencies.

In particular, we’ll talk about cryptographic hashes and digital signatures, and we’ll talk about some of the ways in which those are used to build cryptocurrencies.

And then at the end of the lecture, we’ll start talking about cryptocurrencies, and I’ll give some examples of simple cryptocurrencies that illustrate some of the design challenges that we need to deal with.

I want to apologize for covering the cryptographic material at the beginning. Unfortunately, we have to eat some of our vegetables a little bit in order to lay groundwork for the cryptocurrency stuff.

So if you came for the cryptocurrency stuff, let me assure you, first of all, that we will get to it in this lecture, and that having laid the groundwork in this lecture, there’s going to be a lot more specifically cryptocurrency-focused material in later lectures.

All right. So let’s get to it.
Benvenuti alla prima lezione della nostra serie su Bitcoin e Cryptocurrencies. Voglio iniziare presentando i quattro docenti che parleranno nella serie. Il primo docente è Joseph Bonneau. È un ricercatore postdottorato in informatica presso la Princeton University. Il secondo docente sono io, Ed Felten. Sono un professore a Princeton in informatica e alla Woodrow Wilson School. Il terzo docente è Arvind Narayanan. È un professore di informatica di Princeton. E in quarto luogo, il nostro docente ospite speciale è Andrew Miller. È uno studente di dottorato in informatica presso l’Università del Maryland. Ci saranno 11 lezioni in totale.

In questa lezione, numero uno, faremo due cose. Innanzitutto introdurremo alcune crittografie primitive che risultano essere necessarie per parlare di criptovalute.

In particolare, parleremo di funzioni crittografiche di hash e firme digitali e parleremo di alcuni dei modi in cui questi vengono utilizzati per costruire criptovalute.

E poi alla fine della lezione, inizieremo a parlare di criptovalute, e darò alcuni esempi di semplici criptovalute che illustrano alcune delle sfide progettuali che dobbiamo affrontare.

Voglio scusarmi per aver affrontato il materiale crittografico all’inizio. Sfortunatamente, dobbiamo mangiare un po’ dei nostri ortaggi per gettare le basi per la criptovaluta.

Quindi, se sei venuto per la criptovaluta, ti assicuro, prima di tutto, che ci arriveremo in questa lezione, e che avendo posto le basi in questa lezione, e che ci sarà molto più specificamente materiale focalizzato sulla criptovaluta nelle successive lezioni.

Tutto ok. Quindi proviamoci.

[top]

 

Sezione 01.01 – Funzione di Hash Crittografica
01.01.0
In segment 1.1 we’re going to talk about cryptographic hash functions. We’ll talk about what they are, and what their properties are. And then later we’ll move on and talk about what their applications are.

So, a cryptographic hash function is a mathematical function. And it has three attributes that we need to start with.

First of all, a hash function can take any string as input, absolutely any string of any size. It produces a fixed-size output, we’ll use a 256 bits in this series of lectures, cuz that’s what bitcoin does. And it has to be efficiently computable, meaning given a string, in a reasonable length of time, you can figure out what the output is.

So that’s a hash function, but we’re going to need hash functions that are cryptographically secure.

The cryptographic properties of hash functions are a complicated topic in general. But we’re gonna focus here on three particular properties. And I’ll explain in a minute what those are.

In particular, that the function is collision-free, that it has a hiding property, and that it’s puzzle-friendly. And for each of these, I’ll talk about what the property is, what it means. And then I’ll talk about why it’s useful to have a function that has that property.
Nella sezione 1.1 parleremo delle funzioni hash crittografiche. Parleremo di cosa sono e quali sono le loro proprietà. E poi passeremo a parlare delle loro applicazioni.

Quindi, una funzione di hash crittografica è una funzione matematica. E ha tre attributi da cui dobbiamo iniziare.

Prima di tutto, una funzione di hash può prendere qualsiasi stringa come input, assolutamente qualsiasi stringa di qualsiasi dimensione. Produce un output di dimensioni fisse, useremo 256 bit in questa serie di lezioni, perché è ciò che fa bitcoin. E deve essere calcolabile in modo efficiente, nel senso che data una stringa, in un ragionevole lasso di tempo, è possibile capire quale sia l’output.

Quindi questa è una funzione di hash, ma avremo bisogno di funzioni di hash che siano crittograficamente sicure.

Le proprietà crittografiche delle funzioni di hash sono un argomento complicato in generale. Ma ci concentreremo qui su tre particolari proprietà. E spiegherò in un minuto cosa sono.

In particolare, che la funzione è collision free (resistente alle collisioni), che ha una proprietà nascosta e che è puzzle-friendly [adatta ai rompicapo !!]. E per ognuno di questi, parlerò di quale è la proprietà, e cosa significa. E poi parlerò del perché è utile avere una funzione che ha quella proprietà.
01.01.01
So, first, collision-free. So, the first property that we need from a cryptographic hash function is that it’s collision free. And what that means is that it’s impossible, nobody can find values x and y, such that x and y are different, and yet the hash of x is equal to the hash of y.

And so if we look at the operation of the function as depicted by one of these red arrows. Here’s x and H(x), and here’s y and H(y). Then nobody can find a situation like this. That you have an x and y that are separate, and yet when you hash them, they hash to the same value. Now one thing to notice is that I said, nobody can find. I didn’t say that there is no collision, because if you think about it there has to be a collision. Collisions do exist, and to understand why that is, we can use this diagram.
Quindi, prima, collision free (resistente alle collisioni). Quindi, la prima proprietà di cui abbiamo bisogno da una funzione di hash crittografica è che sia collision free. E ciò significa che è impossibile, nessuno può trovare i valori x e y, così che x e y sono diversi, e mentre l’hash di x è uguale all’hash di y.

E quindi se osserviamo l’operazione della funzione come raffigurata da una di queste frecce rosse. Ecco x e H (x), e ecco y e H (y). Quindi nessuno può trovare una situazione come questa. Che tu abbia una x e una y che sono separate, e mentre (sono sotto) hash, esse hanno l’hash allo stesso valore. Ora una cosa da notare è che ho detto, nessuno può trovare. Non ho detto che non c’è collisione, perché se ci pensi ci deve essere una collisione. Le collisioni esistono e per capire perché, possiamo usare questo diagramma.
 
01.01.02
Over here on the left, I’m depicting all of the possible inputs to this function, which can be a string of any size. And over here, I have all of the possible outputs, which has to be string of 256 bits in size. So the right hand side here, the outputs, there are only 2 to the 256 possibilities. Over here, there are more possibilities. Qui a sinistra, sto descrivendo tutti i possibili input per questa funzione, che può essere una stringa di qualsiasi dimensione. E qui ho tutte le uscite possibili, che devono essere una stringa di 256 bit. Quindi il lato destro qui, le uscite, ci sono solo 2 su 256 possibilità. Qui, ci sono più possibilità.
 
01.01.03
And so if you think that every point here on the left is gonna be mapped by an arrow, to some point on the right. You can see that as you go from all the points over here on the left into the right, it has to get crowded. And in fact, that there have to be multiple values over here on the left that map to the same output over here. In fact, in general, there will be a very large number of possible inputs that map to any particular output. So collisions do exist. I said before nobody can find a collision. And that’s the key question. We know collisions exist. The question is are there any collisions that are findable by regular people using regular computers? E quindi se pensi che ogni punto qui a sinistra sia mappato da una freccia, ad un certo punto a destra. Puoi vedere che mentre vai da tutti i punti qui a sinistra a destra, deve essere affollato. E infatti, ci devono essere più valori qui a sinistra che mappano allo stesso output qui. Di fatto, in generale, ci sarà un numero molto grande di input possibili che si associano a un particolare output. Quindi esistono collisioni. Ho detto prima che nessuno possa trovare una collisione. E questa è la domanda chiave. Sappiamo che esistono delle collisioni. La domanda è: ci sono collisioni che possono essere trovate da persone normali che usano computer normali?
01.01.04
Okay, now to make things even worse, I said that it has to be impossible to find a collision. Let me tell you how to find a collision, because there’s a method that’s guaranteed to work. And the method works like this.

That we’re gonna pick 2 to the 130 randomly chosen inputs, over on the left cloud of that previous diagram. And if we pick those 2 to the 130 randomly chosen inputs, it turns out there’s a 99.8% chance that at least two of them are going to collide. And so this is a simple method for finding a collision. It works no matter what the hash function is, but of course, the problem is, that this takes a very, very long time to do. You have to compute the hash function 2 to the 130 times. And that’s, of course, an astronomical number. This method works no matter which hash function we’re using. There’s still a 99.8% probability that this works. And if it doesn’t work, just try it again, it’ll probably work the next time. But, this doesn’t really matter. And the reason it doesn’t really matter, is that this procedure takes 2 to the 130 steps, in order to get to that high probability.

So, we can say something like this. We can say that if every computer ever made by humanity was computing since the beginning of the entire Universe up to now, the odds that they would have found a collision is still infinitesimally small. So small that it’s way less than the odds that the Earth will be destroyed by a giant meteor in the next two seconds, …… which didn’t happen.
Ok, ora per rendere le cose ancora peggiori, ho detto che deve essere impossibile trovare una collisione. Lascia che ti dica come trovare una collisione, perché c’è un metodo che è garantito funzioni. E il metodo funziona così.

Se selezioneremo 2 dei 130 input scelti a caso, sulla nuvola sinistra del diagramma di prima. E se prendiamo quei 2 sui 130 input scelti a caso, si scopre che c’è una possibilità del 99,8% che almeno due di loro entreranno in collisione. E quindi questo è un metodo semplice per trovare una collisione. Funziona indipendentemente dalla funzione hash, ma ovviamente il problema è che ci vuole molto, molto tempo per farlo. Devi calcolare la funzione hash 2 su 130 volte. E questo è, ovviamente, un numero astronomico. Questo metodo funziona indipendentemente dalla funzione di hash che stiamo usando. C’è ancora una probabilità del 99,8% che funzioni. E se non funziona, prova ancora, probabilmente funzionerà la prossima volta. Ma questo non importa. E la ragione per cui non ha molta importanza, è che questa procedura richiede da 2 a 130 passaggi, per arrivare a quella alta probabilità.

Quindi, possiamo dire qualcosa del genere. Possiamo dire che se ogni computer mai realizzato dall’umanità fosse stato computerizzato dall’inizio dell’intero Universo fino ad ora, le probabilità che avrebbero trovato una collisione sono ancora infinitamente piccole. Così piccolo che è molto meno delle probabilità che la Terra venga distrutta da una gigantesca meteora nei due secondi successivi, …. il che non è accaduto.
 
01.01.05
Okay, so we know how to find a collision. But this method takes too long to matter. The question is, is there some other method that could be used on a particular hash function, in order to find a collision? And that’s the question that is harder to answer. Is there a faster way to find collisions? Well, for some possible values of hash functions, of course there are. For example, if our hash function were to simply take the input, modulo 2 to the 256, that is, it just selected the last 256 bits of the input. Then we would know an easy way to find a collision. One collision would be the values 3, and 3 plus 2 to the 256. So, for some possible values of the hash function, it’s very easy to find a collision. For others, we don’t know.

Now, one thing I need to note is that there’s no hash function in existence which has been proven to be collision free. There are just some that people have tried really, really hard to find collisions and haven’t succeeded. And so we choose to believe that those are collision free.
Ok, quindi sappiamo come trovare una collisione. Ma questo metodo richiede troppo tempo per avere importanza. La domanda è, c’è qualche altro metodo che potrebbe essere utilizzato su una particolare funzione di hash, al fine di trovare una collisione? E questa è la domanda a cui è più difficile rispondere. C’è un modo più veloce per trovare le collisioni? Bene, per alcuni possibili valori delle funzioni di hash, ovviamente ci sono. Ad esempio, se la nostra funzione di hash dovesse semplicemente prendere l’input, modulo 2 su 256, cioè, ha appena selezionato gli ultimi 256 bit dell’input. Allora sapremmo in modo semplice come trovare una collisione. Una collisione sarebbero i valori 3 e 3 più 2 su 256. Quindi, per alcuni possibili valori della funzione hash, è molto facile trovare una collisione. Per gli altri, non lo sappiamo.

Ora, una cosa che devo notare è che non esiste alcuna funzione di hash esistente che sia stata dimostrata priva di collisioni. Ce ne sono solo alcune che le persone hanno provato davvero, molto difficile trovare collisioni e non ci sono riusciti. E così scegliamo di credere che quelli siano privi di collisioni.
 
01.01.06
Okay, now, what good does collision freedom do us? If we can assume that we have a hash function that is collision free, then we can use that hash function as message digest.
And what I mean by that is the following. That if we know that x and y have the same hash, then it’s safe to assume that x and y are the same. Because if someone knew an x and y that were different, that had the same hash, of course, that would be a collision. Since there’s not a collision that we know of, then knowing the hashes are the same, we can assume that the values are the same. And this let’s us use the hash as a kind of message digest.

Suppose, for example, that we had a file, a really big file. And we wanted to be able to recognize later whether another file was the same as the file we saw the first time, right? So one way to do that would be to save the whole big file. And then when we saw another file later, just compare them. But because we have hashes that we believe are collision free, it’s more efficient to just remember the hash of the original file. Then if someone shows us a new file, and claims that it’s the same, we can compute the hash of that new file and compare the hashes. If the hashes are the same, then we conclude that the files must have been the same. And that gives us a very efficient way to remember things we’ve seen before and recognize them again. And, of course, this is useful because the hash is small, it’s only 256 bits, while the original file might be really big. So hash is useful as a message digest.

And we’ll see, later on in this lecture, and in subsequent lectures, why it’s useful to use hash as a message digest.
Ok, ora, a che serve la collision free [resistenza alle collisioni]? Se possiamo assumere che abbiamo una funzione di hash che è collision free, allora possiamo usare quella funzione di hash come message digest. Quello che voglio dire è questo: se sappiamo che x e y hanno lo stesso hash, allora è sicuro assumere che x e y siano uguali. Perché se qualcuno conoscesse una x e una y diversa, che avesse lo stesso hash, ovviamente, sarebbe una collisione. Fino a quando non saremo a conoscenza che non c’è una collisione, e quindi sapere che gli hash sono gli stessi, possiamo supporre che i valori siano gli stessi. E questo ci lascia usare l’hash come una sorta di message digest.

Supponiamo, per esempio, di avere un file, un file veramente grande; e volevamo essere in grado di riconoscere in seguito se un altro file fosse uguale al primo file. Un modo per farlo sarebbe quello di salvare l’intero file. E poi quando abbiamo visto un altro file in seguito, basta confrontarli. Ma poiché abbiamo degli hash che riteniamo privi di collisione, è più efficiente ricordare semplicemente l’hash del file originale. Quindi se qualcuno ci mostra un nuovo file e afferma che è lo stesso, possiamo calcolare l’hash di quel nuovo file e confrontare gli hash. Se gli hash sono gli stessi, concludiamo che i file devono essere gli stessi. E questo ci dà un modo molto efficace per ricordare cose che abbiamo visto prima e riconoscerle di nuovo. E, naturalmente, questo è utile perché l’hash è piccolo, ha solo 256 bit, mentre il file originale potrebbe essere davvero grande. Quindi l’hash è utile come message digest.

Vedremo, più avanti in questa sezione e nelle sezioni successive, perché è utile usare l’hash come message digest.
 
01.01.07
So, the second property that we want from our hash function is that it’s hiding. And the property that we want is something like this. That if we’re given the output of the hash function, that there’s no feasible way to figure out what the input x was. The problem is that this property doesn’t exactly hold. And to understand why that’s the case, let’s look at this example. Quindi, la seconda proprietà che vogliamo dalla nostra funzione di hash è che si nasconde. E la proprietà che vogliamo è qualcosa di simile. Che se ci viene dato l’output della funzione hash, non c’è modo di capire quale sia l’input x. Il problema è che questa proprietà non regge esattamente. E per capire perché questo è il caso, diamo un’occhiata a questo esempio.
 
01.01.08
So here, what we’re going to do is an experiment where we flip a coin. And if the result of the coin flip was heads, we’re going to return the hash of the string “heads”. And if the result was tails, we’re going to return the hash of the string “tails”.

And now we’re gonna ask someone who didn’t see the coin flip, but only saw this hash output, to figure out what the string was that was hashed. That, of course, is going to be easy.
Quindi qui, quello che faremo è un esperimento in cui lanciamo una moneta. E se il risultato del lancio della moneta fosse la testa, restituiremo l’hash della stringa “teste”. E se il risultato fosse una croce, restituiremo l’hash della stringa “croce”. [tails = croce]

E ora chiederemo a qualcuno che non ha visto il lancio della moneta, ma ha visto solo questo output di hash, per capire quale fosse la stringa che era stata sottoposta a hash. Questo, ovviamente, sarà facile.
 
01.01.09
It’s easy in this scenario to find what the input string was, it’s easy to find x. You simply compute the hash of the string “heads” and the hash of the string “tails”, and you see which one you got. And so, in just a couple of steps, you can figure out what x was. So the reason this example failed, that is the reason why an adversary was able to guess what the string was, was that there were only a couple of possible values of x. And so, if we’re gonna have a hiding property like this, it needs to be the case that there’s no value of x which is particularly likely. That is, x has to be chosen from a set that’s, in some sense, very spread out. So that this method for the adversary of just trying all the possible values of x, or just trying few values of x that are especially likely, is not going to work. In questo scenario è facile trovare quale fosse la stringa di input, è facile trovare x. Calcoli semplicemente l’hash della stringa “teste” e l’hash della stringa “croce”, e vedi quale hai ottenuto. E così, in un paio di passaggi, puoi capire che cosa fosse x. Quindi il motivo per cui questo esempio è fallito, è il motivo per cui un avversario è stato in grado di indovinare quale fosse la stringa, era che c’erano solo un paio di valori possibili di x. E così, se avremo una proprietà nascosta come questa, è necessario che non ci sia alcun valore di x che è particolarmente probabile. Cioè, x deve essere scelto da un set che, in un certo senso, è molto diffuso. In modo che questo metodo per l’avversario di provare tutti i possibili valori di x, o semplicemente provare alcuni valori di x che sono particolarmente probabili, non funzionerà.
01.01.10
So the hiding property that we are going to need to set up is a little bit more complicated. And the way we’re gonna fix this problem with the common value x, like heads and tails, is we’re gonna take the x. And we’re gonna put next to it, we’re gonna concatenate with it, a value, r, which is chosen from a distribution that’s really spread out.

And so this H(r | x), that means take all the bits of r, and put after them all the bits of x. And so what we’re going to say is given the hash of r together with x, that it’s infeasible to find x. And that this will be true in the formally stated property that, if r is a random value chosen from a distribution that has high min-entropy, then, given H(r | x), it’s infeasible to find x. And what does high min-entropy mean? Well, it captures this intuitive idea that r is chosen from a distribution that’s really spread out. And what that means specifically is that there is no particular value that r could have had, that would occur with more than a negligible probability. So, for xample, if r is chosen uniformly from among all of the strings that are 256 bits long, then any particular string was chosen with probability 1 in 2 to the 256, which is truly a negligible value. So, as long as r was chosen that way, then the hash of r concatenated with x is going to hide x. And that’s the hiding property that the hash function will be deemed to have.
Quindi la proprietà nascosta che avremo bisogno di impostare è un po’ più complicata. E il modo in cui risolveremo questo problema con il valore comune x, come testa e croce, è che prenderemo la x. E ci metteremo vicino, ci concateneremo con esso, un valore, r, che viene scelto da una distribuzione che è davvero diffusa.

E così questo H (r | x), che significa prendere tutti i bit di r, e mettere dopo di loro tutti i bit di x. E quindi quello che stiamo per dire è dato l’hash di r insieme a x, che è impossibile trovare x. E questo sarà vero nella proprietà formalmente dichiarata che, se r è un valore casuale scelto da una distribuzione che ha un’alta min entropia, allora, dato H (r | x), è impossibile trovare x. E cosa significa alta min entropia? Bene, cattura questa idea intuitiva che viene scelta da una distribuzione che è davvero diffusa. E ciò che significa in particolare è che non esiste un particolare valore che avrebbe potuto avere, che si sarebbe verificato con una probabilità più che trascurabile. Quindi, per esempio, se r viene scelto in modo uniforme tra tutte le stringhe lunghe 256 bit, allora ogni stringa particolare è stata scelta con probabilità 1 in 2 su 256, il che è veramente un valore trascurabile. Quindi, fintanto che r è stato scelto in questo modo, l’hash di r concatenato con x sta per nascondere x. E questa è la proprietà nascosta che si suppone che la funzione di hash abbia.
 
01.01.11
Okay, now let’s look at an application of that hiding property. And, in particular, what we wanna do is something called a commitment. And this is kind of the digital analogy of taking a value, a number, and sealing it in an envelope, and putting that envelope out on the table, where everyone can see it. Now, when you do that, you’ve committed to what’s in the envelope.

But you haven’t opened it, it’s secret from everyone else. Later, you can open the envelope and get out the value, but it’s sealed. So commit to a value and reveal it later. We wanna do that in a digital sense.
Ok, ora guardiamo un’applicazione di quella proprietà nascosta. E, in particolare, quello che vogliamo fare è qualcosa chiamato impegno. E questo è un po’ l’analogia digitale di prendere un valore, un numero e sigillarlo in una busta, e mettere quella busta sul tavolo, dove tutti possono vederla. Ora, quando lo fai, ti impegni a quello che c’è nella busta.

Ma non l’hai aperto, è segreto da tutti gli altri. Più tardi, puoi aprire la busta e ottenere il valore, ma è sigillato. Quindi impegnarsi in un valore e rivelarlo in seguito. Vogliamo farlo in senso digitale.
01.01.12
So, to be more specific about what is the API that we’re going to provide here, the commitment API looks like this, that there are two things you can do. First, you can commit to a message. And that’s going to return two values, a commitment and a key. Think of the commitment as the envelope that you’re gonna put on the table, and the key as a secret key for unlocking the envelope. Then later, you allow someone else to verify, given the commitment and given a key, which you’ve told them in the meantime, and the message. So they can verify that that commitment, key, and message really do go together. And this will return a true or false. Okay, now to seal an msg in an envelope, what we do is we commit to the message. And that returns a commitment and a key, and then we publish the commitment. That’s putting the envelope on the table. Now, later, to open the envelope, what we’re going to do is publish the key and the message that we committed to. And then anybody can use this verify call, with the commitment that we published previously, the key and message that we just announced, to check the validity of our opening the envelope. Okay, and the property, of course, we want from this, is that it behaves like sealing an envelope. Quindi, per essere più specifici su quale sia l’API che forniremo qui, l’API di impegno appare così, che ci sono due cose che puoi fare. Innanzitutto, puoi impegnarti in un messaggio. E questo restituirà due valori, un impegno e una chiave. Pensa all’impegno come alla busta che porterai sul tavolo e alla chiave come chiave segreta per sbloccare la busta. Successivamente, consenti a qualcun altro di verificare, dato l’impegno e la chiave fornita, che hai detto loro nel frattempo, e il messaggio. Quindi possono verificare che quell’impegno, la chiave e il messaggio vanno davvero insieme. E questo restituirà un vero o falso. Ok, ora per sigillare un messaggio in una busta, ciò che facciamo è che ci impegniamo a trasmettere il messaggio. E ciò restituisce un impegno e una chiave, e quindi pubblichiamo l’impegno. Questo sta mettendo la busta sul tavolo. Ora, più tardi, per aprire la busta, quello che faremo è pubblicare la chiave e il messaggio a cui ci siamo impegnati. E poi chiunque può usare questa chiamata di verifica, con l’impegno che abbiamo pubblicato in precedenza, la chiave e il messaggio che abbiamo appena annunciato, per verificare la validità della nostra apertura. Ok, e la proprietà, ovviamente, vogliamo da questo, è che si comporta come chiudere una busta.
01.01.13
And, in particular, the two security properties are these. First, given com, the commitment, the envelope on the table, that someone just looking at the envelope can’t figure out what the message is.

The second property is that it’s binding, that when you commit to what’s in the envelope, you can’t change your mind later. That is, it’s infeasible to find two different messages, such that you can commit to one message, and then later claim that you committed to another, and the whole thing will verify.
In particolare, le due proprietà di sicurezza sono queste. Innanzitutto, dato com, l’impegno, la busta sul tavolo, che qualcuno che guarda la busta non può capire quale sia il messaggio.

La seconda proprietà è che è vincolante, che quando ti impegni a quello che c’è nella busta, non puoi cambiare idea in seguito. Cioè, è impossibile trovare due messaggi diversi, in modo tale che tu possa impegnarti in un solo messaggio, e poi rivendicare che ti impegni in un altro, e l’intera cosa verificherà.
01.01.14
Okay, so how do we know that these two properties hold? Well, first we need to talk about how we’re actually gonna implement commitments. And the way we’re gonna implement commitments is like this.

That in order to commit to a value message, we’re going to generate a random 256 bit value and call it the key. And then we’re going to, as the commitment, return the hash of the key concatenated together with the message. And as the key value, we’re going to return H of this key. And then later, to verify, someone is going to compute this same hash of the key they were given, concatenated with the message. And they’re gonna check whether that’s equal to the commitment that they saw, okay? So this is a way of using hash functions of both in the commitment and in the verification. So now the security properties. If we go down to the security properties that were at the bottom of the previous slide, and we just plug in the definitions of how we’re going to implement this here. That is, this used to say com, given com infeasible to find msg, we just plug in what com is. Com is the hash of key concatenated with msg. And similarly down here, this is what happens when we take what was written there before and plug in the definition of verify in com. Okay, so now what these properties become, the first one is given H(key | msg), it’s infeasible to find msg. Well, it turns out that that’s exactly the hiding property that we talked about before. Key was chosen random 256-bit value. And therefore, the hiding property says that if we take the message, and we put before it something that was chosen from a very spread out distribution, like I said a random 256-bit value, then it’s infeasible to find the message. So this is exactly the hiding property. And this one down here turns out to be exactly the collision-free property. So that if someone can find two messages which have the same hash like this, well then they have an input value here and an input value there that are different, and yet those have the same hash. And so because of the two security properties we’ve talked about for hashes so far, this commitment scheme will work, in the sense that it will have the necessary security properties. Okay, so that’s the second security property of hashes, that they’re hiding. And the application of that is commitments.
Ok, allora come facciamo a sapere che queste due proprietà valgono? Bene, per prima cosa dobbiamo parlare di come implementeremo effettivamente gli impegni. E il modo in cui implementeremo gli impegni è come questo.

Per poter inviare un messaggio di valore, genereremo un valore casuale a 256 bit e chiameremo la chiave. E poi stiamo andando, come impegno, a restituire l’hash della chiave concatenata insieme al messaggio. E come valore chiave, restituiremo H di questa chiave. E poi, per verificare, qualcuno calcolerà lo stesso hash della chiave che gli è stata data, concatenata con il messaggio. E controlleranno se è uguale all’impegno che hanno visto, ok? Quindi questo è un modo di usare le funzioni hash sia nell’impegno che nella verifica. Quindi ora le proprietà di sicurezza. Se andiamo alle proprietà di sicurezza che erano nella parte inferiore della diapositiva precedente, e inseriamo semplicemente le definizioni di come implementeremo questo aspetto qui. Cioè, questo era solito dire com, dato che non è possibile trovare msg, basta collegare ciò che è. Com è l’hash della chiave concatenato con msg. E allo stesso modo qui sotto, questo è quello che succede quando prendiamo ciò che è stato scritto lì prima e inseriamo la definizione di verifica in com. Ok, ora che cosa diventano queste proprietà, la prima è data H (chiave | msg), è impossibile trovare msg. Bene, si scopre che questa è esattamente la proprietà nascosta di cui abbiamo parlato prima. La chiave è stata scelta a caso valore a 256-bit. E quindi, la proprietà nascosta dice che se prendiamo il messaggio, e mettiamo prima di esso qualcosa che è stato scelto da una distribuzione molto diffusa, come ho detto un valore casuale a 256-bit, allora è impossibile trovare il messaggio. Quindi questa è esattamente la proprietà nascosta. E questo qui sotto si rivela essere esattamente la proprietà esente da collisione. In modo che se qualcuno può trovare due messaggi che hanno lo stesso hash come questo, allora hanno qui un valore di input e un valore di input diverso, eppure hanno lo stesso hash. E così, a causa delle due proprietà di sicurezza di cui abbiamo parlato finora per gli hash, questo schema di impegno funzionerà, nel senso che avrà le proprietà di sicurezza necessarie. Ok, questa è la seconda proprietà di sicurezza degli hash, che si stanno nascondendo. E l’applicazione di questo è impegno.
 
01.01.15
The third security property we’re going to need is that they’re puzzle-friendly. And this is, again, a little bit more complicated, but let me just go through it bit by bit. That for any possible output value y that you might want from the hash function. We’re going to use y as an output value of the hash later. That if k is chosen from a distribution that has high min-entropy. That is, k is chosen randomly from some set that’s super spread out. Then there’s no way to find an x, such that the hash of k and x is equal to y. So, what this means is basically that if someone wants to target the hash function, if they want it to come out to some particular output value y. That if there’s part of the input that is chosen in a suitably randomized way, that it’s very difficult to find another value that hits exactly that target. So the application we’re going to use of this, is we’re going to build a search puzzle. And what that means is we’re going to build a mathematical problem, which requires searching a very large space in order to find the solution. And where there’s no shortcuts, a way to find a good solution, other than searching that large space. That’s a search puzzle. La terza proprietà di sicurezza di cui avremo bisogno è che siano puzzle-friendly [adatti al rompicapo!!]. E questo è, ancora una volta, un po’ più complicato, ma lasciatemi solo esaminarlo un po’ alla volta. Quello per qualsiasi possibile valore di output che potresti desiderare dalla funzione hash. Utilizzeremo y come valore di output dell’hash in seguito. Che se k è scelto da una distribuzione che ha alta min entropia. Cioè, k viene scelto in modo casuale da un set che è molto diffuso. Quindi non c’è modo di trovare una x, tale che l’hash di k e x sia uguale a y. Quindi, ciò significa in sostanza che se qualcuno vuole indirizzare la funzione di hash, se vuole che venga fuori ad un particolare valore di output y. Che se c’è una parte dell’input che viene scelta in un modo opportunamente randomizzato, è molto difficile trovare un altro valore che colpisca esattamente quell’obiettivo. Quindi, l’applicazione che useremo di questo, è che stiamo per costruire un puzzle di ricerca. E ciò significa che stiamo per costruire un problema matematico, che richiede la ricerca di uno spazio molto grande per trovare la soluzione. E dove non ci sono scorciatoie, un modo per trovare una buona soluzione, oltre a cercare quello spazio grande. Questo è un puzzle di ricerca.
 
01.01.16
To be more specific, the idea is that if we’re given a puzzle ID, which is chosen from some high min-entropy distribution. That is some very spread out probability distribution. And we’re given a target set, Y, which someone wants to make the hash function fall into. Then we wanna try to find a solution, x. So that if we hash the puzzle ID together with the solution X, we get a result that’s in the set Y. So the idea is Y is a target range or a set of hash results that we want. ID specifies a particular puzzle, and x is a solution to the puzzle.

And the puzzle-friendly property here implies that there’s no solving strategy for this puzzle, which is much better than just trying random values of x. And so if we wanna pose a puzzle that’s difficult to solve, that we can do it this way, as long as we can generate puzzle IDs in a suitably random way. And we’re going to use that later when we talk about bitcoin mining. That’s the sort of computational puzzle we’re going to use. Okay, so we’ve talked about three properties of hash functions and one application of each of those.
Per essere più specifici, l’idea è che se ci viene dato un puzzle ID, che viene scelto da una distribuzione ad alta min entropia. Questa è una distribuzione di probabilità molto diffusa. E ci viene assegnato un set di obiettivi, Y, a cui qualcuno vuole far cadere la funzione di hash. Allora vogliamo provare a trovare una soluzione, x. In modo che se abbiamo l’ID del puzzle insieme alla soluzione X, otteniamo un risultato che si trova nel set Y. Quindi l’idea è Y è un intervallo di destinazione o un insieme di risultati di hash che vogliamo. ID specifica un particolare puzzle, e x è una soluzione al puzzle.

E la proprietà amichevole dei puzzle qui implica che non esiste una strategia di risoluzione per questo puzzle, che è molto meglio che provare solo valori casuali di x. Quindi, se vogliamo creare un puzzle che è difficile da risolvere, possiamo farlo in questo modo, a patto che possiamo generare ID puzzle in modo appropriato. E lo useremo più tardi quando parliamo di bitcoin mining. Questo è il tipo di puzzle computazionale che useremo. Ok, abbiamo parlato di tre proprietà delle funzioni hash e di una di ognuna di queste.
 
01.01.17
Now let me talk just very briefly about the particular hash function we’re going to use. There are lots of hash functions in existence, but this is the one bitcoin uses, and it’s a pretty good one to use. It called SHA-256 or SHA-256, and it works like this. Basically, it takes the message that you’re hashing, and it breaks it up into blocks that are 512 bits in size. The message isn’t gonna be, in general, necessarily exactly a multiple of the block size, so we’re going to add some padding at the end. And the padding is gonna consist of, at the end of the padding, a 64 bit length field, which is the length of the message in bits. And then before that, it’s gonna consist of a one bit, followed by some number of zero bits. And you choose the number of zero bits so that this comes out exactly to the end of a block. So once you’ve padded the message so that its length is exactly a multiple of the 512 bit block size, you then chop it up into blocks, and you then execute this computation. You start with the 256 bit value called the IV. That’s just a number that you look up in a standards document. And then take the IV and the first block of the message. You take those 768 total bits, and you run them through this special function, c, the compression function, and out comes 256 bits. You now take that with the next 512 bits of the message, run it through c again, and you keep going. Each iteration of c crunches in another 512 bit block of the message and mixes it in, sort of logically to the result. And when you get to the very end, you have consumed all of the blocks of the message plus the padding. The result is the hash, that’s a 256 bit value. And it’s easy to show that, if this function, c, this compression function is collision free, then this entire hash function will also be collision free. The other properties are a little bit more complicated, so I won’t talk about them here.

Okay, so we’ve talked hash functions. We’ve talked about what hash functions do. We’ve talked about three properties of hash functions and applications of those properties, and the specific hash function that we use in bitcoin. In the next lecture segment, we’ll talk about ways of using hash functions to build more complicated data structures that are used in distributed systems like bitcoin.
Ora lasciatemi parlare molto brevemente della particolare funzione di hash che useremo. Esistono molte funzioni hash, ma questo è l’unico bitcoin utilizzato ed è piuttosto buono da usare. È chiamato SHA-256 o SHA-256 e funziona così. Fondamentalmente, prende il messaggio che stai facendo l’hashing e lo scompone in blocchi che hanno una dimensione di 512 bit. Il messaggio non sarà, in generale, necessariamente esattamente un multiplo della dimensione del blocco, quindi aggiungeremo del padding alla fine. E il padding sarà costituito, alla fine del padding, da un campo a 64 bit, che è la lunghezza del messaggio in bit. E prima, sarà composto da un bit, seguito da un certo numero di bit zero. E tu scegli il numero di bit zero in modo che questo esca esattamente alla fine di un blocco. Quindi, una volta riempito il messaggio in modo che la sua lunghezza sia esattamente un multiplo della dimensione del blocco di 512 bit, lo si riduce in blocchi e quindi si esegue questo calcolo. Si inizia con il valore a 256 bit chiamato IV. Questo è solo un numero che cerchi in un documento standard. E poi prendi la IV e il primo blocco del messaggio. Si prendono quei 768 bit totali e li si esegue attraverso questa funzione speciale, c, la funzione di compressione e l’uscita arriva a 256 bit. Ora lo prendi con i successivi 512 bit del messaggio, eseguilo nuovamente attraverso c, e continui ad andare avanti. Ogni iterazione di c crunch in un altro blocco di 512 bit del messaggio e lo mescola, in modo logico al risultato. E quando arrivi alla fine, hai consumato tutti i blocchi del messaggio più il padding. Il risultato è l’hash, che è un valore di 256 bit. Ed è facile dimostrare che, se questa funzione, c, questa funzione di compressione è libera da collisioni, allora anche questa intera funzione di hash sarà priva di collisioni. Le altre proprietà sono un po ‘più complicate, quindi non ne parlerò qui.

Ok, quindi abbiamo parlato delle funzioni hash. Abbiamo parlato di quali funzioni hash fanno. Abbiamo parlato di tre proprietà delle funzioni di hash e delle applicazioni di tali proprietà e della funzione di hash specifica che usiamo in bitcoin. Nel prossimo segmento di conferenze, parleremo dei modi di usare le funzioni hash per costruire strutture dati più complicate che vengono utilizzate in sistemi distribuiti come bitcoin.

[top]

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

 

Tecnologie di Bitcoin e delle Criptovalute
Indice
W01.02
Puntatori Hash e Strutture di Dati