Riepilogo Tecnico: Giskard

Problema

L'apprendimento decentralizzato offre un'alternativa preservante la privacy rispetto all'addestramento centralizzato, permettendo ai partecipanti di interagire peer-to-peer senza un orchestratore centrale fidato. Tuttavia, questi sistemi affrontano due sfide simultanee e spesso contrastanti:

1. Robustezza Bizantina: Nodi malevoli o difettosi possono inviare aggiornamenti del modello arbitrari e manipolati (avvelenamento del modello) per corrompere il modello globale. Difendersi da ciò richiede tipicamente l'ispezione e il confronto dei singoli contributi per filtrare gli outlier (ad esempio, utilizzando mediane coordinate-wise o medie troncate).
2. Riservatezza: I partecipanti devono mantenere privati i propri dati locali e i propri aggiornamenti del modello. Le tecniche crittografiche come la Computazione Multipartitica Sicura (MPC) nascondono questi aggiornamenti, ma le funzioni di aggregazione robusta standard (che si basano su ordinamento e confronto) sono computazionalmente costose da implementare in forma criptata.

Le soluzioni esistenti affrontano questi problemi separatamente o li combinano utilizzando l'MPC in modi che non scalano. Molti approcci MPC decentralizzati precedenti si affidano a una comunicazione all-to-all o delegano il calcolo a un singolo piccolo comitato, risultando in una complessità di comunicazione per nodo che cresce linearmente o peggio con la dimensione della rete ($O(n)$ o $O(n \log^2 n)$). Ciò crea un collo di bottiglia fondamentale per la scalabilità in implementazioni su larga scala (ad esempio, $n \ge 10^4$).

Metodologia: Il Protocollo Giskard

Giskard è un protocollo progettato per ottenere sia la robustezza bizantina che la riservatezza in un contesto completamente decentralizzato con una complessità di comunicazione sub-lineare. Opera sotto un modello di avversario statico e computazionalmente limitato, in cui fino a $f < n/4$ parti possono essere corrotte.

Intuizioni Tecniche Core

1. Ricerca Binaria per la Mediana: Invece di implementare costosi circuiti di ordinamento generici in MPC, Giskard riformula il calcolo della mediana coordinate-wise come una ricerca binaria sicura sul dominio dei valori. Il protocollo restringe iterativamente l'intervallo $[Left, Right]$ contando quanti input sono inferiori a un pivot $p_t$. Ciò riduce il problema a una sequenza di operazioni di conteggio sicure.
2. Albero Gerarchico di Comitati: Per distribuire il carico computazionale, Giskard organizza $n$ parti in un albero $k$-ario di comitati, ciascuno di dimensione $m = O(\log n)$.
   • Foglie (Livello 0): Le singole parti confrontano i propri vettori locali con l'attuale pivot e condividono segretamente i vettori di bit risultanti con i loro comitati di base assegnati.
   • Comitati di Base (Livello 1): Validano il dominio dei bit condivisi (assicurando che siano 0 o 1) utilizzando una prova di grado 2, aggregano le quote e ri-condividono le somme parziali verso l'alto.
   • Comitati Intermedi (Livelli da 2 a $L-1$): Ricevono le quote dai comitati figli, eseguono la ri-condivisione verificabile e aggregano verso l'alto.
   • Comitato Radice (Livello $L$): Ricostruisce il conteggio globale in chiaro, aggiorna il pivot e trasmette il nuovo pivot verso il basso nell'albero per l'iterazione successiva.
3. Primitiva Crittografiche: Il protocollo utilizza la Verifiable Secret Sharing (VSS) basata sullo schema BGW (Asharov e Lindell) per garantire la sicurezza contro avversari malevoli. Impiega sottoprotoocoli per la condivisione, la moltiplicazione e la ri-condivisione, tutti dimostrati essere sicuri secondo il modello Universalmente Componibile (UC).

Garanzie di Sicurezza e Robustezza

• Riservatezza: Gli input individuali e i conteggi intermedi rimangono nascosti; viene rivelato solo il conteggio aggregato finale (utilizzato per aggiornare il pivot).
• Robustezza Bizantina: Il protocollo tollera fino a $n/4$ parti bizantine. Soddisfa il criterio di robustezza bizantina $(f, \kappa)$, garantendo che l'output rimanga vicino alla media degli aggiornamenti onesti, eguagliando la soglia di robustezza della mediana coordinate-wise.
• Correttezza: La ricerca binaria converge alla mediana con una precisione $q$ dopo $N_{iter} = \lceil \log_2(2u/q) \rceil$ iterazioni.

