W01.02 – PUNTATORI HASH E STRUTTURE DI DATI


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.02 – Puntatori Hash e Strutture di Dati
01.02.01
In section 1.2, we’re going to talk about Hash Pointers and their application. A hash pointer is a kind of data structure that turns out to be used a lot in the systems that we’re talking about. And a hash pointer is basically a simple thing, that we’re going to take a pointer to where some information is stored. And we’re going to together with the pointer store a cryptographic hash of the information.

So whereas a regular pointer gives you a way to retrieve the information. A hash pointer is gonna let us ask to get the information back.

It’s also gonna let us verify that the information hasn’t changed. So a hash pointer tells us where something is and what it’s value was.
Nella sezione 1.2, parleremo di Hash Pointer e della loro applicazione. Un puntatore hash è una sorta di struttura dati che risulta essere utilizzata molto nei sistemi di cui stiamo parlando. Un puntatore hash è fondamentalmente una cosa semplice, va a prendere un puntatore in cui sono memorizzate alcune informazioni. E insieme al puntatore memorizza un hash crittografico delle informazioni.

Quindi, mentre un puntatore regolare ti dà un modo per recuperare le informazioni. Un puntatore hash ci consentirà di chiedere di ottenere le informazioni indietro.

Ci consentirà anche di verificare che le informazioni non siano cambiate. Quindi un puntatore hash ci dice dove si trova qualcosa e qual è il suo valore.
01.02.02
And we’re gonna draw a hash pointer in diagrams like this. That we’re gonna have each of, and then an arrow that points to something. So anything drawn like this, think of it as being a hash pointer to this thing. It’s a pointer to where it’s stored and it’s also the hash of the value that this data had when we last saw it.

And we can take hash pointers and we can use them to build all kinds of data structures.
Disegneremo un puntatore hash come questo nei diagrammi. E avremo ognuno di questi, e quindi una freccia che punta a qualcosa. Quindi, qualsiasi cosa sia disegnata in questo modo, va pensata come un puntatore di hash su questa cosa. È un puntatore a dove è memorizzato ed è anche l’hash del valore che questi dati hanno avuto quando l’abbiamo visto l’ultima volta.

E possiamo prendere i puntatori hash e possiamo usarli per costruire tutti i tipi di strutture dati.
 
01.02.03
So a key idea here: take any data structure or link lists or binary search tree or something like that and implement it with hash pointers instead of pointers as we normally would. Idea chiave, prendi qualsiasi struttura di dati o elenchi di link o albero di ricerca binario o qualcosa del genere e implementalo con puntatori hash invece di puntatori come faremmo normalmente.
 
01.02.04
For example here is a linked list that we built with hash pointers. And this is a data structure that we’re gonna call a block chain.

So just like a regular linked list where you have a series of blocks and each block has data as well as a pointer to the previous block in the list, here the previous block pointer will be replaced with a hash pointer.

So it says where it is and what the value of this entire previous block was. And we’re going to store, we’re gonna remember the head of the list like this. Just as a regular hash pointer. And a use case for this for a block train like this is a tamper evident log, that is if we wanna build a log data structure that stores a bunch of data.

So that we can add data onto the end of the log but if somebody goes later and messes with data that is earlier in the log we’re going to be detect it. That’s what tamper evidence means. So to understand why a block chain gives us this tamper evident property. Let’s ask what happens if an adversary wants to go back and tamper with data later that’s in the middle of the chain.
Ad esempio, ecco un elenco collegato che abbiamo creato con puntatori hash. E questa è una struttura dati che chiameremo una catena di blocchi.

Quindi, proprio come una normale lista concatenata in cui hai una serie di blocchi e ogni blocco ha dati e un puntatore al blocco precedente nell’elenco, qui il precedente puntatore al blocco verrà sostituito con un puntatore hash.

Quindi dice dove si trova e qual è il valore di questo intero blocco precedente. E stiamo per immagazzinare, ricorderemo la testa della lista come questa. Proprio come un normale puntatore di hash. E un caso d’uso per questo per un treno a blocchi come questo è un registro a prova di manomissione, cioè se vogliamo costruire una struttura di dati di registro che memorizzi un mucchio di dati.

