Technische Samenvatting: Giskard

Probleemstelling

Gedecentraliseerd leren biedt een privacy-beschermend alternatief voor gecentraliseerde training door deelnemers toe te staan om peer-to-peer met elkaar te interageren zonder een vertrouwde centrale orchestrator. Deze systemen worden echter geconfronteerd met twee gelijktijdige, vaak conflicterende uitdagingen:

1. Byzantijnse Robuustheid: Kwaadwillige of defecte knooppunten kunnen willekeurige, gemanipuleerde modelupdates (modelvergiftiging) indienen om het globale model te corrumperen. Het verdedigen tegen dit type aanvallen vereist doorgaans het inspecteren en vergelijken van individuele bijdragen om uitschieters te filteren (bijv. door middel van coördinaat-gewijze medianen of getrimde gemiddelden).
2. Vertrouwelijkheid: Deelnemers moeten hun lokale data en modelupdates privé houden. Cryptografische technieken zoals Secure Multi-Party Computation (MPC) verbergen deze updates, maar standaard robuuste aggregatiefuncties (die afhankelijk zijn van sorteren en vergelijken) zijn computationeel duur om in versleutelde vorm te implementen.

Bestaande oplossingen pakken deze problemen apart aan of combineren ze met MPC op manieren die niet schalen. Veel eerdere gedecentraliseerde MPC-benaderingen vertrouwen op all-to-all communicatie of delegeren de berekening aan een enkele kleine commissie, wat resulteert in een per-node communicatiecomplexiteit die lineair of zelfs erger groeit met de netwerkomvang ($O(n)$ of $O(n \log^2 n)$). Dit creëert een fundamentele schaalbaarheidsbottleneck voor grootschalige implementaties (bijv. $n \ge 10^4$).

Methodologie: Het Giskard-protocol

Giskard is een protocol dat ontworpen is om zowel Byzantijnse robuustheid als vertrouwelijkheid te bereiken in een volledig gedecentraliseerde setting met sub-lineaire communicatiecomplexiteit. Het opereert onder een statisch, computationeel begrensd adversary-model waarbij tot $f < n/4$ partijen gecorrumpeerd kunnen zijn.

Kerninzichten

1. Binair Zoeken naar de Mediaan: In plaats van het implementeren van generieke sorteercircuits (die duur zijn in MPC), herformuleert Giskard de coördinaat-gewijze mediaanberekening als een veilige binaire zoekopdracht over het waardedomein. Het protocol verkleint iteratief het bereik $[Left, Right]$ door te tellen hoeveel inputs kleiner zijn dan een pivot $p_t$. Dit reduceert het probleem tot een reeks veilige teloperaties.
2. Hiërarchische Commissieboom: Om de computationele last te verdelen, organiseert Giskard $n$ partijen in een $k$-aire boom van commissies, waarbij elke commissie een grootte heeft van $m = O(\log n)$.
   • Bladeren (Niveau 0): Individuele partijen vergelijken hun lokale vectoren met de huidige pivot en delen de resulterende bit-vectoren via secret-sharing met hun toegewezen basiscommissies.
   • Basiscommissies (Niveau 1): Valideren het domein van de gedeelde bits (om te garanderen dat ze 0 of 1 zijn) met behulp van een graad-2 bewijs, aggregeren de shares en delen de partiële sommen weer upward via resharing.
   • Tussenliggende Commissies (Niveaus 2 tot $L-1$): Ontvangen shares van kind-commissies, voeren verifieerbare resharing uit en aggregeren upward.
   • Root-commissie (Niveau $L$): Reconstrueert de globale count in het klaren (in de clear), werkt de pivot bij en broadcast de nieuwe pivot omlaag in de boom voor de volgende iteratie.
3. Cryptografische Primitieven: Het protocol maakt gebruik van Verifiable Secret Sharing (VSS) gebaseerd op het BGW-schema (Asharov en Lindell) om veiligheid tegen kwaadwillende actoren te garanderen. Het gebruikt sub-protocollen voor sharing, vermenigvuldiging en resharing, die bewezen Universally Composable (UC) veilig zijn.

Veiligheids- en Robuustheidsgaranties

• Vertrouwelijkheid: Individuele inputs en tussenliggende counts blijven verborgen; alleen de uiteindelijke geaggregeerde count (gebruikt voor het bijwerken van de pivot) wordt onthuld.
• Byzantijnse Robuustheid: Het protocol tolereert tot $n/4$ Byzantijnse partijen. Het voldoet aan het $(f, \kappa)$-Byzantijnse robuustheidscriterium, wat garandeert dat de output dicht bij het gemiddelde van de eerlijke updates blijft, overeenkomend met de robuustheidsdrempel van de coördinaat-gewijze mediaan.
• Correctheid: De binaire zoekopdracht convergeert naar de mediaan binnen een precisie $q$ na $N_{iter} = \lceil \log_2(2u/q) \rceil$ iteraties.

