Questo è il primo di una serie di post che spiegano i protocolli di consenso descritti nel progetto Coordicidio di IOTA.
L'obiettivo principale di questa serie è quello di tenere la comunità aggiornata sui recenti risultati delle ricerche ed anche di spiegare interessanti questioni di ricerca che hanno buone possibilità di essere finanziati dal fondo Coordicidio. Come vedrete, l'argomento è piuttosto vasto e ci sono molte connessioni e dipendenze da altre parti del progetto Coordicidio.
Di fronte a questa complessità, cercheremo di spiegare solo alcuni punti alla volta e ci concentreremo sulle domande che sono attualmente in fase di ricerca. Detto questo, notiamo che IOTA ha già tutti gli ingredienti necessari per una soluzione efficiente e sicura per il Coordicide.
Le altre domande riguardano, ad esempio, l'ottimizzazione della soluzione:
Ora, scendiamo al punto e comprendiamo che cosa è a tutti gli effetti questo "consenso".
Gli algoritmi di consenso distribuito consentono ai sistemi in rete di accordarsi su uno stato o un'opinione richiesta in situazioni in cui il processo decisionale decentralizzato è difficile o addirittura impossibile.
La computazione distribuita è intrinsecamente inaffidabile. Il raggiungimento del consenso permette ad un sistema distribuito di funzionare come un'unica entità. L'importanza di questa sfida deriva dalla sua onnipresenza in cui la tolleranza ai guasti è uno degli aspetti fondamentali.
Esempi comuni includono: file system replicati, sincronizzazione dell'orologio, allocazione delle risorse, pianificazione delle attività ed infine, registri distribuiti.
I sistemi distribuiti costituiscono un argomento vasto e classico dell'informatica e lo stesso vale per i protocolli di consenso associati: vedi "How does distributed consensus work" (ndr articolo in inglese) per un'elegante introduzione a questo argomento.
I protocolli di consenso esistenti sono essenzialmente i protocolli classici - ad esempio quelli basati su PAXOS - ed il recente ed innovativo: consenso di Nakamoto. Entrambi i protocolli hanno serie restrizioni.
I protocolli classici hanno una complessità quadratica dei messaggi, richiedono una conoscenza precisa dei membri e sono piuttosto fragili contro i disturbi. Il protocollo Nakamoto, d'altra parte, è robusto e non richiede affiliazioni precise. Tuttavia, si basa sul PoW, il che porta a problemi ben noti come le gare del miming e la mancanza di scalabilità.
Guardiamo prima di tutto al consenso di Nakamoto. Una brillante idea del consenso di Nakamoto è quella di rendere il consenso non deterministico o probabilistico. Invece di far concordare tutti i nodi del sistema (distribuito) sulla correttezza di un valore, essi concordano sulla "probabilità" che quel valore sia corretto.
Il ruolo del leader nei protocolli tradizionali di consenso è assunto dal nodo che risolve per primo e più velocemente un dato puzzle computazionale; questo vincitore aggiunge un nuovo blocco alla blockchain. In questo modo, la rete (distribuita) costruisce la blockchain in continua crescita e concorda sulla validità della catena più lunga o della catena con le maggiori difficoltà cumulative.
Allora perché questo consenso è probabilistico? Per sapere che una certa transazione sarà considerata valida, ad esempio in 100 giorni, dobbiamo sapere che la catena più lunga in 100 giorni conterrà questa transazione.
In altre parole, siamo interessati alla probabilità che la catena più lunga in 100 giorni conterrà questa transazione. La probabilità che una transazione non venga annullata aumenta man mano che il blocco che contiene la transazione affonda "più in profondità" nella catena.
Nella blockchain di bitcoin, ad esempio, si consiglia di attendere fino a quando una transazione non è a sei blocchi di profondità nella blockchain. Dopo questa profondità, la probabilità che una transazione venga invertita è molto bassa.
Questo effetto vale anche per il Tangle. Più in profondità - o più "avvolta" dal Tangle - è una transazione e diventa più definitiva. Nella figura seguente, la transazione di colore verde scuro è convalidata da tutte le transazioni di colore verde chiaro. Man mano che il numero di transazioni di colore verde chiaro cresce, la probabilità che la transazione di colore verde scuro si troverà nel futuro Tangle converge a 1.
Ma aspetta, il Tangle è diverso da una blockchain! Mentre per la blockchain non è permesso di contenere due transazioni in conflitto, il Tangle può contenere temporaneamente tali transazioni. Pertanto, può accadere che un partecipante malevolo alleghi due transazioni in conflitto in diverse parti del Tangle, come i quadrati verde scuro ed arancione nell'immagine qui sopra.
Queste transazioni possono "sopravvivere" nel Tangle per un breve periodo di tempo fino a quando i nodi onesti non rilevano il conflitto. Una volta individuato il conflitto, i nodi decidono quale transazione scegliere. Nell'esempio precedente, la transazione verde più scura è "più avvolta" dal Tangle e dovrebbe essere approvata da tutti i nodi.
Affinché il groviglio diventi un vero e proprio protocollo di consenso, dobbiamo decidere in merito alle transazioni in conflitto. Tale decisione dovrebbe essere presa utilizzando un protocollo di consenso.
Ci siamo mossi in tondo? Fortunatamente no: il Coordicidio propone altri due protocolli di consenso:
Il resto di questo post sarà dedicato a una breve introduzione a FPC ed a spiegare come raggiungere il consenso quando si tratta di decidere se una singola transazione è valida o meno.
In un futuro post, si affronterà il motivo per cui questo è sufficiente per raggiungere il consenso a livello di Tangle e si discuterà la finalità delle transazioni nel Tangle.
In termini elaborati, l'FPC è un protocollo di consenso binario probabilistico senza leader di bassa complessità comunicativa che è robusto in un'infrastruttura bizantina - controlla l'articolo originale di Serguei Popov e Bill Buchananan.
Vediamo, mentre procediamo su ciò che tutti questi termini significano realmente e cominciamo a presentare una versione più leggera del FPC che è facile da implementare e contiene la maggior parte delle caratteristiche importanti.
Assumiamo che la rete abbia n nodi indicizzati per 1,2,…,n. Ogni nodo ha un'opinione od uno stato. Denotiamo s_i(t) per l'opinione del nodo i al tempo t. Le opinioni hanno valore in {0,1}; essendo la ragione per cui si parla di un consenso binario.
L'idea di base è il voto a maggioranza. Ad ogni turno, ogni nodo interroga nodi k nodi casuali ed imposta la sua opinione uguale alla maggioranza dei nodi interrogati. Tutto qui! Tuttavia, questa votazione a maggioranza semplice si rivela fragile contro i nodi difettosi e gli aggressori malevoli. Ha bisogno di un ingrediente aggiuntivo, in realtà un'ulteriore casualità, per renderlo robusto.
Più formalmente, ad ogni passo, ogni nodo sceglie k nodi casuali C_i, interroga le loro opinioni e calcola l'opinione mediana.
Indichiamo 𝝉 ∊ [0,1] la prima soglia che permette una certa natura asimmetrica del protocollo, altro argomento che affronteremo in un prossimo futuro. Inoltre, introduciamo "ulteriore casualità"; lasciamo U_{t}, i=1, 2,… essere variabili casuali i.i.d. con legge Unif (𝜷, 1- 𝜷) per alcuni parametri 𝜷 ∊ [0,1/2].
Ogni volta, ogni nodo i usa le opinioni dei nodi casuali k per aggiornare la propria opinione:
e per t>0:
E' importante che ad ogni round un nodo interroghi un diverso insieme casuale di nodi e che le variabili casuali U_t siano aggiornate anche in ogni round.
Introduciamo una regola di terminazione locale per ridurre la complessità di comunicazione del protocollo. Ogni nodo mantiene una variabile contatore cnt che viene incrementata di 1 se non vi è alcun cambiamento di opinione e che viene impostata a 0 se vi è un cambiamento di opinione.
Una volta che il contatore raggiunge una certa soglia l, cioè cnt≥1, il nodo considera lo stato attuale come definitivo. Il nodo non invierà quindi più alcuna domanda, ma risponderà comunque alle domande in arrivo. I grafici successivi mostrano le evoluzioni tipiche della variabile cnt per ogni nodo con l=5, k=10 e opinioni iniziali del 90% di 1 e del 10% di 0.
Nel'animazione a sinistra il protocollo non è disturbato, ma in quella di destra il 20% dei nodi sta cercando maliziosamente di ribaltare la maggior parte dei nodi onesti. In entrambi i casi, alla fine tutti i nodi onesti sono d'accordo sulla maggioranza iniziale.
Vogliamo evidenziare la caratteristica delle soglie casuali comuni dell'FPC e fare riferimento a "Simulation of the FPC" per una prima analisi dell'FPC per diversi tipi di parametrizzazione e strategie di attacco.
L'importanza dell'incertezza in guerra è stata introdotta da Carl von Clausewitz:
La guerra è il campo dell'incerto. I tre quarti delle cose su cui si basa per agire sono immerse nella nebbia dell'incertezza. Perciò è necessaria per prima cosa un'intelligenza molto penetrante per giungere all'intuizione della verità mediante il proprio raziocinio.
Carl von Clausewitz, 1873
Che cosa ha questo a che fare con le soglie casuali nel FPC? Votando in maggioranza semplice, queste soglie sarebbero pari a 0,5. Una strategia di attacco fruttuosa potrebbe essere quella di mantenere gli η dei nodi onesti intorno allo 0,5 impedendo una convergenza del protocollo (vedremo in seguito un attacco così riuscito). L'idea di Popov e Buchananan era di aggiungere "rumore" o "nebbia" al sistema per aumentare l'incertezza delle informazioni per i potenziali aggressori.
Perché tutto questo è così importante? In una situazione senza nodi melvoli, la distribuzione degli η sarà vicina ad una distribuzione normale:
Già in una situazione non disturbata, le opinioni dei nodi onesti possono rimanere vicine a situazioni 50:50. Tuttavia, gli effetti casuali, causati dal voto casuale, portano infine alla convergenza del protocollo. Questa situazione è completamente diversa in un'infrastruttura bizantina.
Consideriamo una strategia avversaria che suddivide i nodi onesti in due gruppi egualmente dimensionati di opinioni diverse che portano ad una distribuzione dei η tra nodi onesti come:
Quindi, come può un avversario raggiungere questo obiettivo?
L'avversario aspetta che tutti i nodi onesti abbiano ricevuto opinioni da tutti gli altri nodi onesti. L'avversario calcola quindi la mediana di questi η intermedi. Ora, l'avversario cerca di mantenere la mediana dei η vicino a 0,5 cercando di massimizzare le variazioni dei η.
Come può FPC prevenire un tale attacco? Sostituendo la soglia deterministica (rossa, tratteggiata) con soglie casuali (blu, tratteggiata). Nel grafico seguente, ogni linea blu rappresenta una soglia casuale di un dato round. Poiché queste soglie sono casuali, l'avversario non può prevedere come dividere i nodi onesti per mantenere la situazione del 50:50. Il modo migliore è di dividerli ancora intorno al valore 0,5.
Tuttavia, una volta che una linea blu (in r3 nella figura sotto) è abbastanza lontana dalla linea rossa, l'avversario perde il controllo dei nodi onesti ed il protocollo termina.
Nella seguente animazione si può vedere il comportamento e l'esito del protocollo quando questa strategia contraddittoria viene applicata senza casualità (soglia=0,5) e dopo l'aggiunta della casualità. Come si può vedere, l'avversario riesce a mantenere i nodi nel limbo per un lungo periodo di tempo. Ma, peggio ancora, la rete ha un'opinione divisa - portando ad un fallimento dell'accordo. Tuttavia, dopo l'introduzione della casualità aggiuntiva, il protocollo si conclude rapidamente ed in coesione.
Infine - ma non meno importante - torniamo ad alcuni dei punti su cui IOTA sta attualmente lavorando e segnaliamo alcuni esempi di future collaborazioni:
Non vediamo l'ora di portarvi con noi nell'entusiasmante viaggio del Coordicidio attraverso gli occhi del dipartimento di ricerca e speriamo che possiate godere dello sviluppo di questo progetto come noi.
Come sempre, accogliamo con favore i vostri commenti e domande sia qui nei commenti o in #tanglemath su Discord. Puoi anche impegnarti in una più intensa collaborazione scientifica con noi e richiere una sovvenzione.
L'autore originale non è membro della IOTA Foundation. Ha scritto questo blogpost in collaborazione con i membri del gruppo di ricerca IOTA.
Il testo originale in lingua inglese si trova qui: https://blog.iota.org/consensus-in-the-iota-tangle-fpc-b98e0f1e8fa
Per ulteriori informazioni in italiano o tedesco trovate i miei contatti a questa pagina.
Se avete trovato utile la mia libera traduzione, accetto volentieri delle donazioni ;)
IOTA:QOQJDKYIZYKWASNNILZHDCTWDM9RZXZV9DUJFDRFWKRYPRMTYPEXDIVMHVRCNXRSBIJCJYMJ9EZ9USHHWKEVEOSOZB
BTC:36yzaypPy6qmNnFGVTBsRPXaVdFbruFSMm
Non garantisco nulla e mi libero da ogni responsabilità.
