Questa è la seconda parte della nostra serie sul sistema di consenso di Polkadot. Per l'introduzione si veda la parte 1.

Nell'introduzione a questa serie, ho spiegato che un algoritmo di consenso aiuta un network di computer a rispondere a tre domande. GRANDPA risponde alla seconda.

• Chi può proporre la prossima modifica?
• Quale serie di modifiche è definitiva?
• Cosa succede se qualcuno infrange le regole?

GRANDPA è il dispositivo di finalizzazione di Polkadot. Il suo scopo è selezionare in modo deterministico la canonical chain. In altre parole, GRANDPA decide quale insieme di modifiche è definitivo. Non produce blocchi da solo; invece, i validatori GRANDPA importano i blocchi da un modulo di produzione di blocchi (di cui parleremo nella parte 3).

Uno dei vantaggi della separazione tra la produzione di blocchi e la sicurezza¹, oltre al fatto che si tratta in generale di una buona tecnica, è che GRANDPA non impone molti requisiti sui blocchi che importa. GRANDPA richiede solo che il sistema di produzione dei blocchi abbia una sicurezza finale, che segua la regola di scelta dei fork di GRANDPA e che l'intestazione di un blocco abbia un puntatore al suo blocco genitore. Questa terza proprietà garantisce che i client leggeri possano seguire la chain.

Il protocollo GRANDPA

GRANDPA si distingue da altri algoritmi di blockchain a tolleranza di errore bizantina (BFT) in quanto i validatori votano sulle chain, non sui blocchi. Il protocollo applica i voti in modo transitorio e l'algoritmo GRANDPA trova il numero di blocco più alto con un numero sufficiente di voti per essere considerato definitivo. Questo processo consente di finalizzare diversi blocchi in un unico round.

Quest'ultima parte è fondamentale perché elimina un collo di bottiglia che ostacola altri dispositivi di finalizzazione della blockchain. GRANDPA, come altri derivati della PBFT, ha una complessità O(n²). In altre parole, se si raddoppia il numero di nodi, si deve inviare un numero di messaggi quattro volte superiore. I sistemi di consenso che rendono la produzione di blocchi parte del processo di finalizzazione prevedono l'invio di questi messaggi per ogni singolo blocco. Isolando la produzione di blocchi in un altro modulo, possiamo produrre blocchi in modo molto più efficiente (O(n) per BABE) e finalizzarne diversi insieme in un unico round.

Per vedere un esempio di ciò, osservate questi messaggi di log da un nodo Kusama:

Idle (24 peers), best: #664257 (0x706c…76b7), finalized #664253 (0xe4ab…4d2a)

Imported #664258 (0xee71…6321)

Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)

Si noti che in un unico round, GRANDPA ha finalizzato tre blocchi. (664,254 to 664,256).

Questo è un esempio di come GRANDPA possa finalizzare più blocchi in un round, come si vede nei messaggi di log qui sopra. I blocchi grigio scuro a sinistra erano già stati finalizzati e i validatori (punti grigi a destra) hanno inviato i voti per il nuovo round. Altri tre blocchi hanno ottenuto una supermaggioranza e sono stati finalizzati.

Un round di GRANDPA

I votanti eseguono le seguenti operazioni per finalizzare i nuovi blocchi:

1. Un nodo designato come "primario" trasmette dal turno precedente il blocco più alto che ritiene possa essere finalizzato.
2. Dopo aver atteso un ritardo del network, ogni validatore trasmette un "pre-voto" per il blocco più alto che ritiene debba essere finalizzato. Se la supermaggioranza dei validatori è onesta, questo blocco dovrebbe ampliare la chain trasmessa dal primario. Questa nuova chain potrebbe essere più lunga di diversi blocchi rispetto all'ultima chain finalizzata.
3. Ogni validatore calcola il blocco più alto che può essere finalizzato in base all'insieme dei pre-voti. Se l'insieme dei pre-voti estende l'ultima chain finalizzata, ogni validatore lancia un "pre-commit" a quella chain.
4. Ogni validatore attende di ricevere un numero sufficiente di pre-commit per formare un messaggio di commit sulla chain appena finalizzata.

Una sottile ma importante distinzione rispetto ad altri algoritmi a tolleranza d'errore bizantina (come PBFT e Hotstuff) è che non vi è alcun cambio di visuale sul percorso critico. Sebbene il primario cambi a ogni round, questo cambio di visuale serve solo a iniziare un nuovo round in condizioni di network asincrono, in modo che in network parzialmente sincroni il protocollo avanzi sempre, anche senza assegnare un primario.

Le fasi del protocollo sono completabili quando hanno più di due terzi dei pre-voti o dei pre-commit dei validatori. Per avere una finalizzazione deterministica, il numero di voti nell'insieme dei validatori deve essere limitato. Ciò è diverso dalle chain con finalizzazione probabilistica, che possono avere insiemi di validatori illimitati. Il metodo di selezione dell'insieme dei votanti è una logica definita al di fuori del protocollo GRANDPA (vedi parte 4).

