DEV Community: Venerito Gianmarco

Trie: struttura dati ad albero ordinato

Venerito Gianmarco — Tue, 14 Feb 2023 06:54:03 +0000

Il trie: cos'è e come funziona

Il trie, o albero di prefissi, è una struttura dati ad albero utilizzata per memorizzare e cercare rapidamente stringhe o sequenze di caratteri. In un trie, ogni nodo rappresenta un carattere all'interno della stringa e gli archi che collegano i nodi rappresentano le possibili scelte di caratteri successivi. Il percorso dalla radice dell'albero fino ad una foglia rappresenta una specifica stringa.

L'accesso a un valore all'interno del trie è molto veloce e richiede solo un numero di operazioni proporzionale alla lunghezza della stringa. Questa caratteristica lo rende particolarmente utile per le applicazioni che richiedono la ricerca di stringhe in un grande insieme di dati, come i suggerimenti di completamento automatico nei motori di ricerca.

La storia del trie

Il trie è stato sviluppato per la prima volta negli anni '50 come un tipo di struttura dati per la ricerca di parole in un dizionario. Il suo nome deriva dalla parola "retrieval" (recupero) e fu coniato da René de la Briandais, uno dei primi ricercatori a sviluppare questa tecnologia. Nel corso degli anni, il trie è stato esteso e utilizzato in una vasta gamma di applicazioni.

Utilizzi del trie

Il trie è utilizzato principalmente per le applicazioni che richiedono l'accesso efficiente e veloce alle stringhe. In particolare, il trie è particolarmente utile per l'implementazione di suggerimenti di completamento automatico in un motore di ricerca o in un'app di messaggistica. Ad esempio, quando un utente inizia a digitare una parola, il trie può essere utilizzato per suggerire le possibili completamenti sulla base delle stringhe già presenti nel dizionario.

Il trie è inoltre utilizzato nella compressione dei dati. In questo caso, la struttura viene utilizzata per memorizzare le sequenze di caratteri comuni all'interno di un insieme di dati, riducendo così lo spazio di archiviazione richiesto.

Benefici e svantaggi del trie

Tra i principali vantaggi del trie ci sono la velocità di ricerca, la capacità di ridurre lo spazio di archiviazione necessario per una vasta gamma di stringhe e la flessibilità nell'aggiungere e rimuovere stringhe.

Tuttavia, ci sono anche alcuni svantaggi nel suo utilizzo. La complessità di implementazione del trie può essere piuttosto elevata, soprattutto per stringhe molto lunghe. Inoltre, le prestazioni del trie possono essere influenzate dalla dimensione dell'alfabeto utilizzato nella stringa, il che può portare a un aumento delle dimensioni e della complessità della struttura dati. Infine, il trie può richiedere più spazio di archiviazione rispetto ad altre strutture dati simili, come le tabelle hash.

Coding Time

Concentriamoci su questo esempio:

Per creare questo trie, è sufficiente procedere in questo modo:

trie = new Trie();
trie.insert('HEY');

Vediamo ora i dati che ci aspettiamo nei nostri nodi del trie di esempio:

Qui, la casella all'interno del JSON indica un riferimento all'altro nodo.

1) Il nodo radice memorizza un riferimento al nodo H nella chiave H della sua proprietà children.

2) Il primo nodo memorizza un riferimento al nodo E nella chiave E della sua proprietà children.

Si noti che solo l'ultimo nodo Y ha impostato la proprietà isWord su true. Questa proprietà dovrebbe indicare se il nodo è la fine di una parola.

Partiamo creando due file Javascript: nel primo file, chiamato TrieNode.js, scriveremo il codice necessario per creare la classe TrieNode.
Questa classe è utilizzata per creare un oggetto che rappresenta un nodo all'interno di un trie, con una chiave, una lista di figli e un indicatore per segnalare se il nodo rappresenta una parola completa.

class TrieNode {
    constructor(key) {
        this.key = key;
        this.children = {};
        this.isWord = false;
    }
}

module.exports = TrieNode;

Come possiamo vedere dal codice, la classe TrieNode ha un costruttore che prende come parametro una chiave (o un carattere). La chiave è memorizzata all'interno della proprietà 'key' del nodo. Il nodo ha anche una proprietà 'children', che è un oggetto vuoto inizialmente, e viene utilizzato per memorizzare i figli del nodo. Infine, troviamo una proprietà 'isWord', inizializzata a 'false', che viene utilizzata per indicare se il nodo rappresenta la fine di una parola.

Utilizziamo poi l'espressione module.exports = TrieNode per esportare la classe TrieNode, in modo che possa essere utilizzata nel secondo file.

Nel secondo file, che ho chiamato per comodita' Trie.js, creiamo la classe Trie: essa ha un costruttore che inizializza un nodo radice utilizzando la classe TrieNode che abbiamo scritto nel file precedente. Il nodo radice rappresenta la radice del trie e ha una lista di figli vuota.

const TrieNode = require('./TrieNode');

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let currentnode = this.root;
        const chararray = word.split("");

        for (let i = 0; i < chararray.length; i++) {
            const alphabet = chararray[i];
            if (!(alphabet in currentnode.children)) {
                currentnode.children[alphabet] = new TrieNode(alphabet);
            }
            currentnode = currentnode.children[alphabet];
        }
        currentnode.isWord = true;
    }
}

module.exports = Trie;

Parafrasando il codice..
La classe Trie ha un metodo insert(word) che prende come parametro una parola e la inserisce all'interno del trie. Il metodo crea un puntatore a 'currentnode' che viene inizializzato con il nodo radice. Successivamente, la parola viene divisa in un array di caratteri utilizzando il metodo split(). Viene quindi effettuata un'iterazione attraverso l'array di caratteri e, per ciascun carattere, viene controllato se esiste un nodo figlio corrispondente nel nodo corrente. Se non esiste, viene creato un nuovo nodo figlio per il carattere corrente. Il puntatore 'currentnode' viene quindi aggiornato per puntare al nodo figlio corrispondente al carattere corrente.

Alla fine del ciclo, il nodo corrente viene marcato come una parola completa impostando l'indicatore 'isWord' su 'true'.

Il Branching

Un aspetto importante del trie è la sua capacità di branching, ovvero di ramificarsi e di avere molti figli. Vediamo un esempio più ampio:

In questo esempio, sia la lettera E che la prima L avranno due figli.
I dati per la E sarebbero:

{
    key: "E",
    isWord: false,
    children: {
        'L': lNode,
        'R': rNode,
    }
}

In questo caso, hNode, lNode e rNode sono riferimenti agli oggetti di quei particolari nodi.

Nell'esempio precedente, ci sono tre nodi che dovrebbero avere isWord impostato su true. Si tratta di D, O e T.

Nel codice che abbiamo scritto nel secondo file, il branching nel trie viene effettuato nel metodo insert(word) della classe Trie.

if (!(alphabet in currentnode.children)) {
                currentnode.children[alphabet] = new TrieNode(alphabet);

Il branching in questo caso avviene quando incontriamo un carattere che non ha un nodo figlio corrispondente nel nodo corrente.
In questo caso, viene creato un nuovo nodo figlio per il carattere corrente e il puntatore currentnode viene aggiornato per puntare al nodo figlio appena creato.

Questo è ciò che viene comunemente definito branching all'interno del trie, poiché il flusso della struttura dati si divide in due percorsi separati, uno per la parola corrente e uno per le parole future. Questo processo viene ripetuto per ogni carattere della parola che viene inserita nel trie.

Ethereum, Patricia Trie e Patricia Merkle Trie

Venerito Gianmarco — Mon, 23 Jan 2023 23:25:13 +0000

INDICE

1. Introduzione
2. Uno sguardo in parallelo a Bitcoin
3. Radix Trie
4. Patricia Merkle Trie
4.1 Utilità dei PMT in Ethereum
4.2 Utilità dell'intestazione del blocco Ethereum
4.3 Trie dello Stato di Ethereum
4.4 Trie delle transazioni Ethereum
4.5 Trie delle ricevute delle transazioni Ethereum
5. Conclusioni

Introduzione

Bitcoin fu la prima rete decentralizzata basata su blockchain che ha reso popolare l'uso degli alberi di Merkle per un tipo di inclusione scalabile delle transazioni.

Qualche anno più tardi, Ethereum entrò i campo schierando anch'esso gli alberi di Merkle ma, essendo un progetto completamente diverso per sua natura, fu scelta anche un'altra importante struttura di dati ad albero, con riferimento ad alcune delle sue esigenze di archiviazione dei dati.

Gli alberi utilizzati in Ethereum sappiamo che non sono dei semplici alberi di Merkle, e richiedono delle caratteristiche aggiuntive:

L'albero deve essere facilmente modificabile, in quanto i dati contenuti in esso cambiano frequentemente;
La radice dell'albero deve dipendere solo dai dati e non dall'ordine in cui gli aggiornamenti ad esso vengono fatti;
L'albero deve avere una "profondità" limitata;

E la soluzione a queste funzionalità è il "Merkle Patricia trie", rivisitato e adattato all'infrastruttura Ethereum.

Dei Patricia Trie se ne parlava già nel lontano 1968: a pubblicare il paper all'epoca fu un certo Donald R. Morrison all'interno del Journal of the Association for Computing Machinery.

Ritorniamo ora per qualche momento sulla struttura di Bitcoin.

Uno sguardo in parallelo a Bitcoin

L'architettura di Bitcoin è "semplice": consiste in un libro mastro che tiene traccia delle transazioni utilizzando un modello UTXO.

Poiché Ethereum tiene traccia di una maggiore quantità di dati di stato, l'architettura dei blocchi è completamente diversa:

Perché ora siamo passati a questa architettura a blocchi, non stavamo parlando di alberi?

Perché questi blocchi contengono riferimenti alle strutture dati ad albero di cui stiamo parlando.

L'obiettivo è quello di mostrare prima l'architettura a blocchi e poter comparare e avere familiarità con tre delle proprietà fondamentali dei blocchi di Ethereum incluse nel diagramma qui sopra:
1) State Root,
2) Transaction Root,
3) Receipt Root - proprio come nell'ultima sezione abbiamo trattato il significato di merkleRootHash nel contesto di un blocco Bitcoin, ora esamineremo tre nuovi usi simili dell'albero in Ethereum.

