Protocolli BFT: PBFT e Tendermint

Il Problema dei generali bizantini, formulato da Lamport, Shostak e Pease nel 1982, chiede: un sistema distribuito può raggiungere il consenso quando alcuni partecipanti inviano messaggi contraddittori? Il problema prende il nome dai generali bizantini che devono coordinare un attacco, ma possono includere traditori che inviano ordini discordanti. Un sistema è Byzantine Fault Tolerant (BFT) se raggiunge un consenso corretto nonostante la presenza di fino a f nodi malevoli su un totale di 3f+1. La BFT è lo standard di riferimento per il consenso nelle blockchain che richiedono sicurezza in condizioni avversarie.

PBFT (Castro e Liskov, 1999) è stato il primo protocollo BFT pratico e ha dimostrato che la BFT poteva operare in modo efficiente nei sistemi reali. PBFT opera in view (termine), ciascuna con un primary (leader) designato. Il funzionamento normale prevede tre fasi: pre-prepare (il primary trasmette in broadcast la richiesta del client e il numero di sequenza), prepare (le repliche trasmettono in broadcast il proprio accordo insieme alla sequenza) e commit (le repliche trasmettono in broadcast la conferma del commit). Una richiesta viene eseguita quando una replica raccoglie 2f+1 messaggi commit corrispondenti. PBFT garantisce safety e liveness assumendo che meno di 1/3 delle repliche siano bizantine.

Il principale limite di PBFT è la complessità O(n^2) dei messaggi per richiesta: ciascuna delle n repliche invia messaggi a tutte le altre nelle fasi prepare e commit. Con n=100 repliche, ogni richiesta genera circa 10.000 messaggi. Questo rende PBFT impraticabile per grandi insiemi di validatori. La comunità di ricerca BFT ha trascorso due decenni a migliorare questo aspetto: BFT-SMART ha ridotto le costanti, HotStuff ha raggiunto una complessità lineare dei messaggi tramite un modello di inoltro da parte del leader, e Tendermint ha adattato le idee di PBFT all'uso nelle blockchain pubbliche.

Quando si sospetta che il primary di PBFT sia guasto (timeout), le repliche avviano un view change. Ogni replica trasmette in broadcast un messaggio view-change contenente il proprio stato (i valori prepared della view precedente). Il nuovo primary raccoglie 2f+1 messaggi view-change, costruisce un messaggio new-view che dimostra che la transizione di stato è coerente con i valori già committati e lo trasmette in broadcast. I view change sono costosi — O(n^3) messaggi — e costituivano un collo di bottiglia pratico. Ottimizzazioni come il certificato di view-change di PBFT e il design con pipelining di HotStuff affrontano questo problema.

Tendermint (2014, Kwon; in produzione in Cosmos dal 2019) adatta PBFT agli ambienti blockchain pubblici. Tendermint prevede tre fasi per blocco: propose (il leader trasmette il blocco proposto), prevote (i validatori votano la proposta) e precommit (i validatori votano per committare il blocco dopo aver visto 2/3 dei prevote). Un blocco è committato quando un validatore raccoglie 2/3 dei voti precommit (un certificato di quorum). I validatori si alternano come proponenti in ordine round-robin, con peso proporzionale allo stake. Se un round scade senza un commit, i validatori passano al round successivo con un voto nil.

Tendermint garantisce una forte safety: un blocco committato è definitivo e non può essere annullato finché meno di 1/3 dello stake è bizantino. Questa è una finalità sincrona: dopo il commit non ci sono fork. La liveness richiede una rete parzialmente sincrona: il protocollo avanza quando i ritardi dei messaggi sono limitati, ma non richiede una sincronia continua. Il compromesso tra liveness e safety è fondamentale: Tendermint sacrifica la liveness (può arrestarsi se la rete si partiziona) per garantire la safety, a differenza di chain come Bitcoin, che sacrificano la safety (consentono fork temporanei) per la liveness.