Possiamo aggiungere dati alla fine del log, ma se qualcuno va più tardi e ha problemi con i dati che si trovano prima nel log, lo rileveremo. Questo è ciò che si intende per prova di manomissione. Quindi capiamo perché una catena di blocchi ci dà questa proprietà di manomissione.
Chiediamoci cosa succede se un avversario vuole tornare indietro e manomettere i dati più avanti nel mezzo della catena.
 
01.02.05
So let’s assume that an adversary wants to tamper with this block down here. He wants to change the data here. And he wants to do it in such a way that we, the holders of the hash pointer at the head here, won’t be able to detect it.

So the adversary changed the contents of this block. And therefore, the hash here which is a hash of this entire block is not going to mash up because the hash function is collision free, it must be the case that the hash of this block is now different. And so we could detect the inconsistency between this data and the hash pointer that we remembered before or we could do that unless the advisory allows tampers with the hash pointer.
Supponiamo che un avversario voglia manomettere questo blocco quaggiù. Vuole cambiare i dati qui. E vuole farlo in modo tale che noi, i detentori del puntatore dell’hash in testa qui, non saremo in grado di rilevarlo.

L’avversario ha cambiato il contenuto di questo blocco. E quindi, l’hash qui che è un hash di questo intero blocco non sta andando a mescolare/schiacciare perché la funzione hash è libera da collisioni, deve essere il caso che l’hash di questo blocco è ora diverso. E così abbiamo potuto rilevare l’inconsistenza tra questi dati e il puntatore hash che abbiamo ricordato in precedenza o che potremmo fare a meno che l’advisory non permetta di manomettere il puntatore dell’hash.
01.02.06
If he tampers with this hash pointer then he makes these two match up. But now he’s changed the content of this block. And what that means is that when we come back later and hash the contents of this block, it’s not going to match the hash that we remembered before because the contents of the block has changed. Se manomette questo puntatore di hash, fa questi due match. Ma ora ha cambiato il contenuto di questo blocco. E ciò significa che quando torneremo indietro e cancelleremo il contenuto di questo blocco, non corrisponderà all’hash che abbiamo ricordato prima perché il contenuto del blocco è cambiato.
01.02.07
And so we’re going to detect the inconsistency between the contents of this block and this hash, unless the adversary also tampers with the block over here on the right. But now, when he does that, the hash of this block is not going to match the hash that we remembered up here and the hash that we’re holding on to. And this the adversary can’t tamper with because this is the value that we remembered as being the head of the list. And so the upshot of this is that if the adversary wants to tamper with data anywhere in this entire chain, in order to keep the story consistent he’s going to have to tamper with hash pointers all the way back to the beginning. And he’s ultimately going to run into a road block because he’s wont be able to tamper with the head of the list.

And so what this means is that just by remembering this hash pointer, we’ve essentially remembered a kind of hash, a tamper evident hash of the entire list all the way back to the beginning. And so we can build a block chain like this containing as many blocks as we want going back to some special block at the beginning of the list which we might call the genesis block. And that’s a tamper evidence log built out of the block chamber.
Quindi rileveremo l’incoerenza tra il contenuto di questo blocco e questo hash, a meno che l’avversario non manchi anche il blocco qui a destra. Ma ora, quando lo fa, l’hash di questo blocco non corrisponderà all’hash che abbiamo ricordato qui sopra e all’hash su cui ci stiamo aggrappando. E questo l’avversario non può manomettere perché questo è il valore che abbiamo ricordato come il capo della lista. E così il risultato è che se l’avversario vuole manomettere i dati in qualsiasi parte dell’intera catena, al fine di mantenere la trama coerente, dovrà manomettere i puntatori di hash fino all’inizio. E alla fine si imbatterà in un blocco stradale perché non sarà in grado di manomettere il capo della lista.

Quindi ciò che significa è che semplicemente ricordando questo puntatore di hash, abbiamo essenzialmente ricordato una specie di hash, un hash antimanomissione dell’intero elenco fino all’inizio. E così possiamo costruire una catena di blocchi come questa che contiene tanti blocchi quanti vogliamo tornare ad un blocco speciale all’inizio della lista che potremmo chiamare il blocco genesis. E questo è un registro delle manomissioni ricavato dalla camera di blocco.
01.02.08
Now, another useful data structure that we can build using hash pointers is a binary tree. We can build a binary tree with hash pointers and this is called in the jargon, a Merkle tree after Ralph Merkle who invented it.