Teniamo questo a mente, dopo ci torneremo!

Radix Trie o Patricia Trie

Il PATRICIA trie viene descritto come un albero che permette di conservare una serie di dati di tipo chiave - valore e poi di recuperarli in modo semplice ed efficiente.

La chiave indica il "percorso" da seguire per giungere alla foglia, la quale contiene il valore corrispondente.

Il PATRICIA Trie, per recuperare un valore stringa, percorre un ramo di nodi che memorizzano riferimenti associati (chiavi) e che insieme portano al valore finale, e che può essere quindi restituito.

I PATRICIA Tries presentano però una grande limitazione: sono inefficienti. Se si vuole memorizzare solo una coppia (chiave/ valore) in cui si trova il percorso (nel caso del trie di stato di Ethereum), lunga 64 caratteri in bytes32, servirà oltre un kilobyte di spazio aggiuntivo per memorizzare un livello per carattere, e per ogni ricerca o eliminazione verranno eseguiti tutti i 64 passaggi.

Il Patricia Merkle Trie risolve questo problema.

Come scrivevamo prima, Ethereum utilizza la struttura di dati radix trie (detta anche Patricia Trie o radix tree) ma solo per quei dati permanenti, e per i dati più effimeri e variabili combina questa struttura di dati con un albero di Merkle per creare un Patricia Merkle Trie (PMT).

Patricia Trie + Albero di Merkle = Patricia Merkle Trie (a volte pronunciato come tree, "albero", a volte come trie, "prova") 👀

CURIOSITA': Cosa significa Trie?
"Trie" deriva dalla parola "retrieval", ovvero recupero, con riferimento al modo ben ottimizzato con il quale i Patricia Merkle Tries riescono a recuperare dati all'interno di particolare strutture.

Ripetiamo: I patricia Merkle Tries sono spesso chiamati anche Patricia Merkle Trees 🎄.

Radix Trie o Patricia Trie

Una Patricia Merkle trie è una struttura dati che memorizza coppie chiave-valore, proprio come una tabella hash.
Inoltre, consente di verificare l'integrità dei dati e l'inclusione di una coppia chiave-valore.

I Patricia Merkle Trie raggruppano i nodi con valori simili nell'albero. In questo modo per esempio, la ricerca di "HELP" porta allo stesso percorso della ricerca di "HELLO" - essendo le prime tre lettere voci condivise di parole diverse.
È un'ottima soluzione per l'efficienza di spazio e delle operazioni di lettura/scrittura.

I PMT sono in pratica alberi di Merkle sotto steroidi: efficienti per la verifica dei dati, ma anche per la loro modifica.

E finalmente sveliamo l'arcano: perchè Patricia?

P = Practical
A = Algorithm
T = To
R = Retrieve
I = Information
C = Coded
I = In
A = Alphanumeric

Utilità dei PMT in Ethereum

Torniamo sui motivi per cui è stata scelto questo algoritmo.

In genere, esistono due tipi diversi di dati:

1) Permanenti

Una volta che si verifica una transazione, quel record viene sigillato per sempre.
Ciò significa che una volta individuata una transazione nel trie delle transazioni di un blocco, è possibile tornare allo stesso percorso più volte per recuperare lo stesso risultato.

2) Dati effimeri

Nel caso di Ethereum, gli stati dei conti cambiano continuamente! (Ad esempio, un utente riceve qualche ETH, interagisce con un contratto, ne consuma altri in gas fee ecc.)
Tra queste tipologie di dati figurano: nonce, balance, storageRoot, codeHash;

È logico che i dati permanenti, come le transazioni minate, e i dati effimeri, come i conti Ethereum (saldo, nonce, ecc.), debbano essere archiviati separatamente.

Gli alberi di Merkle, ancora una volta, sono perfetti per i dati permanenti.

I PMT sono perfetti per i dati effimeri, di cui Ethereum è estremamente ricco rispetto a Bitcoin (ecco perchè vi ho annoiato con il parallelismo con Bitcoin lol).

A differenza della cronologia delle transazioni, lo stato degli account di Ethereum deve essere aggiornato frequentemente. Il saldo-balance e il nonce dei conti vengono spesso modificati e, inoltre, vengono frequentemente inseriti nuovi account e rispettive chiavi in memoria, anch'esse frequentemente inserite e cancellate.

Intestazione del blocco Ethereum

L'intestazione del blocco contiene molti dati. L'intestazione del blocco è il risultato dell'hash di tutti gli elementi di dati contenuti in un blocco: una sorta di packaging di tutti i dati del blocco.

Se guardiamo il diagramma dell'architettura di Ethereum inserito all'inizio di questo post, l'intestazione del blocco finisce per fare da hash a tutte le proprietà dei dati del blocco. Esso include anche:

1) State Root: l'hash della radice del trie di stato;
2) Transactions Root: l'hash della radice delle transazioni del blocco;
3) Receipts Root: l'hash della radice del trie delle ricevute.

Trie dello Stato di Ethereum

Come mostrato nel diagramma qui sotto, il *trie di stato * di Ethereum funge da mappatura tra gli indirizzi e gli stati degli account.

Esso può essere visto come uno stato globale che viene costantemente aggiornato dall'esecuzione delle transazioni.

La rete Ethereum è un computer decentralizzato e lo state trie è considerato un disco rigido.
Tutte le informazioni sugli account sono memorizzate nello state trie globale ed è possibile recuperare le informazioni interrogandolo.

Esempio di conto
Come già detto, lo state trie è solo una mappatura che utilizza un indirizzo come chiave e lo stato del conto (nonce, saldo, ecc.) come valore restituito.

Questo è ciò che si ottiene da una richiesta JavaScript allo stato globale di Ethereum.
Solo un oggetto contenente alcuni dati! Questo è tutto ciò che è lo stato dell'account.
Essendo troppi i dati da memorizzare, si utilizza un hash radice.

Trie delle transazioni Ethereum

Il trie delle transazioni registra le transazioni in Ethereum. Una volta che il blocco è stato estratto, il trie delle transazioni non viene mai aggiornato.

Ogni transazione in Ethereum registra più elementi specifici per ogni transazione, come il prezzo del gas e il valore.

Esempio di transazione

Probabilmente lo avete visto attraverso servizi come Etherscan. Tutto ciò che questi servizi fanno è interrogare la blockchain di Ethereum per trovare i dati delle transazioni e poi indicizzarli in un visualizzatore di transazioni organizzato.

Si può anche provare a interrogare direttamente il trie delle transazioni usando strumenti esterni, come Alchemy Composer. Basterà prendere un hash casuale di tx e usare il metodo eth_getTransactionByHash: si otterrà una risposta molto simile all'oggetto nell'immagine qui sopra.

Trie delle ricevute delle transazioni Ethereum

Il trie delle ricevute delle transazioni registra le ricevute (i risultati) delle transazioni. I dati includono gasUsed e log (gli eventi emessi sono contenuti in questo trie).

Una volta che il blocco è stato estratto, il trie di ricezione delle transazioni non viene mai aggiornato. Un esempio qui sotto:

Conclusioni

Il diagramma sopra riportato è un'eccellente visualizzazione di come i Trie finiscono per essere impegnati in ogni blocco tramite il loro hash principale.
I dati grezzi sono memorizzati altrove in Ethereum, in particolare nei nodi di archiviazione.

Il diagramma dell'architettura a blocchi di Ethereum vi sembra meno minaccioso rispetto all'inizio? Se sì, bene! Abbiamo trattato, seppur velocemente, alcuni degli aspetti di livello più basso dell'archiviazione dei dati in Ethereum, e sono importantissimi! Non solo si ha una comprensione più olistica di Ethereum, ma si tratta di conoscenze applicabili a tutta l'informatica e persino alla fisica 🤯.

L'aspetto più importante di questa lezione è stato sicuramente capire perché queste strutture dati di basso livello sono usate da Ethereum:
a) ottimizzare lo spazio dei dati;
b) ottimizzare l'efficienza di lettura/scrittura;

Alcuni testi e letture per approfondire gli argomenti trattati:

Gli alberi di Merkle in Bitcoin

Venerito Gianmarco — Fri, 20 Jan 2023 09:18:24 +0000

In quest'ultima analisi sugli alberi di Merkle ci soffermeremo nel capire come essi vengano usati all'interno della tecnologia Bitcoin :)

Come detto nei precedenti post, la struttura degli alberi di Merkle li rende estremamente efficienti per la verifica dei dati.
Nello specifico, in ₿ Bitcoin gli alberi di Merkle sono utilizzati per memorizzare in modo efficiente ogni transazione estratta dalla rete Bitcoin. Diamo ora uno sguardo alla struttura di un blocco Bitcoin:

Il diagramma qui sopra mostra l'architettura di un blocco di bitcoin. Pensavate che un blocco di bitcoin contenesse tutte le transazioni per blocco? In un certo senso sì, ma tramite gli alberi di Merkle!

Come?
Tutte le transazioni per ogni blocco sono organizzate in un mega albero di Merkle. Ciò che in realtà finisce per essere incluso nel blocco è l'hash della radice di quell'albero di Merkle.

Includendo l'hash della radice dell'albero, i dati delle transazioni possono essere memorizzati fuori dalla catena (i nodi completi, ad esempio, memorizzano i record delle transazioni su un LevelDB integrato in tutti i nodi completi).

Grazie agli alberi di Merkle, l'archiviazione sulla blockchain è molto efficiente: risulta infatti necessario impegnare solo un pezzo di dati invece di migliaia di transazioni per blocco, che gonfierebbero davvero il sistema!

Lo scopo principale dell'utilizzo degli alberi di Merkle su insiemi di dati (solitamente transazioni) di grandi dimensioni è quello di mantenere la dimensione della blockchain il più piccola possibile.
Data la natura del loro utilizzo, le blockchain crescono in continuazione, quindi è necessario prevedere un'archiviazione efficiente dei dati. Mantenere le dimensioni della blockchain contenute significa che più utenti possono sostenere l'esecuzione di nodi completi, il che aiuta la decentralizzazione della rete.