Un meccanismo fondamentale di Tendermint è il vote locking. Quando un validatore invia un precommit per un blocco al round r, si vincola a quel blocco. Nei round successivi, un validatore vincolato può esprimere un prevote solo per il blocco a cui è vincolato (oppure un voto nil se riceve la prova che il blocco non è stato committato). Questo impedisce commit contraddittori tra round diversi. Un validatore può sbloccarsi solo se riceve una polka (2/3 dei prevote) per un blocco diverso in un round successivo, dimostrando che il blocco originale non è stato committato.

Cosmos Inter-Blockchain Communication (IBC) si basa sulla finalità immediata di Tendermint per i trasferimenti tra chain. Un light client Tendermint tiene traccia dell'insieme dei validatori e dell'ultimo commit (un'intestazione di blocco più 2/3 firme di precommit). Per verificare un pacchetto proveniente dalla chain A, il modulo IBC della chain B verifica il certificato di quorum, cioè che 2/3 dei validatori della chain A abbiano firmato l'intestazione di blocco interessata. In questo modo, la sicurezza di IBC dipende dalla garanzia BFT di Tendermint: un trasferimento tra chain è definitivo non appena il blocco d'origine viene committato.

HotStuff (Yin et al., 2018; alla base di LibraBFT/DiemBFT di Facebook, oggi Aptos e Sui) raggiunge una complessità O(n) dei messaggi per round di consenso usando una topologia a stella: tutti i validatori inviano i voti al leader, il leader li aggrega in una firma a soglia (QC, quorum certificate) e trasmette il QC. HotStuff usa un design concatenato a tre fasi, in cui le dimostrazioni di safety si estendono su tre QC consecutivi, consentendo il pipelining. La complessità lineare rende HotStuff pratico per 100-300 validatori, come adottato in Aptos e Sui.

Le blockchain aziendali (Hyperledger Fabric, Besu, Quorum) usano il consenso BFT per reti permissioned in cui l'identità dei validatori è nota. Il servizio di ordinamento basato su Raft di Hyperledger Fabric fornisce tolleranza ai guasti da crash (non bizantini) per consorzi fidati. L'obiettivo BFT previsto da Fabric è SmartBFT, un'implementazione basata su libreria. R3 Corda usa un cluster di notary con BFT-SMART per prevenire la doppia spesa. La scelta tra CFT e BFT riflette le ipotesi sulla fiducia: la BFT è necessaria quando i validatori possono essere avversari, mentre la CFT è sufficiente quando sono semplicemente inaffidabili.

Per comprendere la BFT è necessario capire quali attacchi contrasta e quali invece non gestisce. La BFT gestisce i validatori che fanno equivocazione, inviando messaggi contraddittori a peer diversi, e i validatori che vanno in crash o restano silenziosi. Non gestisce gli attacchi Sybil: un attaccante che controlla 1/3 dei validatori creando identità false può compromettere la safety. Per questo le chain BFT pubbliche usano il peso dello stake PoS: acquisire 1/3 dello stake costa denaro reale e fornisce resistenza agli attacchi Sybil. La BFT presume inoltre la consegna eventuale dei messaggi (sincronia parziale): una partizione di rete che duri più del timeout di liveness può arrestare la chain.

Qual è la frazione massima di validatori che può essere bizantina in un protocollo BFT standard mantenendo la safety?

I protocolli BFT garantiscono il consenso nonostante la presenza di fino a 1/3 di validatori malevoli. PBFT (1999) ha dimostrato che la BFT è pratica, ma presenta una complessità O(n^2) dei messaggi. Tendermint adatta PBFT alle blockchain con finalità immediata e blocco dei voti. HotStuff raggiunge una complessità O(n) tramite QC con firme a soglia ed è utilizzato in Aptos e Sui. Cosmos IBC usa la finalità immediata di Tendermint per trasferimenti tra chain verificati. Le blockchain aziendali usano BFT-SMART o Raft a seconda che ci si aspetti la presenza di guasti bizantini o semplicemente di guasti da crash.