💻 computer science

Giskard : Byzantine Robust and Confidential Aggregation for Large-Scale Decentralized Learning

Giskard ist ein skalierbares Protokoll für dezentrales Lernen in großem Maßstab, das gleichzeitig die Vertraulichkeit der Daten und die Byzantinische Robustheit gewährleistet, indem es Teilnehmer in einem Baum aus Komitees organisiert, um eine sichere, koordinatenweise approximative Median-Aggregation mit reduzierter Kommunikationskomplexität durchzuführen.

Ursprüngliche Autoren: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

Veröffentlicht 2026-06-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine riesige Gruppe von Menschen vor, die gemeinsam ein gigantisches Puzzle lösen wollen. Jeder Mensch besitzt ein einzigartiges Teil des Puzzles (seine privaten Daten) und möchte helfen, das fertige Bild (ein maschinelles Lernmodell) zu erstellen, ohne dabei sein Teil jemals jemand anderem zu zeigen. Das ist die Welt des dezentralen Lernens.

Es gibt jedoch zwei große Probleme:

Die heimlichen Saboteure (Byzantine Faults): Einige Leute in der Gruppe könnten versuchen, das Puzzle absichtlich zu ruinieren. Sie könnten falsche Teile oder verdrehte Versionen ihrer Teile einreichen, um das endgültliche Bild zu manipulieren.
Die Geheimnisbewahrer (Vertraulichkeit): Alle anderen wollen ihre Puzzleteile verborgen halten. Wenn sie ihre Teile einfach übergeben würden, könnten die Saboteure (oder auch neugierige Nachbarn) hineinspähen und private Details aus dem Leben der Person herausfinden.

Normalerweise muss man sich entscheiden: Entweder man überprüft alle Teile, um die Saboteure zu fangen (was Geheimnisse preisgibt), oder man verbirgt die Teile, um Geheimnisse zu wahren (was es schwierig macht, Saboteure zu entlarven).

Hier kommt Giskard ins Spiel: Die „Baum der Komitees“-Lösung

Das Paper stellt Giskard vor, eine clevere neue Methode, die beide Probleme gleichzeitig löst, selbst wenn die Gruppe auf eine Million Menschen anwächst. So funktioniert es, unter Verwendung einfacher Analogien:

1. Das Problem mit alten Methoden

Stellen Sie sich vor, die Gruppe versuchte, das Puzzle zu lösen, indem alle in einem riesigen Kreis stehen und ihre Antworten an alle anderen schreien.

Die „All-to-All“-Methode: Jeder spricht mit jedem. Wenn es 1.000 Menschen sind, sind das eine Million Gespräche. Wenn es eine Million Menschen sind, stürzt das Netzwerk ab. Es ist zu laut und zu langsam.
Die „Ein großes Komitee“-Methode: Die Gruppe wählt ein kleines Team von 100 Personen aus, die das gesamte Prüfen und Zählen übernehmen. Während dies für den Rest der Gruppe schneller ist, werden diese 100 Personen überfordert. Wenn die Gruppe auf eine Million anwächst, muss dieses kleine Team immer noch die gesamte schwere Arbeit leisten, und sie werden unter der Last zusammenbrechen.

2. Die Giskard-Lösung: Ein hierarchischer Baum

Giskard verändert das Spiel, indem es die Million Menschen in einen Baum aus kleinen Komitees organisiert.

Die Blätter (Die Menschen): Anstatt dass jeder mit jedem spricht, werden die Menschen in kleine Teams (Komitees) von etwa 50–100 Personen gruppiert.
Die Zweige (Die Komitees): Diese kleinen Teams sprechen miteinander, dann sprechen ihre „Eltern-Teams“ mit ihren Eltern, und so weiter bis nach oben im Baum.
Die Wurzel (Das oberste Komitee): Ganz oben trifft ein letztes kleines Team die Entscheidung.

Der magische Trick: Das „Geheimnisvolle Zahlenraten“-Spiel
Giskard versucht nicht, den „Durchschnitt“ zu finden (was leicht zu manipulieren ist) oder die Zahlen aller Teilnehmer zu sortieren (was schwer geheim zu halten ist). Stattdessen spielt es ein „Rate das Zahl“-Spiel mittels einer geheimen binären Suche.