GRANDPA supporta il voto pesato. Ad esempio, si potrebbe implementare GRANDPA sulla propria chain, dove i validatori con più stake ottengono più voti. In Polkadot, tuttavia, tutti i validatori hanno un singolo voto, dello stesso peso. Questa attribuzione di pesi è stata una decisione economica per evitare che piccoli gruppi di nodi guadagnino una grande quota di network.

Sicurezza affidabile: Quando le cose vanno male

GRANDPA dispone di una funzione chiamata "accountable safety" per ritenere i validatori responsabili delle violazioni della sicurezza. Una violazione della sicurezza si verifica quando due blocchi che si trovano in chain diverse vengono finalizzati. La accountable safety è come un'indagine dopo un incidente.

Ma prima di tutto, come hanno fatto due chain in conflitto a trovare una soluzione conclusiva? I sistemi BFT sono sempre costruiti sulla base del requisito che il numero massimo di validatori difettosi sia una frazione, nel nostro caso un terzo, del totale dei validatori. Per finalizzare due chain in conflitto, l'insieme dei validatori non ha soddisfatto questo requisito: almeno un terzo dei validatori ha votato su queste due chain.

In questo esempio, ci sono 10 validatori, quindi 3 è il numero massimo di validatori fallaci che il sistema può sopportare (f = (10 - 1) / 3). Con 4 validatori fallaci (rossi) e una partizione del network, ogni gruppo di validatori onesti (blu) può pensare che un blocco diverso sia definitivo.

Votare su due chain in conflitto si chiama equivocare. È una verità universalmente riconosciuta che l'equivoco è un affronto ai sistemi BFT. In GRANDPA possiamo rilevarlo.

Per prima cosa, iniziamo a chiedere ai nodi perché non hanno considerato definitivo un blocco quando hanno votato per finalizzare il secondo blocco. Qualsiasi validatore onesto dovrebbe rispondere con una serie di pre-voti o pre-commit per il secondo round che abbia una supermaggioranza per il secondo blocco.

Se è così, poniamo una seconda domanda: Quali pre-voti per il primo turno hai visto? In sostanza, chiediamo loro di fare la spia su altri validatori e di rivelare tutti i voti che hanno ricevuto dai loro pari. Da qualche parte nell'unione di entrambi gli insiemi si scopriranno i validatori che hanno votato per le due chain in conflitto. Presumibilmente, saranno puniti pesantemente, ma questo è il compito della logica della chain, non del consenso.

Se si verifica un errore di sicurezza, il network dovrà effettuare un hard fork per scegliere quale delle chain in conflitto è quella definitiva. Con la “accountable safety” (sicurezza responsabile), Polkadot può garantire che i validatori che hanno eseguito l'attacco siano puniti e non rimangano nell'insieme dei validatori.

Come GRANDPA aiuta la disponibilità e la validità

Ricordate i messaggi di log di cui sopra? Si noti che il blocco finalizzato è due blocchi indietro rispetto al blocco migliore. Questo ritardo è in realtà un vantaggio del mantenere distinte la produzione e la finalizzazione dei blocchi.

Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)

I sistemi di interoperabilità blockchain, Polkadot compreso, hanno un problema di disponibilità dei dati. Immaginate che un singolo collator invii un blocco a un validatore, ma che nessuno degli altri parachain collators lo abbia visto. Cosa succederebbe se il collator che ha inviato il blocco andasse offline? I validatori hanno la responsabilità di conservare i blocchi completi per un certo periodo di tempo, in modo che qualsiasi collator di parachain possa richiedere il blocco.

I validatori dovrebbero eseguire i blocchi prima di votarli, ma vogliamo essere sicuri che lo facciano. In Polkadot esistono alcuni nodi, che chiamiamo “pescatori”, che eseguono i blocchi e segnalano qualsiasi comportamento scorretto dei validatori, ad esempio la proposta di un blocco non valido da includere nella Relay Chain.

Non vogliamo mai che si finalizzi un blocco non valido o che si finalizzi un blocco che i collator non possono recuperare. Mantenendo la finalizzazione qualche blocco dietro la punta della chain, possiamo lasciare che i “pescatori” verifichino la correttezza dei blocchi e sfidare i validatori per la validità dei blocchi.

Abbiamo discusso su come decidere la canonical chain, ma da dove provengono queste opzioni di chain? È qui che entra in gioco BABE, che vedremo nella parte 3 di questa serie.

[1] Preferisco il termine "sicurezza" a quello di "finalità" perché i blocchi finalizzati non sono definitivi nel senso delle leggi della fisica. Sono definitivi perché l'ha detto il GRANDPA. Preferisco di gran lunga il termine "sicuro", che comporta aspettative più ragionevoli rispetto a "definitivo". Ad esempio, consideriamo sicuri i viaggi in aereo, ma sappiamo tutti che a volte gli aerei precipitano. Inoltre, quando un aereo precipita, abbiamo un processo di indagine e di ricorso legale per ritenere responsabili alcune parti.

Leggi la terza parte su BABE ->

December 18, 2019 in Consensus,GRANDPA by Joe Petrowski