💻 computer science

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

Giskard is a scalable protocol for large-scale decentralized learning that simultaneously ensures data confidentiality and Byzantine robustness by organizing participants into a tree of committees to perform secure, coordinate-wise approximate median aggregation with reduced communication complexity.

Original authors: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive group of people trying to solve a giant puzzle together. Each person has a unique piece of the puzzle (their private data) and wants to help build the final picture (a machine learning model) without ever showing their piece to anyone else. This is the world of decentralized learning.

However, there are two big problems:

The Sneaky Saboteurs (Byzantine Faults): Some people in the group might be trying to ruin the puzzle on purpose. They might submit fake pieces or twisted versions of their pieces to mess up the final image.
The Secret Keepers (Confidentiality): Everyone else wants to keep their puzzle pieces hidden. If they just hand over their pieces, the saboteurs (or even curious neighbors) could peek and figure out private details about the person's life.

Usually, you have to choose one: either you check everyone's pieces to catch the saboteurs (which reveals secrets), or you hide the pieces to keep secrets (which makes it hard to catch saboteurs).

Enter Giskard: The "Tree of Committees" Solution

The paper introduces Giskard, a clever new way to solve this puzzle that handles both problems at once, even when the group grows to a million people. Here is how it works, using simple analogies:

1. The Problem with Old Methods

Imagine if the group tried to solve the puzzle by having everyone stand in a giant circle and shout their answers to everyone else.

The "All-to-All" method: Everyone talks to everyone. If there are 1,000 people, that's a million conversations. If there are a million people, the network crashes. It's too loud and too slow.
The "One Big Committee" method: The group picks a small team of 100 people to do all the checking and counting. While this is faster for the rest of the group, those 100 people get overwhelmed. If the group grows to a million, that small team is still doing all the heavy lifting, and they get crushed by the workload.

2. The Giskard Solution: A Hierarchical Tree

Giskard changes the game by organizing the million people into a tree of small committees.

The Leaves (The People): Instead of everyone talking to everyone, people are grouped into small teams (committees) of about 50–100.
The Branches (The Committees): These small teams talk to each other, then their "parent" teams talk to their parents, all the way up to the top of the tree.
The Root (The Top Committee): At the very top, a final small team makes the decision.

The Magic Trick: The "Secret Counting" Game
Giskard doesn't try to find the "average" (which is easy to trick) or sort everyone's numbers (which is hard to do secretly). Instead, it plays a game of "Guess the Number" using a secret binary search.

The Pivot: The group picks a middle number (a "pivot").
The Secret Vote: Everyone looks at their own number and asks, "Is my number smaller than the pivot?" They don't say "Yes" or "No" out loud. Instead, they write the answer on a piece of paper, tear it up, and hand the pieces to their small committee.
The Committee Count: The small committee puts the pieces back together (using math magic called Secure Multi-Party Computation) to count how many "Yes" votes they have. They don't know who voted yes, just how many.
Passing the Buck: The committee sends their count up the tree. The next level adds up the counts from their children, and so on, until the top committee knows the total number of "Yes" votes from the whole group.
The Update: Based on the total count, the group knows if the "true answer" is higher or lower than the pivot. They pick a new pivot and repeat the game.

3. Why This is a Game-Changer

It's Secret: Because the math is done on "shredded" pieces of paper (secret sharing), no single person or small group can reconstruct anyone's original number. The saboteurs can't see the data.
It's Robust: Even if some people in a small committee are saboteurs trying to lie about the count, the math ensures that as long as the majority of the committee is honest, the final count is correct. The system is designed so that saboteurs can't trick the "Guess the Number" game.
It's Fast (Scalable): This is the biggest win. In the old "One Big Committee" method, if you double the number of people, the workload for the committee gets much heavier. In Giskard, because the work is split up the tree, adding more people barely increases the work for any single person.
- The Paper's Claim: Giskard reduces the communication cost for each person so drastically that it can handle one million participants efficiently. Compared to the closest competitor, Giskard reduces the data each person has to send by 1,775 times when the network is huge.

4. The Results

The authors tested Giskard with up to a million simulated participants.

Speed: It is vastly more efficient than previous methods. While other methods would take years to finish with a million people, Giskard could theoretically finish in a reasonable time (minutes to hours, depending on internet speed).
Accuracy: Even with 25% of the group being saboteurs trying to ruin the model, Giskard still produced a high-quality model, performing just as well as standard methods that don't protect privacy.

In Summary:
Giskard is like organizing a massive, secret, anti-sabotage voting system. Instead of having everyone shout their votes (slow and insecure) or having one tiny group do all the counting (overwhelmed), it builds a tree of small teams that pass secret tallies up the branches. This allows a million people to learn together, keep their secrets safe, and stop saboteurs from ruining the party, all without the network collapsing under the weight of the conversation.

Technical Summary: Giskard

Problem Statement

Decentralized learning offers a privacy-preserving alternative to centralized training by allowing participants to interact peer-to-peer without a trusted central orchestrator. However, these systems face two simultaneous, often conflicting challenges:

Byzantine Robustness: Malicious or faulty nodes may submit arbitrary, manipulated model updates (model poisoning) to corrupt the global model. Defending against this typically requires inspecting and comparing individual contributions to filter outliers (e.g., using coordinate-wise medians or trimmed means).
Confidentiality: Participants must keep their local data and model updates private. Cryptographic techniques like Secure Multi-Party Computation (MPC) hide these updates, but standard robust aggregation functions (which rely on sorting and comparison) are computationally expensive to implement in encrypted form.