Der Pivot: Die Gruppe wählt eine mittlere Zahl (einen „Pivot“).
Die geheime Abstimmung: Jeder schaut auf seine eigene Zahl und fragt sich: „Ist meine Zahl kleiner als der Pivot?“ Er sagt nicht laut „Ja“ oder „Nein“. Stattdessen schreibt er die Antwort auf ein Stück Papier, zerreißt es und übergibt die Schnipsel an sein kleines Komitee.
Die Komitee-Zählung: Das kleine Komitee setzt die Schnipsel mithilfe von mathematischer Magie (genannt Secure Multi-Party Computation) wieder zusammen, um zu zählen, wie viele „Ja“-Stimmen sie haben. Sie wissen nicht, wer mit „Ja“ gestimmt hat, sondern nur, wie viele es sind.
Die Weitergabe: Das Komitee sendet seine Zählung den Baum hinauf. Die nächste Ebene addiert die Zählungen ihrer Kinder, und so weiter, bis das oberste Komitee die Gesamtzahl der „Ja“-Stimmen der gesamten Gruppe kennt.
Das Update: Basierend auf der Gesamtzahl weiß die Gruppe, ob die „wahre Antwort“ höher oder niedriger als der Pivot ist. Sie wählen einen neuen Pivot und wiederholen das Spiel.

3. Warum dies ein Game-Changer ist

Es ist geheim: Da die Mathematik auf „zerteilten“ Papierstücken (Secret Sharing) basiert, kann niemand oder kein kleines Team die ursprüngliche Zahl eines Einzelnen rekonstruieren. Die Saboteure können die Daten nicht sehen.
Es ist robust: Selbst wenn einige Leute in einem kleinen Komitee Saboteure sind, die versuchen, die Zählung zu manipulieren, stellt die Mathematik sicher, dass die endgültige Zählung korrekt ist, solange die Mehrheit des Komitees ehrlich ist. Das System ist so konzipiert, dass Saboteure das „Rate das Zahl“-Spiel nicht austricksen können.
Es ist schnell (skalierbar): Dies ist der größte Gewinn. In der alten „Ein großes Komitee“-Methode steigt, wenn man die Anzahl der Menschen verdoppelt, die Arbeitslast für das Komitee massiv an. In Giskard wird die Arbeit durch die Aufteilung im Baum verteilt, sodass das Hinzufügen von mehr Menschen die Arbeit für den Einzelnen kaum erhöht.
- Die Behauptung des Papers: Giskard reduziert die Kommunikationskosten für jeden Teilnehmer so drastisch, dass es eine Million Teilnehmer effizient bewältigen kann. Im Vergleich zum engsten Konkurrenten reduziert Giskard die Datenmenge, die jede Person senden muss, um das 1.775-fache, wenn das Netzwerk sehr groß ist.

4. Die Ergebnisse

Die Autoren haben Giskard mit bis zu einer Million simulierten Teilnehmern getestet.

Geschwindigkeit: Es ist weitaus effizienter als bisherige Methoden. Während andere Methoden mit einer Million Menschen Jahre zum Abschluss benötigen würden, könnte Giskard theoretisch in einer angemessenen Zeit fertig werden (Minuten bis Stunden, abhängig von der Internetgeschwindigkeit).
Genauigkeit: Selbst wenn 25 % der Gruppe Saboteure sind, die versuchen, das Modell zu ruinieren, liefert Giskard immer noch ein qualitativ hochwertiges Modell, das fast genauso gut abschneidet wie Standardmethoden, die keinen Datenschutz bieten.

Zusammenfassend:
Giskard ist wie die Organisation eines massiven, geheimen, manipulationssicheren Abstimmungssystems. Anstatt dass alle ihre Stimmen laut rufen (langsam und unsicher) oder ein winziges Team die ganze Arbeit machen lässt (überfordert), baut es einen Baum aus kleinen Teams, die geheime Zwischenstände die Zweige hinaufreichen. Dies ermöglicht es einer Million Menschen, gemeinsam zu lernen, ihre Geheimnisse zu bewahren und Saboteure zu stoppen, die die Party ruin könnten – und das alles, ohne dass das Netzwerk unter der Last des Gesprächs zusammenbricht.

Technisches Resümee: Giskard

Problemstellung

Dezentrales Lernen bietet eine datenschutzfreundliche Alternative zum zentralisierten Training, indem es Teilnehmern ermöglicht, Peer-to-Peer ohne einen vertrauenswürdigen zentralen Orchestrator zu interagieren. Diese Systeme stehen jedoch vor zwei gleichzeitigen, oft gegensätzlichen Herausforderungen:

Byzantinische Robustheit: Böswillige oder fehlerhafte Knoten können beliebige, manipulierte Modellaktualisierungen (Model Poisoning) einreichen, um das globale Modell zu korrumpieren. Die Abwehr erfordert typischerweise die Inspektion und den Vergleich einzelner Beiträge, um Ausreißer zu filtern (z. B. durch koordinatenweise Mediane oder getrimmte Mittelwerte).
Vertraulichkeit: Teilnehmer müssen ihre lokalen Daten und Modellaktualisierungen privat halten. Kryptografische Techniken wie Secure Multi-Party Computation (MPC) verbergen diese Aktualisierungen, aber Standard-Aggregationfunktionen für robuste Verfahren (die auf Sortierung und Vergleich basieren) sind in verschlüsselter Form rechentechnisch sehr aufwendig.

Bestehende Lösungen adressieren diese Probleme entweder separat oder kombinieren sie mittels MPC auf eine Weise, die nicht skaliert. Viele bisherige dezentrale MPC-Ansätze verlassen sich auf All-to-All-Kommunikation oder delegieren die Berechnung an ein einzelnes kleines Komitee, was zu einer pro Knoten resultierenden Kommunikationskomplexität führt, die linear oder schlimmer mit der Netzwerkgröße wächst ( $O(n)$ oder $O(n \log^2 n)$ ). Dies schafft einen fundamentalen Skalierbarkeitsengpass für groß angelegte Einsätze (z. B. $n \ge 10^4$ ).

Methodik: Das Giskard-Protokoll

Giskard ist ein Protokoll, das darauf ausgelegt ist, sowohl byzantinische Robustheit als auch Vertraulichkeit in einem vollständig dezentralen Setting mit sublinearer Kommunikationskomplexität zu erreichen. Es operiert unter einem statischen, rechnerisch beschränkten Adversary-Modell, bei dem bis zu $f < n/4$ Parteien korrumpiert sein können.

Kerntechnische Erkenntnisse

Binäre Suche für den Median: Anstatt teure generische Sortierschaltkreise in MPC zu implementieren, formuliert Giskard die koordinatenweise Median-Berechnung als sichere binäre Suche über den Wertebereich um. Das Protokoll verengt iterativ das Intervall $[Left, Right]$, indem es zählt, wie viele Eingaben kleiner als ein Pivot $p_t$ sind. Dies reduziert das Problem auf eine Sequenz von sicheren Zählovorgängen.
Hierarchischer Komitee-Baum: Um die Rechenlast zu verteilen, organisiert Giskard $n$ $n$ Parteien in einem $k$ $k$ -ary Baum aus Komitees, wobei jedes eine Größe von $m = O(\log n)$ $m = O (lo g n)$ hat.
- Blätter (Level 0): Einzelne Parteien vergleichen ihre lokalen Vektoren mit dem aktuellen Pivot und teilen die resultierenden Bit-Vektoren mittels Secret Sharing an ihre zugewiesenen Basis-Komitees weiter.
- Basis-Komitees (Level 1): Validieren den Bereich der geteilten Bits (stellen sicher, dass sie 0 oder 1 sind) mittels eines Grad-2-Beweises, aggregieren die Anteile und teilen die Teilsummen nach oben hin neu auf.
- Zwischen-Komitees (Levels 2 bis $L-1$ ): Erhalten Anteile von Kind-Komitees, führen eine verifizierbare Neuverteilung (Resharing) durch und aggregieren nach oben.
- Root-Komitee (Level $L$ ): Rekonstruiert den globalen Zähler im Klartext, aktualisiert den Pivot und überträgt den neuen Pivot nach unten durch den Baum für die nächste Iteration.
Kryptografische Primitiven: Das Protokoll nutzt Verifiable Secret Sharing (VSS) basierend auf dem BGW-Schema (Asharov und Lindell), um Sicherheit gegen bösartige Akteure zu gewährleisten. Es verwendet Sub-Protokolle für das Teilen, Multiplizieren und Resharing, die als Universally Composable (UC) sicher bewiesen sind.

Sicherheits- und Robustheitsgarantien

Vertraulichkeit: Einzelne Eingaben und Zwischenzähler bleiben verborgen; nur der finale aggregierte Zähler (der zur Aktualisierung des Pivots verwendet wird) wird offengelegt.
Byzantinische Robustheit: Das Protokoll toleriert bis zu $n/4$ byzantinische Parteien. Es erfüllt das $(f, \kappa)$ -Byzantine-Robustness-Kriterium und stellt sicher, dass das Ergebnis nahe am Durchschnitt der ehrlichen Updates bleibt, was dem Robustheitsschwellenwert des koordinatenweisen Median entspricht.
Korrektheit: Die binäre Suche konvergiert nach $N_{iter} = \lceil \log_2(2u/q) \rceil$ Iterationen gegen den Median mit einer Präzision $q$ .

Wichtigste Beiträge

