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 consente a reti di calcolo decentralizzate senza leader di raggiungere efficacemente un consenso su qualsiasi decisione. La rete di pagamento Stellar utilizza il Stellar Consensus Protocol (SCP) per mantenere una storia delle transazioni concordata, visibile a tutti i partecipanti.
Si ritiene che i protocolli di consenso siano difficili da comprendere. L'SCP è più semplice della maggior parte di essi, ma conserva comunque questa reputazione — in parte a causa della errata idea che il “voto federativo”, dedicato alla prima metà dell'articolo scientifico, sia l'SCP. Ma non è così! È solo un importante mattone costruttivo, utilizzato nella seconda metà dell'articolo per costruire il reale protocollo di consenso Stellar.
In questo articolo parleremo brevemente di cosa sia un "sistema di accordo", cosa possa renderlo "bizantino" e perché realizzare un sistema bizantino come “federativo”. Successivamente, spiegheremo la procedura di voto federativo descritta nell'articolo sul SCP e, infine, spiegheremo il protocollo SCP stesso.
Sistemi di accordo
Il sistema di accordi consente a un gruppo di partecipanti di giungere a un consenso su un determinato argomento, 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 di accordo 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? Può decidere da solo che tutti dobbiamo diventare vegani. Tra una settimana o due, probabilmente lo deporremo e faremo assumere i poteri a Elizabeth. Ma improvvisamente, lei ama l'avocado con le acciughe e pensa che tutti debbano diventare così. Il potere corrompe. È meglio quindi trovare un metodo più democratico: un modo per assicurarsi che vengano considerate le diverse preferenze, garantendo al contempo un risultato tempestivo e univoco, per evitare che nessuno ordini il pranzo o che cinque persone facciano ordini diversi, o che la discussione si protragga fino a sera.
Sembrerebbe che la soluzione sia semplice: fare un voto! Ma questa è un'impressione ingannevole. Chi raccoglierà le schede e comunicherà i risultati? E perché gli altri dovrebbero fidarsi di ciò che dirà? Forse possiamo prima votare per un leader di cui ci fidiamo per dirigere il voto — ma chi guiderà questo primo voto? E se non riuscissimo a metterci d'accordo su un leader? O se ci accordassimo, e questo leader rimanesse bloccato a una riunione o andasse in malattia?
Problemi simili si incontrano nelle reti informatiche distribuite. Tutti i partecipanti o nodi devono concordare una soluzione, ad esempio chi è responsabile per aggiornare un file condiviso o per prelevare 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 a volte sono in conflitto. Questo consenso di rete garantisce al destinatario che la moneta è (a) valida (non contraffatta) e (b) non è stata spesa altrove. Garantisce anche che il destinatario possa 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 a prova di guasto: deve fornire risultati coerenti, nonostante errori come linee di comunicazione lente, nodi non responsivi e ordine errato dei messaggi. Bizantino il sistema degli accordi è ulteriormente resistente agli errori "bizantini": a nodi che forniscono informazioni false, sia per errore che per tentativi deliberati di compromettere il sistema o ottenere un vantaggio. La resilienza "bizantina" è la capacità di fidarsi della decisione collettiva, anche quando alcuni membri del gruppo possono mentire o in altro modo non seguire le regole di decisione, prende il nome da , che cercavano di coordinare un attacco. di Anthony Stevens.
Consideriamo Alice, una proprietaria di criptovalute, che deve scegliere tra acquistare un delizioso gelato da Bob e pagare un debito a Carol. Potrebbe essere che Alice voglia pagare entrambi contemporaneamente, spendendo fraudolentemente la stessa moneta. 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 accordi bizantini rende praticamente impossibile questo, utilizzando una forma di regola della maggioranza chiamata quorum. Un nodo in una rete di questo tipo rifiuta di passare a una determinata versione della storia finché non vede che un numero sufficiente di nodi peer-to-peer — un quorum — è d'accordo su tale transizione. Non appena ciò avviene, formeranno un blocco elettorale sufficientemente grande per costringere gli altri nodi della rete ad accettare la loro decisione. Alice può costringere alcuni nodi a mentire a suo nome, ma se la rete è sufficientemente grande, il suo tentativo sarà soppressato dai voti dei nodi onesti.
Quanti nodi servono per formare un quorum? Almeno la maggioranza, e più precisamente, una maggioranza qualificata per combattere gli errori e le frodi. Ma per contare la maggioranza, è necessario conoscere il numero totale di partecipanti. Negli uffici di Interstellar o nelle elezioni distrettuali, questi numeri sono facilmente accessibili. Ma se il vostro gruppo è una rete poco definita, in cui i nodi possono entrare e uscire a piacimento senza coordinarsi con un centro, allora è necessario federativa sistema di consenso bizantino in grado di definire i quorum non da una lista predefinita di nodi, ma dinamicamente, da un'istantanea in costante cambiamento e inevitabilmente incompleta dei nodi in un determinato momento.
Può sembrare impossibile creare un quorum dal punto di vista di un singolo nodo in una rete estesa, ma è possibile. Un tale quorum può persino garantire risultati di votazioni decentralizzate. Il documento tecnico SCP mostra come farlo tramite una procedura chiamata votazione federativa.
Per i più impazienti
Il resto dell'articolo descrive in modo più dettagliato la votazione federativa e il protocollo di consenso Stellar. Se non sei interessato ai dettagli, ecco una panoramica generale del processo.
- I nodi conducono round di voto federativo sui 'nominati'. Un round di voto federativo implica:
- Il nodo vota per una qualsiasi affermazione, ad esempio, 'Propongo il valore V';
- Il nodo ascolta le voci dei peer finché non trova quella che può 'accettare';
- Il nodo cerca un 'quorum' per questa affermazione. Il quorum 'conferma' il nominato.
- Non appena il nodo può confermare uno o più candidati, cerca di "preparare" il "ballottaggio" attraverso diversi turni di voto federativo.
- Quando il nodo è in grado di verificare la prontezza del ballottaggio, cerca di commetterlo con l'ausilio di un numero maggiore di turni di voto federativo.
- Una volta che il nodo può confermare il commit del ballottaggio, può "esternalizzare" il valore di questo ballottaggio, utilizzandolo come risultato del consenso.
Questi passaggi includono diversi turni di voto federativo, che insieme formano un turno SCP. Vediamo più nel dettaglio cosa accade a ogni passo.
Voto federativo
Il voto federativo è la procedura per decidere se la rete può accordarsi su una proposta. Nel turno di voto, ogni nodo deve scegliere uno dei potenziali molteplici valori. Non può farlo finché non è certo che gli altri nodi della rete non sceglieranno un altro risultato. Per esserne certi, i nodi scambiano una raffica di messaggi avanti e indietro affinché ognuno. ha confermato, che quorum nodi accetta lo stesso soluzione. Il resto di questa sezione spiega i termini in questa frase e come avviene l'intera procedura.
Quorum e slice di quorum
Iniziamo con la definizione di quorum. Come discusso in precedenza, in una rete decentralizzata con adesioni dinamiche, non è possibile conoscere in anticipo il numero di nodi e, di conseguenza, quanti sono necessari per la maggioranza. Il voto federato risolve questo problema introducendo una nuova idea slice di quorum (quorum slice): un piccolo insieme di nodi peer che un nodo considera affidabili per la trasmissione delle informazioni sullo stato del voto al resto della rete. Ogni nodo definisce il proprio slice di quorum (di cui diventa membro di fatto).
La formazione del quorum inizia dallo slice di quorum. Per ciascun nodo, vengono aggiunti i nodi del suo slice. Successivamente, vengono aggiunti i membri degli slice di questi nodi e così via. Man mano che si procede, si incontrano sempre più nodi che non si possono aggiungere perché sono già inclusi nello slice. Quando non ci sono più nuovi nodi da aggiungere, il processo si interrompe: abbiamo formato il quorum attraverso la «chiusura transitiva» (transitive closure) dello slice di quorum del nodo iniziale.
Per trovare il quorum da un certo nodo...
... aggiungiamo i membri della sua fetta...
... poi aggiungiamo i membri delle fette di questi nodi.
Continuiamo finché non ci sono più nodi da aggiungere.
Non ci sono più nodi da aggiungere. Questo è il quorum.
In realtà, ogni nodo può far parte di più di una fetta. Per formare un quorum, seleziona solo una delle fette e aggiungi membri; poi scegli qualsiasi fetta per ciascuno dei membri e aggiungi membri questo della fetta e così via. Questo significa che ogni nodo è membro di molti possibili quorums.
Seleziona solo una fetta di quorum a ogni passaggio.
Un possibile quorum. Oppure un’alternativa…
... scegliamo altre fette...
... (quando possibile)...
... crea un altro quorum.
Come fa un nodo a sapere in quali fette si trovano gli altri nodi? Proprio come con altre informazioni sugli altri nodi: dalle trasmissioni che ogni nodo invia in rete quando cambia il suo stato di voto. Ogni trasmissione include informazioni sulle fette del nodo mittente. Nel documento tecnico SCP non è specificato il meccanismo di comunicazione. Le implementazioni di solito utilizzano per garantire la trasmissione dei messaggi in tutta la rete.
Ricordiamo che nel sistema di accordo bizantino non federativo, il quorum è definito come la maggioranza di tutti i nodi. Il sistema di accordo bizantino è progettato in relazione alla domanda: quanti nodi disonesti può tollerare il sistema? In un sistema con N nodi, progettato per sopravvivere a f guasti (impostori), 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 f peer (da cui il nodo non ha ricevuto risposta) siano in realtà onesti. Pertanto, i malintenzionati sono f tra i N−f peer (da cui è stata ricevuta la risposta). Affinché i nodi raggiungano un consenso, la maggioranza degli altri nodi deve essere onesta; quindi, abbiamo bisogno che N−f sia maggiore di 2f, ovvero N > 3f. Quindi, in genere, un sistema progettato per sopravvivere a f guasti avrà un totale di N=3f+1 nodi e una dimensione del quorum di 2f+1. Una volta che la proposta supera la soglia del quorum, gli altri membri della rete sono convinti che qualsiasi proposta concorrente fallirà. Così, la rete converge verso il risultato.
Nella federativa sistema bizantino di accordi, non solo non può esserci una maggioranza (perché nessuno conosce la grandezza complessiva della rete), ma il concetto stesso di maggioranza è completamente inutile! Se l'appartenenza al sistema è aperta, qualcuno può ottenere la maggioranza semplicemente lanciando un attacco Sybil: connettersi ripetutamente alla rete attraverso diversi nodi. Allora, perché il chiusura transitiva del taglio può essere chiamato quorum, e come riesce a sopprimere le proposte concorrenti?
Tecnicamente, non c'è modo! Immagina una rete di sei nodi, dove due terne sono isolate nei loro propri tagli di quorum. Il primo sottoinsieme può prendere una decisione di cui il secondo non sentirà mai parlare, e viceversa. In questa rete non c'è modo di raggiungere il consenso (se non per caso).
Pertanto, lo SCP richiede che per il voto federativo (e per l'applicazione delle importanti teoremi dell'articolo) la rete debba possedere una proprietà chiamata intersezione dei quorumi. Nella rete con questa proprietà, qualsiasi due quorum che possono essere costruiti si sovrappongono sempre in almeno un nodo. Per determinare le tendenze predominanti della rete, questo è altrettanto efficace che avere una maggioranza. Intuitivamente, significa che se un qualsiasi quorum concorda con l'affermazione X, nessun altro quorum potrà mai concordare su qualcos'altro, poiché includerà necessariamente un nodo del primo quorum che ha già votato per X.
Se nella rete ci sono sovrapposizioni di quorum…
… allora qualsiasi due quorum che puoi costruire…
… si sovrapporranno sempre.
(Naturalmente, i nodi sovrapposti potrebbero risultare bizantini-bugiosi o scadenti in altri aspetti. In questo caso, l'intersezione dei quorum non aiuta affatto la rete a raggiungere un consenso. Per questo motivo, molti risultati nel documento tecnico SCP si basano su assunzioni esplicite, come che nella rete rimanga un'intersezione di quorum anche dopo la rimozione dei nodi cattivi. Per semplicità, lasciamo queste assunzioni implicite nel resto dell'articolo).
Potrebbe sembrare irragionevole aspettarsi che una rete di nodi indipendenti possa ottenere un affidabile incrocio di quorum. Ma ci sono due motivi per cui è così.
Il primo motivo è l'esistenza stessa di Internet. Internet è un esempio ideale di rete di nodi indipendenti con incroci di quorum. La maggior parte dei nodi in Internet si connette solo con alcuni altri nodi locali, ma questi piccoli gruppi si sovrappongono abbastanza da garantire che ogni nodo sia accessibile da ogni altro nodo tramite uno qualsiasi dei percorsi disponibili.
La seconda ragione è specifica per la rete di pagamento Stellar (il suo uso più comune è SCP). Ogni attivo nella rete Stellar ha un emittente, e le raccomandazioni di Stellar richiedono che ogni emittente nomini uno o più nodi in rete per gestire le richieste di rimborso. È nel tuo interesse includere direttamente o indirettamente questi nodi nei quorum per ogni attivo che ti interessa. In tal modo, i quorum per tutti i nodi interessati a un determinato attivo si sovrapporranno almeno in questi nodi di rimborso. I nodi interessati a più attivi includeranno nei loro quorum tutti i nodi di rimborso degli emittenti corrispondenti e cercheranno di unire insieme tutti gli attivi. Inoltre, qualsiasi attivo che non sia collegato in questo modo ad altri nella rete, e non deve essere collegato — è progettato in modo tale che non ci siano sovrapposizioni di quorum in questa rete (per esempio, le banche nella zona del dollaro a volte vogliono commerciare con le banche nella zona euro e con le banche nella zona del peso, quindi si trovano nella stessa rete, ma a nessuno di loro interessa una rete distinta di bambini che commerciano carte da baseball).
Certo, l'attesa l'intersezione dei quorum non è una garanzia. Altre complesse sistemi di accordo bizantino devono la loro complessità in larga parte alla garanzia dei quorum. Un'importante novità dello SCP è che si libera della responsabilità di creare i quorum dal proprio algoritmo di consenso e lo porta a livello applicativo. Pertanto, anche se il voto federato è piuttosto comune per votare su qualsiasi questione, la sua affidabilità dipende in modo critico da un significato più ampio di questi valori. Alcuni ipotetici tipi di utilizzo possono rivelarsi meno adatti a creare reti ben collegate rispetto ad altri.
Votazione, adozione e conferma
Nel turno di voto federato, un nodo inizia opzionalmente a votare per un certo valore V. Questo significa trasmettere in rete il messaggio: «Io sono il nodo N, i miei tagli di quorum Q, e voto per V». Quando un nodo vota in questo modo, promette di non aver mai votato contro V e di non farlo mai.
Nei trasferimenti da nodi peer-to-peer ogni nodo vede come votano gli altri. Una volta che un nodo raccoglie un numero sufficiente di tali messaggi, può tracciare le sezioni di quorum e cercare di trovare i quorum. Se vede un quorum di pari che votano anche per V, può passare a accettare V e trasmettere questo nuovo messaggio nella rete: «Io sono il nodo N, le mie sezioni di quorum sono Q, e accetto V». L'accettazione fornisce una garanzia più forte rispetto a un 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).
Naturalmente, è probabile che non si trovi immediatamente un quorum di nodi che siano d'accordo su V. Altri nodi possono votare per altri valori. Ma per un nodo c'è un altro modo per passare da un 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 farlo basta vedere un insieme bloccante nodi che accettano W. Un insieme bloccante è costituito da un nodo di ciascuno dei tagli di quorumi N. Come suggerisce il nome, può bloccare qualsiasi altro valore. Se tutti i nodi in tale insieme accettano W, allora (secondo il teorema 8) non sarà mai possibile formare un quorum che accetti un valore diverso, e quindi è sicuro accettare W anche per N.
Nodo N con tre tagli di quorumi.
B-D-F è un insieme bloccante per N: include un nodo di ciascuno dei tagli N.
B-E è anch'esso un insieme bloccante per N, perché E appare in due tagli di N.
Ma un insieme bloccante non è un quorum. Sarebbe troppo facile ingannare il nodo N affinché accetti un valore desiderato, se bastasse compromettere solo un nodo in ciascuno dei sottogruppi N. Pertanto, accettare un valore non significa ancora che il voto sia terminato. Invece, N deve confermare il valore, cioè vedere un quorum di nodi che lo accettano. Se arriva a questo punto, come dimostra il documento tecnico SCP (nella Teorema 11), l'intero resto della rete alla fine confermerà lo stesso valore, quindi N concluderà il voto federativo con un valore specifico come risultato.
Voto federativo.
Il processo di voto, accettazione e conferma costituisce un intero ciclo di voto federativo. Il protocollo di consenso Stellar unisce molti di questi cicli per creare un sistema di consenso completo.
Protocollo di consenso Stellar
Le due proprietà più importanti di un sistema di consenso sono sicurezza e resilienzaUn algoritmo di consenso è «sicuro» se non può mai restituire risultati diversi a partecipanti diversi (una copia della storia di Bob non contraddirà mai quella di Carol). La «vitalità» significa che l'algoritmo fornirà sempre un risultato, ovvero non si bloccherà.
La procedura di voto federato descritta è sicura nel senso che se un nodo conferma il valore V, nessun altro nodo confermerà un altro valore. Tuttavia, «non confermare un altro valore» non significa che debba necessariamente confermare qualcosa. I partecipanti possono votare per un numero così elevato di valori diversi che nessuno raggiunga la soglia di accettazione. Questo significa che nel voto federato manca resilienza.
Il protocollo di consenso Stellar utilizza il voto federato in modo da garantire sia la sicurezza che la resilienza. (Le garanzie di sicurezza e resilienza del SCP hanno un limite teorico. La costruzione sceglie un'ottima garanzia di sicurezza, sacrificando una leggera riduzione della resilienza, ma tenendo conto di un tempo sufficiente, il consenso sarà raggiunto con alta probabilità). In breve, l'idea è quella di svolgere più votazioni federate su diversi valori finché uno di essi non attraversi completamente tutte le fasi di votazione SCP, descritte di seguito.
I valori di cui il SCP cerca il consenso possono essere una cronologia di transazioni o un ordine per il pranzo, o qualcos'altro, ma è importante notare che questi non sono i valori che vengono accettati o confermati. Invece, il voto federato avviene su affermazioni su questi valori.
I primi turni di voto federato si svolgono nella fase di proposizione (fase di nominazione), in cui si raccolgono proposte del tipo 'Io nomino V', potenzialmente per molti significati diversi di V. L'obiettivo della nomination è quello di trovare una o più proposte che possano passare all'approvazione e conferma.
Dopo aver trovato candidati verificabili, SCP passa alla fase di voto, dove l'obiettivo è trovare un ballottaggio (cioè un contenitore per il valore proposto) e un quorum che possa 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—annullare i ballottaggi per trovare quello per cui si può confermare il commit—comprendono diversi round di voto federativo su più proposte di ballottaggio.
Nei prossimi capitoli si descrivono più dettagliatamente la nomination e il voto.
Nomination
All'inizio della fase di candidatura, ogni nodo può scegliere spontaneamente un valore V e votare per l'approvazione con "Propongo V". L'obiettivo di questa fase è confermare la candidatura di un certo valore attraverso un voto federativo.
È possibile che un numero sufficiente di nodi voti per affermazioni abbastanza diverse, e quindi nessuna proposta possa raggiungere la soglia di approvazione. Pertanto, oltre a trasmettere i propri voti di nomina, i nodi "riflettono" le nomine dei loro pari. Il riflesso (echo) significa che se un nodo vota per la proposta V, ma vede un messaggio da un vicino che vota per la proposta W, allora voterà ora sia per V che per W. (Non tutti i voti dei pari vengono riflessi durante la nomina, poiché ciò potrebbe portare a un'esplosione di diversi nominati. SCP include un meccanismo per regolare questi voti. In breve, esiste una formula per determinare il "priorità" di un pari dal punto di vista di un nodo, e vengono riflessi solo i voti dei nodi di alta priorità. Quanto più a lungo dura la nomina, tanto più bassa è la soglia, quindi il nodo espande l'insieme di pari i cui voti rifletterà. La formula di priorità include il numero di slot come uno degli input, quindi un nodo peer di alta priorità per uno slot può essere di bassa priorità per un altro, e viceversa).
Concettualmente, iliziare parallelamente sia V che W rappresenta voti federativi distinti, ognuno capace di raggiungere l'adozione o la conferma. Nella pratica, i messaggi del protocollo SCP raggruppano questi voti separati.
Sebbene votare per la candidatura di V implichi una promessa di non votare mai contro, a livello applicativo — in questo caso SCP — viene definito cosa significa "contro". SCP non vede un'affermazione che contraddica il voto "Io propongo X", cioè non c'è messaggio "Io sono contro la proposta di X", quindi il nodo può votare per la proposta di qualsiasi valore. Molte di queste nomination non porteranno a nulla, ma alla fine il nodo sarà in grado di adottare o confermare uno o più valori. Una volta che il candidato è confermato, diventa candidato.
Proposta di SCP tramite voto federativo. Possono esserci molti valori “B” proposti da nodi peer e “riflessi” da un nodo.
La nomina dei candidati può portare all'emergere di più candidati confermabili. Pertanto, SCP richiede che il livello applicativo fornisca un metodo per unire i candidati in uno solo. composito (composite). Il metodo di unione può essere qualsiasi. L'importante è che, se questo metodo è deterministico, ogni nodo unisca gli stessi candidati. Nel sistema di votazione per il pranzo, 'unione' può semplicemente significare scartare 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 avviene la votazione sulla cronologia delle transazioni, unire due candidati proposti implica unire le transazioni che contengono e le ultime delle loro due tempistiche.
La descrizione tecnica di SCP dimostra (teorema 12) che alla fine della fase di proposizione la rete converge infine verso un unico composito. Ma c'è un problema: il voto federativo è un protocollo asincrono (come SCP). In altre parole, i nodi non sono sincronizzati temporalmente, ma solo in base ai messaggi che inviano. Dal punto di vista del nodo non è chiaro quando sia terminata la fase di proposizione. E sebbene tutti i nodi alla fine raggiungano lo stesso composito, possono seguire percorsi diversi lungo il cammino, creando lungo il percorso diversi candidati compositi, e non possono mai dire quale di essi sia finale.
Ma va bene così. La proposizione è solo una preparazione. L'importante è limitare il numero di candidati per raggiungere il consenso, che avviene nel processo di votazione (balloting).
Votazione
Un bollettino è una coppia , dove counter è un numero intero che inizia da 1 e value è un candidato dell fase di nomina. Questo può essere un candidato del nodo stesso o un candidato di un nodo vicino accettato da questo nodo. In altre parole, durante le elezioni si compiono tentativi ripetuti per far sì che la rete raggiunga un consenso su un candidato in un determinato bollettino attraverso la realizzazione di potenziali molteplici votazioni federative riguardanti le dichiarazioni sui bollettini. I contatori nei bollettini tengono traccia dei tentativi effettuati e i bollettini con contatori più alti hanno priorità rispetto a quelli con contatori più bassi. Se il bollettino si blocca, si avvia una nuova votazione, ora sul bollettino .
È importante distinguere i valori (per esempio, cosa dovrebbe essere ordinato per il pranzo: pizza o insalate), i bollettini (la coppia counter-value) e le dichiarazioni sui bollettini. Un round SCP comprende diversi round di votazione federativa, in particolare riguardo a queste dichiarazioni:
- "Sono pronto per il commit del bollettino B" e
- "Dichiaro il commit del bollettino B"
Dal punto di vista di questo nodo, il consenso si raggiunge quando trova il bollettino B, per il quale può confermare (cioè trovare un quorum favorevole) l'affermazione "Dichiaro il commit del bollettino B". Da quel momento in poi, è possibile agire in base al valore indicato in B — ad esempio, effettuare questo ordine per il pranzo. Questo processo è chiamato esterna-lizzazione del valore. Una volta confermato l'accettazione del bollettino, il nodo può essere certo che qualsiasi altro nodo ha esternalizzato lo stesso valore o lo farà sicuramente in futuro.
Sebbene concettualmente molte votazioni federative vengano effettuate su dichiarazioni di vari bollettini, non scambiano un numero così elevato di messaggi, poiché ogni messaggio incapsula una serie di bollettini. Un singolo messaggio, quindi, avanza lo stato immediatamente di molte votazioni federative, ad esempio: "Accetto il commit dei bollettini nell'intervallo da a ".
Cosa significano i termini "preparato" (prepared) e "commit" (commit)?
Un nodo vota per il commit della busta quando è convinto che altri nodi non eseguiranno commit di buste con altri valori. Essere convinti di questo è l'obiettivo della preparazione della dichiarazione. Il voto che afferma: "Sono pronto per il commit della busta B" è una promessa di non effettuare mai un commit della busta inferiore a B, cioè con un contatore minore (SCP richiede che i valori nelle buste abbiano un certo ordine. Pertanto, la busta è inferiore a se N1<N2, e anche se N1=N2 e V1<V2). Queste buste minori vengono "annullate" (aborted) durante il voto preparatorio, mentre B è considerata "preparata".
Perché "Sono pronto per il commit della busta B" significa "Prometto di non permettere mai commit di buste inferiori a B"? Perché SCP definisce abort come l'opposto di commit. Il voto per la preparazione della busta implica anche il voto per annullare alcune altre buste, e, come abbiamo discusso in precedenza, votare per una cosa implica promettere di non votare mai contro di essa.
Prima di trasmettere il commit, il nodo deve prima trovare la scheda che può convalidare come preparata. In altre parole, conduce una votazione federativa sulla questione "Sono pronto a fare il commit della scheda B", possibilmente per molte diverse schede, fino a trovare quella che accetta il quorum.
Da dove provengono le schede per la preparazione al voto? Innanzitutto, il nodo trasmette la preparazione al voto per , dove C è un candidato composito prodotto nella fase di nomina. Tuttavia, anche dopo l'inizio della preparazione al voto, la nomina può portare alla comparsa di ulteriori candidati, che diventeranno nuove schede. Nel frattempo, i peer possono avere candidati diversi e possono formare un insieme bloccante che accetta "Sono pronto a fare il commit della scheda B2", convincendo anche il nodo ad accettarlo. Infine, esiste un meccanismo di timeout che genera nuovi turni di votazione federativa su nuove schede con contatori più elevati, se le schede attuali si sono bloccate.
Non appena un nodo trova un bollettino B che può confermare come preparato, trasmette un nuovo messaggio "Commit del bollettino B". Questa votazione comunica ai peer che il nodo non abbandonerà mai B. In effetti, se B rappresenta un bollettino , allora "Commit del bollettino " implica un consenso incondizionato a votare per la prontezza di ogni bollettino da a . Questo valore aggiuntivo aiuta gli altri nodi a raggiungere il peer con il commit, se sono ancora nelle fasi precedenti del protocollo.
In questa fase è opportuno sottolineare ancora una volta che si tratta di protocolli asincroni. Solo perché un nodo invia voti per il commit, non significa che i suoi pari lo facciano altrettanto. Alcuni di essi potrebbero essere ancora impegnati a votare sulle dichiarazioni per la preparazione al voto, altri potrebbero aver già esternalizzato il valore. SCP spiega come un nodo dovrebbe gestire ogni tipo di messaggio peer-to-peer indipendentemente dalla sua fase.
Se il messaggio "Annuncio 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 altri, poiché il nodo ha già promesso di non annullare mai . Al momento in cui il nodo trasmette i voti per il commit, sarà C o nulla, a seconda di quanto lontano si spingerà il consenso. Tuttavia, questo non è ancora sufficiente per il nodo per esternalizzare C. Alcuni festini bizantini (costituenti meno del quorum, basandosi sulle nostre assunzioni di sicurezza) possono mentire al nodo. Accettare, e poi confermare, un bollettino (o un intervallo di bollettini) è ciò che dà al nodo la certezza di esternalizzare infine C.
Votazione SCP tramite voto federato. Non mostrato: in qualsiasi momento potrebbe scattare un timer, aumentando il conteggio nel bollettino (e, possibilmente, generare un nuovo composito da ulteriori candidati proposti).
E questo è tutto! Una volta che la rete raggiunge il consenso, è pronta a farlo di nuovo e di nuovo. Nella rete di pagamenti Stellar, questo avviene circa ogni 5 secondi: un risultato che richiede sia sicurezza che resilienza, garantite dallo SCP.
Lo SCP riesce a raggiungere questo obiettivo basandosi su più turni di voto federato. Il voto federato è reso possibile grazie al concetto di tagli di quorum: set di nodi peer-to-peer a cui ogni nodo ha deciso di affidarsi come parte del proprio quorum (soggettivo). Questa configurazione significa che si può raggiungere il consenso anche in una rete con adesione aperta e inganni bizantini.
Ulteriore lettura
- Il documento tecnico originale dello SCP può essere trovato , e progetto di specifiche per la sua implementazione.
- L’autore originale del protocollo SCP, David Mazieres, spiega in modo semplificato (ma comunque tecnico) .
- Potresti essere sorpreso di non trovare in questo articolo i termini "mining" o "proof of work". Lo SCP non utilizza questi metodi, ma alcuni altri algoritmi di consenso lo fanno. Zain Waiserspoon ha scritto una accessibile .
- una rete semplice che raggiunge il consenso in un unico round completo di SCP.
- Per i lettori interessati alle implementazioni di SCP: vedi. , utilizzato dalla rete di pagamento Stellar, oppure , che ho scritto per una migliore comprensione di SCP.
Fonte: habr.com
