💻 computer science

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

Giskard 是一个用于大规模去中心化学习的可扩展协议，它通过将参与者组织成一个执行安全、逐分量近似中值聚合且具有降低通信复杂度的树状委员会结构，从而同时确保数据机密性和拜占庭鲁棒性。

原作者： Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Ousmane Touat, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，一大群人正试图共同完成一个巨大的拼图。每个人都拥有一块独特的拼图碎片（他们的私有数据），并且都想协助构建最终的图像（机器学习模型），但绝不想让任何人看到自己的那块碎片。这就是**去中心化学习（Decentralized Learning）**的世界。

然而，这里有两个大问题：

潜伏的破坏者（拜占庭故障/Byzantine Faults）： 这群人中有些人可能会故意破坏拼图。他们可能会提交虚假的或扭曲的碎片版本，以此来搞砸最终的图像。
秘密守护者（机密性/Confidentiality）： 其他每个人都希望隐藏自己的拼图碎片。如果他们直接交出碎片，破坏者（甚至好奇的邻居）就可能窥探并查出关于此人生活的隐私细节。

通常情况下，你必须做出选择：要么检查每个人的碎片以抓捕破坏者（这会泄露秘密），要么隐藏碎片以保护秘密（但这会让抓捕破坏者变得困难）。

走进 Giskard：一种“委员会之树”的解决方案

这篇论文介绍了一种名为 Giskard 的聪明方法，它能同时解决这两个问题，即使是在规模达到一百万人的情况下也是如此。以下是它的工作原理，我们使用简单的类比来解释：

1. 旧方法的缺陷

想象一下，如果这群人试图通过让所有人站成一个巨大的圆圈，并向所有人喊出自己的答案来解决拼图。

“全对全”（All-to-All）方法： 每个人都和所有人交谈。如果有 1,000 人，就会产生一百万次对话。如果有 100 万人，网络就会崩溃。这太吵闹也太慢了。
“单一大型委员会”（One Big Committee）方法： 这一组人选出 100 人的小团队来负责所有的检查和计数工作。虽然对于其他成员来说这更快了，但那 100 个人会被压垮。如果人数增加到 100 万，这个小团队仍然要承担所有的重任，他们会被繁重的工作压垮。

2. Giskard 的解决方案：层级化树状结构

Giskard 通过将这 100 万人组织成一个由小委员会组成的树状结构来改变了游戏规则。

叶子节点（普通人）： 与其让每个人都和所有人交谈，不如将人们分组为约 50–100 人的小团队（委员会）。
树枝（委员会）： 这些小团队彼此交谈，然后他们的“父级”团队与他们的“父级”交谈，一直向上延伸到树顶。
根节点（顶层委员会）： 在最顶端，最后一个小团队做出最终决定。

神奇的技巧：“猜数字”游戏
Giskard 并不试图寻找“平均值”（这很容易被欺骗）或对所有数字进行排序（这在秘密状态下很难实现）。相反，它利用秘密二分查找来玩一场**“猜数字”**的游戏。

基准值（The Pivot）： 团队选择一个中间数字（一个“基准值”）。
秘密投票： 每个人看一眼自己的数字，并问自己：“我的数字是否小于这个基准值？”他们不会大声说“是”或“不是”。相反，他们把答案写在纸上，撕碎，然后把碎片交给他们所属的小委员会。
委员会计数： 小委员会利用数学魔法（称为安全多方计算/Secure Multi-Party Computation）将碎片重新组合起来，统计有多少个“是”的票数。他们不知道是谁投了“是”，只知道“有多少人”投了“是”。
逐级传递： 委员会将他们的计数结果向上层传递。下一层会将来自其子节点的计数相加，以此类推，直到顶层委员会知道整个群体中总共有多少个“是”的票数。
更新： 根据总计数，小组可以知道“真实答案”是高于还是低于当前的基准值。他们选取一个新的基准值并重复游戏。

3. 为什么这是一个游戏规则的改变者