Grazie agli alberi di Merkle, esiste un modo efficiente per verificare l'esistenza di alcuni dati in un hash radice. Prendete l'immagine qui sotto: riuscite a immaginare quanto sarebbe gonfio ogni blocco se fosse necessario memorizzare ogni singola transazione? Molto meglio memorizzare un solo hash radice che rappresenti tutte le transazioni per blocco!

Prova di Merkle

Come abbiamo visto nel post precedente, il vantaggio del design dell'albero di Merkle - un algoritmo ricorsivo basato sull'hashing - è che consente di dimostrare in modo efficiente che alcuni dati esistono all'interno della costruzione dell'hash della radice (effettivamente contenuti nel blocco, nel nostro caso); in altre parole, consente di ottenere prove Merkle.
Una prova Merkle può confermare che delle transazioni specifiche rappresentate da una foglia o da un ramo hash siano all'interno di una radice hash Merkle.

Quindi, se qualcuno ha bisogno di provare che una transazione è esistita in un determinato momento nella blockchain, deve solo fornire una prova Merkle :)

Nel diagramma qui sopra, supponiamo di voler dimostrare che C (ovvero una qualche transazione tx casuale) esiste in questo blocco. Grazie alle prove Merkle, sono necessari solo 3 dati in tutto - D, H(A-B), H(E-H) - per costruire l'hash della radice dell'albero** H(A-H)**.
Potrebbe sembrare poco per un albero così piccolo, ma che dire di un albero contenente oltre 10.000 o 100.000 transazioni?
Se si riuscisse a costruire con successo l'hash della radice si otterrebbe una prova sufficiente che la transazione in questione facesse effettivamente parte di quell'albero Merkle in quel dato momento.

Casi d'uso degli alberi Merkle

Ricapitolando, gli alberi Merkle sono:

efficienti dal punto di vista spaziale e computazionale;
ottimi per la scalabilità e la decentralizzazione;
non c'è bisogno di riempire un blocco di transazioni: basta impegnare un hash della radice Merkle e mantenere le transazioni in altri luoghi in grado di gestirle;

In termini più profondi, essi:

Riducono significativamente la memoria necessaria per verificare che i dati abbiano mantenuto la loro integrità e non siano stati alterati.
Richiedono la trasmissione di meno dati attraverso la rete blockchain per verificare i dati e le transazioni. Ciò migliora l'efficienza di una blockchain.
Consentono la verifica semplice dei pagamenti (SPV), che consente di verificare una transazione senza scaricare un intero blocco o blockchain. Ciò consente di inviare e ricevere transazioni utilizzando un nodo light-client, più comunemente noto come portafoglio di criptovalute.

PROVER E VERIFIER

Quando si verificano i dati utilizzando un albero di Merkle, ci imbatteremo in un Prover e un Verifier:

Un Prover esegue tutti i calcoli necessari per creare la radice di Merkle (solo un hash!).
Un verifier, o verificatore: esso non ha bisogno di conoscere tutti i valori per avere la certezza che un valore sia presente nell'albero.

Scala logaritmica

Nota: La quantità di prove Merkle necessarie cresce in modo logaritmico rispetto alla dimensione dell'array di dati da inserire nell'algoritmo di hash dell'albero di Merkle.

Conclusione

Gli alberi di Merkle sono una struttura di dati molto popolare nelle blockchain e la ragione alla base è mantenere l'archiviazione dei dati snella ed efficiente; questa comprensione è essenziale quando si inizia a costruire una dApp, perché si vuole sempre essere snelli ed efficienti con l'archiviazione dei dati. Perché? Meno efficiente è l'uso dell'archiviazione dei dati, più costoso sarà il nostro programma per noi e per i nostri utenti.

Nella prossima sezione vedremo Patricia Merkle Tries, una struttura di dati ampiamente utilizzata in Ethereum.

Terminologia

Albero di Merkle: struttura utilizzata per la validazione dei dati.
Radice di Merkle: l'hash contenuto nell'intestazione del blocco, derivato dagli hash di tutte le altre transazioni del blocco.
Merkle path: rappresenta l'informazione di cui l'utente ha bisogno per calcolare il valore atteso per la radice di Merkle di un blocco, a partire dall'hash della propria transazione contenuta in quel blocco. Il percorso di Merkle viene utilizzato come parte della prova di Merkle.
Prova di Merkle: dimostra l'esistenza di una transazione specifica in un blocco specifico (senza che l'utente debba esaminare tutte le transazioni del blocco). Include la radice Merkle e il percorso Merkle.

Costruire una prova di Merkle e verificarla

Venerito Gianmarco — Wed, 18 Jan 2023 05:13:10 +0000

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;

Gli alberi di Merkle

Venerito Gianmarco — Wed, 18 Jan 2023 04:50:32 +0000

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;

Albero binario di ricerca (BST)

Venerito Gianmarco — Thu, 12 Jan 2023 09:59:06 +0000

INDICE

Albero di ricerca binario
Creare un nodo
Il nodo radice
Costruzione del primo livello
Generalizzare l'albero
Implementazione della ricerca

Albero di ricerca binario

Nella programmazione, gli alberi sono una struttura di dati che si presenta sorprendentemente spesso. Hanno una serie di utilizzi diversi, che vanno dall'archiviazione efficiente dei dati alla rappresentazione di una gerarchia di file.

In particolare, in questo post esamineremo l'albero di ricerca binaria. Il suo nome può sembrare intimidatorio, ma in realtà è molto semplice!

Concetti

Gli alberi iniziano con un nodo radice che si dirama verso i nodi sottostanti (i suoi figli). La parola binario indica che ogni nodo ha al massimo 2 figli. Si chiama albero di ricerca perché l'ordine dei nodi è ordinato in base al valore dei dati. Vediamo un esempio:

Ogni figlio che si trova a sinistra del suo genitore è più piccolo. Ogni figlio che si trova a destra del suo genitore è maggiore. Per esempio, la radice 5 ha due figli 3 e 7. Poiché 3 è minore di 5, è alla sinistra di 5.

Sapendo che i dati sono in quest'ordine, ci vorrà meno tempo per trovare un particolare nodo. Ad esempio, cerchiamo il 4.
Partendo dalla radice, sappiamo che è minore di 5 e quindi andiamo a sinistra. Poi incontriamo 3 e sappiamo che 4 è maggiore di 3, quindi andiamo a destra. E qui troviamo il 4.
In media questo metodo sarà più veloce di una ricerca casuale. Il risparmio di tempo diventa tanto maggiore quanto più grande è l'albero.

Ora proviamo a costruire il nostro albero di ricerca binaria scrivendo un po' di codice, che non fa mai male :)

Creare un nodo

Creiamo innanzitutto la classe Node, dalla quale creeremo ogni elemento del nostro albero:

Il nodo deve contenere dei dati, che inseriremo successivamente. Deve inoltre contenere i riferimenti al figlio sinistro (left) e al figlio destro (right).

Completiamo il metodo costruttore e la funzione costruttore sul nodo. Successivamente, memorizziamo i dati in una proprietà data dell'istanza.

Infine, memorizziamo null, left e right nelle proprietà utilizzando this.

Esempio di utilizzo:

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;


    }
}

module.exports = Node;

Il nodo radice

Ora è il momento di creare il nostro albero.
Un albero terrà traccia di una proprietà specifica: il riferimento al nodo radice.

Radice

Completiamo la funzione costruttore della classe Tree nel nuovo file Tree.js.

Tutto ciò che occorre fare per ora è memorizzare null nella proprietà root.

class Tree {
    constructor() {
        this.root = null;
    }
}

module.exports = Tree;

Aggiunta di una radice

In questa fase creeremo un nuovo metodo per aggiungere nodi al nostro albero. È un compito difficile da generalizzare, quindi lo affronteremo pezzo per pezzo :)

Per prima cosa iniziamo ad aggiungere una radice a un albero vuoto.

Creiamo un nuovo metodo addNode sulla classe Tree che prenda un nuovo nodo e lo aggiunga all'albero.

Si supponga che l'albero sia vuoto per questa fase. È sufficiente impostare la radice come il nodo passato nel metodo.

    addNode(newNode) {
        this.root = newNode;
    }

Costruzione del primo livello

Ora è il momento di concentrarsi sull'aggiunta del primo strato di nodi sotto la nostra radice! :)

Ogni nodo che non presenta archi uscenti è detto foglia (leaf node) e in ogni albero finito, cioè con un numero finito di nodi, si trova almeno un nodo foglia. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante, ovvero se è diverso dalla radice).

Manteniamo il codice utilizzato per superare l'ultima fase e aggiungiamo un'altra casistica per quando esiste già una radice:

Quando la radice esiste già, dobbiamo decidere da che parte aggiungere il nuovo nodo foglia.

Se i dati del nuovo nodo sono inferiori a quelli della radice, lo aggiungeremo a sinistra.

Al contrario, se i dati sono maggiori, lo aggiungeremo a destra.

Modifichiamo ora la funzione addNode per gestire anche l'aggiunta dei primi figli della radice:

// Nuovo metodo: se la root esiste, e se il dato del nuovo nodo e' minore, aggiungiamo il nodo a sinistra. Viceversa, a destra.

    addNode(newNode) {
        if (this.root) {
            if (newNode.data < this.root.data) {
                this.root.left = newNode;
            } else {
                this.root.right = newNode;
            }

            // Se non dovesse esistere una gia' una radice..
        } else {
            this.root = newNode;
        }
    }

Generalizzare l'albero

Ora è il momento di far funzionare la funzione addNode per generali livelli dell'albero.
Completiamo la funzione addNode in modo che possa gestire l'aggiunta di nodi indipendentemente dalle dimensioni dell'albero.

Possiamo farlo in modo iterativo o ricorsivo!

Soluzione ricorsiva

Abbiamo già scritto il codice per aggiungere un nodo sotto un altro nodo. Tutto ciò che dobbiamo fare è applicarlo in modo ricorsivo.

Un buon modo per iniziare la soluzione ricorsiva è scrivere una nuova funzione su Albero che prenda due argomenti: un genitore e un figlio. Questa funzione deve aggiungere il figlio sotto il nodo genitore.

Caso 1

Se i dati del figlio sono inferiori a quelli del genitore, sceglieremo di andare a sinistra.

