1. Introduzione

Questo argomento è stato trattato in blockchains

---

Distributed Ledger Technologies (DLT)

Distributed Ledger Technologies (DLT): definizione

Un ledger distribuito è un sistema in cui i dati (digitali) sono replicati, condivisi e sincronizzati tra più localizzazione, garantendo che tutti i partecipando mantengano una replica dei dati. Questo favorisce trasparenza, sicurezza e fiducia nel sistema, senza il bisogno di una autorità centrale.

Blockchain risulta essere l’implementazione più popolare. Tuttavia, non tutti i DLTs sono blockchain.

Fondamentali di crittografia

CIA triad

• confidenzialità: impedisce accessi non autorizzati (generalmente si usa la crittografia);
• integrità: impedisce modifiche non autorizzate (generalmente si usano le funzioni di hash);
• autenticità: verifica l’identità (generalmente si usa la firma digitale).

Funzioni di hash

Una funzione di hash è una funzione che converte una stringa arbitrariamente lunga in una “fingerprint” a grandezza fissata, in maniera efficiente rispetto alla computazione.

Resistenza alla collisione

Resistenza alla collisione: definizione

Una funzione di hash $H$ è detta resistente alla collisione se è impossibile trovare due valori, $x$ e $y$, tali che $x\ne y$ ma $H(x)=H(y)$.

Prendendo $2^{256}+1$ valori distinti e calcolandone l’hash, alcune coppie sicuramente collideranno. Tuttavia, se si prendono input casuali, dopo $2^{130}+1$ input c’è una possibilità del $99.8\%$ che almeno due collidano, ma anche calcolando 10000 hash al secondo, ci vorranno più di $10^{27}$ anni.

Hiding

Hiding: definizione

Una funzione di hash $H$ è hiding se, quando un valore segreto $r$ è scelto da una distribuzione di probabilità con alta min-entropia¹, allora dato $H(r||r)$, è impossibile calcolare $x$.

Avalanche Effect

Una proprietà desiderabile e importante di una buona funzione di hashing è la non correlazione tra input e output, il cosiddetto avalanche effect, che comporta, ad un minimo cambiamento dell’input, un significativo cambiamento nell’output, rendendolo statisticamente indistinguibile dal casuale. In una funzione di hash, tipicamente, flippare un singolo bit comporta il cambiamento di metà dei bit dell’output.

Puzzle friendliness

Puzzle friendliness: definizione

Una funzione di hash $H$ è detta puzzle-friendly se, per ogni possibile valore di output a $n$ bit $y$, se $k$ è scelta da una distribuzione con alta min-entropia, allora è impossibile trovare $x$ tale che $H(k||x)=y$ in un tempo significativamente minore di $2^n$.

Hash pointer e strutture dati

Un hash pointer è un puntatore in cui alcune informazioni sono salvate insieme a un hash crittografico dell’informazione. Se un puntatore regolare fornisce un modo per recuperare l’informazione, un hash pointer fornisce anche un modo per verificare che l’informazione non sia cambiata.

Tamper-evident log

Se un avversario modifica dati in qualsiasi punto di una block chain (“catena di blocchi”), questo comporterà che l’hash pointer del blocco successivo sarà non corretto.

Merkle Tree

Un Merkle tree è un albero binario in cui le foglie sono blocchi che contengono dei dati. I blocchi di dati sono raggruppati in coppie e l’hash di ognuno di questi blocchi è conservato nel nodo genitore. I nodi genitori sono, a loro volta, raggruppati in coppie e i loro hash sono salvati un livello più in alto nell’albero, fino a raggiungere il nodo radice.

Proof of Membership

Per provare che un blocco di dati è incluso nell’albero, c’è bisogno solamente di mostrare i blocchi nel percorso dal blocco di dati specifico fino alla radice. Questo richiede spazio e tempo (complessità) che è logaritmica rispetto al numero di nodi nell’albero.

Crittografia asimmetrica

Ogni entità ha una coppia di chiavi:

• una chiave pubblica, condivisa con gli altri per crittografare messaggi e verificare le firme;
• una chiave privata, mantenuta segreta e usata per decifrare messaggi e firmare transazioni.

Public Key Infrastructure (PKI)