它是保密的： 因为所有的数学运算都是在“粉碎”后的纸片上进行的（秘密共享），没有任何一个人或小组能够重建任何人的原始数字。破坏者无法看到数据。
它是鲁棒的： 即使小委员会中的某些人是试图通过撒谎来破坏计数的破坏者，数学也能确保只要委员会中的大多数人是诚实的，最终的计数就是正确的。该系统经过设计，使得破坏者无法通过这种方式欺骗“猜数字”游戏。
它是快速的（可扩展性）： 这是最大的胜利。在旧有的“单一大型委员会”方法中，如果人数翻倍，委员会的工作量会变得沉重得多。而在 Giskard 中，由于工作被分散到了整棵树上，增加人数几乎不会增加任何单个人的工作量。
- 论文的说法： Giskard 大幅降低了每个人的通信成本，使其能够高效处理一百万人的参与者。与最接近的竞争对手相比，当网络规模巨大时，Giskard 将每个人需要发送的数据量减少了 1,775 倍。

4. 结果

作者使用高达一百万个模拟参与者对 Giskard 进行了测试。

速度： 它比以往的方法效率高得多。当面对一百万人时，其他方法可能需要数年才能完成，而 Giskard 理论上可以在合理的时间内完成（取决于互联网速度，约为几分钟到几小时）。
准确性： 即使有 25% 的成员是试图破坏模型的破坏者，Giskard 仍然能产生高质量的模型，其表现与那些不保护隐私的标准方法不相上下。

总结：
Giskard 就像是在组织一个大规模、秘密且具备反破坏能力的投票系统。它不是让每个人都大声喊出他们的选票（既慢又不安全），也不是让一个微小的群体承担所有的计数工作（会被压垮），而是建立了一个由小团队组成的树状结构，通过树枝传递秘密统计数据。这使得一百万人可以共同学习、保护自己的秘密，并阻止破坏者搞砸聚会，而不会导致网络因对话量过大而崩溃。

技术摘要：Giskard

问题陈述

去中心化学习通过允许参与者在没有可信中央编排器的情况下进行点对点交互，提供了一种保护隐私的替代方案。然而，这些系统面临着两个同时存在且往往相互冲突的挑战：

拜占庭鲁棒性（Byzantine Robustness）： 恶意或故障节点可能会提交任意的、经过操纵的模型更新（模型投毒）以破坏全局模型。防御此类攻击通常需要检查并比较单个贡献值，以过滤异常值（例如，使用逐坐标中位数或修剪均值）。
机密性（Confidentiality）： 参与者必须保持其本地数据和模型更新的私密性。加密技术（如安全多方计算，MPC）可以隐藏这些更新，但标准的鲁棒聚合函数（依赖于排序和比较）在加密形式下的实现计算成本极高。

现有的解决方案要么分别解决这些问题，要么以无法扩展的方式结合 MPC。先前的去中心化 MPC 方法通常依赖于全对全（all-to-all）通信，或将计算委托给单个小型委员会，这导致每个节点的通信复杂度随网络规模线性或更糟地增长（ $O(n)$ 或 $O(n \log^2 n)$ ）。这为大规模部署（例如 $n \ge 10^4$ ）造成了根本性的可扩展性瓶颈。

方法论：Giskard 协议

Giskard 是一个旨在在完全去中心化的设置下，以亚线性通信复杂度实现拜占庭鲁棒性和机密性的协议。它运行在静态、计算受限的对手模型下，其中最多有 $f < n/4$ 个参与者可能被破坏。

核心技术洞察

中位数的二分查找（Binary Search for Median）： Giskard 没有实现通用的排序电路（这在 MPC 中非常昂贵），而是将逐坐标中位数的计算重新表述为在值域上的安全二分查找。该协议通过迭代缩小 $[Left, Right]$ 范围，统计小于给定枢轴（pivot） $p_t$ 的输入数量。这使得问题简化为一系列安全计数操作。
层级化委员会树（Hierarchical Committee Tree）： 为了分配计算负载，Giskard 将 $n$ $n$ 个参与者组织成一个由大小为 $m = O(\log n)$ $m = O (lo g n)$ 的委员会组成的 $k$ $k$ 叉树。
- 叶子节点（第 0 层）： 个人参与者将其本地向量与当前枢轴进行比较，并将生成的位向量（bit vectors）通过安全份额（secret-share）发送给其分配的基础委员会。
- 基础委员会（第 1 层）： 使用二阶证明验证共享位的定义域（确保其为 0 或 1），聚合份额，并将部分和向上重新共享。
- 中间委员会（第 2 层至 $L-1$ 层）： 接收来自子委员会的份额，执行可验证的重共享（verifiable resharing），并向上聚合。
- 根委员会（第 $L$ 层）： 在明文中重建全局计数，更新枢轴，并将新的枢轴向下广播到整棵树进行下一次迭代。
密码学原语： 协议利用基于 BGW 方案（Asharov 和 Lindell）的可验证秘密共享（VSS）来确保针对恶意对手的安全性。它采用了用于共享、乘法和重共享的子协议，这些子协议均被证明是通用可组合（UC）安全的。