And the idea is this, suppose we have a bunch of data blocks which we’ll draw across the bottom down here. We’re going to take consecutive pairs of these data blocks and for these two data blocks we’re going to build a data structure here that has two hash pointers, one to each of these blocks, and similarly all the way across. We’ll then go another level up and this block here will contain a hash pointer of these two children down here. And so on, all the way back up to the root of the tree. And then just like before we’re going to remember just the hash pointer up here at the head of the tree. And we can then, if we want traverse down through the hash pointers to any point in the list.

And we can make sure that the data hasn’t been tampered with. Because just like I showed you with the block chain, if an adversary tampers with some block down here at the bottom with the data that will cause the hash pointer that’s one level up to not match. So he’ll have to tamper with that. And therefore, he’ll have to tamper with the hash pointer one level up from there. And eventually he’ll get up to the top, where he won’t be able to tamper with the hash pointer that we’ve remembered. So again, any attempt to tamper with any piece of data across the bottom will be in short against, by just remembering the hash pointer at the top.

Now, another nice feature about Merkle trees, is that unlike the block chain that we built before, that if someone wants to prove to us that a particular data block is a member of this Merkle tree. All they need to show us is this amount of data.
Un’altra utile struttura di dati che possiamo costruire usando i puntatori di hash è un albero binario. Possiamo costruire un albero binario con puntatori di hash e questo è chiamato in gergo, un albero Merkle dopo Ralph Merkle che l’ha inventato.

L’idea è questa, supponiamo di avere un sacco di blocchi di dati che disegneremo in fondo qui. Prenderemo due coppie consecutive di questi blocchi di dati e per questi due blocchi di dati creeremo qui una struttura di dati con due puntatori di hash, uno per ciascuno di questi blocchi e in modo simile per tutto il percorso. Poi andremo su un altro livello e questo blocco conterrà un puntatore hash di questi due figli quaggiù. E così via, fino alla radice dell’albero. E poi proprio come prima ricorderemo solo il puntatore dell’hash qui in cima all’albero. E possiamo quindi, se vogliamo attraversare i puntatori di hash in qualsiasi punto della lista.

E possiamo assicurarci che i dati non siano stati manomessi. Perché proprio come ti ho mostrato con la catena di blocchi, se un avversario manomette qualche blocco in basso nella parte inferiore con i dati che causeranno il puntatore hash di un livello non corrispondente. Quindi dovrà manometterlo. E quindi, dovrà manomettere il puntatore dell’hash un livello più in alto da lì. E alla fine salirà in cima, dove non sarà in grado di manomettere il puntatore dell’hash che abbiamo ricordato. Quindi, di nuovo, qualsiasi tentativo di manomettere qualsiasi parte di dati sul fondo sarà in breve contro, semplicemente ricordando il puntatore dell’hash in alto.

Ora, un’altra bella caratteristica degli alberi di Merkle è che, a differenza della catena di blocchi che abbiamo costruito prima, che se qualcuno vuole dimostrarci che un particolare blocco di dati è un membro di questo albero Merkle. Tutto ciò di cui hanno bisogno per mostrarci è questa quantità di dati.
01.02.09
So if we remember just the root and someone wants to convince us that this block is in the Merkle tree, they need to show us this block. And we can verify that the hash matches up. And then they need to show us this block and we can verify that the hash of this matches that. They can show us this block. We verify that the hash of this block matches this hash pointer. And then they show us the data. And just by verifying the hashes up to the root, we can ensure, we can verify that this data block was in the Merkle tree. So that takes about log n items that we need to be shown, and it takes about log n time for us to verify it. And so at the very large number of data blocks in the Merkle tree, we can still verify proven membership in a relatively short time. Quindi, se ricordiamo solo la radice e qualcuno vuole convincerci che questo blocco si trova nell’albero Merkle, devono mostrarci questo blocco. E possiamo verificare che l’hash corrisponda. E poi hanno bisogno di mostrarci questo blocco e possiamo verificare che l’hash di questo corrisponde a quello. Possono mostrarci questo blocco. Verifichiamo che l’hash di questo blocco corrisponda a questo puntatore di hash. E poi ci mostrano i dati. E solo verificando gli hash fino alla radice, possiamo assicurarci che possiamo verificare che questo blocco di dati si trovasse nell’albero Merkle. In questo modo sono necessari gli elementi log n che dobbiamo mostrare, e ci vuole tempo log n per noi per verificarlo. E così al numero molto grande di blocchi di dati nell’albero Merkle, possiamo ancora verificare l’adesione comprovata in un tempo relativamente breve.
01.02.10
So Merkle trees have various advantages.

