Gli alberi di Merkle

Gli alberi di Merkle ci permettono di verificare se un dato è contenuto/compreso all'interno di una struttura di dati più grande, senza il vincolo di dover avere tutti i dati di quella struttura. Ciò significa che possono essere utilizzati per verificare le incoerenze in tutti i tipi di sistemi distribuiti, che è la funzione che ci interessa di più :)

Per le blockchain ed i sistemi distribuiti, la memorizzazione delle transazioni come alberi di Merkle ci permette di esaminare un blocco e verificare che una transazione ne faccia parte, disponendo solo di una parte dei dati!

Ricordate che i dati di un blocco blockchain sono, semplificando, un insieme di transazioni.

Vediamo un esempio.

Albero di Merkle ipotetico: ABCDEFGHIJ

In questo albero ogni lettera rappresenta un hash, e le lettere combinate rappresentano la concatenazione degli hash e l'hashing di questi ultimi.

      Radice 
        / \
    ABCD EFGHIJ
     | / \
    ABCD EFGH IJ
    / \ / \ |
   AB CD EF GH IJ
  / \ / \ / \ / \ / \      
  A B C D E F G H I J

Per dimostrare che l'hash A fa parte della Radice di Merkle non è necessario conoscere gli hash C o D, ma solo l'hash CD. La prova necessaria per A è:

🧠 Hash(Hash(A + B) + CD) + EFGHIJ) ,

nella quale abbiamo bisogno di conoscere solo gli hash B, CD e EFGHIJ per dimostrare che A è nella radice di Merkle.

Se tutto questo vi sembra senza senso, non preoccupatevi :)

Presto uniremo i puntini ("looking backwards") e torneremo su questo argomento.

Combinare due foglie

Bene, costruiamo un albero di Merkle!

Un albero di Merkle prende un array di nodi foglia, combinandoli insieme due alla volta, strato per strato, fino a ridurli a un singolo nodo radice. Questo forma una struttura ad albero di hashing.

Obiettivo: radice di due foglie

Per prima cosa, scriviamo un costruttore per la classe MerkleTree. Questo costruttore accetta due argomenti passati in quest'ordine:

1) Un array di nodi foglia;
2) Una funzione di combinazione utilizzata per concatenare e fare l'hash di due foglie;

Diamo un'occhiata più da vicino alla funzione di combinazione.

Funzione di combinazione

Per semplificare l'implementazione di questo albero di Merkle e per facilitarne il debug, passeremo una funzione di combinazione al costruttore MerkleTree.

Questa funzione prenderà due argomenti: un nodo foglia sinistro e un nodo foglia destro e restituirà la combinazione risultante.

Per esempio, in un albero a quattro foglie:

  Radice   
    / \    
   AB CD
  / \ / \ 
  A B C  D

La funzione viene utilizzata tre volte, per ogni combinazione. La indicheremo qui come Hash:

Hash(Hash(A + B) + Hash(C + D))

Per prima cosa combiniamo A e B. Poi combiniamo C e D. Infine combiniamo il risultato di queste due combinazioni AB e CD per ottenere l'hash della radice.

Confronteremo poi la stringa creata con il risultato atteso.

Aggiungiamo quindi una funzione getRoot alla classe MerkleTree. Questa funzione troverà la radice di Merkle.

Come detto prima, in questa fase è necessario prendere solo due foglie e metterle in hash insieme:

  Radice
    / \ 
   A   B

In questo esempio, A e B sono i nodi foglia e la radice è il risultato della combinazione. È sufficiente prendere il primo e il secondo nodo foglia e utilizzare la funzione di combinazione per ottenere il risultato.

Non ci preoccupiamo ancora di generalizzare il nostro codice: più avanti passeremo ad uno scenario più approfondito.

In codice:

class MerkleTree {
    constructor(leaves, concat) {
        this.leaves = leaves;
        this.concat = concat;
    }
    getRoot() {
        this.root = this.concat(this.leaves[0], this.leaves[1]);
        return this.root;
    }
}

module.exports = MerkleTree;

Strati multipli

Ora è il momento di gestire un albero di Merkle più grande!

Questo albero avrà più livelli. Ad esempio, con quattro nodi foglia si combineranno i primi due nodi e poi gli ultimi due. Quindi si prenderanno i due risultati e li si combinerà per ottenere il nodo radice.

🧠 > Prima di generalizzare l'algoritmo, potrebbe essere utile rivedere lo scopo dell'albero di Merkle.

Scopo dell'albero di Merkle

Consideriamo l'esempio delle quattro foglie:

  ABCD
    / \ 
   AB CD
  / \ / \
  A B C  D

Di cosa abbiamo bisogno per dimostrare che C è compresa in ABCD?

Si potrebbe dire che abbiamo bisogno di A, B e D. Ma in realtà queste sono più informazioni di quelle che ci servono!

In realtà abbiamo bisogno solo di AB e D, infatti:

Hash(AB, Hash(C, D))

In questa derivazione di ABCD, possiamo dimenticarci di A e B. Non abbiamo bisogno di sapere cosa sono per dimostrare che C è nella Radice. Abbiamo solo bisogno di D e AB.