Una infrastruttura a chiave pubblica è un insieme di ruoli, politiche, hardware, software e procedure per creare, gestire, distribuire, usare, conservare e revocare certificati digitali, che associano chiavi pubbliche alle rispettive identità.

Firma digitale

Una firma digitale è uno schema matematico per verificare l’autenticità di un messaggio digitale o un documento.

Unforgeability

Un avversario che conosce la chiave pubblica e vede le firme su altri messaggi non deve essere in grado di falsificare (to forge) la firma su messaggio per il quale non abbia mai visto la firma.

Chiavi pubbliche come identità

Si può prendere una chiave pubblica e uguagliarla all’identità di una persona o un attore in un sistema, rendendo facile la creazione di nuove identità. Chiunque può creare una nuova identità, senza la necessità di avere un’autorità centrale fidata: vi è dunque la gestione decentralizzata delle identità.

Le chiavi pubbliche sono generalmente grandi, dunque si preferisce usare il relativo hash: questo è l’indirizzo in blockchain, che non garantisce l’anonimato (es. tracciamento dell’IP associato alla chiave).

Fondamentali di blockchain

Scalabilità

La scalabilità è la capacità di un sistema, rete o processo, di gestire una quantità crescente di lavoro o che possa potenzialmente essere allargata per gestire questa crescita.

In una blockchain pubblica, tipicamente si affronta un trilemma: scalabilità, sicurezza e decentralizzazione².

Disponibilità (avaliability)

La disponibilità è una metrica che misura la probabilità che un sistema non sia in fallimento o in riparazione quando deve essere usato. Vi è alta disponibilità con Bitcoin perché più nodi mantengono il ledger e l’alta disponibilità viene mantenuta finché la maggior parte dei nodi è online.

La disponibilità si calcola come; $availability=\frac{uptime}{uptime+downtime}$

Throughput

Il throughput è la misura di quante unità di informazione un sistema può processare in una data unità di tempo.

In blockchain, il throughput è il numero di transazioni processate per secondo (TPS). Si noti che:

• il consenso aggiunge ritardo;
• blocchi più grandi impiegano più tempo per essere propagati sulla rete;
• alcune blockchain propongono soluzioni innovative sul consenso per migliorare il tps.

Single Point of Failure

Una parte del sistema che, se fallisce, arresta il funzionamento dell’intero sistema. Un’architettura decentralizzata sorpassa questa limitazione.

Bottleneck

Il bottleneck avviene quando una parte del sistema limita le prestazioni complessive.

Il consenso è computazionalmente intensivo e limita la velocità delle transazioni.

Al crescere della blockchain, i nodi hanno bisogno di più risorse per conservare e trasmettere dati.

Churn

Con churn si identifica il continuo arrivo, abbandono e fallimento di processi in un breve periodo di tempo.

I nodi di una blockchain possono frequentemente unirsi e abbandonare la rete, causando squilibri temporanei. Un churn alto può creare ritardi nella propagazione delle transazioni.

Distribuito vs Decentralizzato

I sistemi possono essere categorizzati sulla base di dove la computazione avviene e su chi prende decisioni:

• sistemi centralizzati: la maggior parte della computazione e dello storage dei dati avviene su un singolo server centrale. Il server centrale gestisce tutte le operazioni, risorse e dati, agendo come l’hub attraverso il quale sono processate tutte le richieste dei client (+: single point of control, semplicità, efficienza; -:problemi di scalabilità, single point of faiilure);
• sistemi distribuiti: architetture di computazione in cui più nodi indipendenti lavorano insieme per raggiungere un obiettivo condiviso. Questi nodi comunicano e si coordinano mediate una rete, apparendo come un singolo sistema coeso all’utente finale (+: distribuzione geografica, condivisione delle risorse, scalabilità, fault tolerance, trasparenza);
• sistemi decentralizzati: più nodi, sparsi in più località, condividono il controllo e la potenza computazionale senza un’autorità centrale. Ogni nodo opera in maniera indipendente ma collabora con altri per ottenere un obiettivo comune (+: controllo distribuito, fault tolerance, scalabilità, coordinazione e comunicazione, autonomia e ridondanza);
• modello peer-to-peer: i nodi agiscono sia come client che come server. I pari (peers) rendono una parte delle proprie risorse direttamente disponibili ad altri partecipanti della rete, senza la necessità di coordinazione di server o host stabili.

