Riepilogo Tecnico: Digest a Conservazione della Distanza per il Consenso BFT

1. Enunciato del Problema

I protocolli di consenso tolleranti ai guasti bizantini (BFT), inclusi HotStuff, PBFT ed Ethereum 2.0, si affidano a hash resistenti alle collisioni (ad es. SHA-256) per confrontare gli stati dei validatori. Sebbene efficaci nel prevenire la falsificazione, questo approccio distrugge le informazioni sulla "distanza". Se due validatori concordano su 19 transazioni su 20, i loro hash sono completamente non correlati, indistinguibili da validatori che non condividono alcuna transazione. Questa limitazione impone tre vincoli strutturali alla letteratura BFT:

1. Sincronizzazione Obbligatoria dello Stato: I validatori devono sincronizzare completamente lo stato prima di votare, poiché gli hash non possono misurare un accordo parziale.
2. Qualità dell'Accordo Immisurabile: I protocolli non possono rilevare un accordo unanime fino al completamento di tutti i round di votazione, imponendo latenze fisse multi-round anche in condizioni ideali.
3. Grandi Comitati Gerarchici: Per garantire la sicurezza in un consenso strutturato ad albero, i gruppi foglia devono essere sufficientemente grandi (ad es. 128 validatori in Ethereum) per soddisfare indipendentemente la soglia di tolleranza bizantina $2N/3$, limitando la profondità dell'albero e la scalabilità.

2. Metodologia: Digest a Conservazione della Distanza

Il documento introduce un primitivo chiamato Digest a Conservazione della Distanza per sostituire gli hash resistenti alle collisioni nel confronto degli stati. La costruzione prevede:

• Vettorializzazione: Ogni transazione viene hashata utilizzando SHA-512. L'output di 64 byte viene suddiviso in 8 segmenti.
• Mappatura delle Coordinate: Ogni segmento è trattato come un intero senza segno, ridotto modulo 10.000 e diviso per 10.000 per produrre una coordinata nell'intervallo $[0, 1)$.
• Somma Commutativa: Il digest di un validatore per un insieme di transazioni $T$ è la somma vettoriale $D(T) = \sum_{tx \in T} v(tx)$ in uno spazio a 8 dimensioni.

Questo primitivo possiede tre proprietà che gli hash non hanno:

1. Distanza Proporzionale: La distanza euclidea tra due digest è proporzionale al numero di transazioni diverse.
2. Sintesi Esatta: La media ponderata di un gruppo di digest è una rappresentazione esatta dello stato aggregato del gruppo, permettendo a un gruppo di validatori di essere sintetizzato in un singolo valore compatto (76 byte) senza perdita di informazioni.
3. Identificazione delle Differenze di Insieme: Quando i digest differiscono, una diff di Bloom filter permette all'aggregatore di identificare esattamente quali transazioni mancano dalla visione di un validatore, consentendo una sincronizzazione mirata senza scambio completo dello stato.

3. Contributi Chiave e Applicazioni

Il documento dimostra tre applicazioni principali di questo primitivo all'interno di un nuovo protocollo denominato Proxima:

A. Protocollo BFT a Due Fasi (Proxima)

Proxima opera in due fasi:

• Fase 1 (Filtraggio della Distanza): I validatori inviano digest e Bloom filter a un aggregatore. L'aggregatore raggruppa i validatori entro una soglia di distanza. Se la varianza del gruppo è vicina a zero (indicando un alto accordo), il protocollo emette un certificato di finalità a round singolo (percorso veloce). In caso contrario, spinge le transazioni mancanti tramite diff di Bloom.
• Fase 2 (Impegno): I membri del gruppo firmano l'hash del blocco utilizzando firme BLS. L'aggregatore produce una firma aggregata.
• Risultato: A differenza di HotStuff, che richiede tre round indipendentemente dall'accordo, Proxima raggiunge la finalità a round singolo quando i validatori concordano.

B. Consenso Strutturato ad Albero con Piccoli Gruppi

Poiché il filtraggio della distanza opera a livello individuale piuttosto che richiedere un BFT a livello di gruppo, Proxima abilita un consenso gerarchico con piccoli gruppi (ad es. 10 validatori).