Se il genitore ha già un nodo sinistro, chiameremo questa nuova funzione ricorsivamente con quel nodo sinistro come genitore;
Se il genitore non ha un nodo sinistro, impostiamo il nuovo nodo come nuovo nodo sinistro;

Caso 2

Se i dati del figlio sono maggiori di quelli del genitore, sceglieremo di andare a destra.

Se il genitore ha già un nodo destro, chiameremo questa nuova funzione ricorsivamente con quel nodo destro come genitore;
Se il genitore non ha un nodo destro, impostiamo il nuovo nodo come nuovo nodo destro;

Ora è possibile invocare questo metodo da addNode se esiste una radice. Inizialmente la radice sarà il genitore, che si espanderà man mano che verranno aggiunti altri nodi.

constructor() {
        this.root = null;
    }

    // Soluzione ricorsiva
    insertNode(root, newNode) {
        if (newNode.data < root.data) {
            if (root.left) {
                this.insertNode(root.left, newNode);
            } else {
                root.left = newNode;
                return;
            }
        } else {
            if (root.right) {
                this.insertNode(root.right, newNode);
            } else {
                root.right = newNode;
                return;
            }
        }
    }
    addNode(newNode) {
        if (this.root) {
            this.insertNode(this.root, newNode);
        } else {
            this.root = newNode;
        }

Implementazione della ricerca

È il momento di raccogliere i frutti della creazione del nostro albero di ricerca binario. E' il momento della ricerca :)

Il nostro obiettivo: costruire il metodo hasNode.
Il metodo hasNode prende come input un numero e cerca nel nostro albero un nodo che abbia quel numero all'interno della sua proprietà dati.

Se esiste un nodo con il numero, restituisce true. In caso contrario, restituisce false.

Utilizziamo l'ordine di ordinamento per trovare i nodi dell'albero. Ad esempio, se cercassimo il nodo 4, potremmo usare l'ordine di ordinamento per trovare i nodi nell'albero:

1) Partiamo dalla radice 5, riconosciamo che 4 è minore di 5 e ci spostiamo a sinistra.

2) Troviamo 3, riconosciamo che 4 è maggiore di 3 e ci spostiamo a destra.

3) Troviamo 4, riconosciamo che è quello che stiamo cercando e restituiamo true.

Se cerchiamo un nodo mancante, restituiamo false.

Ad esempio, se cercassimo 7 in questo albero:

Ci accorgeremmo che 7 è maggiore di 5, e spostandoci a destra non troveremo nessun nodo destro! Restituiamo quindi false.

Come implementiamo lato codice tutto questo bel ragionare?

    hasNode(data) {
        return this.findNode(this.root, data);
    }
    findNode(root, data) {

        // Caso base ricorsivo
        if (!root) {
            return false; // Se la root non viene trovata, restituiamo false
        } else if (root.data === data) {
            return true;
        // Chiamata ricorsiva a sinistra
        } else if (root.data > data) {
            return this.findNode(root.left, data); 
        // Chiamata ricorsiva a destra    
        } else if (root.data < data) {
            return this.findNode(root.right, data); 
        }
    }

const tree = new Tree();
const node1 = new Node(4);

Nel prossimo approfondimento analizzeremo gli alberi di Merkle, la loro struttura e il loro funzionamento, il tutto condito con del sano codice JS :)

Grazie per la lettura ed il tempo dedicato!

Strutture dati ad albero

Venerito Gianmarco — Mon, 09 Jan 2023 06:19:00 +0000

Introduzione

Le reti blockchain utilizzano le transazioni per cambiare lo stato e tenere traccia dei saldi degli utenti, come abbiamo visto nella sezione precedente. Scaviamo ancora più a fondo nella complessità di questi sistemi e iniziamo a vedere quali strutture dati utilizzano per memorizzare tutti questi dati di stato in continua evoluzione.

Un orientamento agli alberi

Prima di tutto, gli informatici sono strani. A noi piace disegnare gli alberi al contrario lol

Come nella vita reale esistono molti tipi di alberi, anche in informatica esistono molte strutture di dati simili ad alberi. Vediamo di familiarizzare con alcuni di questi alberi.

Assicuratevi di dare un'occhiata ai termini in grassetto, poiché si tratta di un vocabolario molto importante da imparare per le blockchain in generale!

I nodi

Il primo termine che vedrete ampiamente utilizzato nelle strutture dati: nodi. Un nodo è un'unità di base di una struttura di dati.

Nei sistemi informatici, "nodo" può anche riferirsi ai nodi di rete che comunicano dati su una rete peer-to-peer (come sono Bitcoin ed Ethereum!). Il contesto è importante!

Albero semplice

Nel nodo semplice come nella foto qui sopra, vediamo un nodo arancione in alto, definito genitore, mentre i nodi verdi in basso vengono definiti figli (rispetto al nodo genitore).

Albero binario

E' tipico osservare qualche proprietà di applicazione delle strutture "albero" per distinguerne i diversi tipi di dati.

Un albero è considerato binario quando ogni genitore ha al massimo due figli. La parola chiave di questo albero è "binario" che, come altri termini che precedono "albero", stabilisce un tipo di regola per l'albero, in questo caso che ogni nodo genitore può avere al massimo due figli.

Si noti che l'albero nel diagramma precedente ha ora quattro nuovi nodi grigi. Questi vengono ora chiamati foglie, poiché sono l'ultimo livello dell'albero e non hanno altri figli.

Un albero generico

L'albero qui sopra mostra che un albero può essere un genitore qualsiasi con un numero qualsiasi di figli. Non è necessario che l'albero sia sottoposto a regole, è semplicemente un albero di dati.

Vedremo emergere uno schema in cui la parola "albero" è solitamente preceduta da un termine che indica quali tipi di regole l'albero applicherà. Un albero binario applica la regola secondo cui i genitori possono avere al massimo due figli. Un albero senza aggettivi... beh è solo un albero!

Albero vs. Elenco collegato

Anche un elenco collegato è un albero, solo che è molto lungo e ha solo un figlio per ogni genitore in una lunga catena continua. Un albero non è necessariamente un elenco collegato. Ecco le due implementazioni del codice per un LinkedListNode e unTreeNode, per aiutare a distinguere:

class LinkedListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class TreeNode {
    constructor(data) {
        this.data = data;
        this.children = []; // riferimento al figlio 
    }
}

Si noti che il TreeNode contiene i dati tipici e un array per contenere i riferimenti ai figli di quel nodo (genitore).

Il LinkedListNode tiene solo traccia di un nodo successivo.

Vocaboli utili

Notate tutte le relatività che si verificano quando un albero cresce di dimensioni. Un nodo che era un nodo foglia diventa un nodo genitore una volta aggiunto un nuovo figlio sotto di esso.

Ecco alcuni vocaboli utili quando si parla di strutture dati ad albero:

chiave (key): dati effettivi contenuti nel nodo;
radice (root): il nodo padre di un albero;
fratelli (siblings): nodi sotto lo stesso genitore e allo stesso livello;
sottoalbero (subtree): una volta isolata una parte di un albero più ampio, è possibile formare un albero nuovo con nuove relazioni;

Quando usare un albero 🌲

A volte gli alberi si formano in modo del tutto naturale! LOL
Prendiamo ad esempio un file system:

Un file system ad esempio può essere un albero con una quantità arbitraria di figli in ogni directory.

Uso dell'albero:

Se i dati possono essere memorizzati in modo gerarchico, l'uso di un albero può essere una buona struttura di dati da utilizzare.
Un albero è anche una struttura dati molto efficiente per la ricerca e l'ordinamento dei dati.
Gli algoritmi ricorsivi sono spesso utilizzati insieme agli alberi.
Questi ultimi infatti possono essere strutture di dati molto efficienti per la ricerca e l'ordinamento dei dati proprio per le regole che stabiliscono, come abbiamo visto per l'albero binario, o addirittura un insieme di regole ancora più rigide, come con l'albero di ricerca binario.

Albero di ricerca binario

Un albero di ricerca binario, come quello sopra descritto, ha le seguenti proprietà:

è un albero binario;
il sottoalbero sinistro di un nodo contiene solo nodi con chiavi minori della chiave del nodo stesso;
il sottoalbero destro di un nodo contiene solo nodi con chiavi maggiori della chiave del nodo stesso;
anche i sottoalberi sinistro e destro di ogni nodo devono essere un albero di ricerca binario;

Questi tipi di imposizioni rendono l'albero di ricerca binario una struttura dati molto richiesta, poiché gli algoritmi possono ora tenere conto di queste regole e la memorizzazione/ricerca è molto più efficiente;

Curiosità sull'albero di ricerca binario

Sapendo che ogni figlio sinistro è minore del genitore e ogni figlio destro è maggiore del genitore, quanti tentativi sono necessari per trovare un numero (chiave) al massimo?

L'aggiunta di un nuovo livello di elementi aggiunge solo 1 tentativo di ricerca in più, nella peggiore delle ipotesi. Grazie alle proprietà di applicazione del BST (acronimo di Binary Search Tree), il tempo di ricerca rimane sempre O(log n), dove n è il numero di nodi dell'albero.

L'albero nel diagramma qui sopra è un BST di altezza (quanti livelli ha un albero) pari a tre, con nodi a ogni livello che aumentano di una potenza di due a ogni livello inferiore. L'ultimo livello contiene 4 nodi, il che significa che il livello successivo conterrà 8 nodi (al massimo). Ecco la vera magia degli alberi a proprietà forzata come i BST: anche se aggiungiamo un intero nuovo livello di nuovi dati, il tempo di ricerca aumenta solo di uno. In altre parole, mentre la dimensione dell'albero cresce in modo esponenziale, il tempo di ricerca rimane sempre O(log n).

Ecco un grafico per visualizzare quanto il tempo di ricerca dell'algoritmo sia influenzato dalla crescita dell'input (n).

Poiché le blockchain sono fondamentalmente dei database, la notazione O-Grande è molto importante per aiutare a scegliere la struttura dei dati più efficiente (bassi costi di archiviazione, facilità di ricerca e recupero).
Quando si progetta un sistema con esigenze di dati, si desidera che la struttura dei dati sia il più possibile vicina al tempo costante (la linea blu del grafico).