Modelli di comunicazione

• sincrono: tutti i processi condividono lo stesso clock, c’è un limite superiore alla consegna di messaggi;
• asincrono: l’assunzione più debole possibile.

Consenso distribuito

La decentralizzazione rimuove la figura di un coordinatore centrale. I processi distribuiti devono accordarsi su un singolo valore (es. il nuovo stato del sistema).

Le proprietà:

• agreement: se un processo corretto decide un valore, allora tutti i processi corretti decideranno infine lo stesso valore;
• termination: ogni processo corretto deciderà infine un valore.

Un fallimento, in questo contesto, è una condizione che che comporta il fallimento di una unità funzionale nello svolgere la funzione richiesta:

• fallimento “benigno”: un nodo smette di compiere l’operazione che gli è richiesta (es. crash);
• fallimento bizantino (arbitrario): un nodo inizia a compiere operazioni arbitrarie, non presenti nel corretto flusso delle operazioni.

Consenso di Fischer, Lynch, Paterson (FLP consensus)

Il consenso di Fisher, Lynch e Paterson determina l’impossibilità di un consenso distribuito con un processo faulty. Non c’è nessun protocollo deterministico che risolve il consenso in un sistema asincrono in cui al massimo un processo può fallire crashando.

Il modello di computazione del consenso FLP si applica a sistemi asincroni distribuiti, in cui i messaggi possono essere ritardati in maniera indefinita. Anche il crash di un singolo nodo (mancata risposta) può impedire la garanzia di un agreement usando un protocollo di consenso deterministico.

Blockchain e sorpasso di FLP

Blockchain utilizza delle assunzioni rilassate, come una parziale sincronia, in cui la consegna dei messaggi è limitata oltre un certo punto non noto. Blockchain ha una finalità probabilistica: i nodi si accorderanno, infine, con la catena più lunga. La probabilità di decisioni conflittuali (forks) diminuisce esponenzialmente con il numero di conferme. Si aggiunge la proof of work, che garantisce che la riscrittura della catena diventa computazionalmente non fattibile per un avversario con meno del 50% della potenza di mining, e dei trade offs sacrificando la velocità in favore della fault tolerance, operando in modello con ritardi impliciti e potenziali fork.

Algoritmo del consenso di Paxos

L’algoritmo del consenso di Paxos è un protocollo che garantisce che, in un sistema distribuito, tutti i nodi della rete si accordino su un singolo valore, anche in presenza di problemi di rete e di fallimenti benigni dei nodi.

Il problema: un algoritmo per il consenso garantisce che un singolo, tra i valori proposti, viene scelto. Se nessun valore è proposto, allora nessun valore deve essere scelto. Se un valore è stato scelto, allora i processi devono essere in grado di apprendere il valore scelto.

I requisiti di sicurezza:

• solo un valore che è stato proposto può essere scelto;
• solo un singolo valore è scelto;
• un processo non apprende mai che un valore è stato scelto, a meno che non lo sia per davvero.

Con il consenso di Paxos:

• si raggiunge l’accordo su un risultato;
• una volta che la maggioranza è d’accordo su una proposta, quello è il consenso;
• il consenso raggiunto sarà infine noto per tutti;
• le parti coinvolte vogliono accordarsi su un qualsiasi risultato, non sulla sua proposta;
• i canali di comunicazione possono essere faulty e quindi i messaggi possono essere persi;
• ci si affida in pratica a un meccanismo di sincronia parziale (es con timeout adattivi).

Modello del Sistema

L’algoritmo prevede tre ruoli, svolti da tre classi di agenti: proposers, acceptors e lerarners.

Si assume che gli agenti possano comunicare gli uni con gli altri inviando messaggi. Si usa un modello personalizzato, asincrono, non bizantino, in cui:

• gli agenti operano a velocità arbitraria, possono fallire arrestandosi e possono riavviarsi. Siccome tutti gli agenti possono fallire dopo un certo valore è stato scelto e riavviarsi, una soluzione è impossibile a meno che alcune informazioni possono essere ricordate da un agente;
• i messaggi possono impiegare un tempo arbitrariamente lungo per essere consegnati, possono essere duplicati e persi, ma non corrotti.