One advantage of course, is the tree holds many items but we just need to remember the one root hash which is only 256 bits. We can verify membership in a Merkle tree in logarithmic time and logarithmic space. That’s nice. And there’s a variant which is a sorted Merkle tree. That’s just a Merkle tree where we take the blocks at the bottom and we sort them into some order. Say alphabetical, lexicographic or numeric order or some order that we agree on. Having done that, once we’ve sorted the Merkle tree now, it’s possible to verify non-membership in a Merkle tree. That is, we can prove that a particular block is not in the Merkle tree. And the way we do that is simply by showing a path to the item that’s just before where that item would be and just after where it would be. And then we can say look, both of these items are in the Merkle tree, they’re consecutive. And therefore there is no space in between them. There is nothing in between them and so the thing that we are trying to prove non-membership of can’t be there. Merkle tree is binary search tree, built with hash pointers, we can do logarithmic time membership proofs, non-membership proofs if we sort the tree and it is very efficient.
Quindi gli alberi di Merkle hanno diversi vantaggi.

Un vantaggio, naturalmente, è che l’albero contiene molti elementi, ma dobbiamo solo ricordare l’hash di una radice che è solo 256 bit. Possiamo verificare l’appartenenza a un albero Merkle in tempo logaritmico e spazio logaritmico. Bello. E c’è una variante che è un albero Merkle ordinato. Quello è solo un albero Merkle dove prendiamo i blocchi in fondo e li ordiniamo in un certo ordine. Un ordine alfabetico, lessicografico o numerico o un ordine su cui siamo d’accordo. Fatto ciò, una volta che abbiamo ordinato l’albero Merkle ora, è possibile verificare la non appartenenza a un albero Merkle. Cioè, possiamo provare che un particolare blocco non è nell’albero Merkle. E il modo in cui lo facciamo è semplicemente mostrando un percorso per l’oggetto che è appena prima dove quell’elemento sarebbe e subito dopo dove sarebbe. E poi possiamo dire guarda, entrambi questi elementi sono nell’albero Merkle, sono consecutivi. E quindi non c’è spazio tra loro. Non c’è niente in mezzo a loro e quindi la cosa che stiamo cercando di dimostrare non appartenenza non può esserci. L’albero di Merkle è un albero di ricerca binario, costruito con puntatori di hash, possiamo fare prove logaritmiche sull’appartenenza al tempo, prove di non appartenenza se ordiniamo l’albero ed è molto efficiente.
01.02.11
More generally, it turns out that we can use has pointers in any pointer-based data structure as long as the data structure doesn’t have cycles. If there are cycles in the data structure, then we won’t be able to make all hashes match up. If you think about it in an acyclic data structure, we can sort of start near the lees or near the things that don’t have any pointers coming out of them compute the hashes of those and then work our way back, sort of towards the beginning. But in a structure with cycles, there’s no end that we can start with and compute back from. So for example, a directed acyclic graph, out of hash pointers and we’ll be able to verify membership in that day very efficiently. And it’ll be easy to compute. So this is a general trick you’ll see over and over throughout the distributed data structures and throughout the algorithms that we talk about later in this lecture and in subsequent lectures. Più in generale, si scopre che possiamo usare i puntatori in qualsiasi struttura di dati basata su puntatore, purché la struttura dei dati non abbia cicli. Se ci sono cicli nella struttura dei dati, allora non saremo in grado di far coincidere tutti gli hash. Se ci pensi in una struttura dati aciclica, possiamo iniziare in prossimità delle fecce o vicino alle cose che non hanno alcun suggerimento che esce da loro calcolare gli hash di quelli e poi tornare indietro, un pò verso l’inizio. Ma in una struttura con cicli, non c’è fine da cui partire e da cui partire. Quindi, ad esempio, un grafico aciclico diretto, con puntatori di hash e saremo in grado di verificare l’appartenenza in quel giorno in modo molto efficiente. E sarà facile da calcolare. Quindi questo è un trucco generale che vedrai più e più volte nelle strutture di dati distribuiti e in tutti gli algoritmi di cui parleremo più avanti in questa lezione e nelle conferenze successive.

[top]

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

W01.01
Funzione di Hash Crittografica
W01.03
Firme digitali