Neuartiges Protokoll: Vorschlag von Giskard, einem robusten und vertraulichen dezentralen Lernprotokoll, das in der Lage ist, auf Millionen von Parteien zu skalieren.
Theoretische Sicherheit: Ein formaler Beweis, dass Giskard im Hybrid-Modell UC-sicher ist, basierend auf Standard-Kryptografie-Annahmen und der Sicherheit seiner Sub-Protokolle (BA, VSS, etc.).
Analyse der Kommunikationskomplexität: Nachweis, dass die Worst-Case-Kommunikationskomplexität pro Partei polylogarithmisch in $n$ ist ( $O(d \cdot N_{iter} \cdot \log^3 n)$ ), was eine signifikante Verbesserung gegenüber Wettbewerbern wie All-to-All ( $O(d \cdot n^2)$ ) oder All-to-Committee ( $O(d \cdot n \log^2 n)$ ) darstellt.
Experimentelle Validierung: Umfangreiche Evaluierung auf MNIST- und CIFAR-10-Datensätzen mit Netzwerkgrößen von bis zu $n=10^6$ .

Experimentelle Ergebnisse

Die Autoren evaluierten Giskard gegen zwei Baseline-Topologien: All-to-All (A2A) und All-to-Committee (A2C).

Skalierbarkeit (Kommunikationskosten):
- Bei $n=10^6$ mit einem byzantinischen Anteil von 10 % reduziert Giskard die Kommunikation pro Partei um etwa das 1.775-Fache im Vergleich zu A2C und um Größenordnungen im Vergleich zu A2A.
- Während A2C die Last auf ein einzelnes Komitee konzentriert (was aufgrund von Bandbreitenbeschränkungen bei Skalierung unpraktisch ist), verteilt Giskard die Last über den Baum und hält die Kosten pro Partei auch für $n=10^6$ handhabbar.
- Die geschätzte Wanduhrzeit für A2C und A2A bei großen Skalen übersteigt praktische Grenzen (Tage bis Jahre), während Giskard innerhalb von Minuten bis Stunden bleibt.
Modellnutzen (Robustheit):
- Unter vier Model-Poisoning-Angriffen (Label Flipping, Sign Flipping, IPM, ALIE) auf Non-i.i.d.-Daten erreichte der binär suchende Median von Giskard eine Testgenauigkeit, die mit State-of-the-Art Cleartext-Robust-Aggregatoren (Trimmed Mean, Median) vergleichbar ist.
- Auf MNIST lag die Genauigkeitsdifferenz unter 0,4 %. Auf CIFAR-10 lag die Differenz im Allgemeinen unter 1,5 %, mit etwas höheren Abweichungen (bis zu 2,7 %) bei hochoptimierten Angriffen, die eine feinere Präzision erfordern.
- Die Experimente identifizierten einen scharfen Schwellenwert für die Anzahl der binären Suchiterationen ( $N_{iter}$ ); eine Erhöhung der Iterationen über $\approx 10$ hinaus lieferte keine signifikanten Robustheitsgewinne, steigerte aber die Kommunikationskosten linear.

Bedeutung und Ansprüche

Das Paper behauptet, dass Giskard die Lücke zwischen Skalierbarkeit und Sicherheit im dezentralen Lernen schließt. Durch die Kombination einer hierarchischen Komitee-Struktur mit einer spezialisierten Binärsuch-Formulierung des Medians erreicht Giskard:

Sublineare Kommunikation: Es ist das erste Protokoll, das eine polylogarithmische pro-ParteI-Kommunikation für byzantinisch-robuste, vertrauliche Aggregation in einem vollständig dezentralen Setting erreicht.
Formale Garantien: Im Gegensatz zu heuristischen Ansätzen liefert Giskard UC-Sicherheitsbeweise und formale Robustheitsgrenzen.
Praktikabilität: Die experimentellen Ergebnisse zeigen, dass das Protokoll für groß angelegte Einsätze (bis zu einer Million Teilnehmer) geeignet ist, bei denen frühere MPC-basierte Lösungen rechentechnisch oder kommunikativ nicht mehr machbar wären.

Die Autoren kommen zu dem Schluss, dass das Protokoll zwar einen Trade-off zwischen Iterationsanzahl und Präzision einführt, das vorgeschlagene System jedoch Vertraulichkeit, Robustheit und Skalierbarkeit effektiv ausbalanciert und somit groß angelegtes sicheres dezentrales Lernen praktikabel macht. Zukünftige Arbeiten sollen computergestützte Varianten basierend auf kryptografischen Annahmen untersuchen, um die Kosten weiter zu senken.