Il protocollo di consenso Stellar è stato descritto per la prima volta in David Mazier nel 2015. Si tratta di un “sistema di accordi federali bizantini” che consente a reti informatiche decentralizzate e senza leader di raggiungere in modo efficiente il consenso su una decisione. La rete di pagamento Stellar utilizza lo Stellar Consensus Protocol (SCP) per mantenere una cronologia coerente delle transazioni visibile a tutti i partecipanti.
I protocolli di consenso sono considerati difficili da comprendere. L'SCP è più semplice della maggior parte di essi, ma condivide comunque questa reputazione, in parte a causa dell'idea sbagliata che il "voto federato", oggetto della prima metà dell'articolo scientifico, sia SCP. Ma non è vero! Questo è solo un elemento importante che viene utilizzato per creare la seconda metà dell'articolo attuale Protocollo di consenso stellare.
In questo articolo spiegheremo brevemente cos’è un “sistema di accordi”, cosa può renderlo “bizantino” e perché rendere “federale” il sistema bizantino. Spiegheremo quindi la procedura di voto federato descritta nell'articolo SCP e infine spiegheremo il protocollo SCP stesso.
Sistemi contrattuali
Un sistema di accordi consente a un gruppo di partecipanti di raggiungere un consenso su un argomento, ad esempio cosa ordinare per pranzo.
In Interstellar abbiamo implementato il nostro sistema di convenzione ristorazione: ordiniamo ciò che dice il nostro responsabile delle operazioni, John. Si tratta di un sistema contrattuale semplice ed efficace. Abbiamo tutti fiducia in John e crediamo che ogni giorno troverà qualcosa di interessante e nutriente.
Ma cosa succederebbe se John abusasse della nostra fiducia? Può decidere da solo che dovremmo diventare tutti vegani. Tra una settimana o due probabilmente lo rovesceremo e consegneremo il potere a Elizabeth. Ma all'improvviso adora gli avocado con le acciughe e pensa che tutti dovrebbero essere così. Il potere corrompe. Allora è meglio trovare un metodo più democratico: un modo per assicurarsi che le diverse preferenze siano prese in considerazione, garantendo al tempo stesso un risultato tempestivo e inequivocabile, in modo che nessuno finisca per ordinare il pranzo, o cinque persone facciano ordini diversi, o la discussione si trascina fino a sera.
Sembrerebbe che la soluzione sia semplice: votare! Ma questa è un’impressione fuorviante. Chi raccoglierà le schede e comunicherà i risultati? E perché gli altri dovrebbero credere a ciò che dice? Forse possiamo all'inizio votare per un leader di cui confidiamo per guidare il voto, ma che lo guiderà prima votando? E se non riuscissimo a metterci d'accordo su un leader? Oppure cosa succede se raggiungiamo un accordo, ma questo leader rimane bloccato in una riunione o va in congedo per malattia?
Problemi simili si verificano nelle reti di computer distribuite. Tutti i partecipanti o i nodi devono concordare su alcune decisioni, ad esempio a chi tocca aggiornare un file condiviso o rimuovere un'attività dalla coda di elaborazione. In una rete di criptovaluta, i nodi devono ripetutamente scegliere come apparire la storia completa tra diverse versioni possibili, che a volte sono in conflitto. Questo accordo di rete garantisce al destinatario che la moneta è (a) valida (non contraffatta) e (b) non ancora spesa altrove. Questo garantisce anche che potrà spendere le monete in futuro perché il nuovo destinatario avrà le stesse garanzie per gli stessi motivi.
Qualsiasi sistema di consenso in una rete informatica distribuita deve essere tollerante ai guasti: deve produrre risultati coerenti nonostante errori come collegamenti lenti, nodi che non rispondono e ordinamento errato dei messaggi. bizantino Il sistema degli accordi è inoltre resistente agli errori "bizantini": nodi che forniscono informazioni false, sia a causa di un errore che nel tentativo deliberato di indebolire il sistema o ottenere qualche vantaggio. La tolleranza agli errori "bizantina" - la capacità di fidarsi di una decisione del gruppo anche quando alcuni membri del gruppo possono mentire o altrimenti non seguire le regole del processo decisionale - viene chiamata che ha cercato di coordinare l'attacco. presso Anthony Stevens.
Consideriamo la proprietaria di criptovalute Alice, che deve scegliere tra acquistare un delizioso gelato da Bob e saldare il debito di Carol. Forse Alice vuole pagarli entrambi contemporaneamente spendendo fraudolentemente la stessa moneta. Per fare ciò, 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. Il sistema di accordi bizantino lo rende praticamente impossibile, utilizzando una forma di regola della maggioranza chiamata quorum. Un nodo di una rete di questo tipo si rifiuta di passare a una particolare versione della storia finché non vede che un numero sufficiente di pari - un quorum - accetta tale transizione. Una volta che ciò accadrà, formeranno un blocco elettorale abbastanza grande da costringere i restanti nodi della rete ad essere d’accordo con la loro decisione. Alice può forzare alcuni nodi a mentire per suo conto, ma se la rete è abbastanza grande, il suo tentativo sarà vanificato dai voti dei nodi onesti.
Quanti nodi sono necessari per il quorum? Come minimo, una maggioranza, o meglio, una maggioranza qualificata per combattere gli errori e le frodi. Ma per contare la maggioranza è necessario conoscere il numero totale dei partecipanti. All'ufficio Interstellar o alle elezioni distrettuali, questi numeri sono facili da scoprire. Ma se il vostro gruppo è una rete vagamente definita in cui i nodi possono entrare e uscire a piacimento senza l’approvazione del centro, allora avete bisogno federale un sistema di accordi bizantini in grado di determinare i quorum non da un elenco predeterminato di nodi, ma dinamicamente, da un’istantanea di nodi in continua evoluzione e inevitabilmente incompleta in un dato momento.
Può sembrare impossibile creare un quorum dal punto di vista di un singolo nodo in una vasta rete, ma è possibile. Un tale quorum può anche garantire i risultati del voto decentralizzato. Il white paper SCP mostra come eseguire questa operazione utilizzando una procedura chiamata con voto federale.
Per gli impazienti
Il resto dell'articolo descrive in modo più dettagliato il voto federato e il protocollo di consenso Stellar. Se non sei interessato ai dettagli, ecco una panoramica generale del processo.
- I nodi conducono turni di votazione federale sui “candidati”. Una votazione federale significa:
- Il nodo vota per qualche affermazione, ad esempio “Propongo il valore di V”;
- Il nodo ascolta le voci dei peer finché non ne trova uno in grado di "ricevere";
- Il nodo cerca un "quorum" per questa affermazione. Il quorum “conferma” il candidato.
- Una volta che un nodo può confermare uno o più candidati, tenta di "preparare" la "scheda elettorale" attraverso diversi turni di votazione federata.
- Una volta che un nodo è in grado di verificare che la scheda elettorale sia pronta, tenta di impegnarla attraverso ancora più turni di votazione federata.
- Una volta che un nodo può confermare il commit di una votazione, può "esternalizzare" il valore di quella votazione utilizzandolo come risultato di consenso.
Questi passaggi comportano più round di votazione federata, che collettivamente formano un round SCP. Diamo uno sguardo più da vicino a cosa succede in ogni passaggio.
Voto federato
Il voto federato è una procedura per determinare se la rete può concordare una proposta. Nella tornata di votazione, ciascun nodo deve scegliere uno tra potenzialmente molti valori possibili. Non può farlo a meno che non sia sicuro che altri nodi della rete non sceglieranno un risultato diverso. Per garantire ciò, i nodi si scambiano una raffica di messaggi avanti e indietro in modo che tutti confermatoChe quorum nodi prende Uno e lo stesso decisione. Il resto di questa sezione spiega i termini di questa frase e come avviene l'intera procedura.
Quorum e sezioni di quorum
Cominciamo definendo un quorum. Come abbiamo discusso in precedenza, in una rete decentralizzata con appartenenza dinamica, è impossibile conoscere in anticipo il numero di nodi e quindi quanti sono necessari per la maggioranza. Il voto federato risolve questo problema introducendo una nuova idea taglio del quorum (quorum slice): un piccolo insieme di peer di cui un nodo si fida per comunicare le informazioni sullo stato del voto al resto della rete. Ogni nodo definisce la propria porzione di quorum (di cui diventa membro di fatto).
La formazione del quorum inizia con una riduzione del quorum. Per ogni nodo vengono aggiunti i nodi tagliati. Quindi vengono aggiunti i termini della sezione questi nodi e così via. Man mano che prosegui, ci sono sempre più nodi che non puoi aggiungere perché sono già inclusi nella sezione. Quando non ci sono più nuovi nodi da aggiungere, il processo si ferma: abbiamo formato un quorum per “chiusura transitiva” della fetta di quorum del nodo iniziale.
Per trovare il quorum da un determinato nodo...
... aggiungi membri della sua porzione...
...quindi aggiungiamo i membri della sezione 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ò apparire in più di una sezione. Per formare un quorum, seleziona solo una delle sezioni e aggiungi membri; quindi seleziona qualsiasi sezione per ciascuno dei membri e aggiungi membri esso tagliare e così via. Ciò significa che ogni nodo è membro di molti quorum possibili.
Selezionare solo una sezione del quorum per ogni passaggio.
Un quorum possibile. Oppure un'alternativa...
...seleziona altre fette...
…(quando è possibile)…
... crea un altro quorum.
Come fa un nodo a sapere in quali slice si trovano gli altri nodi? Allo stesso modo delle altre informazioni sugli altri nodi: dalle trasmissioni che ogni nodo trasmette alla rete quando cambia il suo stato di voto. Ogni trasmissione include informazioni sulle sezioni del nodo mittente. Il white paper SCP non specifica un meccanismo di comunicazione. Le implementazioni in genere utilizzano per la diffusione garantita dei messaggi su tutta la rete.
Ricordiamo che nel sistema di accordi bizantino non federale, un quorum è definito come la maggioranza di tutti i nodi. Il sistema di accordi bizantini è concepito dal punto di vista della domanda: quanti nodi disonesti può tollerare il sistema? In un sistema di N nodi progettato per sopravvivere a f fallimenti, un nodo dovrebbe essere in grado di fare progressi ricevendo feedback da N−f peer poiché f di essi potrebbero essere inattivi. Ma avendo ricevuto una risposta da N−f peer, possiamo supporre che tutti i peer f (dai quali il nodo non ha ricevuto risposta) siano effettivamente onesti. Pertanto, f su N−f peer (dai quali è stata ricevuta la risposta) sono dannosi. Affinché i nodi raggiungano lo stesso consenso, la maggioranza dei nodi rimanenti deve essere onesta, cioè è necessario che N−f sia maggiore di 2f o N > 3f. Quindi tipicamente un sistema progettato per sopravvivere a f fallimenti avrà un totale di N=3f+1 nodi e una dimensione del quorum di 2f+1. Una volta che una proposta supera la soglia del quorum, il resto della rete è convinto che qualsiasi proposta concorrente fallirà. È così che la rete converge al risultato.
Ma in un sistema di accordi federali bizantini, non solo non può esserci una maggioranza (perché nessuno conosce la dimensione totale della rete), ma il concetto di maggioranza è completamente inutile! Se l’appartenenza al sistema è aperta, allora qualcuno può ottenere la maggioranza semplicemente eseguendo un cosiddetto attacco Sybil: unendosi ripetutamente alla rete su più nodi. Allora perché si può chiamare chiusura transitiva della fetta quorum, e come riesce a sopprimere le proposte concorrenti?
Tecnicamente, assolutamente no! Immagina una rete di sei nodi, in cui due triplette sono isolate l'una nelle rispettive sezioni di quorum. Il primo sottogruppo può prendere una decisione di cui il secondo non verrà mai a conoscenza, e viceversa. Non c’è modo per questa rete di raggiungere il consenso (se non per caso).
Pertanto, SCP richiede che per il voto federato (e affinché gli importanti teoremi del documento possano essere applicati), la rete deve avere una proprietà chiamata incrocio dei quorum. In una rete con questa proprietà, due quorum qualsiasi che possono essere costruiti si sovrappongono sempre in almeno un nodo. Per determinare il sentimento prevalente della rete, questo equivale ad avere la maggioranza. Intuitivamente, ciò significa che se qualsiasi quorum concorda con l’affermazione X, nessun altro quorum potrà mai accettare qualcos’altro, perché includerà necessariamente qualche nodo del primo quorum che ha già votato per X.
Se c'è un'intersezione di quorum nella rete...
...poi due quorum qualsiasi che puoi costruire...
...si intersecherà sempre.
(Naturalmente, la sovrapposizione dei nodi può rivelarsi bizantina o comunque negativa. In questo caso, l'intersezione del quorum non aiuta affatto la rete ad essere d'accordo. Per questo motivo, molti dei risultati nel white paper SCP sono basati su presupposti espliciti, come ciò che rimane nell'attraversamento del quorum della rete anche dopo aver rimosso i nodi danneggiati. Per semplicità lasciamo da parte queste ipotesi implicito nel resto dell'articolo).
Può sembrare irragionevole aspettarsi che sia possibile un affidabile superamento del quorum in una rete di nodi indipendenti. Ma ci sono due ragioni per cui è così.
Il primo motivo è l’esistenza stessa di Internet. Internet è un perfetto esempio di rete di nodi indipendenti con quorum che si intersecano. La maggior parte dei nodi su Internet si connettono solo a pochi altri nodi locali, ma questi piccoli insiemi si sovrappongono abbastanza da consentire a ogni nodo di essere raggiunto da ogni altro nodo lungo un percorso.
Il secondo motivo è specifico della rete di pagamento Stellar (l’uso più comune di SCP). Ogni risorsa sulla rete Stellar ha un emittente e le linee guida di Stellar richiedono che ciascun emittente designi uno o più nodi sulla rete per elaborare le richieste di riscatto. È nel tuo interesse includere direttamente o indirettamente questi nodi nelle sezioni del quorum per ogni risorsa a cui sei interessato. I quorum per tutti i nodi interessati a un dato asset si sovrapporranno quindi almeno in quei nodi di riscatto. I nodi interessati a più asset includeranno tutti i nodi di riscatto dei rispettivi emittenti nelle loro porzioni di quorum e cercheranno di mettere insieme tutti gli asset. Inoltre, tutte le risorse che non sono collegate in questo modo ad altre sulla rete e non dovrebbe essere collegato - questo è progettato in modo tale che non vi sia alcuna sovrapposizione di quorum per questa rete (ad esempio, le banche della zona del dollaro a volte vogliono commerciare con le banche della zona euro e con le banche della zona del peso, quindi sono sulla stessa rete, ma nessuna di loro si preoccupano della rete separata di bambini che vendono figurine di baseball).
Ovviamente, ожидание il superamento del quorum non lo è garanzia. Altri sistemi di accordi bizantini devono gran parte della loro complessità alla garanzia dei quorum. Un’importante innovazione di SCP è che rimuove la responsabilità della creazione dei quorum dall’algoritmo di consenso stesso e lo porta a livello applicativo. Pertanto, sebbene il voto federato sia sufficientemente generale per votare su qualsiasi questione, la sua affidabilità in realtà dipende in modo critico dal significato più ampio di questi significati. Alcuni usi ipotetici potrebbero non essere altrettanto favorevoli alla creazione di reti ben connesse come altri.
Votazione, accettazione e conferma
In una sessione di votazione federata, un nodo inizia facoltativamente a votare per un valore V. Ciò significa trasmettere un messaggio alla rete: “Sono il nodo N, le mie sezioni di quorum sono Q e sto votando per V”. Quando un nodo vota in questo modo, promette che non ha mai votato contro V e mai lo farà.
Nelle trasmissioni peer-to-peer, ogni nodo vede come votano gli altri. Una volta che un nodo ha raccolto un numero sufficiente di questi messaggi, può tenere traccia delle sezioni di quorum e provare a trovare i quorum. Se vede un quorum di pari che votano anche per V, può procedere adozione V e trasmetto questo nuovo messaggio alla rete: "Sono il nodo N, le mie sezioni di quorum sono Q e accetto V." L’accettazione fornisce una garanzia più forte del semplice voto. Quando un nodo vota per V, non può mai votare per altre opzioni. Ma se un nodo accetta V, nessun nodo sulla rete accetterà mai l’altra opzione (il Teorema 8 nel white paper SCP lo dimostra).
Naturalmente, c'è un'alta probabilità che non si raggiunga immediatamente un quorum di nodi che concordano con V. Altri nodi potrebbero votare per altri valori. Ma esiste un altro modo in cui un nodo può passare dal semplice voto all’accettazione. N può accettare un valore diverso per W, anche se non ha votato a favore, e anche se non vede un quorum per esso. Per decidere di cambiare il tuo voto, basta vedere insieme di blocco nodi che hanno accettato W. Un set di blocco è un nodo da ciascuna delle sezioni del quorum N. Come suggerisce il nome, può per bloccare qualsiasi altro significato. Se tutti i nodi di un tale insieme accettano W, allora (per il Teorema 8) non sarà mai possibile formare un quorum che assuma un valore diverso, e quindi è sicuro anche per N accettare W.
Nodo N con tre sezioni di quorum.
BDF è un insieme di blocco per N: include un nodo da ciascuna delle fette di N.
BE è anche un insieme bloccante per N perché E appare in due fette di N.
Ma il set di blocco non è un quorum. Sarebbe troppo facile ingannare il nodo N facendogli accettare il valore desiderato se fosse sufficiente hackerare un solo nodo in ciascuna delle fette di N. Pertanto, accettare il valore non è la fine della votazione. Invece, N deve confermare il valore, cioè vedere un quorum di nodi che lo accettano. Se si arriva a quel punto, allora, come dimostra il whitepaper SCP (nel Teorema 11), anche il resto della rete alla fine confermerà lo stesso valore, quindi N terminerà il voto federato con un certo valore come risultato.
Voto federato.
Il processo di votazione, accettazione e conferma costituisce un ciclo completo di votazione federata. Il protocollo di consenso Stellar combina molti di questi cicli per creare un sistema di consenso completo.
Protocollo di consenso stellare
Le due proprietà più importanti di un sistema di consenso sono − sicurezza и sopravvivenza. Un algoritmo di consenso è "sicuro" se non può mai fornire risultati diversi a partecipanti diversi (la copia della storia di Bob non contraddirà mai Carol). “Vivibilità” significa che l’algoritmo produrrà sempre un risultato, cioè non si bloccherà.
Procedura di voto federale descritta sicuro nel senso che se un nodo conferma il valore di V, nessun altro nodo confermerà l'altro valore. Ma “non confermerà un altro significato” non significa che confermerà necessariamente qualcosa. I partecipanti possono votare su così tanti valori diversi che nulla raggiungerà la soglia di accettazione. Ciò significa che nel voto federale non c'è sopravvivenza.
Il protocollo di consenso Stellar utilizza il voto federato in modo da garantire sia sicurezza che sopravvivenza. (Le garanzie di sicurezza e sopravvivenza di SCP hanno un limite teorico. Il progetto sceglie una garanzia di sicurezza molto forte, sacrificando una piccola mitigazione della sopravvivenza, ma dato un tempo sufficiente, è molto probabile che il consenso venga raggiunto.) In poche parole, l’idea è di avere più voti federati su più valori finché uno di essi non supera tutte le fasi di voto SCP descritte di seguito.
I valori su cui SCP cerca consenso potrebbero essere la cronologia delle 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 federale avviene secondo dichiarazioni su questi valori.
Si svolgono le prime votazioni federali fase di nomina (fase di nomina), su un insieme di affermazioni come “Nomino V”, magari per molti valori diversi di V. Lo scopo della nomina è trovare una o più affermazioni che passino attraverso l’accettazione e la conferma.
Dopo aver trovato i candidati verificabili, SCP passa alla fase di votazione, dove l'obiettivo è trovarne uno certo бюллетень (ovvero un contenitore per il valore proposto) e un quorum che può dichiarare commettere per questo (impegnarsi). Se un quorum impegna una votazione, il suo valore è accettato come consenso. Ma prima che un nodo possa votare su un impegno di votazione, deve prima confermarlo cancellazione tutte le schede con un controvalore inferiore. Questi passaggi, ovvero l'annullamento delle schede elettorali per trovarne una che possa essere impegnata, comportano più turni di votazione federata su più richieste di voto.
Le sezioni seguenti descrivono la nomina e la votazione in modo più dettagliato.
Nomina
All’inizio della fase di nomina, ogni nodo può scegliere spontaneamente un valore per V e votare per l’affermazione “Nomino V”. L'obiettivo in questa fase è confermare la nomina di un certo valore attraverso un voto federato.
Forse un numero sufficiente di nodi vota su proposizioni sufficientemente diverse da far sì che nessuna nomina possa raggiungere la soglia di accettazione. Pertanto, oltre a trasmettere i propri voti di nomina, i nodi “riflettono” le candidature dei loro pari. Eco significa che se un nodo vota per la nomina V, ma vede un messaggio da un vicino che vota per la nomina W, ora voterà sia per V che per W. (Non tutti i voti dei pari vengono ripetuti durante la nomina perché questo può portare a un'esplosione di diversi candidati. SCP include un meccanismo per regolare questi voti. In breve, esiste una formula per determinare la "priorità" di un peer dal punto di vista di un nodo e vengono riflessi solo i voti dei nodi ad alta priorità. Più lunga è la nomina richiede, più bassa è la soglia, quindi il nodo espande l'insieme di peer i cui voti rifletterà. La formula di priorità include il numero di slot come uno dei suoi input, quindi un peer ad alta priorità per uno slot può essere un peer a bassa priorità per un altro e viceversa).
Concettualmente, la nomina è parallela, sia V che W sono voti federali separati, ciascuno individualmente capace di ottenere l'accettazione o la conferma. In pratica, i messaggi del protocollo SCP raggruppano insieme questi voti individuali.
Sebbene votare per la nomina di V sia una promessa di non votare mai contro la nomina di V, è a livello di applicazione - in questo caso SCP - che si determina cosa significa "contro". SCP non vede un'affermazione che contraddice il voto "Nomino X", ovvero non c'è il messaggio "Sono contrario alla nomina di X", quindi il nodo può votare per nominare qualsiasi valore. Molte di queste nomine non andranno da nessuna parte, ma alla fine il nodo sarà in grado di accettare o confermare uno o più valori. Una volta confermato un candidato, diventa candidato.
Nomina SCP utilizzando il voto federato. Possono esserci molti valori “B” proposti dai peer e “riflessi” dal nodo.
Le candidature possono comportare più candidati confermati. Pertanto, SCP richiede che il livello dell'applicazione fornisca un metodo per combinare i candidati in uno solo composito (composito). Il metodo di unione può essere qualsiasi cosa. La cosa principale è che se questo metodo è deterministico, ogni nodo combinerà gli stessi candidati. In un sistema di votazione a pranzo, "unificazione" può semplicemente significare respingere uno dei due candidati. (Ma in modo deterministico: ogni nodo deve selezionare lo stesso valore da reimpostare. Ad esempio, la selezione precedente in ordine alfabetico). Nella rete di pagamento Stellar, dove si vota sulla cronologia delle transazioni, l'unione di due candidati proposti comporta l'unione delle transazioni che contengono e dell'ultimo dei loro due timestamp.
Il whitepaper SCP dimostra (Teorema 12) che entro la fine della fase di estensione, la rete alla fine converge in un unico composito. Ma c'è un problema: il voto federato è un protocollo asincrono (come SCP). In altre parole, i nodi non sono coordinati dal tempo, ma solo dai messaggi che inviano. Dal punto di vista del nodo, non è chiaro quando conclusa fase di estensione. E sebbene tutti i nodi alla fine arriveranno allo stesso composito, potrebbero prendere percorsi diversi lungo il percorso, creando diversi candidati compositi lungo il percorso, e non potranno mai dire quale sia quello finale.
Ma è normale. La nomina è solo una preparazione. La cosa principale è limitare il numero di candidati per raggiungere il consenso, che si verifica nel processo in esecuzione (ballottaggio).
Corsa
Il bollettino è una coppia , dove contatore è un numero intero che inizia da 1 e valore è un candidato dalla fase di nomina. Questo può essere il candidato di un nodo o il candidato di un nodo vicino accettato da quel nodo. In parole povere, una votazione implica ripetuti tentativi di forzare la rete a raggiungere un consenso su alcuni candidati in una certa votazione, detenendo potenzialmente molti voti federati sulle dichiarazioni elettorali. I contatori sulle schede tengono traccia dei tentativi effettuati e le schede con conteggi più alti hanno la precedenza su schede con conteggi inferiori. Se la newsletter si blocca, inizia una nuova votazione, ora sulla scheda elettorale .
È importante distinguere senso (ad esempio, quale dovrebbe essere l'ordine del pranzo: pizza o insalate), newsletter (coppia di controvalore) e dichiarazione riguardo alle schede elettorali. Il turno SCP prevede diverse votazioni federali, in particolare sulle seguenti dichiarazioni:
- "Sono pronto a impegnare lo scrutinio B" e
- "Annuncio l'impegno dello scrutinio B"
Dal punto di vista di un dato nodo, il consenso viene raggiunto quando trova una votazione B per la quale può confermare (cioè trovare un quorum accettante) l'affermazione "Impegno la votazione B". Da questo momento in poi è sicuro agire sul valore specificato in B, ad esempio effettuando l'ordine per il pranzo. È chiamato esternalizzazione significati. Una volta confermata l’accettazione del voto, un nodo può essere sicuro che qualunque altro nodo abbia esternalizzato lo stesso valore o lo farà in futuro.
Sebbene molte votazioni federate siano concettualmente condotte sulla base di rivendicazioni per molte schede diverse, non si scambiano tanti messaggi perché ogni messaggio incapsula un numero di schede. Un messaggio promuove quindi lo stato di molti voti federati contemporaneamente, ad esempio: “Accetto voti vincolanti che vanno da Prima "
Cosa significano i termini “preparato” e “impegnarsi”?
Un nodo vota per impegnare una votazione quando è sicuro che altri nodi non impegneranno schede con valori diversi. Convincere questo è lo scopo della preparazione della domanda. Un voto che dice "Sono pronto a impegnare la scheda B" è una promessa di non impegnare mai una scheda più piccola di B, cioè con un conteggio inferiore (SCP richiede che i valori nelle schede siano in un certo ordine. Pertanto, newsletter meno , se N1
Perché "Sono pronto a impegnare la scheda elettorale B" significa "Prometto di non impegnare mai schede elettorali inferiori a B"? Perché SCP definisce l'interruzione come l'opposto del commit. Un voto per preparare una votazione implica anche un voto per squalificare alcune altre schede e, come abbiamo discusso in precedenza, votare per una cosa è una promessa di non votare mai contro di essa.
Prima di trasmettere un commit, un nodo deve prima trovare un bollettino che può confermare come preparato. In altre parole, esegue un voto federato sull'argomento “Sono pronto a impegnare la votazione B”, possibilmente su molte schede diverse, finché non ne trova una che accetti il quorum.
Da dove provengono le schede per preparare il voto? Innanzitutto, il nodo trasmette i preparativi per votare per <1,C>, dove C è il candidato composito prodotto in fase di nomina. Tuttavia, anche dopo l'inizio dei preparativi per la votazione, le candidature potrebbero far sì che ulteriori candidati diventino nuove schede. Nel frattempo, i peer possono avere candidati diversi e possono formare un set di blocco che accetta "Sono pronto a impegnare la votazione B2", che convincerà anche il nodo ad accettarlo. Infine, esiste un meccanismo di timeout che genera nuovi turni di votazione federata su nuove schede con conteggi più alti se le schede attuali sono bloccate.
Non appena il nodo trova una scheda B che può confermare come preparata, trasmette un nuovo messaggio “Conferma scheda B”. Questo voto dice ai pari che il nodo non rinuncerà mai a B. In effetti, se B è una votazione , quindi “Conferma voto " significa il consenso incondizionato al voto per la disponibilità di ciascuna scheda elettorale a <∞, s>. Questo valore extra aiuta gli altri peer a mettersi al passo con il peer di commit se si trovano ancora nelle fasi precedenti del protocollo.
A questo punto è bene sottolineare ancora una volta che si tratta di protocolli asincroni. Solo perché un nodo invia voti positivi per un commit non significa che lo facciano anche i suoi pari. Alcuni di loro potrebbero ancora votare su dichiarazioni in preparazione al voto, altri potrebbero averne già esternato il significato. SCP spiega come un nodo dovrebbe elaborare ogni tipo di messaggio peer indipendentemente dalla sua fase.
Se viene visualizzato il messaggio "Ho annunciato un commit » non può essere ricevuto né confermato, ovvero la probabilità che il messaggio venga accettato o confermato O - o comunque una qualunque scheda di valore C, e non un'altra, visto che il nodo ha già promesso di non annullarla mai . Nel momento in cui un nodo trasmette i voti per un commit, sarà C o niente, a seconda di quanto lontano arriva il consenso. Tuttavia, questo non è ancora sufficiente affinché il nodo possa esternalizzare C. Alcuni peer bizantini (che costituiscono meno del quorum, in base ai nostri presupposti di sicurezza) potrebbero mentire al nodo. Accettare e poi confermare qualche scheda elettorale (o una serie di schede elettorali) è ciò che dà al nodo la fiducia necessaria per esternalizzare finalmente C.
Voto SCP attraverso il voto federato. Non mostrato: il timer può suonare in qualsiasi momento, aumentando il conteggio sulla scheda elettorale (ed eventualmente producendo un nuovo composto di ulteriori candidati nominati).
E questo è tutto! Una volta che la rete ha raggiunto un consenso, è pronta a farlo ancora e ancora. Sulla rete di pagamento Stellar, ciò accade circa una volta ogni 5 secondi: un’impresa che richiede sia la sicurezza che la sopravvivenza garantite da SCP.
SCP può raggiungere questo obiettivo facendo affidamento su più turni di votazione federata. Il voto federato è reso possibile dal concetto di quorum slice: insiemi di peer di cui ogni nodo ha deciso di fidarsi come parte del suo quorum (soggettivo). Questa configurazione significa che il consenso può essere raggiunto anche in una rete con membri aperti e inganni bizantini.
ulteriore lettura
- È possibile trovare il white paper SCP originale E progetto di specifiche per la sua attuazione.
- L'autore originale del protocollo SCP, David Mazier, lo spiega in modo semplificato (ma pur sempre tecnico). .
- Potresti essere rimasto sorpreso di non trovare i termini “estrazione mineraria” o “prova di lavoro” in questo articolo. SCP non utilizza questi metodi, ma alcuni altri algoritmi di consenso lo fanno. Zane Witherspoon ha scritto accessibile .
- una rete semplice che raggiunge il consenso in un ciclo completo di SCP.
- Per i lettori interessati alle implementazioni SCP: vedere , utilizzato dalla rete di pagamento Stellar, o , che ho scritto per una migliore comprensione di SCP.
Fonte: habr.com