Il modo naïve per scegliere un valore è avere un singolo agente acceptor. Un proposer invia una proposta all’acceptor, che sceglie il primo valore proposto che riceve.

Usando più acceptors, una proposer invia una proposta a un insieme di acceptors e uno di questi può accettare il valore proposto. Il valore viene scelto quando un insieme sufficientemente grande di acceptors l’hanno accettato.

Per garantire che un solo un singolo valore sia scelto, si può considerare che un insieme sia composto da una maggioranza qualsiasi degli agenti noti. Poiché qualsiasi due maggioranze hanno almeno un acceptor in comune, questo funziona se un acceptor può accettare al massimo un valore³.

Byzantine fault tolerance (BFT)

La byzantine fault tolerance (BFT) è l’abilità di un rete decentralizzata di selezionare e rigettare informazioni false dai partecipanti della rete. La BFT permette alla rete di funzionare anche quando i nodi diventano faulty e malevoli:

• agreement: tutti i nodi “leali” decidono lo stesso valore;
• validity: se il comandante è leale, tutti i generali seguono l’ordine.

Tutte le blockchains decentralizzate devono risolvere il problema dei generali bizantini, in cui la decisione rappresenta lo stato corrente del sistema. Un fallimento avviene se il sistema non riesce a distinguere i nodi faulty dai nodi funzionanti e quindi confonde transazioni valide con fraudolente. Il meccanismo di consenso deve stabilire forti incentivi per fare in modo che i partecipanti della rete lavorino in modo onesto e per scoraggiarli ad agire in maniera malevola.

Consistency, Availability and Partition

Consistency, Availability e Partition afferma che è impossibile per un data store distribuito offrire più di due delle tre garanzie: consistency, availability e partition.

Nel dettaglio:

• consistency (consistenza): in ogni momento, tutti i nodi della rete hanno lo stesso valore più recente;
• availability (disponibilità): ogni richiesta della rete riceve una risposta, ma senza garanzia che il dato ritornato sia il più recente;
• partition tolerance: la rete continua a operare anche con un numero arbitrario di nodi in fallimento.

Availability over Consistency (A+P)

Quando la availability è preferita alla consistenza, il sistema processerà sempre le query e tenterà di ritornare la versione più recente del dato, anche se non può garantire cje è aggiornato a causa del partizionamento della rete.

→ mancanza di consistenza

Consistency over availability (C+P)

Quando la consistenza è preferita alla disponibilità, il sistema processerà le query solo se i dati sono aggiornati.

→ sistema non disponibile

In Blockchain

In blockchain, si preferisce sacrificare la consistenza immediata per la disponibilità e la partition tolerance. Richiedendo la blockchain delle conferme, la consistenza sarà infine raggiunta.

Footnotes

1. Con alta min-entropia si intende che la sorgente produce valori molto difficili da indovinare, poiché nessun esito è significativamente più probabile degli altri. ↩

2. Ad esempio, la grandezza del blocco di Bitcoin e il limite nella capacità transazionale: Bitcoin può gestire al massimo 7 transazioni per secondo in media e il ritardo per la conferma è di almeno 10 minuti. Con Ethereum, vi è la congestione con il boom di NFT o DeFi e questo comporta alte commissioni. ↩

3. Perché la maggioranza garantisce unicità? - Da Claude Supponi di avere 5 acceptor. Per scegliere un valore, ne servono almeno 3 che lo accettino. Ora chiediti: è possibile che il sistema scelga contemporaneamente due valori diversi A e B?

   • Per scegliere A servono almeno 3 acceptor che accettano A.
   • Per scegliere B servono almeno 3 acceptor che accettano B.
   • Ma 3 + 3 = 6, e gli acceptor sono solo 5. È matematicamente impossibile trovare due gruppi da 3 dove ogni elemento accetta un valore diverso, perché i “posti” non bastano. Almeno un acceptor dovrebbe comparire in entrambi i gruppi, e poiché ogni acceptor accetta al massimo un valore, non può contribuire sia alla scelta di A che a quella di B. Quindi il sistema non può mai trovarsi nella situazione in cui due valori sono stati entrambi scelti.
   ↩