La notazione O-Grande ci dà un indicatore approssimativo del rendimento di un algoritmo in termini di N (numero di elementi in ingresso). Vogliamo che i nostri algoritmi siano efficienti.

Conclusione

Abbiamo trattato le strutture dati ad albero di base, i diversi tipi di applicazione sugli alberi e il vocabolario generale delle strutture dati ad albero. Si tratta di informazioni importanti per addentrarci ancora di più in alberi più specifici e con imposizioni più specifiche. Nel prossimo post invece, affronteremo gli alberi di Merkle.

UTXO e Modelli di Account

Venerito Gianmarco — Mon, 09 Jan 2023 05:52:10 +0000

Con le piattaforme tradizionali basate su server web2, tenere traccia dei dati e delle informazioni degli utenti è molto più facile che con le blockchain. Questo perché c'è un unico server centralizzato che memorizza lo stato degli account degli utenti. Non c'è bisogno di consenso o di risolvere le discrepanze perché c'è un solo luogo centrale che memorizza le informazioni.

Tuttavia, quando si passa a un sistema decentralizzato, il problema della memorizzazione dei saldi degli utenti diventa complicato. Le reti decentralizzate come Bitcoin ed Ethereum hanno bisogno di modelli specifici per tenere traccia dello stato degli utenti. Bitcoin utilizza il modello UTXO per tenere traccia dei saldi degli utenti. Ethereum e altre catene EVM utilizzano il modello di account per tenere traccia dei saldi degli utenti.

Approfondiamo... :)

UTXO è l'acronimo di "Unspent Transaction Output". Vedrete il termine UTXO usato un po' in questo post.
Bitcoin utilizza il modello UTXO, quindi ci piace includerlo perché ci aiuta a capire i compromessi nei modelli di archiviazione della blockchain e ci aiuta a fare un confronto con Ethereum e il suo uso del modello Account.

Le transazioni

Il miglior punto di partenza, prima di esaminare come le blockchain tengono traccia dei saldi degli utenti, è il luogo in cui i saldi degli utenti hanno inizio: la transazione. Esploriamo con la seguente domanda:

Di cosa abbiamo bisogno in una transazione?
Principalmente, di 3 cose:

1) importo: l'importo da inviare a qualcuno
2) pagante: la persona che invia l'importo del trasferimento
3) beneficiario: la persona che riceve l'importo del trasferimento.

Dal momento che lavoriamo in sistemi basati su una crittografia molto sicura, abbiamo bisogno di un'altra cosa per completare tutto ciò che è necessario per una transazione blockchain di successo: l'autorizzazione del pagante. Una sorta di autorizzazione non falsificabile fornita dall'iniziatore della transazione.
Questo quarto elemento finirebbe per essere la firma digitale, che è fondamentalmente un hash estremamente difficile da replicare se non si dispone degli input corretti - in questo caso, le chiavi private di un utente. Senza le chiavi private, non è possibile autorizzare un pagamento. L'unico modo per farlo sarebbe quello di "hackerare" la crittografia di base, cosa praticamente impossibile.

Qual è lo scopo di una transazione?

Cambiare lo stato di un utente! Se Alice invia a Bob 5 $DAI, il saldo $DAI di Alice dovrebbe andare a -5, quello di Bob a +5. La transazione di Alice è responsabile della modifica dello stato dei loro saldi. La modifica dello stato è estremamente importante nelle blockchain (che sono tipicamente reti basate sulle transazioni!), quindi tenetelo a mente!

Bitcoin, Ethereum e le normali banche si affidano a modelli basati sulle transazioni per tenere traccia dei saldi degli utenti. Diamo un'ulteriore occhiata qui di seguito...

Modello basato sul conto

Se avete un conto corrente bancario, conoscete bene questo modello per tenere traccia dei saldi degli utenti. Il modello basato sui conti è proprio questo: conti. Tiene traccia dei saldi degli utenti in base allo stato generale del loro conto, senza tenere traccia di ciò che costituisce il saldo stesso. In altre parole, un libro mastro basato sui conti segnerebbe una voce come questa:

Acct #12345 -> Nome: Rick Sanchez -> Saldo: 142,62 dollari
Notate come lo stato del conto sia mantenuto ad un livello molto alto? Il saldo del conto di Rick è un importo in dollari e centesimi e basta. Non vengono fornite ulteriori informazioni sulla ripartizione del saldo, ad esempio: 142,62 dollari corrispondono a una banconota da 100 dollari, una banconota da 20 dollari, due banconote da 10 dollari, otto quarti di dollaro, cinque monete, due monetine e due penny. Quando Rick si reca al bancomat e preleva dal suo saldo, lo riceve in qualsiasi banconota + spiccioli che la banca ha a disposizione, non negli spiccioli esatti che sono serviti per formare il saldo.

Come si presenta una transazione in un modello basato sul conto?
Alice ha un saldo totale di 60 dollari
Bob ha un saldo totale di 20 dollari
Bob invia ad Alice 5 dollari
Al saldo di Bob vengono sottratti 5 dollari, se il saldo rimanente è maggiore di 0 si procede, altrimenti si torna indietro
Il saldo di Alice viene sommato a 5 dollari
Il libro mastro viene contrassegnato da entrambe le parti per aggiornare i saldi totali e questa è la fine della transazione in un modello basato sui conti.
Questo potrebbe sembrare strano. Perché dovremmo tenere traccia di questi dettagli per qualcosa di così semplice come un saldo totale? Vediamo un modello per la conservazione dei saldi degli utenti che include questa funzione: il modello UTXO.

Modello basato su UTXO

Ethereum utilizza il modello basato sugli account, mentre Bitcoin utilizza gli UTXO (acronimo di Unspent Transaction Outputs) per tenere traccia dello stato e dei saldi degli utenti.

Il modello UTXO è molto diverso dal modello basato sui conti. È un po' più complesso, soprattutto perché non è un'interfaccia familiare come il modello del conto! Tuttavia, presenta alcune caratteristiche interessanti...

Note importanti sugli UTXO:

1) Tutti gli UTXO non sono fungibili (curiosità: la prima raccolta NFT in assoluto è stata... Bitcoin!).
2) Per spendere un UTXO, è necessario fare riferimento a quello specifico UTXO. Gli UTXO di un utente sono sparsi in blocchi.

3) Una volta che un UTXO viene "consumato", qualsiasi resto della transazione crea nuovi UTXO che rappresentano gli importi del cambiamento.
4) Un UTXO, spesso chiamato "moneta", può essere speso una sola volta. Non è possibile spendere due volte!
5) In Bitcoin, a ogni UTXO è associato uno script. Gli script sono sostanzialmente un codice programmato che ogni UTXO memorizza. Di solito contengono le condizioni per sbloccare l'UTXO per ulteriori spese.

Modello di conto vs UTXO

Conclusione

Decidere quale modello adottare è un gioco di compromessi progettuali. Ethereum utilizza il modello delle transazioni basato sugli account, che deve essere più flessibile per tenere conto dei numerosi elementi di stato in movimento nel sistema. Bitcoin utilizza gli UTXO, in quanto è una rete progettata appositamente per essere il più semplice e senza stato possibile.

(UTXO) - Uscite di transazione non spese

Bitcoin utilizza gli Output di transazione non spesi per gestire la proprietà delle monete da parte degli utenti. Ciò si contrappone al modello basato sugli account utilizzato da Ethereum, che tiene traccia dei saldi di determinati indirizzi.

Consideriamo un paio di esempi.

Esempio UTXO 1
Bob gestisce un minatore Bitcoin. Calcola con successo un blocco e si ricompensa con 12,5 BTC secondo le regole di emissione. Questo è un nuovissimo Unspent Transaction Output (UTXO) che Bob ha introdotto nel sistema.

Supponiamo ora che Bob voglia inviare ad Alice 6,0 BTC. Può farlo utilizzando il suo UTXO con 12,5 BTC. Ma, aspettate, Bob non vuole inviare ad Alice 12,5 BTC! Come gestire il resto?

Si scopre che Bitcoin consente di designare più uscite per ogni transazione. In questa particolare transazione, creeremo un UTXO di 6,0 BTC per Alice e un altro UTXO di 6,5 BTC per Bob (il resto). Quindi, contrassegneremo l'UTXO di 12,5 BTC come speso, poiché è stato utilizzato come ingresso per la transazione. Ottimo!

Esempio UTXO 2
Una cosa che può accadere spesso quando si utilizza questo modello è che gli utenti si ritrovino con molti piccoli UTXO. Man mano che Alice effettua transazioni con la rete, l'UTXO si frammenta in uscite più piccole, finché non le rimangono 3 UTXO del valore di 1,0 BTC, 1,5 BTC e 0,8 BTC.

Supponiamo che Alice voglia acquistare qualcosa per 3,0 BTC. Può farlo specificando diversi input alla transazione. Può inserire tutti e tre i suoi UTXO come input nella transazione per un totale di 3,3 BTC. Dopo l'esecuzione della transazione, riceverà un nuovo UTXO di 0,3 BTC e i suoi input precedenti saranno tutti contrassegnati come spesi.

Ok, per ora gli esempi sono sufficienti! Impariamo da soli con
alcuni esercizi di coding.

Ora è il momento di creare un oggetto per i Transaction Outputs (TXO).

Utilizzando un Bitcoin Block Explorer è possibile cercare i TXO sulla rete reale. Se volessimo cercare gli UTXO per un particolare indirizzo, per esempio:

https://blockchain.info/unspent?active=1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa

Il valore dopo active= è un indirizzo. Questo particolare indirizzo è quello che Satoshi ha usato quando ha estratto il primo blocco di Bitcoin.

Completiamo il metodo constructor e i metodi di spesa (spend) per la classe TXO nel file TXO.js.

Il costruttore deve memorizzare i valori che gli vengono passati nelle proprietà con lo stesso nome. Dovrebbe anche creare una proprietà spent e impostarla come predefinita su false.
La funzione spend deve impostare la proprietà spent su true. Ad esempio:

class TXO {
    constructor(owner, amount) {
        this.owner = owner;
        this.amount = amount;
        this.spent = false;
    }
    spend() {
        this.spent = true;
    }
}
const txo = new TXO("1FNv3tXLkejPBYxDHDaZz6ENNz3zn3G4GM", 10);
console.log("Owner address: ", txo.owner); // uguale a 1FNv3tXLkejPBYxDHDaZz6ENNz3zn3G4GM
console.log("Amount: ", txo.amount); //uguale a 10
console.log("IsSpent", txo.spent); // uguale a false
txo.spend(); // funzione di spesa della somma 
console.log("IsSpent", txo.spent); //uguale a true
module.exports = TXO;

Si noti come spent sia inizialmente falso quando creiamo il nuovo TXO. Dopo aver invocato la funzione spend, spent viene impostato a true.

Le transazioni

Le transazioni sulla rete Bitcoin possono avere molti ingressi e molte uscite.

Si può dare un'occhiata a questa transazione Bitcoin per vedere un esempio di transazione con molte uscite.

Questo, combinato con un sistema di scripting su ogni transazione, permette agli utenti Bitcoin di impegnarsi in accordi finanziari più complessi rispetto al semplice invio di denaro da parte di un individuo all'altro.

Per una transazione media, lo script richiede semplicemente che i nuovi UTXO possano essere spesi solo dall'indirizzo associato.

Obiettivo? Garantire che gli input siano UTXO.

Ora, introduciamo un nuovo file Transaction.js.

Nel costruttore della transazione vengono passati due argomenti: inputUTXO e outputUTXO. Entrambi gli oggetti sono array contenenti istanze di output della transazione.

Memorizziamo inputUTXO e outputUTXO nell'oggetto transazione.
Nella funzione execute faremo solo una cosa per ora: assicurarci che nessuno degli inputUTXO sia già stato speso. Non possiamo permettere che i TXO vengano spesi due volte!
Lanceremo un errore in execute se un TXO di input è già stato speso.
La terminologia tra UTXO e TXO può talvolta creare confusione.
Ricordate che un TXO è solo la nomenclatura di un UTXO già speso!



class Transaction {
    constructor(inputUTXOs, outputUTXOs) {
        this.inputUTXOs = inputUTXOs;
        this.outputUTXOs = outputUTXOs;
    }
    execute() {
        for (let utxo of this.inputUTXOs) {
            if (utxo.spent) {
                throw "UTXO already spent";
            }
        }
    }
}

module.exports = Transaction;

Ingressi e uscite

Con una moltitudine di UTXO di ingresso e di uscita consentiti in ogni transazione, esistono molte possibilità di scambio.

Il software del portafoglio Bitcoin a volte sceglie di includere molti UTXO di ingresso solo per aggregarli in un UTXO più grande da inviare al proprietario.

Ad esempio, se si dispone di cinque UTXO, ciascuno con un importo di 0,1 BTC, il portafoglio potrebbe scegliere di combinarli in 0,5 BTC nella transazione successiva. La magia dietro le quinte :)

La parte importante è assicurarsi che il valore totale degli UTXO in ingresso sia sufficiente a coprire l'importo totale degli UTXO in uscita.

Il nostro obiettivo: garantire un ingresso sufficiente.

Assicuriamoci che gli UTXO di input abbiano un valore totale sufficiente a coprire il valore totale degli UTXO di output.
Se il valore totale degli ingressi è inferiore al valore totale delle uscite, lanceremo un errore nella funzione execute.

class Transaction {
    constructor(inputUTXOs, outputUTXOs) {
        this.inputUTXOs = inputUTXOs;
        this.outputUTXOs = outputUTXOs;
    }
    execute() {
        let totalInput = 0;
        let totalOutput = 0;
        for (let utxo of this.inputUTXOs) {
            if (utxo.spent) {
                throw "UTXO già spesi";
            }
            totalInput += utxo.amount;
        }
        for (let utxo of this.outputUTXOs) {
            totalOutput += utxo.amount;
        }

        if (totalInput < totalOutput) {
            throw new Error("Non hai abbastanza fondi da spendere");
        }
    }
}

module.exports = Transaction;

Riuscita delle transazioni

Quando una transazione ha successo e viene inserita nella blockchain, gli UTXO in uscita diventano nuovi TXO pronti per essere spesi. Gli UTXO in entrata devono essere contrassegnati come spesi, per garantire che non vengano spesi di nuovo :)

Dopotutto, lo scopo della blockchain è proprio quello di risolvere il problema della doppia spesa.

Qui il nostro obiettivo è contrassegnare gli input come spesi.
Se non vengono innescati errori durante la funzione di esecuzione della transazione, questa ha avuto successo.

class Transaction {
    constructor(inputUTXOs, outputUTXOs) {
        this.inputUTXOs = inputUTXOs;
        this.outputUTXOs = outputUTXOs;
    }
    execute() {
        let totalInput = 0;
        let totalOutput = 0;
        for (let utxo of this.inputUTXOs) {
            if (utxo.spent) {
                throw "UTXO già spesi";
            }
            totalInput += utxo.amount;
        }
        for (let utxo of this.outputUTXOs) {
            totalOutput += utxo.amount;
        }

        if (totalInput < totalOutput) {
            throw new Error("Non hai abbastanza fondi da spendere");
        }
        for (let utxo of this.inputUTXOs) {
            utxo.spent = true;
        }
    }
}

module.exports = Transaction;

COMMISSIONI DI MINING

A questo punto ci chiediamo perché nel terzo step abbiamo richiesto solo che la quantità totale di input sia superiore alla quantità totale di output.

Non dovremmo mostrare un errore anche quando la quantità in uscita risulta inferiore?

No! In realtà, il resto viene dato al miner.

Questa è una scelta progettuale del sistema Bitcoin. Si tratta della cosiddetta tassa di transazione, o transaction fee.

La commissione di transazione può contribuire ad accelerare la richiesta. Un miner è molto più propenso a includere la vostra transazione nel blocco successivo se includete un bel premio da riscuotere!

Bitcoin ha un'offerta controllata. Per un periodo di tempo limitato, ogni blocco prevede una ricompensa per il miner. A un certo punto, questo si interromperà e l'unica ricompensa per il miner diventerà la commissione di transazione.

Il nostro obiettivo: calcolare la commissione!
Alla fine della funzione execute, calcoliamo la tariffa come somma di tutti gli input meno la somma di tutti gli output.

Dato che lanciamo un errore se gli input sono insufficienti, questo numero dovrebbe essere almeno pari a zero. Ogni volta che le uscite sono inferiori, il compenso deve essere positivo.
Memorizziamo perciò l'importo della tassa in una proprietà chiamata fee sulla transazione stessa.


const minerFee = totalInput - totalOutput;
        if (minerFee < 0) {
            throw "Miner fee inferiore a zero. Il miner non pagherà per te lol";
        }
        this.fee = minerFee;

Nel prossimo post vedremo nel dettaglio le strutture dati ad albero e i principali metodi per interagire con queste strutture.

Blockchain e struttura dei dati

Venerito Gianmarco — Mon, 09 Jan 2023 03:07:31 +0000

In questo post impareremo a conoscere i blocchi, gli hash e il modo in cui i blocchi sono collegati tra loro per creare una struttura blockchain crittograficamente sicura.

L'implementazione della blockchain risultante avrà un aspetto simile a questo:

Ogni blocco contiene un Hash precedente che rappresenta il contenuto del suo predecessore, e i dati (nello specifico, il payload) che sono le informazioni memorizzate nel blocco.

DEFINIZIONE

Blockchain è effettivamente un nome appropriato: si tratta infatti di una catena di blocchi. Ogni blocco contiene dati transazionali, alcuni metadati che descrivono il blocco stesso e un collegamento al blocco precedente. Questi componenti vengono inseriti in una funzione di hash per creare una sequenza unica di bit che rappresenta il blocco.

Il primo blocco di una blockchain viene spesso chiamato blocco genesi. Il blocco ha solitamente un indice pari a 0 - questa è l'informatica, dove sappiamo ormai che tutto è indicizzato a 0 :)

L'aggiunta dell'hash del blocco precedente (previousHash) al nuovo blocco creerà un collegamento tra i due.

FUNZIONI DI HASH

Le funzioni hash sono utilizzate per prendere in input dati di qualsiasi dimensione e restituire una serie unica di bit di dimensioni specifiche che rappresentano i dati originali.

Una funzione hash crittografica ideale può, dato un qualsiasi input, restituire un output coerente ma apparentemente casuale.

È importante che l'output sia coerente, in modo da poter contare sul fatto di inserire gli stessi input e ricevere lo stesso output.

È anche importante che la casualità sia abbastanza forte da rendere impossibile ricostruire l'input dall'output. In questo modo, sappiamo che è a prova di manomissione.

Ad esempio, l'algoritmo SHA256 accetta un input come "Music" e restituisce un output coerente:

const hash = SHA256("Music");
console.log( hash.toString() ); // b12595…1cbe7e abbreviato per comodita'

Il log è abbreviato, in realtà è lungo 64 caratteri esadecimali. SHA256 produce 256 bit. Poiché un carattere esadecimale richiede 4 bit, ci sono 64 caratteri esadecimali in un hash SHA256.

Se invece il mio input fosse "music" in minuscolo, il risultato sarebbe completamente diverso:

const hash = SHA256("music");
console.log( hash.toString() ); // ec4f2d...56f1cb

Questi risultati hash sono apparentemente casuali rispetto ai loro input: "Music" e "music". Sono anche coerenti: inserendo questi input si ottengono sempre gli stessi output. Per questi motivi sha256 è una funzione hash crittografica ideale e viene spesso utilizzata nei programmi crittografici.

Crypto-JS

La libreria crypto-js ci fornisce diverse utilità crittografiche da poter implementare scrivendo codice in Javascript. In particolare, il metodo SHA256 di questa libreria è un'implementazione dell'algoritmo SHA256 progettato dall'NSA.

Questa funzione accetta come argomento qualsiasi stringa, indipendentemente dalla sua dimensione, e la sottopone ad hash in un array di 256 bit. Se chiamiamo toString() sull'oggetto restituito, riceveremo una stringa esadecimale di 64 caratteri.

Esadecimale
Si noterà che gli output mostrati consistono in un insieme di caratteri che vanno da a a f e da 0 a 9. Si tratta di caratteri esadecimali: è ormai consuetudine utilizzare l'esadecimale quando si visualizza un hash.

