Costruire una prova di Merkle e verificarla

Nel post precedente abbiamo imparato a conoscere gli alberi di Merkle, capire a cosa servono e i loro punti di forza.

Vediamo ora come costruire una prova di Merkle, ovvero la prova che un particolare nodo foglia esiste all'interno di un dato albero

In questa verifica, vogliamo includere solo gli hash necessari per creare l'hash della radice dal nostro nodo foglia target.

Esempio di prova - Merkle ABCDE

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

Prova di C

Dimostriamo che C è compresa nella radice di Merkle!

Costruiamo il percorso per creare la radice da C:

Hash(Hash(AB + Hash(C + D)) + E)

I quattro hash utilizzati sono AB, C, D ed E. Poiché iniziamo con C, non ne avremo bisogno nella prova. Avremo bisogno di conoscere AB, D ed E.

Inoltre, dobbiamo conoscere l'ordine in cui devono essere combinati. Hash(A + B) non sarà uguale a Hash(B + A). La nostra prova deve contenere i dati (l'hash) e se il nodo si trova o meno nella posizione di sinistra.

La nostra prova risultante avrà il seguente aspetto:

[
 { dati: 'D', left: false },
 { dati: 'AB', left: true },
 { dati: 'E', left: false }
]

Osservando questa prova, possiamo facilmente ottenere la combinazione radice. Partiamo da C, concateniamo D a destra (CD), concateniamo AB a sinistra (ABCD) e poi concateniamo E a destra per ottenere la radice ABCDE.

Ma guarda un po'! Non avevamo nemmeno bisogno di conoscere A o B, ma solo l'hash combinato dei due.

Un altro esempio?

Dimostriamo che A appartiene all'albero di Merkle ABCDEFGHIJ

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

Per dimostrare che A si trova in questo albero abbiamo bisogno del seguente percorso di prova:

Hash(Hash(Hash(A + B) + CD) + EFGH) + IJ)

Avremo quindi bisogno di quattro hash: B, CD, EFGH e IJ.

[
 { dati: 'B', left: false },
 { dati: 'CD', left: false },
 { dati: 'EFGH', left: false }
 { dati: 'IJ', left: false }
]

Un albero così grande e abbiamo bisogno solo di quattro hash per dimostrare A?! Senza considerare che per I o J il risparmio sarebbe ancora maggiore in questo albero: solo due hash necessari per le loro prove. Noice :)

In codice

Tenendo a mente il codice del post precedente, aggiungiamo un metodo getProof alla nostra classe MerkleTree. Questa funzione accetta l'indice di un nodo foglia e restituisce una prova di Merkle.

*La Merkle Proof * sarà un array di oggetti con le proprietà data (l'hash) e left (un booleano che indica se l'hash è a sinistra).

Approccio consigliato

L'approccio è simile a quello seguito per l'algoritmo getRoot. Pensiamo all'algoritmo suddiviso a livelli.

Utilizziamo l'albero di Merkle ABCDE come esempio:

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

Supponiamo di voler dimostrare che C esiste nell'albero. Ci viene dato l'indice 2, che corrisponde alla posizione di C nell'array passato nel nostro costruttore dell'albero di Merkle.

Quindi iniziamo da C nel livello inferiore. Di che cosa abbiamo bisogno per prima cosa?

Dobbiamo sapere se C è il nodo sinistro o destro all'interno della sua coppia. Possiamo determinarlo controllando l'indice di C (2). Due è pari, quindi è un nodo di sinistra. Ora che lo sappiamo, dobbiamo aggiungere 1 al nostro indice per ottenere il nodo destro: D. Aggiungiamo D alla nostra prova e possiamo affermare che è un nodo a sinistra: falso (perché è a destra).

La nostra prova finora:

[
  { dati: 'D', left: false }
]

Poiché siamo partiti da C e abbiamo D nella nostra prova, vogliamo ottenere la parte che si combina con CD. Dobbiamo salire di un livello e spostarci all'indice di CD.

Poiché il nostro albero di Merkle è un albero binario, ogni livello combina le sue coppie, ottenendo un numero di nodi dimezzato. Ciò significa che dovremmo dimezzare il nostro indice e arrotondare per difetto. Potete verificarlo voi stessi dando un'occhiata a ogni singolo nodo e pensando a dove volete essere al prossimo livello:

• Per A all'indice 0, vogliamo spostarci su AB all'indice 0;
• Per B a indice 1, vogliamo spostarci in AB a indice 0;
• Per C all'indice 2, vogliamo spostarci su CD all'indice 1;
• Per D all'indice 3, vogliamo spostarci su CD all'indice 1;
• Per E all'indice 4, vogliamo spostarci su EF all'indice 2;
• Per F all'indice 5, vogliamo spostarci su EF all'indice 2;

Si noti che ogni volta dobbiamo dividere l'indice a metà e arrotondare per difetto.

Ora ci spostiamo all'indice 1 del secondo livello, che è CD. Verifichiamo se CD è un nodo sinistro o destro: poiché è un numero dispari, è un nodo destro. Sottraiamo uno per ottenere il nodo sinistro AB e lo aggiungiamo alla nostra prova:

[
  { dati: 'D', left: false }, 
  { dati: 'AB', left: true }
]

Se ripetiamo questo schema, divideremo il nostro indice (1) per 2, prenderemo il livello (0) e ci troveremo in ABCD. Prendiamo il nodo destro E e lo aggiungiamo alla nostra prova:

[
  { dati: 'D', left: false },
  { dati: 'AB', left: true },
  { dati: 'E', left: false }
]

A questo punto raggiungeremo il livello superiore, con un solo nodo e potremo restituire la nostra prova.

In codice, aggiungiamo il metodo getProof:

 getProof(index) {
        let currentLayer = this.leaves;

        let proof = [];
        while (currentLayer.length > 1) {
            let newLayer = [];
            let isOdd = currentLayer.length % 2 !== 0;
            let toRange = isOdd ? currentLayer.length - 1 : currentLayer.length;

            for (let i = 0; i < toRange; i += 2) {
                newLayer.push(
                    this.concat(currentLayer[i], currentLayer[i + 1])
                );
                if (i === index) {
                    proof.push({ data: currentLayer[i + 1], left: false });
                }
                if (i + 1 === index) {
                    proof.push({ data: currentLayer[i], left: true });
                }
            }

            if (isOdd) {
                newLayer.push(currentLayer[currentLayer.length - 1]);
            }

            index = Math.floor(index / 2);
            currentLayer = newLayer;
        }

        return proof;
    }

Verificare la prova di Merkle

E ora che abbiamo ottenuto la prova?

È ora di verificarla.

Creiamo una funzione verifyProof che accetti quattro parametri: proof, node, root e concat.

Ecco le loro definizioni:

1) proof - Un array di oggetti le cui proprietà sono data e left. (La prova creata nella fase precedente);
2) node - Un nodo foglia che stiamo cercando di dimostrare essere all'interno dell'albero di Merkle.
3) root - La radice Merkle valida.
4) concat - Il metodo usato per combinare i nodi foglia.

Questo metodo prende il nodo e lo combina con tutti i dati forniti nella prova.

A questo punto si avrà la propria radice derivata dal nodo e dalla prova. Infine, la confrontiamo con la vera radice per vedere se corrispondono.

In codice:

function verifyProof(proof, node, root, concat) {
    for (let i = 0; i < proof.length; i++) {
        let proofNode = proof[i];
        if (proofNode.left) {
            node = concat(proofNode.data, node);
        } else {
            node = concat(node, proofNode.data);
        }
    }
    return node === root;
}

module.exports = verifyProof;