Belangrijkste Bijdragen

1. Nieuw Protocol: Voorstel van Giskard, een robuust en vertrouwelijk gedecentraliseerd leerprotocol dat in staat is om te schalen naar miljoenen partijen.
2. Theoretische Veiligheid: Een formeel bewijs dat Giskard UC-veilig is in het hybride model, leunend op standaard cryptografische aannames en de veiligheid van zijn sub-protocollen (BA, VSS, etc.).
3. Communicatiecomplexiteitsanalyse: Demonstratie dat de worst-case per-party communicatiecomplexiteit polylogaritmisch is in $n$ ($O(d \cdot N_{iter} \cdot \log^3 n)$), een significante verbetering ten opzichte van concurrenten zoals All-to-All ($O(d \cdot n^2)$) of All-to-Committee ($O(d \cdot n \log^2 n)$).
4. Experimentele Validatie: Uitgebreide evaluatie op MNIST en CIFAR-10 datasets met netwerkomvang tot $n=10^6$.

Experimentele Resultaten

De auteurs evalueerden Giskard tegen twee baseline topologieën: All-to-All (A2A) en All-to-Committee (A2C).

• Schaalbaarheid (Communicatiekosten):

  • Bij $n=10^6$ met een Byzantijnse fractie van 10%, vermindert Giskard de per-party communicatie met ongeveer 1.775 keer vergeleken met A2C en met ordes van grootte vergeleken met A2A.
  • Terwijl A2C de last concentreert op een enkele commissie (wat onpraktisch maakt vanwege bandbreedtebeperkingen op schaal), verdeelt Giskard de last over de boom, waardoor de per-party kosten beheersbaar blijven, zelfs voor $n=10^6$.
  • De geschatte wall-clock tijd voor A2C en A2A bij grote schaal overschrijdt praktische limieten (dagen tot jaren), terwijl Giskard binnen minuten tot uren blijft.

• Model Nut (Robuustheid):

  • Onder vier modelvergiftigingsaanvallen (Label Flipping, Sign Flipping, IPM, ALIE) op non-i.i.d. data, bereikte de binaire zoekmediaan van Giskard een testnauwkeurigheid die vergelijkbaar is met state-of-the-art cleartext robuuste aggregatoren (Trimmed Mean, Median).
  • Op MNIST was het nauwkeurigheidsverschil minder dan 0,4%. Op CIFAR-10 lag het verschil over het algemeen onder de 1,5%, met iets hogere verschillen (tot 2,7%) voor sterk geoptimaliseerde aanvallen die fijnere precisie vereisen.
  • De experimenten identificeerden een scherpe drempel voor het aantal iteraties van de binaire zoekopdracht ($N_{iter}$); het verhogen van het aantal iteraties boven $\approx 10$ leverde geen significante winst in robuustheid op, maar verhoogde de communicatiekosten lineair.

Betekenis en Claims

Het artikel claimt dat Giskard de kloof overbrugt tussen schaalbaarheid en veiligheid in gedecentraliseerd leren. Door een hiërarchische commissiestructuur te combineren met een gespecialiseerde binaire zoekformulering van de mediaan, bereikt Giskard:

• Sub-lineaire communicatie: Het is het eerste protocol dat polylogaritmische per-party communicatie bereikt voor Byzantijnse-robuuste, vertrouwelijke aggregatie in een volledig gedecentraliseerde setting.
• Formele Garanties: In tegenstelling tot heuristische benaderingen biedt Giskard UC-veiligheidsbewijzen en formele robuustheidsgrenzen.
• Praktische Bruikbaarheid: De experimentele resultaten tonen aan dat het protocol levensvatbaar is voor grootschalige implementaties (tot één miljoen deelnemers), waar eerdere MPC-gebaseerde oplossingen computationeel en communicatief onhaalbaar zouden zijn.

De auteurs concluderen dat hoewel het protocol een afruil introduceert tussen het aantal iteraties en precisie, het voorgestelde systeem effectief een balans vindt tussen vertrouwelijkheid, robuustheid en schaalbaarheid, waardoor grootschalig veilig gedecentraliseerd leren praktisch wordt. Toekomstig werk wordt gesuggereerd om computationele varianten te verkennen op basis van cryptografische aannames om de kosten verder te verlagen.