Existing solutions address these issues separately or combine them using MPC in ways that do not scale. Prior decentralized MPC approaches often rely on all-to-all communication or delegate computation to a single small committee, resulting in per-node communication complexity that grows linearly or worse with the network size ( $O(n)$ or $O(n \log^2 n)$ ). This creates a fundamental scalability bottleneck for large-scale deployments (e.g., $n \ge 10^4$ ).

Methodology: The Giskard Protocol

Giskard is a protocol designed to achieve both Byzantine robustness and confidentiality in a fully decentralized setting with sub-linear communication complexity. It operates under a static, computationally bounded adversary model where up to $f < n/4$ parties can be corrupted.

Core Technical Insights

Binary Search for Median: Instead of implementing generic sorting circuits (which are expensive in MPC), Giskard reformulates the coordinate-wise median computation as a secure binary search over the value domain. The protocol iteratively narrows the range $[Left, Right]$ by counting how many inputs are less than a pivot $p_t$ . This reduces the problem to a sequence of secure counting operations.
Hierarchical Committee Tree: To distribute the computational load, Giskard organizes $n$ $n$ parties into a $k$ $k$ -ary tree of committees, each of size $m = O(\log n)$ $m = O (lo g n)$ .
- Leaves (Level 0): Individual parties compare their local vectors to the current pivot and secret-share the resulting bit vectors to their assigned base committees.
- Base Committees (Level 1): Validate the domain of shared bits (ensuring they are 0 or 1) using a degree-2 proof, aggregate the shares, and re-share the partial sums upward.
- Intermediate Committees (Levels 2 to $L-1$ ): Receive shares from child committees, perform verifiable resharing, and aggregate upward.
- Root Committee (Level $L$ ): Reconstructs the global count in the clear, updates the pivot, and broadcasts the new pivot down the tree for the next iteration.
Cryptographic Primitives: The protocol utilizes Verifiable Secret Sharing (VSS) based on the BGW scheme (Asharov and Lindell) to ensure security against malicious adversaries. It employs sub-protocols for sharing, multiplication, and resharing, all proven to be Universally Composable (UC) secure.

Security and Robustness Guarantees

Confidentiality: Individual inputs and intermediate counts remain hidden; only the final aggregate count (used to update the pivot) is revealed.
Byzantine Robustness: The protocol tolerates up to $n/4$ Byzantine parties. It satisfies the $(f, \kappa)$ -Byzantine robustness criterion, ensuring the output remains close to the average of honest updates, matching the robustness threshold of the coordinate-wise median.
Correctness: The binary search converges to the median within a precision $q$ after $N_{iter} = \lceil \log_2(2u/q) \rceil$ iterations.

Key Contributions

Novel Protocol: Proposal of Giskard, a robust and confidential decentralized learning protocol capable of scaling to millions of parties.
Theoretical Security: A formal proof that Giskard is UC-secure in the hybrid model, relying on standard cryptographic assumptions and the security of its sub-protocols (BA, VSS, etc.).
Communication Complexity Analysis: Demonstration that the worst-case per-party communication complexity is polylogarithmic in $n$ ( $O(d \cdot N_{iter} \cdot \log^3 n)$ ), a significant improvement over competitors like All-to-All ( $O(d \cdot n^2)$ ) or All-to-Committee ( $O(d \cdot n \log^2 n)$ ).
Experimental Validation: Extensive evaluation on MNIST and CIFAR-10 datasets with network sizes up to $n=10^6$ .

Experimental Results

The authors evaluated Giskard against two baseline topologies: All-to-All (A2A) and All-to-Committee (A2C).

Scalability (Communication Cost):
- At $n=10^6$ with a 10% Byzantine fraction, Giskard reduces per-party communication by approximately 1,775 times compared to A2C and by orders of magnitude compared to A2A.
- While A2C concentrates load on a single committee (making it impractical due to bandwidth limits at scale), Giskard distributes the load across the tree, keeping per-party costs manageable even for $n=10^6$ .
- Estimated wall-clock time for A2C and A2A at large scales exceeds practical limits (days to years), whereas Giskard remains within minutes to hours.
Model Utility (Robustness):
- Under four model poisoning attacks (Label Flipping, Sign Flipping, IPM, ALIE) on non-i.i.d. data, Giskard's binary-search median achieved test accuracy comparable to state-of-the-art cleartext robust aggregators (Trimmed Mean, Median).
- On MNIST, the accuracy gap was below 0.4%. On CIFAR-10, the gap was generally below 1.5%, with slightly higher gaps (up to 2.7%) for highly optimized attacks requiring finer precision.
- The experiments identified a sharp threshold for the number of binary search iterations ( $N_{iter}$ ); increasing iterations beyond $\approx 10$ yielded no significant robustness gains but linearly increased communication costs.

Significance and Claims

The paper claims that Giskard bridges the gap between scalability and security in decentralized learning. By combining a hierarchical committee structure with a specialized binary-search formulation of the median, Giskard achieves:

Sub-linear communication: It is the first protocol to achieve polylogarithmic per-party communication for Byzantine-robust, confidential aggregation in a fully decentralized setting.
Formal Guarantees: Unlike heuristic approaches, Giskard provides UC-security proofs and formal robustness bounds.
Practicality: The experimental results demonstrate that the protocol is viable for large-scale deployments (up to one million participants) where previous MPC-based solutions would be computationally and communicatively infeasible.

The authors conclude that while the protocol introduces a trade-off between iteration count and precision, the proposed system effectively balances confidentiality, robustness, and scalability, making large-scale secure decentralized learning practical. Future work is suggested to explore computational variants based on cryptographic assumptions to further reduce costs.