Spesso si incontra anche un hash con un prefisso 0x davanti. Questo prefisso significa che viene utilizzata la notazione esadecimale. Quindi, se si vede una stringa di caratteri "0x123abc", lo "0x" indica l'uso di esadecimali e il valore della stringa è in realtà solo la parte successiva, ovvero "123abc".

Per il file di prova che troverete qui sotto, si noterà che l'hash del blocco viene testato dall'espressione regolare (regex) /^[0-9A-F]{64}$/i. L'espressioneSta semplicemente verificando che si tratti di un output esadecimale di 64 caratteri.

Le espressioni regolari possono aiutare a definire un modello di ricerca per i dati in ingresso. Potete trovare maggiori informazioni sulle espressioni regolari su MDN

Perché 64 caratteri esadecimali?

Un bit può rappresentare due valori: 0 e 1. Due bit possono rappresentare quattro valori: 00, 01, 10 e 11. Quattro bit possono rappresentare 16 valori da 0000 a 1111. Possiamo mappare ciascuno di questi valori con un carattere dell'alfabeto esadecimale, poiché contiene 16 caratteri :)

Poiché SHA256 produce 256 bit, dividiamo questo valore per il numero di bit che rappresentano un carattere esadecimale (4) per ottenere 64 caratteri.

Guardiamo ora come implementare un modello semplificativo tramite JS.

In un file che chiameremo Block.js, abbiamo una classe Block. Utilizzando la funzione SHA256 della libreria Crypto JS, otteniamo un hash valido nella funzione toHash.

Iniziamo con l'aggiungere dati alla funzione di hash:
In questo modo si assicura che l'hash del blocco sia legato al suo contenuto.

Quando si crea un nuovo blocco, i dati vengono passati al suo costruttore:

const block = new Block("Alice ha inviato a Bob 1 BTC");

console.log( block.data ); // Alice ha inviato a Bob 1 BTC

Come mostrato sopra, aggiungiamo una proprietà data al blocco.

Successivamente, aggiungiamo un costruttore alla nostra classe Block che prenda un parametro data e lo assegni a this.data
Una volta aggiunti i dati al blocco, li utilizziamo per calcolare l'hash del blocco nella funzione toHash.

const SHA256 = require("crypto-js/sha256");

// 
class Block {
  constructor(data) {
    this.data = data;
  }

  // Ritorniamo l'hash di data
  toHash() {
    return SHA256(this.data + this.previousHash);
  }
}

Ora creiamo un nuovo file: Blockchain.js :)

Il file si concentrerà sull'aggiunta del primo blocco alla nostra nuova classe Blockchain. Il primo blocco viene spesso chiamato blocco Genesi.

Il file Blockchain.js contiene la classe Blockchain che al suo interno contiene un array chiamato chain. Aggiungiamo il blocco Genesi a questo array.

const Block = require('./Block');

class Blockchain {
    constructor() {
        this.chain = [new Block()];
    }
}

module.exports = Blockchain;

Creiamo quindi un nuovo blocco nel costruttore di Blockchain e aggiungiamo l'array chain.

Funzione AddBlock

Creiamo una funzione addBlock nella nostra classe Blockchain.

Questa funzione accetta un nuovo blocco e lo aggiunge all'array chain:

addBlock(block) {
    // Aggiunge il previousHash al nuovo blocco, collegandoli.

    block.previousHash = this.chain[this.chain.length - 1].toHash();
    this.chain.push(block);
  }

Ora dovremmo avere sia il blocco genesi che il nuovo blocco.

Funzione di Linking dei blocchi

È il momento di aggiungere un altro input cruciale al calcolo dell'hash del nostro blocco: l'hash del blocco precedente nella catena.
In questo modo si crea una catena in cui qualsiasi modifica ai dati di un blocco precedente si ripercuote su ogni blocco successivo.

Per collegare i blocchi occorre fare due cose:

1) Aggiungere una proprietà previousHash a ogni blocco. Il valore di questa proprietà deve essere l'hash del blocco precedente nella catena.
2) Utilizzare questa proprietà previousHash nel calcolo dell'hash del blocco.

const Block = require("./Block");
const SHA256 = require("crypto-js/sha256");

class Blockchain {
    constructor() {
        const block = new Block("Music");
        this.chain = [block]; // genisis block
    }
    addBlock(newBlock) {
        newBlock.previousHash = this.chain[this.chain.length - 1].toHash();
        newBlock.data = "Altri dati";
        this.chain.push(newBlock);
    }
}
const blockchain = new Blockchain();
const block = new Block();

blockchain.addBlock(block);

module.exports = Blockchain;

La Chain Validation
Le blockchain sono gestite da una rete di nodi, come dicevamo. Quando un nodo trova un nuovo blocco, trasmette la nuova versione della blockchain a tutti i suoi pari. In qualsiasi momento possono esistere più versioni della blockchain. Tuttavia, la blockchain valida più a lungo è quella accettata.

Creiamo ora una funziona per validare i blocchi.

Creare una funzione chiamata isValid sulla nostra Blockchain che restituisca true o false se un blocco è rispettivamente valido o non valido.
isValid deve controllare l'integrità di ogni blocco nella sua catena, guardando il campo previousHash di ogni blocco e assicurandosi che sia uguale all'hash del blocco precedente.


isValid() {
    let bool = true;

    for (let i = 0; i < this.chain.length - 2; i++) {
      const hashPrev = this.chain[i].toHash();
      const prevHash = this.chain[i + 1].previousHash;

      if (hashPrev.toString() != prevHash.toString()) {
        bool = false;
        break;
      }
    }

    return bool;
  }

Il blocco Genesi e il Blockchain Explorer

È un buon momento per parlare del blocco genesi, (Genesis Block) e di Bitcoin.

Guardiamo il blocco genesi di Bitcoin dall'explorer.

Il numero di conferme è il numero di blocchi dal blocco genesi. Poiché il blocco genesi è il primo blocco, questo è anche l'altezza del blocco della blockchain!

È interessante notare che se si guarda al nonce del blocco genesi, esso è 2.083.236.893. Se si dà un'occhiata a un blocco più recente, ad esempio il 632900, si vedrà che il nonce è in realtà molto più basso. Perché? La difficoltà non dovrebbe aumentare con la crescita della rete?

Scopriamo così che il nonce del blocco è in realtà un campo di 32 bit e 2^32 fa 4.294.967.296, quindi questa è la dimensione massima di un nonce. Cosa succede quando il miner raggiunge questo punto? Può cambiare qualsiasi altra cosa nell'intestazione del blocco per aumentare la casualità. Altre proprietà includono:

Versione del software - Traccia gli aggiornamenti del software Bitcoin.
Hash del blocco precedente - Hash del blocco precedente a questo
Merkle Root - Non l'abbiamo ancora analizzato, è un hash che rappresenta tutte le transazioni!
Timestamp - Ora approssimativa (meno di due ore nel futuro secondo le regole del consenso)
Target - Obiettivo di difficoltà che stabilisce quanto deve essere piccola la Proof Of Work.

L'algoritmo ECDSA

Venerito Gianmarco — Sat, 07 Jan 2023 19:08:06 +0000

In questo post esploreremo come un algoritmo di curva ellittica, nello specifico l'algoritmo di firma digitale a curva ellittica (ECDSA), venga utilizzato sul web e come possa migliorare le prestazioni generali e la sicurezza.

UN PO' DI STORIA

Quando visitiamo un sito che inizia con https:// anziché http://, il nostro browser si connette a quel sito tramite una connessione crittografata.
Il browser verifica che il sito web sia esattamente chi che afferma di essere utilizzando la crittografia a chiave pubblica insieme ad un certificato digitale.

Nella crittografia a chiave pubblica, ogni utente ha una coppia di chiavi: una chiave pubblica e una privata. Di solito si tratta di numeri scelti in modo tale da avere una relazione matematica specifica.

In RSA (crittografia a chiave simmetrica), la chiave pubblica è il risultato del prodotto di due numeri primi, a cui si somma un numero più piccolo. La chiave privata è un numero correlato.

In ECC (Crittografia a curva ellittica) la chiave pubblica corrisponde ad un'equazione per una curva ellittica ed un punto che si trova su quella curva.

La chiave privata associata alla chiave pubblica può essere utilizzata per creare una firma digitale per qualsiasi tipo di dati utilizzando un algoritmo di firma digitale. Questo processo solitamente implica il prelievo di un hash crittografico dei dati e l'esecuzione di una operazione matematica su di esso utilizzando la chiave privata. Chiunque abbia la chiave pubblica può verificare che questa firma sia stata creata utilizzando sia la chiave privata, sia l'algoritmo di convalida della firma appropriato.
La firma digitale risulta oggi uno strumento efficace in quanto consente di attestare pubblicamente qualsiasi messaggio.

Un certificato per sito web di solito contiene due elementi:

1) Informazioni riguardanti l'identità: di solito, chi possiede il certificato e per quali domini il certificato è valido.

2) Una chiave pubblica: fornita la chiave pubblica di una coppia di chiavi, il proprietario del sito controlla e mantiene segreta la chiave privata associata a quella pubblica.

Il certificato è successivamente firmato digitalmente da un'autorità di certificazione affidabile che convalida l'identità del proprietario del sito.

Dall'introduzione di SSL da parte di Netscape nel 1994, i certificati per i siti web hanno di solito utilizzato una coppia di chiavi pubbliche/private basata sull'algoritmo RSA. Man mano che il protocollo SSL si e' evoluto in TLS, ad esso è stato aggiunto il supporto per diversi altri tipi algoritmi di chiave pubblica.

SCELTE ED UTILIZZI

Sebbene ECDSA non abbia preso piede tra le applicazioni web, l'algoritmo è diventato lo schema di firma digitale scelto per tutta una serie di nuove applicazioni crittografiche non web.

Bitcoin è un buon esempio di sistema che si affida a ECDSA per la sicurezza.
Ogni indirizzo Bitcoin è costituito da un hash crittografico di una chiave pubblica ECDSA.
La proprietà del conto Bitcoin è determinata da chi controlla la chiave privata ECDSA. Per trasferire una quantità di Bitcoin a un'altra persona, il mittente esegue una transazione, firma quella transazione con la sua chiave privata e lo invii alla blockchain Bitcoin per la sua validazione.
In questo caso, il perno della sicurezza e della coerenza del sistema Bitcoin risiede proprio nella sicurezza delle chiavi private ECDSA.