Contributi Chiave

1. Protocollo Innovativo: Proposta di Giskard, un protocollo di apprendimento decentralizzato robusto e riservato capace di scalare a milioni di parti.
2. Sicurezza Teorica: Una prova formale che Giskard è UC-sicuro nel modello ibrido, basandosi su standard assunzioni crittografiche e sulla sicurezza dei suoi sottoprotoocolli (BA, VSS, ecc.).
3. Analisi della Complessità di Comunicazione: Dimostrazione che la complessità di comunicazione per parte nel caso peggiore è polilogaritmica in $n$ ($O(d \cdot N_{iter} \cdot \log^3 n)$), un miglioramento significativo rispetto ai competitor come All-to-All ($O(d \cdot n^2)$) o All-to-Committee ($O(d \cdot n \log^2 n)$).
4. Validazione Sperimentale: Valutazione estesa sui dataset MNIST e CIFAR-10 con dimensioni di rete fino a $n=10^6$.

Risultati Sperimentali

Gli autori hanno valutato Giskard contro due topologie di base: All-to-All (A2A) e All-to-Committee (A2C).

• Scalabilità (Costo di Comunicazione):

  • A $n=10^6$ con una frazione bizantina del 10%, Giskard riduce la comunicazione per parte di circa 1.775 volte rispetto ad A2C e di ordini di grandezza rispetto ad A2A.
  • Mentre A2C concentra il carico su un singolo comitato (rendendolo impraticabile a causa dei limiti di banda su larga scala), Giskard distribuisce il carico attraverso l'albero, mantenendo gestibili i costi per singola parte anche per $n=10^6$.
  • Il tempo di esecuzione stimato per A2C e A2A a scale elevate supera i limiti pratici (giorni o anni), mentre Giskard rimane nell'ordine di minuti o ore.

• Utilità del Modello (Robustezza):

  • Sotto quattro attacchi di avvelenamento del modello (Label Flipping, Sign Flipping, IPM, ALIE) su dati non-i.i.d., la mediana a ricerca binaria di Giskard ha raggiunto un'accuratezza di test comparabile agli aggregatori robusti in chiaro allo stato dell'arte (Trimmed Mean, Median).
  • Su MNIST, il divario di accuratezza era inferiore allo 0,4%. Su CIFAR-10, il divario era generalmente inferiore all'1,5%, con scarti leggermente superiori (fino al 2,7%) per attacchi altamente ottimizzati che richiedono una precisione maggiore.
  • Gli esperimenti hanno identificato una soglia netta per il numero di iterazioni della ricerca binaria ($N_{iter}$); aumentare le iterazioni oltre $\approx 10$ non ha prodotto guadagni significativi in termini di robustezza, ma ha aumentato linearmente i costi di comunicazione.

Significato e Rivendicazioni

Il documento sostiene che Giskard colma il divario tra scalabilità e sicurezza nell'apprendimento decentralizzato. Combinando una struttura gerarchica di comitati con una formulazione specializzata della mediana tramite ricerca binaria, Giskard ottiene:

• Comunicazione sub-lineare: È il primo protocollo a raggiungere una comunicazione per parte polilogaritmica per l'aggregazione riservata e bizantina-robusta in un contesto completamente decentralizzato.
• Garanzie Formali: A differenza degli approcci euristici, Giskard fornisce prove di sicurezza UC e limiti formali di robustezza.
• Praticità: I risultati sperimentali dimostrano che il protocollo è vitale per implementazioni su larga scala (fino a un milione di partecipanti) dove le precedenti soluzioni MPC sarebbero state computazionalmente e comunicativamente impraticabili.

Gli autori concludono che, sebbene il protocollo introduca un compromesso tra numero di iterazioni e precisione, il sistema proposto bilancia efficacemente riservatezza, robustezza e scalabilità, rendendo pratico l'apprendimento decentralizzato sicuro su larga scala. Si suggerisce come lavoro futuro l'esplorazione di varianti computazionali basate su assunzioni crittografiche per ridurre ulteriormente i costi.