Questa ottimizzazione è la forza degli alberi di Merkle. Diventa ancora più evidente con alberi più grandi, dove sono necessari meno dati per dimostrare che un nodo foglia fa parte dell'albero. Un albero Merkle di 128 nodi richiede solo altri 7 hash per dimostrare che un nodo fogliare appartiene all'insieme.

Aggiornarniamo ora la funzione getRoot per gestire alberi di Merkle con più di due nodi foglia.

Nella scomposizione della logica degli alberi di Merkle, prima otteniamo l'hash di A e B, poi di C e D. Poi passiamo all'hash della combinazione di A e B (AB) con la combinazione di C e D (CD). Qualcosa del genere:

  ABCD
    / \ 
   AB CD
  / \ / \
  A B C  D

Nella stesura del codice sarà utile pensare all'albero come se avesse più livelli:

1) Il primo strato è costituito dalle foglie (A, B, C, D).
2) Il secondo è la combinazione di entrambe le combinazioni (AB, CD).
3) L'ultimo strato è la combinazione finale: la radice di Merkle (ABCD).

In ogni strato, dovremo combinare gli elementi due alla volta fino a raggiungere uno strato con un solo elemento. A quel punto possiamo fermarci, sapendo di aver trovato la radice.

Approccio consigliato

Ci sono diversi modi per affrontare la scrittura di questo algoritmo. Innanzitutto, occorre scegliere tra ricorsione e iterazione. Personalmente, trovo l'approccio ricorsivo più elegante e facile da usare. Sentitevi liberi di scegliere l'approccio con cui vi sentite più a vostro agio :)

In ogni caso, vediamo il processo mentale su come affrontare il problema.

Abbiamo un albero di Merkle con un numero arbitrario di nodi foglia. Forse è un albero a quattro foglie:

  Radice
    / \ 
   AB CD
  / \ / \
  A B C D

Forse è l'albero magico dalle otto foglie:

      Radice
       / \
    ABCD EFGH
    / \ / \
   AB CD EF GH
  / \ / \ / \ / \
  A B C D E F G H

O forse ancora peggio lol

L'approccio consigliato per questo problema è quello di suddividerlo in livelli.

Consideriamo l'albero a otto foglie. Per ogni livello, vogliamo prendere 2 nodi e combinarli.

Quindi, se ci troviamo nel livello inferiore:

• Combinare A e B per ottenere AB
• Combinare C e D per ottenere CD
• Combinare E e F per ottenere EF
• Combinare G e H per ottenere GH

Dopodiché, saliamo di livello! Il prossimo livello:

• Combinare AB e CD per ottenere ABCD
• Combinare EF e GH per ottenere EFGH

Infine:

• Combinare ABCD ed EFGH per ottenere ABCDEFGH

A ogni livello si controlla se è rimasto un solo elemento. Se rimane un solo elemento, abbiamo trovato la radice.

💡 > In alternativa, si può calcolare in anticipo quanti strati ci saranno nell'albero. In questo modo si saprà quando restituire la radice in base al numero di livelli su cui si è lavorato.

Caso 2: Gestire un numero dispari di foglie

Consideriamo ora il caso di un albero Merkle con un numero dispari di foglie.

Come fare? Possiamo adottare questa strategia: ogni volta che non abbiamo una coppia per un dato elemento, vogliamo semplicemente portare quella foglia "single" ad un livello più in alto:

   Radice
    / \ 
   AB  C
  / \  |
  A B  C

In questo caso non usiamo il nodo C finché non lo combiniamo con AB per creare la radice Merkle.
Gestiamo questa casistica nella nostra funzione getRoot.

La regola degli alberi dispari

La regola per gli alberi dispari è sempre quella di utilizzare tutto ciò che si trova sul lato sinistro prima di riempire il lato destro dell'albero.

Ipotizziamo un albero con cinque foglie: utilizziamo le prime quattro come lato sinistro e portiamo la quinta fino all'ultima combinazione.

   Radice
     /  \
    ABCD  E
    / \   |
   AB CD  E
  / \ / \ |
  A B C D E

In codice:

class MerkleTree {
    constructor(leaves, concat) {
        this.leaves = leaves;
        this.concat = concat;
    }
    // Funzione di combinazione
    combine(newLeaves, leafLength) {
        let n = leafLength;

        if (leafLength == 1) {
            // console.log(newLeaves)
            return newLeaves;
        }
        else {
            let i = 0;
            for (i = 0; i < n - 1; i += 2) {
                newLeaves[i / 2] = this.concat(newLeaves[i], newLeaves[i + 1])
            }
            newLeaves[i / 2] = newLeaves[leafLength - 1];
            return this.combine(newLeaves.slice(0, Math.ceil(leafLength / 2)), Math.ceil(leafLength / 2))
        }
    }

    getRoot() {
        // this.root = this.concat(this.leaves[0], this.leaves[1])
        // console.log(this.combine(this.leaves, this.leaves.length))
        return this.combine(this.leaves, this.leaves.length)
    }

}

module.exports = MerkleTree;