Il protocollo di consenso Stellar è stato descritto per la prima volta in di David Mazieres nel 2015. Si tratta di un "sistema federativo di consenso bizantino", che permette a reti di calcolo decentralizzate senza leader di raggiungere efficientemente un consenso su una qualsiasi decisione. La rete di pagamento Stellar utilizza il Stellar Consensus Protocol (SCP) per mantenere una storia delle transazioni coerente, visibile a tutti i partecipanti.
Si considera che i protocolli di consenso siano difficili da comprendere. L'SCP è più semplice della maggior parte di essi, ma condivide comunque questa reputazione, in parte a causa dell'idea errata che il "voto federativo", di cui si parla nella prima metà dell'articolo scientifico, sia l'SCP. Ma non è così! È solo un importante mattoncino che nella seconda metà dell'articolo viene utilizzato per costruire il vero protocollo di consenso Stellar.
In questo articolo spiegheremo brevemente cosa sia un "sistema di accordo", cosa possa renderlo "bizantino" e perché rendere un sistema bizantino "federativo". Poi spiegheremo la procedura di voto federativa descritta nell'articolo sul SCP, e infine spiegheremo il protocollo SCP stesso.
Sistemi di accordo
Un sistema di accordo consente a un gruppo di partecipanti di raggiungere un consenso su una qualche questione, ad esempio cosa ordinare per pranzo.
Noi di Interstellar abbiamo implementato il nostro sistema di accordo per il pranzo: ordiniamo ciò che dice il nostro manager operativo, John. È un sistema semplice ed efficace. Ci fidiamo tutti di John e crediamo che ogni giorno troverà qualcosa di interessante e nutriente.
Ma cosa succede se John abusa della nostra fiducia? Potrebbe decidere unilateralmente che tutti noi dobbiamo diventare vegani. Tra una settimana o due, probabilmente lo deporremo e daremo il potere a Elizabeth. Ma improvvisamente, potrebbe amare l'avocado con le acciughe e pensare che tutti debbano essere come lei. Il potere corrompe. Quindi è meglio trovare un metodo più democratico: un modo per assicurarsi che diverse preferenze siano considerate, mentre si garantisce un risultato chiaro e tempestivo, per evitare che nessuno ordini pranzo o che cinque persone facciano ordini diversi, o che la discussione si protragga fino alla sera.
A prima vista, la soluzione sembra semplice: fare una votazione! Ma è un'impressione ingannevole. Chi si occuperà di raccogliere le schede e comunicare i risultati? E perché gli altri dovrebbero credere a ciò che dirà? Forse possiamo prima di tutto votare per un leader di cui ci fidiamo per guidare la votazione — ma chi guiderà questa prima votazione? E se non riusciamo a trovare un accordo su un leader? O se troviamo un accordo, ma quel leader è bloccato in un incontro o va in malattia?
Problemi simili si presentano nelle reti di computer distribuite. Tutti i partecipanti o nodi devono concordare su una certa decisione, come chi è il turno di aggiornare un file condiviso o prendere un compito dalla coda di elaborazione. Nella rete di criptovalute, i nodi devono spesso scegliere quale sia la storia completa, tra diverse versioni possibili, che talvolta sono in conflitto. Questo accordo di rete garantisce al destinatario che la moneta è (a) valida (non contraffatta) e (b) non è stata ancora spesa altrove. Garantisce anche che potrà spendere le monete in futuro, poiché il nuovo destinatario avrà le stesse garanzie per le stesse ragioni.
Qualsiasi sistema di consenso in una rete di calcolo distribuito deve essere resilienti agli errori: deve fornire risultati coerenti nonostante errori quali linee di comunicazione lente, nodi non reattivi e ordine sbagliato dei messaggi. Il sistema di consenso bizantino è ulteriormente resistente agli errori "bizantini": nodi che forniscono informazioni false, che siano a causa di un errore o di un tentativo intenzionale di minare il sistema o ottenere un certo vantaggio. La resilienza "bizantina" — la capacità di fidarsi di una decisione di gruppo, anche quando alcuni membri del gruppo possono mentire o in altro modo non seguire le regole della decisione — prende il suo nome dalla , che cercavano di coordinare un attacco. è quella di Anthony Stevens.
Consideriamo il proprietario della criptovaluta Alice, che deve scegliere tra comprare un delizioso gelato da Bob e pagare il debito a Carol. È possibile che Alice voglia pagare entrambi contemporaneamente, spendendo la stessa moneta in modo fraudolento. Per farlo, deve convincere il computer di Bob che la moneta non è mai stata pagata a Carol e convincere il computer di Carol che la moneta non è mai stata pagata a Bob. Un sistema di accordo bizantino rende praticamente impossibile questo utilizzando una forma della regola della maggioranza, chiamata quorum. Un nodo in una tale rete rifiuta di passare a una certa versione della storia finché non vede che un numero sufficiente di nodi peer-to-peer — il quorum — è d'accordo su tale passaggio. Una volta che ciò avviene, formano un blocco elettorale sufficientemente grande da costringere i nodi rimanenti della rete ad accettare la loro decisione. Alice può convincere alcuni nodi a mentire a suo nome, ma se la rete è abbastanza grande, il suo tentativo sarà soffocato dai voti dei nodi onesti.
Quanti nodi sono necessari per un quorum? Al minimo, la maggioranza, e più precisamente, una maggioranza qualificata per affrontare errori e frodi. Ma per contare la maggioranza, è necessario conoscere il numero totale di partecipanti. Nell'ufficio Interstellar o nelle elezioni circondariali, questi numeri sono facili da ottenere. Ma se il tuo gruppo è una rete scarsamente definita, dove i nodi possono entrare ed uscire a piacimento senza coordinarsi con un centro, allora è necessario un sistema federativo di accordo bizantino, capace di determinare i quorum non da un elenco di nodi predefiniti, ma in modo dinamico, da uno snapshot in continua evoluzione e inevitabilmente incompleto dei nodi in un dato momento.
Può sembrare impossibile creare un quorum dal punto di vista di un singolo nodo in una vasta rete, ma è possibile. Tale quorum può anche garantire i risultati di un voto decentralizzato. Un documento tecnico SCP dimostra come farlo attraverso una procedura chiamata votazione federativa.
Per gli impazienti
Il resto dell'articolo descrive più in dettaglio la votazione federativa e il protocollo di consenso Stellar. Se non ti interessano i dettagli, ecco una panoramica generale del processo.
- I nodi conducono round di voto federale sui "nominati". Un round di voto federale significa:
- Il nodo vota per quanto riguarda un'affermazione, ad esempio, "Propongo il valore V";
- Il nodo ascolta le voci dei partecipanti finché non trova quella che può "accettare";
- Il nodo cerca il "quorum" per questa affermazione. Il quorum "conferma" il nominato.
- Non appena il nodo può confermare uno o più nominati, cerca di "preparare" una "scheda" attraverso diversi round di voto federale.
- Quando il nodo è in grado di verificare la prontezza della scheda, tenta di impegnarla con ulteriori round di voto federale.
- Una volta che il nodo può confermare l'impegno della scheda, può "esternaizzare" il valore di questa scheda, utilizzandola come risultato del consenso.
Questi passaggi comprendono diversi round di voto federale, i quali insieme formano un solo round SCP. Approfondiamo cosa succede in ogni fase.
Voto federale
Il voto federale è la procedura per determinare se la rete può concordare su una proposta. In un round di voto, ogni nodo deve scegliere uno dei potenzialmente molti valori. Non può farlo finché non è certo che altri nodi nella rete non sceglieranno un altro risultato. Per essere certi di ciò, i nodi si scambiano un'infinità di messaggi avanti e indietro, in modo che ognuno confermi, che quorum nodi accettano lo stesso risultato. Il resto di questa sezione spiega i termini in questa affermazione e come si svolge l'intera procedura.
Quorum e fette di quorum
Iniziamo definendo il quorum. Come abbiamo discusso sopra, in una rete decentralizzata con membri dinamici, non è possibile sapere in anticipo il numero di nodi e dunque quanti servano per la maggioranza. Il voto federale risolve questo problema introducendo una nuova idea fetta di quorum (quorum slice): un piccolo insieme di nodi equivalenti ai quali un nodo si fida per trasmettere informazioni sullo stato del voto al resto della rete. Ogni nodo definisce la propria fetta di quorum (di cui diventa membro di fatto).
La formazione del quorum inizia con il taglio del quorum. Per ogni nodo vengono aggiunti i nodi del suo taglio. Poi vengono aggiunti i membri dei tagli di questi nodi e così via. Man mano che si procede, si trovano sempre più nodi che non si possono aggiungere perché sono già inclusi nel taglio. Quando non ci sono più nuovi nodi da aggiungere, il processo si ferma: abbiamo formato un quorum tramite la "chiusura transitiva" del taglio del nodo iniziale.
Per trovare un quorum da un dato nodo…
… aggiungiamo i membri del suo taglio…
… poi aggiungiamo i membri dei tagli di questi nodi.
Continuiamo finché non ci sono più nodi da aggiungere.
Non ci sono più nodi da aggiungere. Questo è il quorum.
In effetti, ogni nodo può appartenere a più di un taglio. Per formare un quorum, scegli solo uno dei tagli e aggiungi i membri; poi seleziona qualsiasi taglio per ciascuno dei membri e aggiungi membri di questo taglio e così via. Ciò significa che ogni nodo è membro di un insieme di possibili quorums.
Scegli solo un taglio di quorum ad ogni passo.
Un possibile quorum. O un'alternativa…
… scegliamo altri tagli…
…(quando possibile)…
… crea un altro quorum.
Come fa un nodo a sapere in quali tagli si trovano gli altri nodi? Proprio come altre informazioni sugli altri nodi: dalle trasmissioni che ogni nodo invia nella rete quando cambia il suo stato di voto. Ogni trasmissione include informazioni sui tagli del nodo mittente. Nel documento tecnico SCP non è specificato il meccanismo di comunicazione. Le implementazioni solitamente usano per garantire la trasmissione dei messaggi su tutta la rete.
Ricordiamo che nel sistema di accordi bizantini non federativi il quorum è definito come la maggioranza di tutti i nodi. Il sistema di accordi bizantini è stato progettato considerando la seguente domanda: quanto possono tollerare il sistema nodi disonesti? In un sistema con N nodi, progettato per resistere a f guasti (inganni), un nodo deve essere in grado di progredire ricevendo risposte da N−f peer, poiché f di essi potrebbero non funzionare. Tuttavia, ricevendo risposte da N−f peer, si può presumere che tutti i f peer (da cui il nodo non ha ricevuto risposta) siano effettivamente onesti. Pertanto, i peer disonesti sono f di N−f peer (da cui si è ricevuta risposta). Affinché i nodi raggiungano un consenso, deve esserci una maggioranza di nodi onesti tra gli altri, ovvero è necessario che N−f sia maggiore di 2f oppure N > 3f. Quindi, di solito un sistema progettato per sopravvivere a f guasti avrà in totale N=3f+1 nodi e una dimensione del quorum di 2f+1. Non appena la proposta supera la soglia del quorum, gli altri membri della rete sono convinti che eventuali proposte concorrenti falliranno. Così la rete converge verso il risultato.
Ma nel sistema di accordi bizantini federativi non può esserci solo una maggioranza (perché nessuno conosce la dimensione complessiva della rete), e il concetto di maggioranza è completamente inutile! Se l'appartenenza al sistema è aperta, qualcuno può ottenere la maggioranza semplicemente effettuando quella che viene chiamata l'attacco di Sybil: unendosi alla rete più volte tramite diversi nodi. Quindi, come si può chiamare quorum, e come è in grado di sopprimere proposte concorrenti?
Tecnicamente, non c'è modo! Immagina una rete di sei nodi, dove due gruppi di tre sono isolati nei quorum degli altri. Il primo sottogruppo può prendere decisioni di cui il secondo non sentirà mai parlare, e viceversa. Per questa rete non esiste un modo per raggiungere un consenso (se non per caso).
Pertanto, SCP richiede che per il voto federativo (e per l'applicazione di teoremi importanti dell'articolo) la rete debba possedere una proprietà chiamata intersezione dei quorum. Nella rete con questa proprietà, qualsiasi due quorum che possono essere costruiti si sovrappongono sempre in almeno un nodo. Per definire i sentimenti prevalenti nella rete, è altrettanto utile che avere una maggioranza. Intuitivamente, questo significa che se un qualche quorum è d'accordo con l'affermazione X, nessun altro quorum sarà mai in grado di concordare su qualcos'altro, perché dovrà includere qualche nodo del primo quorum che ha già votato per X.
Se nella rete ci sono sovrapposizioni tra i quorum…
…allora qualsiasi due quorum che puoi costruire…
…si sovrapporranno sempre.
(Naturalmente, i nodi sovrapposti possono rivelarsi beati bizantini o difettosi in altri aspetti. In tal caso, la sovrapposizione dei quorum non aiuta affatto la rete a raggiungere un consenso. Per questa ragione, molti risultati nel documento tecnico SCP si basano su assunzioni esplicitamente dichiarate, come quella che ci sia ancora sovrapposizione di quorum nella rete anche dopo la rimozione dei nodi difettosi. Per semplicità, lasceremo queste assunzioni implicite per il resto dell'articolo).
Può sembrare irragionevole aspettarsi una sovrapposizione affidabile dei quorum in una rete di nodi indipendenti. Ma ci sono due motivi per cui ciò accade.
Il primo motivo è l'esistenza stessa di Internet. Internet è un esempio ideale di una rete di nodi indipendenti con sovrapposizione dei quorum. La maggior parte dei nodi in Internet è collegata solo a pochi altri nodi locali, ma questi piccoli insiemi si sovrappongono a sufficienza affinché ogni nodo sia accessibile da ogni altro nodo attraverso un percorso o un altro.
La seconda ragione è specifica per la rete di pagamento Stellar (il più comune utilizzo di SCP). Ogni asset nella rete Stellar ha un emittente, e le linee guida di Stellar richiedono che ogni emittente designi uno o più nodi nella rete per gestire le richieste di rimborso. È nel tuo interesse includere direttamente o indirettamente questi nodi nei gruppi di quorum per ogni asset di tuo interesse. I quorum per tutti i nodi interessati da un dato asset si sovrapporranno almeno in questi nodi di rimborso. I nodi interessati a più asset includeranno nei loro gruppi di quorum tutti i nodi di rimborso degli emittenti corrispondenti e cercheranno di unire tutti gli asset insieme. Inoltre, qualsiasi asset che non è collegato in questo modo ad altri nella rete, e non deve essere collegato — è progettato affinché non ci siano sovrapposizioni di quorum in questa rete (per esempio, le banche della zona dollaro a volte vogliono commerciare con banche della zona euro e banche della zona peso, quindi si trovano nella stessa rete, ma nessuno di loro è interessato a una rete separata di bambini che commerciano figurine di baseball).
Certo, l'aspettativa di sovrapposizioni di quorum non è una garanzia. Altri sistemi di accordo bizantino sono complessi in gran parte a causa della garanzia dei quorum. Una novità importante di SCP è che solleva la responsabilità della creazione dei quorum dall'algoritmo di consenso e la porta a livello di applicazione. Pertanto, sebbene il voto federativo sia abbastanza comune per il voto su qualsiasi questione, in realtà la sua affidabilità dipende criticamente dal significato più ampio di questi valori. Alcuni tipi ipotetici di utilizzo potrebbero risultare meno convenienti per creare reti ben collegate rispetto ad altri.
Voto, approvazione e conferma
Nel round di voto federativo, un nodo inizia opzionalmente a votare per un valore V. Questo significa trasmettere alla rete un messaggio: 'Io sono il nodo N, i miei gruppi di quorum sono Q e voto per V'. Quando un nodo vota in questo modo, promette che non ha mai votato contro V e non lo farà mai.
Nelle trasmissioni dai nodi peer-to-peer, ogni nodo vede come votano gli altri. Una volta che un nodo raccoglie un numero sufficiente di questi messaggi, può monitorare i campioni di quorum e cercare di trovare i quorum. Se vede un quorum di peer che votano per V, può passare a l'accettazione di V e trasmettere questo nuovo messaggio nella rete: «Io sono il nodo N, i miei campioni di quorum Q e accetto V». L'accettazione fornisce una garanzia più forte rispetto al semplice voto. Quando un nodo vota per V, non può mai votare per altre opzioni. Ma se un nodo accetta V, nessun nodo nella rete accetterà mai un'altra opzione (teorema 8 nel documento tecnico SCP lo dimostra).
Certamente, c'è alta probabilità che non si trovi subito un quorum di nodi che concordano su V. Altri nodi potrebbero votare per altri valori. Ma per un nodo c'è un altro modo per passare dal semplice voto all'accettazione. N può accettare un altro valore W, anche se non ha votato per esso, e anche se non vede un quorum per esso. Per decidere di cambiare il proprio voto, è sufficiente vedere un insieme bloccante di nodi che hanno accettato W. Un insieme bloccante è composto da un nodo per ciascuno dei campioni di quorum di N. Come suggerisce il nome, è in grado di bloccare qualsiasi altro valore. Se tutti i nodi in un tale insieme accettano W, allora (secondo il teorema 8) non si potrà mai formare un quorum che accetti un valore diverso, e quindi per N è sicuro accettare W.
Il nodo N con tre campioni di quorum.
B-D-F è un insieme bloccante per N: include un nodo per ciascuno dei campioni di N.
B-E è anch'esso un insieme bloccante per N, perché E appare in due campioni di N.
Ma un insieme bloccante non è un quorum. Sarebbe troppo facile ingannare il nodo N affinché accetti il valore desiderato, se fosse sufficiente violare solo un nodo in ciascuno dei campioni di N. Pertanto, l'accettazione di un valore non segna la fine del voto. Invece, N deve confermare il valore, cioè vedere un quorum di nodi che lo accettano. Se N arriva così lontano, allora, come dimostra il documento tecnico SCP (nel teorema 11), anche il resto della rete alla fine confermerà lo stesso valore, quindi N completerà il voto federativo con un determinato valore come risultato.
Voto federativo.
Il processo di voto, approvazione e conferma costituisce un intero ciclo di voto federativo. Il protocollo di consenso Stellar riunisce molti di questi cicli per creare un sistema di consenso completo.
Protocollo di consenso Stellar
Le due caratteristiche più importanti di un sistema di consenso sono sicurezza e robustezza. Un algoritmo di consenso è "sicuro" se non può mai fornire risultati diversi a partecipanti diversi (la copia della storia di Bob non contraddirà mai quella di Carol). La "robustezza" significa che l'algoritmo fornisce sempre un risultato, cioè non si blocca mai.
La procedura di voto federativo descritta è sicura nel senso che se un nodo conferma un valore V, nessun altro nodo confermerà un altro valore. Ma "non confermare un altro valore" non significa necessariamente che debba confermare qualcosa. I partecipanti possono votare per un numero così elevato di valori diversi che nulla raggiungerà la soglia di accettazione. Questo significa che nel voto federativo non c'è robustezza.
Il protocollo di consenso Stellar utilizza il voto federativo in modo da garantire sia la sicurezza che la robustezza. (Le garanzie di sicurezza e robustezza dell'SCP hanno un limite teorico. La costruzione sceglie una garanzia di sicurezza molto forte, sacrificando un lieve indebolimento della robustezza, ma considerando un tempo sufficiente, è molto probabile che si raggiunga un consenso). In breve, l'idea è quella di condurre più voti federativi su diversi valori finché uno di essi non supera tutte le fasi di voto SCP descritte di seguito.
I valori per i quali l'SCP cerca consenso possono essere la storia delle transazioni, un ordine per il pranzo o qualcos'altro, ma è importante notare che non sono i valori che vengono accettati o confermati. Invece, il voto federativo si svolge su affermazioni su questi valori.
I primi round di voto federativo avvengono in fase di nomina (nomination phase), su un insieme di affermazioni del tipo "Nomino V", potenzialmente per molti valori diversi V. L'obiettivo della nomina è trovare una o più affermazioni che superino il processo di accettazione e conferma.
Dopo aver identificato i candidati verificabili, SCP passa alla fase di voto, dove l'obiettivo è trovare un certo ballottaggio (cioè un contenitore per il valore proposto) e il quorum che può dichiarare commit per esso (commit). Se il quorum effettua il commit del ballottaggio, il suo valore viene accettato come consenso. Ma prima che un nodo possa votare per il commit del ballottaggio, deve prima confermare l'annullamento di tutti i ballottaggi con un valore di contatore inferiore. Questi passaggi - l'annullamento dei ballottaggi per trovare quello per il quale si può confermare il commit - includono diversi turni di voto federato su diverse proposte di ballottaggio.
Nei prossimi paragrafi si descrivono più dettagliatamente le candidature e il voto.
Candidatura
All'inizio della fase di candidatura, ogni nodo può spontaneamente scegliere un valore V e votare per affermare "Candidatura di V". L'obiettivo in questa fase è confermare la candidatura di un certo valore tramite il voto federato.
È possibile che un numero sufficiente di nodi voti per affermazioni abbastanza diverse e nessuna candidatura riesca a raggiungere la soglia di accettazione. Pertanto, oltre a trasmettere i propri voti di candidatura, i nodi "rispecchiano" le candidature dei propri pari. Rispecchiare (echo) significa che se un nodo vota per la candidatura di V, ma vede un messaggio da un vicino che vota per la candidatura di W, ora voterà per candidare sia V che W. (Non tutti i voti dei pari vengono rispecchiati durante la candidatura, poiché ciò potrebbe portare a un'esplosione di diversi candidati. SCP include un meccanismo di regolazione di questi voti. In breve, esiste una formula per determinare la "priorità" di un pari dal punto di vista di un nodo e vengono rispecchiati solo i voti dei nodi ad alta priorità. Più a lungo dura la candidatura, più bassa è la soglia, quindi un nodo amplia l'insieme dei pari i cui voti rispecchierà. La formula di priorità come uno degli input include il numero di slot, quindi un nodo peer ad alta priorità per uno slot può essere a bassa priorità per un altro, e viceversa.
Concettualmente, la proposizione simultanea di V e W è una voce federativa separata, ognuna in grado di raggiungere l'adozione o la conferma in modo autonomo. Nella pratica, i messaggi del protocollo SCP raggruppano queste voci separate insieme.
Sebbene la votazione per la proposta di V rappresenti una promessa di non votare mai contro la proposta di V, a livello applicativo - in questo caso SCP - viene definito cosa significhi "contro". SCP non considera una dichiarazione che contraddica il voto "Propongo X", cioè non esiste un messaggio "Sono contro la proposta di X", pertanto il nodo può votare per la proposta di qualsiasi valore. Molte di queste nomination non porteranno a nulla, ma alla fine il nodo potrà adottare o confermare uno o più valori. Una volta che il nominato è confermato, diventa candidato.
Proposta di SCP utilizzando il voto federativo. Possono esserci molti valori "B" proposti da nodi alla pari e "riflessi" da un nodo.
La proposta di candidati può portare alla creazione di più candidati confermabili. Pertanto, SCP richiede che il livello applicativo fornisca un qualche metodo per unire i candidati in un composito (composite). Il metodo di unione può essere qualsiasi. L'importante è che, se questo metodo è deterministico, ogni nodo unirà gli stessi candidati. Nel sistema di voto per il pranzo, "unione" può semplicemente significare rinunciare a uno dei due candidati. (Ma in modo deterministico: ogni nodo deve scegliere lo stesso valore per il reset. Ad esempio, una scelta precedente in ordine alfabetico). Nella rete di pagamento Stellar, dove si vota sulla storia delle transazioni, l'unione di due candidati proposti implica l'unione delle transazioni che contengono e delle ultime delle loro due timeline.
La descrizione tecnica di SCP dimostra (teorema 12) che alla fine della fase di proposta la rete converge a un unico composito. Ma c'è un problema: il voto federativo è un protocollo asincrono (così come SCP). In altre parole, i nodi non sono coordinati nel tempo, ma solo nei messaggi che inviano. Dal punto di vista di un nodo, non è chiaro quando è concluso fase di proposta. Anche se tutti i nodi arriveranno infine allo stesso composto, possono scegliere percorsi diversi lungo il cammino, creando di volta in volta diversi candidati compositi, e non possono mai sapere quale di essi sarà quello finale.
Ma va bene. La proposta è solo una preparazione. È importante limitare il numero di candidati per raggiungere un consenso che si verifica nel processo di voto (voto).
Il voto
Un bollettino è una coppia , dove counter è un intero che inizia da 1 e value è il candidato della fase di proposta. Questo può essere un candidato proprio del nodo o un candidato di un nodo adiacente, accettato da questo nodo. In termini semplici, durante il voto si fanno più tentativi per far sì che la rete raggiunga un consenso su un candidato in un certo bollettino attraverso potenzialmente molte votazioni federative sulle dichiarazioni di bollettini. I contatori nei bollettini tengono traccia dei tentativi effettuati e i bollettini con contatori più alti hanno la priorità su quelli con contatori più bassi. Se il bollettino si impantana, inizia una nuova votazione, ora sul bollettino .
È importante distinguere i valori (per esempio, quale dovrebbe essere l'ordine del pranzo: pizza o insalate), i bollettini (coppia counter-value) e le dichiarazioni sui bollettini. Un round SCP comprende diversi round di votazione federativa, in particolare su tali dichiarazioni:
- "Sono pronto a impegnare il bollettino B" e
- "Dichiaro di impegnare il bollettino B"
Dal punto di vista di questo nodo, il consenso si raggiunge quando trova il bollettino B, per il quale può convalidare (cioè trovare un quorum accettante) la dichiarazione "Dichiaro di impegnare il bollettino B". Da quel momento, si può agire in modo sicuro sul valore indicato in B - ad esempio, effettuare questo ordine per il pranzo. Questo si chiama esternalizzazione del valore. Una volta confermato l'impegno del bollettino, il nodo può essere certo che qualsiasi altro nodo abbia esternalizzato lo stesso valore o lo farà necessariamente in futuro.
Sebbene concettualmente molte votazioni federative vengano svolte su dichiarazioni riguardanti molte schede diverse, esse scambiano non un gran numero di messaggi, perché ogni messaggio incapsula una serie di schede. Un messaggio, quindi, promuove lo stato di molte votazioni federative contemporaneamente, ad esempio: «Accetto il commit delle schede nell'intervallo da a ».
Cosa significano i termini «preparato» (prepared) e «commit» (commit)?
Un nodo vota per il commit della scheda quando è convinto che altri nodi non eseguiranno il commit di schede con valori diversi. Essere convinti di ciò è l'obiettivo della preparazione della dichiarazione. Il voto, che dice: «Sono pronto a commit della scheda B», è una promessa di non mai eseguire il commit di schede con un valore inferiore a B, cioè con un contatore più basso (SCP richiede che i valori delle schede abbiano un certo ordine. Pertanto, la scheda è inferiore a se N1<N2, e anche se N1=N2 e V1<V2). Queste schede minori vengono «annullate» (aborted) durante il voto di preparazione, mentre B è considerato «preparato».
Perché «Sono pronto a commit della scheda B» significa «Prometto di non mai eseguire il commit di schede con valore inferiore a B»? Perché SCP definisce abort come l'opposto di commit. Il voto per la preparazione della scheda implica anche un voto per annullare alcune altre schede, e, come discusso in precedenza, votare per qualcosa implica anche una promessa di non votare mai contro di esso.
Prima di trasmettere un commit, un nodo deve prima trovare una scheda che può confermare come preparata. In altre parole, svolge una votazione federativa sulla questione «Sono pronto a commit della scheda B», possibilmente per molte schede diverse, fino a trovare quella che accetta il quorumi.
Da dove provengono le schede per la preparazione del voto? Inizialmente, il nodo trasmette la preparazione al voto per , dove C è il candidato composito, prodotto nella fase di candidatura. Tuttavia, anche dopo l'inizio della preparazione al voto, la candidatura può portare alla comparsa di candidati aggiuntivi che diventeranno nuove schede. Nel frattempo, i peer possono avere candidati diversi e possono formare un insieme bloccante che accetta "Sono pronto a compromettere la scheda B2", il che convincerà il nodo ad accettarlo anch'esso. Infine, esiste un meccanismo di timeout che genera nuovi turni di votazione federativa su nuove schede con conteggi più elevati, se le schede attuali sono bloccate.
Non appena il nodo trova la scheda B, che può confermare come preparata, trasmette un nuovo messaggio "Impegno sulla scheda B". Questa votazione informa i peer che il nodo non rinuncerà mai a B. In effetti, se B rappresenta una scheda , allora "Impegno sulla scheda " implica un consenso incondizionato a votare per la disponibilità di ogni scheda da a . Questo valore aggiuntivo aiuta altri nodi a raggiungere un peer con l'impegno, se sono ancora in fasi precedenti del protocollo.
A questo punto vale la pena sottolineare ancora una volta che si tratta di protocolli asincroni. Solo perché un nodo invia voti per l'impegno, non significa che anche i suoi pari lo facciano. Alcuni di essi possono ancora votare su dichiarazioni per la preparazione al voto, altri potrebbero aver già esternalizzato il valore. SCP spiega come un nodo deve gestire ogni tipo di messaggio peer-to-peer indipendentemente dalla sua fase.
Se il messaggio «Dichiaro il commit » non può essere accettato o confermato, c'è la possibilità di accettare o confermare il messaggio o — o, in ogni caso, qualsiasi bollettino con valore C, e non con nessun altro, poiché il nodo ha già promessa di non annullare mai . Entro il momento in cui il nodo trasmette i voti per il commit, sarà C o nulla, a seconda di quanto lontano arriverà il consenso. Tuttavia, questo non è ancora sufficiente per il nodo per esternalizzare C. Alcuni festini bizantini (composti da meno di un quorum, basandosi sulle nostre assunzioni di sicurezza) possono mentire al nodo. L'accettazione e poi la conferma di un certo bollettino (o intervallo di bollettini) è ciò che dà al nodo la certezza di poter finalmente esternalizzare C.
Votazione SCP tramite voto federato. Non mostrato: a qualsiasi momento può attivarsi un timer, aumentando il conteggio nel bollettino (e, possibilmente, generando un nuovo composito da candidati supplementari proposti).
E questo è tutto! Una volta che la rete raggiunge il consenso, è pronta a farlo di nuovo e di nuovo. Nella rete di pagamento Stellar, questo avviene circa ogni 5 secondi: un'impresa che richiede sia sicurezza sia resilienza, garantite dal SCP.
SCP può raggiungere questo obiettivo affidandosi a diversi round di voto federato. Il voto federato è possibile grazie al concetto di slice di quorum: set di nodi peer-to-peer a cui ogni nodo ha deciso di fidarsi come parte del proprio (soggettivo) quorum. Questa configurazione significa che è possibile raggiungere un consenso anche in una rete con adesione aperta e inganni bizantini.
Ulteriori letture
- Il documento tecnico originale del SCP può essere trovato , ma progetto di specifiche per la sua implementazione.
- L'autore originale del protocollo SCP, David Mazieres, spiega semplificato (ma comunque tecnicamente) come funziona .
- Potresti essere sorpreso di non trovare in questo articolo i termini «mining» o «proof of work». SCP non utilizza questi metodi, ma alcuni altri algoritmi di consenso sì. Zain Wierszspin ha scritto un disponibile .
- di una semplice rete che raggiunge consenso in un solo round completo di SCP.
- Per i lettori interessati alle implementazioni di SCP: vedi. , utilizzato dalla rete di pagamento Stellar, o , che ho scritto per una migliore comprensione dello SCP.
Fonte: habr.com