安全性与鲁棒性保证

机密性： 个体输入和中间计数保持隐藏；仅最终的聚合计数（用于更新枢로）会被揭示。
拜占庭鲁棒性： 协议可以容忍高达 $n/4$ 的拜占庭参与者。它满足 $(f, \kappa)$ -拜占庭鲁棒性准则，确保输出结果接近诚实更新的平均值，达到了逐坐标中位数的鲁棒性阈值。
正确性： 二分查找将在 $N_{iter} = \lceil \log_2(2u/q) \rceil$ 次迭代后收敛至精度 $q$ 范围内。

核心贡献

新颖协议： 提出了 Giskard，一种能够扩展至数百万个参与者的鲁棒且机密的去中心化学习协议。
理论安全性： 提供了一个形式化证明，证明 Giskard 在混合模型下是 UC 安全的，该证明依赖于标准的密码学假设及其子协议（BA、VSS 等）的安全性。
通信复杂度分析： 证明了 Giskard 的最坏情况每参与者通信复杂度是 $n$ 的多项式对数级别（ $O(d \cdot N_{iter} \cdot \log^3 n)$ ），相比于竞争对手如全对全（ $O(d \cdot n^2)$ ）或全对委员会（ $O(d \cdot n \log^2 n)$ ）有了显著改进。
实验验证： 在 MNIST 和 CIFAR-10 数据集上，针对网络规模高达 $n=10^6$ 的情况进行了广泛评估。

实验结果

作者将 Giskard 与两种基准拓扑结构进行了对比：全对全（All-to-All, A2A）和全对委员会（All-to-Committee, A2C）。

可扩展性（通信成本）：
- 在 $n=10^6$ 且拜占庭比例为 10% 时，Giskard 比 A2C 减少了约 1,775 倍 的每参与者通信量，且比 A2A 低了数个数量级。
- 虽然 A2C 会将负载集中在单个委员会上（由于大规模下的带宽限制，这在实践中是不可行的），但 Giskgard 通过在树结构中分布负载，即使在 $n=10^6$ 时也能保持可控的每参与者成本。
- 在大规模场景下，A2C 和 A2A 的估计实际运行时间超过了实际限制（数天甚至数年），而 Giskard 仍能保持在几分钟到几小时内。
模型效用（鲁棒性）：
- 在非独立同分布（non-i.i.d.）数据上针对四种模型投毒攻击（标签翻转、符号翻转、IPM、ALIE）进行测试时，Giskard 的二分查找中位数达到了与最先进的明文鲁棒聚合器（修剪均值、中位数）相当的测试准确率。
- 在 MNIST 上，准确率差距低于 0.4%。在 CIFAR-10 上，差距通常低于 1.5%，对于需要更高精度的优化攻击，差距略高（最高达 2.7%）。
- 实验确定了二分查找迭代次数（ $N_{iter}$ ）的一个锐利阈值；当迭代次数增加到 $\approx 10$ 以上时，并未带来显著的鲁棒性提升，但线性增加了通信成本。

意义与主张

论文声称 Giskard 弥合了去中心化学习中可扩展性与安全性之间的鸿沟。通过结合层级化委员会结构与专门的二分查找中位数公式，Giskard 实现了：

亚线性通信： 它是第一个在完全去中心化设置下实现拜占庭鲁棒、机密聚合且具有多项式对数级每参与者通信复杂度的协议。
形式化保证： 不同于启发式方法，Giskard 提供了 UC 安全证明和形式化的鲁棒性界限。
实用性： 实验结果表明，该协议对于大规模部署（高达一百万个参与者）是可行的，而之前的基于 MPC 的解决方案在计算和通信上都难以实现。

作者总结道，尽管协议在迭代次数与精度之间存在权衡，但所提出的系统有效地平衡了机密性、鲁棒性和可扩展性，使大规模安全去中心化学习变得切实可行。未来的工作建议探索基于计算假设的变体，以进一步降低成本。