• Meccanismo: I leader delle foglie filtrano i validatori bizantini (che sono lontani dal riferimento) e riportano la media ponderata dei validatori onesti.
• Risultato: Questo elimina la necessità di grandi comitati (128 validatori) per garantire la sicurezza, permettendo alberi più profondi (5 livelli contro 2–3 livelli) e riducendo la complessità dei messaggi.

C. Verifica della Coerenza Cross-Shard

I digest abilitano una verifica a costo costante tra gli shard.

• Meccanismo: Gli shard vicini scambiano digest delle transazioni della zona di sovrapposizione. Se la distanza è zero, gli stati corrispondono. Se non è zero, la diff di Bloom identifica le specifiche transazioni divergenti per la risoluzione.
• Risultato: Questo sostituisce il coordinamento per transazione del Two-Phase Commit (2PC) o delle catene di ricevute, riducendo l'overhead cross-shard del 99% rispetto al 2PC a tassi di propagazione del 95%.

4. Risultati e Valutazione

Il documento valuta Proxima rispetto a HotStuff, PBFT e alla struttura dei comitati di Ethereum utilizzando simulazioni con $N=100.000$ validatori e il 30% di guasti bizantini.

• Complessità dei Messaggi: Proxima Tree utilizza 2,2 volte meno messaggi rispetto a HotStuff. Questa è una proprietà strutturale non influenzata dal parallelismo, derivante dall'esecuzione a due fasi, dal pre-filtraggio dei nodi bizantini e dall'instradamento ad albero con sintesi compatte.
• Latenza:
  • Single-Core: Proxima raggiunge la finalità single-core in ~0,9 secondi (902 ms) rispetto a ~18 secondi per HotStuff. La struttura ad albero distribuisce l'aggregazione BLS, mantenendo bassa l'elaborazione del percorso critico (9,9 ms).
  • Multi-Core: Sebbene l'aggregazione BLS multi-core riduca il divario (HotStuff scende a ~940 ms, Proxima Flat a ~220 ms), l'albero mantiene un vantaggio nel tempo BLS del percorso critico perché i nodi foglia elaborano pochissime firme.
• Overhead Cross-Shard: Al 95% di propagazione, la verifica basata su digest utilizza il 99% di messaggi in meno rispetto al 2PC e il 95% in meno rispetto agli approcci basati su ricevute (NEAR Nightshade).
• Sicurezza: La sicurezza è dimostrata indipendente dal raggruppamento della Fase 1. Meno di $N/3$ validatori bizantini non possono causare finalizzazioni conflittuali. La Fase 1 può escludere validatori onesti (rischio di liveness), ma questo è limitato dall'ineguaglianza di Hoeffding a essere trascurabile ($<10^{-9}$ a $N$ pratici).

5. Significato e Affermazioni

Il documento afferma che i digest a conservazione della distanza rimuovono i tre vincoli fondamentali imposti dall'hashing resistente alle collisioni nel BFT. Abilitando la misurazione della qualità dell'accordo, il primitivo permette:

1. Percorsi Veloci Ottimistici: I protocolli possono finalizzare in un round quando il consenso è alto.
2. Gerarchie Scalabili: Gli alberi di consenso possono utilizzare piccoli gruppi (dimensione 10) e strutture profonde, poiché la sicurezza è mantenuta tramite filtraggio della distanza piuttosto che tramite votazione per gruppo.
3. Sharding Efficiente: La coerenza cross-shard può essere verificata a un costo costante per coppia di shard, scalando con la divergenza effettiva piuttosto che con il volume totale delle transazioni.

Gli autori sottolineano che, sebbene il primitivo sia un'applicazione nota dell'Hashing Sensibile alla Località (LSH) nelle strutture dati, la sua applicazione al accordo bizantino è innovativa. La sicurezza del sistema si basa su assunzioni crittografiche standard (firme BLS e SHA-512), con il filtro della distanza che funge da meccanismo di liveness e ottimizzazione piuttosto che da meccanismo di sicurezza. Il documento conclude che questo approccio offre un miglioramento generale per qualsiasi protocollo BFT che confronta stati tramite hash.