Le curve ellittiche e, in particolare, le curve ECDSA sono utilizzate per garantire la sicurezza delle applicazioni di messaggistica. Nel recente whitepaper di Apple sulla sicurezza di iOS, gli sviluppatori di Cupertino hanno riferito come utilizzino ampiamente ECDSA nell'ecosistema Apple. Due rapidi esempi: le conversazioni tramite iMessage sono firmate con ECDSA e la sincronizzazione del portachiavi iCloud si basa anch'essa su ECDSA. Sempre più tecnologie utilizzano ECDSA per la sicurezza, incluse le app di messaggistica a end-to-end criptate TextSecure e CryptoCat.

La grande battaglia: ECDSA vs RSA

Perché ECDSA è l'algoritmo scelto per i nuovi protocolli quando RSA è disponibile ed è stato il gold standard per la crittografia asimmetrica dal 1977? Il motivo è che noi umani siamo più bravi a violare RSA che a violare ECC.

Nello specifico, la sicurezza di una chiave dipende dalla sua dimensione e dal suo algoritmo. Alcuni algoritmi sono più facili da decifrare di altri e richiedono chiavi più grandi per lo stesso livello di sicurezza. Per decifrare una chiave RSA è necessario fattorizzare un numero grande. Purtroppo o per fortuna, nel corso degli anni, siamo diventati abbastanza bravi a fattorizzare numeri grandi e miglioriamo continuamente.
Per decifrare una chiave ECDSA invece, diventa necessario risolvere un particolare problema, quello del logaritmo discreto della curva ellittica (ECDLP). La comunità matematica non ha fatto grandi progressi nel migliorare gli algoritmi per risolvere questo problema da quando è stato introdotto in modo indipendente dai matematici *Koblitz * e **Miller **nel 1985.

Ciò significa che con ECDSA è possibile ottenere lo stesso livello di sicurezza di RSA, ma con chiavi più piccole: e le chiavi più piccole sono migliori di quelle più grandi per diversi motivi:
1) Le chiavi più piccole sono caratterizzate da algoritmi più veloci per la generazione delle firme, perché i calcoli riguardano ovviamente numeri più piccoli.
2) Chiavi pubbliche più piccole significano certificati più piccoli e meno dati da trasmettere per stabilire una connessione TLS. Ciò significa connessioni più veloci e tempi di caricamento più rapidi sui siti web.

Secondo le raccomandazioni di ECRYPT II sulla lunghezza delle chiavi, una chiave a curva ellittica a 256 bit fornisce la stessa protezione di una chiave asimmetrica a 3.248 bit.

Ora effettuiamo un piccolo test.
Sappiamo che e chiavi RSA tipiche dei certificati dei siti web sono a 2048 bit.

Se confrontiamo la parte dell'handshake TLS che avviene sul server per le chiavi ECDSA a 256 bit con le chiavi RSA a 2048 bit, crittograficamente molto più deboli, otteniamo quanto segue:

                            sign/s
256 bit ecdsa (nistp256)    9516.8
rsa 2048 bits               1001.8

(openssl 1.0.2 beta on x86_64 with enable-ec_nistp_64_gcc_128)

La sezione qui sopra mostra il numero di firme ECDSA e RSA possibili al secondo (sign/s).
Come visionabile dal test effettuato, l'uso di un certificato ECDSA riduce il costo dell'operazione di chiave privata di di circa 9,5 volte, risparmiando in modo consistente sui cicli della CPU.

ESISTE UNA DANGER ZONE?

Possiamo essere relativamente fiduciosi sulla sicurezza matematica connessa alle ECDSA.
La storia della crittografia ci mostra che la buona crittografia è stata ripetutamente sconfitta non a causa di una cattiva matematica, ma a causa di cattive implementazioni della buona matematica.

Una particolarità interessante dell'algoritmo ECDSA è che ogni firma richiede come input alcuni dati casuali o imprevedibili. Se la fonte di casualità è prevedibile per un attaccante, questi può scoprire la chiave privata. E storicamente, hacker black-hat hanno sfruttato questa vulnerabilità in diversi casi di alto profilo.

Nel 2010 ad esempio, una falla nel modo in cui venivano utilizzati i numeri casuali in ECDSA su Playstation 3 di Sony ha portato alla fuga di una chiave privata. Più di recente, si è scoperto che alcuni dispositivi Android generavano in modo errato valori casuali, che ha causato un massiccio furto di Bitcoin da dispositivi che eseguivano il software BTC sulla macchina.

Esistono altri attacchi più esoterici contro specifiche implementazioni di ECDSA.
In un paper pubblicato da un gruppo di ricercatori australiani e britannici, si descrive un attacco all'implementazione di ECDSA di OpenSSL per la curva secp256k1 (la specifica curva utilizzata dal protocollo Bitcoin). Fortunatamente, questo attacco non rappresenta attualmente una minaccia per i server remoti occupati.

Esiste inoltre un pericolo legato alla perdita di chiavi tramite dati casuali di scarsa qualità o attacchi side channel, ma rimane una casistica gestibile con una preparazione adeguata e con una attenta attivita' di prevenzione.
La chiave di volta sta nell'assicurare che il generatore di numeri casuali (PRNG - pseudorandom number generator) del sistema abbia un'entropia sufficiente.

Tale crittografia è difficile da implementare correttamente, soprattutto nel contesto di un protocollo complesso come TLS, come dimostrato da alcune famose correzioni di bug recenti. Detto questo, i vantaggi sembrano superare i rischi in questo caso.

Blockchain 101 - Public key cryptography

Venerito Gianmarco — Tue, 27 Dec 2022 19:11:51 +0000

CONTEXT

Public key cryptography is a fundamental part of modern digital security, and it plays a crucial role in ensuring the privacy and integrity of information transmitted over the internet. It allows individuals and organizations to communicate securely and authenticate the identity of users, without the need for a shared secret key.

THE PRINCIPLE

The basic principle behind public key cryptography is that each user has a pair of keys - a public key and a private key - that are mathematically related. The public key is used to encrypt messages, while the private key is used to decrypt them. This means that anyone can use a user's public key to send an encrypted message, but only the user with the corresponding private key can decrypt and read the message.

ECDSA

One important algorithm used in public key cryptography is the Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is a cryptographic algorithm used to generate digital signatures, which are used to verify the authenticity of a message or document. It is based on the mathematical concept of elliptic curves and provides a high level of security.

ELLIPTIC CURVES

Elliptic curves are a type of mathematical curve that can be defined over a finite field, such as the set of integers or the set of points on a plane. They have a number of interesting properties that make them well-suited for use in cryptography.

One of the key properties of elliptic curves is that they allow for the efficient generation of a large number of points that are very difficult to distinguish from each other. This makes them useful for generating cryptographic keys, as it ensures that the keys are effectively random and cannot be easily guessed or derived by an attacker.

In addition to their key generation capabilities, elliptic curves also allow for the efficient implementation of various cryptographic algorithms, such as the Elliptic Curve Digital Signature Algorithm (ECDSA).

The security of ECDSA and other algorithms based on elliptic curves derives from the difficulty of solving certain mathematical problems that are related to elliptic curves. These problems are believed to be computationally infeasible to solve, even with the use of powerful computers, making it very difficult for an attacker to break the encryption or forge a digital signature.

When users want to send a message, they use their private key to create a digital signature. This signature is then attached to the message and sent along with it. When the recipient receives it, they use the sender's public key to verify the signature and confirm that the message is authentic. If the signature is valid, it indicates that the message was indeed sent by the user with the corresponding private key.

SIGNING A MESSAGE WITH secp256k1

With secp256k1, the process of signing a message includes returning the signature along with the recovery bit. This allows us to recover the public key from the signature, enabling a blockchain node to identify the address that authenticated a given transaction based on the signature. This is a crucial aspect of blockchain transactions, as they not only demonstrate the intent of the signer but also authenticate their identity through public key cryptography.

noble-secp256k1: A JS LIBRARY

The noble-secp256k1 library (official Github here) is a JavaScript implementation of the secp256k1 elliptic curve cryptography algorithm.
It allows users to sign and verify messages, recover public keys from signatures, and transform public keys into Ethereum addresses. The library is designed to be fast and easy to use, with a simple API and no dependencies. It is tested and well-documented, with comprehensive documentation and examples provided. Overall, the noble-secp256k1 library is a reliable and convenient tool for working with secp256k1 in JavaScript applications.

Recovering the public key WITH secp256k1

Recovering the public key from a signature is an important aspect of public key cryptography. It allows blockchain nodes to identify the user who signed a particular transaction, and to verify the authenticity of the transaction.

To recover the public key from a signature, you will need to have the signature itself, along with the recovery bit. The recovery bit is a piece of information included with the signature that allows the public key to be recovered. It is a single bit that indicates which of the two possible public keys corresponds to the private key used to generate the signature.

Once you have the signature and recovery bit, you can use the Elliptic Curve Digital Signature Algorithm (ECDSA) to reverse the process and extract the public key. This involves solving a mathematical problem related to the elliptic curve used in the ECDSA algorithm.

Here's a code example in JavaScript that demonstrates how to recover the public key from a signature using the noble-secp256k1 library:

const secp256k1 = require('noble-secp256k1');

const signature = '...'; // The signature, including the recovery bit
const messageHash = '...'; // The hash of the message that was signed

// Use the recover function to extract the public key from the signature
const publicKey = secp256k1.recover(messageHash, signature);

console.log(publicKey); // Outputs the public key in hexadecimal format

Code explanation

This code defines an async function called recoverKey that takes a message, signature, and recovery bit as input, and uses the recover function from the secp256k1 library to extract the public key. The function returns the public key in hexadecimal format.

The code also includes a test of the function, using sample values for the message, signature, and recovery bit. When the function is called, it returns the public key, which is then logged to the console.

Keep in mind that this code assumes you have already installed the secp256k1 library and imported it into your project. You can install it using npm by running npm install secp256k1.